Страница:
ти. Если значение счетчика становится равным 0 и если нет причины оставлять
область без изменений (область не является областью разделяемой памяти или
областью команд с признаками неотъемлемой части процесса, о чем будет идти
речь в разделе 7.5), ядро освобождает область по алгоритму freereg. В про-
тивном случае ядро снимает с индекса и с области блокировку, установленную
для того, чтобы предотвратить конкуренцию между параллельно выполняющимися
процессами (см. раздел 7.5), но оставляет область и ее ресурсы без измене-
ний.
168
Частные таблицы областей процессов Области
+--------------+ +-------------+
Команды | +-------------->| Разделяемая |
+--------------+ +------->+-------------+
Данные | +----+ |
+--------------+ | | +-------------+
Стек | +--+ +-|------->| Частная +-+
+--------------+ | | +-------------+ | Копи-
Процесс A | | | рова-
| | +-------------+ | ние
+---|------->| Частная +-|-+ дан-
+--------------+ | +-------------+ | | ных
Команды | +------+ | |
+--------------+ +-------------+ | |
Данные | +-------------->| Частная |<+ |
+--------------+ +-------------+ |
Стек | +------+ |
+--------------+ | +-------------+ |
Процесс B +------->| Частная |<--+
+-------------+
Рисунок 6.27. Копирование содержимого области
+------------------------------------------------------------+
| алгоритм dupreg /* копирование содержимого существующей |
| области */ |
| входная информация: указатель на точку входа в таблице об-|
| ластей |
| выходная информация: указатель на область, являющуюся точ- |
| ной копией существующей области |
| { |
| если (область разделяемая) |
| /* в вызывающей программе счетчик ссылок на об- |
| ласть будет увеличен, после чего будет испол- |
| нен алгоритм attachreg */ |
| возвратить (указатель на исходную область); |
| выделить новую область (алгоритм allocreg); |
| установить значения вспомогательных структур управления|
| памятью в точном соответствии со значениями существую-|
| щих структур исходной области; |
| выделить для содержимого области физическую память; |
| "скопировать" содержимое исходной области во вновь соз-|
| данную область; |
| возвратить (указатель на выделенную область); |
| } |
+------------------------------------------------------------+
Рисунок 6.28. Алгоритм копирования содержимого существующей области
Системная функция fork требует, чтобы ядро скопировало содержимое облас-
тей процесса. Если же область разделяемая (разделяемый текст команд или раз-
деляемая память), ядру нет надобности копировать область физически; вместо
этого оно увеличивает значение счетчика ссылок на область, позволяя роди-
тельскому и порожденному процессам использовать область совместно. Если об-
ласть не является разделяемой и ядру нужно физически копировать ее содержи-
мое, оно выделяет новую запись в таблице областей, новую таблицу страниц и
169
отводит под создаваемую область физическую память. В качестве примера расс-
мотрим Рисунок 6.27, где процесс A порождает с помощью функции fork процесс
B и копирует области родительского процесса. Область команд процесса A явля-
ется разделяемой, поэтому процесс B может использовать эту область совместно
с процессом A. Однако области данных и стека родительского процесса являются
его личной принадлежностью (имеют частный тип), поэтому процессу B нужно
скопировать их содержимое во вновь выделенные области. При этом даже для об-
ластей частного типа физическое копирование области не всегда необходимо, в
чем мы убедимся позже (глава 9). На Рисунке 6.28 приведен алгоритм копирова-
ния содержимого области (dupreg).
К настоящему моменту мы рассмотрели все функции работы с внутренними
структурами процесса, выполняющиеся на нижнем уровне взаимодействия с про-
цессом и обеспечивающие переход в состояние "выполнения в режиме ядра" и вы-
ход из этого состояния в другие состояния, за исключением функций, переводя-
щих процесс в состояние "приостанова выполнения". Теперь перейдем к рассмот-
рению алгоритмов, с помощью которых процесс переводится из состояния "выпол-
нения в режиме ядра" в состояние "приостанова в памяти" и из состояния при-
останова в состояния "готовности к запуску" с выгрузкой и без выгрузки из
памяти.
+-------------------------------+
| Контекстный уровень ядра 2 |
| Исполнить программу пере- |
| ключения контекста |
| |
| Сохранить регистровый кон- |
| текст обращения к системной |
| функции |
Запуск алгоритма приостанова -+-------------------------------+
^ | Контекстный уровень ядра 1 |
| | Исполнить обращение к сис- |
| | темной функции |
| | |
| | Сохранить регистровый кон- |
| | текст пользовательского |
| | уровня |
Вызов системной функции ------+-------------------------------+
^
|
|
Исполнение в режиме задачи
Рисунок 6.29. Стандартные контекстные уровни приостановленно-
го процесса
Выполнение процесса приостанавливается обычно во время исполнения запро-
шенной им системной функции: процесс переходит в режим ядра (контекстный
уровень 1), исполняя внутреннее прерывание операционной системы, и приоста-
навливается в ожидании ресурсов. При этом процесс переключает контекст, за-
поминая в стеке свой текущий контекстный уровень и исполняясь далее в рамках
системного контекстного уровня 2 (Рисунок 6.29). Выполнение процессов приос-
танавливается также и в том случае, когда оно наталкивается на отсутствие
страницы в результате обращения к виртуальным адресам, не загруженным физи-
чески; процессы не будут выполняться, пока ядро не считает содержимое стра-
170
ниц.
Как уже говорилось во второй главе, процессы приостанавливаются до нас-
тупления определенного события, после которого они "пробуждаются" и перехо-
дят в состояние "готовности к выполнению" (с выгрузкой и без выгрузки из па-
мяти). Такого рода абстрактное рассуждение недалеко от истины, ибо в конк-
ретном воплощении совокупность событий отображается на совокупность вирту-
альных адресов (ядра). Адреса, с которыми связаны события, закодированы в
ядре, и их единственное назначение состоит в их использовании в процес-
процесс a ---+ +--- ожидание завершения ---+
| | ввода-вывода |
процесс b -++|----+ |
||| +---- адрес A
процесс c -|++-------- ожидание выделения |
+----++--- (освобождения) буфера --+
процесс d --+ ||+--+|
| |||+--+
процесс e --|---|+||
|+--|-+|
процесс f --|+ +--|-- ожидание выделения --------- адрес B
| +----|-(освобождения) индекса
процесс g --|-+ |
+|------+
процесс h -++--------- ожидание ввода с тер- ------ адрес C
минала
Рисунок 6.30. Процессы, приостановленные до наступления собы-
тий, и отображение событий на конкретные адреса
се отображения ожидаемого события на конкретный адрес. Как для абстрактного
рассмотрения, так и для конкретной реализации события безразлично, сколько
процессов одновременно ожидают его наступления. Как результат, возможно воз-
никновение некоторых противоречий. Во-первых, когда событие наступает и про-
цессы, ожидающие его, соответствующим образом оповещаются об этом, все они
"пробуждаются" и переходят в состояние "готовности к выполнению". Ядро выво-
дит процессы из состояния приостанова все сразу, а не по одному, несмотря на
то, что они в принципе могут конкурировать за одну и ту же заблокированную
структуру данных и большинство из них через небольшой промежуток времени
опять вернется в состояние приостанова (более подробно об этом шла речь в
главах 2 и 3). На Рисунке 6.30 изображены несколько процессов, приостанов-
ленных до наступления определенных событий.
Еще одно противоречие связано с тем, что на один и тот же адрес могут
отображаться несколько событий. На Рисунке 6.30, например, события "освобож-
дение буфера" и "завершение ввода-вывода" отображаются на адрес буфера ("ад-
рес A"). Когда ввод-вывод в буфер завершается, ядро возобновляет выполнение
всех процессов, приостановленных в ожидании наступления как того, так и дру-
гого события. Поскольку процесс, ожидающий завершения ввода-вывода, удержи-
вает буфер заблокированным, другие процессы, которые ждали освобождения бу-
фера, вновь приостановятся, ибо буфер все еще занят. Функционирование систе-
мы было бы более эффективным, если бы отображение событий на адреса было од-
нозначным. Однако на практике такого рода противоречие на производительности
системы не отражается, поскольку отображение на один адрес более одного со-
бытия имеет место довольно редко, а также поскольку выполняющийся процесс
обычно освобождает заблокированные ресурсы до того, как начнут выполняться
171
другие процессы. Стилистически, тем не менее, механизм функционирования ядра
стал бы более понятен, если бы отображение было однозначным.
+------------------------------------------------------------+
| алгоритм sleep |
| входная информация: (1) адрес приостанова |
| (2) приоритет |
| выходная информация: 1, если процесс возобновляется по сиг-|
| налу, который ему удалось уловить; |
| вызов алгоритма longjump, если процесс|
| возобновляется по сигналу, который ему|
| не удалось уловить; |
| 0 - во всех остальных случаях; |
| { |
| поднять приоритет работы процессора таким образом, чтобы|
| заблокировать все прерывания; |
| перевести процесс в состояние приостанова; |
| включить процесс в хеш-очередь приостановленных процес- |
| сов, базирующуюся на адресах приостанова; |
| сохранить адрес приостанова в таблице процессов; |
| сделать ввод для процесса приоритетным; |
| если (приостанов процесса НЕ допускает прерываний) |
| { |
| выполнить переключение контекста; |
| /* с этого места процесс возобновляет выполнение, |
| когда "пробуждается" */ |
| снизить приоритет работы процессора так, чтобы вновь |
| разрешить прерывания (как было до приостанова про- |
| цесса); |
| возвратить (0); |
| } |
| |
| /* приостанов процесса принимает прерывания, вызванные |
| сигналами */ |
| если (к процессу не имеет отношения ни один из сигналов)|
| { |
| выполнить переключение контекста; |
| /* с этого места процесс возобновляет выполнение, |
| когда "пробуждается" */ |
| если (к процессу не имеет отношения ни один из сигна-|
| лов) |
| { |
| восстановить приоритет работы процессора таким, |
| каким он был в момент приостанова процесса; |
| возвратить (0); |
| } |
| } |
| удалить процесс из хеш-очереди приостановленных процес- |
| сов, если он все еще находится там; |
| |
| восстановить приоритет работы процессора таким, каким он|
| был в момент приостанова процесса; |
| если (приоритет приостановленного процесса позволяет |
| принимать сигналы) |
| возвратить (1); |
| запустить алгоритм longjump; |
| } |
+------------------------------------------------------------+
Рисунок 6.31. Алгоритм приостанова процесса
172
На Рисунке 6.31 приведен алгоритм приостанова процесса. Сначала ядро по-
вышает приоритет работы процессора так, чтобы заблокировать все прерывания,
которые могли бы (путем создания конкуренции) помешать работе с очередями
приостановленных процессов, и запоминает старый приоритет, чтобы восстано-
вить его, когда выполнение процесса будет возобновлено. Процесс получает по-
метку "приостановленного", адрес приостанова и приоритет запоминаются в таб-
лице процессов, а процесс помещается в хеш-очередь приостановленных процес-
сов. В простейшем случае (когда приостанов не допускает прерываний) процесс
выполняет переключение контекста и благополучно "засыпает". Когда приоста-
новленный процесс "пробуждается", ядро начинает планировать его запуск: про-
цесс возвращает сохраненный в алгоритме sleep контекст, восстанавливает ста-
рый приоритет работы процессора (который был у него до начала выполнения ал-
горитма) и возвращает управление ядру.
+------------------------------------------------------------+
| алгоритм wakeup /* возобновление приостановленного про- |
| цесса */ |
| входная информация: адрес приостанова |
| выходная информация: отсутствует |
| { |
| повысить приоритет работы процессора таким образом, что-|
| бы заблокировать все прерывания; |
| найти хеш-очередь приостановленных процессов с указанным|
| адресом приостанова; |
| для (каждого процесса, приостановленного по указанному |
| адресу) |
| { |
| удалить процесс из хеш-очереди; |
| сделать пометку о том, что процесс находится в состо-|
| янии "готовности к запуску"; |
| включить процесс в список процессов, готовых к запус-|
| ку (для планировщика процессов); |
| очистить поле, содержащее адрес приостанова, в записи|
| таблицы процессов; |
| если (процесс не загружен в память) |
| возобновить выполнение программы подкачки (нуле-|
| вой процесс); |
| в противном случае |
| если (возобновляемый процесс более подходит для ис- |
| полнения, чем ныне выполняющийся) |
| установить соответствующий флаг для планировщи- |
| ка; |
| } |
| восстановить первоначальный приоритет работы процессора;|
| } |
+------------------------------------------------------------+
Рисунок 6.32. Алгоритм возобновления приостановленного процесса
Чтобы возобновить выполнение приостановленных процессов, ядро обращается
к алгоритму wakeup (Рисунок 6.32), причем делает это как во время исполнения
алгоритмов реализации стандартных системных функций, так и в случае обработ-
ки прерываний. Алгоритм iput, например, освобождает заблокированный индекс и
173
возобновляет выполнение всех процессов, ожидающих снятия блокировки. Точно
так же и программа обработки прерываний от диска возобновляет выполнение
процессов, ожидающих завершения ввода-вывода. В алгоритме wakeup ядро снача-
ла повышает приоритет работы процессора, чтобы заблокировать прерывания. За-
тем для каждого процесса, приостановленного по указанному адресу, выполняют-
ся следующие действия: делается пометка в поле, описывающем состояние про-
цесса, о том, что процесс готов к запуску; процесс удаляется из списка при-
остановленных процессов и помещается в список процессов, готовых к запуску;
поле в записи таблицы процессов, содержащее адрес приостанова, очищается.
Если возобновляемый процесс не загружен в память, ядро запускает процесс
подкачки, обеспечивающий подкачку возобновляемого процесса в память (подра-
зумевается система, в которой подкачка страниц по обращению не поддерживает-
ся); в противном случае, если возобновляемый процесс более подходит для ис-
полнения, чем ныне выполняющийся, ядро устанавливает для планировщика специ-
альный флаг, сообщающий о том, что процессу по возвращении в режим задачи
следует пройти через алгоритм планирования (глава 8). Наконец, ядро восста-
навливает первоначальный приоритет работы процессора. При этом на ядро не
оказывается никакого давления: "пробуждение" (wakeup) процесса не вызывает
его немедленного исполнения; благодаря "пробуждению", процесс становится
только доступным для запуска.
Все, о чем говорилось выше, касается простейшего случая выполнения алго-
ритмов sleep и wakeup, поскольку предполагается, что процесс приостанавлива-
ется до наступления соответствующего события. Во многих случаях процессы
приостанавливаются в ожидании событий, которые "должны" наступить, например,
в ожидании освобождения ресурса (индексов или буферов) или в ожидании завер-
шения ввода-вывода, связанного с диском. Уверенность процесса в неминуемом
возобновлении основана на том, что подобные ресурсы могут быть предоставлены
только во временное пользование. Тем не менее, иногда процесс может приоста-
новиться в ожидании события, не будучи уверенным в неизбежном наступлении
последнего, в таком случае у процесса должна быть возможность в любом случае
вернуть себе управление и продолжить выполнение. В подобных ситуациях ядро
немедленно нарушает "сон" приостановленного процесса, посылая ему сигнал.
Более подробно о сигналах мы поговорим в следующей главе; здесь же примем
допущение, что ядро может (выборочно) возобновлять приостановленные процессы
по сигналу и что процесс может распознавать получаемые сигналы.
Например, если процесс обратился к системной функции чтения с терминала,
ядро не будет в состоянии выполнить запрос процесса до тех пор, пока пользо-
ватель не введет данные с клавиатуры терминала (глава 10). Тем не менее,
пользователь, запустивший процесс, может оставить терминал на весь день, при
этом процесс останется приостановленным в ожидании ввода, а терминал может
понадобиться другому пользователю. Если другой пользователь прибегнет к ре-
шительным мерам (таким как выключение терминала), ядро должно иметь возмож-
ность восстановить отключенный процесс: в качестве первого шага ядру следует
возобновить приостановленный процесс по сигналу. В том, что процессы могут
приостановиться на длительное время, нет ничего плохого. Приостановленный
процесс занимает позицию в таблице процессов и может поэтому удлинять время
поиска (ожидания) путем выполнения определенных алгоритмов, которые не зани-
мают время центрального процессора и поэтому выполняются практически неза-
метно.
Чтобы как-то различать между собой состояния приостанова, ядро устанав-
ливает для приостанавливаемого процесса (при входе в это состояние) приори-
тет планирования на основании соответствующего параметра алгоритма sleep. То
есть ядро запускает алгоритм sleep с параметром "приоритет", в котором отра-
жается наличие уверенности в неизбежном наступлении ожидаемого события. Если
приоритет превышает пороговое значение, процесс не будет преждевременно вы-
ходить из приостанова по получении сигнала, а будет продолжать ожидать нас-
тупления события. Если же значение приоритета ниже порогового, процесс будет
немедленно возобновлен по получении сигнала (****).
174
---------------------------------------
(****) Словами "выше" и "ниже" мы заменяем термины "высокий приоритет" и
"низкий приоритет". Однако на практике приоритет может измеряться
числами, более низкие значения которых подразумевают более высокий
приоритет.
Проверка того, имеет ли процесс уже сигнал при входе в алгоритм sleep,
позволяет выяснить, приостанавливался ли процесс ранее. Например, если зна-
чение приоритета в вызове алгоритма sleep превышает пороговое значение, про-
цесс приостанавливается в ожидании выполнения алгоритма wakeup. Если же зна-
чение приоритета ниже порогового, выполнение процесса не приостанавливается,
но на сигнал процесс реагирует точно так же, как если бы он был приостанов-
лен. Если ядро не проверит наличие сигналов перед приостановом, возможна
опасность, что сигнал больше не поступит вновь и в этом случае процесс ни-
когда не возобновится.
Когда процесс "пробуждается" по сигналу (или когда он не переходит в
состояние приостанова из-за наличия сигнала), ядро может выполнить алгоритм
longjump (в зависимости от причины, по которой процесс был приостановлен). С
помощью алгоритма longjump ядро восстанавливает ранее сохраненный контекст,
если нет возможности завершить выполняемую системную функцию. Например, если
изза того, что пользователь отключил терминал, было прервано чтение данных с
терминала, функция read не будет завершена, но возвратит признак ошибки. Это
касается всех системных функций, которые могут быть прерваны во время приос-
танова. После выхода из приостанова процесс не сможет нормально продолжать-
ся, поскольку ожидаемое событие не наступило. Перед выполнением большинства
системных функций ядро сохраняет контекст процесса, используя алгоритм
setjump и вызывая тем самым необходимость в последующем выполнении алгоритма
longjump.
Встречаются ситуации, когда ядро требует, чтобы процесс возобновился по
получении сигнала, но не выполняет алгоритм longjump. Ядро запускает алго-
ритм sleep со специальным значением параметра "приоритет", подавляющим ис-
полнение алгоритма longjump и заставляющим алгоритм sleep возвращать код,
равный 1. Такая мера более эффективна по сравнению с немедленным выполнением
алгоритма setjump перед вызовом sleep и последующим выполнением алгоритма
longjump для восстановления первоначального контекста процесса. Задача зак-
лючается в том, чтобы позволить ядру очищать локальные структуры данных.
Драйвер устройства, например, может выделить свои частные структуры данных и
приостановиться с приоритетом, допускающим прерывания; если по сигналу его
работа возобновляется, он освобождает выделенные структуры, а затем выполня-
ет алгоритм longjump, если необходимо. Пользователь не имеет возможности
проконтролировать, выполняет ли процесс алгоритм longjump; выполнение этого
алгоритма зависит от причины приостановки процесса, а также от того, требуют
ли структуры данных ядра внесения изменений перед выходом из системной функ-
ции.
Мы завершили рассмотрение контекста процесса. Процессы в системе UNIX
могут находиться в различных логических состояниях и переходить из состояния
в состояние в соответствии с установленными правилами перехода, при этом ин-
формация о состоянии сохраняется в таблице процессов и в адресном пространс-
тве процесса. Контекст процесса состоит из пользовательского контекста и
системного контекста. Пользовательский контекст состоит из программ процес-
са, данных, стека задачи и областей разделяемой памяти, а системный контекст
состоит из статической части (запись в таблице процессов, адресное простран-
ство процесса и информация, необходимая для отображения адресного пространс-
тва) и динамической части (стек ядра и сохраненное состояние регистров пре-
дыдущего контекстного уровня системы), которые запоминаются в стеке и выби-
175
раются из стека при выполнении процессом обращений к системным функциям, при
обработке прерываний и при переключениях контекста. Пользовательский кон-
текст процесса распадается на отдельные области, которые представляют собой
непрерывные участки виртуального адресного пространства и трактуются как са-
мостоятельные объекты использования и защиты. В модели управления памятью,
которая использовалась при описании формата виртуального адресного простран-
ства процесса, предполагалось наличие у каждой области процесса своей табли-
цы страниц. Ядро располагает целым набором различных алгоритмов для работы с
областями. В заключительной части главы были рассмотрены алгоритмы приоста-
нова (sleep) и возобновления (wakeup) процессов. Структуры и алгоритмы, опи-
санные в данной главе, будут использоваться в последующих главах при расс-
мотрении системных функций управления процессами и планирования их выполне-
ния, а также при объяснении различных методов распределения памяти.
1. Составьте алгоритм преобразования виртуальных адресов в физические, на
входе которого задаются виртуальный адрес и адрес точки входа в частную
таблицу областей.
2. В машинах AT&T 3B2 и NSC серии 32000 используется двухуровневая схема
трансляции виртуальных адресов в физические (с сегментацией). То есть в
системе поддерживается указатель на таблицу страниц, каждая запись ко-
торой может адресовать фиксированную часть адресного пространства про-
цесса по смещению в таблице. Сравните алгоритм трансляции виртуальных
адресов на этих машинах с алгоритмом, изложенным в тексте при обсужде-
нии модели управления памятью. Подумайте над проблемами производитель-
ности и потребности в памяти для размещения вспомогательных таблиц.
область без изменений (область не является областью разделяемой памяти или
областью команд с признаками неотъемлемой части процесса, о чем будет идти
речь в разделе 7.5), ядро освобождает область по алгоритму freereg. В про-
тивном случае ядро снимает с индекса и с области блокировку, установленную
для того, чтобы предотвратить конкуренцию между параллельно выполняющимися
процессами (см. раздел 7.5), но оставляет область и ее ресурсы без измене-
ний.
168
Частные таблицы областей процессов Области
+--------------+ +-------------+
Команды | +-------------->| Разделяемая |
+--------------+ +------->+-------------+
Данные | +----+ |
+--------------+ | | +-------------+
Стек | +--+ +-|------->| Частная +-+
+--------------+ | | +-------------+ | Копи-
Процесс A | | | рова-
| | +-------------+ | ние
+---|------->| Частная +-|-+ дан-
+--------------+ | +-------------+ | | ных
Команды | +------+ | |
+--------------+ +-------------+ | |
Данные | +-------------->| Частная |<+ |
+--------------+ +-------------+ |
Стек | +------+ |
+--------------+ | +-------------+ |
Процесс B +------->| Частная |<--+
+-------------+
Рисунок 6.27. Копирование содержимого области
+------------------------------------------------------------+
| алгоритм dupreg /* копирование содержимого существующей |
| области */ |
| входная информация: указатель на точку входа в таблице об-|
| ластей |
| выходная информация: указатель на область, являющуюся точ- |
| ной копией существующей области |
| { |
| если (область разделяемая) |
| /* в вызывающей программе счетчик ссылок на об- |
| ласть будет увеличен, после чего будет испол- |
| нен алгоритм attachreg */ |
| возвратить (указатель на исходную область); |
| выделить новую область (алгоритм allocreg); |
| установить значения вспомогательных структур управления|
| памятью в точном соответствии со значениями существую-|
| щих структур исходной области; |
| выделить для содержимого области физическую память; |
| "скопировать" содержимое исходной области во вновь соз-|
| данную область; |
| возвратить (указатель на выделенную область); |
| } |
+------------------------------------------------------------+
Рисунок 6.28. Алгоритм копирования содержимого существующей области
Системная функция fork требует, чтобы ядро скопировало содержимое облас-
тей процесса. Если же область разделяемая (разделяемый текст команд или раз-
деляемая память), ядру нет надобности копировать область физически; вместо
этого оно увеличивает значение счетчика ссылок на область, позволяя роди-
тельскому и порожденному процессам использовать область совместно. Если об-
ласть не является разделяемой и ядру нужно физически копировать ее содержи-
мое, оно выделяет новую запись в таблице областей, новую таблицу страниц и
169
отводит под создаваемую область физическую память. В качестве примера расс-
мотрим Рисунок 6.27, где процесс A порождает с помощью функции fork процесс
B и копирует области родительского процесса. Область команд процесса A явля-
ется разделяемой, поэтому процесс B может использовать эту область совместно
с процессом A. Однако области данных и стека родительского процесса являются
его личной принадлежностью (имеют частный тип), поэтому процессу B нужно
скопировать их содержимое во вновь выделенные области. При этом даже для об-
ластей частного типа физическое копирование области не всегда необходимо, в
чем мы убедимся позже (глава 9). На Рисунке 6.28 приведен алгоритм копирова-
ния содержимого области (dupreg).
К настоящему моменту мы рассмотрели все функции работы с внутренними
структурами процесса, выполняющиеся на нижнем уровне взаимодействия с про-
цессом и обеспечивающие переход в состояние "выполнения в режиме ядра" и вы-
ход из этого состояния в другие состояния, за исключением функций, переводя-
щих процесс в состояние "приостанова выполнения". Теперь перейдем к рассмот-
рению алгоритмов, с помощью которых процесс переводится из состояния "выпол-
нения в режиме ядра" в состояние "приостанова в памяти" и из состояния при-
останова в состояния "готовности к запуску" с выгрузкой и без выгрузки из
памяти.
+-------------------------------+
| Контекстный уровень ядра 2 |
| Исполнить программу пере- |
| ключения контекста |
| |
| Сохранить регистровый кон- |
| текст обращения к системной |
| функции |
Запуск алгоритма приостанова -+-------------------------------+
^ | Контекстный уровень ядра 1 |
| | Исполнить обращение к сис- |
| | темной функции |
| | |
| | Сохранить регистровый кон- |
| | текст пользовательского |
| | уровня |
Вызов системной функции ------+-------------------------------+
^
|
|
Исполнение в режиме задачи
Рисунок 6.29. Стандартные контекстные уровни приостановленно-
го процесса
Выполнение процесса приостанавливается обычно во время исполнения запро-
шенной им системной функции: процесс переходит в режим ядра (контекстный
уровень 1), исполняя внутреннее прерывание операционной системы, и приоста-
навливается в ожидании ресурсов. При этом процесс переключает контекст, за-
поминая в стеке свой текущий контекстный уровень и исполняясь далее в рамках
системного контекстного уровня 2 (Рисунок 6.29). Выполнение процессов приос-
танавливается также и в том случае, когда оно наталкивается на отсутствие
страницы в результате обращения к виртуальным адресам, не загруженным физи-
чески; процессы не будут выполняться, пока ядро не считает содержимое стра-
170
ниц.
Как уже говорилось во второй главе, процессы приостанавливаются до нас-
тупления определенного события, после которого они "пробуждаются" и перехо-
дят в состояние "готовности к выполнению" (с выгрузкой и без выгрузки из па-
мяти). Такого рода абстрактное рассуждение недалеко от истины, ибо в конк-
ретном воплощении совокупность событий отображается на совокупность вирту-
альных адресов (ядра). Адреса, с которыми связаны события, закодированы в
ядре, и их единственное назначение состоит в их использовании в процес-
процесс a ---+ +--- ожидание завершения ---+
| | ввода-вывода |
процесс b -++|----+ |
||| +---- адрес A
процесс c -|++-------- ожидание выделения |
+----++--- (освобождения) буфера --+
процесс d --+ ||+--+|
| |||+--+
процесс e --|---|+||
|+--|-+|
процесс f --|+ +--|-- ожидание выделения --------- адрес B
| +----|-(освобождения) индекса
процесс g --|-+ |
+|------+
процесс h -++--------- ожидание ввода с тер- ------ адрес C
минала
Рисунок 6.30. Процессы, приостановленные до наступления собы-
тий, и отображение событий на конкретные адреса
се отображения ожидаемого события на конкретный адрес. Как для абстрактного
рассмотрения, так и для конкретной реализации события безразлично, сколько
процессов одновременно ожидают его наступления. Как результат, возможно воз-
никновение некоторых противоречий. Во-первых, когда событие наступает и про-
цессы, ожидающие его, соответствующим образом оповещаются об этом, все они
"пробуждаются" и переходят в состояние "готовности к выполнению". Ядро выво-
дит процессы из состояния приостанова все сразу, а не по одному, несмотря на
то, что они в принципе могут конкурировать за одну и ту же заблокированную
структуру данных и большинство из них через небольшой промежуток времени
опять вернется в состояние приостанова (более подробно об этом шла речь в
главах 2 и 3). На Рисунке 6.30 изображены несколько процессов, приостанов-
ленных до наступления определенных событий.
Еще одно противоречие связано с тем, что на один и тот же адрес могут
отображаться несколько событий. На Рисунке 6.30, например, события "освобож-
дение буфера" и "завершение ввода-вывода" отображаются на адрес буфера ("ад-
рес A"). Когда ввод-вывод в буфер завершается, ядро возобновляет выполнение
всех процессов, приостановленных в ожидании наступления как того, так и дру-
гого события. Поскольку процесс, ожидающий завершения ввода-вывода, удержи-
вает буфер заблокированным, другие процессы, которые ждали освобождения бу-
фера, вновь приостановятся, ибо буфер все еще занят. Функционирование систе-
мы было бы более эффективным, если бы отображение событий на адреса было од-
нозначным. Однако на практике такого рода противоречие на производительности
системы не отражается, поскольку отображение на один адрес более одного со-
бытия имеет место довольно редко, а также поскольку выполняющийся процесс
обычно освобождает заблокированные ресурсы до того, как начнут выполняться
171
другие процессы. Стилистически, тем не менее, механизм функционирования ядра
стал бы более понятен, если бы отображение было однозначным.
+------------------------------------------------------------+
| алгоритм sleep |
| входная информация: (1) адрес приостанова |
| (2) приоритет |
| выходная информация: 1, если процесс возобновляется по сиг-|
| налу, который ему удалось уловить; |
| вызов алгоритма longjump, если процесс|
| возобновляется по сигналу, который ему|
| не удалось уловить; |
| 0 - во всех остальных случаях; |
| { |
| поднять приоритет работы процессора таким образом, чтобы|
| заблокировать все прерывания; |
| перевести процесс в состояние приостанова; |
| включить процесс в хеш-очередь приостановленных процес- |
| сов, базирующуюся на адресах приостанова; |
| сохранить адрес приостанова в таблице процессов; |
| сделать ввод для процесса приоритетным; |
| если (приостанов процесса НЕ допускает прерываний) |
| { |
| выполнить переключение контекста; |
| /* с этого места процесс возобновляет выполнение, |
| когда "пробуждается" */ |
| снизить приоритет работы процессора так, чтобы вновь |
| разрешить прерывания (как было до приостанова про- |
| цесса); |
| возвратить (0); |
| } |
| |
| /* приостанов процесса принимает прерывания, вызванные |
| сигналами */ |
| если (к процессу не имеет отношения ни один из сигналов)|
| { |
| выполнить переключение контекста; |
| /* с этого места процесс возобновляет выполнение, |
| когда "пробуждается" */ |
| если (к процессу не имеет отношения ни один из сигна-|
| лов) |
| { |
| восстановить приоритет работы процессора таким, |
| каким он был в момент приостанова процесса; |
| возвратить (0); |
| } |
| } |
| удалить процесс из хеш-очереди приостановленных процес- |
| сов, если он все еще находится там; |
| |
| восстановить приоритет работы процессора таким, каким он|
| был в момент приостанова процесса; |
| если (приоритет приостановленного процесса позволяет |
| принимать сигналы) |
| возвратить (1); |
| запустить алгоритм longjump; |
| } |
+------------------------------------------------------------+
Рисунок 6.31. Алгоритм приостанова процесса
172
На Рисунке 6.31 приведен алгоритм приостанова процесса. Сначала ядро по-
вышает приоритет работы процессора так, чтобы заблокировать все прерывания,
которые могли бы (путем создания конкуренции) помешать работе с очередями
приостановленных процессов, и запоминает старый приоритет, чтобы восстано-
вить его, когда выполнение процесса будет возобновлено. Процесс получает по-
метку "приостановленного", адрес приостанова и приоритет запоминаются в таб-
лице процессов, а процесс помещается в хеш-очередь приостановленных процес-
сов. В простейшем случае (когда приостанов не допускает прерываний) процесс
выполняет переключение контекста и благополучно "засыпает". Когда приоста-
новленный процесс "пробуждается", ядро начинает планировать его запуск: про-
цесс возвращает сохраненный в алгоритме sleep контекст, восстанавливает ста-
рый приоритет работы процессора (который был у него до начала выполнения ал-
горитма) и возвращает управление ядру.
+------------------------------------------------------------+
| алгоритм wakeup /* возобновление приостановленного про- |
| цесса */ |
| входная информация: адрес приостанова |
| выходная информация: отсутствует |
| { |
| повысить приоритет работы процессора таким образом, что-|
| бы заблокировать все прерывания; |
| найти хеш-очередь приостановленных процессов с указанным|
| адресом приостанова; |
| для (каждого процесса, приостановленного по указанному |
| адресу) |
| { |
| удалить процесс из хеш-очереди; |
| сделать пометку о том, что процесс находится в состо-|
| янии "готовности к запуску"; |
| включить процесс в список процессов, готовых к запус-|
| ку (для планировщика процессов); |
| очистить поле, содержащее адрес приостанова, в записи|
| таблицы процессов; |
| если (процесс не загружен в память) |
| возобновить выполнение программы подкачки (нуле-|
| вой процесс); |
| в противном случае |
| если (возобновляемый процесс более подходит для ис- |
| полнения, чем ныне выполняющийся) |
| установить соответствующий флаг для планировщи- |
| ка; |
| } |
| восстановить первоначальный приоритет работы процессора;|
| } |
+------------------------------------------------------------+
Рисунок 6.32. Алгоритм возобновления приостановленного процесса
Чтобы возобновить выполнение приостановленных процессов, ядро обращается
к алгоритму wakeup (Рисунок 6.32), причем делает это как во время исполнения
алгоритмов реализации стандартных системных функций, так и в случае обработ-
ки прерываний. Алгоритм iput, например, освобождает заблокированный индекс и
173
возобновляет выполнение всех процессов, ожидающих снятия блокировки. Точно
так же и программа обработки прерываний от диска возобновляет выполнение
процессов, ожидающих завершения ввода-вывода. В алгоритме wakeup ядро снача-
ла повышает приоритет работы процессора, чтобы заблокировать прерывания. За-
тем для каждого процесса, приостановленного по указанному адресу, выполняют-
ся следующие действия: делается пометка в поле, описывающем состояние про-
цесса, о том, что процесс готов к запуску; процесс удаляется из списка при-
остановленных процессов и помещается в список процессов, готовых к запуску;
поле в записи таблицы процессов, содержащее адрес приостанова, очищается.
Если возобновляемый процесс не загружен в память, ядро запускает процесс
подкачки, обеспечивающий подкачку возобновляемого процесса в память (подра-
зумевается система, в которой подкачка страниц по обращению не поддерживает-
ся); в противном случае, если возобновляемый процесс более подходит для ис-
полнения, чем ныне выполняющийся, ядро устанавливает для планировщика специ-
альный флаг, сообщающий о том, что процессу по возвращении в режим задачи
следует пройти через алгоритм планирования (глава 8). Наконец, ядро восста-
навливает первоначальный приоритет работы процессора. При этом на ядро не
оказывается никакого давления: "пробуждение" (wakeup) процесса не вызывает
его немедленного исполнения; благодаря "пробуждению", процесс становится
только доступным для запуска.
Все, о чем говорилось выше, касается простейшего случая выполнения алго-
ритмов sleep и wakeup, поскольку предполагается, что процесс приостанавлива-
ется до наступления соответствующего события. Во многих случаях процессы
приостанавливаются в ожидании событий, которые "должны" наступить, например,
в ожидании освобождения ресурса (индексов или буферов) или в ожидании завер-
шения ввода-вывода, связанного с диском. Уверенность процесса в неминуемом
возобновлении основана на том, что подобные ресурсы могут быть предоставлены
только во временное пользование. Тем не менее, иногда процесс может приоста-
новиться в ожидании события, не будучи уверенным в неизбежном наступлении
последнего, в таком случае у процесса должна быть возможность в любом случае
вернуть себе управление и продолжить выполнение. В подобных ситуациях ядро
немедленно нарушает "сон" приостановленного процесса, посылая ему сигнал.
Более подробно о сигналах мы поговорим в следующей главе; здесь же примем
допущение, что ядро может (выборочно) возобновлять приостановленные процессы
по сигналу и что процесс может распознавать получаемые сигналы.
Например, если процесс обратился к системной функции чтения с терминала,
ядро не будет в состоянии выполнить запрос процесса до тех пор, пока пользо-
ватель не введет данные с клавиатуры терминала (глава 10). Тем не менее,
пользователь, запустивший процесс, может оставить терминал на весь день, при
этом процесс останется приостановленным в ожидании ввода, а терминал может
понадобиться другому пользователю. Если другой пользователь прибегнет к ре-
шительным мерам (таким как выключение терминала), ядро должно иметь возмож-
ность восстановить отключенный процесс: в качестве первого шага ядру следует
возобновить приостановленный процесс по сигналу. В том, что процессы могут
приостановиться на длительное время, нет ничего плохого. Приостановленный
процесс занимает позицию в таблице процессов и может поэтому удлинять время
поиска (ожидания) путем выполнения определенных алгоритмов, которые не зани-
мают время центрального процессора и поэтому выполняются практически неза-
метно.
Чтобы как-то различать между собой состояния приостанова, ядро устанав-
ливает для приостанавливаемого процесса (при входе в это состояние) приори-
тет планирования на основании соответствующего параметра алгоритма sleep. То
есть ядро запускает алгоритм sleep с параметром "приоритет", в котором отра-
жается наличие уверенности в неизбежном наступлении ожидаемого события. Если
приоритет превышает пороговое значение, процесс не будет преждевременно вы-
ходить из приостанова по получении сигнала, а будет продолжать ожидать нас-
тупления события. Если же значение приоритета ниже порогового, процесс будет
немедленно возобновлен по получении сигнала (****).
174
---------------------------------------
(****) Словами "выше" и "ниже" мы заменяем термины "высокий приоритет" и
"низкий приоритет". Однако на практике приоритет может измеряться
числами, более низкие значения которых подразумевают более высокий
приоритет.
Проверка того, имеет ли процесс уже сигнал при входе в алгоритм sleep,
позволяет выяснить, приостанавливался ли процесс ранее. Например, если зна-
чение приоритета в вызове алгоритма sleep превышает пороговое значение, про-
цесс приостанавливается в ожидании выполнения алгоритма wakeup. Если же зна-
чение приоритета ниже порогового, выполнение процесса не приостанавливается,
но на сигнал процесс реагирует точно так же, как если бы он был приостанов-
лен. Если ядро не проверит наличие сигналов перед приостановом, возможна
опасность, что сигнал больше не поступит вновь и в этом случае процесс ни-
когда не возобновится.
Когда процесс "пробуждается" по сигналу (или когда он не переходит в
состояние приостанова из-за наличия сигнала), ядро может выполнить алгоритм
longjump (в зависимости от причины, по которой процесс был приостановлен). С
помощью алгоритма longjump ядро восстанавливает ранее сохраненный контекст,
если нет возможности завершить выполняемую системную функцию. Например, если
изза того, что пользователь отключил терминал, было прервано чтение данных с
терминала, функция read не будет завершена, но возвратит признак ошибки. Это
касается всех системных функций, которые могут быть прерваны во время приос-
танова. После выхода из приостанова процесс не сможет нормально продолжать-
ся, поскольку ожидаемое событие не наступило. Перед выполнением большинства
системных функций ядро сохраняет контекст процесса, используя алгоритм
setjump и вызывая тем самым необходимость в последующем выполнении алгоритма
longjump.
Встречаются ситуации, когда ядро требует, чтобы процесс возобновился по
получении сигнала, но не выполняет алгоритм longjump. Ядро запускает алго-
ритм sleep со специальным значением параметра "приоритет", подавляющим ис-
полнение алгоритма longjump и заставляющим алгоритм sleep возвращать код,
равный 1. Такая мера более эффективна по сравнению с немедленным выполнением
алгоритма setjump перед вызовом sleep и последующим выполнением алгоритма
longjump для восстановления первоначального контекста процесса. Задача зак-
лючается в том, чтобы позволить ядру очищать локальные структуры данных.
Драйвер устройства, например, может выделить свои частные структуры данных и
приостановиться с приоритетом, допускающим прерывания; если по сигналу его
работа возобновляется, он освобождает выделенные структуры, а затем выполня-
ет алгоритм longjump, если необходимо. Пользователь не имеет возможности
проконтролировать, выполняет ли процесс алгоритм longjump; выполнение этого
алгоритма зависит от причины приостановки процесса, а также от того, требуют
ли структуры данных ядра внесения изменений перед выходом из системной функ-
ции.
Мы завершили рассмотрение контекста процесса. Процессы в системе UNIX
могут находиться в различных логических состояниях и переходить из состояния
в состояние в соответствии с установленными правилами перехода, при этом ин-
формация о состоянии сохраняется в таблице процессов и в адресном пространс-
тве процесса. Контекст процесса состоит из пользовательского контекста и
системного контекста. Пользовательский контекст состоит из программ процес-
са, данных, стека задачи и областей разделяемой памяти, а системный контекст
состоит из статической части (запись в таблице процессов, адресное простран-
ство процесса и информация, необходимая для отображения адресного пространс-
тва) и динамической части (стек ядра и сохраненное состояние регистров пре-
дыдущего контекстного уровня системы), которые запоминаются в стеке и выби-
175
раются из стека при выполнении процессом обращений к системным функциям, при
обработке прерываний и при переключениях контекста. Пользовательский кон-
текст процесса распадается на отдельные области, которые представляют собой
непрерывные участки виртуального адресного пространства и трактуются как са-
мостоятельные объекты использования и защиты. В модели управления памятью,
которая использовалась при описании формата виртуального адресного простран-
ства процесса, предполагалось наличие у каждой области процесса своей табли-
цы страниц. Ядро располагает целым набором различных алгоритмов для работы с
областями. В заключительной части главы были рассмотрены алгоритмы приоста-
нова (sleep) и возобновления (wakeup) процессов. Структуры и алгоритмы, опи-
санные в данной главе, будут использоваться в последующих главах при расс-
мотрении системных функций управления процессами и планирования их выполне-
ния, а также при объяснении различных методов распределения памяти.
1. Составьте алгоритм преобразования виртуальных адресов в физические, на
входе которого задаются виртуальный адрес и адрес точки входа в частную
таблицу областей.
2. В машинах AT&T 3B2 и NSC серии 32000 используется двухуровневая схема
трансляции виртуальных адресов в физические (с сегментацией). То есть в
системе поддерживается указатель на таблицу страниц, каждая запись ко-
торой может адресовать фиксированную часть адресного пространства про-
цесса по смещению в таблице. Сравните алгоритм трансляции виртуальных
адресов на этих машинах с алгоритмом, изложенным в тексте при обсужде-
нии модели управления памятью. Подумайте над проблемами производитель-
ности и потребности в памяти для размещения вспомогательных таблиц.