Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Синхронизация






При работе параллельного приложения его потокам часто требуется способ связи друг с другом для координации своих действий. Пример такой связи — передача данных через каналы. Однако простейшей формой связи является синхронизация (synchronization). Синхронизация означает способность пото­ка добровольно приостанавливать свое исполнение и ожидать, пока не завер­шится выполнение некоторой операции другим потоком.

В приведенном выше примере с компилятором препроцессор считывает исходный код на С и помещает результаты его обработки в буфер памяти, который он использует совместно с компилятором. Последний принимает ре­зультаты препроцессора в качестве исходных данных, выполняет компиляцию и генерирует объектный код. После запуска программы поток компилятора должен ждать, пока поток препроцессора поместит что-либо в буфер, и лишь затем читать данные. Аналогично, когда весь буфер заполнен, препроцессор должен ждать, пока компилятор не выберет данные из буфера, прежде чем записывать туда новую информацию.

Все ОС, поддерживающие многозадачность или мультипроцессорную обработку, должны предоставлять потокам способ ожидания того, что другой поток что-либо сделает: например, освободит накопитель на магнитной ленте или закончит запись в совместно используемый буфер памяти. ОС должна так­же дать потоку возможность сообщить другим потокам об окончании выпол­нения операции. Получив такое уведомление, ожидающий поток может про­должить выполнение.

Средства ожидания и сообщения реализованы в исполнительной систе­ме NT как часть объектной архитектуры. Синхронизационные объекты (synchronization objects) — это объекты исполнительной системы, при помо­щи которых поток синхронизирует свое выполнение. К их числу относятся следующие объекты

• Процесс

• Поток

• Файл

• Событие

• Пара событий

• Семафор

• Таймер

• Мутант

Первые три из перечисленных выше объектов выполняют и другие функ­ции, в то время как последние пять существуют исключительно для поддержки синхронизации. При помощи этих объектов исполнительной системы потоки могут координировать свое выполнение с разнообразными происшествиями в системе, используя различные правила для различных ситуаций.

В любой момент времени синхронизационный объект находится в одном из двух состояний: свободен (signaled state) либо занят (nonsignaled state). Состояние " свободен" определено по-разному для разных объектов. Объект-поток находится в состоянии " занят" все время существования, но устанавливается системой в состояние " свободен", когда его выполнение завершается. Ана­логично, ядро устанавливает процесс в состояние " свободен", когда завершает­ся его последний поток. В противоположность этому, объект-таймер " сраба­тывает" через заданное время (по истечении этого времени ядро устанавливает объект-таймер в состояние " свободен").

Для синхронизации с объектом поток вызывает один из системных сервисов ожидания, предоставляемых диспетчером объектов, и передает описа­тель данного объекта. Поток может ждать один или несколько объектов, а так­же задать отмену ожидания, если оно не закончилось за некоторый промежу­ток времени. Всякий раз, когда ядро устанавливает объект в состояние " свобо­ден", оно проверяет, есть ли потоки, ожидающие этот объект. Если такие пото­ки есть, то ядро выводит один или несколько из них из состояния ожидания, и они могут продолжить выполнение.

При выборе механизма синхронизации следует учитывать правила, уп­равляющие поведением различных синхронизационных объектов. Закончится ли ожидание потока, когда объект, у которого он ждет, будет переведен в со­стояние " свободен", зависит от типа объекта, как показано в табл. 4-3.

Таблица 4-3. Определения состояния " свободен"

Тип объекта Устанавливается в состояние " свободен", когда: Как влияет на ожидающие потоки:
Процесс завершается последний поток все освобождаются
Поток завершается исполнение потока то же
Файл завершается операция ввода-вывода — " —
Событие поток устанавливает событие — " —
Пара событий выделенный поток клиента или сервера устанавливает событие освобождается другой выделенный поток
Семафор счетчик семафора доходит до нуля все освобождаются
Таймер наступает заданное время или то же
Мутант истекает временной интервал поток освобождает мутант освобождается один поток

 

В большинстве случаев, когда объект устанавливается в состояние " сво­боден", все ожидающие потоки немедленно освобождаются. Например, объект-событие используется для оповещения о том, что произошло некото­рое событие. Когда объект-событие устанавливается в состояние " свободен", все ожидающие его потоки освобождаются. Исключением является поток, ожидающий одновременно более одного объекта; такому потоку, возможно, потребуется продолжать ожидание до тех пор, пока и остальные объекты не станут свободными.

В отличие от объекта-события, для объекта-мутанта (для программистов в Win32 он видим как объект-мьютекс) определено понятие владения им. Объект-мутант применяется, чтобы установить взаимоисключающий доступ к ресурсу, и в данный момент времени владеть им может не более одного потока. Когда мутант освобождается, ядро устанавливает его в состояние " свободен", после чего выбирает для исполнения один из потоков, ожидающих его. Поток, выбранный ядром, завладевает мутантом, а все остальные потоки продолжают ждать

Семантика синхронизации исполнительной системы NT видима про­граммистам Win32 посредством функций API WaitForSingleObject() и WaitFor-MultipleObjects(), которые реализованы при помощи вызовов аналогичных си­стемных сервисов диспетчера объектов NT. Поток в приложении Win32 может синхронизироваться с такими объектами Win32, как процесс, поток, событие, семафор, мьютекс или файл. В качестве примера рассмотрим синхронизацию потока в программе электронной таблицы с другим потоком этой программы. Предположим, что у приложения есть основной поток, выполняющий обыч­ные функции работы с электронной таблицей, и вспомогательный поток, вы­водящий файлы электронной таблицы на принтер. Теперь допустим, что пользователь отправляет электронную таблицу на печать и, прежде чем печать завершится, вводит команду выхода из программы. Основной поток, который получает запрос на выход из программы, не завершает процесс немедленно (хотя он может убрать окно программы с экрана). Вместо этого он вызывает функцию WaitForSingleObject(), чтобы подождать, пока поток спулера не за­кончит печать и не завершится. После завершения потока спулера основной поток освобождается и завершается, что приводит к выходу из программы электронной таблицы и завершению соответствующего процесса.

 

27. Оповещения и асинхронные вызовы процедур

В некоторых ситуациях полезно позволить одному потоку асинхронно уве­домлять другой поток о необходимости остановить выполнение. Эта операция называется в исполнительной системе NT оповещением (alert) и тесно связана с синхронизацией. Представьте себе приложение базы данных, обрабатываю­щее запрос. Приложению неизвестно, находятся ли необходимые данные на локальном или на удаленном компьютере. На всякий случай приложение запус­кает два потока; один ищет данные локально, второй — по сети. Как только один из потоков найдет данные, он посылает оповещение другому потоку. В ответ на это оповещенный поток прекращает выполнение текущей операции и возвращается к исходному состоянию, готовый к выполнению новой задачи.

Оповещения не слишком широко применяются в Windows NT, помимо тех случаев, когда они используются в комбинации с другим механизмом асинхронного уведомления — асинхронным вызовам процедур (asynchronous procedure call, APC). Время от времени ОС требуется уведомлять поток о том, что он должен выполнить некоторое действие. Иногда поток должен выпол­нить определенное действие после того, как произошло некоторое событие. Например, пользователь может захотеть, чтобы Windows послала ему сообще­ние с напоминанием о времени запланированной встречи. В Windows NT этот тип асинхронного уведомления реализуется с применением APC пользователь­ского режима. Это означает, что подсистема Win32 обращается к исполнитель­ной системе NT для установки таймера и передает указатель на процедуру (APC), которая будет посылать сообщение пользователю. Когда таймер сраба­тывает, исполнительная система NT напоминает потоку подсистемы Win32 о необходимости выполнения заданной процедуры APC. После ее выполнения поток Win32 продолжает выполнять то, чем был занят раньше.

Хотя некоторые асинхронные операции генерируются программами пользовательского режима, большинство из них генерируются ОС и особенно системой ввода-вывода NT. Последняя является асинхронной, т. е. вызывающий поток может запустить операцию ввода-вывода, а потом заниматься дру­гими делами, пока устройство ввода-вывода выполняет ее. Когда оно закончит передачу данных, система ввода—вывода должна приостановить вызывающий поток и скопировать результаты операции ввода-вывода в его адресное про­странство. Для этого система ввода-вывода использует АРС режима ядра.

АРС пользовательского режима и режима ядра имеют ряд различий, но одно из них особенно важно. АРС режима ядра может в любой момент пре­рвать исполнение потока пользовательского режима и заставить его выпол­нить заданную процедуру. Обычно это происходит без ведома приложения. Генерируется программное прерывание, и, как и в случае аппаратного преры­вания, система просто на короткое время " крадет" поток приложения и застав­ляет его выполнить процедуру АРС. В противоположность этому, АРС пользо­вательского режима может быть доставлен только в определенные точки, когда запросивший его поток готов к исполнению АРС.

NT предоставляет потоку два способа регулировки того, в какой момент он получит асинхронное уведомление пользовательского режима (оповеще­ние или АРС пользовательского режима). Поток может либо вызвать базовый сервис, чтобы проверить, было ли ему послано оповещение, либо ждать у описателя объекта, разрешив прерывание этого ожидания оповещением. В обоих случаях, если имеется ожидающий АРС для данного потока, ядро NT доставляет его, и поток выполняет заданную процедуру. После этого ядро во­зобновляет исполнение потока в той точке, где он был прерван.

Доступ к оповещениям и АРС в API Win32 (только для NT) осуществляется через расширенные функции ввода-вывода. Расширенные функции ReadFileEx() и WriteFileEx() позволяют потоку выполнять чтение и запись файла асин­хронно, предоставив процедуру АРС, которую поток будет выполнять после завершения операции ввода-вывода. Функции WaitForSingleObjectEx и WaitForMultipleObjectsEx позволяют потоку ожидать в оповещенном состоянии в неко­торой точке после выдачи запроса ввода-вывода. Подсистема POSIX не предо­ставляет возможностей АРС для приложений POSIX, но использует АРС режима ядра для эмуляции доставки сигналов POSIX. А

 

28. Структура процессов

Процессы — это динамические сущности, создаваемые и уничтожаемые при работе ОС. Один процесс создает другой, который, в свою очередь, также может создавать процессы. Структура процессов (process structure) определя­ет, каким образом ОС создает, использует и уничтожает процессы и потоки и какие отношения существуют между данным процессом и другими процессами.

Программисты, пишущие приложения Win32, MS-DOS, OS/2 или POSIX, никогда не имеют дела с базовыми процессами и потоками NT. Win32 и другие подсистемы изолируют программиста от них, создавая собственные среды, в которых программист Win32 видит только процессы Win32, программист POSIX — только процессы POSIX и т. д. Однако, в первую очередь благодаря нижележащим средствам структуры процессов исполнительной системы NT, эти непохожие среды и могут сосуществовать в одной ОС.

Требования подсистем среды

Одной из основных задач подсистемы среды Windows NT является эмуляция API, для которого написаны ее клиентские приложения (например, API Win32 или POSIX). Другая ее основная функция — реализация структуры процессов, требуемой этими клиентами. Ниже приводятся (относящиеся к процессам) сред­ства, необходимые для типичной среды:

• Создание и завершение процессов и потоков.

• Протоколирование и поддержка взаимоотношений между процессами.

• Выполнение операций (как локальных, так и сетевых) от имени клиент­ского процесса.

• Чтение и запись и другие манипуляции с адресным пространством клиентского процесса.

• Остановка клиентского потока, возможно, изменение его контекста и запуск вновь.

• Перехват и обработка исключений, генерируемых клиентскими процессами.

Создание процесса, стоящее первым пунктом в списке, — это самая обыч­ная операция для подсистемы, и она хорошо иллюстрирует использование подсистемами среды базовых сервисов процесса для выполнения своих задач. На рис. 4-11 показано, как соотносятся создание процесса из прикладной программы и создание процесса исполнительной системы NT.

Клиентское приложение, в данном примере приложение Win32, POSIX или OS/2, создает процесс с помощью соответствующих API своей среды. За­прос на создание процесса передается через средство передачи сообщений исполнительной системы NT соответствующему серверу, который обращается к диспетчеру процес­сов NT для создания базового процесса.

После создания базового процесса NT диспетчер процессов возвращает описатель объекта-процесса. Подсистемы среды принимают этот описатель и создают подходящие возвращаемые значения для клиентских приложений. На рис. 4-12 показано, что именно возвращают различные подсистемы.

Между получением описателя от диспетчера процессов и возвратом результата клиентскому приложению подсистема сре­ды должна проделать некоторую дополнительную работу. В частности, подси­стемы снова обращаются к диспетчеру процессов, чтобы создать поток для нового процесса.

Рис. 4-11. Создание процесса.

Как показано на рис. 4—12, разные среды ОС возвращают при создании процесса разные результаты. Кроме того, ОС различаются принятыми в них правилами и соглашениями по управлению процессами. Одно из фундамен­тальных различий между поддерживаемыми в Windows NT средами ОС связано с тем, поддерживают ли они многопоточные процессы. Win32 и OS/2, напри­мер, допускают многопоточные процессы, тогда как POSIX, MS-DOS и 16-раз­рядная Windows — нет.

Подсистемы среды различаются и тем, какие существуют в них отношения между процессами. Например, POSIX и OS/2 объединяют свои процессы в иерар­хии, или деревья процессов (process trees). И та и другая создают начальный про­цесс, который порождает так называемые дочерние процессы, (child process). До­черний процесс, в свою очередь, может создать собственные дочерние процессы. Все процессы, кроме начального, имеют родителя, от которого наследуют неко­торые ресурсы и характеристики.

Как POSIX, так и OS/2 используют соотношения между клиентскими про­цессами для управления последними. Например, при завершении процесса POSIX или OS/2 система завершает все его дочерние процессы. Более того, совместимая с POSIX ОС поддерживает другие типы соотношений между про­цессами, включая группы процессов (process groups) — объединения взаимосвя­занных процессов и сессии (sessions) — объединения групп процессов. Для сес­сий и групп процессов системы POSIX обеспечивается детализированная се-

Рис. 4-12. Возврат после создания процесса.

мантика управления процессами, не имеющая точных эквивалентов в других ОС Исполнительная система NT должна обеспечить подсистеме среды возможность поддержки любых необходимых ей соотношений между процессами.

 

Помимо различий в группировании процессов и в поддержке многопоточности, подсистемы среды различаются правилами создания новых процес­сов. В табл. 4-4 показаны некоторые различия между структурами процессов для трех сред ОС, поддерживаемых Windows NT.

Таблица 4-4. Семантика создания процессов

    Windows (32-разрядная) POSIX OS/2
Функция API CreateProcess() Fork() DosExecPgm()-
Иерархия Не поддерживает Новый процесс Новый процесс со­
процессов формального соотно­ создается как по­ здается как пото­
    шения родитель-по­ томок вызываю­ мок вызывающего
    томок щего процесса процесса
Наследование Копирует для дочер­ Копирует для по­ Копирует для по­
    него процесса все опи­ томка файловые томка все описате­
    сатели объектов, от­ дескрипторы ли файлов, каналов
    крытые с атрибутом родителя и семафоров роди­
    наследования     теля, которые были
            открыты с правами
            наследования
Инициализация Инициализирует Инициализирует Инициализирует
адресного адресное простран­ адресное простран­ адресное простран­
пространства ство процесса испол­ ство потомка, копи­ ство потомка
    няемой программой руя адресное прост­ исполняемой
        ранство родителя программой
Идентифика­ Возвращает описатель Возвращает иденти­ Возвращает иденти­
ция процесса нового процесса фикатор процесса фикатор процесса
        нового потомка нового потомка
            (если потомок
            выполняется
            асинхронно)
Потоки Создает один поток Создает один поток, Создает один поток
    и поддерживает но не поддерживает и поддерживает
    многопоточность многопоточность многопоточность

 

Иерархии процессов, инициализация адресного про­странства и идентификация процессов различны в разных средах. Хотя неко­торые различия кажутся небольшими, диспетчер процессов должен поддержи­вать все среды одинаково хорошо и обеспечить существование различных структур процессов без конфликтов между ними.

 

 

29. Базовая структура процессов

При проектировании базовой структуры процессов разработчики быстро по­няли, что поддержка нескольких типов структуры процессов в базовой ОС, даже если бы она была возможна, привела бы к созданию крайне сложной и хаотичной системы. Большинство деталей, относящихся к структу­ре процессов, не являются фундаментальными для функционирования нижеле­жащей ОС. Структуры процессов могут быть реализованы подсистемами сре­ды, работающими в пользовательском режиме за пределами исполнительной системы NT. Чтобы обеспечить такую возможность, структура процессов ис­полнительной системы NT не устанавливает жестко каких-либо правил, кото­рые могли бы помешать реализации другого набора правил. Вместо этого пре­доставляется базовый набор механизмов, который подсистемы могут исполь­зовать как основу для реализации собственных структур процессов. Как при­мер такого подхода, в табл. 4—5 представлены гибкие правила создания про­цесса исполнительной системы NT.

Исполнительная система NT рассматривает создание процесса как созда­ние объекта, и не более того. Когда диспетчер процессов заканчивает создание процесса, он возвращает подсистеме среды описатель нового процесса. Под­система отвечает за вызов диспетчера процессов для создания потока в новом процессе.

Таблица 4-5. Семантика создания базового процесса NT

NT
Функция API Иерархия процессов Наследование Инициализация адресного пространства Идентификация процесса Потоки NtCreateProcess() Создает новый процесс, независимый от вызывающего процесса, и возвращает описатель объекта Вызывающий задает родителя, от которого новый процесс насле­дует описатели объектов, открытые с атрибутом наследования Инициализирует адресное пространство нового процесса исполняемой программой или как копию адресного пространства родителя Возвращает описатель объекта NT для нового процесса Не создает поток в новом процессе автоматически, но поддер­живает многопоточность

 

Диспетчер процессов NT не запоминает информацию о том, каким про­цессом создан новый процесс. Поэтому для эмуляции соотношений между про­цессами, необходимых приложениям, каждая подсистема среды поддерживает записи о созданных ею клиентских процессах и соотношениях между ними.

Управление клиентскими процессами

Для запуска базового процесса NT нужно не только создать поток, но и предо­ставить минимальный набор ресурсов. Если снова обратиться к рис. 4-2, то можно видеть, что у процесса есть маркер доступа, свое содержимое адресно­го пространства и свои описатели объектов. Эти ресурсы, а также квоты про­цесса и другие параметры полностью или частично наследуются от другого процесса — " родительского". Термин " родительский процесс" взят в кавычки из-за принятого в исполнительной системе NT уникального понятия назнача­емого родителя. Рассмотрим схему, показанную на рис. 4-14.

На рисунке приложение POSIX вызывает подсистему POSIX для создания нового процесса POSIX. Подсистема (являющаяся также процессом) вызывает исполнительную систему NT, чтобы создать базовый процесс. Так как подсис­тема POSIX выступает от лица клиентского приложения, то новый процесс должен наследовать ресурсы не от подсистемы, а от ее клиента. То же самое верно и для создания процесса приложением Win32 и OS/2. Чтобы подсистемы

 

Рис. 4-14. Назначение родительского процесса.

среды могли эмулировать семантику наследования процессов, необходимую их приложениям, в исполнительной системе NT имеется сервис процесса, ко­торый позволяет вызывающему (в данном случае, подсистеме) по желанию задать родителя нового процесса.

Новый базовый процесс NT наследует от родительского процесса маркер доступа, размеры квот, базовый приоритет и процессорное сродство по умол­чанию. Он наследует и все описатели из родительской таблицы объектов, от­крытые с признаком наследования. Адресное пространство процесса также может наследоваться, если это нужно подсистеме. Подсистема POSIX использу­ет эту возможность для эмуляции функции API POSIX fork(), тогда как подсис­темы Win32 и OS/2 задают исполняемую программу, подлежащую загрузке в адресное пространство нового процесса.

Прежде чем новый процесс начнет выполняться, ему должен быть придан поток. Для приложений Win32 и OS/2 создание потока не рассматривается как операция, отдельная от создания нового процесса. Приложения Win32 и OS/2 предполагают, что, когда функция создания процесса возвращает им управление, поток уже создан. Однако в NT поток не создается автоматически, поэтому под­системы среды должны снова вызвать диспетчер процессов для создания потока в новом процессе. Создавая поток, диспетчер процессов позволяет подсистемам указать процесс, которому будет принадлежать новый поток. Это дает возмож­ность, например, подсистеме Win32 создать процесс для одного из своих клиен­тов, после чего поместить поток в адресное пространство этого клиента. Новый поток начинает исполняться с базовым приоритетом клиентского процесса, на наборе процессоров, заданных в процессорном сродстве клиентского процесса, и с ограничениями, установленными маркером доступа клиентского процесса.

Помимо создания процессов и потоков от лица других процессов, дис­петчер процессов NT предоставляет средства, позволяющие подсистеме при­соединяться к адресному пространству клиента и производить его чтение или запись в него, выделять и освобождать виртуальную память клиента, а также приостанавливать выполнение клиентских потоков, изменять их контексты и снова запускать. Подсистема также может дублировать описатели из собствен­ной таблицы объектов в таблицу объектов клиента. Более того, она может за­вершать клиентские потоки или клиентский процесс.

Эти мощные возможности дают подсистемам пользовательского режима такие средства управления, которые в большинстве ОС имеются только у кода ОС в режиме ядра. Подсистемы среды получают свободу управлять своими клиентскими приложениями и создавать для них среду ОС, которая отличается от базовой среды исполнительной системы NT.

 

Как предотвратить неправильное использование

Создание процессов и потоков от лица другого процесса, чтение и запись в виртуальную память другого процесса и управление потоками другого про­цесса — это операции, которые нельзя использовать беспорядочно. Чтобы предотвратить их неправильное использование, система защиты Windows NT (конкретно, ее механизмы защиты объектов) гарантирует, что такие операции будут тщательно контролироваться.

Подсистемы среды Windows NT в своей основе — это просто обычные процессы. Подобно другим процессам, они определяют, какие права доступа предоставляются создаваемым ими процессам. Поскольку практически все процессы пользовательского режима создаются подсистемами среды, эти под­системы управляют поведением всех пользовательских процессов в системе.

Например, при создании клиентского процесса подсистема отказывает ему в возможности обойти ее и завершиться вызовом базового сервиса NT. В противном случае процесс мог бы оставить глобальные структуры данных подсистемы в неактуальном состоянии, возможно, повредив другим процес­сам, выполняющимся под ее управлением. Подсистема предотвращает это, не предоставляя новому процессу прав на удаление его собственного объекта-процесса в списке контроля доступа (ACL) этого объекта. Не имея прав на удаление, процесс никогда не сможет открыть собственный описатель, который позволил бы ему завершить­ся. Система защиты не позволит сервису завершения успешно выполниться, если ему не передан правильный описатель.

Благодаря системе защиты объектов клиент не может получить какую-либо возможность, если она не предоставлена ему явно подсистемой. Таким образом, проектировщику подсистемы не надо держать в голове все те неза­конные действия, которые может предпринять клиентский процесс, и изобре­тать средства их предотвращения. Вместо этого достаточно определить, что процесс должен быть способен делать, и предоставить ему соответствующие возможности. В большинстве случаев это означает, что ни один из обычных процессов пользовательского режима не может вызывать базовые сервисы NT. Процесс пользовательского режима может вызывать лишь функции API, предо­ставленные создавшей его подсистемой.

Те же самые механизмы не дают пользовательским процессам завершать другие процессы или манипулировать ими. Для доступа к другим процессам процесс может вызывать только те функции API, которые доступны в его среде (Win32 или POSIX, например). Более того, способность процесса вызывать даже эти сервисы ограничена его правами доступа к базовым объектам, кото­рые будут в этом случае затронуты. И опять, не предоставляя клиентскому про­цессу прав доступа к базовым объектам, подсистема предотвращает его неже­лательное поведение.

 

52. База данных страничных фреймов

Таблицы страниц процесса содержат информацию о том, в каком месте физи­ческой памяти расположены виртуальные страницы. Кроме того, диспетчеру виртуальной памяти нужна структура данных для отслеживания состояния фи­зической памяти. Например, ему нужно знать, свободен ли данный страничный фрейм, и если нет, то кто его использует. Для этой цели и служит база данных страничных фреймов (page frame database). Она представляет собой массив элементов, пронумерованных от нуля до числа страничных фреймов в системе (минус 1). Каждый элемент содержит информацию о соответствующем стра­ничном фрейме. База данных страничных фреймов и ее связь с таблицами стра­ниц показаны на рис. 6-13. Как видно, действительные элементы таблицы стра­ниц указывают на элементы базы данных страничных фреймов, а последние указывают обратно на использующую их страничную таблицу. Диспетчер вирту­альной памяти использует прямой указатель, когда процесс обращается по дей­ствительному виртуальному адресу. Он следует по указателю, чтобы найти физи­ческую страницу, соответствующую виртуальному адресу.

Некоторые недействительные элементы таблицы страниц также ссылают­ся на элементы базы данных страничных фреймов. Эти " переходные" элементы таблицы страниц указывают на страничные фреймы, которые могут быть, но еще не использованы повторно, и, таким образом, их содержимое пока не изме­нялось. Если процесс обращается к одной из таких страниц, прежде чем она будет снова использована другим процессом, то диспетчер виртуальной памяти может быстро восстановить ее. Другие недействительные элементы таблицы страниц содержат дисковые адреса, по которым хранятся страницы. При обращении процесса к одной из таких страниц происходит страничная ошибка, и диспетчер виртуальной памя­ти считывает содержимое страницы с диска.

В любой момент времени страничный фрейм может находиться в одном из шести состояний:

• Действительный. Страничный фрейм используется процессом, и на него указывает действительный элемент таблицы страниц.

• Обнуленный. Страничный фрейм свободен и инициализирован нулями.

• Свободный. Страничный фрейм свободен, но не инициализирован.

• Резервный. Данный фрейм использовался процессом, но был удален из рабочего набора последнего. Соответствующий элемент таблицы стра­ниц недействителен, но помечен как переходный.

• Измененный. Данное состояние аналогично резервному за исключени­ем того, что процесс, использовавший этот фрейм, осуществил запись в него, и содержимое еще не записано на диск. Соответствующий эле­мент таблицы страниц недействителен, но помечен как переходный.

• Плохой. Страничный фрейм вызвал ошибку четности или другой аппа­ратный сбой, и его нельзя использовать.

База данных страничных фреймов группирует те неиспользуемые фрей­мы, которые находятся в одном и том же состоянии, создавая таким образом пять отдельных списков: список обнуленных, список свободных, список резерв­ных, список измененных и список плохих страниц. Связь между базой данных страничных фреймов и списками страниц показана на рис. 6-14.

Как видно, в данные списки включены все страничные фреймы компьюте­ра, которые в данный момент не используются. Указатели на используемые фреймы содержатся в таблице страниц соответствующего процесса. Если про­цесс освобождает страничный фрейм или если диспетчер виртуальной памяти откачивает его содержимое на диск, то фрейм становится свободным, и диспет­чер виртуальной памяти помещает его обратно в один из списков.

Если диспетчеру виртуальной памяти требуется инициализированный страничный фрейм (тот, который содержит одни нули) для обработки странич­ной ошибки, он пытается взять первый из списка обнуленных страниц; если этот список пуст, то диспетчер выбирает фрейм из списка свободных и обнуляет его. Если диспетчеру виртуальной памяти не нужна инициализированная стра­ница, то он берет первую из списка свободных; если список пуст, то использует­ся первая из списка обнуленных. И в том и в другом случае, если оба списка пусты, диспетчер виртуальной памяти использует список резервных. Всякий раз,

Рис. 6-13. Таблицы страниц и база данных страничных фреймов.

 

Рис. 6-14. Списки страниц в базе данных страничных фреймов.

когда количество страниц в списках обнуленных, свободных и резервных стра­ниц снижается до порогового значения, поток, называемый средством записи измененных страниц (modified page writer), " пробуждается", записывает содер­жимое измененных страниц на диск, после чего помещает их в список резерв­ных для повторного использования.

Если даже список измененных стал слишком коротким, то диспетчер вир­туальной памяти начинает урезать рабочие наборы всех процессов до их мини­мальных размеров. Вновь освобожденные страницы помещаются в список из­мененных или резервных для повторного использования по запросу. Диаграмма состояний страничного фрейма показана на рис. 6-15.

Прежде чем диспетчер виртуальной памяти сможет использовать страни­цу из списка резервных или измененных, он должен обновить недействитель­ный элемент таблицы страниц (или прототипный РТЕ), который по-прежнему указывает на данный фрейм. Возвращаясь к рис. 6-13, можно видеть, что элемен­ты базы данных страничных фреймов содержат обратные указатели на таблицу страниц процесса, использовавшего их последним (или на прототипный РТЕ для совместно используемых страниц), что и позволяет выполнить обновление.

 

Рис. 6-15. Диаграмма состояний страничных фреймов.

 

53. Дескрипторы виртуальных адресов

Диспетчер виртуальной памяти использует алгоритм подкачки по запросу для определения момента загрузки страницы в память. Прежде чем переписать страницу с диска, он ждет, пока некоторый поток не обратится по расположен­ному на ней адресу и не вызовет страничной ошибки. Подобная подкачка по запросу является разновидностью отложенных вычислений. Алгоритмы отло­женного вычисления избегают выполнения дорогостоящих операций, таких как подкачка, пока это не станет абсолютно необходимым.

Диспетчер виртуальной памяти использует отложенные вычисления и в другой области, а именно, для формирования таблиц страниц. Например, когда поток выделяет большую область виртуальной памяти, можно было бы сразу же создать таблицы страниц, необходимые для доступа ко всему выделенному диа­пазону адресов. Однако, если приложение использует не всю выделенную память, то создание таблиц страниц будет напрасной тратой сил. Следовательно, диспетчер виртуальной памяти не делает этого до тех пор, пока не произойдет страничная ошибка. Использование отложенных вычислений дает значитель­ный выигрыш в производительности для приложений, резервирующих много памяти, но использующих (передающих) ее не целиком.

Выделение памяти, даже больших блоков, с использованием алгоритма отложенных вычислений выполняется очень быстро. Однако этот выигрыш в производительности дается не даром. Когда поток выделяет память, диспетчер виртуальной памяти должен в ответ вернуть диапазон адресов, которые поток сможет использовать. Однако, поскольку таблица страниц процесса не загружа­ется до тех пор, пока поток фактически не обратится к памяти, диспетчер вир­туальной памяти не может обратиться к ней, чтобы определить, какие виртуаль­ные адреса свободны. Следовательно, диспетчер виртуальной памяти должен поддерживать другой набор структур данных, чтобы отслеживать, какие адреса из виртуального адресного пространства процесса уже заняты, а какие нет. В этих целях и используются дескрипторы виртуальных адресов.

Для каждого процесса диспетчер виртуальной памяти поддерживает набор дескрипторов виртуальных адресов, описывающий состояние виртуального ад­ресного пространства процесса (см. рис. 6-16).

Когда процесс выделяет память (или отображает проекцию совместно ис­пользуемой памяти), диспетчер виртуальной памяти создает дескриптор вирту­ального адреса для хранения всей информации, относящейся к запросу распреде­ления памяти: выделяемый диапазон адресов, будет ли эта область памяти совме­стно используемой или собственной, может ли содержимое области памяти на­следоваться дочерним процессом, а также каков тип защиты страниц. Затем этот дескриптор виртуального адреса вставляется в древо дескрипторов виртуальных адресов процесса (самобалансирумое двоичное древо) для ускорения его поиска.

При первом обращении потока по некоторому адресу диспетчер вирту­альной памяти должен создать элемент таблицы страниц для страницы, содер­жащей этот адрес. Для этого он ищет дескриптор виртуального адреса, в диапа­зон адресов которого попадает данный адрес, и по информации из дескриптора создает элемент таблицы страниц. Если адрес не попадает в диапазон ни одного из дескрипторов, то диспетчер виртуальной памяти определяет, что поток пыта­ется обратиться по адресу, который не был выделен; имеет место нарушение

доступа к памяти.


 

Рис. 6-16. Дескрипторы виртуальных адресов.

Соображения мультипроцессорной обработки

Любой код, который может выполняться одновременно на нескольких процес­сорах, должен удовлетворять некоторым ограничениям. Он должен быть реен­терабельным, предотвращать одновременное использование несколькими по­токами глобальных структур данных и не позволять двум потокам захватывать ресурсы таким образом, чтобы заблокировать друг друга (взаимоблокировка, или клинч, deadlock). Кроме того, на многопроцессорных системах существуют специфические проблемы производительности (отсутствующие на однопро­цессорных машинах).

Диспетчер виртуальной памяти реентерабелен, так что для него основны­ми проблемами были предотвращение разрушения данных и взаимоблокиро­вок, а также достижение хорошей производительности.

Для защиты своей самой важной структуры данных — базы данных стра­ничных фреймов — диспетчер виртуальной памяти использует спин-блокиров­ку. Всякий раз, когда возникает страничная ошибка, средство подкачки страниц перехватывает управление вызвавшим ее потоком, обрабатывает ошибку и об­новляет базу данных. Прежде чем получить доступ к базе данных, поток должен завладеть связанной с нею спин-блокировкой. Пока поток владеет спин-блоки­ровкой, никакой другой поток не может читать или записывать в базу данных страничных фреймов. Таким образом, когда в Windows NT происходят две стра­ничных ошибки одновременно, один из потоков приостанавливается до осво­бождения базы данных страничных фреймов.

Задержка доступа потока к базе данных страничных фреймов является примером противоречия между скоростью выполнения и требованиями много­процессорной системы. Диспетчер виртуальной памяти мог бы позволить не­скольким потокам одновременно обращаться к разным частям базы данных, разбив ее на несколько структур данных и защитив каждую часть отдельной блокировкой. Однако получение и освобождение блокировки — дорогостоящая операция, поэтому обработка страничных ошибок выполнялась бы дольше, если бы потоку пришлось захватывать три блокировки вместо одной. Разработчики отдали предпочтение ско­рости обработки страничных ошибок перед большей степенью параллелизма средства подкачки страниц. Они решили использовать для защиты базы данных одну блокировку, предполагая, что при меньших накладных расходах поток бу­дет быстрее входить и выходить из владения базой данных, освобождая ее для других потоков.

Использование одной блокировки означает, что база данных страничных фреймов может стать узким местом при интенсивной подкачке страниц. Чтобы избежать этого, диспетчер виртуальной памяти пытается минимизировать коли­чество страничных ошибок. Для этого он делает следующее:

•предоставляет каждому процессу достаточное количество страниц в рабочем наборе;

•автоматически урезает рабочие наборы процессов, чтобы излишние или неиспользуемые страницы стали доступны другим процессам.

Соображения переносимости

Диспетчер виртуальной памяти зависит от определенных аппаратных возмож­ностей. Ниже приведены требования, которые он предъявляет к процессору:

• 32-разрядные адреса (64-разрядные адреса поддерживаются, но тре­буют некоторой переделки диспетчера виртуальной памяти).

• Поддержка виртуальной памяти и подкачки страниц. Процессор дол­жен предоставлять возможность отображения виртуальных адресов в физические, а также предоставлять механизмы подкачки.

• Прозрачные, когерентные аппаратные кэши на многопроцессорных системах. Когда поток, исполняющийся на одном из процессоров, об­новляет данные в кэше последнего, все другие процессоры должны полу­чить уведомление, что их кэши теперь содержат некорректные данные.

• Совмещение виртуальных адресов. Процессор должен допускать ото­бражение на один и тот же страничный фрейм двух элементов таблицы страниц одного и того же процесса. ОС часто использует страницу совместно с пользовательским процессом, отображая второй элемент таблицы страниц.

Некоторые части диспетчера виртуальной памяти зависят от особеннос­тей процессора, на котором исполняется ОС. Перечисленные ниже части дис­петчера памяти должны быть модифицированы для каждой аппаратной плат­формы, на которую он переносится.

• Элементы таблицы страниц. Когда элемент таблицы страниц действи­телен, процессор подразделяет эти 32 бита на поля и устанавливает их значения соответствующим образом. Когда элемент недействителен, диспетчер виртуальной памяти использует остальной 31 бит по своему усмотрению. Формат, выбираемый им, зависит от средств виртуальной памяти, предоставляемых процессором.

• Размер страницы. Разные процессоры используют разные размеры страницы. Диспетчер виртуальной памяти выделяет ее в пределах блока в 64 Кбайт, что гарантирует возможность поддержки любого размера страницы от 4 до 64 Кбайт. Страницы менее 4 Кбайт не поддерживаются.

• Защита страниц. Способ использования диспетчером виртуальной па­мяти аппаратной защиты страниц для реализации дополнительной про­граммной защиты, естественно, аппаратно зависим.

• Трансляция виртуального адреса. Алгоритм, используемый диспетчером виртуальной памяти для трансляции виртуального адреса в номер эле­мента таблицы страниц, тоже аппаратно зависим.

 

 

54. Операционная система, как и любая большая программная сис­тема, состоит из расположенных друг над другом уровней кода. Верхние уров­ни используют более примитивные (но в данном случае более мощные) функ­ции и структуры данных нижних уровней.

Ядро выполняет наиболее фундаментальные функции Windows NT, опре­деляя, как ОС использует процессор или процессоры и обеспечивая рациональ­ность их использования. Таким образом, эффективность всей ОС зависит от правильной и эффективной работы ядра.

Главной задачей разработчиков при создании ядра NT было обеспечение базы, со­стоящей из примитивов и механизмов с тщательно определенным и предсказу­емым поведением, которые позволили бы высокоуровневым компонентам ис­полнительной системы NT выполнять свои задачи. Используя примитивы ядра, исполнительная система NT может создавать бесконечное разнообразие абст­ракций высокого уровня. Ей не нужно использовать для этого недокументиро­ванные интерфейсы и хитрые трюки или непосредственно обращаться к аппа­ратуре. Ядро отделяет себя от остальных частей исполнительной системе, реа­лизуя механизмы ОС и избегая установления жестких правил.

Предоставляя богатый набор контролируемых универсальных механизмов, ядро NT позволяет Windows NT расти и расширяться предсказуемым и упорядо­ченным образом. (Для простоты будем использовать термин исполнительная система (executive) для обозначения всех компонентов ОС, работающих в режиме ядра, за исключением самого ядра.)

Общие сведения

Отделение механизмов ОС от ее правил является важным принципом Windows NT. Механизмы — это способы выполнения различных задач в системе, и выра­жением их являются алгоритмы и код. Правила или стратегии определяют, когда и какие задачи должны быть выполнены, и даже следует ли вообще выполнять некоторые из них. Код ОС, поддерживающий строгое разделение между меха­низмами и стратегией, помогает системе оставаться гибкой. Со временем прави­ла могут меняться, не вызывая множества изменений в системе или механизмах.

Принцип разделения механизмов и стратегий используется в Windows NT на нескольких уровнях. На самом высоком уровне каждая подсистема среды устанав­ливает слой правил ОС, отличающийся от устанавливаемого другими подсистема­ми. Непосредственно под ними исполнительная система NT определяет другой, более фундаментальный слой правил, подходящий для всех подсистем. На самом нижнем уровне ОС ядро не устанавливает правил вообще. Вместо этого оно служит прослойкой между остальными частями ОС и процессором. Все операции, связан­ные с процессором, обязательно проходят через ядро, что обеспечивает большую переносимость и предсказуемость. Исполнительная система имеет лишь ограни­ченное влияние на выполнение этих операций (посредством вызова функций ядра). Помимо функций, предоставляемых исполнительной системой NT, ядро решает четыре основных задачи:

• планирует выполнение потоков;

• передает управление процедурам обработки при возникновении пре­рываний или исключений;

• выполняет низкоуровневую многопроцессорную синхронизацию;

• реализует процедуры восстановления системы после сбоя питания.

 

Ядро отличается от других компонентов исполнительной системы не­сколькими аспектами. В отличие от других частей исполнительной системы, оно никогда не откачивается из памяти. Аналогично, оно никогда не вытесня­ется, хотя его работа может быть прервана для обработки прерывания. Другими словами, на короткие периоды времени, пока выполняется ядро, многозадачность исчезает. Ядро всегда работает в ре­жиме ядра — привилегированном режиме процессора. Оно сделано неболь­шим, компактным и настолько переносимым, насколько это позволяют сообра­жения производительности и различия процессорных архитектур. Ядро напи­сано в основном на С, с использованием ассемблера только для тех задач, ко­торые требуют максимально возможной скорости выполнения или сильно зависят от особенностей процессора.

За пределами ядра исполнительная система представляет потоки и другие совместно используемые ресурсы в виде объектов. Эти объекты требуют некото­рых накладных расходов, связанных с правилами. Для работы с объектами необ­ходимы описатели, проверки прав доступа, квоты ресурсов и рутинные механиз­мы выделения и освобождения памяти. Ядро избегает этих накладных расходов, поскольку реализует набор более простых объектов, называемых объектами ядра (kernel objects). Они помогают ядру управлять центральным процессором и под­держивают создание объектов исполнительной системы. Большинство объек­тов уровня исполнительной системы включают в себя один или несколько объектов ядра, объединяя их мощные атрибуты (определяемые ядром).

Одна группа объектов ядра, называемых управляющими объектами (cont­rol objects), устанавливает семантику управления различными функциями ОС. В эту группу входят объект-процесс ядра, объект асинхронный вызов процедуры (asynchronous procedure call, APC), объект отложенный вызов процедуры (defer­red procedure call, DPC) и несколько объектов, используемых системой ввода-вывода. В их числе объект—прерывание, объект-уведомление питания и объект-состояние питания. Другая группа объектов ядра, известных как диспетчерские объекты (dispatcher objects), включает средства синхронизации и изменяет или влияет на планирование потоков. К диспетчерским объектам относятся поток ядра, мьютекс ядра, мутант ядра, событие ядра, пара событий ядра, семафор ядра и таймер ядра. Исполнительная система использует функции ядра для создания экземпляров его объектов, работы с ними и для создания более слож­ных объектов, которые она предоставляет процессам пользовательского режи­ма.

Планирование потоков

Поток выполняется в адресном пространстве некоторого процесса и исполь­зует ресурсы последнего. Одной из функций ядра NT является отслеживание готовых к исполнению потоков и определение порядка, в котором они будут выполняться, — задача, известная как планирование потоков (thread scheduling). При выполнении необходимых условий ядро выбирает поток для исполнения и переключает контекст на него. Переключение контекста (context switch) — это процедура сохранения текущего машинного состояния, связанного с ис­полняющимся потоком, загрузка состояния другого потока и запуск последне­го. Модулем, выполняющим эти обязанности, служит диспетчер ядра.

 

55. Объекты процесс ядра и поток ядра

Диспетчер должен следить за тем, чтобы из всех ожидающих исполнения по­токов процессоры всегда исполняли именно те, которые необходимо испол­нять в данный момент. Когда в системе происходит событие, изменяющее со­стояние некоторого потока, диспетчер просматривает список ожидающих потоков и, если это необходимо, переключает контекст на новый поток.

Хотя диспетчер манипулирует потоками, он рассматривает их не так, как это делают программы пользовательского режима или другие части ОС. Ядро работает с сокращенной версией объекта-потока, называемой объект-поток ядра (kernel thread object). Объект—поток ядра содержится внутри объекта—по­тока исполнительной системы и содержит информацию, необходимую ядру для направления потока на исполнение. Аналогично, ядро реализует минимальную версию объекта-процесса, называемую объект-процесс ядра (kernel process object). На рис. 7-1 показано соотношение между объектами процесс ядра и поток ядра и их высокоуровневыми аналогами в исполнительной системе.

Как показано на рис. 7-2, объект-процесс ядра содержит указатель на спи­сок потоков ядра. (Ядро ничего не знает об описателях, так что оно действует в обход таблицы объектов.) Кроме того, в объекте-процессе ядра находится ука­затель на каталог таблиц страниц процесса (используется для отслеживания

Рис. 7-1. Объект-процесс ядра и объекты-потоки ядра.

 

Рис. 7-2. Объект-процесс ядра.

виртуального адресного пространства процесса), общее время выполнения всех потоков процесса, базовый диспетчерский приоритет процесса по умолча­нию и набор по умолчанию процессоров, на которых могут исполняться потоки процесса, — так называемое процессорное сродство (processor affinity). Управле­ние информацией, хранящейся в объекте процесс ядра, осуществляет исключи­тельно ядро. Другие части исполнительной системы могут считывать или изме­нять ее, только вызывая функции ядра.

Объект-поток ядра более сложен, чем объект-процесс ядра. Он содержит некоторую очевидную информацию, такую как процессорное сродство потока (неполное подмножество сродства процесса) и общее время выполнения пото­ка. Сюда также входят базовый приоритет потока (который может отличаться от базового приоритета по умолчанию для процесса) и его текущий приоритет. Особенно важный элемент данных, хранящихся в объекте—потоке ядра, — это диспетчерское состояние потока. В любой момент времени поток может нахо­диться в одном из шести состояний; из них только одно делает его кандидатом на выполнение. Диспетчерские состояния потока показаны на рис. 7-3.

" Жизненный цикл" потока начинается тогда, когда программа создает но­вый поток. Этот запрос спускается вниз к исполнительной системе NT, где дис­петчер процессов выделяет пространство для объекта-потока и вызывает ядро для инициализации объекта-потока ядра, содержащегося внутри данного объекта. После инициализации поток проходит через следующие состояния:

• Готовый. Когда диспетчер ищет поток для выполнения, он рассматрива­ет только пул потоков, находящихся в этом состоянии. Готовые потоки просто ждут своего выполнения.

• Резервный. Поток в резервном состоянии был выбран для выполнения следующим на одном из процессоров. При выполнении определенных условий диспетчер выполняет переключение контекста на этот поток. Для каждого процессора системы в резервном состоянии может быть только один поток.

• Исполняющийся. После того, как диспетчер переключает контекст на поток, последний переходит в это состояние и выполняется. Выполне­ние потока продолжается до тех пор, пока он не будет вытеснен ядром для выполнения более высокоприоритетного потока, или не истечет его квант времени, или он не завершится, или добровольно не перейдет в состояние ожидания.

• Ожидающий. Поток может перейти в состояние ожидания несколькими способами. Он может добровольно ждать у объекта для синхронизации своего выполнения; ОС (например, система ввода-вывода) может ждать какого-либо события для него; или подсистема среды может приказать потоку приостановиться. Когда ожидание потока заканчивается, он сно­ва переводится в готовое состояние для продолжения выполнения.

• Переходный. Поток находится в переходном состоянии, если он готов к исполнению, но необходимые ему ресурсы недоступны. Например, стек ядра потока может быть откачан из памяти. Когда ресурсы стано­вятся доступными, поток переходит в состояние готовности.

• Завершившийся. Когда поток заканчивает свое исполнение, он перехо­дит в завершившееся состояние. После своего завершения объект-по­ток может быть (а может и не быть) удален. (Стратегия удаления объек­тов устанавливается диспетчером объектов.) Если у исполнительной системы есть указатель на объект-поток, то она может повторно ини­циализировать его и использовать снова.

Рис. 7-3. Состояния потока.

 

Состояние ожидания требует несколько более подробного обсуждения. Поток находится в состоянии ожидания, когда он ждет установки объекта или группы объектов в состояние " свободен". Объекты исполнительной системы, поддерживающие синхронизацию, всегда находятся в одном из двух состояний: они либо свободны, либо заняты. Объект остается в состоянии " занят" до тех пор, пока не произойдет какое-ни­будь значительное событие. Поток, например, переводится в состояние " свобо­ден", когда завершается. Все пользовательские потоки, ждущие описателя завер­шившегося потока, освобождаются и могут продолжить свое выполнение. Ана­логично, файловый объект устанавливается в состояние " свободен", когда завер­шается операция ввода-вывода. Поток, ждущий у описателя файла, освобожда­ется из состояния ожидания и может продолжать выполнение.

Фактически именно ядро реализует семантику ожидания и сигнализации Windows NT (не путать с сигналами POSIX, которые более походят на исключения NT). Каждый синхронизационный объект, видимый пользовательскому режиму, включает в себя один или несколько диспетчерских объектов ядра. Например, объект-поток содержит поток ядра, а объект-событие, как и объект-файл — со­бытие ядра. Ядро отвечает за установку диспетчерских объектов в состояние " сво­боден" в соответствии с твердо определенными правилами; выполняя свою зада­чу, ядро освобождает потоки, ждущие эти объекты, изменяя их состояние с " ожи­дающий" на " готовый". Это изменение, в свою очередь, говорит диспетчеру о не­обходимости начать планирование потока.

 

56. Приоритеты планирования

Для определения порядка выполнения потоков диспетчер ядра использует си­стему приоритетов, направляя на выполнение потоки с высоким приоритетом раньше потоков с низкими приоритетами. Ядро даже прекращает исполнение, или вытесняет (preempts) поток, если становится готовым к выполнению по­ток с высшим приоритетом.

Первоначально приоритет потока устанавливается в соответствии с при­оритетом процесса, в котором он был создан. Например, когда подсистема сре­ды создает процесс, она назначает ему базовый приоритет по умолчанию (сис­темное значение по умолчанию или число, заданное администратором). Поток наследует этот базовый приоритет и может изменять его так, чтобы он стал немного больше или немного меньше. В результате получается приоритет пла­нирования, с которым поток и начинает исполняться. В процессе исполнения потока его приоритет может отклоняться от базового.

Для планирования выполнения потоков ядро поддерживает набор струк­тур данных, известный как база данных диспетчера (dispatcher database). В базе данных диспетчера отмечается, какие потоки ждут выполнения и какие потоки на каких процессорах выполняются. Самая важная структура данных в базе дан­ных диспетчера называется очередью готовности диспетчера (dispatcher ready queue). На самом деле это группа очередей — по одной для каждого приоритета. Очереди, показанные на рис. 7-4, содержат готовые потоки, ждущие направле­ния на исполнение.

Как видно из рисунка, исполнительная система NT поддерживает 32 уров­ня приоритетов; потоки делятся на два класса - реального времени и переменного приоритета.

 

Рис. 7-4. Очередь готовности диспетчера.

Потоки реального времени, имеющие приоритеты от 16 до 31, — это высокоприоритетные потоки, используемые программами с критическим временем выполнения (например, приложениями управления и автоматиза­ции), которые требуют немедленного внимания процессора.

Для выбора очередного кандидата на исполнение диспетчер начинает с очереди наивысшего приоритета и спускается вниз до тех пор, пока не найдет поток; следовательно, все потоки реального времени будут выполняться прежде потоков переменного приоритета. Большинство потоков в системе относятся к классу переменного приоритета, с уровнями приоритета от 1 до 15 (приоритет 0 зарезервирован для системных целей). Эти потоки называются потоками пе­ременного приоритета (variable priority), так как диспетчер корректирует их приоритеты во время работы для оптимизации времени отклика системы. На­пример, так как Windows NT является системой с вытесняющей многозадачно­стью, диспетчер прерывает поток, после того как последний израсходовал свой квант времени. Если прерванный поток — это поток переменного приоритета, то диспетчер понижает его приоритет. Таким образом, приори­тет потока, выполняющего много вычислений, постепенно понижается (до его базового приоритета).

С другой стороны, диспетчер повышает приоритет потока после освобож­дения последнего из состояния ожидания. Обычно добавка к приоритету потока определяется кодом исполнительной системы, находящимся вне ядра, однако величина этой добавки определяется тем, какого события ожидал поток. Напри­мер, поток, ожидавший ввода с клавиатуры, получает большую добавку, чем по­ток, ожидавший завершения дискового ввода-вывода. В общем и целом, имеется тенденция к установлению для интерактивных потоков высокого переменного приоритета, для потоков, выполняющих ввод-вывод — среднего и для вычисли­тельных потоков — низкого. (Приоритет потока переменного приоритета не может быть повышен до уровня потоков реального времени.)

Процессорное сродство потока также влияет на порядок исполнения по­токов. Ядро выбирает поток в зависимости от его приоритета и затем проверяет, на каких процессорах он может исполняться. Если процессорное сродство по­тока не позволяет ему выполняться ни на одном из свободных процессоров, то будет выполняться следующий по приоритету поток.

Когда в системе ничего не происходит, ядро предоставляет для каждого про­цессора один поток, который всегда готов выполняться. Такие потоки называются потоками простоя; диспетчер считает, что их приоритет ниже приоритета всех остальных потоков. Поток простоя всего лишь (в цикле) проверяет, не появился ли в резервном состоянии другой поток, готовый к исполнению на данном процессо­ре. При обнаружении такого потока поток простоя инициирует переключение контекста на него. Потоки простоя проверяют также наличие ожидающих выпол­нения отложенных вызовов процедуры (DPC).

 

Переключение контекста

После того, как истек квант времени потока, ядро вытесняет его и выполняет перепланировку загрузки процессора. Однако истечение кванта времени — не единственная причина начала планировки. Она начинается, когда исполнение текущего потока не может продолжаться или когда изменилось состояние не­которого потока и текущий поток не является более самым высокоприоритет­ным. Некоторые условия, вызывающие перепланировку, перечислены ниже:

• Поток становится готовым к выполнению — например, вновь инициализи­рованный поток или поток, только что вышедший из состояния ожидания.

• Истек квант времени потока, поток завершился или вошел в состояние ожидания.

• Диспетчер или исполнительная система (возможно, по запросу при­кладной программы) изменили приоритет потока.

• Исполнительная система или прикладная программа изменила процес­сорное сродство выполняющегося потока.

Цель перепланировки — выбор потока, который будет выполняться сле­дующим на некотором процессоре, и перевод его в резервное состояние. Однако просто найти поток недостаточно. Диспетчер также должен направить его на выполнение.

Когда выполняющийся поток завершился или не может продолжать ис­полнение по другой причине, диспетчер просто выполняет переключение кон­текста на новый поток. В других случаях от диспетчера требуется большее. Пусть, например, высокоприоритетный поток реального времени становится готовым к выполнению, но выполняется поток с меньшим приоритетом. В этой ситуации диспетчер должен вытеснить исполняющийся поток. Для этого он запрашивает программное прерывание, чтобы начать переключение контекста, как показано на рис. 7-5.

Выполняя перепланировку потоков, ядро использует базу данных диспетчера, чтобы быстро определить, какие процессоры заняты, какие простаивают (исполня­ют поток простоя) и каковы приоритеты потоков, исполняющихся на каждом из процессоров. В данном примере ядро (выполняющееся на процессоре А) опреде­ляет, что процессор В выполняет поток с меньшим приоритетом, чем у вновь гото­вого потока. Ядро запрашивает диспетчерское прерывание для вытеснения потока, исполняющегося на процессоре В. Ядро, выпо


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.052 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал