| | | Сохранить регистровый кон- | | | текст пользовательского | | | уровня | Вызов системной функции ------+-------------------------------+ ^ | | Исполнение в режиме задачи Рисунок 6.29. Стандартные контекстные уровни приостановленно- го процесса Выполнение процесса приостанавливается обычно во время исполнения запро- шенной им системной функции: процесс переходит в режим ядра (контекстный уровень 1), исполняя внутреннее прерывание операционной системы, и приоста- навливается в ожидании ресурсов. При этом процесс переключает контекст, за- поминая в стеке свой текущий контекстный уровень и исполняясь далее в рамках системного контекстного уровня 2 (Рисунок 6.29). Выполнение процессов приос- танавливается также и в том случае, когда оно наталкивается на отсутствие страницы в результате обращения к виртуальным адресам, не загруженным физи- чески; процессы не будут выполняться, пока ядро не считает содержимое стра- 170 ниц. 6.6.1 События, вызывающие приостанов выполнения, и их адреса Как уже говорилось во второй главе, процессы приостанавливаются до нас- тупления определенного события, после которого они "пробуждаются" и перехо- дят в состояние "готовности к выполнению" (с выгрузкой и без выгрузки из па- мяти). Такого рода абстрактное рассуждение недалеко от истины, ибо в конк- ретном воплощении совокупность событий отображается на совокупность вирту- альных адресов (ядра). Адреса, с которыми связаны события, закодированы в ядре, и их единственное назначение состоит в их использовании в процес- процесс 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.6.2 Алгоритмы приостанова и возобновления выполнения На Рисунке 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; выполнение этого алгоритма зависит от причины приостановки процесса, а также от того, требуют ли структуры данных ядра внесения изменений перед выходом из системной функ- ции. 6.7 ВЫВОДЫ Мы завершили рассмотрение контекста процесса. Процессы в системе UNIX могут находиться в различных логических состояниях и переходить из состояния в состояние в соответствии с установленными правилами перехода, при этом ин- формация о состоянии сохраняется в таблице процессов и в адресном пространс- тве процесса. Контекст процесса состоит из пользовательского контекста и системного контекста. Пользовательский контекст состоит из программ процес- са, данных, стека задачи и областей разделяемой памяти, а системный контекст состоит из статической части (запись в таблице процессов, адресное простран- ство процесса и информация, необходимая для отображения адресного пространс- тва) и динамической части (стек ядра и сохраненное состояние регистров пре- дыдущего контекстного уровня системы), которые запоминаются в стеке и выби- 175 раются из стека при выполнении процессом обращений к системным функциям, при обработке прерываний и при переключениях контекста. Пользовательский кон- текст процесса распадается на отдельные области, которые представляют собой непрерывные участки виртуального адресного пространства и трактуются как са- мостоятельные объекты использования и защиты. В модели управления памятью, которая использовалась при описании формата виртуального адресного простран- ства процесса, предполагалось наличие у каждой области процесса своей табли- цы страниц. Ядро располагает целым набором различных алгоритмов для работы с областями. В заключительной части главы были рассмотрены алгоритмы приоста- нова (sleep) и возобновления (wakeup) процессов. Структуры и алгоритмы, опи- санные в данной главе, будут использоваться в последующих главах при расс- мотрении системных функций управления процессами и планирования их выполне- ния, а также при объяснении различных методов распределения памяти. 6.8 УПРАЖНЕНИЯ 1. Составьте алгоритм преобразования виртуальных адресов в физические, на входе которого задаются виртуальный адрес и адрес точки входа в частную таблицу областей. 2. В машинах AT&T 3B2 и NSC серии 32000 используется двухуровневая схема трансляции виртуальных адресов в физические (с сегментацией). То есть в системе поддерживается указатель на таблицу страниц, каждая запись ко- торой может адресовать фиксированную часть адресного пространства про- цесса по смещению в таблице. Сравните алгоритм трансляции виртуальных адресов на этих машинах с алгоритмом, изложенным в тексте при обсужде- нии модели управления памятью. Подумайте над проблемами производитель- ности и потребности в памяти для размещения вспомогательных таблиц. 3. В архитектуре системы VAX-11 поддерживаются два набора регистров защиты памяти, используемых машиной в процессе трансляции пользовательских ад- ресов. Механизм трансляции используется тот же, что и в предыдущем пун- кте, за одним исключением: указателей на таблицу страниц здесь два. Ес- ли процесс располагает тремя областями - команд, данных и стека - то каким образом, используя два набора регистров, следует производить отображение областей на таблицы страниц ? Увеличение стека в архитекту- ре системы VAX-11 идет в направлении младших виртуальных адресов. Какой тогда вид имела бы область стека ? В главе 11 будет рассмотрена область разделяемой памяти: как она может быть реализована в архитектуре систе- мы VAX-11 ? 4. Составьте алгоритм выделения и освобождения страниц памяти и таблиц страниц. Какие структуры данных следует использовать, чтобы достичь на- ивысшей производительности или наибольшей простоты реализации алгоритма? 5. Устройство управления памятью MC68451 для семейства микропроцессоров Motorola 68000 допускает выделение сегментов памяти размером от 256 байт до 16 мегабайт. Каждое (физическое) устройство управления памятью поддерживает 32 дескриптора сегментов. Опишите эффективный метод выде- ления памяти для этого случая. Каким образом осуществлялась бы реализа- ция областей ? 6. Рассмотрим отображение виртуальных адресов, представленное на Рисунке 6.5. Предположим, что ядро выгружает процесс (в системе с подкачкой процессов) или откачивает в область стека большое количество страниц (в системе с замещением страниц). Если через какое-то время процесс обра- тится к виртуальному адресу 68432, будет ли он должен обратиться к со- ответствующей ячейке физической памяти, из которой он считывал данные до того, как была выполнена операция выгрузки (откачки) ? Если нижние уровни системы управления памятью реализуются с использованием таблицы страниц, следует ли эти таблицы располагать в тех же, что и сами стра- ницы, местах физической памяти ? *7. Можно реализовать систему, в которой стек ядра располагается над верши- 176 ной стека задачи. Подумайте о достоинствах и недостатках подобной сис- темы. 8. Каким образом, присоединяя область к процессу, ядро может проверить то, что эта область не накладывается на виртуальные адреса областей, уже присоединенных к процессу ? 9. Обратимся к алгоритму переключения контекста. Допустим, что в системе готов к выполнению только один процесс. Другими словами, ядро выбирает для выполнения процесс с только что сохраненным контекстом. Объясните, что произойдет при этом. 10. Предположим, что процесс приостановился, но в системе нет процессов, готовых к выполнению. Что произойдет, когда приостановившийся процесс переключит контекст ? 11. Предположим, что процесс, выполняемый в режиме задачи, израсходовал вы- деленный ему квант времени и в результате прерывания по таймеру ядро выбирает для выполнения новый процесс. Объясните, почему переключение контекста произойдет на системном контекстном уровне 2. 12. В системе с замещением страниц процесс, выполняемый в режиме задачи, может столкнуться с отсутствием нужной страницы, которая не была загру- жена в память. В ходе обработки прерывания ядро считывает страницу из области подкачки и приостанавливается. Объясните, почему переключение контекста (в момент приостанова) произойдет на системном контекстном уровне 2. 13. Процесс использует системную функцию read с форматом вызова read(fd,buf,1024); в системе с замещением страниц памяти. Предположим, что ядро исполняет алгоритм read для считывания данных в системный буфер, однако при по- пытке копирования данных в адресное пространство задачи сталкивается с отсутствием нужной страницы, содержащей структуру buf, вследствие того, что она была ранее выгружена из памяти. Ядро обрабатывает возникшее прерывание, считывая отсутствующую страницу в память. Что происходит на каждом из системных контекстных уровней ? Что произойдет, если програм- ма обработки прерывания приостановится в ожидании завершения считывания страницы ? 14. Что произошло бы, если бы во время копирования данных из адресного пространства задачи в память ядра (Рисунок 6.17) обнаружилось, что ука- занный пользователем адрес неверен ? *15. При выполнении алгоритмов sleep и wakeup ядро повышает приоритет работы процессора так, чтобы не допустить прерываний, препятствующих ей. Какие отрицательные последствия могли бы возникнуть, если бы ядро не предпри- нимало этих действий ? (Намек: ядро зачастую возобновляет приостанов- ленные процессы прямо из программ обработки прерываний). *16. Предположим, что процесс пытается приостановиться до наступления собы- тия A, но, запуская алгоритм sleep, еще не заблокировал прерывания; до- пустим, что в этот момент происходит прерывание и программа его обра- ботки пытается возобновить все процессы, приостановленные до наступле- ния события A. Что случится с первым процессом ? Не представляет ли эта ситуация опасность ? Если да, то может ли ядро избежать ее возникнове- ния ? 17. Что произойдет, если ядро запустит алгоритм wakeup для всех процессов, приостановленных по адресу A, в то время, когда по этому адресу не ока- жется ни одного приостановленного процесса ? 18. По одному адресу может приостановиться множество процессов, но ядру мо- жет потребоваться возобновление только некоторых из них - тех, которым будет послан соответствующий сигнал. С помощью механизма посылки сигна- лов можно идентифицировать отдельные процессы. Подумайте, какие измене- ния следует произвести в алгоритме wakeup для того, чтобы можно было возобновлять выполнение только одного процесса, а не всех процессов, приостановленных по заданному адресу. 19. Обращения к алгоритмам sleep и wakeup в системе Multics 177 имеют следующий синтаксис: sleep (событие); wakeup (событие, приоритет); Таким образом, в алгоритме wakeup возобновляемому процессу присваивает- ся приоритет. Сравните форму вызова этих алгоритмов с формой вызова со- 178