Geum.ru

The design of the unix operating system by Maurice J

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

│ global = 2; /* запись в область данных родителя */│

│ local = 3; /* запись в стек родителя */ │

│ _exit(); │

│ } │

│ printf("global %d local %d\n",global,local); │

│ } │

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


Рисунок 9.16. Функция vfork и искажение информации процесса


В качестве примера рассмотрим программу, приведенную на Ри-

сунке 9.16. После выполнения функции vfork процесс-потомок не за-

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

global и local и завершается (****). Система гарантирует, что

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

мок исполнит функции exec или exit. Возобновив в конечном итоге

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

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

до обращения к функции vfork ! Еще больший эффект может произвес-

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

vfork (см. упражнение 9.8).


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

(****) Функция exit используется в варианте _exit, потому что она

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

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

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

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

ный эффект от применения функции vfork.


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


Как уже говорилось в главе 7, когда процесс обращается к сис-

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

указанный исполняемый файл. Однако в системе с замещением страниц

по запросу исполняемый файл, имеющий большой размер, может не

уместиться в доступном пространстве основной памяти. Поэтому ядро

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

по мере надобности. Сначала ядро назначает файлу таблицы страниц

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

как "заполняемые при обращении" (для всех данных, кроме имеющих

тип bss) или "обнуляемые при обращении" (для данных типа bss).

Считывая в память каждую страницу файла по алгоритму read, про-

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

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

"заполняемой при обращении" (тогда ее содержимое будет немедленно

затираться содержимым исполняемого файла и поэтому ее не надо

очищать) или "обнуляемой при обращении" (тогда ее следует очис-

тить). В разделе 9.2.3 мы увидим, как это происходит. Если про-

цесс не может поместиться в памяти, "сборщик" страниц освобождает

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

страницы.

В этой схеме видны явные недостатки. Во-первых, при чтении

каждой страницы исполняемого файла процесс сталкивается с ошибкой

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

когда и не обращался к ней. Во-вторых, если после того, как

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

функция exec, каждая только что выгруженная и вновь понадобившая-

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

Чтобы повысить эффективность функции exec, ядро может востребо-

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

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

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

ных алгоритмов доступа к файлу (например, bmap) потребовало бы

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

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

ферного кеша для чтения каждого блока. Кроме того, функция bmap

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

целостности данных. Во время выполнения системной функции read

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

раметров ввода-вывода. Если при попытке скопировать данные в

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

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

реть содержащие эти параметры поля. Поэтому ядро не может прибе-

гать к использованию обычных алгоритмов обработки ошибок данного

рода. Конечно же алгоритмы должны быть в обычных случаях реенте-

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

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

системных функций.

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

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

список номеров дисковых блоков файла и присоединяет этот список к

индексу файла. Работая с таблицами страниц такого файла, ядро на-

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

нает номер блока внутри файла; этот номер позже используется при

загрузке страницы из файла. На Рисунке 9.17 показан пример, в ко-

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

мером 84 от начала файла. В области имеется указатель на индекс,

в котором содержится номер соответствующего физического блока на

диске (279).


Список блоков,

Область --> связанный с индексом

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

│ Индекс-----------+-- 0 │ │

│ │ │ │

│ │ │ │

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

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

│ │ Логический блок 84 │ │ +----------------+

│ L---------------------------- │ 84 │ 279 │

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

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

│ │

│ │

│ │

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


Рисунок 9.17. Отображение файла на область


9.2.2 "Сборщик" страниц


"Сборщик" страниц (page stealer) является процессом, принад-

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

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

множества пользовательского процесса. Этот процесс создается яд-

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

когда в нем возникает необходимость. Он просматривает все актив-

ные незаблокированные области и увеличивает значение "возраста"

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

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

ны). Когда процесс при работе со страницей, принадлежащей облас-

ти, получает ошибку, ядро блокирует область, чтобы "сборщик" не

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

тана.

Страница в памяти может находиться в двух состояниях: либо

"дозревать", не будучи еще готовой к выгрузке, либо быть готовой

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

цам. Первое состояние означает, что процесс обратился к странице

и поэтому страница включена в его рабочее множество. При обраще-

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

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

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

9.2.4). Если страница находится в первом состоянии, "сборщик"

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

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

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

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

соответствии с тем, сколько раз "сборщик" страниц обратился к

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

Рисунок 9.18). Когда это число превышает некоторое пороговое зна-

чение, ядро переводит страницу во второе состояние - состояние

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

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

зации и ограничивается числом отведенных для этого поля разрядов

в записи таблицы страниц.

На Рисунке 9.19 показано взаимодействие между процессами, ра-

ботающими со страницей, и "сборщиком" страниц. Цифры обозначают

номер обращения "сборщика" к странице с того момента, как страни-


Ссылка на страницу

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

│ │

v │ │ │ │ Готов-

--------┐ │ │ │ │ ность

│ Стра- │ --+-┐ --+-┐ --+-┐ --+-┐ к

│ ница в│----->│ 1 +----->│ 2 +----->│ 3 +----····---->│ n │ вы-

│ памяти│ L---- L---- L---- L-T-- груз-

L-------- "Дозревание" страницы --- отсутствие │ ке

ссылок │

│ │

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

│ │ Страни-│ │

За- L-----------------------│ ца вы- │<------------------- Выгруз-

грузка │ гружена│ ка

L---------


Рисунок 9.18. Диаграмма состояний страницы


ца была загружена в память. Процесс, обратившийся к странице пос-

ле второго просмотра страниц "сборщиком", сбросил ее "возраст" в

0. После каждого просмотра пользовательский процесс обращался к

странице вновь, но в конце концов "сборщик" страниц осуществил

три просмотра страницы с момента последнего обращения к ней со

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

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

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

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

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

"сборщика" страниц это не имеет никакого значения. Если страница

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

тается в памяти; в противном случае она может быть выгружена. Ни-

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

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

количество страниц из всех активных областей.

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

в системе свободная память имеет размер, не дотягивающий до ниж-

ней допустимой отметки, и тогда "сборщик" производит откачку

страниц до тех пор, пока объем свободной памяти не превысит верх-

нюю отметку. При использовании двух отметок количество производи-

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

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

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

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

бодного пространства вскоре вновь опустится ниже этого порога.

Объем свободной памяти при этом постоянно бы поддерживался около

пороговой отметки. Выгрузка страниц с освобождением памяти в объ-

еме, превышающем верхнюю отметку, откладывает момент, когда объем

свободной памяти в системе станет меньше нижней отметки, поэтому

"сборщику" страниц не приходится уже так часто выполнять свою ра-

боту. Оптимальный выбор уровней верхней и нижней отметок адми-

нистратором повышает производительность системы.

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

из памяти, он проверяет возможность нахождения копии этой страни-

цы на устройстве выгрузки. При этом могут иметь место три случая:


Состояние страницы Время (последнего

упоминания)

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

│ В памяти │ 0 │

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

│ │ 1 │

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

│ │ 2 │

+----------------------+-----------+ Ссылка на страницу

│ │ 0 │

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

│ │ 1 │

+----------------------+-----------+ Ссылка на страницу

│ │ 0 │

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

│ │ 1 │

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

│ │ 2 │

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

│ │ 3 │

+----------------------+-----------+ Страница выгружена

│ Вне памяти │ │

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


Рисунок 9.19. Пример "созревания" страницы


1. Если на устройстве выгрузки есть копия страницы, ядро "плани-

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

сок выгруженных страниц и переходит дальше; выгрузка считает-

ся логически завершившейся. Когда число страниц в списке пре-

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

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

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

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

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

лен), ядро сбрасывает в ноль бит доступности (в той же запи-

си таблицы), уменьшает значение счетчика ссылок в таблице

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

щего переназначения.

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

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

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

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

"Сборщик" страниц копирует страницу на устройство выгрузки,

если имеют место случаи 1 и 3.

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

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

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

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

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

"сборщик" страниц вновь примет решение выгрузить страницу. Если с

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

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

вой копии и в переписи страницы на устройство выгрузки необходи-

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

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

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

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

том. Ядро не сразу использует освобожденное пространство на уст-

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

непрерывное размещение занятых участков, что повышает эффектив-

ность использования области выгрузки.

"Сборщик" страниц заполняет список выгруженных страниц, кото-

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

нии списка откачивает их на устройство выгрузки. Нет необходимос-

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

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

"созрели" для этого. В этом видится различие со стратегией выг-

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

ницы одного процесса, вместе с тем метод переписи данных на уст-

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

мы с замещением процессов в разделе 9.1.2. Если на устройстве

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

страницы по отдельности (по одной странице за операцию), что в

конечном итоге обходится недешево. В системе с замещением страниц

фрагментация на устройстве выгрузки выше, чем в системе с замеще-

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

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

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

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

страниц и уменьшает значение счетчика ссылок в соответствующей

записи таблицы pfdata. Если значение счетчика становится равным

0, запись таблицы pfdata помещается в конец списка свободных

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

чение счетчика отлично от 0, это означает, что страница (в ре-

зультате выполнения функции fork) используется совместно несколь-

кими процессами, но ядро все равно выгружает ее. Наконец, ядро

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

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

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

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

процесс обнаружил ее отсутствие, получив соответствующую ошибку,

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

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

если она попала в список "сборщика" страниц.

Предположим, к примеру, что "сборщик" страниц выгружает 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. Выделенные для размещения страниц за две операции

участки области выгрузки могут быть и несмежными. "Сборщик" сох-

раняет оставшиеся 12 страниц процесса D в списке выгружаемых

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

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

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

не нужны использующим их процессам (процессы завершились), в об-

ласти выгрузки освобождается место.

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

памяти две фазы. На первой фазе "сборщик" страниц ищет страницы,

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

мых страниц. На второй фазе ядро копирует страницу на устройство

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

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

значение счетчика ссылок в соответствующей записи таблицы pfdata


Страницы выгружаются группами по 64 страницы

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

│Процесс A 30 стр-ц │ │Процесс B 6 стр-ц │ │Процесс D 12 стр-ц │

│ │ │ │ │ │

│Процесс B 34 стр-цы│ │Процесс C 50 стр-ц│ │ │

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

│Процесс D 8 стр-ц │ L--------------------

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


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

│ │ A 30 B 34 │ │ B 6 C 50 D 8 │ │

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

Устройство выгрузки


Рисунок 9.20. Выделение пространства на устройстве выгрузки в

системе с замещением страниц


и если оно становится равным 0, помещает эту запись в конец спис-

ка свободных страниц. Содержимое физической страницы в памяти не

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

гому процессу.


9.2.3 Отказы при обращениях к страницам


В системе встречаются два типа отказов при обращении к стра-

нице: отказы из-за отсутствия (недоступности) данных и отказы

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

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

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

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

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

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