Страница:
В главе 2 были сформулированы характеристики процессов. В настоящей гла-
ве на более формальном уровне определяется понятие "контекст процесса" и по-
казывается, каким образом ядро идентифицирует процесс и определяет его мес-
тонахождение. В разделе 6.1 описаны модель состояний процессов для системы
UNIX и последовательность возможных переходов из состояния в состояние. В
ядре находится таблица процессов, каждая запись которой описывает состояние
одного из активных процессов в системе. В пространстве процесса хранится до-
полнительная информация, используемая в управлении протеканием процесса. За-
пись в таблице процессов и пространство процесса составляют в совокупности
контекст процесса. Аспектом контекста процесса, наиболее явно отличающим
данный контекст от контекста другого процесса, без сомнения является содер-
жимое адресного пространства процесса. В разделе 6.2 описываются принципы
управления распределением памяти для процессов и ядра, а также взаимодейст-
вие операционной системы с аппаратными средствами при трансляции виртуальных
адресов в физические. Раздел 6.3 посвящен рассмотрению составных элементов
контекста процесса, а также описанию алгоритмов управления контекстом про-
цесса. Раздел 6.4 демонстрирует, каким образом осуществляется сохранение
контекста процесса ядром в случае прерывания, вызова системной функции или
переключения контекста, а также каким образом возобновляется выполнение при-
остановленного процесса. В разделе 6.5 приводятся различные алгоритмы, ис-
пользуемые в тех системных функциях, которые работают с адресным пространст-
вом процесса и которые будут рассмотрены в следующей главе. И, наконец, в
разделе 6.6 рассматриваются алгоритмы приостанова и возобновления выполнения
процессов.
Как уже отмечалось в главе 2, время жизни процесса можно теоретически
разбить на несколько состояний, описывающих процесс. Полный набор состояний
процесса содержится в следующем перечне:
1. Процесс выполняется в режиме задачи.
2. Процесс выполняется в режиме ядра.
3. Процесс не выполняется, но готов к запуску под управлением ядра.
4. Процесс приостановлен и находится в оперативной памяти.
5. Процесс готов к запуску, но программа подкачки (нулевой процесс) должна
еще загрузить процесс в оперативную память, прежде чем он будет запущен
под управлением ядра. Это состояние будет предметом обсуждения в главе 9
при рассмотрении системы подкачки.
6. Процесс приостановлен и программа подкачки выгрузила его во внешнюю па-
мять, чтобы в оперативной памяти освободить место для других процессов.
7. Процесс возвращен из привилегированного режима (режима ядра) в неприви-
легированный (режим задачи), ядро резервирует его и переключает контекст
на другой процесс. Об отличии этого состояния от состояния 3 (готовность
к запуску) пойдет речь ниже.
8. Процесс вновь создан и находится в переходном состоянии; процесс сущест-
вует, но не готов к выполнению, хотя и не приостановлен. Это состояние
является начальным состоянием всех процессов, кроме нулевого.
9. Процесс вызывает системную функцию exit и прекращает существование. Од-
нако, после него осталась запись, содержащая код выхода, и некоторая
хронометрическая статистика, собираемая родительским процессом. Это сос-
137
тояние является последним состоянием процесса. Рисунок 6.1 представляет
собой полную диаграмму переходов
процесса из состояния в состояние. Рассмотрим с помощью модели переходов ти-
пичное поведение процесса. Ситуации, которые будут обсуждаться, несколько
искусственны и процессы не всегда имеют дело с ними, но эти ситуации вполне
Выполняется в
режиме задачи
+-------+
| 1 |
Вызов функ- | |
ции, преры- ++------+
вание | ^ ^
Преры- +-----+ +-------+ | |
вание, | | | +-------+ +---+ Возврат в
возврат| | | | Возврат | режим задачи
из пре-| | | | |
рыва-| v v | Выполняет- |
+-------+ ния | +------++ся в режи- ++------+
| | +-->| |ме ядра | |
| 9 |<-----------+ 2 +------------>| 7 |
| | Выход | | Резервирует-| |
+-------+ ++------+ ся +-------+
Прекращение | ^ - Зарезер-
существования | | - вирован
+---------------+ +------+ --------
| Приостанов Запуск | -
v | -
При-+-------+ +-+-----+ Готов к
ос- | | Возобновление | | запуску
та- | 4 +----------------------->| 3 | в памяти
нов-| | | |
лен +---+---+ ++------+
в па- | | ^ ^
мяти | | | | Достаточно
| | | | памяти
| | | +---+
| Вы- Вы- | | |
| грузка грузка | | | Создан
| | |За- ++------+
| | |груз-| | fork
| | |ка | 8 |<-----
| | | ++------+
| | | | Недоста-
| | | +---+ точно
| | | | памяти
| | | | (только система
| | | | подкачки)
v v | v
+-------+ +---+---+
| | Возобновление | |
| 6 +----------------------->| 5 |
+-------+ +-------+
Приостановлен, Готов к запуску,
выгружен выгружен
Рисунок 6.1. Диаграмма переходов процесса из состояния в сос-
тояние
138
применимы для иллюстрации различных переходов. Начальным состоянием модели
является создание процесса родительским процессом с помощью системной функ-
ции fork; из этого состояния процесс неминуемо переходит в состояние готов-
ности к запуску (3 или 5). Для простоты предположим, что процесс перешел в
состояние "готовности к запуску в памяти" (3). Планировщик процессов в ко-
нечном счете выберет процесс для выполнения и процесс перейдет в состояние
"выполнения в режиме ядра", где доиграет до конца роль, отведенную ему функ-
цией fork.
После всего этого процесс может перейти в состояние "выполнения в режиме
задачи". По прохождении определенного периода времени может произойти преры-
вание работы процессора по таймеру и процесс снова перейдет в состояние "вы-
полнения в режиме ядра". Как только программа обработки прерывания закончит
работу, ядру может понадобиться подготовить к запуску другой процесс, поэто-
му первый процесс перейдет в состояние "резервирования", уступив дорогу вто-
рому процессу. Состояние "резервирования" в действительности не отличается
от состояния "готовности к запуску в памяти" (пунктирная линия на рисунке,
соединяющая между собой оба состояния, подчеркивает их эквивалентность), но
они выделяются в отдельные состояния, чтобы подчеркнуть, что процесс, выпол-
няющийся в режиме ядра, может быть зарезервирован только в том случае, если
он собирается вернуться в режим задачи. Следовательно, ядро может при необ-
ходимости подкачивать процесс из состояния "резервирования". При известных
условиях планировщик выберет процесс для исполнения и тот снова вернется в
состояние "выполнения в режиме задачи".
Когда процесс выполняет вызов системной функции, он из состояния "выпол-
нения в режиме задачи" переходит в состояние "выполнения в режиме ядра".
Предположим, что системной функции требуется ввод-вывод с диска и поэтому
процесс вынужден дожидаться завершения ввода-вывода. Он переходит в состоя-
ние "приостанова в памяти", в котором будет находиться до тех пор, пока не
получит извещения об окончании ввода-вывода. Когда ввод-вывод завершится,
произойдет аппаратное прерывание работы центрального процессора и программа
обработки прерывания возобновит выполнение процесса, в результате чего он
перейдет в состояние "готовности к запуску в памяти".
Предположим, что система выполняет множество процессов, которые одновре-
менно никак не могут поместиться в оперативной памяти, и программа подкачки
(нулевой процесс) выгружает один процесс, чтобы освободить место для другого
процесса, находящегося в состоянии "готов к запуску, но выгружен". Первый
процесс, выгруженный из оперативной памяти, переходит в то же состояние.
Когда программа подкачки выбирает наиболее подходящий процесс для загрузки в
оперативную память, этот процесс переходит в состояние "готовности к запуску
в памяти". Планировщик выбирает процесс для исполнения и он переходит в сос-
тояние "выполнения в режиме ядра". Когда процесс завершается, он исполняет
системную функцию exit, последовательно переходя в состояния "выполнения в
режиме ядра" и, наконец, в состояние "прекращения существования".
Процесс может управлять некоторыми из переходов на уровне задачи.
Во-первых, один процесс может создать другой процесс. Тем не менее, в какое
из состояний процесс перейдет после создания (т.е. в состояние "готов к вы-
полнению, находясь в памяти" или в состояние "готов к выполнению, но выгру-
жен") зависит уже от ядра. Процессу эти состояния не подконтрольны. Во-вто-
рых, процесс может обратиться к различным системным функциям, чтобы перейти
из состояния "выполнения в режиме задачи" в состояние "выполнения в режиме
ядра", а также перейти в режим ядра по своей собственной воле. Тем не менее,
момент возвращения из режима ядра от процесса уже не зависит; в результате
каких-то событий он может никогда не вернуться из этого режима и из него пе-
рейдет в состояние "прекращения существования" (см. раздел 7.2, где говорит-
ся о сигналах). Наконец, процесс может завершиться с помощью функции exit по
своей собственной воле, но как указывалось ранее, внешние события могут пот-
ребовать завершения процесса без явного обращения к функции exit. Все ос-
139
тальные переходы относятся к жестко закрепленной части модели, закодирован-
ной в ядре, и являются результатом определенных событий, реагируя на них в
соответствии с правилами, сформулированными в этой и последующих главах. Не-
которые из правил уже упоминались: например, то, что процесс может выгрузить
другой процесс, выполняющийся в ядре.
Две принадлежащие ядру структуры данных описывают процесс: запись в таб-
лице процессов и пространство процесса. Таблица процессов содержит поля, ко-
торые должны быть всегда доступны ядру, а пространство процесса - поля, не-
обходимость в которых возникает только у выполняющегося процесса. Поэтому
ядро выделяет место для пространства процесса только при создании процесса:
в нем нет необходимости, если записи в таблице процессов не соответствует
конкретный процесс.
Запись в таблице процессов состоит из следующих полей:
* Поле состояния, которое идентифицирует состояние процесса.
* Поля, используемые ядром при размещении процесса и его пространства в
основной или внешней памяти. Ядро использует информацию этих полей для
переключения контекста на процесс, когда процесс переходит из состояния
"готов к выполнению, находясь в памяти" в состояние "выполнения в режиме
ядра" или из состояния "резервирования" в состояние "выполнения в режиме
задачи". Кроме того, ядро использует эту информацию при перекачки про-
цессов из и в оперативную память (между двумя состояниями "в памяти" и
двумя состояниями "выгружен"). Запись в таблице процессов содержит также
поле, описывающее размер процесса и позволяющее ядру планировать выделе-
ние пространства для процесса.
* Несколько пользовательских идентификаторов (UID), устанавливающих раз-
личные привилегии процесса. Поля UID, например, описывают совокупность
процессов, могущих обмениваться сигналами (см. следующую главу).
* Идентификаторы процесса (PID), указывающие взаимосвязь между процессами.
Значения полей PID задаются при переходе процесса в состояние "создан"
во время выполнения функции fork.
* Дескриптор события (устанавливается тогда, когда процесс приостановлен).
В данной главе будет рассмотрено использование дескриптора события в ал-
горитмах функций sleep и wakeup.
* Параметры планирования, позволяющие ядру устанавливать порядок перехода
процессов из состояния "выполнения в режиме ядра" в состояние "выполне-
ния в режиме задачи".
* Поле сигналов, в котором перечисляются сигналы, посланные процессу, но
еще не обработанные (раздел 7.2).
* Различные таймеры, описывающие время выполнения процесса и использование
ресурсов ядра и позволяющие осуществлять слежение за выполнением и вы-
числять приоритет планирования процесса. Одно из полей является тайме-
ром, который устанавливает пользователь и который необходим для посылки
процессу сигнала тревоги (раздел 8.3). Пространство процесса содержит
поля, дополнительно характеризующие состояния процесса. В предыдущих
главах были рассмотрены последние семь из приводимых ниже полей прост-
ранства процесса, которые мы для полноты вновь кратко перечислим:
* Указатель на таблицу процессов, который идентифицирует запись, соответс-
твующую процессу.
* Пользовательские идентификаторы, устанавливающие различные привилегии
процесса, в частности, права доступа к файлу (см. раздел 7.6).
* Поля таймеров, хранящие время выполнения процесса (и его потомков) в ре-
жиме задачи и в режиме ядра.
* Вектор, описывающий реакцию процесса на сигналы.
* Поле операторского терминала, идентифицирующее "регистрационный терми-
нал", который связан с процессом.
* Поле ошибок, в которое записываются ошибки, имевшие место при выполнении
системной функции.
* Поле возвращенного значения, хранящее результат выполнения системной
функции.
140
* Параметры ввода-вывода: объем передаваемых данных, адрес источника (или
приемника) данных в пространстве задачи, смещения в файле (которыми
пользуются операции ввода-вывода) и т.д.
* Имена текущего каталога и текущего корня, описывающие файловую систему,
в которой выполняется процесс.
* Таблица пользовательских дескрипторов файла, которая описывает файлы,
открытые процессом.
* Поля границ, накладывающие ограничения на размерные характеристики про-
цесса и на размер файла, в который процесс может вести запись.
* Поле прав доступа, хранящее двоичную маску установок прав доступа к фай-
лам, которые создаются процессом. Пространство состояний процесса и пе-
реходов между ними рассматривалось в данном разделе на логическом уров-
не. Каждое состояние имеет также физические характеристики, управляемые
ядром, в частности, виртуальное адресное пространство процесса. Следую-
щий раздел посвящен описанию модели распределения памяти; в остальных
разделах состояния процесса и переходы между ними рассматриваются на фи-
зическом уровне, особое внимание при этом уделяется состояниям "выполне-
ния в режиме задачи", "выполнения в режиме ядра", "резервирования" и
"приостанова (в памяти)". В следующей главе затрагиваются состояния
"создания" и "прекращения существования", а в главе 8 - состояние "го-
товности к запуску в памяти". В главе 9 обсуждаются два состояния выгру-
женного процесса и организация подкачки по обращению.
Предположим, что физическая память машины имеет адреса, начиная с 0 и
кончая адресом, равным объему памяти в байтах. Как уже отмечалось в главе 2,
процесс в системе UNIX состоит из трех логических секций: команд, данных и
стека. (Общую память, которая рассматривается в главе 11, можно считать в
данном контексте частью секции данных). В секции команд хранится набор ма-
шинных инструкций, исполняемых под управлением процесса; адресами в секции
команд выступают адреса команд (для команд перехода и обращений к подпрог-
раммам), адреса данных (для обращения к глобальным переменным) и адреса сте-
ка (для обращения к структурам данных, которые локализованы в подпрограм-
мах). Если адреса в сгенерированном коде трактовать как адреса в физической
памяти, два процесса не смогут параллельно выполняться, если их адреса пе-
рекрываются. Компилятор мог бы генерировать адреса, непересекающиеся у раз-
ных программ, но на универсальных ЭВМ такой порядок не практикуется, пос-
кольку объем памяти машины ограничен, а количество транслируемых программы
неограничено. Даже если для того, чтобы избежать излишнего пересечения адре-
сов в процессе их генерации, машина будет использовать некоторый набор эв-
ристических процедур, подобная реализация не будет достаточно гибкой и не
сможет удовлетворять предъявляемым к ней требованиям.
Поэтому компилятор генерирует адреса для виртуального адресного прост-
ранства заданного диапазона, а устройство управления памятью, называемое
диспетчером памяти, транслирует виртуальные адреса, сгенерированные компиля-
тором, в адреса ячеек, расположенных в физической памяти. Компилятору нет
необходимости знать, в какое место в памяти ядро потом загрузит выполняемую
программу. На самом деле, в памяти одновременно могут существовать несколько
копий программы: все они могут выполняться, используя одни и те же виртуаль-
ные адреса, фактически же ссылаясь на разные физические ячейки. Те подсисте-
мы ядра и аппаратные средства, которые сотрудничают в трансляции виртуальных
адресов в физические, образуют подсистему управления памятью.
Ядро в версии V делит виртуальное адресное пространство процесса на со-
141
вокупность логических областей. Область - это непрерывная зона виртуального
адресного пространства процесса, рассматриваемая в качестве отдельного объ-
екта для совместного использования и защиты. Таким образом, команды, данные
и стек обычно образуют автономные области, принадлежащие процессу. Несколько
процессов могут использовать одну и ту же область. Например, если несколько
процессов выполняют одну и ту же программу, вполне естественно, что они ис-
пользуют одну и ту же область команд. Точно так же, несколько процессов мо-
гут объединиться и использовать общую область разделяемой памяти.
Ядро поддерживает таблицу областей и выделяет запись в таблице для каж-
дой активной области в системе. В разделе 6.5 описываются поля таблицы об-
ластей и операции над областями более подробно, но на данный момент предпо-
ложим, что таблица областей содержит информацию, позволяющую определить мес-
тоположение области в физической памяти. Каждый процесс имеет частную табли-
цу областей процесса. Записи этой таблицы могут располагаться, в зависимости
от конкретной реализации, в таблице процессов, в адресном пространстве про-
цесса или в отдельной области памяти; для простоты предположим, что они яв-
ляются частью таблицы процессов. Каждая запись частной таблицы областей со-
держит указатель на соответствующую запись общей таблицы областей и первый
виртуальный адрес процесса в данной области. Разделяемые области могут иметь
разные виртуальные адреса в каждом процессе. Запись частной таблицы областей
также содержит поле прав доступа, в котором указывается тип доступа, разре-
шенный процессу: только чтение, только запись или только исполнение. Частная
таблица областей и структура области аналогичны таблице файлов и структуре
индекса в файловой системе: несколько процессов могут совместно использовать
адресное пространство через область, подобно тому, как они разделяют доступ
к файлу с помощью индекса; каждый процесс имеет доступ к области благодаря
использованию записи в частной таблице областей, точно так же он обращается
к индексу, используя соответствующие записи в таблице пользовательских деск-
рипторов файла и в таблице файлов, принадлежащей ядру.
На Рисунке 6.2 изображены два процесса, A и B, показаны их области, час-
тные таблицы областей и виртуальные адреса, в которых эти области соединяют-
ся. Процессы разделяют область команд 'a' с виртуальными адресами 8К и 4К
соответственно. Если процесс A читает ячейку памяти с адресом 8К, а процесс
Частные таблицы областей Области
процесса
(Виртуальные адреса) +--------+
Коман-+--------------+ | |
ды | 8К +-----+ +-->| b |
Процесс Дан-+--------------+ | | | |
A ные | 16К +-----|---+ +--------+ +--------+
+--------------+ | | |
Стек | 32К +-----|-------------------->| c |
+--------------+ | +--------+ | |
+------>| | +--------+
| a |
Коман-+--------------+ +------>| |
ды | 4К +-----+ +--------+ +--------+
Процесс Дан-+--------------+ | |
B ные | 8К +-------------------------->| e |
+--------------+ +--------+ | |
Стек | 32К +-----+ | | +--------+
+--------------+ +------>| d |
| |
+--------+
Рисунок 6.2. Процессы и области
142
B читает ячейку с адресом 4К, то они читают одну и ту же ячейку в области
'a'. Область данных и область стека у каждого процесса свои.
Область является понятием, не зависящим от способа реализации управления
памятью в операционной системе. Управление памятью представляет собой сово-
купность действий, выполняемых ядром с целью повышения эффективности совмес-
тного использования оперативной памяти процессами. Примерами способов управ-
ления памятью могут служить рассматриваемые в главе 9 замещение страниц па-
мяти и подкачка по обращению. Понятие области также не зависит и от собст-
венно распределения памяти: например, от того, делится ли память на страницы
или на сегменты. С тем, чтобы заложить фундамент для перехода к описанию ал-
горитмов подкачки по обращению (глава 9), все приводимые здесь рассуждения
относятся, в первую очередь, к организации памяти, базирующейся на страни-
цах, однако это не предполагает, что система управления памятью основывается
на указанных алгоритмах.
В этом разделе описывается модель организации памяти, которой мы будем
пользоваться на протяжении всей книги, но которая не является особенностью
системы UNIX. В организации памяти, базирующейся на страницах, физическая
память разделяется на блоки одинакового размера, называемые страницами.
Обычный размер страниц составляет от 512 байт до 4 Кбайт и определяется кон-
фигурацией технических средств. Каждая адресуемая ячейка памяти содержится в
некоторой странице и, следовательно, каждая ячейка памяти может адресоваться
парой (номер страницы, смещение внутри страницы в байтах). Например, если
объем машинной памяти составляет 2 в 32-й степени байт, а размер страницы 1
Кбайт, общее число страниц - 2 в 22-й степени; можно считать, что каждый
32-разрядный адрес состоит из 22-разрядного номера страницы и 10-разрядного
смещения внутри страницы (Рисунок 6.3).
Когда ядро назначает области физические страницы памяти, необходимости в
назначении смежных страниц и вообще в соблюдении какой-либо очередности при
назначении не возникает. Целью страничной организации памяти является повы-
+------------------------------------------------------------+
| Шестнадцатиричный адрес 58432 |
| |
| Двоичный 0101 1000 0100 0011 0010 |
| |
| Номер страницы, смещение |
| внутри страницы 01 0110 0001 00 0011 0010 |
| |
| В шестнадцатиричной системе 161 32 |
+------------------------------------------------------------+
Рисунок 6.3. Адресация физической памяти по страницам
+------------------------------------------------------+
| Логический номер страницы Физический номер страницы |
| |
| 0 177 |
| 1 54 |
| 2 209 |
| 3 17 |
+------------------------------------------------------+
Рисунок 6.4. Отображение логических номеров страниц на физические
143
шение гибкости назначения физической памяти, которое строится по аналогии с
назначением дисковых блоков файлам в файловой системе. Как и при назначении
блоков файлу, так и при назначении области страниц памяти, преследуется за-
дача повышения гибкости и сокращения неиспользуемого (вследствие фрагмента-
ции) пространства памяти.
Ядро устанавливает соотношение между виртуальными адресами области и ма-
шинными физическими адресами посредством отображения логических номеров
страниц в области на физические номера страниц в машине, как это показано на
Рисунке 6.4. Поскольку область это непрерывное пространство виртуальных ад-
ресов программы, логический номер страницы служит указателем на элемент мас-
сива физических номеров страниц. Запись таблицы областей содержит указатель
на таблицу физических номеров страниц, именуемую таблицей страниц. Записи
таблицы страниц содержат машинно-зависимую информацию, такую как права дос-
тупа на чтение или запись страницы. Ядро поддерживает таблицы страниц в па-
мяти и обращается к ним так же, как и ко всем остальным структурам данных
ядра.
На Рисунке 6.5 приведен пример отображения процесса в физические адреса
памяти. Пусть размер страницы составляет 1 Кбайт и пусть процессу нужно об-
ратиться к объекту в памяти, имеющему виртуальный адрес 68432. Из таблицы
областей видно, что виртуальный адрес начала области стека - 65536 (64К),
если предположить, что стек растет в направлении увеличения адресов. После
вычитания этого адреса из адреса 68432 получаем смещение в байтах внутри об-
ласти, равное 2896. Так как каждая страница имеет размер 1 Кбайт, адрес ука-
зывает со смещением 848 на 2-ю (начиная с 0) страницу области, расположенной
ве на более формальном уровне определяется понятие "контекст процесса" и по-
казывается, каким образом ядро идентифицирует процесс и определяет его мес-
тонахождение. В разделе 6.1 описаны модель состояний процессов для системы
UNIX и последовательность возможных переходов из состояния в состояние. В
ядре находится таблица процессов, каждая запись которой описывает состояние
одного из активных процессов в системе. В пространстве процесса хранится до-
полнительная информация, используемая в управлении протеканием процесса. За-
пись в таблице процессов и пространство процесса составляют в совокупности
контекст процесса. Аспектом контекста процесса, наиболее явно отличающим
данный контекст от контекста другого процесса, без сомнения является содер-
жимое адресного пространства процесса. В разделе 6.2 описываются принципы
управления распределением памяти для процессов и ядра, а также взаимодейст-
вие операционной системы с аппаратными средствами при трансляции виртуальных
адресов в физические. Раздел 6.3 посвящен рассмотрению составных элементов
контекста процесса, а также описанию алгоритмов управления контекстом про-
цесса. Раздел 6.4 демонстрирует, каким образом осуществляется сохранение
контекста процесса ядром в случае прерывания, вызова системной функции или
переключения контекста, а также каким образом возобновляется выполнение при-
остановленного процесса. В разделе 6.5 приводятся различные алгоритмы, ис-
пользуемые в тех системных функциях, которые работают с адресным пространст-
вом процесса и которые будут рассмотрены в следующей главе. И, наконец, в
разделе 6.6 рассматриваются алгоритмы приостанова и возобновления выполнения
процессов.
Как уже отмечалось в главе 2, время жизни процесса можно теоретически
разбить на несколько состояний, описывающих процесс. Полный набор состояний
процесса содержится в следующем перечне:
1. Процесс выполняется в режиме задачи.
2. Процесс выполняется в режиме ядра.
3. Процесс не выполняется, но готов к запуску под управлением ядра.
4. Процесс приостановлен и находится в оперативной памяти.
5. Процесс готов к запуску, но программа подкачки (нулевой процесс) должна
еще загрузить процесс в оперативную память, прежде чем он будет запущен
под управлением ядра. Это состояние будет предметом обсуждения в главе 9
при рассмотрении системы подкачки.
6. Процесс приостановлен и программа подкачки выгрузила его во внешнюю па-
мять, чтобы в оперативной памяти освободить место для других процессов.
7. Процесс возвращен из привилегированного режима (режима ядра) в неприви-
легированный (режим задачи), ядро резервирует его и переключает контекст
на другой процесс. Об отличии этого состояния от состояния 3 (готовность
к запуску) пойдет речь ниже.
8. Процесс вновь создан и находится в переходном состоянии; процесс сущест-
вует, но не готов к выполнению, хотя и не приостановлен. Это состояние
является начальным состоянием всех процессов, кроме нулевого.
9. Процесс вызывает системную функцию exit и прекращает существование. Од-
нако, после него осталась запись, содержащая код выхода, и некоторая
хронометрическая статистика, собираемая родительским процессом. Это сос-
137
тояние является последним состоянием процесса. Рисунок 6.1 представляет
собой полную диаграмму переходов
процесса из состояния в состояние. Рассмотрим с помощью модели переходов ти-
пичное поведение процесса. Ситуации, которые будут обсуждаться, несколько
искусственны и процессы не всегда имеют дело с ними, но эти ситуации вполне
Выполняется в
режиме задачи
+-------+
| 1 |
Вызов функ- | |
ции, преры- ++------+
вание | ^ ^
Преры- +-----+ +-------+ | |
вание, | | | +-------+ +---+ Возврат в
возврат| | | | Возврат | режим задачи
из пре-| | | | |
рыва-| v v | Выполняет- |
+-------+ ния | +------++ся в режи- ++------+
| | +-->| |ме ядра | |
| 9 |<-----------+ 2 +------------>| 7 |
| | Выход | | Резервирует-| |
+-------+ ++------+ ся +-------+
Прекращение | ^ - Зарезер-
существования | | - вирован
+---------------+ +------+ --------
| Приостанов Запуск | -
v | -
При-+-------+ +-+-----+ Готов к
ос- | | Возобновление | | запуску
та- | 4 +----------------------->| 3 | в памяти
нов-| | | |
лен +---+---+ ++------+
в па- | | ^ ^
мяти | | | | Достаточно
| | | | памяти
| | | +---+
| Вы- Вы- | | |
| грузка грузка | | | Создан
| | |За- ++------+
| | |груз-| | fork
| | |ка | 8 |<-----
| | | ++------+
| | | | Недоста-
| | | +---+ точно
| | | | памяти
| | | | (только система
| | | | подкачки)
v v | v
+-------+ +---+---+
| | Возобновление | |
| 6 +----------------------->| 5 |
+-------+ +-------+
Приостановлен, Готов к запуску,
выгружен выгружен
Рисунок 6.1. Диаграмма переходов процесса из состояния в сос-
тояние
138
применимы для иллюстрации различных переходов. Начальным состоянием модели
является создание процесса родительским процессом с помощью системной функ-
ции fork; из этого состояния процесс неминуемо переходит в состояние готов-
ности к запуску (3 или 5). Для простоты предположим, что процесс перешел в
состояние "готовности к запуску в памяти" (3). Планировщик процессов в ко-
нечном счете выберет процесс для выполнения и процесс перейдет в состояние
"выполнения в режиме ядра", где доиграет до конца роль, отведенную ему функ-
цией fork.
После всего этого процесс может перейти в состояние "выполнения в режиме
задачи". По прохождении определенного периода времени может произойти преры-
вание работы процессора по таймеру и процесс снова перейдет в состояние "вы-
полнения в режиме ядра". Как только программа обработки прерывания закончит
работу, ядру может понадобиться подготовить к запуску другой процесс, поэто-
му первый процесс перейдет в состояние "резервирования", уступив дорогу вто-
рому процессу. Состояние "резервирования" в действительности не отличается
от состояния "готовности к запуску в памяти" (пунктирная линия на рисунке,
соединяющая между собой оба состояния, подчеркивает их эквивалентность), но
они выделяются в отдельные состояния, чтобы подчеркнуть, что процесс, выпол-
няющийся в режиме ядра, может быть зарезервирован только в том случае, если
он собирается вернуться в режим задачи. Следовательно, ядро может при необ-
ходимости подкачивать процесс из состояния "резервирования". При известных
условиях планировщик выберет процесс для исполнения и тот снова вернется в
состояние "выполнения в режиме задачи".
Когда процесс выполняет вызов системной функции, он из состояния "выпол-
нения в режиме задачи" переходит в состояние "выполнения в режиме ядра".
Предположим, что системной функции требуется ввод-вывод с диска и поэтому
процесс вынужден дожидаться завершения ввода-вывода. Он переходит в состоя-
ние "приостанова в памяти", в котором будет находиться до тех пор, пока не
получит извещения об окончании ввода-вывода. Когда ввод-вывод завершится,
произойдет аппаратное прерывание работы центрального процессора и программа
обработки прерывания возобновит выполнение процесса, в результате чего он
перейдет в состояние "готовности к запуску в памяти".
Предположим, что система выполняет множество процессов, которые одновре-
менно никак не могут поместиться в оперативной памяти, и программа подкачки
(нулевой процесс) выгружает один процесс, чтобы освободить место для другого
процесса, находящегося в состоянии "готов к запуску, но выгружен". Первый
процесс, выгруженный из оперативной памяти, переходит в то же состояние.
Когда программа подкачки выбирает наиболее подходящий процесс для загрузки в
оперативную память, этот процесс переходит в состояние "готовности к запуску
в памяти". Планировщик выбирает процесс для исполнения и он переходит в сос-
тояние "выполнения в режиме ядра". Когда процесс завершается, он исполняет
системную функцию exit, последовательно переходя в состояния "выполнения в
режиме ядра" и, наконец, в состояние "прекращения существования".
Процесс может управлять некоторыми из переходов на уровне задачи.
Во-первых, один процесс может создать другой процесс. Тем не менее, в какое
из состояний процесс перейдет после создания (т.е. в состояние "готов к вы-
полнению, находясь в памяти" или в состояние "готов к выполнению, но выгру-
жен") зависит уже от ядра. Процессу эти состояния не подконтрольны. Во-вто-
рых, процесс может обратиться к различным системным функциям, чтобы перейти
из состояния "выполнения в режиме задачи" в состояние "выполнения в режиме
ядра", а также перейти в режим ядра по своей собственной воле. Тем не менее,
момент возвращения из режима ядра от процесса уже не зависит; в результате
каких-то событий он может никогда не вернуться из этого режима и из него пе-
рейдет в состояние "прекращения существования" (см. раздел 7.2, где говорит-
ся о сигналах). Наконец, процесс может завершиться с помощью функции exit по
своей собственной воле, но как указывалось ранее, внешние события могут пот-
ребовать завершения процесса без явного обращения к функции exit. Все ос-
139
тальные переходы относятся к жестко закрепленной части модели, закодирован-
ной в ядре, и являются результатом определенных событий, реагируя на них в
соответствии с правилами, сформулированными в этой и последующих главах. Не-
которые из правил уже упоминались: например, то, что процесс может выгрузить
другой процесс, выполняющийся в ядре.
Две принадлежащие ядру структуры данных описывают процесс: запись в таб-
лице процессов и пространство процесса. Таблица процессов содержит поля, ко-
торые должны быть всегда доступны ядру, а пространство процесса - поля, не-
обходимость в которых возникает только у выполняющегося процесса. Поэтому
ядро выделяет место для пространства процесса только при создании процесса:
в нем нет необходимости, если записи в таблице процессов не соответствует
конкретный процесс.
Запись в таблице процессов состоит из следующих полей:
* Поле состояния, которое идентифицирует состояние процесса.
* Поля, используемые ядром при размещении процесса и его пространства в
основной или внешней памяти. Ядро использует информацию этих полей для
переключения контекста на процесс, когда процесс переходит из состояния
"готов к выполнению, находясь в памяти" в состояние "выполнения в режиме
ядра" или из состояния "резервирования" в состояние "выполнения в режиме
задачи". Кроме того, ядро использует эту информацию при перекачки про-
цессов из и в оперативную память (между двумя состояниями "в памяти" и
двумя состояниями "выгружен"). Запись в таблице процессов содержит также
поле, описывающее размер процесса и позволяющее ядру планировать выделе-
ние пространства для процесса.
* Несколько пользовательских идентификаторов (UID), устанавливающих раз-
личные привилегии процесса. Поля UID, например, описывают совокупность
процессов, могущих обмениваться сигналами (см. следующую главу).
* Идентификаторы процесса (PID), указывающие взаимосвязь между процессами.
Значения полей PID задаются при переходе процесса в состояние "создан"
во время выполнения функции fork.
* Дескриптор события (устанавливается тогда, когда процесс приостановлен).
В данной главе будет рассмотрено использование дескриптора события в ал-
горитмах функций sleep и wakeup.
* Параметры планирования, позволяющие ядру устанавливать порядок перехода
процессов из состояния "выполнения в режиме ядра" в состояние "выполне-
ния в режиме задачи".
* Поле сигналов, в котором перечисляются сигналы, посланные процессу, но
еще не обработанные (раздел 7.2).
* Различные таймеры, описывающие время выполнения процесса и использование
ресурсов ядра и позволяющие осуществлять слежение за выполнением и вы-
числять приоритет планирования процесса. Одно из полей является тайме-
ром, который устанавливает пользователь и который необходим для посылки
процессу сигнала тревоги (раздел 8.3). Пространство процесса содержит
поля, дополнительно характеризующие состояния процесса. В предыдущих
главах были рассмотрены последние семь из приводимых ниже полей прост-
ранства процесса, которые мы для полноты вновь кратко перечислим:
* Указатель на таблицу процессов, который идентифицирует запись, соответс-
твующую процессу.
* Пользовательские идентификаторы, устанавливающие различные привилегии
процесса, в частности, права доступа к файлу (см. раздел 7.6).
* Поля таймеров, хранящие время выполнения процесса (и его потомков) в ре-
жиме задачи и в режиме ядра.
* Вектор, описывающий реакцию процесса на сигналы.
* Поле операторского терминала, идентифицирующее "регистрационный терми-
нал", который связан с процессом.
* Поле ошибок, в которое записываются ошибки, имевшие место при выполнении
системной функции.
* Поле возвращенного значения, хранящее результат выполнения системной
функции.
140
* Параметры ввода-вывода: объем передаваемых данных, адрес источника (или
приемника) данных в пространстве задачи, смещения в файле (которыми
пользуются операции ввода-вывода) и т.д.
* Имена текущего каталога и текущего корня, описывающие файловую систему,
в которой выполняется процесс.
* Таблица пользовательских дескрипторов файла, которая описывает файлы,
открытые процессом.
* Поля границ, накладывающие ограничения на размерные характеристики про-
цесса и на размер файла, в который процесс может вести запись.
* Поле прав доступа, хранящее двоичную маску установок прав доступа к фай-
лам, которые создаются процессом. Пространство состояний процесса и пе-
реходов между ними рассматривалось в данном разделе на логическом уров-
не. Каждое состояние имеет также физические характеристики, управляемые
ядром, в частности, виртуальное адресное пространство процесса. Следую-
щий раздел посвящен описанию модели распределения памяти; в остальных
разделах состояния процесса и переходы между ними рассматриваются на фи-
зическом уровне, особое внимание при этом уделяется состояниям "выполне-
ния в режиме задачи", "выполнения в режиме ядра", "резервирования" и
"приостанова (в памяти)". В следующей главе затрагиваются состояния
"создания" и "прекращения существования", а в главе 8 - состояние "го-
товности к запуску в памяти". В главе 9 обсуждаются два состояния выгру-
женного процесса и организация подкачки по обращению.
Предположим, что физическая память машины имеет адреса, начиная с 0 и
кончая адресом, равным объему памяти в байтах. Как уже отмечалось в главе 2,
процесс в системе UNIX состоит из трех логических секций: команд, данных и
стека. (Общую память, которая рассматривается в главе 11, можно считать в
данном контексте частью секции данных). В секции команд хранится набор ма-
шинных инструкций, исполняемых под управлением процесса; адресами в секции
команд выступают адреса команд (для команд перехода и обращений к подпрог-
раммам), адреса данных (для обращения к глобальным переменным) и адреса сте-
ка (для обращения к структурам данных, которые локализованы в подпрограм-
мах). Если адреса в сгенерированном коде трактовать как адреса в физической
памяти, два процесса не смогут параллельно выполняться, если их адреса пе-
рекрываются. Компилятор мог бы генерировать адреса, непересекающиеся у раз-
ных программ, но на универсальных ЭВМ такой порядок не практикуется, пос-
кольку объем памяти машины ограничен, а количество транслируемых программы
неограничено. Даже если для того, чтобы избежать излишнего пересечения адре-
сов в процессе их генерации, машина будет использовать некоторый набор эв-
ристических процедур, подобная реализация не будет достаточно гибкой и не
сможет удовлетворять предъявляемым к ней требованиям.
Поэтому компилятор генерирует адреса для виртуального адресного прост-
ранства заданного диапазона, а устройство управления памятью, называемое
диспетчером памяти, транслирует виртуальные адреса, сгенерированные компиля-
тором, в адреса ячеек, расположенных в физической памяти. Компилятору нет
необходимости знать, в какое место в памяти ядро потом загрузит выполняемую
программу. На самом деле, в памяти одновременно могут существовать несколько
копий программы: все они могут выполняться, используя одни и те же виртуаль-
ные адреса, фактически же ссылаясь на разные физические ячейки. Те подсисте-
мы ядра и аппаратные средства, которые сотрудничают в трансляции виртуальных
адресов в физические, образуют подсистему управления памятью.
Ядро в версии V делит виртуальное адресное пространство процесса на со-
141
вокупность логических областей. Область - это непрерывная зона виртуального
адресного пространства процесса, рассматриваемая в качестве отдельного объ-
екта для совместного использования и защиты. Таким образом, команды, данные
и стек обычно образуют автономные области, принадлежащие процессу. Несколько
процессов могут использовать одну и ту же область. Например, если несколько
процессов выполняют одну и ту же программу, вполне естественно, что они ис-
пользуют одну и ту же область команд. Точно так же, несколько процессов мо-
гут объединиться и использовать общую область разделяемой памяти.
Ядро поддерживает таблицу областей и выделяет запись в таблице для каж-
дой активной области в системе. В разделе 6.5 описываются поля таблицы об-
ластей и операции над областями более подробно, но на данный момент предпо-
ложим, что таблица областей содержит информацию, позволяющую определить мес-
тоположение области в физической памяти. Каждый процесс имеет частную табли-
цу областей процесса. Записи этой таблицы могут располагаться, в зависимости
от конкретной реализации, в таблице процессов, в адресном пространстве про-
цесса или в отдельной области памяти; для простоты предположим, что они яв-
ляются частью таблицы процессов. Каждая запись частной таблицы областей со-
держит указатель на соответствующую запись общей таблицы областей и первый
виртуальный адрес процесса в данной области. Разделяемые области могут иметь
разные виртуальные адреса в каждом процессе. Запись частной таблицы областей
также содержит поле прав доступа, в котором указывается тип доступа, разре-
шенный процессу: только чтение, только запись или только исполнение. Частная
таблица областей и структура области аналогичны таблице файлов и структуре
индекса в файловой системе: несколько процессов могут совместно использовать
адресное пространство через область, подобно тому, как они разделяют доступ
к файлу с помощью индекса; каждый процесс имеет доступ к области благодаря
использованию записи в частной таблице областей, точно так же он обращается
к индексу, используя соответствующие записи в таблице пользовательских деск-
рипторов файла и в таблице файлов, принадлежащей ядру.
На Рисунке 6.2 изображены два процесса, A и B, показаны их области, час-
тные таблицы областей и виртуальные адреса, в которых эти области соединяют-
ся. Процессы разделяют область команд 'a' с виртуальными адресами 8К и 4К
соответственно. Если процесс A читает ячейку памяти с адресом 8К, а процесс
Частные таблицы областей Области
процесса
(Виртуальные адреса) +--------+
Коман-+--------------+ | |
ды | 8К +-----+ +-->| b |
Процесс Дан-+--------------+ | | | |
A ные | 16К +-----|---+ +--------+ +--------+
+--------------+ | | |
Стек | 32К +-----|-------------------->| c |
+--------------+ | +--------+ | |
+------>| | +--------+
| a |
Коман-+--------------+ +------>| |
ды | 4К +-----+ +--------+ +--------+
Процесс Дан-+--------------+ | |
B ные | 8К +-------------------------->| e |
+--------------+ +--------+ | |
Стек | 32К +-----+ | | +--------+
+--------------+ +------>| d |
| |
+--------+
Рисунок 6.2. Процессы и области
142
B читает ячейку с адресом 4К, то они читают одну и ту же ячейку в области
'a'. Область данных и область стека у каждого процесса свои.
Область является понятием, не зависящим от способа реализации управления
памятью в операционной системе. Управление памятью представляет собой сово-
купность действий, выполняемых ядром с целью повышения эффективности совмес-
тного использования оперативной памяти процессами. Примерами способов управ-
ления памятью могут служить рассматриваемые в главе 9 замещение страниц па-
мяти и подкачка по обращению. Понятие области также не зависит и от собст-
венно распределения памяти: например, от того, делится ли память на страницы
или на сегменты. С тем, чтобы заложить фундамент для перехода к описанию ал-
горитмов подкачки по обращению (глава 9), все приводимые здесь рассуждения
относятся, в первую очередь, к организации памяти, базирующейся на страни-
цах, однако это не предполагает, что система управления памятью основывается
на указанных алгоритмах.
В этом разделе описывается модель организации памяти, которой мы будем
пользоваться на протяжении всей книги, но которая не является особенностью
системы UNIX. В организации памяти, базирующейся на страницах, физическая
память разделяется на блоки одинакового размера, называемые страницами.
Обычный размер страниц составляет от 512 байт до 4 Кбайт и определяется кон-
фигурацией технических средств. Каждая адресуемая ячейка памяти содержится в
некоторой странице и, следовательно, каждая ячейка памяти может адресоваться
парой (номер страницы, смещение внутри страницы в байтах). Например, если
объем машинной памяти составляет 2 в 32-й степени байт, а размер страницы 1
Кбайт, общее число страниц - 2 в 22-й степени; можно считать, что каждый
32-разрядный адрес состоит из 22-разрядного номера страницы и 10-разрядного
смещения внутри страницы (Рисунок 6.3).
Когда ядро назначает области физические страницы памяти, необходимости в
назначении смежных страниц и вообще в соблюдении какой-либо очередности при
назначении не возникает. Целью страничной организации памяти является повы-
+------------------------------------------------------------+
| Шестнадцатиричный адрес 58432 |
| |
| Двоичный 0101 1000 0100 0011 0010 |
| |
| Номер страницы, смещение |
| внутри страницы 01 0110 0001 00 0011 0010 |
| |
| В шестнадцатиричной системе 161 32 |
+------------------------------------------------------------+
Рисунок 6.3. Адресация физической памяти по страницам
+------------------------------------------------------+
| Логический номер страницы Физический номер страницы |
| |
| 0 177 |
| 1 54 |
| 2 209 |
| 3 17 |
+------------------------------------------------------+
Рисунок 6.4. Отображение логических номеров страниц на физические
143
шение гибкости назначения физической памяти, которое строится по аналогии с
назначением дисковых блоков файлам в файловой системе. Как и при назначении
блоков файлу, так и при назначении области страниц памяти, преследуется за-
дача повышения гибкости и сокращения неиспользуемого (вследствие фрагмента-
ции) пространства памяти.
Ядро устанавливает соотношение между виртуальными адресами области и ма-
шинными физическими адресами посредством отображения логических номеров
страниц в области на физические номера страниц в машине, как это показано на
Рисунке 6.4. Поскольку область это непрерывное пространство виртуальных ад-
ресов программы, логический номер страницы служит указателем на элемент мас-
сива физических номеров страниц. Запись таблицы областей содержит указатель
на таблицу физических номеров страниц, именуемую таблицей страниц. Записи
таблицы страниц содержат машинно-зависимую информацию, такую как права дос-
тупа на чтение или запись страницы. Ядро поддерживает таблицы страниц в па-
мяти и обращается к ним так же, как и ко всем остальным структурам данных
ядра.
На Рисунке 6.5 приведен пример отображения процесса в физические адреса
памяти. Пусть размер страницы составляет 1 Кбайт и пусть процессу нужно об-
ратиться к объекту в памяти, имеющему виртуальный адрес 68432. Из таблицы
областей видно, что виртуальный адрес начала области стека - 65536 (64К),
если предположить, что стек растет в направлении увеличения адресов. После
вычитания этого адреса из адреса 68432 получаем смещение в байтах внутри об-
ласти, равное 2896. Так как каждая страница имеет размер 1 Кбайт, адрес ука-
зывает со смещением 848 на 2-ю (начиная с 0) страницу области, расположенной