Страница:
несмежными. "Сборщик" сохраняет оставшиеся 12 страниц процесса D в списке
выгружаемых страниц, но не выгружает их до тех пор, пока список не будет за-
полнен до конца. Как только у процессов возникает потребность в подкачке
страниц с устройства выгрузки или если страницы больше не нужны использующим
их процессам (процессы завершились), в области выгрузки освобождается место.
Чтобы подвести итог, выделим в процессе откачки страницы из памяти две
фазы. На первой фазе "сборщик" страниц ищет страницы, подходящие для выгруз-
ки, и помещает их номера в список выгружаемых страниц. На второй фазе ядро
копирует страницу на устройство выгрузки (если на нем имеется место), сбра-
сывает в ноль бит допустимости в соответствующей записи таблицы страниц,
уменьшает значение счетчика ссылок в соответствующей записи таблицы pfdata
Страницы выгружаются группами по 64 страницы
+--------------------+ +-------------------+ +-------------------+
|Процесс A 30 стр-ц | |Процесс B 6 стр-ц | |Процесс D 12 стр-ц |
| | | | | - |
|Процесс B 34 стр-цы| |Процесс C 50 стр-ц| | - |
+--------------------+ | | | - |
- - |Процесс D 8 стр-ц | +-------------------+
- -+-------------------+
- - - -
- - - -
- - - -
- - - -
- - - -
+-------+-------------------+-------+-----------------+----------+
| | A 30 B 34 | | B 6 C 50 D 8 | |
+-------+-------------------+-------+-----------------+----------+
Устройство выгрузки
Рисунок 9.20. Выделение пространства на устройстве выгрузки в
системе с замещением страниц
и если оно становится равным 0, помещает эту запись в конец списка свободных
страниц. Содержимое физической страницы в памяти не изменяется до тех пор,
пока страница не будет переназначена другому процессу.
В системе встречаются два типа отказов при обращении к странице: отказы
из-за отсутствия (недоступности) данных и отказы системы защиты. Поскольку
программы обработки прерываний по отказу могут приостанавливать свое выпол-
нение на время считывания страницы с диска в память, эти программы являются
исключением из общего правила, утверждающего невозможность приостанова обра-
ботчиков прерываний. Тем не менее, поскольку программа обработки прерываний
277
по отказу приостанавливается в контексте процесса, породившего фатальную
ошибку памяти, отказ относится к текущему процессу; следовательно, процессы
приостанавливаются не произвольным образом.
Если процесс пытается обратиться к странице, бит доступности для которой
не установлен, он получает отказ из-за отсутствия (недоступности) данных и
ядро запускает программу обработки прерываний по отказу данного типа (Рису-
нок 9.21). Бит доступности не устанавливается ни для тех страниц, которые
располагаются за пределами виртуального адресного пространства процесса, ни
для тех, которые входят в состав этого пространства, но не имеют в настоящий
момент физического аналога в памяти. Фатальная ошибка памяти произошла в ре-
зультате обращения ядра по виртуальному адресу страницы, поэтому ядро выхо-
дит на соответствующую этой странице запись в таблице страниц и дескриптор
дискового блока. Чтобы предотвратить взаимную блокировку, которая может про-
изойти, если "сборщик" попытается выгрузить страницу из памяти, ядро фикси-
рует в памяти область с соответствующей записью таблицы страниц. Если в дес-
крипторе дискового блока отсутствует информация о странице,
сделанная ссылка на страницу является недопустимой и ядро посылает процес-
су-нарушителю сигнал о "нарушении сегментации" (см. Рисунок 7.25). Такой по-
рядок действий совпадает с тем порядком, которого придерживается ядро, когда
процесс обратился по неверному адресу, если не принимать во внимание то обс-
тоятельство, что ядро узнает об ошибке немедленно, так как все "доступные"
страницы являются резидентными в памяти. Если ссылка на страницу сделана
правильно, ядро выделяет физическую страницу в памяти и считывает в нее со-
держимое виртуальной страницы с устройства выгрузки или из исполняемого фай-
ла.
Страница, вызвавшая отказ, находится в одном из пяти состояний:
1. На устройстве выгрузки вне памяти.
2. В списке свободных страниц в памяти.
3. В исполняемом файле.
4. С пометкой "обнуляемая при обращении".
5. С пометкой "заполняемая при обращении".
Рассмотрим каждый случай в подробностях.
Если страница находится на устройстве выгрузки, вне памяти (случай 1),
это означает, что она когда-то располагалась в памяти, но была выгружена от-
туда "сборщиком" страниц. Обратившись к дескриптору дискового блока, ядро
узнает из него номера устройства выгрузки и блока, где расположена страница,
и проверяет, не осталась ли страница в кеше. Ядро корректирует запись табли-
цы страниц так, чтобы она указывала на страницу, которую предполагается счи-
тать в память, включает соответствующую запись таблицы pfdata в хеш-очередь
(облегчая последующую обработку отказа) и считывает страницу с устройства
выгрузки. Допустивший ошибку процесс приостанавливается до момента заверше-
ния ввода-вывода; вместе с ним будут возобновлены все процессы, ожидавшие
загрузки содержимого страницы.
Обратимся к Рисунку 9.22 и в качестве примера рассмотрим запись таблицы
страниц, связанную с виртуальным адресом 66К. Если при обращении к странице
процесс получает отказ из-за недоступности данных, программа обработки отка-
за обращается к дескриптору дискового блока и обнаруживает то, что страница
находится на устройстве выгрузки в блоке с номером 847 (если предположить,
что в системе только одно устройство выгрузки): следовательно, виртуальный
адрес указан верно. Затем программа обработки отказа обращается к кешу, но
не находит информации о дисковом блоке с номером 847. Таким образом, копия
виртуальной страницы в памяти отсутствует и программа обработки отказа долж-
на загрузить ее с устройства выгрузки. Ядро отводит физическую страницу с
номером 1776 (Рисунок 9.23), считывает в нее с устройства выгрузки содержи-
мое виртуальной страницы и перенастраивает запись таблицы страниц на страни-
цу с номером 1776. В завершение ядро корректирует дескриптор дискового бло-
278
+------------------------------------------------------------+
| алгоритм vfault /* обработка отказа из-за отсутствия |
| (недоступности) данных */ |
| входная информация: адрес, по которому получен отказ |
| выходная информация: отсутствует |
| { |
| найти область, запись в таблице страниц, дескриптор дис-|
| кового блока, связанные с адресом, по которому получен |
| отказ, заблокировать область; |
| если (адрес не принадлежит виртуальному адресному прост-|
| ранству процесса) |
| { |
| послать сигнал (SIGSEGV: нарушение сегментации) про- |
| цессу; |
| перейти на out; |
| } |
| если (адрес указан неверно) /* возможно, процесс нахо-|
| дился в состоянии при- |
| останова */ |
| перейти на out; |
| если (страница имеется в кеше) |
| { |
| убрать страницу из кеша; |
| поправить запись в таблице страниц; |
| выполнять пока (содержимое страницы не станет доступ-|
| ным) /* другой процесс получил такой же отказ, |
| * но раньше */ |
| приостановиться; |
| } |
| в противном случае /* страница отсутствует в кеше */|
| { |
| назначить области новую страницу; |
| |
| поместить новую страницу в кеш, откорректировать за- |
| пись в таблице pfdata; |
| если (страница ранее не загружалась в память и имеет |
| пометку "обнуляемая при обращении") |
| очистить содержимое страницы; |
| в противном случае |
| { |
| считать виртуальную страницу с устройства выгруз-|
| ки или из исполняемого файла; |
| приостановиться (до завершения ввода-вывода); |
| } |
| возобновить процессы (ожидающие загрузки содержимого |
| страницы); |
| } |
| установить бит доступности страницы; |
| сбросить бит модификации и "возраст" страницы; |
| пересчитать приоритет процесса; |
| out: снять блокировку с области; |
| } |
+------------------------------------------------------------+
Рисунок 9.21. Алгоритм обработки отказа из-за отсутствия (не-
доступности) данных
279
ка, делая указание о том, что страница загружена, а также запись таблицы
pfdata, отмечая, что на устройстве выгрузки в блоке с номером 847 содержится
дубликат виртуальной страницы.
При обработке отказов из-за недоступности данных ядро не всегда прибега-
ет к выполнению операции ввода-вывода, даже когда из дескриптора дискового
блока видно, что страница загружена (в случае 2). Может случиться так, что
ядро после выгрузки содержимого физической страницы так и не переприсвоило
ее или же какой-то иной процесс в результате отказа загрузил содержимое вир-
туальной страницы в другую физическую страницу. В любом случае программа об-
работки отказа обнаруживает страницу в кеше, в качестве ключа используя но-
мер блока в дескрипторе дискового блока. Она перенастраивает соответствующую
запись в таблице страниц на только что найденную страницу, увеличивает зна-
чение счетчика ссылок на страницу и в случае необходимости убирает страницу
из списка свободных страниц. Предположим, к примеру, что процесс по-
Записи Дескрипторы
таблицы страниц дисковых блоков Страничные блоки
Физи-
ческая Диско-
Виртуаль- стра- Состо- Состо- Стра- вый Счет-
ный адрес ница яние яние Блок ница блок чик
+-----+--------+++-------+---------+ +----+------+----+
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К | | ||| | | | | | |
+-----+--------+++-------+---------+ +----+------+----+
Рисунок 9.22. Иллюстрация к отказу из-за недоступности данных
280
лучил отказ при обращении к виртуальному адресу 64К (Рисунок 9.22). Просмат-
ривая кеш, ядро устанавливает, что страничный блок с номером 1861 связан с
дисковым блоком 1206. Ядро перенастраивает запись таблицы страниц с вирту-
альным адресом 64К на страницу с номером 1861, устанавливает бит доступности
и передает управление программе обработки отказа. Таким образом, номер дис-
кового блока связывает вместе записи таблицы страниц и таблицы pfdata, чем и
объясняется его запоминание в обеих таблицах.
Как и ядру, программе обработки отказа не нужно считывать страницу в па-
мять, если какой-то иной процесс уже получил отказ по той же самой странице,
но еще не полностью загрузил ее. Программа находит область с записью таблицы
Записи Дескрипторы
таблицы страниц дисковых блоков Страничные блоки
Физи-
ческая Диско-
Виртуаль- стра- Состо- Состо- Стра- вый Счет-
ный адрес ница яние яние Блок ница блок чик
+-----+--------+++-------+---------+ +----+------+----+
66К | 1776| Доступ-|||На дис-| 847 | |1776| 847 | 1 |
| | на |||ке | | | | | |
+-----+--------+++-------+---------+ +----+------+----+
Рисунок 9.23. Результат загрузки страницы в память
Процесс A Процесс B
+------------------------------------------------------------
| Отказ при обращении к стра- - -
| нице - -
| Виртуальный адрес страницы - -
| верен - -
| Приостанов до завершения - -
| считывания страницы - -
| - - Отказ при обращении к стра-
| - - нице
| - - Виртуальный адрес страницы
| - - верен
| - - Загрузка страницы в память
| - - Приостанов до окончания
| - - загрузки
| - - -
| Выход из приостанова -- - -
| страница в памяти - -
| Страница помечается как - -
| доступная - -
| Выход из приостанова других - -
| процессов - -
| - Выход из приостанова
| Возобновление выполнения - -
| - - -
| - - Возобновление выполнения
| - - -
| - - -
| Время -
v
Рисунок 9.24. Два отказа на одной странице
281
страниц, которую она уже ранее заблокировала. Она дожидается, пока будет за-
кончен цикл обработки предыдущего отказа, после чего обнаруживает, что стра-
ница стала доступной, и завершает свою работу. Эта процедура прослеживается
на Рисунке 9.24.
Если копия страницы находится не на устройстве выгрузки, а в исполняемом
файле (случай 3), ядро загружает страницу из файла. Программа обработки от-
каза обращается к дескриптору дискового блока, ищет соответствующий номер
логического блока внутри файла, содержащего страницу, и индекс, ассоцииро-
ванный с записью таблицы областей. Номер логического блока используется
программой в качестве смещения внутри списка номеров дисковых блоков, присо-
единенного к индексу во время выполнения функции exec. По номеру блока на
диске программа считывает страницу в память. Так, например, дескриптор дис-
кового блока, связанный с виртуальным адресом 1К, показывает, что содержимое
страницы располагается в исполняемом файле, внутри логического блока с номе-
ром 3 (см. Рисунок 9.22).
Если процесс получил отказ при обращении к странице, имеющей пометку
"заполняемая при обращении" или "обнуляемая при обращении" (случаи 4 и 5),
ядро выделяет свободную страницу в памяти и корректирует соответствующую за-
пись таблицы страниц. Если страница "обнуляемая при обращении", ядро также
очищает ее содержимое. В завершение обработки флаги "заполняемая при обраще-
нии" и "обнуляемая при обращении" сбрасываются. Теперь страница находится в
памяти, доступна процессам и ее содержимое не имеет аналогов ни на устройст-
ве выгрузки, ни в файловой системе. Так происходит, если процесс обращается
к страницам с виртуальными адресами 3К и 65К (см. Рисунок 9.22): ни один из
процессов не обращался к этим страницам с тех пор, как файл был запущен на
выполнение функцией exec.
В завершение своей работы программа обработки отказов из-за отсутствия
(недоступности) данных устанавливает бит доступности страницы и сбрасывает
бит модификации. Приоритет процесса при этом пересчитывается, ибо во время
выполнения программы процесс мог приостановить свое выполнение на уровне яд-
ра, получая тем самым по возвращении в режим задачи незаслуженное преимущес-
тво перед другими процессами. И, наконец, возвращаясь в режим задачи, прог-
рамма проверяет, не было ли за время обработки отказа поступления каких-либо
сигналов.
Вторым типом отказа, встречающегося при обращении к странице, является
отказ системы защиты, который означает, что процесс обратился к существующей
странице памяти, но судя по разрядам, описывающим права доступа к странице,
доступ к ней со стороны текущего процесса не разрешен. (Вспомним пример,
описывающий попытку процесса произвести запись данных в область команд; см.
Рисунок 7.22). Отказ данного типа имеет место также тогда, когда процесс
предпринимает попытку записать что-то на страницу, для которой во время вы-
полнения системной функции fork был установлен бит копирования при записи.
Ядро должно различать между собой ситуации, когда отказ произошел по причине
того, что страница требует копирования при записи, и когда имело место дейс-
твительно что-то недопустимое.
Программа обработки отказа системы защиты автоматически получает вирту-
альный адрес, по которому произошел отказ, и ведет поиск соответствующей об-
ласти и записи таблицы страниц (Рисунок 9.25). Она блокирует область, чтобы
"сборщик" страниц не мог выгрузить страницу, пока связанный с ней отказ не
будет обработан. Если программа обработки отказа устанавливает, что причиной
отказа послужила установка бита копирования при записи, и если страницу ис-
пользуют сразу несколько процессов, ядро выделяет в памяти новую страницу и
копирует в нее содержимое старой страницы; ссылки других процессов на старую
282
страницу сохраняют свое значение. После копирования и внесения в запись таб-
лицы страниц нового номера страницы ядро уменьшает значение счетчика ссылок
в записи таблицы pfdata, соответствующей старой странице. Вся процедура по-
казана на Рисунке 9.26, где три процесса совместно используют физическую
страницу с номером 828. Процесс B считывает страницу, но поскольку бит копи-
рования при записи установлен, получает отказ системы защиты. Программа об-
работки отказа выделяет страницу с номером 786, копирует в нее содержимое
страницы 828, уменьшает значение счетчика ссылок на скопированную страницу и
перенастраивает соответствующую запись таблицы страниц на страницу с номером
786.
Если бит копирования при записи установлен, но страница используется
только одним процессом, ядро дает процессу возможность воспользоваться физи-
ческой страницей повторно. Оно отключает бит копирования при записи и разры-
вает связь страницы с ее копией на диске (если таковая существует), посколь-
ку не исключена возможность того, что дисковой копией пользуются другие про-
цессы. Затем ядро убирает запись таблицы pfdata из очереди страниц, ибо но-
вая
+------------------------------------------------------------+
| алгоритм pfault /* обработка отказа системы защиты */ |
| входная информация: адрес, по которому получен отказ |
| выходная информация: отсутствует |
| { |
| найти область, запись в таблице страниц, дескриптор дис-|
| кового блока, связанные с адресом, по которому получен |
| отказ, заблокировать область; |
| если (страница недоступна в памяти) |
| перейти на out; |
| если (бит копирования при записи не установлен) |
| перейти на out; /* программная ошибка - сигнал */|
| если (счетчик ссылок на страничный блок > 1) |
| { |
| выделить новую физическую страницу; |
| скопировать в нее содержимое старой страницы; |
| уменьшить значение счетчика ссылок на старый стра- |
| ничный блок; |
| перенастроить запись таблицы страниц на новую физи- |
| ческую страницу; |
| } |
| в противном случае /* убрать страницу, поскольку она |
| * никем больше не используется */ |
| { |
| если (копия страницы имеется на устройстве выгрузки)|
| освободить место на устройстве, разорвать связь|
| со страницей; |
| если (страница находится в хеш-очереди страниц) |
| убрать страницу из хеш-очереди; |
| } |
| в записи таблицы страниц установить бит модификации, |
| сбросить бит копирования при записи; |
| пересчитать приоритет процесса; |
| проверить, не поступали ли сигналы; |
| out: снять блокировку с области; |
| } |
+------------------------------------------------------------+
Рисунок 9.25. Алгоритм обработки отказа системы защиты
283
копия виртуальной страницы располагается не на устройстве выгрузки. Кроме
того, ядро уменьшает значение счетчика ссылок на страницу в таблице исполь-
зования области подкачки, и если это значение становится равным 0, освобож-
дает место на устройстве (см. упражнение 9.11).
Если запись в таблице страниц указывает на то, что страница недоступна,
и ее бит копирования при записи установлен, выступая поводом для отказа сис-
темы защиты, допустим, что система при обращении к странице сначала обраба-
тывает отказ из-за недоступности данных (обратная очередность рассматривает-
ся в упражнении 9.17). Несмотря на это, программа обработки отказа системы
защиты все равно обязана убедиться в доступности страницы, поскольку при ус-
тановке блокировки на область программа может приостановиться, а "сборщик"
страниц тем временем может выгрузить страницу из памяти. Если страница не-
доступна (бит доступности сброшен), программа немедленно завершит работу и
процесс получит отказ из-за недоступности данных. Ядро обработает этот от-
каз, но процесс вновь получит отказ системы защиты. Более чем вероятно, что
заключительный отказ системы защиты будет обработан без каких-либо препятст-
вий и помех, поскольку пройдет довольно значительный период времени, прежде
чем страница достаточно "созреет" для выгрузки из памяти. Описанная последо-
вательность событий показана на Рисунке 9.27.
Запись таблицы страниц - Процесс A
+-----------------------------------------------+
| Страница 828: доступна, копируется при записи +-+
+-----------------------------------------------+ |
|
Запись таблицы страниц - Процесс B | +-----------+
+-----------------------------------------------+ +->| Страничный|
| Страница 828: доступна, копируется при записи +--->| блок 828 |
+-----------------------------------------------+ +->| Счетчик |
| | ссылок 3 |
Запись таблицы страниц - Процесс C | +-----------+
+-----------------------------------------------+ |
| Страница 828: доступна, копируется при записи +-+
+-----------------------------------------------+
(а) Перед тем, как процесс B получил отказ системы защиты
Запись таблицы страниц - Процесс A
+-----------------------------------------------+ +-----------+
| Страница 828: доступна, копируется при записи +-+ | Страничный|
+-----------------------------------------------+ | | блок 828 |
+->| Счетчик |
Запись таблицы страниц - Процесс B +->| ссылок 2 |
+-----------------------------------------------+ | +-----------+
| Страница 828: доступна ++|
+-----------------------------------------------+|| +-----------+
+|->| Страничный|
Запись таблицы страниц - Процесс C | | блок 786 |
+-----------------------------------------------+ | | Счетчик |
| Страница 828: доступна, копируется при записи +-+ | ссылок 1 |
+-----------------------------------------------+ +-----------+
(б) После запуска программы обработки отказа системы защиты
для процесса B
Рисунок 9.26. Отказ системы защиты из-за установки бита копи-
рования при записи
284
Перед завершением программа обработки отказа системы защиты устанавлива-
ет биты модификации и защиты, но сбрасывает бит копирования при записи. Она
пересчитывает приоритет процесса и проверяет, не поступали ли за время ее
работы сигналы, предназначенные процессу, в точности повторяя то, что дела-
ется по завершении обработки отказа из-за недопустимости данных.
Процесс, получающий отказы при
обращении к странице "Сборщик" страниц
+------------------------------------------------------------
| - -
| - Блокирует область
| - -
| Отказ системы защиты -
| Приостанов - область -
| заблокирована -
| - -
| - Выгрузка страницы - бит
| - допустимости сброшен
| - -
| - -
| - Выводит из приостанова
| - процессы, ожидающие
| - снятия с области
| - блокировки
| Выход из приостанова -
| - -
| - -
| Проверка бита доступ- -
| ности - сброшен -
| Выход из программы обра- -
| ботки отказа системы за- -
| щиты -
| - -
| - -
| Отказ из-за недоступ- -
| ности данных -
v
Время
Рисунок 9.27. Взаимодействие отказа системы защиты и отказа
выгружаемых страниц, но не выгружает их до тех пор, пока список не будет за-
полнен до конца. Как только у процессов возникает потребность в подкачке
страниц с устройства выгрузки или если страницы больше не нужны использующим
их процессам (процессы завершились), в области выгрузки освобождается место.
Чтобы подвести итог, выделим в процессе откачки страницы из памяти две
фазы. На первой фазе "сборщик" страниц ищет страницы, подходящие для выгруз-
ки, и помещает их номера в список выгружаемых страниц. На второй фазе ядро
копирует страницу на устройство выгрузки (если на нем имеется место), сбра-
сывает в ноль бит допустимости в соответствующей записи таблицы страниц,
уменьшает значение счетчика ссылок в соответствующей записи таблицы pfdata
Страницы выгружаются группами по 64 страницы
+--------------------+ +-------------------+ +-------------------+
|Процесс A 30 стр-ц | |Процесс B 6 стр-ц | |Процесс D 12 стр-ц |
| | | | | - |
|Процесс B 34 стр-цы| |Процесс C 50 стр-ц| | - |
+--------------------+ | | | - |
- - |Процесс D 8 стр-ц | +-------------------+
- -+-------------------+
- - - -
- - - -
- - - -
- - - -
- - - -
+-------+-------------------+-------+-----------------+----------+
| | A 30 B 34 | | B 6 C 50 D 8 | |
+-------+-------------------+-------+-----------------+----------+
Устройство выгрузки
Рисунок 9.20. Выделение пространства на устройстве выгрузки в
системе с замещением страниц
и если оно становится равным 0, помещает эту запись в конец списка свободных
страниц. Содержимое физической страницы в памяти не изменяется до тех пор,
пока страница не будет переназначена другому процессу.
В системе встречаются два типа отказов при обращении к странице: отказы
из-за отсутствия (недоступности) данных и отказы системы защиты. Поскольку
программы обработки прерываний по отказу могут приостанавливать свое выпол-
нение на время считывания страницы с диска в память, эти программы являются
исключением из общего правила, утверждающего невозможность приостанова обра-
ботчиков прерываний. Тем не менее, поскольку программа обработки прерываний
277
по отказу приостанавливается в контексте процесса, породившего фатальную
ошибку памяти, отказ относится к текущему процессу; следовательно, процессы
приостанавливаются не произвольным образом.
Если процесс пытается обратиться к странице, бит доступности для которой
не установлен, он получает отказ из-за отсутствия (недоступности) данных и
ядро запускает программу обработки прерываний по отказу данного типа (Рису-
нок 9.21). Бит доступности не устанавливается ни для тех страниц, которые
располагаются за пределами виртуального адресного пространства процесса, ни
для тех, которые входят в состав этого пространства, но не имеют в настоящий
момент физического аналога в памяти. Фатальная ошибка памяти произошла в ре-
зультате обращения ядра по виртуальному адресу страницы, поэтому ядро выхо-
дит на соответствующую этой странице запись в таблице страниц и дескриптор
дискового блока. Чтобы предотвратить взаимную блокировку, которая может про-
изойти, если "сборщик" попытается выгрузить страницу из памяти, ядро фикси-
рует в памяти область с соответствующей записью таблицы страниц. Если в дес-
крипторе дискового блока отсутствует информация о странице,
сделанная ссылка на страницу является недопустимой и ядро посылает процес-
су-нарушителю сигнал о "нарушении сегментации" (см. Рисунок 7.25). Такой по-
рядок действий совпадает с тем порядком, которого придерживается ядро, когда
процесс обратился по неверному адресу, если не принимать во внимание то обс-
тоятельство, что ядро узнает об ошибке немедленно, так как все "доступные"
страницы являются резидентными в памяти. Если ссылка на страницу сделана
правильно, ядро выделяет физическую страницу в памяти и считывает в нее со-
держимое виртуальной страницы с устройства выгрузки или из исполняемого фай-
ла.
Страница, вызвавшая отказ, находится в одном из пяти состояний:
1. На устройстве выгрузки вне памяти.
2. В списке свободных страниц в памяти.
3. В исполняемом файле.
4. С пометкой "обнуляемая при обращении".
5. С пометкой "заполняемая при обращении".
Рассмотрим каждый случай в подробностях.
Если страница находится на устройстве выгрузки, вне памяти (случай 1),
это означает, что она когда-то располагалась в памяти, но была выгружена от-
туда "сборщиком" страниц. Обратившись к дескриптору дискового блока, ядро
узнает из него номера устройства выгрузки и блока, где расположена страница,
и проверяет, не осталась ли страница в кеше. Ядро корректирует запись табли-
цы страниц так, чтобы она указывала на страницу, которую предполагается счи-
тать в память, включает соответствующую запись таблицы pfdata в хеш-очередь
(облегчая последующую обработку отказа) и считывает страницу с устройства
выгрузки. Допустивший ошибку процесс приостанавливается до момента заверше-
ния ввода-вывода; вместе с ним будут возобновлены все процессы, ожидавшие
загрузки содержимого страницы.
Обратимся к Рисунку 9.22 и в качестве примера рассмотрим запись таблицы
страниц, связанную с виртуальным адресом 66К. Если при обращении к странице
процесс получает отказ из-за недоступности данных, программа обработки отка-
за обращается к дескриптору дискового блока и обнаруживает то, что страница
находится на устройстве выгрузки в блоке с номером 847 (если предположить,
что в системе только одно устройство выгрузки): следовательно, виртуальный
адрес указан верно. Затем программа обработки отказа обращается к кешу, но
не находит информации о дисковом блоке с номером 847. Таким образом, копия
виртуальной страницы в памяти отсутствует и программа обработки отказа долж-
на загрузить ее с устройства выгрузки. Ядро отводит физическую страницу с
номером 1776 (Рисунок 9.23), считывает в нее с устройства выгрузки содержи-
мое виртуальной страницы и перенастраивает запись таблицы страниц на страни-
цу с номером 1776. В завершение ядро корректирует дескриптор дискового бло-
278
+------------------------------------------------------------+
| алгоритм vfault /* обработка отказа из-за отсутствия |
| (недоступности) данных */ |
| входная информация: адрес, по которому получен отказ |
| выходная информация: отсутствует |
| { |
| найти область, запись в таблице страниц, дескриптор дис-|
| кового блока, связанные с адресом, по которому получен |
| отказ, заблокировать область; |
| если (адрес не принадлежит виртуальному адресному прост-|
| ранству процесса) |
| { |
| послать сигнал (SIGSEGV: нарушение сегментации) про- |
| цессу; |
| перейти на out; |
| } |
| если (адрес указан неверно) /* возможно, процесс нахо-|
| дился в состоянии при- |
| останова */ |
| перейти на out; |
| если (страница имеется в кеше) |
| { |
| убрать страницу из кеша; |
| поправить запись в таблице страниц; |
| выполнять пока (содержимое страницы не станет доступ-|
| ным) /* другой процесс получил такой же отказ, |
| * но раньше */ |
| приостановиться; |
| } |
| в противном случае /* страница отсутствует в кеше */|
| { |
| назначить области новую страницу; |
| |
| поместить новую страницу в кеш, откорректировать за- |
| пись в таблице pfdata; |
| если (страница ранее не загружалась в память и имеет |
| пометку "обнуляемая при обращении") |
| очистить содержимое страницы; |
| в противном случае |
| { |
| считать виртуальную страницу с устройства выгруз-|
| ки или из исполняемого файла; |
| приостановиться (до завершения ввода-вывода); |
| } |
| возобновить процессы (ожидающие загрузки содержимого |
| страницы); |
| } |
| установить бит доступности страницы; |
| сбросить бит модификации и "возраст" страницы; |
| пересчитать приоритет процесса; |
| out: снять блокировку с области; |
| } |
+------------------------------------------------------------+
Рисунок 9.21. Алгоритм обработки отказа из-за отсутствия (не-
доступности) данных
279
ка, делая указание о том, что страница загружена, а также запись таблицы
pfdata, отмечая, что на устройстве выгрузки в блоке с номером 847 содержится
дубликат виртуальной страницы.
При обработке отказов из-за недоступности данных ядро не всегда прибега-
ет к выполнению операции ввода-вывода, даже когда из дескриптора дискового
блока видно, что страница загружена (в случае 2). Может случиться так, что
ядро после выгрузки содержимого физической страницы так и не переприсвоило
ее или же какой-то иной процесс в результате отказа загрузил содержимое вир-
туальной страницы в другую физическую страницу. В любом случае программа об-
работки отказа обнаруживает страницу в кеше, в качестве ключа используя но-
мер блока в дескрипторе дискового блока. Она перенастраивает соответствующую
запись в таблице страниц на только что найденную страницу, увеличивает зна-
чение счетчика ссылок на страницу и в случае необходимости убирает страницу
из списка свободных страниц. Предположим, к примеру, что процесс по-
Записи Дескрипторы
таблицы страниц дисковых блоков Страничные блоки
Физи-
ческая Диско-
Виртуаль- стра- Состо- Состо- Стра- вый Счет-
ный адрес ница яние яние Блок ница блок чик
+-----+--------+++-------+---------+ +----+------+----+
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К | | ||| | | | | | |
+-----+--------+++-------+---------+ +----+------+----+
Рисунок 9.22. Иллюстрация к отказу из-за недоступности данных
280
лучил отказ при обращении к виртуальному адресу 64К (Рисунок 9.22). Просмат-
ривая кеш, ядро устанавливает, что страничный блок с номером 1861 связан с
дисковым блоком 1206. Ядро перенастраивает запись таблицы страниц с вирту-
альным адресом 64К на страницу с номером 1861, устанавливает бит доступности
и передает управление программе обработки отказа. Таким образом, номер дис-
кового блока связывает вместе записи таблицы страниц и таблицы pfdata, чем и
объясняется его запоминание в обеих таблицах.
Как и ядру, программе обработки отказа не нужно считывать страницу в па-
мять, если какой-то иной процесс уже получил отказ по той же самой странице,
но еще не полностью загрузил ее. Программа находит область с записью таблицы
Записи Дескрипторы
таблицы страниц дисковых блоков Страничные блоки
Физи-
ческая Диско-
Виртуаль- стра- Состо- Состо- Стра- вый Счет-
ный адрес ница яние яние Блок ница блок чик
+-----+--------+++-------+---------+ +----+------+----+
66К | 1776| Доступ-|||На дис-| 847 | |1776| 847 | 1 |
| | на |||ке | | | | | |
+-----+--------+++-------+---------+ +----+------+----+
Рисунок 9.23. Результат загрузки страницы в память
Процесс A Процесс B
+------------------------------------------------------------
| Отказ при обращении к стра- - -
| нице - -
| Виртуальный адрес страницы - -
| верен - -
| Приостанов до завершения - -
| считывания страницы - -
| - - Отказ при обращении к стра-
| - - нице
| - - Виртуальный адрес страницы
| - - верен
| - - Загрузка страницы в память
| - - Приостанов до окончания
| - - загрузки
| - - -
| Выход из приостанова -- - -
| страница в памяти - -
| Страница помечается как - -
| доступная - -
| Выход из приостанова других - -
| процессов - -
| - Выход из приостанова
| Возобновление выполнения - -
| - - -
| - - Возобновление выполнения
| - - -
| - - -
| Время -
v
Рисунок 9.24. Два отказа на одной странице
281
страниц, которую она уже ранее заблокировала. Она дожидается, пока будет за-
кончен цикл обработки предыдущего отказа, после чего обнаруживает, что стра-
ница стала доступной, и завершает свою работу. Эта процедура прослеживается
на Рисунке 9.24.
Если копия страницы находится не на устройстве выгрузки, а в исполняемом
файле (случай 3), ядро загружает страницу из файла. Программа обработки от-
каза обращается к дескриптору дискового блока, ищет соответствующий номер
логического блока внутри файла, содержащего страницу, и индекс, ассоцииро-
ванный с записью таблицы областей. Номер логического блока используется
программой в качестве смещения внутри списка номеров дисковых блоков, присо-
единенного к индексу во время выполнения функции exec. По номеру блока на
диске программа считывает страницу в память. Так, например, дескриптор дис-
кового блока, связанный с виртуальным адресом 1К, показывает, что содержимое
страницы располагается в исполняемом файле, внутри логического блока с номе-
ром 3 (см. Рисунок 9.22).
Если процесс получил отказ при обращении к странице, имеющей пометку
"заполняемая при обращении" или "обнуляемая при обращении" (случаи 4 и 5),
ядро выделяет свободную страницу в памяти и корректирует соответствующую за-
пись таблицы страниц. Если страница "обнуляемая при обращении", ядро также
очищает ее содержимое. В завершение обработки флаги "заполняемая при обраще-
нии" и "обнуляемая при обращении" сбрасываются. Теперь страница находится в
памяти, доступна процессам и ее содержимое не имеет аналогов ни на устройст-
ве выгрузки, ни в файловой системе. Так происходит, если процесс обращается
к страницам с виртуальными адресами 3К и 65К (см. Рисунок 9.22): ни один из
процессов не обращался к этим страницам с тех пор, как файл был запущен на
выполнение функцией exec.
В завершение своей работы программа обработки отказов из-за отсутствия
(недоступности) данных устанавливает бит доступности страницы и сбрасывает
бит модификации. Приоритет процесса при этом пересчитывается, ибо во время
выполнения программы процесс мог приостановить свое выполнение на уровне яд-
ра, получая тем самым по возвращении в режим задачи незаслуженное преимущес-
тво перед другими процессами. И, наконец, возвращаясь в режим задачи, прог-
рамма проверяет, не было ли за время обработки отказа поступления каких-либо
сигналов.
Вторым типом отказа, встречающегося при обращении к странице, является
отказ системы защиты, который означает, что процесс обратился к существующей
странице памяти, но судя по разрядам, описывающим права доступа к странице,
доступ к ней со стороны текущего процесса не разрешен. (Вспомним пример,
описывающий попытку процесса произвести запись данных в область команд; см.
Рисунок 7.22). Отказ данного типа имеет место также тогда, когда процесс
предпринимает попытку записать что-то на страницу, для которой во время вы-
полнения системной функции fork был установлен бит копирования при записи.
Ядро должно различать между собой ситуации, когда отказ произошел по причине
того, что страница требует копирования при записи, и когда имело место дейс-
твительно что-то недопустимое.
Программа обработки отказа системы защиты автоматически получает вирту-
альный адрес, по которому произошел отказ, и ведет поиск соответствующей об-
ласти и записи таблицы страниц (Рисунок 9.25). Она блокирует область, чтобы
"сборщик" страниц не мог выгрузить страницу, пока связанный с ней отказ не
будет обработан. Если программа обработки отказа устанавливает, что причиной
отказа послужила установка бита копирования при записи, и если страницу ис-
пользуют сразу несколько процессов, ядро выделяет в памяти новую страницу и
копирует в нее содержимое старой страницы; ссылки других процессов на старую
282
страницу сохраняют свое значение. После копирования и внесения в запись таб-
лицы страниц нового номера страницы ядро уменьшает значение счетчика ссылок
в записи таблицы pfdata, соответствующей старой странице. Вся процедура по-
казана на Рисунке 9.26, где три процесса совместно используют физическую
страницу с номером 828. Процесс B считывает страницу, но поскольку бит копи-
рования при записи установлен, получает отказ системы защиты. Программа об-
работки отказа выделяет страницу с номером 786, копирует в нее содержимое
страницы 828, уменьшает значение счетчика ссылок на скопированную страницу и
перенастраивает соответствующую запись таблицы страниц на страницу с номером
786.
Если бит копирования при записи установлен, но страница используется
только одним процессом, ядро дает процессу возможность воспользоваться физи-
ческой страницей повторно. Оно отключает бит копирования при записи и разры-
вает связь страницы с ее копией на диске (если таковая существует), посколь-
ку не исключена возможность того, что дисковой копией пользуются другие про-
цессы. Затем ядро убирает запись таблицы pfdata из очереди страниц, ибо но-
вая
+------------------------------------------------------------+
| алгоритм pfault /* обработка отказа системы защиты */ |
| входная информация: адрес, по которому получен отказ |
| выходная информация: отсутствует |
| { |
| найти область, запись в таблице страниц, дескриптор дис-|
| кового блока, связанные с адресом, по которому получен |
| отказ, заблокировать область; |
| если (страница недоступна в памяти) |
| перейти на out; |
| если (бит копирования при записи не установлен) |
| перейти на out; /* программная ошибка - сигнал */|
| если (счетчик ссылок на страничный блок > 1) |
| { |
| выделить новую физическую страницу; |
| скопировать в нее содержимое старой страницы; |
| уменьшить значение счетчика ссылок на старый стра- |
| ничный блок; |
| перенастроить запись таблицы страниц на новую физи- |
| ческую страницу; |
| } |
| в противном случае /* убрать страницу, поскольку она |
| * никем больше не используется */ |
| { |
| если (копия страницы имеется на устройстве выгрузки)|
| освободить место на устройстве, разорвать связь|
| со страницей; |
| если (страница находится в хеш-очереди страниц) |
| убрать страницу из хеш-очереди; |
| } |
| в записи таблицы страниц установить бит модификации, |
| сбросить бит копирования при записи; |
| пересчитать приоритет процесса; |
| проверить, не поступали ли сигналы; |
| out: снять блокировку с области; |
| } |
+------------------------------------------------------------+
Рисунок 9.25. Алгоритм обработки отказа системы защиты
283
копия виртуальной страницы располагается не на устройстве выгрузки. Кроме
того, ядро уменьшает значение счетчика ссылок на страницу в таблице исполь-
зования области подкачки, и если это значение становится равным 0, освобож-
дает место на устройстве (см. упражнение 9.11).
Если запись в таблице страниц указывает на то, что страница недоступна,
и ее бит копирования при записи установлен, выступая поводом для отказа сис-
темы защиты, допустим, что система при обращении к странице сначала обраба-
тывает отказ из-за недоступности данных (обратная очередность рассматривает-
ся в упражнении 9.17). Несмотря на это, программа обработки отказа системы
защиты все равно обязана убедиться в доступности страницы, поскольку при ус-
тановке блокировки на область программа может приостановиться, а "сборщик"
страниц тем временем может выгрузить страницу из памяти. Если страница не-
доступна (бит доступности сброшен), программа немедленно завершит работу и
процесс получит отказ из-за недоступности данных. Ядро обработает этот от-
каз, но процесс вновь получит отказ системы защиты. Более чем вероятно, что
заключительный отказ системы защиты будет обработан без каких-либо препятст-
вий и помех, поскольку пройдет довольно значительный период времени, прежде
чем страница достаточно "созреет" для выгрузки из памяти. Описанная последо-
вательность событий показана на Рисунке 9.27.
Запись таблицы страниц - Процесс A
+-----------------------------------------------+
| Страница 828: доступна, копируется при записи +-+
+-----------------------------------------------+ |
|
Запись таблицы страниц - Процесс B | +-----------+
+-----------------------------------------------+ +->| Страничный|
| Страница 828: доступна, копируется при записи +--->| блок 828 |
+-----------------------------------------------+ +->| Счетчик |
| | ссылок 3 |
Запись таблицы страниц - Процесс C | +-----------+
+-----------------------------------------------+ |
| Страница 828: доступна, копируется при записи +-+
+-----------------------------------------------+
(а) Перед тем, как процесс B получил отказ системы защиты
Запись таблицы страниц - Процесс A
+-----------------------------------------------+ +-----------+
| Страница 828: доступна, копируется при записи +-+ | Страничный|
+-----------------------------------------------+ | | блок 828 |
+->| Счетчик |
Запись таблицы страниц - Процесс B +->| ссылок 2 |
+-----------------------------------------------+ | +-----------+
| Страница 828: доступна ++|
+-----------------------------------------------+|| +-----------+
+|->| Страничный|
Запись таблицы страниц - Процесс C | | блок 786 |
+-----------------------------------------------+ | | Счетчик |
| Страница 828: доступна, копируется при записи +-+ | ссылок 1 |
+-----------------------------------------------+ +-----------+
(б) После запуска программы обработки отказа системы защиты
для процесса B
Рисунок 9.26. Отказ системы защиты из-за установки бита копи-
рования при записи
284
Перед завершением программа обработки отказа системы защиты устанавлива-
ет биты модификации и защиты, но сбрасывает бит копирования при записи. Она
пересчитывает приоритет процесса и проверяет, не поступали ли за время ее
работы сигналы, предназначенные процессу, в точности повторяя то, что дела-
ется по завершении обработки отказа из-за недопустимости данных.
Процесс, получающий отказы при
обращении к странице "Сборщик" страниц
+------------------------------------------------------------
| - -
| - Блокирует область
| - -
| Отказ системы защиты -
| Приостанов - область -
| заблокирована -
| - -
| - Выгрузка страницы - бит
| - допустимости сброшен
| - -
| - -
| - Выводит из приостанова
| - процессы, ожидающие
| - снятия с области
| - блокировки
| Выход из приостанова -
| - -
| - -
| Проверка бита доступ- -
| ности - сброшен -
| Выход из программы обра- -
| ботки отказа системы за- -
| щиты -
| - -
| - -
| Отказ из-за недоступ- -
| ности данных -
v
Время
Рисунок 9.27. Взаимодействие отказа системы защиты и отказа