Страница:
выделяет страницы из этого списка по вышеназванному принципу замещения "ста-
риков". Ядро выстраивает записи таблицы в хеш-очередь в соответствии с номе-
ром устройства (выгрузки) и номером блока. Используя эти номера, ядро может
быстро отыскать страницу, если она находится в памяти. Передавая физическую
страницу области, ядро выбирает соответствующую запись из списка свободных
страниц, исправляет указанные в ней номера устройства и блока и помещает ее
в соответствующее место хеш-очереди.
Каждая запись таблицы использования области подкачки соответствует стра-
нице, находящейся на устройстве выгрузки. Запись содержит счетчик ссылок,
показывающий количество записей таблицы страниц, в которых имеется ссылка на
текущую страницу.
На Рисунке 9.14 показана взаимосвязь между записями таблицы страниц,
дескрипторами дисковых блоков, записями таблицы pfdata и таблицы использова-
ния области подкачки. Виртуальный адрес 1493К отображается на запись таблицы
страниц, соответствующую странице с физическим номером 794; дескриптор дис-
кового блока, связанный с этой записью, свидетельствует о том, что содержи-
мое страницы располагается на устройстве выгрузки с номером 1 в дисковом
блоке с номером 2743. Запись таблицы pfdata, помимо того, что указывает на
те же номера устройства и блока, сообщает, что счетчик ссылок на физическую
страницу имеет значение, равное 1. О том, почему номер дискового блока дуб-
лируется в записи таблицы pfdata, вы узнаете из раздела 9.2.4.1. Счетчик
ссылок на виртуальную страницу (в записи таблицы использования области под-
качки) свидетельствует о том, что на копию страницы на устройстве выгрузки
269
ссылается только одна запись таблицы страниц.
Как уже говорилось в разделе 7.1, во время выполнения функции fork ядро
создает копию каждой области родительского процесса и присоединяет ее к про-
цессу-потомку. В системе с замещением стра-
+-----------------------+--------------------------+
Виртуальный |Запись таблицы страниц|Дескриптор дискового блока|
адрес +-----------------------+--------------------------+
1493К | Номер страницы 794 | Устройство 1 Блок 2743 |
+---+-+-----------------+--------------------+-----+
| | |
| | Запись таблицы pfdata, |
| | соответствующая стра- +------------+
+------------+ v нице с номером 794 |
| +------------+-----------------------+ |
| | | Счетчик ссылок 1 | | Запись таблицы
| | +-----------------------+ | использования
| | | Номер устройства 1 | | области подкачки
| | +-----------------------+ | +-----------------+
| | | Номер блока 2743 | | |Счетчик ссылок 1|
| | +-----------------+-----+ | +--------+--------+
| | | +-----+ |
| | | | +--------------+
v v v v v
+--------------------------+ +---------------------------+
| Физическая страница 794 | | Номер блока 2743 |
+--------------------------+ +---------------------------+
Рисунок 9.14. Взаимосвязь между структурами данных, участвующими в реа-
лизации механизма замещения страниц по обращению
ниц ядро по традиции создает физическую копию адресного пространства процес-
са-родителя, что в общем случае является довольно расточительной операцией,
поскольку процесс часто после выполнения функции fork обращается к функции
exec и незамедлительно освобождает только что скопированное пространство.
Если область разделяемая, в версии V вместо копирования страницы ядро просто
увеличивает значение счетчика ссылок на область (в таблице областей, в таб-
лице страниц и в таблице pfdata). Тем не менее, для частных областей, таких
как область данных и стека, ядро отводит в таблице областей и таблице стра-
ниц новую запись, после чего просматривает в таблице страниц все записи про-
цесса-родителя: если запись верна, ядро увеличивает значение счетчика ссылок
в таблице pfdata, отражающее количество процессов, использующих страницу че-
рез разные области (в отличие от тех процессов, которые используют данную
страницу через разделяемую область). Если страница располагается на устройс-
тве выгрузки, ядро увеличивает значение счетчика ссылок в таблице использо-
вания области подкачки.
Теперь на страницу могут ссылаться обе области, использующие эту страни-
цу совместно, пока процесс не ведет на нее запись. Как только страница пона-
добится процессу для записи, ядро создаст ее копию, с тем, чтобы у каждой
области была своя личная версия страницы. Для этого при выполнении функции
fork в каждой записи таблицы страниц, соответствующей частным областям роди-
теля и потомка, ядро устанавливает бит "копирования при записи". Если один
из процессов попытается что-то записать на страницу, он получит отказ систе-
мы защиты, после чего для него будет создана новая копия содержимого страни-
цы. Таким образом, физическое копирование страницы откладывается до того мо-
270
мента, когда в этом возникнет реальная потребность.
В качестве примера рассмотрим Рисунок 9.15. Процессы разделяют доступ к
таблице страниц совместно используемой области команд T, поэтому значение
счетчика ссылок на область равно 2, а на страницы области единице (в таблице
pfdata). Ядро назначает про-
Процесс-родитель Процесс-потомок
Частная таблица Частная таблица
областей процесса областей процесса
+--------------+ +--------------+
| - | | - |
+--------------+ +--------------+
| - - | | - - |
+--------------+ +--------------+
- + ---------------------+ -
- - - -
v v v v
+-------------------+ +-------------------+ +-------------------+
| Область T | | Область P1 | | Область C1 |
| Счетчик ссылок 2 | | Счетчик ссылок 1 | | Счетчик ссылок 1 |
|+-----------------+| |+-----------------+| |+-----------------+|
|| Записи таблицы || || Записи таблицы || || Записи таблицы ||
|| страниц || || страниц || || страниц ||
|+-----------------+| |+-----------------+| |+-----------------+|
|| - || || - || || - ||
|| - || || - || || - ||
|+-----------------+| || - || || - ||
||Виртуаль- Стра-|| || - || || - ||
||ный адрес ница || || - || || - ||
|| 24К 967 || || - || || - ||
|+-----------------+| |+-----------------+| |+-----------------+|
|| - - || ||Виртуаль- Стра-|| ||Виртуаль- Стра-||
|| - - || ||ный адрес ница || ||ный адрес ница ||
|| - - || || 97К 613 || || 97К 613 ||
|| - - || |+-----------------+| |+-----------------+|
|| - - || || - - || || - - ||
|| - - || || - - || || - - ||
|+-----------------+| |+-----------------+| |+-----------------+|
+-------------------+ +-------------------+ +-------------------+
- - -----------
v v v
+---------------------+ +---------------------+
| Страничный блок 967 | | Страничный блок 613 |
| Счетчик ссылок 1 | | Счетчик ссылок 2 |
+---------------------+ +---------------------+
Рисунок 9.15. Адресация страниц, участвующих в процессе вы-
полнения функции fork
цессу-потомку новую область данных C1, являющуюся копией области P1 процес-
са-родителя. Обе области используют одни и те же записи таблицы страниц, это
видно на примере страницы с виртуальным адресом 97К. Этой странице в таблице
pfdata соответствует запись с номером 613, счетчик ссылок в которой равен 2,
ибо на страницу ссылаются две области.
В ходе выполнения функции fork в системе BSD создается физическая копия
страниц родительского процесса. Однако, учитывая наличие ситуаций, в которых
создание физической копии не является обязательным, в системе BSD существует
271
также функция vfork, которая используется в том случае, если процесс сразу
по завершении функции fork собирается запустить функцию exec. Функция vfork
не копирует таблицы страниц, поэтому она работает быстрее, чем функция fork
в версии V системы UNIX. Однако процесс-потомок при этом исполняется в тех
же самых физических адресах, что и его родитель, и может поэтому затереть
данные и стек родительского процесса. Если программист использует функцию
vfork неверно, может возникнуть опасная ситуация, поэтому вся ответствен-
ность за ее использование возлагается на программиста. Различие в подходах к
рассматриваемому вопросу в системах UNIX и BSD имеет философский характер,
они дают разный ответ на один и тот же вопрос: следует ли ядру скрывать осо-
бенности реализации своих функций, превращая их в тайну для пользователей,
или же стоит дать опытным пользователям возможность повысить эффективность
выполнения системных операций ?
+------------------------------------------------------------+
| int global; |
| main() |
| { |
| int local; |
| |
| local = 1; |
| if (vfork() == 0) |
| { |
| /* потомок */ |
| global = 2; /* запись в область данных родителя */|
| local = 3; /* запись в стек родителя */ |
| _exit(); |
| } |
| printf("global %d local %d\n",global,local); |
| } |
+------------------------------------------------------------+
Рисунок 9.16. Функция vfork и искажение информации процесса
В качестве примера рассмотрим программу, приведенную на Рисунке 9.16.
После выполнения функции vfork процесс-потомок не запускает функцию exec, а
переустанавливает значения переменных global и local и завершается (****).
Система гарантирует, что процесс-родитель приостанавливается до того момен-
та, когда потомок исполнит функции exec или exit. Возобновив в конечном ито-
ге свое выполнение, процесс-родитель обнаружит, что значения двух его пере-
менных не совпадают с теми значениями, которые были у них до обращения к
функции vfork ! Еще больший эффект может произвести возвращение процесса-по-
томка из функции, вызвавшей функцию vfork (см. упражнение 9.8).
Как уже говорилось в главе 7, когда процесс обращается к системной функ-
ции exec, ядро считывает из файловой системы в память указанный исполняемый
файл. Однако в системе с замещением страниц по запросу исполняемый файл,
---------------------------------------
(****) Функция exit используется в варианте _exit, потому что она "очищает"
структуры данных, передаваемые через стандартный ввод-вывод (на поль-
зовательском уровне), для обоих процессов, так что оператор printf,
используемый родителем, не даст правильный результат - еще один неже-
лательный побочный эффект от применения функции vfork.
272
имеющий большой размер, может не уместиться в доступном пространстве основ-
ной памяти. Поэтому ядро не назначает ему сразу все пространство, а отводит
место в памяти по мере надобности. Сначала ядро назначает файлу таблицы
страниц и дескрипторы дисковых блоков, помечая страницы в записях таблиц как
"заполняемые при обращении" (для всех данных, кроме имеющих тип bss) или
"обнуляемые при обращении" (для данных типа bss). Считывая в память каждую
страницу файла по алгоритму read, процесс получает ошибку из-за отсутствия
(недоступности) данных. Подпрограмма обработки ошибок проверяет, является ли
страница "заполняемой при обращении" (тогда ее содержимое будет немедленно
затираться содержимым исполняемого файла и поэтому ее не надо очищать) или
"обнуляемой при обращении" (тогда ее следует очистить). В разделе 9.2.3 мы
увидим, как это происходит. Если процесс не может поместиться в памяти,
"сборщик" страниц освобождает для него место, периодически откачивая из па-
мяти неиспользуемые страницы.
В этой схеме видны явные недостатки. Во-первых, при чтении каждой стра-
ницы исполняемого файла процесс сталкивается с ошибкой из-за обращения к от-
сутствующей странице, пусть даже процесс никогда и не обращался к ней.
Во-вторых, если после того, как "сборщик" страниц откачал часть страниц из
памяти, была запущена функция exec, каждая только что выгруженная и вновь
понадобившаяся страница потребует дополнительную операцию по ее загрузке.
Чтобы повысить эффективность функции exec, ядро может востребовать страницу
непосредственно из исполняемого файла, если данные в файле соответствующим
образом настроены, что определяется значением т.н. "магического числа". Од-
нако, использование стандартных алгоритмов доступа к файлу (например, bmap)
потребовало бы при обращении к странице, состоящей из блоков косвенной адре-
сации, больших затрат, связанных с многократным использованием буферного ке-
ша для чтения каждого блока. Кроме того, функция bmap не является реентера-
бельной, отсюда возникает опасность нарушения целостности данных. Во время
выполнения системной функции read ядро устанавливает в пространстве процесса
значения различных параметров ввода-вывода. Если при попытке скопировать
данные в пространство пользователя процесс столкнется с отсутствием нужной
страницы, он, считывая страницу из файловой системы, может затереть содержа-
щие эти параметры поля. Поэтому ядро не может прибегать к использованию
обычных алгоритмов обработки ошибок данного рода. Конечно же алгоритмы долж-
ны быть в обычных случаях реентерабельными, поскольку у каждого процесса
свое отдельное адресное пространство и процесс не может одновременно испол-
нять несколько системных функций.
Для того, чтобы считывать страницы непосредственно из исполняемого фай-
ла, ядро во время исполнения функции exec составляет список номеров дисковых
блоков файла и присоединяет этот список к индексу файла. Работая с таблицами
страниц такого файла, ядро находит дескриптор дискового блока, содержащего
страницу, и запоминает номер блока внутри файла; этот номер позже использу-
Список блоков,
Область +-> связанный с индексом
+---------------------------------+ | +----------------+
| Индекс-----------+-+ 0 | |
| | - | |
| | - | |
| Дескриптор дискового блока | - | |
| +---------------------------+ | - | |
| | Логический блок 84 | | - +----------------+
| +---------------------------+ | 84 | 279 |
| | +----------------+
+---------------------------------+ | |
| |
+----------------+
Рисунок 9.17. Отображение файла на область
273
ется при загрузке страницы из файла. На Рисунке 9.17 показан пример, в кото-
ром страница имеет адрес расположения в логическом блоке с номером 84 от на-
чала файла. В области имеется указатель на индекс, в котором содержится но-
мер соответствующего физического блока на диске (279).
"Сборщик" страниц (page stealer) является процессом, принадлежащим ядру
операционной системы и выполняющим выгрузку из памяти тех страниц, которые
больше не входят в состав рабочего множества пользовательского процесса.
Этот процесс создается ядром во время инициализации системы и запускается в
любой момент, когда в нем возникает необходимость. Он просматривает все ак-
тивные незаблокированные области и увеличивает значение "возраста" каждой
принадлежащей им страницы (заблокированные области пропускаются, но впослед-
ствии, по снятии блокировки, тоже будут учтены). Когда процесс при работе со
страницей, принадлежащей области, получает ошибку, ядро блокирует область,
чтобы "сборщик" не смог выгрузить страницу до тех пор, пока ошибка не будет
обработана.
Страница в памяти может находиться в двух состояниях: либо "дозревать",
не будучи еще готовой к выгрузке, либо быть готовой к выгрузке и доступной
для привязки к другим виртуальным страницам. Первое состояние означает, что
процесс обратился к странице и поэтому страница включена в его рабочее мно-
жество. При обращении к странице в некоторых машинах аппаратно устанавлива-
ется бит упоминания, если же эта операция не выполняется, соответственно, и
программные методы скорее всего используются другие (раздел 9.2.4). Если
страница находится в первом состоянии, "сборщик" сбрасывает бит упоминания в
ноль, но запоминает количество просмотров множества страниц, выполненных с
момента последнего обращения к странице со стороны пользовательского процес-
са. Таким образом, первое состояние распадается на несколько подсостояний в
соответствии с тем, сколько раз "сборщик" страниц обратился к странице до
того, как страница стала готовой для выгрузки (см. Рисунок 9.18). Когда это
число превышает некоторое пороговое значение, ядро переводит страницу во
второе состояние - состояние готовности к выгрузке. Максимальная продолжи-
тельность пребывания страницы в первом состоянии зависит от условий конкрет-
ной реализации и ограничивается числом отведенных для этого поля разрядов в
записи таблицы страниц.
На Рисунке 9.19 показано взаимодействие между процессами, работающими со
страницей, и "сборщиком" страниц. Цифры обозначают номер обращения "сборщи-
Ссылка на страницу
+------------+----------+----------+-----------------+
| ^ ^ ^ |
v | | | | Готов-
+-------+ | | | | ность
| Стра- | +-+-+ +-+-+ +-+-+ +-+-+ к
| ница в|----->| 1 +----->| 2 +----->| 3 +-------->| n | вы-
| памяти| +---+ +---+ +---+ +-+-+ груз-
+-------+ "Дозревание" страницы --- отсутствие | ке
^ ссылок |
| |
| +--------+ |
| | Страни-| |
За- +-----------------------| ца вы- |<------------------+ Выгруз-
грузка | гружена| ка
+--------+
Рисунок 9.18. Диаграмма состояний страницы
274
ка" к странице с того момента, как страни-
ца была загружена в память. Процесс, обратившийся к странице после второго
просмотра страниц "сборщиком", сбросил ее "возраст" в 0. После каждого прос-
мотра пользовательский процесс обращался к странице вновь, но в конце концов
"сборщик" страниц осуществил три просмотра страницы с момента последнего об-
ращения к ней со стороны пользовательского процесса и выгрузил ее из памяти.
Если область используется совместно не менее, чем двумя процессами, все
они работают с битами упоминания в одном и том же наборе записей таблицы
страниц. Таким образом, страницы могут включаться в рабочие множества нес-
кольких процессов, но для "сборщика" страниц это не имеет никакого значения.
Если страница включена в рабочее множество хотя бы одного из процессов, она
остается в памяти; в противном случае она может быть выгружена. Ничего, что
одна область, к примеру, имеет в памяти страниц больше, чем имеют другие:
"сборщик" страниц не пытается выгрузить равное количество страниц из всех
активных областей.
Ядро возобновляет работу "сборщика" страниц, когда доступная в системе
свободная память имеет размер, не дотягивающий до нижней допустимой отметки,
и тогда "сборщик" производит откачку страниц до тех пор, пока объем свобод-
ной памяти не превысит верхнюю отметку. При использовании двух отметок коли-
чество производимых операций сокращается, ибо если ядро использует только
одно пороговое значение, оно будет выгружать достаточное число страниц для
освобождения памяти свыше порогового значения, но в результате возвращения
ошибочно выгруженных страниц в память размер свободного пространства вскоре
вновь опустится ниже этого порога. Объем свободной памяти при этом постоянно
бы поддерживался около пороговой отметки. Выгрузка страниц с освобождением
памяти в объеме, превышающем верхнюю отметку, откладывает момент, когда объ-
ем свободной памяти в системе станет меньше нижней отметки, поэтому "сборщи-
ку" страниц не приходится уже так часто выполнять свою работу. Оптимальный
выбор уровней верхней и нижней отметок администратором повышает производи-
тельность системы.
Когда "сборщик" страниц принимает решение выгрузить страницу из памяти,
он проверяет возможность нахождения копии этой страницы на устройстве выг-
рузки. При этом могут иметь место три случая:
Состояние страницы Время (последнего упоминания)
+----------------------+-----------+
| В памяти | 0 |
+----------------------+-----------+
| | 1 |
+----------------------+-----------+
| | 2 |
+----------------------+-----------+ Ссылка на страницу
| | 0 |
+----------------------+-----------+
| | 1 |
+----------------------+-----------+ Ссылка на страницу
| | 0 |
+----------------------+-----------+
| | 1 |
+----------------------+-----------+
| | 2 |
+----------------------+-----------+
| | 3 |
+----------------------+-----------+ Страница выгружена
| Вне памяти | |
+----------------------+-----------+
Рисунок 9.19. Пример "созревания" страницы
275
1. Если на устройстве выгрузки есть копия страницы, ядро "планирует" выг-
рузку страницы: "сборщик" страниц помещает ее в список выгруженных стра-
ниц и переходит дальше; выгрузка считается логически завершившейся. Ког-
да число страниц в списке превысит ограничение (определяемое возможнос-
тями дискового контроллера), ядро переписывает страницы на устройство
выгрузки.
2. Если на устройстве выгрузки уже есть копия страницы и ее содержимое ни-
чем не отличается от содержимого страницы в памяти (бит модификации в
записи таблицы страниц не установлен), ядро сбрасывает в ноль бит дос-
тупности (в той же записи таблицы), уменьшает значение счетчика ссылок в
таблице pfdata и помещает запись в список свободных страниц для будущего
переназначения.
3. Если на устройстве выгрузки есть копия страницы, но процесс изменил со-
держимое ее оригинала в памяти, ядро планирует выгрузку страницы и осво-
бождает занимаемое ее копией место на устройстве выгрузки.
"Сборщик" страниц копирует страницу на устройство выгрузки, если имеют
место случаи 1 и 3.
Чтобы проиллюстрировать различия между последними двумя случаями, пред-
положим, что страница находится на устройстве выгрузки и загружается в ос-
новную память после того, как процесс столкнулся с отсутствием необходимых
данных. Допустим, ядро не стало автоматически удалять копию страницы на дис-
ке. В конце концов, "сборщик" страниц вновь примет решение выгрузить страни-
цу. Если с момента загрузки в память в страницу не производилась запись дан-
ных, содержимое страницы в памяти идентично содержимому ее дисковой копии и
в переписи страницы на устройство выгрузки необходимости не возникает. Одна-
ко, если процесс успел что-то записать на страницу, старый и новый ее вари-
анты будут различаться, поэтому ядру следует переписать страницу на устройс-
тво выгрузки, освободив предварительно место, занимаемое на устройстве ста-
рым вариантом. Ядро не сразу использует освобожденное пространство на уст-
ройстве выгрузки, поэтому оно имеет возможность поддерживать непрерывное
размещение занятых участков, что повышает эффективность использования облас-
ти выгрузки.
"Сборщик" страниц заполняет список выгруженных страниц, которые в прин-
ципе могут принадлежать разным областям, и по заполнении списка откачивает
их на устройство выгрузки. Нет необходимости в том, чтобы все страницы одно-
го процесса непременно выгружались: к примеру, некоторые из страниц, возмож-
но, недостаточно "созрели" для этого. В этом видится различие со стратегией
выгрузки процессов, согласно которой из памяти выгружаются все страницы од-
ного процесса, вместе с тем метод переписи данных на устройство выгрузки
идентичен тому методу, который описан для системы с замещением процессов в
разделе 9.1.2. Если на устройстве выгрузки недостаточно непрерывного прост-
ранства, ядро выгружает страницы по отдельности (по одной странице за опера-
цию), что в конечном итоге обходится недешево. В системе с замещением стра-
ниц фрагментация на устройстве выгрузки выше, чем в системе с замещением
процессов, поскольку ядро выгружает блоки страниц, но загружает в память
каждую страницу в отдельности.
Когда ядро переписывает страницу на устройство выгрузки, оно сбрасывает
бит доступности в соответствующей записи таблицы страниц и уменьшает значе-
ние счетчика ссылок в соответствующей записи таблицы pfdata. Если значение
счетчика становится равным 0, запись таблицы pfdata помещается в конец спис-
ка свободных страниц и запоминается для последующего переназначения. Если
значение счетчика отлично от 0, это означает, что страница (в результате вы-
полнения функции fork) используется совместно несколькими процессами, но яд-
ро все равно выгружает ее. Наконец, ядро выделяет пространство на устройстве
выгрузки, сохраняет его адрес в дескрипторе дискового блока и увеличивает
значение счетчика ссылок на страницу в таблице использования области подкач-
ки. Если в то время, пока страница находится в списке свободных страниц,
процесс обнаружил ее отсутствие, получив соответствующую ошибку, ядро может
276
восстановить ее в памяти, не обращаясь к устройству выгрузки. Однако, стра-
ница все равно будет считаться выгруженной, если она попала в список "сбор-
щика" страниц.
Предположим, к примеру, что "сборщик" страниц выгружает 30, 40, 50 и 20
страниц из процессов A, B, C и D, соответственно, и что за одну операцию
выгрузки на дисковое устройство откачиваются 64 страницы. На Рисунке 9.20
показана последовательность имеющих при этом место операций выгрузки при ус-
ловии, что "сборщик" страниц осуществляет просмотр страниц процессов в оче-
редности: A, B, C, D. "Сборщик" выделяет на устройстве выгрузки место для 64
страниц и выгружает 30 страниц процесса A и 34 страницы процесса B. Затем он
выделяет место для следующих 64 страниц и выгружает оставшиеся 6 страниц
процесса B, 50 страниц процесса C и 8 страниц процесса D. Выделенные для
размещения страниц за две операции участки области выгрузки могут быть и
риков". Ядро выстраивает записи таблицы в хеш-очередь в соответствии с номе-
ром устройства (выгрузки) и номером блока. Используя эти номера, ядро может
быстро отыскать страницу, если она находится в памяти. Передавая физическую
страницу области, ядро выбирает соответствующую запись из списка свободных
страниц, исправляет указанные в ней номера устройства и блока и помещает ее
в соответствующее место хеш-очереди.
Каждая запись таблицы использования области подкачки соответствует стра-
нице, находящейся на устройстве выгрузки. Запись содержит счетчик ссылок,
показывающий количество записей таблицы страниц, в которых имеется ссылка на
текущую страницу.
На Рисунке 9.14 показана взаимосвязь между записями таблицы страниц,
дескрипторами дисковых блоков, записями таблицы pfdata и таблицы использова-
ния области подкачки. Виртуальный адрес 1493К отображается на запись таблицы
страниц, соответствующую странице с физическим номером 794; дескриптор дис-
кового блока, связанный с этой записью, свидетельствует о том, что содержи-
мое страницы располагается на устройстве выгрузки с номером 1 в дисковом
блоке с номером 2743. Запись таблицы pfdata, помимо того, что указывает на
те же номера устройства и блока, сообщает, что счетчик ссылок на физическую
страницу имеет значение, равное 1. О том, почему номер дискового блока дуб-
лируется в записи таблицы pfdata, вы узнаете из раздела 9.2.4.1. Счетчик
ссылок на виртуальную страницу (в записи таблицы использования области под-
качки) свидетельствует о том, что на копию страницы на устройстве выгрузки
269
ссылается только одна запись таблицы страниц.
Как уже говорилось в разделе 7.1, во время выполнения функции fork ядро
создает копию каждой области родительского процесса и присоединяет ее к про-
цессу-потомку. В системе с замещением стра-
+-----------------------+--------------------------+
Виртуальный |Запись таблицы страниц|Дескриптор дискового блока|
адрес +-----------------------+--------------------------+
1493К | Номер страницы 794 | Устройство 1 Блок 2743 |
+---+-+-----------------+--------------------+-----+
| | |
| | Запись таблицы pfdata, |
| | соответствующая стра- +------------+
+------------+ v нице с номером 794 |
| +------------+-----------------------+ |
| | | Счетчик ссылок 1 | | Запись таблицы
| | +-----------------------+ | использования
| | | Номер устройства 1 | | области подкачки
| | +-----------------------+ | +-----------------+
| | | Номер блока 2743 | | |Счетчик ссылок 1|
| | +-----------------+-----+ | +--------+--------+
| | | +-----+ |
| | | | +--------------+
v v v v v
+--------------------------+ +---------------------------+
| Физическая страница 794 | | Номер блока 2743 |
+--------------------------+ +---------------------------+
Рисунок 9.14. Взаимосвязь между структурами данных, участвующими в реа-
лизации механизма замещения страниц по обращению
ниц ядро по традиции создает физическую копию адресного пространства процес-
са-родителя, что в общем случае является довольно расточительной операцией,
поскольку процесс часто после выполнения функции fork обращается к функции
exec и незамедлительно освобождает только что скопированное пространство.
Если область разделяемая, в версии V вместо копирования страницы ядро просто
увеличивает значение счетчика ссылок на область (в таблице областей, в таб-
лице страниц и в таблице pfdata). Тем не менее, для частных областей, таких
как область данных и стека, ядро отводит в таблице областей и таблице стра-
ниц новую запись, после чего просматривает в таблице страниц все записи про-
цесса-родителя: если запись верна, ядро увеличивает значение счетчика ссылок
в таблице pfdata, отражающее количество процессов, использующих страницу че-
рез разные области (в отличие от тех процессов, которые используют данную
страницу через разделяемую область). Если страница располагается на устройс-
тве выгрузки, ядро увеличивает значение счетчика ссылок в таблице использо-
вания области подкачки.
Теперь на страницу могут ссылаться обе области, использующие эту страни-
цу совместно, пока процесс не ведет на нее запись. Как только страница пона-
добится процессу для записи, ядро создаст ее копию, с тем, чтобы у каждой
области была своя личная версия страницы. Для этого при выполнении функции
fork в каждой записи таблицы страниц, соответствующей частным областям роди-
теля и потомка, ядро устанавливает бит "копирования при записи". Если один
из процессов попытается что-то записать на страницу, он получит отказ систе-
мы защиты, после чего для него будет создана новая копия содержимого страни-
цы. Таким образом, физическое копирование страницы откладывается до того мо-
270
мента, когда в этом возникнет реальная потребность.
В качестве примера рассмотрим Рисунок 9.15. Процессы разделяют доступ к
таблице страниц совместно используемой области команд T, поэтому значение
счетчика ссылок на область равно 2, а на страницы области единице (в таблице
pfdata). Ядро назначает про-
Процесс-родитель Процесс-потомок
Частная таблица Частная таблица
областей процесса областей процесса
+--------------+ +--------------+
| - | | - |
+--------------+ +--------------+
| - - | | - - |
+--------------+ +--------------+
- + ---------------------+ -
- - - -
v v v v
+-------------------+ +-------------------+ +-------------------+
| Область T | | Область P1 | | Область C1 |
| Счетчик ссылок 2 | | Счетчик ссылок 1 | | Счетчик ссылок 1 |
|+-----------------+| |+-----------------+| |+-----------------+|
|| Записи таблицы || || Записи таблицы || || Записи таблицы ||
|| страниц || || страниц || || страниц ||
|+-----------------+| |+-----------------+| |+-----------------+|
|| - || || - || || - ||
|| - || || - || || - ||
|+-----------------+| || - || || - ||
||Виртуаль- Стра-|| || - || || - ||
||ный адрес ница || || - || || - ||
|| 24К 967 || || - || || - ||
|+-----------------+| |+-----------------+| |+-----------------+|
|| - - || ||Виртуаль- Стра-|| ||Виртуаль- Стра-||
|| - - || ||ный адрес ница || ||ный адрес ница ||
|| - - || || 97К 613 || || 97К 613 ||
|| - - || |+-----------------+| |+-----------------+|
|| - - || || - - || || - - ||
|| - - || || - - || || - - ||
|+-----------------+| |+-----------------+| |+-----------------+|
+-------------------+ +-------------------+ +-------------------+
- - -----------
v v v
+---------------------+ +---------------------+
| Страничный блок 967 | | Страничный блок 613 |
| Счетчик ссылок 1 | | Счетчик ссылок 2 |
+---------------------+ +---------------------+
Рисунок 9.15. Адресация страниц, участвующих в процессе вы-
полнения функции fork
цессу-потомку новую область данных C1, являющуюся копией области P1 процес-
са-родителя. Обе области используют одни и те же записи таблицы страниц, это
видно на примере страницы с виртуальным адресом 97К. Этой странице в таблице
pfdata соответствует запись с номером 613, счетчик ссылок в которой равен 2,
ибо на страницу ссылаются две области.
В ходе выполнения функции fork в системе BSD создается физическая копия
страниц родительского процесса. Однако, учитывая наличие ситуаций, в которых
создание физической копии не является обязательным, в системе BSD существует
271
также функция vfork, которая используется в том случае, если процесс сразу
по завершении функции fork собирается запустить функцию exec. Функция vfork
не копирует таблицы страниц, поэтому она работает быстрее, чем функция fork
в версии V системы UNIX. Однако процесс-потомок при этом исполняется в тех
же самых физических адресах, что и его родитель, и может поэтому затереть
данные и стек родительского процесса. Если программист использует функцию
vfork неверно, может возникнуть опасная ситуация, поэтому вся ответствен-
ность за ее использование возлагается на программиста. Различие в подходах к
рассматриваемому вопросу в системах UNIX и BSD имеет философский характер,
они дают разный ответ на один и тот же вопрос: следует ли ядру скрывать осо-
бенности реализации своих функций, превращая их в тайну для пользователей,
или же стоит дать опытным пользователям возможность повысить эффективность
выполнения системных операций ?
+------------------------------------------------------------+
| int global; |
| main() |
| { |
| int local; |
| |
| local = 1; |
| if (vfork() == 0) |
| { |
| /* потомок */ |
| global = 2; /* запись в область данных родителя */|
| local = 3; /* запись в стек родителя */ |
| _exit(); |
| } |
| printf("global %d local %d\n",global,local); |
| } |
+------------------------------------------------------------+
Рисунок 9.16. Функция vfork и искажение информации процесса
В качестве примера рассмотрим программу, приведенную на Рисунке 9.16.
После выполнения функции vfork процесс-потомок не запускает функцию exec, а
переустанавливает значения переменных global и local и завершается (****).
Система гарантирует, что процесс-родитель приостанавливается до того момен-
та, когда потомок исполнит функции exec или exit. Возобновив в конечном ито-
ге свое выполнение, процесс-родитель обнаружит, что значения двух его пере-
менных не совпадают с теми значениями, которые были у них до обращения к
функции vfork ! Еще больший эффект может произвести возвращение процесса-по-
томка из функции, вызвавшей функцию vfork (см. упражнение 9.8).
Как уже говорилось в главе 7, когда процесс обращается к системной функ-
ции exec, ядро считывает из файловой системы в память указанный исполняемый
файл. Однако в системе с замещением страниц по запросу исполняемый файл,
---------------------------------------
(****) Функция exit используется в варианте _exit, потому что она "очищает"
структуры данных, передаваемые через стандартный ввод-вывод (на поль-
зовательском уровне), для обоих процессов, так что оператор printf,
используемый родителем, не даст правильный результат - еще один неже-
лательный побочный эффект от применения функции vfork.
272
имеющий большой размер, может не уместиться в доступном пространстве основ-
ной памяти. Поэтому ядро не назначает ему сразу все пространство, а отводит
место в памяти по мере надобности. Сначала ядро назначает файлу таблицы
страниц и дескрипторы дисковых блоков, помечая страницы в записях таблиц как
"заполняемые при обращении" (для всех данных, кроме имеющих тип bss) или
"обнуляемые при обращении" (для данных типа bss). Считывая в память каждую
страницу файла по алгоритму read, процесс получает ошибку из-за отсутствия
(недоступности) данных. Подпрограмма обработки ошибок проверяет, является ли
страница "заполняемой при обращении" (тогда ее содержимое будет немедленно
затираться содержимым исполняемого файла и поэтому ее не надо очищать) или
"обнуляемой при обращении" (тогда ее следует очистить). В разделе 9.2.3 мы
увидим, как это происходит. Если процесс не может поместиться в памяти,
"сборщик" страниц освобождает для него место, периодически откачивая из па-
мяти неиспользуемые страницы.
В этой схеме видны явные недостатки. Во-первых, при чтении каждой стра-
ницы исполняемого файла процесс сталкивается с ошибкой из-за обращения к от-
сутствующей странице, пусть даже процесс никогда и не обращался к ней.
Во-вторых, если после того, как "сборщик" страниц откачал часть страниц из
памяти, была запущена функция exec, каждая только что выгруженная и вновь
понадобившаяся страница потребует дополнительную операцию по ее загрузке.
Чтобы повысить эффективность функции exec, ядро может востребовать страницу
непосредственно из исполняемого файла, если данные в файле соответствующим
образом настроены, что определяется значением т.н. "магического числа". Од-
нако, использование стандартных алгоритмов доступа к файлу (например, bmap)
потребовало бы при обращении к странице, состоящей из блоков косвенной адре-
сации, больших затрат, связанных с многократным использованием буферного ке-
ша для чтения каждого блока. Кроме того, функция bmap не является реентера-
бельной, отсюда возникает опасность нарушения целостности данных. Во время
выполнения системной функции read ядро устанавливает в пространстве процесса
значения различных параметров ввода-вывода. Если при попытке скопировать
данные в пространство пользователя процесс столкнется с отсутствием нужной
страницы, он, считывая страницу из файловой системы, может затереть содержа-
щие эти параметры поля. Поэтому ядро не может прибегать к использованию
обычных алгоритмов обработки ошибок данного рода. Конечно же алгоритмы долж-
ны быть в обычных случаях реентерабельными, поскольку у каждого процесса
свое отдельное адресное пространство и процесс не может одновременно испол-
нять несколько системных функций.
Для того, чтобы считывать страницы непосредственно из исполняемого фай-
ла, ядро во время исполнения функции exec составляет список номеров дисковых
блоков файла и присоединяет этот список к индексу файла. Работая с таблицами
страниц такого файла, ядро находит дескриптор дискового блока, содержащего
страницу, и запоминает номер блока внутри файла; этот номер позже использу-
Список блоков,
Область +-> связанный с индексом
+---------------------------------+ | +----------------+
| Индекс-----------+-+ 0 | |
| | - | |
| | - | |
| Дескриптор дискового блока | - | |
| +---------------------------+ | - | |
| | Логический блок 84 | | - +----------------+
| +---------------------------+ | 84 | 279 |
| | +----------------+
+---------------------------------+ | |
| |
+----------------+
Рисунок 9.17. Отображение файла на область
273
ется при загрузке страницы из файла. На Рисунке 9.17 показан пример, в кото-
ром страница имеет адрес расположения в логическом блоке с номером 84 от на-
чала файла. В области имеется указатель на индекс, в котором содержится но-
мер соответствующего физического блока на диске (279).
"Сборщик" страниц (page stealer) является процессом, принадлежащим ядру
операционной системы и выполняющим выгрузку из памяти тех страниц, которые
больше не входят в состав рабочего множества пользовательского процесса.
Этот процесс создается ядром во время инициализации системы и запускается в
любой момент, когда в нем возникает необходимость. Он просматривает все ак-
тивные незаблокированные области и увеличивает значение "возраста" каждой
принадлежащей им страницы (заблокированные области пропускаются, но впослед-
ствии, по снятии блокировки, тоже будут учтены). Когда процесс при работе со
страницей, принадлежащей области, получает ошибку, ядро блокирует область,
чтобы "сборщик" не смог выгрузить страницу до тех пор, пока ошибка не будет
обработана.
Страница в памяти может находиться в двух состояниях: либо "дозревать",
не будучи еще готовой к выгрузке, либо быть готовой к выгрузке и доступной
для привязки к другим виртуальным страницам. Первое состояние означает, что
процесс обратился к странице и поэтому страница включена в его рабочее мно-
жество. При обращении к странице в некоторых машинах аппаратно устанавлива-
ется бит упоминания, если же эта операция не выполняется, соответственно, и
программные методы скорее всего используются другие (раздел 9.2.4). Если
страница находится в первом состоянии, "сборщик" сбрасывает бит упоминания в
ноль, но запоминает количество просмотров множества страниц, выполненных с
момента последнего обращения к странице со стороны пользовательского процес-
са. Таким образом, первое состояние распадается на несколько подсостояний в
соответствии с тем, сколько раз "сборщик" страниц обратился к странице до
того, как страница стала готовой для выгрузки (см. Рисунок 9.18). Когда это
число превышает некоторое пороговое значение, ядро переводит страницу во
второе состояние - состояние готовности к выгрузке. Максимальная продолжи-
тельность пребывания страницы в первом состоянии зависит от условий конкрет-
ной реализации и ограничивается числом отведенных для этого поля разрядов в
записи таблицы страниц.
На Рисунке 9.19 показано взаимодействие между процессами, работающими со
страницей, и "сборщиком" страниц. Цифры обозначают номер обращения "сборщи-
Ссылка на страницу
+------------+----------+----------+-----------------+
| ^ ^ ^ |
v | | | | Готов-
+-------+ | | | | ность
| Стра- | +-+-+ +-+-+ +-+-+ +-+-+ к
| ница в|----->| 1 +----->| 2 +----->| 3 +-------->| n | вы-
| памяти| +---+ +---+ +---+ +-+-+ груз-
+-------+ "Дозревание" страницы --- отсутствие | ке
^ ссылок |
| |
| +--------+ |
| | Страни-| |
За- +-----------------------| ца вы- |<------------------+ Выгруз-
грузка | гружена| ка
+--------+
Рисунок 9.18. Диаграмма состояний страницы
274
ка" к странице с того момента, как страни-
ца была загружена в память. Процесс, обратившийся к странице после второго
просмотра страниц "сборщиком", сбросил ее "возраст" в 0. После каждого прос-
мотра пользовательский процесс обращался к странице вновь, но в конце концов
"сборщик" страниц осуществил три просмотра страницы с момента последнего об-
ращения к ней со стороны пользовательского процесса и выгрузил ее из памяти.
Если область используется совместно не менее, чем двумя процессами, все
они работают с битами упоминания в одном и том же наборе записей таблицы
страниц. Таким образом, страницы могут включаться в рабочие множества нес-
кольких процессов, но для "сборщика" страниц это не имеет никакого значения.
Если страница включена в рабочее множество хотя бы одного из процессов, она
остается в памяти; в противном случае она может быть выгружена. Ничего, что
одна область, к примеру, имеет в памяти страниц больше, чем имеют другие:
"сборщик" страниц не пытается выгрузить равное количество страниц из всех
активных областей.
Ядро возобновляет работу "сборщика" страниц, когда доступная в системе
свободная память имеет размер, не дотягивающий до нижней допустимой отметки,
и тогда "сборщик" производит откачку страниц до тех пор, пока объем свобод-
ной памяти не превысит верхнюю отметку. При использовании двух отметок коли-
чество производимых операций сокращается, ибо если ядро использует только
одно пороговое значение, оно будет выгружать достаточное число страниц для
освобождения памяти свыше порогового значения, но в результате возвращения
ошибочно выгруженных страниц в память размер свободного пространства вскоре
вновь опустится ниже этого порога. Объем свободной памяти при этом постоянно
бы поддерживался около пороговой отметки. Выгрузка страниц с освобождением
памяти в объеме, превышающем верхнюю отметку, откладывает момент, когда объ-
ем свободной памяти в системе станет меньше нижней отметки, поэтому "сборщи-
ку" страниц не приходится уже так часто выполнять свою работу. Оптимальный
выбор уровней верхней и нижней отметок администратором повышает производи-
тельность системы.
Когда "сборщик" страниц принимает решение выгрузить страницу из памяти,
он проверяет возможность нахождения копии этой страницы на устройстве выг-
рузки. При этом могут иметь место три случая:
Состояние страницы Время (последнего упоминания)
+----------------------+-----------+
| В памяти | 0 |
+----------------------+-----------+
| | 1 |
+----------------------+-----------+
| | 2 |
+----------------------+-----------+ Ссылка на страницу
| | 0 |
+----------------------+-----------+
| | 1 |
+----------------------+-----------+ Ссылка на страницу
| | 0 |
+----------------------+-----------+
| | 1 |
+----------------------+-----------+
| | 2 |
+----------------------+-----------+
| | 3 |
+----------------------+-----------+ Страница выгружена
| Вне памяти | |
+----------------------+-----------+
Рисунок 9.19. Пример "созревания" страницы
275
1. Если на устройстве выгрузки есть копия страницы, ядро "планирует" выг-
рузку страницы: "сборщик" страниц помещает ее в список выгруженных стра-
ниц и переходит дальше; выгрузка считается логически завершившейся. Ког-
да число страниц в списке превысит ограничение (определяемое возможнос-
тями дискового контроллера), ядро переписывает страницы на устройство
выгрузки.
2. Если на устройстве выгрузки уже есть копия страницы и ее содержимое ни-
чем не отличается от содержимого страницы в памяти (бит модификации в
записи таблицы страниц не установлен), ядро сбрасывает в ноль бит дос-
тупности (в той же записи таблицы), уменьшает значение счетчика ссылок в
таблице pfdata и помещает запись в список свободных страниц для будущего
переназначения.
3. Если на устройстве выгрузки есть копия страницы, но процесс изменил со-
держимое ее оригинала в памяти, ядро планирует выгрузку страницы и осво-
бождает занимаемое ее копией место на устройстве выгрузки.
"Сборщик" страниц копирует страницу на устройство выгрузки, если имеют
место случаи 1 и 3.
Чтобы проиллюстрировать различия между последними двумя случаями, пред-
положим, что страница находится на устройстве выгрузки и загружается в ос-
новную память после того, как процесс столкнулся с отсутствием необходимых
данных. Допустим, ядро не стало автоматически удалять копию страницы на дис-
ке. В конце концов, "сборщик" страниц вновь примет решение выгрузить страни-
цу. Если с момента загрузки в память в страницу не производилась запись дан-
ных, содержимое страницы в памяти идентично содержимому ее дисковой копии и
в переписи страницы на устройство выгрузки необходимости не возникает. Одна-
ко, если процесс успел что-то записать на страницу, старый и новый ее вари-
анты будут различаться, поэтому ядру следует переписать страницу на устройс-
тво выгрузки, освободив предварительно место, занимаемое на устройстве ста-
рым вариантом. Ядро не сразу использует освобожденное пространство на уст-
ройстве выгрузки, поэтому оно имеет возможность поддерживать непрерывное
размещение занятых участков, что повышает эффективность использования облас-
ти выгрузки.
"Сборщик" страниц заполняет список выгруженных страниц, которые в прин-
ципе могут принадлежать разным областям, и по заполнении списка откачивает
их на устройство выгрузки. Нет необходимости в том, чтобы все страницы одно-
го процесса непременно выгружались: к примеру, некоторые из страниц, возмож-
но, недостаточно "созрели" для этого. В этом видится различие со стратегией
выгрузки процессов, согласно которой из памяти выгружаются все страницы од-
ного процесса, вместе с тем метод переписи данных на устройство выгрузки
идентичен тому методу, который описан для системы с замещением процессов в
разделе 9.1.2. Если на устройстве выгрузки недостаточно непрерывного прост-
ранства, ядро выгружает страницы по отдельности (по одной странице за опера-
цию), что в конечном итоге обходится недешево. В системе с замещением стра-
ниц фрагментация на устройстве выгрузки выше, чем в системе с замещением
процессов, поскольку ядро выгружает блоки страниц, но загружает в память
каждую страницу в отдельности.
Когда ядро переписывает страницу на устройство выгрузки, оно сбрасывает
бит доступности в соответствующей записи таблицы страниц и уменьшает значе-
ние счетчика ссылок в соответствующей записи таблицы pfdata. Если значение
счетчика становится равным 0, запись таблицы pfdata помещается в конец спис-
ка свободных страниц и запоминается для последующего переназначения. Если
значение счетчика отлично от 0, это означает, что страница (в результате вы-
полнения функции fork) используется совместно несколькими процессами, но яд-
ро все равно выгружает ее. Наконец, ядро выделяет пространство на устройстве
выгрузки, сохраняет его адрес в дескрипторе дискового блока и увеличивает
значение счетчика ссылок на страницу в таблице использования области подкач-
ки. Если в то время, пока страница находится в списке свободных страниц,
процесс обнаружил ее отсутствие, получив соответствующую ошибку, ядро может
276
восстановить ее в памяти, не обращаясь к устройству выгрузки. Однако, стра-
ница все равно будет считаться выгруженной, если она попала в список "сбор-
щика" страниц.
Предположим, к примеру, что "сборщик" страниц выгружает 30, 40, 50 и 20
страниц из процессов A, B, C и D, соответственно, и что за одну операцию
выгрузки на дисковое устройство откачиваются 64 страницы. На Рисунке 9.20
показана последовательность имеющих при этом место операций выгрузки при ус-
ловии, что "сборщик" страниц осуществляет просмотр страниц процессов в оче-
редности: A, B, C, D. "Сборщик" выделяет на устройстве выгрузки место для 64
страниц и выгружает 30 страниц процесса A и 34 страницы процесса B. Затем он
выделяет место для следующих 64 страниц и выгружает оставшиеся 6 страниц
процесса B, 50 страниц процесса C и 8 страниц процесса D. Выделенные для
размещения страниц за две операции участки области выгрузки могут быть и