Geum.ru

The design of the unix operating system by Maurice J

Вид материалаРеферат
Подобный материал:
1   ...   32   33   34   35   36   37   38   39   ...   55
частью от целого, в основной памяти может поместиться больше про-

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

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

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

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

ка, при обработке которой ядро корректирует рабочее множество

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

устройства.

На Рисунке 9.12 приведена последовательность используемых

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

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

ния "стариков" (замещения страниц путем откачки тех, к которым

наиболее долго не было обращений). По мере выполнения процесса

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

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

чет за собой увеличение рабочего множества и, с другой стороны,

сокращение числа ошибок в выполнении процесса. Использование не-

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

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

слишком больших затрат. Приблизительное соответствие между изме-

няемым рабочим множеством и пространством процесса достигается

путем установки бита упоминания (reference bit) при обращении к

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

ниц. Если на страницу была сделана ссылка, эта страница включает-

ся в рабочее множество; в противном случае она "дозревает" в па-

мяти в ожидании своей очереди.

В случае возникновения ошибки из-за обращения к странице,

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

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

и не станет доступной процессу. Когда страница будет загружена,

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

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

мы замещения страниц распадается на две части: откачка редко ис-

пользуемых страниц на устройство выгрузки и обработка ошибок

из-за отсутствия нужной страницы. Такое общее толкование механиз-

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

ретной системы. Оставшуюся часть главы мы посвятим более деталь-

ному рассмотрению особенностей реализации этого механизма в

версии V системы UNIX.


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

страниц


Для поддержки функций управления памятью на машинном (низком)

уровне и для реализации механизма замещения страниц ядро исполь-

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

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

(page frame data table - сокращенно: pfdata) и таблицу использо-

вания области подкачки. Место для таблицы pfdata выделяется один

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

памяти выделяются динамически.

Из главы 6 нам известно, что каждая область располагает свои-

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

физической памяти. Каждая запись таблицы страниц (Рисунок 9.13)

состоит из физического адреса страницы, кода защиты, в разрядах

которого описываются права доступа процесса к странице (на чте-

ние, запись и исполнение), а также следующих двоичных полей, ис-

пользуемых механизмом замещения страниц:


Последователь-

ность указате- Рабочие множества Размеры окон

лей страниц 2 3 4 5

-------------┐ --------T----------T-------------T----------------┐

│ 24 │ │ 24 │ 24 │ 24 │ 24 │

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

│ 15 │ │ 15 24 │ 15 24 │ 15 24 │ 15 24 │

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

│ 18 │ │ 18 15 │ 18 15 24 │ 18 15 24 │ 18 15 24 │

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

│ 23 │ │ 23 18 │ 23 18 15 │ 23 18 15 24 │ 23 18 15 24 │

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

│ 24 │ │ 24 23 │ 24 23 18 │ │ │

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

│ 17 │ │ 17 24 │ 17 24 23 │ 17 24 23 18 │ 17 24 23 18 15 │

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

│ 18 │ │ 18 17 │ 18 17 24 │ │ │

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

│ 24 │ │ 24 18 │ │ │ │

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

│ 18 │ │ 18 24 │ │ │ │

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

│ 17 │ │ 17 18 │ │ │ │

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

│ 17 │ │ │ │ │ │

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

│ 15 │ │ 15 17 │ 15 17 18 │ 15 17 18 24 │ │

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

│ 24 │ │ 24 15 │ 24 15 17 │ │ │

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

│ 17 │ │ 17 24 │ │ │ │

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

│ 24 │ │ 24 17 │ │ │ │

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

│ 18 │ │ 18 24 │ 18 24 17 │ │ │

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


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


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

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

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

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

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

Установка бита доступности свидетельствует о правильности со-

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

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

недопустима, в чем мы убедимся позже. Бит упоминания устанавлива-

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

модификации - в том случае, если процесс скорректировал содержи-

мое страницы. Установка бита копирования при записи, производимая

во время выполнения системной функции fork, свидетельствует о

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

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

страницы говорит о продолжительности ее пребывания в составе ра-

бочего множества процесса. Биты доступности, копирования при за-

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

и модификации - аппаратным путем; в разделе 9.2.4 рассматриваются

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

турой.


---------┐ -->-----------------------T---------------------------┐

│ │ │ │ │ │

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

│ │ │ │ │ │

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

│ Область│ │ │ │ │

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

│ │ │ │Записи таблицы страниц│Дескрипторы дисковых блоков│

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

│ │ │ │ │

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

│ │ │ │ │

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

│ │ │

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

│ │ │

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

│ │ │

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

│ │ │

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


Запись таблицы страниц

------------------------------T-------T-----T-----T----T-----T---┐

│ Адрес страницы (физический) │Возраст│Копи-│Моди-│Упо-│До- │За-│

│ │ │рова-│фика-│ми- │пус- │щи-│

│ │ │ние │ция │на- │ти- │та │

│ │ │при │ │ние │мость│ │

│ │ │запи-│ │ │ │ │

│ │ │си │ │ │ │ │

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


Дескриптор дискового блока

------------------------T---------------T------------------------┐

│ Устройство выгрузки │ Номер блока │ Тип (находится на ус- │

│ │ │ тройстве выгрузки, в │

│ │ │ файле, при обращении │

│ │ │ обнуляется, заполняет- │

│ │ │ ся) │

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


Рисунок 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. О том, почему

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

наете из раздела 9.2.4.1. Счетчик ссылок на виртуальную страницу

(в записи таблицы использования области подкачки) свидетельствует

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

только одна запись таблицы страниц.


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


Как уже говорилось в разделе 7.1, во время выполнения функции

fork ядро создает копию каждой области родительского процесса и

присоединяет ее к процессу-потомку. В системе с замещением стра-


------------------------T--------------------------┐

Виртуальный │Запись таблицы страниц│Дескриптор дискового блока│

адрес +-----------------------+--------------------------+

1493К │ Номер страницы 794 │ Устройство 1 Блок 2743 │

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

│ │ │

│ │ Запись таблицы pfdata, │

│ │ соответствующая стра- --------------

-------------- v нице с номером 794 │

│ -------------T-----------------------┐ │

│ │ │ Счетчик ссылок 1 │ │ Запись таблицы

│ │ +-----------------------+ │ использования

│ │ │ Номер устройства 1 │ │ области подкачки

│ │ +-----------------------+ │ ------------------┐

│ │ │ Номер блока 2743 │ │ │Счетчик ссылок 1│

│ │ L-----------------+------ │ L--------+---------

│ │ │ ------- │

│ │ │ │ ----------------

v v v v v

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

│ Физическая страница 794 │ │ Номер блока 2743 │

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


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

щими в реализации механизма замещения страниц

по обращению


ниц ядро по традиции создает физическую копию адресного прост-

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

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

ния функции fork обращается к функции exec и незамедлительно ос-

вобождает только что скопированное пространство. Если область

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

увеличивает значение счетчика ссылок на область (в таблице облас-

тей, в таблице страниц и в таблице pfdata). Тем не менее, для

частных областей, таких как область данных и стека, ядро отводит

в таблице областей и таблице страниц новую запись, после чего

просматривает в таблице страниц все записи процесса-родителя: ес-

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

лице pfdata, отражающее количество процессов, использующих стра-

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

используют данную страницу через разделяемую область). Если стра-

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

чение счетчика ссылок в таблице использования области подкачки.

Теперь на страницу могут ссылаться обе области, использующие

эту страницу совместно, пока процесс не ведет на нее запись. Как

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

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

страницы. Для этого при выполнении функции fork в каждой записи

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

томка, ядро устанавливает бит "копирования при записи". Если один

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

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

пия содержимого страницы. Таким образом, физическое копирование

страницы откладывается до того момента, когда в этом возникнет

реальная потребность.

В качестве примера рассмотрим Рисунок 9.15. Процессы разделя-

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

T, поэтому значение счетчика ссылок на область равно 2, а на

страницы области единице (в таблице pfdata). Ядро назначает про-


Процесс-родитель Процесс-потомок


Частная таблица Частная таблица

областей процесса областей процесса

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

│ │ │ │

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

│ │ │ │

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

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

v v v v

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

│ Область T │ │ Область P1 │ │ Область C1 │

│ Счетчик ссылок 2 │ │ Счетчик ссылок 1 │ │ Счетчик ссылок 1 │

│------------------┐│ │------------------┐│ │------------------┐│

││ Записи таблицы ││ ││ Записи таблицы ││ ││ Записи таблицы ││

││ страниц ││ ││ страниц ││ ││ страниц ││

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

││ ││ ││ ││ ││ ││

││ ││ ││ ││ ││ ││

││ ││ ││ ││ ││ ││

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

││Виртуаль- Стра-││ ││ ││ ││ ││

││ный адрес ница ││ ││ ││ ││ ││

││ 24К 967 ││ ││ ││ ││ ││

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

││ ││ ││Виртуаль- Стра-││ ││Виртуаль- Стра-││

││ ││ ││ный адрес ница ││ ││ный адрес ница ││

││ ││ ││ 97К 613 ││ ││ 97К 613 ││

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

││ ││ ││ ││ ││ ││

││ ││ ││ ││ ││ ││

││ ││ ││ ││ ││ ││

││ ││ ││ ││ ││ ││

│L-----------------│ │L-----------------│ │L-----------------│

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

---------

v v v

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

│ Страничный блок 967 │ │ Страничный блок 613 │

│ Счетчик ссылок 1 │ │ Счетчик ссылок 2 │

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


Рисунок 9.15. Адресация страниц, участвующих в процессе вы-

полнения функции fork


цессу-потомку новую область данных C1, являющуюся копией области

P1 процесса-родителя. Обе области используют одни и те же записи

таблицы страниц, это видно на примере страницы с виртуальным ад-

ресом 97К. Этой странице в таблице pfdata соответствует запись с

номером 613, счетчик ссылок в которой равен 2, ибо на страницу

ссылаются две области.

В ходе выполнения функции fork в системе BSD создается физи-

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

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

обязательным, в системе BSD существует также функция vfork, кото-

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

функции fork собирается запустить функцию exec. Функция vfork не

копирует таблицы страниц, поэтому она работает быстрее, чем функ-

ция fork в версии V системы UNIX. Однако процесс-потомок при этом

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

тель, и может поэтому затереть данные и стек родительского про-

цесса. Если программист использует функцию vfork неверно, может

возникнуть опасная ситуация, поэтому вся ответственность за ее

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

рассматриваемому вопросу в системах UNIX и BSD имеет философский

характер, они дают разный ответ на один и тот же вопрос: следует

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

их в тайну для пользователей, или же стоит дать опытным пользова-

телям возможность повысить эффективность выполнения системных

операций ?


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

│ int global; │

│ main() │

│ { │

│ int local; │

│ │

│ local = 1; │

│ if (vfork() == 0) │

│ { │

│ /* потомок */ │