Архитектура операционной системы UNIX

Бах Морис Дж.

9.2.1 Структуры данных, используемые подсистемой замещения страниц

Для поддержки функций управления памятью на машинном (низком) уровне и для реализации механизма замещения страниц ядро использует 4 основные структуры данных: записи таблицы страниц, дескрипторы дисковых блоков, таблицу содержимого страничных блоков (page frame data table — сокращенно: pfdata) и таблицу использования области подкачки. Место для таблицы pfdata выделяется один раз на все время жизни системы, для других же структур страницы памяти выделяются динамически.

Из главы 6 нам известно, что каждая область располагает своими таблицами страниц, с помощью которых осуществляется доступ к физической памяти. Каждая запись таблицы страниц (Рисунок 9.13) состоит из физического адреса страницы, кода защиты, в разрядах которого описываются права доступа процесса

к странице (на чтение, запись и исполнение), а также следующих двоичных полей, используемых механизмом замещения страниц:

• бит доступности

• бит упоминания

• бит модификации

• бит копирования при записи

• "возраст" страницы

Установка бита доступности свидетельствует о правильности содержимого страницы памяти, однако из того, что бит доступности выключен, не следует с необходимостью то, что ссылка на страницу недопустима, в чем мы убедимся позже. Бит упоминания устанавливается в том случае, если процесс делает ссылку на страницу, а бит модификации — в том случае, если процесс скорректировал содержимое страницы. Установка бита копирования при записи, производимая во время выполнения системной функции fork, свидетельствует о том, что ядру в случае, когда процесс корректирует содержимое страницы, следует создавать ее новую копию. Наконец, "возраст" страницы говорит о продолжительности ее пребывания в составе рабочего множества процесса. Биты доступности, копирования при записи и "возраст" страницы устанавливаются ядром, биты упоминания и модификации — аппаратным путем; в разделе 9.2.4 рассматриваются конфигурации, в которых эти возможности не поддерживаются аппаратурой.

Рисунок 9.12. Рабочее множество процесса

Рисунок 9.13. Записи таблицы страниц и дескрипторы дисковых блоков

Каждая запись таблицы страниц связана с дескриптором дискового блока, описывающим дисковую копию виртуальной страницы (Рисунок 9.13). Поэтому процессы, использующие разделяемую область, обращаются к общим записям таблицы страниц и к одним и тем же дескрипторам дисковых блоков. Содержимое виртуальной страницы располагается либо в отдельном блоке на устройстве выгрузки, либо в исполняемом файле, либо вообще отсутствует на устройстве выгрузки. Если страница находится на устройстве выгрузки, в дескрипторе дискового блока содержится логический номер устройства и номер блока, по которым можно отыскать содержимое страницы. Если страница содержится в исполняемом файле, в дескрипторе дискового блока располагается номер логического блока в файле с содержимым страницы; ядро может быстро преобразовать этот номер в адрес на диске. В дескрипторе дискового блока также имеется информация о двух устанавливаемых функцией exec особых условиях: страница при обращении к ней заполняется ("demand fill") или обнуляется ("demand zero"). Разъяснения по этому поводу даются в разделе 9.2.1.2.

В таблице pfdata описывается каждая страница физической памяти. Записи таблицы проиндексированы по номеру страницы и состоят из следующих полей:

• Статус страницы, указывающий на то, что страница располагается на устройстве выгрузки или в исполняемом файле, что к странице произведено обращение по прямому доступу в память (путем считывания информации с устройства выгрузки), или на то, что страница может быть переназначена.

• Количество процессов, ссылающихся на страницу. Счетчик ссылок хранит число записей в таблице страниц, имеющих ссылку на текущую страницу. Это значение может отличаться от количества процессов, использующих разделяемую область с данной страницей, в чем мы убедимся чуть позже, когда будем снова обращаться к алгоритму функции fork.

• Логический номер устройства (устройства выгрузки или файловой системы) и номер блока, указывающие расположение содержимого страницы.

• Указатели на другие записи таблицы pfdata в соответствии со списком свободных страниц или с хеш-очередью страниц.

По аналогии с буферным кэшем ядро связывает записи таблицы pfdata в список свободных страниц и хеш-очередь. Список свободных страниц представляет собой буфер, который содержит страницы, доступные для переназначения, однако процесс, обратившийся к этим страницам, может столкнуться с ошибкой адресации, так и не получив соответствующую страницу из списка. Этот список дает ядру возможность

сократить число операций чтения с устройства выгрузки. Ядро выделяет страницы из этого списка по вышеназванному принципу замещения "стариков". Ядро выстраивает записи таблицы в хеш-очередь в соответствии с номером устройства (выгрузки) и номером блока. Используя эти номера, ядро может быстро отыскать страницу, если она находится в памяти. Передавая физическую страницу области, ядро выбирает соответствующую запись из списка свободных страниц, исправляет указанные в ней номера устройства и блока и помещает ее в соответствующее место хеш-очереди.

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

На Рисунке 9.14 показана взаимосвязь между записями таблицы страниц, дескрипторами дисковых блоков, записями таблицы pfdata и таблицы использования области подкачки. Виртуальный адрес 1493К отображается на запись таблицы страниц, соответствующую странице с физическим номером 794; дескриптор дискового блока, связанный с этой записью, свидетельствует о том, что содержимое страницы располагается на устройстве выгрузки с номером 1 в дисковом блоке с номером 2743. Запись таблицы pfdata, помимо того, что указывает на те же номера устройства и блока, сообщает, что счетчик ссылок на физическую страницу имеет значение, равное 1. Счетчик ссылок на виртуальную страницу (в записи таблицы использования области подкачки) свидетельствует о том, что на копию страницы на устройстве выгрузки ссылается только одна запись таблицы страниц.

9.2.1.1 Функция fork в системе с замещением страниц

Как уже говорилось в разделе 7.1, во время выполнения функции fork ядро создает копию каждой области родительского процесса и присоединяет ее к процессу-потомку. В системе с замещением страниц ядро по традиции создает физическую копию адресного пространства процесса-родителя, что в общем случае является довольно расточительной операцией, поскольку процесс часто после выполнения функции fork обращается к функции exec и незамедлительно освобождает только что скопированное пространство. Если область разделяемая, в версии V вместо копирования страницы ядро просто увеличивает значение счетчика ссылок на область (в таблице областей, в таблице страниц и в таблице pfdata). Тем не менее, для частных областей, таких как область данных и стека, ядро отводит в таблице областей и таблице страниц новую запись, после чего просматривает в таблице страниц все записи процесса-родителя: если запись верна, ядро увеличивает значение счетчика ссылок в таблице pfdata, отражающее количество процессов, использующих страницу через разные области (в отличие от тех процессов, которые используют данную страницу через разделяемую область). Если страница располагается на устройстве выгрузки, ядро увеличивает значение счетчика ссылок в таблице использования области подкачки.

Рисунок 9.14. Взаимосвязь между структурами данных, участвующими в реализации механизма замещения страниц по обращению

Теперь на страницу могут ссылаться обе области, использующие эту страницу совместно, пока процесс не ведет на нее запись. Как только страница понадобится процессу для записи, ядро создаст ее копию, с тем, чтобы у каждой области была своя личная версия страницы. Для этого при выполнении функции fork в каждой записи таблицы страниц, соответствующей частным областям родителя и потомка, ядро устанавливает бит "копирования при записи". Если один из процессов попытается что-то записать на страницу, он получит отказ системы защиты, после чего для него будет создана новая копия содержимого страницы. Таким образом, физическое копирование страницы откладывается до того момента, когда в этом возникнет реальная потребность.

В качестве примера рассмотрим Рисунок 9.15. Процессы разделяют доступ к таблице страниц совместно используемой области команд T, поэтому значение счетчика ссылок на область равно 2, а на страницы области единице (в таблице pfdata). Ядро назначает процессу-потомку новую область данных C1, являющуюся копией области P1 процесса-родителя. Обе области используют одни и те же записи таблицы страниц, это видно на примере страницы с виртуальным адресом 97К. Этой странице в таблице pfdata соответствует запись с номером 613, счетчик ссылок в которой равен 2, ибо на страницу ссылаются две области.