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

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

Выполняется в

режиме задачи

--------¬

¦ 1 ¦

Вызов функ- ¦ ¦

вание ¦ ^ ^

Преры- ------¬ --------- ¦ ¦

вание, ¦ ¦ ¦ --------- L---¬ Возврат в

возврат¦ ¦ ¦ ¦ Возврат ¦ режим задачи

рыва-¦ v v ¦ Выполняет- ¦

--------¬ ния ¦ -------+¬ся в режи- -+------¬

¦ ¦ L-->¦ ¦ме ядра ¦ ¦

¦ 9 ¦<-----------+ 2 +------------>¦ 7 ¦

¦ ¦ Выход ¦ ¦ Резервирует-¦ ¦

L-------- LT------- ся L--------

Прекращение ¦ ^ • Зарезер-

существования ¦ ¦ • вирован

----------------- L------¬ ••••••••

¦ Приостанов Запуск ¦ •

v ¦ •

При---------¬ --+-----¬ Готов к

ос- ¦ ¦ Возобновление ¦ ¦ запуску

та- ¦ 4 +----------------------->¦ 3 ¦ в памяти

нов-¦ ¦ ¦ ¦

лен L---T---- LT-------

в па- ¦ ¦ ^ ^

мяти ¦ ¦ ¦ ¦ Достаточно

¦ ¦ ¦ L---¬

¦ Вы- Вы- ¦ ¦ ¦

¦ грузка грузка ¦ ¦ ¦ Создан

¦ ¦ ¦За- -+------¬

¦ ¦ ¦ка ¦ 8 ¦<-----

¦ ¦ ¦ LT-------

¦ ¦ ¦ ¦ Недоста-

¦ ¦ ¦ ¦ памяти

¦ ¦ ¦ ¦ (только система

¦ ¦ ¦ ¦ подкачки)

v v ¦ v

--------¬ ----+---¬

¦ ¦ Возобновление ¦ ¦

¦ 6 +----------------------->¦ 5 ¦

L-------- L--------

Приостановлен, Готов к запуску,

выгружен выгружен

Рисунок 6.1. Диаграмма переходов процесса из состояния в состояние

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

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

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

Процесс может управлять некоторыми из переходов на уровне задачи. Во-первых, один процесс может создать другой процесс. Тем не менее, в какое из состояний процесс перейдет после создания (т.е. в состояние "готов к выполнению, находясь в памяти" или в состояние "готов к выполнению, но выгружен") зависит уже от ядра. Процессу эти состояния не подконтрольны. Во-вторых, процесс может обратиться к различным системным функциям, чтобы перейти из состояния "выполнения в режиме задачи" в состояние "выполнения в режиме ядра", а также перейти в режим ядра по своей собственной воле. Тем не менее, момент возвращения из режима ядра от процесса уже не зависит; в результате каких-то событий он может никогда не вернуться из этого режима и из него перейдет в состояние "прекращения существования" (см. раздел 7.2, где говорится о сигналах). Наконец, процесс может завершиться с помощью функции exit по своей собственной воле, но как указывалось ранее, внешние события могут потребовать завершения процесса без явного обращения к функции exit. Все остальные переходы относятся к жестко закрепленной части модели, закодированной в ядре, и являются результатом определенных событий, реагируя на них в соответствии с правилами, сформулированными в этой и последующих главах. Некоторые из правил уже упоминались: например, то, что процесс может выгрузить другой процесс, выполняющийся в ядре.

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

Запись в таблице процессов состоит из следующих полей:

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

Ядро в версии V делит виртуальное адресное пространство процесса на совокупность логических областей. Область - это непрерывная зона виртуального адресного пространства процесса, рассматриваемая в качестве отдельного объекта для совместного использования и защиты. Таким образом, команды, данные и стек обычно образуют автономные области, принадлежащие процессу. Несколько процессов могут использовать одну и ту же область. Например, если несколько процессов выполняют одну и ту же программу, вполне естественно, что они используют одну и ту же область команд. Точно так же, несколько процессов могут объединиться и использовать общую область разделяемой памяти.

На Рисунке 6.2 изображены два процесса, A и B, показаны их области, частные таблицы областей и виртуальные адреса, в которых эти области соединяются. Процессы разделяют область команд 'a' с виртуальными адресами 8К и 4К соответственно. Если процесс A читает ячейку памяти с адресом 8К, а процесс

Частные таблицы областей Области

(Виртуальные адреса) ---------¬

Коман----------------¬ ¦ ¦

ды ¦ 8К +-----¬ --->¦ b ¦ Процесс Дан-+--------------+ ¦ ¦ ¦ ¦

+--------------+ ¦ ¦ ¦

Стек ¦ 32К +-----¦-------------------->¦ c ¦

L--------------- ¦ ---------¬ ¦ ¦

L------>¦ ¦ L---------

¦ a ¦

Коман----------------¬ ------->¦ ¦

ды ¦ 4К +------ L--------- ---------¬ Процесс Дан-+--------------+ ¦ ¦

B ные ¦ 8К +-------------------------->¦ e ¦

+--------------+ ---------¬ ¦ ¦

Стек ¦ 32К +-----¬ ¦ ¦ L---------

L--------------- L------>¦ d ¦

¦ ¦

L---------

Рисунок 6.2. Процессы и области

B читает ячейку с адресом 4К, то они читают одну и ту же ячейку в области 'a'. Область данных и область стека у каждого процесса свои.

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

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

-------------------------------------------------------------¬

¦ Шестнадцатиричный адрес 58432 ¦

¦ ¦

¦ Двоичный 0101 1000 0100 0011 0010 ¦

¦ ¦

¦ Номер страницы, смещение ¦

¦ внутри страницы 01 0110 0001 00 0011 0010 ¦

¦ ¦

L-------------------------------------------------------------

Рисунок 6.3. Адресация физической памяти по страницам

-------------------------------------------------------¬

¦ Логический номер страницы Физический номер страницы ¦

¦ ¦

¦ 0 177 ¦

¦ 1 54 ¦

¦ 2 209 ¦

¦ 3 17 ¦

L-------------------------------------------------------

Рисунок 6.4. Отображение логических номеров страниц на физические

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

На Рисунке 6.5 приведен пример отображения процесса в физические адреса памяти. Пусть размер страницы составляет 1 Кбайт и пусть процессу нужно обратиться к объекту в памяти, имеющему виртуальный адрес 68432. Из таблицы областей видно, что виртуальный адрес начала области стека - 65536 (64К), если предположить, что стек растет в направлении увеличения адресов. После вычитания этого адреса из адреса 68432 получаем смещение в байтах внутри области, равное 2896. Так как каждая страница имеет размер 1 Кбайт, адрес указывает со смещением 848 на 2-ю (начиная с 0) страницу области, расположенной по физическому адресу 986К. В разделе 6.5.5 (где идет речь о загрузке области) рассматривается случай, когда запись таблицы страниц помечается "пустой".

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

Частная таблица областей Таблицы страниц

процесса (Физические адреса)

---------------¬

Команды ¦ 8К +--------------¬

+--------------+ L-------->---------------¬

Данные ¦ 32К +-------¬ ¦ пусто ¦

+--------------+ ¦ +--------------+

Стек ¦ 64К +---¬ ¦ ¦ 137К ¦

L--------------- ¦ v +--------------+

Виртуальные адреса ¦ ---------------¬ ¦ 852К ¦

¦ ¦ 87К ¦ +--------------+

v ¦ 552К ¦ +--------------+

---------------¬ +--------------+ ¦ 433К ¦

¦ 541К ¦ ¦ 727К ¦ +--------------+

¦ 783К ¦ ¦ 941К ¦ +--------------+

+--------------+ +--------------+ ¦ • ¦

¦ 986К ¦ ¦ 1096К ¦ ¦ • ¦

+--------------+ +--------------+ ¦ • ¦

¦ 897К ¦ ¦ 2001К ¦ ¦ • ¦

+--------------+ +--------------+ L---------------

¦ • ¦ ¦ • ¦

L--------------- L---------------

Рисунок 6.5. Преобразование виртуальных адресов в физические

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

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

Если процесс обращается к ячейкам памяти, расположенным за пределами принадлежащего ему виртуального пространства, создается исключительная ситуация. Например, если область команд имеет размер 16 Кбайт (Рисунок 6.5), а процесс обращается к виртуальному адресу 26К, создается исключительная ситуация, обрабатываемая операционной системой. То же самое происходит, если процесс пытается обратиться к памяти, не имея соответствующих прав доступа, например, пытается записать адрес в защищенную от записи область команд. И в том, и в другом примере процесс обычно завершается (более подробно об этом в следующей главе).

На Рисунке 6.6 приведен пример, в котором виртуальные адреса от 0 до 4М-1 принадлежат ядру, а начиная с 4М - процессу. Имеются две группы регистров управления памятью, одна для адресов ядра и одна для адресов процесса, причем каждой группе соответствует таблица страниц, хранящая номера физических страниц со ссылкой на адреса виртуальных страниц. Адресные ссылки с использованием группы регистров ядра допускаются системой только в режиме ядра; следовательно, для перехода между режимом ядра и режимом задачи требуется только, чтобы система разрешила или запретила адресные ссылки с использованием группы регистров ядра.

Адрес таблицы Вирту- Номера стра-

страниц альный ниц в табли-

------------T------------T-----------¬

Регистр ядра 1 ¦ --------¬ 0 ¦ ¦

+-----------+-¦----------+-----------+

+--------¦--+-¦----------+-----------+

Регистр ядра 3 ¦ --¬¦ ¦ ¦ 2М ¦ ¦

+-------¦¦--+-¦----------+-----------+

Регистр процесса 1 ¦ ---- ¦¦ ¦ ¦ 4М ¦ ¦

+-¦-----¦¦--+-¦----------+-----------+

Регистр процесса 2 ¦ ¦--- ¦¦ ¦ ¦ ¦ ¦

+-¦¦----¦¦--+-¦----------+-----------+

Регистр процесса 3 ¦ ¦¦-- ¦¦ ¦ ¦ ¦ ¦

L-¦¦¦---¦¦--+-¦----------+------------

--------------------------¦¦ ¦¦ ¦

¦ ----------------¦ ¦L----¦-------¬

¦ ¦ ------ L-----¦-------¦----------¬

¦ ¦ ¦ ---- ¦ ¦

v v v v v v

-------¬ -------¬ -------¬ -------¬ -------¬ -------¬

¦ 856K ¦ ¦ 747K ¦ ¦ 556K ¦ ¦ 0K ¦ ¦ 128K ¦ ¦ 256K ¦

+------+ +------+ +------+ +------+ +------+ +------+

¦ 917K ¦ ¦ 950K ¦ ¦ 997K ¦ ¦ 4K ¦ ¦ 97K ¦ ¦ 292K ¦

+------+ +------+ +------+ +------+ +------+ +------+

¦ 564K ¦ ¦ 333K ¦ ¦ 458K ¦ ¦ 3K ¦ ¦ 135K ¦ ¦ 304K ¦

+------+ +------+ +------+ +------+ +------+ +------+

¦ 444K ¦ ¦ • ¦ ¦ 632K ¦ ¦ 17K ¦ ¦ 139K ¦ ¦ 279K ¦

+------+ ¦ • ¦ +------+ +------+ +------+ +------+

¦ • ¦ ¦ • ¦ ¦ • ¦ ¦ • ¦ ¦ • ¦ ¦ • ¦

¦ • ¦ ¦ • ¦ ¦ • ¦ ¦ • ¦ ¦ • ¦ ¦ • ¦

L------- L------- L------- L------- L------- L-------

Таблицы страниц процесса Таблицы страниц ядра

(области)

Рисунок 6.6. Переключение режима работы с непривилегированного (режима задачи) на привилегированный (режим ядра)

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

страниц альный ниц в табли-

адрес це

------------T------------T-----------¬

Регистр ядра 1 ¦ ¦ ¦ ¦

+-----------+------------+-----------+

Регистр ядра 2 ¦ ¦ ¦ ¦

+-----------+------------+-----------+ (Прост- Регистр ядра 3 ¦ ---¬ ¦ 2M ¦ 4 ¦

процесса) ¦

L---------------------¬

¦

Таблицы страниц для пространства процессов ¦

v

-------¬ -------¬ -------¬ -------¬

¦ 114K ¦ ¦ 843K ¦ ¦1879K ¦ ¦ 184K ¦

+------+ +------+ +------+ +------+

¦ 708K ¦ ¦ 794K ¦ ¦ 290K ¦ ¦ 176K ¦

+------+ +------+ +------+ +------+

¦ 143K ¦ ¦ 361K ¦ ¦ 450K ¦ ¦ 209K ¦

+------+ +------+ +------+ +------+

¦ 565K ¦ ¦ 847K ¦ ¦ 770K ¦ ¦ 477K ¦

L------- L------- L------- L-------

Процесс A Процесс B Процесс C Процесс D

Рисунок 6.7. Карта памяти пространства процесса в ядре

Регистровый контекст состоит из следующих компонент:

Системный контекст включает в себя следующие компоненты:

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

Статическая часть контекста Динамическая часть контекста

--------------------------¬ логичес- ¦ • ¦

¦Пользовательский контекст¦ кий ука- ¦ • ¦

¦ ----------------------¬ ¦ затель на¦ • ¦

¦ ¦ Программы процесса ¦ ¦ текущий ¦ • ¦

¦ ¦ Данные ¦ ¦--------->+----------------+

¦ ¦ Стек ¦ ¦¦ контек- ¦ Стек ядра для ¦

¦ ¦ Разделяемые данные ¦ ¦¦ стный ¦ уровня 3 ¦

¦ L---------------------- ¦¦ уровень ¦ ¦

¦ ¦¦ ¦ Сохраненный ре-¦

¦ Статическая часть ¦¦Уровень 3¦ гистровый кон- ¦

¦ системного контекста ¦¦ ¦ текст уровня 2 ¦

¦ ----------------------¬ ¦¦ +----------------+

¦ ¦ Запись таблицы про- ¦ ¦¦ ¦ Стек ядра для ¦

¦ ¦ цессов +-+- ¦ уровня 2 ¦

¦ ¦ Частная таблица об- ¦ ¦ ¦ Сохраненный ре-¦

¦ ¦ ластей процесса ¦ ¦ Уровень 2¦ гистровый кон- ¦

¦ L---------------------- ¦ ¦ текст уровня 1 ¦

L-------------------------- +----------------+

¦ уровня 1 ¦

¦ ¦

¦ Сохраненный ре-¦

Уровень 1¦ гистровый кон- ¦

¦ текст уровня 0 ¦

+----------------+

Контекстный¦ ¦

уровень¦ (Пользователь- ¦

L-----------------

Рисунок 6.8. Компоненты контекста процесса

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

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

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

------------------------------------------¬

¦ Номер прерывания Программа обработки ¦

¦ прерывания ¦

¦ ¦

¦ 0 clockintr ¦

¦ 1 diskintr ¦

¦ 2 ttyintr ¦

¦ 3 devintr ¦

¦ 4 softintr ¦

¦ 5 otherintr ¦

L------------------------------------------

Рисунок 6.9. Пример векторов прерывания

------------------------------------------------------¬

¦ алгоритм inthand /* обработка прерываний */ ¦

¦ входная информация: отсутствует ¦

¦ { ¦

¦ сохранить (поместить в стек) текущий контекстный ¦

¦ уровень; ¦

¦ установить источник прерывания; ¦

¦ вызвать программу обработки прерывания; ¦

¦ восстановить (извлечь из стека) предыдущий кон- ¦

¦ текстный уровень; ¦

¦ } ¦

L------------------------------------------------------

Рисунок 6.10. Алгоритм обработки прерываний

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

E6.4.2 Взаимодействие с операционной системой через вызовыF

Eсистемных функцийF

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

Последовательность прерываний

--------------------------------¬

¦ Исполнить программу обра- ¦

¦ ботки прерывания по таймеру ¦

¦ ¦

¦ текст программы обработки ¦

¦ прерывания от диска ¦

Прерывание по таймеру ••••••••+-------------------------------+

¦ ¦ Исполнить программу обра- ¦

¦ ¦ ботки прерывания от диска ¦

¦ ¦ ¦

¦ ¦ текст обращения к системной ¦

¦ ¦ функции ¦

Прерывание от диска ••••••••••+-------------------------------+

¦ ¦ Исполнить обращение к сис- ¦

¦ ¦ темной функции ¦

¦ ¦ ¦

¦ ¦ текст пользовательского ¦

¦ ¦ уровня ¦

Вызов системной функции ••••••L--------------------------------

^

¦

¦

Исполнение в режиме задачи

Рисунок 6.11. Примеры прерываний особый случай программы обработки прерывания.

Библиотечные функции передают ядру уникальный номер системной функции одним из машинно-зависимых способов - либо как параметр внутреннего прерывания операционной системы, либо через отдельный регистр, либо через стек - а ядро таким образом определяет тип вызываемой функции.

-------------------------------------------------------------¬

¦ алгоритм syscall /* алгоритм запуска системной функции */¦

¦ входная информация: номер системной функции ¦

¦ выходная информация: результат системной функции ¦

¦ { ¦

¦ найти запись в таблице системных функций, соответствую-¦

¦ щую указанному номеру функции; ¦

¦ определить количество параметров, передаваемых функции;¦

¦ скопировать параметры из адресного пространства задачи ¦

¦ в пространство процесса; ¦

¦ сохранить текущий контекст для аварийного завершения ¦

¦ (см. раздел 6.44); ¦

¦ запустить в ядре исполняемый код системной функции; ¦

¦ если (во время выполнения функции произошла ошибка) ¦

¦ { ¦

¦ установить номер ошибки в нулевом регистре сохра- ¦

¦ включить бит переноса в регистре PS сохраненного ¦

¦ регистрового контекста задачи; ¦

¦ } ¦

¦ занести возвращаемые функцией значения в регистры 0 ¦

¦ и 1 в сохраненном регистровом контексте задачи; ¦

¦ } ¦

L-------------------------------------------------------------

Рисунок 6.12. Алгоритм обращения к системным функциям

-----------------------------------------¬

¦ char name[] = "file"; ¦

¦ main() ¦

¦ { ¦

¦ int fd; ¦

¦ fd = creat(name,0666); ¦

¦ } ¦

Рисунок 6.13. Системная функция creat и сгенерированная прог-

рамма ее выполнения в системе Motorola 68000 равление из программы обработки обращений к операционной системе в режим задачи, библиотечная функция проверяет состояние бита переноса в регистре PS (по адресу 7): если бит установлен, управление передается по адресу 13c, из нулевого регистра выбирается код ошибки и помещается в глобальную переменную errno по адресу 20, в регистр 0 заносится -1, и управление возвращается на следующую после адреса 64 (где производится вызов функции) команду. Код завершения функции имеет значение -1, что указывает на ошибку в выполнении системной функции. Если же бит переноса в регистре PS при переходе из режима ядра в режим задачи имеет нулевое значение, процесс с адреса 7 переходит по адресу 86 и возвращает управление вызвавшей программе (адрес 64); регистр 0 содержит возвращаемое функцией значение.

----------¬ ¦ • ¦

¦ • ¦ ¦ • ¦

¦ • ¦ ¦ • ¦

¦ • ¦ ¦стек ядра для кон-¦

¦ • ¦ ¦текстного уровня 1¦

+---------+ ¦ ¦

¦ 1b6 ¦ код режима доступа ¦последовательность¦

¦ ¦ (666 в восьмиричной системе) ¦команд обращения к¦

¦ 204 ¦ адрес переменной "имя файла" ¦ функции creat ¦

¦ 6a ¦ адрес точки возврата после +------------------+

¦ ¦ вызова библиотечной функции ¦сохраненный регис-¦

+---------+<-----¬ ¦ тровый контекст ¦

¦ внутрен-¦ ¦ ¦ для уровня 0 ¦

¦ нее пре-¦ ¦ ¦(пользовательско- ¦

¦ рывание ¦ значение указателя ¦ го) ¦

¦ в ¦ вершины стека в мо- ¦ ¦

¦ 7c ¦ мент внутреннего пре- ¦ счетчик команд, ¦

направление системы ¦ 7e ¦ увеличения стека ¦ ¦

¦ ¦указатель вершины ¦

v ¦ ¦

¦ регистр PS ¦

¦ ¦

¦ значение 8) ¦

¦ ¦

¦ другие регистры ¦

L-------------------

Рисунок 6.14. Конфигурация стека для системной функции creat

Несколько библиотечных функций могут отображаться на одну точку входа в список системных функций. Каждая точка входа определяет точные синтаксис и семантику обращения к системной функции, однако более удобный интерфейс обеспечивается с помощью библиотек. Существует, например, несколько конструкций системной функции exec, таких как execl и execle, выполняющих одни и те же действия с небольшими отличиями. Библиотечные функции, соответствующие этим конструкциям, при обработке параметров реализуют заявленные свойства, но в конечном итоге, отображаются на одну и ту же функцию ядра.

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

---------------------------------------------------------¬

¦ 1. Принять решение относительно необходимости переклю- ¦

¦ чения контекста и его допустимости в данный момент. ¦

¦ 2. Сохранить контекст "прежнего" процесса. ¦

¦ 3. Выбрать процесс, наиболее подходящий для исполнения,¦

¦ используя алгоритм диспетчеризации процессов, приве-¦

¦ денный в главе 8. ¦

L---------------------------------------------------------

Рисунок 6.15. Последовательность шагов, выполняемых при переключении контекста

Текст программы, реализующей переключение контекста в системе UNIX, из всех программ операционной системы самый трудный для понимания, ибо при рассмотрении обращений к функциям создается впечатление, что они в одних случаях не возвращают управление, а в других - возникают непонятно откуда. Причиной этого является то, что ядро во многих системных реализациях сохраняет контекст процесса в одном месте программы, но продолжает работу, выполняя переключение контекста и алгоритмы диспетчеризации в контексте "прежнего" процесса. Когда позднее ядро восстанавливает контекст процесса, оно возобновляет его выполнение в соответствии с ранее сохраненным контекстом. Чтобы различать между собой те случаи, когда ядро восстанавливает контекст нового процесса, и когда оно продолжает исполнять ранее сохраненный контекст, можно варьировать значения, возвращаемые критическими функциями, или устанавливать искусственным образом текущее значение счетчика команд.

На Рисунке 6.16 приведена схема переключения контекста. Функция save_context сохраняет информацию о контексте исполняемого процесса и возвращает значение 1. Кроме всего прочего, ядро сохраняет текущее значение счетчика команд (в функции save_context) и значение 0 в нулевом регистре при выходе из функции. Ядро продолжает исполнять контекст "прежнего" процесса (A), выбирая для выполнения следующий процесс (B) и вызывая функцию resume_context

-------------------------------------------------------------¬

¦ if (save_context()) /* сохранение контекста выполняющегося¦

¦ процесса */ ¦

¦ { ¦

¦ /* выбор следующего процесса для выполнения */ ¦

¦ • ¦

¦ • ¦

¦ • ¦

¦ resume_context(new_process); ¦

¦ /* сюда программа не попадает ! */ ¦

¦ } ¦

¦ /* возобновление выполнение процесса начинается отсюда */ ¦

L-------------------------------------------------------------

Рисунок 6.16. Псевдопрограмма переключения контекста для восстановления его контекста.

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

---------------------------------------------------------¬

¦ fubyte: # пересылка байта из ¦

¦ # пространства задачи ¦

¦ prober $3,$1,*4(ap) # байт доступен ? ¦

¦ movzbl *4(ap),r0 ¦

¦ ret ¦

¦ eret: ¦

¦ mnegl $1,r0 # возврат ошибки (-1) ¦

¦ ret ¦

L---------------------------------------------------------

Рисунок 6.17. Пересылка данных из пространства задачи в пространство ядра в системе VAX

На Рисунке 6.17 показан пример реализованной в системе VAX программы пересылки символа из адресного пространства задачи в адресное пространство ядра. Команда prober проверяет, может ли байт по адресу, равному (регистр указателя аргумента + 4), быть считан в режиме задачи (режиме 3), и если нет, ядро передает управление по адресу eret, сохраняет в нулевом регистре -1 и выходит из программы; при этом пересылки символа не происходит. В противном случае ядро пересылает один байт, находящийся по указанному адресу, в регистр 0 и возвращает его в вызывающую программу. Пересылка 1 символа потребовала пяти команд (включая вызов функции с именем fubyte).

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

Запись таблицы областей содержит информацию, необходимую для описания области. В частности, она включает в себя следующие поля:

• Указатель на индекс файла, содержимое которого было первоначально загружено в область
• Тип области (область команд, разделяемая память, область частных данных или стека)
• Размер области
• Местоположение области в физической памяти
• Статус (состояние) области, представляющий собой комбинацию из следующих признаков:

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

• Счетчик ссылок, в котором хранится количество процессов, ссылающихся на данную область.

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

Операции блокировки и снятия блокировки для области выполняются независимо от операций выделения и освобождения области, подобно тому, как операции блокирования-разблокирования индекса в файловой системе выполняются независимо от операций назначения-освобождения индекса (алгоритмы iget и iput). Таким образом, ядро может заблокировать и выделить область, а потом снять блокировку, не освобождая области. Точно также, когда ядру понадобится обратиться к выделенной области, оно сможет заблокировать область, чтобы запретить доступ к ней со стороны других процессов, и позднее снять блокировку.

-------------------------------------------------------------¬

¦ алгоритм allocreg /* разместить информационную структуру ¦

¦ входная информация: (1) указатель индекса ¦

¦ (2) тип области ¦

¦ выходная информация: заблокированная область ¦

¦ { ¦

¦ выбрать область из списка свободных областей; ¦

¦ назначить области тип; ¦

¦ присвоить значение указателю индекса; ¦

¦ если (указатель индекса имеет ненулевое значение) ¦

¦ увеличить значение счетчика ссылок на индекс; ¦

¦ включить область в список активных областей; ¦

¦ возвратить (заблокированную область); ¦

¦ } ¦

L-------------------------------------------------------------

Рисунок 6.18. Алгоритм выделения области

Ядро присоединяет область к адресному пространству процесса во время выполнения системных функций fork, exec и shmat (алгоритм attachreg, Рисунок 6.19). Область может быть вновь назначаемой или уже существующей, которую процесс будет использовать совместно с другими процессами. Ядро выбирает свободную запись в частной таблице областей процесса, устанавливает в ней поле типа таким образом, чтобы оно указывало на область команд, данных, разделяемую память или область стека, и записывает виртуальный адрес, по которому область будет размещаться в адресном пространстве процесса. Процесс не должен выходить за предел установленного системой ограничения на максимальный виртуальный адрес, а виртуальные адреса новой области не должны пересекаться с адресами существующих уже областей. Например, если система ограничила максимально-допустимое значение виртуального адреса процесса 8 мегабайтами, то привязать область размером 1 мегабайт к виртуальному адресу 7.5M не удастся. Если же присоединение области допустимо, ядро увеличивает значение поля, описывающего размер области процесса в записи таблицы процессов, на величину присоединяемой области, а также увеличивает значение счетчика ссылок на область.

-------------------------------------------------------------¬

¦ алгоритм attachreg /* присоединение области к процессу */ ¦

¦ входная информация: (1) указатель на присоединяемую об- ¦

¦ (2) процесс, к которому присоединяется¦

¦ область ¦

¦ (3) виртуальный адрес внутри процесса,¦

¦ по которому будет присоединена об-¦

¦ ласть ¦

¦ (4) тип области ¦

¦ выходная информация: точка входа в частную таблицу областей¦

¦ { ¦

¦ выделить новую запись в частной таблице областей про- ¦

¦ цесса; ¦

¦ проинициализировать значения полей записи: ¦

¦ установить указатель на присоединяемую область; ¦

¦ установить тип области; ¦

¦ установить виртуальный адрес области; ¦

¦ проверить правильность указания виртуального адреса и ¦

¦ размера области; ¦

¦ увеличить значение счетчика ссылок на область; ¦

¦ увеличить размер процесса с учетом присоединения облас-¦

¦ записать начальные значения в новую группу аппаратных ¦

¦ регистров; ¦

¦ возвратить (точку входа в частную таблицу областей про-¦

¦ } ¦

L-------------------------------------------------------------

Рисунок 6.19. Алгоритм присоединения области

группу регистров управления памятью и заносит в них адрес таблицы страниц области, виртуальный адрес области в пространстве процесса (0) и размер таблицы страниц (9 записей).

Частная таблица областей процесса

----------T-------------T--------¬

¦ таблицы ¦ адрес в про-¦ и ¦

¦ страниц ¦ странстве ¦ защита ¦

¦ ¦ процесса ¦ ¦

+---------+-------------+--------+

для области L----+----+-------------+---------

команд L----¬

v

--------------¬

¦ пусто ¦

+-------------+

+-------------+

¦ 846K ¦

+-------------+

¦ 752K ¦

+-------------+

¦ 341K ¦

+-------------+

¦ 484K ¦

+-------------+

¦ 976K ¦

+-------------+

¦ 342K ¦

+-------------+

¦ 779K ¦

L--------------

Рисунок 6.20. Пример присоединения существующей области команд

ции не могут расширяться. Этот момент будет пояснен в следующей главе.

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

Предположим, например, что область стека процесса начинается с виртуального адреса 128К и имеет размер 6 Кбайт и что ядру нужно расширить эту область на 1 Кбайт (1 страницу). Если размер процесса позволяет это делать и если виртуальные адреса в диапазоне от 134К до 135К - 1 не принадлежат какой-либо области, ранее присоединенной к процессу, ядро увеличивает размер стека. При этом ядро расширяет таблицу страниц, выделяет новую страницу памяти и инициализирует новую запись таблицы. Этот случай проиллюстрирован с помощью Рисунка 6.22.

В системе, где поддерживается подкачка страниц по обращению, ядро может

-------------------------------------------------------------¬

¦ алгоритм growreg /* изменение размера области */ ¦

¦ входная информация: (1) указатель на точку входа в частной¦

¦ (2) величина, на которую нужно изме- ¦

¦ нить размер области (может быть ¦

¦ как положительной, так и отрица- ¦

¦ выходная информация: отсутствует ¦

¦ { ¦

¦ если (размер области увеличивается) ¦

¦ { ¦

¦ проверить допустимость нового размера области; ¦

¦ выделить вспомогательные таблицы (страниц); ¦

¦ если (в системе не поддерживается замещение страниц ¦

¦ по обращению) ¦

¦ { ¦

¦ выделить дополнительную память; ¦

¦ проинициализировать при необходимости значения ¦

¦ полей в дополнительных таблицах; ¦

¦ } ¦

¦ } ¦

¦ в противном случае /* размер области уменьшается */ ¦

¦ { ¦

¦ освободить физическую память; ¦

¦ освободить вспомогательные таблицы; ¦

¦ } ¦

¦ ¦

¦ провести в случае необходимости инициализацию других ¦

¦ вспомогательных таблиц; ¦

¦ переустановить значение поля размера в таблице процес- ¦

¦ сов; ¦

¦ } ¦

L-------------------------------------------------------------

Рисунок 6.21. Алгоритм изменения размера области

При загрузке файла в область алгоритм loadreg (Рисунок 6.23) проверяет разрыв между виртуальным адресом, по которому область присоединяется к процессу, и виртуальным адресом, с которого располагаются данные области, и расширяет область в соответствии с требуемым объемом памяти. Затем область

Частная таблица областей Частная таблица областей

процесса процесса

--------T----------T------¬ --------T----------T------¬

¦ Адрес ¦ Виртуаль-¦ Раз- ¦ ¦ Адрес ¦ Виртуаль-¦ Раз- ¦

¦ табли-¦ ный адрес¦ мер ¦ ¦ табли-¦ ный адрес¦ мер ¦

¦ цы ¦ в прост- ¦ и ¦ ¦ цы ¦ в прост- ¦ и ¦

¦ стра- ¦ ранстве ¦ защи-¦ ¦ стра- ¦ ранстве ¦ защи-¦

¦ ниц ¦ процесса ¦ та ¦ ¦ ниц ¦ процесса ¦ та ¦

+-------+----------+------+ +-------+----------+------+

¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦

+-------+----------+------+ +-------+----------+------+

для L---+---+----------+------- для L---+---+----------+------стека L--¬ стека L--¬

v v

--------------¬ --------------¬

¦ 342K ¦ ¦ 342K ¦

+-------------+ +-------------+

¦ 779K ¦ ¦ 779K ¦

+-------------+ +-------------+

¦ 846K ¦ ¦ 846K ¦

+-------------+ +-------------+

¦ 752K ¦ ¦ 752K ¦

+-------------+ +-------------+

¦ 341K ¦ ¦ 341K ¦

+-------------+ +-------------+

¦ 484K ¦ ¦ 484K ¦

+-------------+ НОВАЯ +-------------+

¦ ¦ СТРАНИЦА-->¦ 976K ¦

+-------------+ +-------------+

¦ ¦ ¦ ¦

+-------------+ +-------------+

¦ ¦ ¦ ¦

L-------------- L--------------

До увеличения стека После увеличения стека

Рисунок 6.22. Увеличение области стека на 1 Кбайт

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

Если ядро загружает область команд, которая может разделяться несколькими процессами, возможна ситуация, когда процесс попытается воспользоваться областью до того, как ее содержимое будет полностью загружено, так как процесс загрузки может приостановиться во время чтения файла. Подробно о том, как это происходит и почему при этом нельзя использовать блокировки, мы поговорим, когда будем вести речь о функции exec в следующей главе и в главе 9. Чтобы устранить эту проблему, ядро проверяет статус области и не разрешает к ней доступ до тех пор, пока загрузка области не будет закончена. По завершении реализации алгоритма loadreg ядро возобновляет выполнение всех процессов, ожидающих окончания загрузки области, и изменяет статус области ("готова, загружена в память").

Предположим, например, что ядру нужно загрузить текст размером 7K в область, присоединенную к процессу по виртуальному адресу 0, но при этом оставить промежуток размером 1 Кбайт от начала области (Рисунок 6.24). К этому

-------------------------------------------------------------¬

¦ алгоритм loadreg /* загрузка части файла в область */ ¦

¦ входная информация: (1) указатель на точку входа в частную¦

¦ таблицу областей процесса ¦

¦ (2) виртуальный адрес загрузки ¦

¦ (4) смещение в байтах до начала считы-¦

¦ ваемой части файла ¦

¦ (5) объем загружаемых данных в байтах ¦

¦ выходная информация: отсутствует ¦

¦ { ¦

¦ увеличить размер области до требуемой величины (алгоритм¦

¦ growreg); ¦

¦ записать статус области как "загружаемой в память"; ¦

¦ снять блокировку с области; ¦

¦ установить в пространстве процесса значения параметров ¦

¦ чтения из файла: ¦

¦ виртуальный адрес, по которому будут размещены счи-¦

¦ тываемые данные; ¦

¦ смещение до начала считываемой части файла; ¦

¦ объем данных, считываемых из файла, в байтах; ¦

¦ загрузить файл в область (встроенная модификация алго- ¦

¦ ритма read); ¦

¦ заблокировать область; ¦

¦ записать статус области как "полностью загруженной в па-¦

¦ возобновить выполнение всех процессов, ожидающих оконча-¦

¦ ния загрузки области; ¦

¦ } ¦

L-------------------------------------------------------------

Рисунок 6.23. Алгоритм загрузки данных области из файла

времени ядро уже выделило запись в таблице областей и присоединило область по адресу 0 с помощью алгоритмов allocreg и attachreg. Теперь же ядро запускает алгоритм loadreg, в котором действия алгоритма growreg выполняются дважды - во-первых, при выделении в начале области промежутка в 1 Кбайт, и во-вторых, при выделении места для содержимого области - и алгоритм growreg назначает для области таблицу страниц. Затем ядро заносит в соответствующие поля пространства процесса установочные значения для чтения данных из файла: считываются 7 Кбайт, начиная с адреса, указанного в виде смещения внутри файла (параметр алгоритма), и записываются в виртуальное пространство процесса по адресу 1K.

Частная таблица областей Частная таблица областей

процесса процесса

--------T----------T------¬ --------T----------T------¬

¦ табли-¦ ный адрес¦ мер ¦ ¦ табли-¦ ный адрес¦ мер ¦

¦ цы ¦ в прост- ¦ и ¦ ¦ цы ¦ в прост- ¦ и ¦

¦ стра- ¦ ранстве ¦ защи-¦ ¦ стра- ¦ ранстве ¦ защи-¦

¦ ниц ¦ процесса ¦ та ¦ ¦ ниц ¦ процесса ¦ та ¦

L-------+----------+------- L---+---+----------+-------

(а) Запись таблицы в перво- L--¬

v

--------------¬

¦ пусто ¦

Частная таблица областей +-------------+

--------T----------T------¬ +-------------+

¦ Адрес ¦ Виртуаль-¦ Раз- ¦ ¦ 846K ¦

¦ табли-¦ ный адрес¦ мер ¦ +-------------+

¦ цы ¦ в прост- ¦ и ¦ ¦ 752K ¦

¦ стра- ¦ ранстве ¦ защи-¦ +-------------+

¦ ниц ¦ процесса ¦ та ¦ ¦ 341K ¦

+-------+----------+------+ +-------------+

¦ ¦ 0 ¦ 1 ¦ ¦ 484K ¦

L---+---+----------+------- +-------------+

L--¬ ¦ 976K ¦

¦ +-------------+

v ¦ 794K ¦

--------------¬ +-------------+

L-------------- L--------------

(б) Запись, указывающая на (в) После второго выполне-

промежуток в начале об- ния алгоритма growreg

ласти (после первого

growreg)

Рисунок 6.24. Загрузка области команд (текста)

-------------------------------------------------------------¬

¦ алгоритм freereg /* освобождение выделенной области */¦

¦ входная информация: указатель на (заблокированную) область¦

¦ выходная информация: отсутствует ¦

¦ { ¦

¦ если (счетчик ссылок на область имеет ненулевое значе- ¦

¦ { ¦

¦ /* область все еще используется одним из процессов */¦

¦ снять блокировку с области; ¦

¦ снять блокировку с индекса; ¦

¦ возвратить управление; ¦

¦ } ¦

¦ освободить индекс (алгоритм iput); ¦

¦ освободить связанную с областью физическую память; ¦

¦ освободить связанные с областью вспомогательные таблицы;¦

¦ очистить поля области; ¦

¦ включить область в список свободных областей; ¦

¦ снять блокировку с области; ¦

¦ } ¦

L-------------------------------------------------------------

Рисунок 6.25. Алгоритм освобождения области

-------------------------------------------------------------¬

¦ алгоритм detachreg /* отсоединить область от процесса */ ¦

¦ входная информация: указатель на точку входа в частной ¦

¦ таблице областей процесса ¦

¦ выходная информация: отсутствует ¦

¦ { ¦

¦ обратиться к вспомогательным таблицам процесса, имеющим ¦

¦ отношение к распределению памяти, ¦

¦ освободить те из них, которые связаны с областью; ¦

¦ уменьшить размер процесса; ¦

¦ уменьшить значение счетчика ссылок на область; ¦

¦ если (значение счетчика стало нулевым и область не явля-¦

¦ освободить область (алгоритм freereg); ¦

¦ в противном случае /* либо значение счетчика отлично ¦

¦ от 0, либо область является не- ¦

¦ отъемлемой частью процесса */ ¦

¦ { ¦

¦ снять блокировку с индекса (ассоциированного с об- ¦

¦ ластью); ¦

¦ } ¦

¦ } ¦

L-------------------------------------------------------------

Рисунок 6.26. Алгоритм отсоединения области

6.5.7 Отсоединение области от процесса

Частные таблицы областей процессов Области

---------------¬ --------------¬

Команды ¦ +-------------->¦ Разделяемая ¦

+--------------+ -------->L--------------

Данные ¦ +----¬ ¦

+--------------+ ¦ ¦ --------------¬

Стек ¦ +--¬ L-¦------->¦ Частная +-¬

Процесс A ¦ ¦ ¦ рова-

¦ ¦ --------------¬ ¦ ние

L---¦------->¦ Частная +-¦-¬ дан-

Команды ¦ +------- ¦ ¦

+--------------+ --------------¬ ¦ ¦

Данные ¦ +-------------->¦ Частная ¦<- ¦

+--------------+ L-------------- ¦

Стек ¦ +------¬ ¦

L--------------- ¦ --------------¬ ¦

Процесс B L------->¦ Частная ¦<---

L--------------

Рисунок 6.27. Копирование содержимого области

-------------------------------------------------------------¬

¦ алгоритм dupreg /* копирование содержимого существующей ¦

¦ области */ ¦

¦ входная информация: указатель на точку входа в таблице об-¦

¦ ластей ¦

¦ выходная информация: указатель на область, являющуюся точ- ¦

¦ ной копией существующей области ¦

¦ { ¦

¦ если (область разделяемая) ¦

¦ /* в вызывающей программе счетчик ссылок на об- ¦

¦ ласть будет увеличен, после чего будет испол- ¦

¦ возвратить (указатель на исходную область); ¦

¦ выделить новую область (алгоритм allocreg); ¦

¦ установить значения вспомогательных структур управления¦

¦ памятью в точном соответствии со значениями существую-¦

¦ щих структур исходной области; ¦

¦ выделить для содержимого области физическую память; ¦

¦ "скопировать" содержимое исходной области во вновь соз-¦

¦ возвратить (указатель на выделенную область); ¦

¦ } ¦

L-------------------------------------------------------------

Рисунок 6.28. Алгоритм копирования содержимого существующей области

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

--------------------------------¬

¦ Контекстный уровень ядра 2 ¦

¦ Исполнить программу пере- ¦

¦ ключения контекста ¦

¦ ¦

¦ Сохранить регистровый кон- ¦

¦ текст обращения к системной ¦

¦ функции ¦

Запуск алгоритма приостанова •+-------------------------------+

^ ¦ Контекстный уровень ядра 1 ¦

¦ ¦ Исполнить обращение к сис- ¦

¦ ¦ темной функции ¦

¦ ¦ ¦

¦ ¦ текст пользовательского ¦

¦ ¦ уровня ¦

Вызов системной функции ••••••L--------------------------------

^

¦

¦

Исполнение в режиме задачи

Рисунок 6.29. Стандартные контекстные уровни приостановленного процесса

Выполнение процесса приостанавливается обычно во время исполнения запрошенной им системной функции: процесс переходит в режим ядра (контекстный уровень 1), исполняя внутреннее прерывание операционной системы, и приостанавливается в ожидании ресурсов. При этом процесс переключает контекст, запоминая в стеке свой текущий контекстный уровень и исполняясь далее в рамках системного контекстного уровня 2 (Рисунок 6.29). Выполнение процессов приостанавливается также и в том случае, когда оно наталкивается на отсутствие страницы в результате обращения к виртуальным адресам, не загруженным физически; процессы не будут выполняться, пока ядро не считает содержимое страниц.

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

процесс a ---¬ ---- ожидание завершения ---¬

¦ ¦ ввода-вывода ¦

процесс b -¬-¦----- ¦

¦¦¦ +---- адрес A

процесс c -¦-L-------- ожидание выделения ¦

L----¬---- (освобождения) буфера ---

процесс d --¬ ¦¦----¦

¦ ¦¦¦----

процесс e --¦---¦-¦¦

¦---¦--¦

процесс f --¦- L--¦-- ожидание выделения --------- адрес B

процесс g --¦-- ¦

-¦-------

процесс h --L--------- ожидание ввода с тер- ------ адрес C

минала

Рисунок 6.30. Процессы, приостановленные до наступления событий, и отображение событий на конкретные адреса

се отображения ожидаемого события на конкретный адрес. Как для абстрактного рассмотрения, так и для конкретной реализации события безразлично, сколько процессов одновременно ожидают его наступления. Как результат, возможно возникновение некоторых противоречий. Во-первых, когда событие наступает и процессы, ожидающие его, соответствующим образом оповещаются об этом, все они "пробуждаются" и переходят в состояние "готовности к выполнению". Ядро выводит процессы из состояния приостанова все сразу, а не по одному, несмотря на то, что они в принципе могут конкурировать за одну и ту же заблокированную структуру данных и большинство из них через небольшой промежуток времени опять вернется в состояние приостанова (более подробно об этом шла речь в главах 2 и 3). На Рисунке 6.30 изображены несколько процессов, приостановленных до наступления определенных событий.

Еще одно противоречие связано с тем, что на один и тот же адрес могут отображаться несколько событий. На Рисунке 6.30, например, события "освобождение буфера" и "завершение ввода-вывода" отображаются на адрес буфера ("адрес A"). Когда ввод-вывод в буфер завершается, ядро возобновляет выполнение всех процессов, приостановленных в ожидании наступления как того, так и другого события. Поскольку процесс, ожидающий завершения ввода-вывода, удерживает буфер заблокированным, другие процессы, которые ждали освобождения буфера, вновь приостановятся, ибо буфер все еще занят. Функционирование системы было бы более эффективным, если бы отображение событий на адреса было однозначным. Однако на практике такого рода противоречие на производительности системы не отражается, поскольку отображение на один адрес более одного события имеет место довольно редко, а также поскольку выполняющийся процесс обычно освобождает заблокированные ресурсы до того, как начнут выполняться другие процессы. Стилистически, тем не менее, механизм функционирования ядра стал бы более понятен, если бы отображение было однозначным.

-------------------------------------------------------------¬

¦ алгоритм sleep ¦

¦ входная информация: (1) адрес приостанова ¦

¦ (2) приоритет ¦

¦ выходная информация: 1, если процесс возобновляется по сиг-¦

¦ налу, который ему удалось уловить; ¦

¦ вызов алгоритма longjump, если процесс¦

¦ возобновляется по сигналу, который ему¦

¦ 0 - во всех остальных случаях; ¦

¦ { ¦

¦ поднять приоритет работы процессора таким образом, чтобы¦

¦ заблокировать все прерывания; ¦

¦ перевести процесс в состояние приостанова; ¦

¦ включить процесс в хеш-очередь приостановленных процес- ¦

¦ сов, базирующуюся на адресах приостанова; ¦

¦ сохранить адрес приостанова в таблице процессов; ¦

¦ сделать ввод для процесса приоритетным; ¦

¦ если (приостанов процесса НЕ допускает прерываний) ¦

¦ { ¦

¦ выполнить переключение контекста; ¦

¦ /* с этого места процесс возобновляет выполнение, ¦

¦ когда "пробуждается" */ ¦

¦ снизить приоритет работы процессора так, чтобы вновь ¦

¦ разрешить прерывания (как было до приостанова про- ¦

¦ цесса); ¦

¦ возвратить (0); ¦

¦ } ¦

¦ ¦

¦ /* приостанов процесса принимает прерывания, вызванные ¦

¦ сигналами */ ¦

¦ если (к процессу не имеет отношения ни один из сигналов)¦

¦ { ¦

¦ выполнить переключение контекста; ¦

¦ /* с этого места процесс возобновляет выполнение, ¦

¦ когда "пробуждается" */ ¦

¦ если (к процессу не имеет отношения ни один из сигна-¦

¦ лов) ¦

¦ { ¦

¦ восстановить приоритет работы процессора таким, ¦

¦ каким он был в момент приостанова процесса; ¦

¦ возвратить (0); ¦

¦ } ¦

¦ } ¦

¦ удалить процесс из хеш-очереди приостановленных процес- ¦

¦ сов, если он все еще находится там; ¦

¦ ¦

¦ восстановить приоритет работы процессора таким, каким он¦

¦ если (приоритет приостановленного процесса позволяет ¦

¦ принимать сигналы) ¦

¦ возвратить (1); ¦

¦ запустить алгоритм longjump; ¦

¦ } ¦

L-------------------------------------------------------------

Рисунок 6.31. Алгоритм приостанова процесса

На Рисунке 6.31 приведен алгоритм приостанова процесса. Сначала ядро повышает приоритет работы процессора так, чтобы заблокировать все прерывания, которые могли бы (путем создания конкуренции) помешать работе с очередями приостановленных процессов, и запоминает старый приоритет, чтобы восстановить его, когда выполнение процесса будет возобновлено. Процесс получает пометку "приостановленного", адрес приостанова и приоритет запоминаются в таблице процессов, а процесс помещается в хеш-очередь приостановленных процессов. В простейшем случае (когда приостанов не допускает прерываний) процесс выполняет переключение контекста и благополучно "засыпает". Когда приостановленный процесс "пробуждается", ядро начинает планировать его запуск: процесс возвращает сохраненный в алгоритме sleep контекст, восстанавливает старый приоритет работы процессора (который был у него до начала выполнения алгоритма) и возвращает управление ядру.

-------------------------------------------------------------¬

¦ алгоритм wakeup /* возобновление приостановленного про- ¦

¦ цесса */ ¦

¦ входная информация: адрес приостанова ¦

¦ выходная информация: отсутствует ¦

¦ { ¦

¦ повысить приоритет работы процессора таким образом, что-¦

¦ бы заблокировать все прерывания; ¦

¦ найти хеш-очередь приостановленных процессов с указанным¦

¦ для (каждого процесса, приостановленного по указанному ¦

¦ адресу) ¦

¦ { ¦

¦ удалить процесс из хеш-очереди; ¦

¦ янии "готовности к запуску"; ¦

¦ включить процесс в список процессов, готовых к запус-¦

¦ ку (для планировщика процессов); ¦

¦ таблицы процессов; ¦

¦ если (процесс не загружен в память) ¦

¦ возобновить выполнение программы подкачки (нуле-¦

¦ в противном случае ¦

¦ если (возобновляемый процесс более подходит для ис- ¦

¦ полнения, чем ныне выполняющийся) ¦

¦ установить соответствующий флаг для планировщи- ¦

¦ ка; ¦

¦ } ¦

¦ восстановить первоначальный приоритет работы процессора;¦

¦ } ¦

L-------------------------------------------------------------

Рисунок 6.32. Алгоритм возобновления приостановленного процесса

Чтобы возобновить выполнение приостановленных процессов, ядро обращается к алгоритму wakeup (Рисунок 6.32), причем делает это как во время исполнения алгоритмов реализации стандартных системных функций, так и в случае обработки прерываний. Алгоритм iput, например, освобождает заблокированный индекс и возобновляет выполнение всех процессов, ожидающих снятия блокировки. Точно так же и программа обработки прерываний от диска возобновляет выполнение процессов, ожидающих завершения ввода-вывода. В алгоритме wakeup ядро сначала повышает приоритет работы процессора, чтобы заблокировать прерывания. Затем для каждого процесса, приостановленного по указанному адресу, выполняются следующие действия: делается пометка в поле, описывающем состояние процесса, о том, что процесс готов к запуску; процесс удаляется из списка приостановленных процессов и помещается в список процессов, готовых к запуску; поле в записи таблицы процессов, содержащее адрес приостанова, очищается. Если возобновляемый процесс не загружен в память, ядро запускает процесс подкачки, обеспечивающий подкачку возобновляемого процесса в память (подразумевается система, в которой подкачка страниц по обращению не поддерживается); в противном случае, если возобновляемый процесс более подходит для исполнения, чем ныне выполняющийся, ядро устанавливает для планировщика специальный флаг, сообщающий о том, что процессу по возвращении в режим задачи следует пройти через алгоритм планирования (глава 8). Наконец, ядро восстанавливает первоначальный приоритет работы процессора. При этом на ядро не оказывается никакого давления: "пробуждение" (wakeup) процесса не вызывает его немедленного исполнения; благодаря "пробуждению", процесс становится только доступным для запуска.

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

Чтобы как-то различать между собой состояния приостанова, ядро устанавливает для приостанавливаемого процесса (при входе в это состояние) приоритет планирования на основании соответствующего параметра алгоритма sleep. То есть ядро запускает алгоритм sleep с параметром "приоритет", в котором отражается наличие уверенности в неизбежном наступлении ожидаемого события. Если приоритет превышает пороговое значение, процесс не будет преждевременно выходить из приостанова по получении сигнала, а будет продолжать ожидать наступления события. Если же значение приоритета ниже порогового, процесс будет немедленно возобновлен по получении сигнала

Проверка того, имеет ли процесс уже сигнал при входе в алгоритм sleep, позволяет выяснить, приостанавливался ли процесс ранее. Например, если значение приоритета в вызове алгоритма sleep превышает пороговое значение, процесс приостанавливается в ожидании выполнения алгоритма wakeup. Если же значение приоритета ниже порогового, выполнение процесса не приостанавливается, но на сигнал процесс реагирует точно так же, как если бы он был приостановлен. Если ядро не проверит наличие сигналов перед приостановом, возможна опасность, что сигнал больше не поступит вновь и в этом случае процесс никогда не возобновится.