Geum.ru

The design of the unix operating system by Maurice J

Вид материалаРеферат
Подобный материал:
1   ...   34   35   36   37   38   39   40   41   ...   55

родившего фатальную ошибку памяти, отказ относится к текущему

процессу; следовательно, процессы приостанавливаются не произ-

вольным образом.


9.2.3.1 Обработка прерываний по отказу из-за недоступности

данных


Если процесс пытается обратиться к странице, бит доступности

для которой не установлен, он получает отказ из-за отсутствия

(недоступности) данных и ядро запускает программу обработки пре-

рываний по отказу данного типа (Рисунок 9.21). Бит доступности не

устанавливается ни для тех страниц, которые располагаются за пре-

делами виртуального адресного пространства процесса, ни для тех,

которые входят в состав этого пространства, но не имеют в настоя-

щий момент физического аналога в памяти. Фатальная ошибка памяти

произошла в результате обращения ядра по виртуальному адресу

страницы, поэтому ядро выходит на соответствующую этой странице

запись в таблице страниц и дескриптор дискового блока. Чтобы пре-

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

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

в памяти область с соответствующей записью таблицы страниц. Если

в дескрипторе дискового блока отсутствует информация о странице,


-------------------------------------------------------------┐

│ алгоритм vfault /* обработка отказа из-за отсутствия │

│ (недоступности) данных */ │

│ входная информация: адрес, по которому получен отказ │

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

│ { │

│ найти область, запись в таблице страниц, дескриптор дис-│

│ кового блока, связанные с адресом, по которому получен │

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

│ если (адрес не принадлежит виртуальному адресному прост-│

│ ранству процесса) │

│ { │

│ послать сигнал (SIGSEGV: нарушение сегментации) про- │

│ цессу; │

│ перейти на out; │

│ } │

│ если (адрес указан неверно) /* возможно, процесс нахо-│

│ дился в состоянии при- │

│ останова */ │

│ перейти на out; │

│ если (страница имеется в кеше) │

│ { │

│ убрать страницу из кеша; │

│ поправить запись в таблице страниц; │

│ выполнять пока (содержимое страницы не станет доступ-│

│ ным) /* другой процесс получил такой же отказ, │

│ * но раньше */ │

│ приостановиться; │

│ } │

│ в противном случае /* страница отсутствует в кеше */│

│ { │

│ назначить области новую страницу; │

│ │

│ поместить новую страницу в кеш, откорректировать за- │

│ пись в таблице pfdata; │

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

│ пометку "обнуляемая при обращении") │

│ очистить содержимое страницы; │

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

│ { │

│ считать виртуальную страницу с устройства выгруз-│

│ ки или из исполняемого файла; │

│ приостановиться (до завершения ввода-вывода); │

│ } │

│ возобновить процессы (ожидающие загрузки содержимого │

│ страницы); │

│ } │

│ установить бит доступности страницы; │

│ сбросить бит модификации и "возраст" страницы; │

│ пересчитать приоритет процесса; │

│ out: снять блокировку с области; │

│ } │

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


Рисунок 9.21. Алгоритм обработки отказа из-за отсутствия (не-

доступности) данных


сделанная ссылка на страницу является недопустимой и ядро посыла-

ет процессу-нарушителю сигнал о "нарушении сегментации" (см. Ри-

сунок 7.25). Такой порядок действий совпадает с тем порядком, ко-

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

адресу, если не принимать во внимание то обстоятельство, что ядро

узнает об ошибке немедленно, так как все "доступные" страницы яв-

ляются резидентными в памяти. Если ссылка на страницу сделана

правильно, ядро выделяет физическую страницу в памяти и считывает

в нее содержимое виртуальной страницы с устройства выгрузки или

из исполняемого файла.

Страница, вызвавшая отказ, находится в одном из пяти состоя-

ний:

1. На устройстве выгрузки вне памяти.

2. В списке свободных страниц в памяти.

3. В исполняемом файле.

4. С пометкой "обнуляемая при обращении".

5. С пометкой "заполняемая при обращении".

Рассмотрим каждый случай в подробностях.

Если страница находится на устройстве выгрузки, вне памяти

(случай 1), это означает, что она когда-то располагалась в памя-

ти, но была выгружена оттуда "сборщиком" страниц. Обратившись к

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

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

осталась ли страница в кеше. Ядро корректирует запись таблицы

страниц так, чтобы она указывала на страницу, которую предполага-

ется считать в память, включает соответствующую запись таблицы

pfdata в хеш-очередь (облегчая последующую обработку отказа) и

считывает страницу с устройства выгрузки. Допустивший ошибку про-

цесс приостанавливается до момента завершения ввода-вывода; вмес-

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

держимого страницы.

Обратимся к Рисунку 9.22 и в качестве примера рассмотрим за-

пись таблицы страниц, связанную с виртуальным адресом 66К. Если

при обращении к странице процесс получает отказ из-за недоступ-

ности данных, программа обработки отказа обращается к дескриптору

дискового блока и обнаруживает то, что страница находится на уст-

ройстве выгрузки в блоке с номером 847 (если предположить, что в

системе только одно устройство выгрузки): следовательно, вирту-

альный адрес указан верно. Затем программа обработки отказа обра-

щается к кешу, но не находит информации о дисковом блоке с

номером 847. Таким образом, копия виртуальной страницы в памяти

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

устройства выгрузки. Ядро отводит физическую страницу с номером

1776 (Рисунок 9.23), считывает в нее с устройства выгрузки содер-

жимое виртуальной страницы и перенастраивает запись таблицы стра-

ниц на страницу с номером 1776. В завершение ядро корректирует

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

загружена, а также запись таблицы pfdata, отмечая, что на уст-

ройстве выгрузки в блоке с номером 847 содержится дубликат вирту-

альной страницы.

При обработке отказов из-за недоступности данных ядро не

всегда прибегает к выполнению операции ввода-вывода, даже когда

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

случае 2). Может случиться так, что ядро после выгрузки содержи-

мого физической страницы так и не переприсвоило ее или же ка-

кой-то иной процесс в результате отказа загрузил содержимое вир-

туальной страницы в другую физическую страницу. В любом случае

программа обработки отказа обнаруживает страницу в кеше, в ка-

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

Она перенастраивает соответствующую запись в таблице страниц на

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

лок на страницу и в случае необходимости убирает страницу из

списка свободных страниц. Предположим, к примеру, что процесс по-


Записи Дескрипторы

таблицы страниц дисковых блоков Страничные блоки


Физи-

ческая Диско-

Виртуаль- стра- Состо- Состо- Стра- вый Счет-

ный адрес ница яние яние Блок ница блок чик

------T--------TTT-------T---------┐ -----T------T----┐

0 │ │ │││ │ │ │ │ │ │

+-----+--------+++-------+---------+ │ │ │ │

1К │ 1648│ Недо- │││В файле│ 3 │ │ │ │ │

│ │ ступна │││ │ │ │ │ │ │

+-----+--------+++-------+---------+ │ │ │ │

2К │ │ │││ │ │ │ │ │ │

+-----+--------+++-------+---------+ │ │ │ │

3К │ Нет │ Недо- │││Заполня│ 5 │ │ │ │ │

│ │ ступна │││ется │ │ │ │ │ │

│ │ │││при об-│ │ │ │ │ │

│ │ │││ращении│ │ │ │ │ │

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

4К │ │ │││ │ │ │1036│ 387 │ 0 │

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

│ │ │││ │ │ │ │ │ │

│ │ │││ │ │ │ │ │ │

│ │ │││ │ │ │ │ │ │

│ │ │││ │ │ +----+------+----+

│ │ │││ │ │ │1648│ 1618 │ 1 │

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

64К │ 1917│ Недо- │││На дис-│ 1206 │ │ │ │ │

│ │ ступна │││ке │ │ │ │ │ │

+-----+--------+++-------+---------+ │ │ │ │

65К │ Нет │ Недо- │││Обнуля-│ │ │ │ │ │

│ │ ступна │││ется │ │ │ │ │ │

│ │ │││при об-│ │ │ │ │ │

│ │ │││ращении│ │ │ │ │ │

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

66К │ 1036│ Недо- │││На дис-│ 847 │ │1861│ 1206 │ 0 │

│ │ ступна │││ке │ │ +----+------+----+

+-----+--------+++-------+---------+ │ │ │ │

67К │ │ │││ │ │ │ │ │ │

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


Рисунок 9.22. Иллюстрация к отказу из-за недоступности данных


лучил отказ при обращении к виртуальному адресу 64К (Рисунок

9.22). Просматривая кеш, ядро устанавливает, что страничный блок

с номером 1861 связан с дисковым блоком 1206. Ядро перенастраива-

ет запись таблицы страниц с виртуальным адресом 64К на страницу с

номером 1861, устанавливает бит доступности и передает управление

программе обработки отказа. Таким образом, номер дискового блока

связывает вместе записи таблицы страниц и таблицы pfdata, чем и

объясняется его запоминание в обеих таблицах.

Как и ядру, программе обработки отказа не нужно считывать

страницу в память, если какой-то иной процесс уже получил отказ

по той же самой странице, но еще не полностью загрузил ее. Прог-

рамма находит область с записью таблицы страниц, которую она уже

ранее заблокировала. Она дожидается, пока будет закончен цикл об-

работки предыдущего отказа, после чего обнаруживает, что страница

стала доступной, и завершает свою работу. Эта процедура прослежи-

вается на Рисунке 9.24.


Записи Дескрипторы

таблицы страниц дисковых блоков Страничные блоки


Физи-

ческая Диско-

Виртуаль- стра- Состо- Состо- Стра- вый Счет-

ный адрес ница яние яние Блок ница блок чик

------T--------TTT-------T---------┐ -----T------T----┐

66К │ 1776│ Доступ-│││На дис-│ 847 │ │1776│ 847 │ 1 │

│ │ на │││ке │ │ │ │ │ │

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


Рисунок 9.23. Результат загрузки страницы в память


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

-------------------------------------------------------------

│ Отказ при обращении к стра-

│ нице

│ Виртуальный адрес страницы

│ верен

│ Приостанов до завершения

│ считывания страницы

│ Отказ при обращении к стра-

│ нице

│ Виртуальный адрес страницы

│ верен

│ Загрузка страницы в память

│ Приостанов до окончания

│ загрузки

│

│ Выход из приостанова --

│ страница в памяти

│ Страница помечается как

│ доступная

│ Выход из приостанова других

│ процессов

│ Выход из приостанова

│ Возобновление выполнения

│

│ Возобновление выполнения

│

│

│ Время

v


Рисунок 9.24. Два отказа на одной странице


Если копия страницы находится не на устройстве выгрузки, а в

исполняемом файле (случай 3), ядро загружает страницу из файла.

Программа обработки отказа обращается к дескриптору дискового

блока, ищет соответствующий номер логического блока внутри файла,

содержащего страницу, и индекс, ассоциированный с записью таблицы

областей. Номер логического блока используется программой в ка-

честве смещения внутри списка номеров дисковых блоков, присоеди-

ненного к индексу во время выполнения функции exec. По номеру

блока на диске программа считывает страницу в память. Так, напри-

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

1К, показывает, что содержимое страницы располагается в исполняе-

мом файле, внутри логического блока с номером 3 (см. Рисунок

9.22).

Если процесс получил отказ при обращении к странице, имеющей

пометку "заполняемая при обращении" или "обнуляемая при обраще-

нии" (случаи 4 и 5), ядро выделяет свободную страницу в памяти и

корректирует соответствующую запись таблицы страниц. Если страни-

ца "обнуляемая при обращении", ядро также очищает ее содержимое.

В завершение обработки флаги "заполняемая при обращении" и "обну-

ляемая при обращении" сбрасываются. Теперь страница находится в

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

на устройстве выгрузки, ни в файловой системе. Так происходит,

если процесс обращается к страницам с виртуальными адресами 3К и

65К (см. Рисунок 9.22): ни один из процессов не обращался к этим

страницам с тех пор, как файл был запущен на выполнение функцией

exec.

В завершение своей работы программа обработки отказов из-за

отсутствия (недоступности) данных устанавливает бит доступности

страницы и сбрасывает бит модификации. Приоритет процесса при

этом пересчитывается, ибо во время выполнения программы процесс

мог приостановить свое выполнение на уровне ядра, получая тем са-

мым по возвращении в режим задачи незаслуженное преимущество пе-

ред другими процессами. И, наконец, возвращаясь в режим задачи,

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

ления каких-либо сигналов.


9.2.3.2 Обработка прерываний по отказу системы защиты


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

является отказ системы защиты, который означает, что процесс об-

ратился к существующей странице памяти, но судя по разрядам, опи-

сывающим права доступа к странице, доступ к ней со стороны теку-

щего процесса не разрешен. (Вспомним пример, описывающий попытку

процесса произвести запись данных в область команд; см. Рисунок

7.22). Отказ данного типа имеет место также тогда, когда процесс

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

время выполнения системной функции fork был установлен бит копи-

рования при записи. Ядро должно различать между собой ситуации,

когда отказ произошел по причине того, что страница требует копи-

рования при записи, и когда имело место действительно что-то не-

допустимое.

Программа обработки отказа системы защиты автоматически полу-

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

поиск соответствующей области и записи таблицы страниц (Рисунок

9.25). Она блокирует область, чтобы "сборщик" страниц не мог выг-

рузить страницу, пока связанный с ней отказ не будет обработан.

Если программа обработки отказа устанавливает, что причиной отка-

за послужила установка бита копирования при записи, и если стра-

ницу используют сразу несколько процессов, ядро выделяет в памяти

новую страницу и копирует в нее содержимое старой страницы; ссыл-

ки других процессов на старую страницу сохраняют свое значение.

После копирования и внесения в запись таблицы страниц нового но-

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

таблицы pfdata, соответствующей старой странице. Вся процедура

показана на Рисунке 9.26, где три процесса совместно используют

физическую страницу с номером 828. Процесс B считывает страницу,

но поскольку бит копирования при записи установлен, получает от-

каз системы защиты. Программа обработки отказа выделяет страницу

с номером 786, копирует в нее содержимое страницы 828, уменьшает

значение счетчика ссылок на скопированную страницу и перенастраи-

вает соответствующую запись таблицы страниц на страницу с номером

786.

Если бит копирования при записи установлен, но страница ис-

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

воспользоваться физической страницей повторно. Оно отключает бит

копирования при записи и разрывает связь страницы с ее копией на

диске (если таковая существует), поскольку не исключена возмож-


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

ядро убирает запись таблицы pfdata из очереди страниц, ибо новая


-------------------------------------------------------------┐

│ алгоритм pfault /* обработка отказа системы защиты */ │

│ входная информация: адрес, по которому получен отказ │

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

│ { │

│ найти область, запись в таблице страниц, дескриптор дис-│

│ кового блока, связанные с адресом, по которому получен │

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

│ если (страница недоступна в памяти) │

│ перейти на out; │

│ если (бит копирования при записи не установлен) │

│ перейти на out; /* программная ошибка - сигнал */│

│ если (счетчик ссылок на страничный блок > 1) │

│ { │

│ выделить новую физическую страницу; │

│ скопировать в нее содержимое старой страницы; │

│ уменьшить значение счетчика ссылок на старый стра- │

│ ничный блок; │

│ перенастроить запись таблицы страниц на новую физи- │

│ ческую страницу; │

│ } │

│ в противном случае /* убрать страницу, поскольку она │

│ * никем больше не используется */ │

│ { │

│ если (копия страницы имеется на устройстве выгрузки)│

│ освободить место на устройстве, разорвать связь│

│ со страницей; │

│ если (страница находится в хеш-очереди страниц) │

│ убрать страницу из хеш-очереди; │

│ } │

│ в записи таблицы страниц установить бит модификации, │

│ сбросить бит копирования при записи; │

│ пересчитать приоритет процесса; │

│ проверить, не поступали ли сигналы; │

│ out: снять блокировку с области; │

│ } │

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


Рисунок 9.25. Алгоритм обработки отказа системы защиты


копия виртуальной страницы располагается не на устройстве выгруз-

ки. Кроме того, ядро уменьшает значение счетчика ссылок на стра-

ницу в таблице использования области подкачки, и если это значе-

ние становится равным 0, освобождает место на устройстве (см.

упражнение 9.11).

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

недоступна, и ее бит копирования при записи установлен, выступая

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

ращении к странице сначала обрабатывает отказ из-за недоступности

данных (обратная очередность рассматривается в упражнении 9.17).

Несмотря на это, программа обработки отказа системы защиты все

равно обязана убедиться в доступности страницы, поскольку при ус-

тановке блокировки на область программа может приостановиться, а

"сборщик" страниц тем временем может выгрузить страницу из памя-

ти. Если страница недоступна (бит доступности сброшен), программа

немедленно завершит работу и процесс получит отказ из-за недос-

тупности данных. Ядро обработает этот отказ, но процесс вновь по-

лучит отказ системы защиты. Более чем вероятно, что заключитель-

ный отказ системы защиты будет обработан без каких-либо препятс-

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

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

памяти. Описанная последовательность событий показана на Рисунке