и в результате не могут использоваться в качестве указателей адресов. Если страницу с нулевым адресом соответствующим образом защитить, процессы, случайно обратившиеся к этому адресу, натолкнутся на ошибку и будут аварийно завершены, и это ускорит обнаружение подобных ошибок в программах. При загрузке файла в область алгоритм loadreg (Рисунок 6.23) проверяет разрыв между виртуальным адресом, по которому область присоединяется к про- цессу, и виртуальным адресом, с которого располагаются данные области, и расширяет область в соответствии с требуемым объемом памяти. Затем область 164 Частная таблица областей Частная таблица областей процесса процесса +-------+----------+------+ +-------+----------+------+ | Адрес | Виртуаль-| Раз- | | Адрес | Виртуаль-| Раз- | | табли-| ный адрес| мер | | табли-| ный адрес| мер | | цы | в прост- | и | | цы | в прост- | и | | стра- | ранстве | защи-| | стра- | ранстве | защи-| | ниц | процесса | та | | ниц | процесса | та | +-------+----------+------+ +-------+----------+------+ | | | | | | | | +-------+----------+------+ +-------+----------+------+ | | | | | | | | Точка+-------+----------+------+ Точка+-------+----------+------+ входа| | 128K | 6K | входа| | 128K | 7K | для +---+---+----------+------+ для +---+---+----------+------+ стека +--+ стека +--+ v v +-------------+ +-------------+ | 342K | | 342K | +-------------+ +-------------+ | 779K | | 779K | +-------------+ +-------------+ | 846K | | 846K | +-------------+ +-------------+ | 752K | | 752K | +-------------+ +-------------+ | 341K | | 341K | +-------------+ +-------------+ | 484K | | 484K | +-------------+ НОВАЯ +-------------+ | | СТРАНИЦА-->| 976K | +-------------+ +-------------+ | | | | +-------------+ +-------------+ | | | | +-------------+ +-------------+ До увеличения стека После увеличения стека Рисунок 6.22. Увеличение области стека на 1 Кбайт переводится в состояние "загрузки в память", при котором данные для области считываются из файла в память с помощью встроенной модификации алгоритма системной функции read. Если ядро загружает область команд, которая может разделяться нескольки- ми процессами, возможна ситуация, когда процесс попытается воспользоваться областью до того, как ее содержимое будет полностью загружено, так как про- цесс загрузки может приостано- виться во время чтения файла. Подробно о том, как это происходит и почему при этом нельзя использовать блокировки, мы поговорим, когда будем вести речь о функции exec в следующей главе и в главе 9. Чтобы устранить эту проб- лему, ядро проверяет статус области и не разрешает к ней доступ до тех пор, пока загрузка области не будет закончена. По завершении реализации алгоритма loadreg ядро возобновляет выполнение всех процессов, ожидающих окончания загрузки области, и изменяет статус области ("готова, загружена в память"). Предположим, например, что ядру нужно загрузить текст размером 7K в об- ласть, присоединенную к процессу по виртуальному адресу 0, но при этом оста- вить промежуток размером 1 Кбайт от начала области (Рисунок 6.24). К этому 165 +------------------------------------------------------------+ | алгоритм loadreg /* загрузка части файла в область */ | | входная информация: (1) указатель на точку входа в частную| | таблицу областей процесса | | (2) виртуальный адрес загрузки | | (3) указатель индекса файла | | (4) смещение в байтах до начала считы-| | ваемой части файла | | (5) объем загружаемых данных в байтах | | выходная информация: отсутствует | | { | | увеличить размер области до требуемой величины (алгоритм| | growreg); | | записать статус области как "загружаемой в память"; | | снять блокировку с области; | | установить в пространстве процесса значения параметров | | чтения из файла: | | виртуальный адрес, по которому будут размещены счи-| | тываемые данные; | | смещение до начала считываемой части файла; | | объем данных, считываемых из файла, в байтах; | | загрузить файл в область (встроенная модификация алго- | | ритма read); | | заблокировать область; | | записать статус области как "полностью загруженной в па-| | мять"; | | возобновить выполнение всех процессов, ожидающих оконча-| | ния загрузки области; | | } | +------------------------------------------------------------+ Рисунок 6.23. Алгоритм загрузки данных области из файла времени ядро уже выделило запись в таблице областей и присоединило область по адресу 0 с помощью алгоритмов allocreg и attachreg. Теперь же ядро запус- кает алгоритм loadreg, в котором действия алгоритма growreg выполняются дважды - во-первых, при выделении в начале области промежутка в 1 Кбайт, и во-вторых, при выделении места для содержимого области - и алгоритм growreg назначает для области таблицу страниц. Затем ядро заносит в соответствующие поля пространства процесса установочные значения для чтения данных из файла: считываются 7 Кбайт, начиная с адреса, указанного в виде смещения внутри файла (параметр алгоритма), и записываются в виртуальное пространство про- цесса по адресу 1K. Частная таблица областей Частная таблица областей процесса процесса +-------+----------+------+ +-------+----------+------+ | Адрес | Виртуаль-| Раз- | | Адрес | Виртуаль-| Раз- | | табли-| ный адрес| мер | | табли-| ный адрес| мер | | цы | в прост- | и | | цы | в прост- | и | | стра- | ранстве | защи-| | стра- | ранстве | защи-| | ниц | процесса | та | | ниц | процесса | та | +-------+----------+------+ +-------+----------+------+ Текст| --- | | 0 | | | 0 | 8 | +-------+----------+------+ +---+---+----------+------+ (а) Запись таблицы в перво- +--+ начальном виде | v 166 +-------------+ | пусто | Частная таблица областей +-------------+ процесса | 779K | +-------+----------+------+ +-------------+ | Адрес | Виртуаль-| Раз- | | 846K | | табли-| ный адрес| мер | +-------------+ | цы | в прост- | и | | 752K | | стра- | ранстве | защи-| +-------------+ | ниц | процесса | та | | 341K | +-------+----------+------+ +-------------+ | | 0 | 1 | | 484K | +---+---+----------+------+ +-------------+ +--+ | 976K | | +-------------+ v | 794K | +-------------+ +-------------+ | пусто | | | +-------------+ +-------------+ (б) Запись, указывающая на (в) После второго выполне- промежуток в начале об- ния алгоритма growreg ласти (после первого выполнения алгоритма growreg) Рисунок 6.24. Загрузка области команд (текста) +------------------------------------------------------------+ | алгоритм freereg /* освобождение выделенной области */| | входная информация: указатель на (заблокированную) область| | выходная информация: отсутствует | | { | | если (счетчик ссылок на область имеет ненулевое значе- | | ние) | | { | | /* область все еще используется одним из процессов */| | снять блокировку с области; | | если (область ассоциирована с индексом) | | снять блокировку с индекса; | | возвратить управление; | | } | | если (область ассоциирована с индексом) | | освободить индекс (алгоритм iput); | | освободить связанную с областью физическую память; | | освободить связанные с областью вспомогательные таблицы;| | очистить поля области; | | включить область в список свободных областей; | | снять блокировку с области; | | } | +------------------------------------------------------------+ Рисунок 6.25. Алгоритм освобождения области 167 6.5.6 Освобождение области Если область не присоединена уже ни к какому процессу, она может быть освобождена ядром и возвращена в список свободных областей (Рисунок 6.25). Если область связана с индексом, ядро освобождает и индекс с помощью алго- ритма iput, учитывая значение счетчика ссылок на индекс, установленное в ал- горитме allocreg. Ядро освобождает все связанные с областью физические ре- сурсы, такие как таблицы страниц и собственно страницы физической памяти. Предположим, например, что ядру нужно освободить область стека, описанную на Рисунке 6.22. Если счетчик ссылок на область имеет нулевое значение, ядро освободит 7 страниц физической памяти вместе с таблицей страниц. +------------------------------------------------------------+ | алгоритм detachreg /* отсоединить область от процесса */ | | входная информация: указатель на точку входа в частной | | таблице областей процесса | | выходная информация: отсутствует | | { | | обратиться к вспомогательным таблицам процесса, имеющим | | отношение к распределению памяти, | | освободить те из них, которые связаны с областью; | | уменьшить размер процесса; | | уменьшить значение счетчика ссылок на область; | | если (значение счетчика стало нулевым и область не явля-| | ется неотъемлемой частью процесса) | | освободить область (алгоритм freereg); | | в противном случае /* либо значение счетчика отлично | | от 0, либо область является не- | | отъемлемой частью процесса */ | | { | | снять блокировку с индекса (ассоциированного с об- | | ластью); | | снять блокировку с области; | | } | | } | +------------------------------------------------------------+ Рисунок 6.26. Алгоритм отсоединения области 6.5.7 Отсоединение области от процесса Ядро отсоединяет области при выполнении системных функций exec, exit и shmdt (отсоединить разделяемую память). При этом ядро корректирует соответс- твующую запись и разъединяет связь с физической памятью, делая недействи- тельными связанные с областью регистры управления памятью (алгоритм detachreg, Рисунок 6.26). Механизм преобразования адресов после этого будет относиться уже к процессу, а не к области (как в алгоритме freereg). Ядро уменьшает значение счетчика ссылок на область и значение поля, описывающего размер процесса в записи таблицы процессов, в соответствии с размером облас- ти. Если значение счетчика становится равным 0 и если нет причины оставлять область без изменений (область не является областью разделяемой памяти или областью команд с признаками неотъемлемой части процесса, о чем будет идти речь в разделе 7.5), ядро освобождает область по алгоритму freereg. В про- тивном случае ядро снимает с индекса и с области блокировку, установленную для того, чтобы предотвратить конкуренцию между параллельно выполняющимися процессами (см. раздел 7.5), но оставляет область и ее ресурсы без измене- ний. 168 Частные таблицы областей процессов Области +--------------+ +-------------+ Команды | +-------------->| Разделяемая | +--------------+ +------->+-------------+ Данные | +----+ | +--------------+ | | +-------------+ Стек | +--+ +-|------->| Частная +-+ +--------------+ | | +-------------+ | Копи- Процесс A | | | рова- | | +-------------+ | ние +---|------->| Частная +-|-+ дан- +--------------+ | +-------------+ | | ных Команды | +------+ | | +--------------+ +-------------+ | | Данные | +-------------->| Частная |<+ | +--------------+ +-------------+ | Стек | +------+ | +--------------+ | +-------------+ | Процесс B +------->| Частная |<--+ +-------------+ Рисунок 6.27. Копирование содержимого области +------------------------------------------------------------+ | алгоритм dupreg /* копирование содержимого существующей | | области */ | | входная информация: указатель на точку входа в таблице об-| | ластей | | выходная информация: указатель на область, являющуюся точ- | | ной копией существующей области | | { | | если (область разделяемая) | | /* в вызывающей программе счетчик ссылок на об- | | ласть будет увеличен, после чего будет испол- | | нен алгоритм attachreg */ | | возвратить (указатель на исходную область); | | выделить новую область (алгоритм allocreg); | | установить значения вспомогательных структур управления| | памятью в точном соответствии со значениями существую-| | щих структур исходной области; | | выделить для содержимого области физическую память; | | "скопировать" содержимое исходной области во вновь соз-| | данную область; | | возвратить (указатель на выделенную область); | | } | +------------------------------------------------------------+ Рисунок 6.28. Алгоритм копирования содержимого существующей области 6.5.8 Копирование содержимого области Системная функция fork требует, чтобы ядро скопировало содержимое облас- тей процесса. Если же область разделяемая (разделяемый текст команд или раз- деляемая память), ядру нет надобности копировать область физически; вместо этого оно увеличивает значение счетчика ссылок на область, позволяя роди- тельскому и порожденному процессам использовать область совместно. Если об- ласть не является разделяемой и ядру нужно физически копировать ее содержи- мое, оно выделяет новую запись в таблице областей, новую таблицу страниц и 169 отводит под создаваемую область физическую память. В качестве примера расс- мотрим Рисунок 6.27, где процесс A порождает с помощью функции fork процесс B и копирует области родительского процесса. Область команд процесса A явля- ется разделяемой, поэтому процесс B может использовать эту область совместно с процессом A. Однако области данных и стека родительского процесса являются его личной принадлежностью (имеют частный тип), поэтому процессу B нужно скопировать их содержимое во вновь выделенные области. При этом даже для об- ластей частного типа физическое копирование области не всегда необходимо, в чем мы убедимся позже (глава 9). На Рисунке 6.28 приведен алгоритм копирова- ния содержимого области (dupreg). 6.6 ПРИОСТАНОВКА ВЫПОЛНЕНИЯ К настоящему моменту мы рассмотрели все функции работы с внутренними структурами процесса, выполняющиеся на нижнем уровне взаимодействия с про- цессом и обеспечивающие переход в состояние "выполнения в режиме ядра" и вы- ход из этого состояния в другие состояния, за исключением функций, переводя- щих процесс в состояние "приостанова выполнения". Теперь перейдем к рассмот- рению алгоритмов, с помощью которых процесс переводится из состояния "выпол- нения в режиме ядра" в состояние "приостанова в памяти" и из состояния при- останова в состояния "готовности к запуску" с выгрузкой и без выгрузки из памяти. +-------------------------------+ | Контекстный уровень ядра 2 | | Исполнить программу пере- | | ключения контекста | | | | Сохранить регистровый кон- | | текст обращения к системной | | функции | Запуск алгоритма приостанова -+-------------------------------+ ^ | Контекстный уровень ядра 1 | | | Исполнить обращение к сис- | | | темной функции | | | | | | Сохранить регистровый кон- | | | текст пользовательского | | | уровня | Вызов системной функции ------+-------------------------------+ ^ | | Исполнение в режиме задачи Рисунок 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