ГЛАВА 9. АЛГОРИТМЫ УПРАВЛЕНИЯ ПАМЯТЬЮ
Алгоритм планирования использования процессорного времени, рассмотренный
в предыдущей главе, в сильной степени зависит от выбранной стратегии управ-
ления памятью. Процесс может выполняться, если он хотя бы частично присутст-
вует в основной памяти; ЦП не может исполнять процесс, полностью выгруженный
во внешнюю память. Тем не менее, основная память - чересчур дефицитный ре-
сурс, который зачастую не может вместить все активные процессы в системе.
Если, например, в системе имеется основная память объемом 8 Мбайт, то девять
процессов размером по 1 Мбайту каждый уже не смогут в ней одновременно поме-
щаться. Какие процессы в таком случае следует размещать в памяти (хотя бы
частично), а какие нет, решает подсистема управления памятью, она же управ-
ляет участками виртуального адресного пространства процесса, не резидентными
в памяти. Она следит за объемом доступного пространства основной памяти и
имеет право периодически переписывать процессы на устройство внешней памяти,
именуемое устройством выгрузки, освобождая в основной памяти дополнительное
место. Позднее ядро может вновь поместить данные с устройства выгрузки в ос-
новную память.
В ранних версиях системы UNIX процессы переносились между основной па-
мятью и устройством выгрузки целиком и, за исключением разделяемой области
команд, отдельные независимые части процесса не могли быть объектами переме-
щения. Такая стратегия управления памятью называется свопингом (подкачкой).
Такую стратегию имело смысл реализовывать на машине типа PDP-11, где макси-
мальный размер процесса составлял 64 Кбайта. При использовании этой страте-
гии размер процесса ограничивается объемом физической памяти, доступной в
системе. Система BSD (версия 4.0) явилась главным полигоном для применения
другой стратегии, стратегии "подкачки по обращению" (demand paging), в соот-
ветствии с которой основная память обменивается с внешней не процессами, а
страницами памяти; эта стратегия поддерживается и в последних редакциях вер-
сии V системы UNIX. Держать в основной памяти весь выполняемый процесс нет
необходимости, и ядро загружает в память только отдельные страницы по запро-
су выполняющегося процесса, ссылающегося на них. Преимущество стратегии под-
качки по обращению состоит в том, что благодаря ей отображение виртуального
адресного пространства процесса на физическую память машины становится более
гибким: допускается превышение размером процесса объема доступной физической
памяти и одновременное размещение в основной памяти большего числа процес-
сов. Преимущество стратегии свопинга состоит в простоте реализации и облег-
чении "надстроечной" части системы. Обе стратегии управления памятью расс-
матриваются в настоящей главе.
Описание алгоритма свопинга можно разбить на три части: управление прос-
транством на устройстве выгрузки, выгрузка процессов из основной памяти и
подкачка процессов в основную память.
9.1.1 Управление пространством на устройстве выгрузки
Устройство выгрузки является устройством блочного типа, которое предс-
тавляет собой конфигурируемый раздел диска. Тогда как обычно ядро выделяет
место для файлов по одному блоку за одну операцию, на устройстве выгрузки
253
пространство выделяется группами смежных блоков. Пространство, выделяемое
для файлов, используется статическим образом; поскольку схема назначения
пространства под файлы действует в течение длительного периода времени, ее
гибкость понимается в смысле сокращения числа случаев фрагментации и, следо-
вательно, объемов неиспользуемого пространства в файловой системе. Выделение
пространства на устройстве выгрузки, напротив, является временным, в сильной
степени зависящим от механизма диспетчеризации процессов. Процесс, размещае-
мый на устройстве выгрузки, в конечном итоге вернется в основную память, ос-
вобождая место на внешнем устройстве. Поскольку время является решающим фак-
тором и с учетом того, что ввод-вывод данных за одну мультиблочную операцию
происходит быстрее, чем за несколько одноблочных операций, ядро выделяет на
устройстве выгрузки непрерывное пространство, не беря во внимание возможную
фрагментацию.
Так как схема выделения пространства на устройстве выгрузки отличается
от схемы, используемой для файловых систем, структуры данных, регистрирующие
свободное пространство, должны также отличаться. Пространство, свободное в
файловых системах, описывается с помощью связного списка свободных блоков,
доступ к которому осуществляется через суперблок файловой системы, информа-
ция о свободном пространстве на устройстве выгрузки собирается в таблицу,
именуемую "карта памяти устройства". Карты памяти, помимо устройства выгруз-
ки, используются и другими системными ресурсами (например, драйверами неко-
торых устройств), они дают возможность распределять память устройства (в ви-
де смежных блоков) по методу первого подходящего.
Каждая строка в карте памяти состоит из адреса распределяемого ресурса и
количества доступных единиц ресурса; ядро интерпретирует элементы строки в
соответствии с типом карты. В самом начале карта памяти состоит из одной
строки, содержащей адрес и общее количество ресурсов. Если карта описывает
распределение памяти на устройстве выгрузки, ядро трактует каждую единицу
ресурса как группу дисковых блоков, а адрес - как смещение в блоках от нача-
ла области выгрузки. Первоначальный вид карты памяти для устройства выгруз-
ки, состоящего из 10000 блоков с начальным адресом, равным 1, показан на Ри-
сунке 9.1. Выделяя и освобождая ресурсы,
ядро корректирует карту памяти, заботясь о том, чтобы в ней постоянно содер-
жалась точная информация о свободных ресурсах в системе.
На Рисунке 9.2 представлен алгоритм выделения пространства с помощью
карт памяти (malloc). Ядро просматривает карту в поисках первой строки, со-
держащей количество единиц ресурса, достаточное для удовлетворения запроса.
Если запрос покрывает все количество единиц, содержащееся в строке, ядро
удаляет строку и уплотняет карту (то есть в карте становится на одну строку
меньше). В противном случае ядро переустанавливает адрес и число оставшихся
единиц в строке в соответствии с числом единиц, выделенных по запросу. На
Рисунке 9.3 показано, как меняется вид карты памяти для устройства выгрузки
после выделения 100, 50 и вновь 100 единиц ресурса. В конечном итоге карта
памяти принимает вид, показывающий, что первые 250 единиц ресурса выделены
по запросам, и что теперь остались свободными 9750 единиц, начиная с адреса
251.
Адрес Число единиц ресурса
+------------------------------------+
| 1 10000 |
+------------------------------------+
Рисунок 9.1. Первоначальный вид карты памяти для устройства выгрузки
254
+------------------------------------------------------------+
| алгоритм malloc /* алгоритм выделения пространства с ис-|
| пользованием карты памяти */ |
| входная информация: (1) адрес /* указывает на тип ис- |
| пользуемой карты */ |
| (2) требуемое число единиц ресурса |
| выходная информация: адрес - в случае успешного завершения |
| 0 - в противном случае |
| { |
| для (каждой строки карты) |
| { |
| если (требуемое число единиц ресурса располагается в |
| строке карты) |
| { |
| если (требуемое число == числу единиц в строке) |
| удалить строку из карты; |
| в противном случае |
| отрегулировать стартовый адрес в строке; |
| вернуть (первоначальный адрес строки); |
| } |
| } |
| вернуть (0); |
| } |
+------------------------------------------------------------+
Рисунок 9.2. Алгоритм выделения пространства с помощью карт памяти
Освобождая ресурсы, ядро ищет для них соответствующее место в карте по
адресу. При этом возможны три случая:
Адрес Число единиц ресурса Адрес Число единиц ресурса
+------------------------------+ +------------------------------+
| 1 10000 | | 101 9900 |
+------------------------------+ +------------------------------+
(а) (б)
Адрес Число единиц ресурса Адрес Число единиц ресурса
+------------------------------+ +------------------------------+
| 151 9850 | | 251 9750 |
+------------------------------+ +------------------------------+
(в) (г)
Рисунок 9.3. Выделение пространства на устройстве выгрузки
1. Освободившиеся ресурсы полностью закрывают пробел в карте памяти. Други-
ми словами, они имеют смежные адреса с адресами ресурсов из строк, не-
посредственно предшествующей и следующей за данной. В этом случае ядро
объединяет вновь освободившиеся ресурсы с ресурсами из указанных строк в
одну строку карты памяти.
2. Освободившиеся ресурсы частично закрывают пробел в карте памяти. Если
они имеют адрес, смежный с адресом ресурсов из строки, непосредственно
предшествующей или непосредственно следующей за данной (но не с адресами
из обеих строк), ядро переустанавливает значение адреса и числа ресурсов
в соответствующей строке с учетом вновь освободившихся ресурсов. Число
строк в карте памяти остается неизменным.
3. Освободившиеся ресурсы частично закрывают пробел в карте памяти, но их
255
адреса не соприкасаются с адресами каких-либо других ресурсов карты. Яд-
ро создает новую строку и вставляет ее в соответствующее место в карте.
Возвращаясь к предыдущему примеру, отметим, что если ядро освобождает 50
единиц ресурса, начиная с адреса 101, в карте памяти появится новая строка,
поскольку освободившиеся ресурсы имеют адреса, не соприкасающиеся с адресами
существующих строк карты. Если же затем ядро освободит 100 единиц ресурса,
начиная с адреса 1, первая строка карты будет расширена, поскольку освобо-
дившиеся ресурсы имеют адрес, смежный с адресом первой строки. Эволюция сос-
тояний карты памяти для данного случая показана на Рисунке 9.4.
Предположим, что ядру был сделан запрос на выделение 200 единиц (блоков)
пространства устройства выгрузки. Поскольку первая строка карты содержит ин-
формацию только о 150 единицах, ядро привлекает для удовлетворения запроса
информацию из второй строки (см. Рисунок 9.5). Наконец, предположим, что яд-
ро освобождает 350
Адрес Число единиц ресурса Адрес Число единиц ресурса
+------------------------------+ +------------------------------+
| 251 9750 | | 101 50 |
+------------------------------+ +------------------------------+
| 251 9750 |
(а) +------------------------------+
(б)
Адрес Число единиц ресурса
+------------------------------+
| 1 150 |
+------------------------------+
| 251 9750 |
+------------------------------+
(в)
Рисунок 9.4. Освобождение пространства на устройстве выгрузки
Адрес Число единиц ресурса Адрес Число единиц ресурса
+------------------------------+ +------------------------------+
| 1 150 | | 1 150 |
+------------------------------+ +------------------------------+
| 251 9750 | | 451 9550 |
+------------------------------+ +------------------------------+
(а) (б)
Рисунок 9.5. Выделение пространства на устройстве выгрузки,
описанного во второй строке карты памяти
единиц пространства, начиная с адреса 151. Несмотря на то, что эти 350 еди-
ниц были выделены ядром в разное время, не существует причины, по которой
ядро не могло бы освободить их все сразу. Ядро узнает о том, что освободив-
шиеся ресурсы полностью закрывают разрыв между первой и второй строками кар-
ты, и вместо прежних двух создает одну строку, в которую включает и освобо-
дившиеся ресурсы.
В традиционной реализации системы UNIX используется одно устройство выг-
рузки, однако в последних редакциях версии V допускается уже наличие множес-
256
тва устройств выгрузки. Ядро выбирает устройство выгрузки по схеме "кольце-
вого списка" при условии, что на устройстве имеется достаточный объем непре-
рывного адресного пространства. Администраторы могут динамически создавать и
удалять из системы устройства выгрузки. Если устройство выгрузки удаляется
из системы, ядро не выгружает данные на него; если же данные подкачиваются с
удаляемого устройства, сначала оно опорожняется и только после освобождения
принадлежащего устройству пространства устройство может быть удалено из сис-
темы.
Ядро выгружает процесс, если испытывает потребность в свободной памяти,
которая может возникнуть в следующих случаях:
1. Произведено обращение к системной функции fork, которая должна выделить
место в памяти для процесса-потомка.
2. Произведено обращение к системной функции brk, увеличивающей размер про-
цесса.
3. Размер процесса увеличился в результате естественного увеличения стека
процесса.
4. Ядру нужно освободить в памяти место для подкачки ранее выгруженных про-
цессов.
Обращение к системной функции fork выделено в особую ситуацию, поскольку
это единственный случай, когда пространство памяти, ранее занятое процессом
(родителем), не освобождается.
Когда ядро принимает решение о том, что процесс будет выгружен из основ-
ной памяти, оно уменьшает значение счетчика ссылок, ассоциированного с каж-
дой областью процесса, и выгружает те области, у которых счетчик ссылок стал
равным 0. Ядро выделяет место на устройстве выгрузки и блокирует процесс в
памяти (в случаях 1-3), запрещая его выгрузку (см. упражнение 9.12) до тех
пор, пока не закончится текущая операция выгрузки. Адрес места выгрузки об-
ластей ядро сохраняет в соответствующих записях таблицы областей.
За одну операцию ввода-вывода, в которой участвуют устройство выгрузки и
адресное пространство задачи и которая осуществляется через буферный кеш,
ядро выгружает максимально-возможное количество данных. Если аппаратура не в
состоянии передать за одну операцию содержимое нескольких страниц памяти,
перед программами ядра встает задача осуществить передачу содержимого памяти
за несколько шагов по одной странице за каждую операцию. Таким образом, точ-
ная скорость и механизм передачи данных определяются, помимо всего прочего,
возможностями дискового контроллера и стратегией распределения памяти. Нап-
ример, если используется страничная организация памяти, существует вероят-
ность, что выгружаемые данные занимают несмежные участки физической памяти.
Ядро обязано собирать информацию об адресах страниц с выгружаемыми данными,
которую впоследствии использует дисковый драйвер, осуществляющий управление
процессом ввода-вывода. Перед тем, как выгрузить следующую порцию данных,
программа подкачки (выгрузки) ждет завершения предыдущей операции ввода-вы-
вода.
При этом перед ядром не встает задача переписать на устройство выгрузки
содержимое виртуального адресного пространства процесса полностью. Вместо
этого ядро копирует на устройство выгрузки содержимое физической памяти, от-
веденной процессу, игнорируя неиспользуемые виртуальные адреса. Когда ядро
подкачивает процесс обратно в память, оно имеет у себя карту виртуальных ад-
ресов процесса и может переназначить процессу новые адреса. Ядро считывает
копию процесса из буферного кеша в физическую память, в те ячейки, для кото-
рых установлено соответствие с виртуальными адресами процесса.
На Рисунке 9.6 приведен пример отображения образа процесса в памяти на
адресное пространство устройства выгрузки (*). Процесс располагает тремя об-
ластями: команд, данных и стека. Область команд заканчивается на виртуальном
257
---------------------------------------
(*) Для простоты виртуальное адресное пространство процесса на этом и на
всех последующих рисунках изображается в виде линейного массива точек
входа в таблицу страниц, не принимая во внимание тот факт, что каждая
область обычно имеет свою отдельную таблицу страниц.
Расположение виртуальных адресов Устройство выгрузки
Виртуальные, физические адреса
+----------------------+ +-----------------+
Область | 0 278К ----+-------684--+---> |
команд +----------------------+ +-----------------+
| 1К 432К ----+------------+---> |
+----------------------+ +-----------------+
| пусто | +--------+---> |
+----------------------+ - +-----------------+
| - | -+-------+---> |
| - | -- +-----------------+
| - | --+------+---> |
+----------------------+ --- +-----------------+
Область | 64К 573К ----+---+-- +----+---> |
данных +----------------------+ -- - +-----------------+
| 65К 647К ----+----+- 690 | |
+----------------------+ - - +-----------------+
| 66К 595К ----+-----+ -
+----------------------+ -
| пусто | -
+----------------------+ -
| - | -
| - | -
+----------------------+ -
Область |128К 401К ----+-------+
стека +----------------------+
| пусто |
+----------------------+
Рисунок 9.6. Отображение пространства процесса на устройство выгрузки
адресе 2К, а область данных начинается с адреса 64К, таким образом в вирту-
альном адресном пространстве образовался пропуск в 62 Кбайта. Когда ядро
выгружает процесс, оно выгружает содержимое страниц памяти с адресами 0, 1К,
64К, 65К, 66К и 128К; на устройстве выгрузки не будет отведено место под
пропуск в 62 Кбайта между областями команд и данных, как и под пропуск в 61
Кбайт между областями данных и стека, ибо пространство на устройстве выгруз-
ки заполняется непрерывно. Когда ядро загружает процесс обратно в память,
оно уже знает из карты памяти процесса о том, что процесс имеет в своем
пространстве неиспользуемый участок размером 62К, и с учетом этого соответс-
твенно выделяет физическую память. Этот случай проиллюстрирован с помощью
Рисунка 9.7. Сравнение Рисунков 9.6 и 9.7 показывает, что физические адреса,
занимаемые процессом до и после выгрузки, не
совпадают между собой; однако, на пользовательском уровне процесс не обраща-
ет на это никакого внимания, поскольку содержимое его виртуального простран-
ства осталось тем же самым.
Теоретически все пространство памяти, занятое процессом, в том числе его
личное адресное пространство и стек ядра, может быть выгружено, хотя ядро и
может временно заблокировать область в памяти на время выполнения критичес-
кой операции. Однако практически, ядро не выгружает содержимое адресного
258
Расположение виртуальных адресов Устройство выгрузки
Виртуальные, физические адреса
+----------------------+ +-----------------+
Область | 0 401К <---+-------684--+---- |
команд +----------------------+ +-----------------+
| 1К 370К <---+------------+---- |
+----------------------+ +-----------------+
| пусто | +--------+---- |
+----------------------+ - +-----------------+
| - | -+-------+---- |
| - | -- +-----------------+
| - | --+------+---- |
+----------------------+ --- +-----------------+
Область | 64К 788К <---+---+-- +----+---- |
данных +----------------------+ -- - +-----------------+
| 65К 492К <---+----+- 690 | |
+----------------------+ - - +-----------------+
| 66К 647К <---+-----+ -
+----------------------+ -
| пусто | -
+----------------------+ -
| - | -
| - | -
+----------------------+ -
Область |128К 955К <---+-------+
стека +----------------------+
| пусто |
+----------------------+
Рисунок 9.7. Загрузка процесса в память
пространства процесса, если в нем находятся таблицы преобразования адресов
(адресные таблицы) процесса. Практическими соображениями так же диктуются
условия, при которых процесс может выгрузить самого себя или потребовать
своей выгрузки другим процессом (см. упражнение 9.4).
9.1.2.1 Выгрузка при выполнении системной функции fork
В описании системной функции fork (раздел 7.1) предполагалось, что про-
цесс-родитель получил в свое распоряжение память, достаточную для создания
контекста потомка. Если это условие не выполняется, ядро выгружает процесс
из памяти, не освобождая пространство памяти, занимаемое его (родителя) ко-
пией. Когда процедура выгрузки завершится, процесс-потомок будет распола-
гаться на устройстве выгрузки; процесс-родитель переводит своего потомка в
состояние "готовности к выполнению" (см. Рисунок 6.1) и возвращается в режим
задачи. Поскольку процесс-потомок находится в состоянии "готовности к выпол-
нению", программа подкачки в конце концов загрузит его в память, где ядро
запустит его на выполнение; потомок завершит тем самым свою роль в выполне-
нии системной функции fork и вернется в режим задачи.
9.1.2.2 Выгрузка с расширением
Если процесс испытывает потребность в дополнительной физической памяти,
либо в результате расширения стека, либо в результате запуска функции brk, и
если эта потребность превышает доступные резервы памяти, ядро выполняет опе-
рацию выгрузки процесса с расширением его размера на устройстве выгрузки. На
устройстве выгрузки ядро резервирует место для размещения процесса с учетом
259
Первоначальное Расширенный
расположение формат
Виртуальные, Виртуальные, Устройство
физические адреса физические адреса выгрузки
+------------+ +------------+ +---------+
Область| 0 278К | | 0 278К -+-----684--+---> |
команд +------------+ +------------+ +---------+
| 1К 432К | | 1К 432К -+----------+---> |
+------------+ +------------+ +---------+
| пусто | | пусто | +--------+---> |
+------------+ +------------+ - +---------+
| - | | - | -+-------+---> |
| - | | - | -- +---------+
| - | | - | --+------+---> |
+------------+ +------------+ --- +---------+
Область| 64К 573К | | 64К 573К -+-+-- +----+---> |
данных +------------+ +------------+ -- - +---------+
| 65К 647К | | 65К 647К -+--+- 690 | |
+------------+ +------------+ - - +---------+
| 66К 595К | | 66К 595К -+---+ 691 +|---> |
+------------+ +------------+ - -+---------+
| пусто | | пусто | - -
+------------+ +------------+ - -
| - | | - | - -
| - | | - | - -
+------------+ +------------+ - -
Область|128К 401К | |128К 401К -+-----+ -
стека +------------+ +------------+ -
| пусто | Новая |129К ... -+---------+
+------------+ страница+------------+
| пусто |
+------------+
Рисунок 9.8. Перенастройка карты памяти в случае выгрузки с расширением
расширения его размера. Затем производится перенастройка таблицы преобразо-
вания адресов процесса с учетом дополнительного виртуального пространства,
но без выделения физической памяти (в связи с ее отсутствием). Наконец, ядро
выгружает процесс, выполняя процедуру выгрузки обычным порядком и обнуляя
вновь выделенное пространство на устройстве (см. Рисунок 9.8). Когда нес-
колько позже ядро будет загружать процесс обратно в память, физическое прос-
транство будет выделено уже с учетом нового состояния таблицы преобразования
адресов. В момент возобновления у процесса уже будет в распоряжении память
достаточного объема.
9.1.3 Загрузка (подкачка) процессов
Нулевой процесс (процесс подкачки) является единственным процессом, заг-
ружающим другие процессы в память с устройств выгрузки. Процесс подкачки на-
чинает работу по выполнению этой своей единственной функции по окончании
инициализации системы (как уже говорилось в разделе 7.9). Он загружает про-
цессы в память и, если ему не хватает места в памяти, выгружает оттуда неко-
торые из процессов, находящихся там. Если у процесса подкачки нет работы
(например, отсутствуют процессы, ожидающие загрузки в память) или же он не в
состоянии выполнить свою работу (ни один из процессов не может быть выгру-
жен), процесс подкачки приостанавливается; ядро периодически возобновляет
260
его выполнение. Ядро планирует запуск процесса подкачки точно так же, как
делает это в отношении других процессов, ориентируясь на более высокий прио-
ритет, при этом процесс подкачки выполняется только в режиме ядра. Процесс
подкачки не обращается к функциям операционной системы, а использует в своей
работе только внутренние функции ядра; он является архетипом всех процессов
ядра.
Как уже вкратце говорилось в главе 8, программа обработки прерываний по
таймеру измеряет время нахождения каждого процесса в памяти или в состоянии
выгрузки. Когда процесс подкачки возобновляет свою работу по загрузке про-
цессов в память, он просматривает все процессы, находящиеся в состоянии "го-
товности к выполнению, будучи выгруженными", и выбирает из них один, который
находится в этом состоянии дольше остальных (см. Рисунок 9.9). Если имеется
достаточно свободной памяти, процесс подкачки загружает выбранный процесс,
выполняя операции в последовательности, обратной выгрузке процесса. Сначала
выделяется физическая память, затем с устройства выгрузки считывается нужный
процесс и освобождается место на устройстве.
Если процесс подкачки выполнил процедуру загрузки успешно, он вновь
просматривает совокупность выгруженных, но готовых к выполнению процессов в
поисках следующего процесса, который предполагается загрузить в память, и
повторяет указанную последовательность действий. В конечном итоге возникает
одна из следующих ситуаций:
* На устройстве выгрузки больше нет ни одного процесса, готового к выпол-
нению. Процесс подкачки приостанавливает свою работу до тех пор, пока не
возобновится процесс на устройстве выгрузки или пока ядро не выгрузит
процесс, готовый к выполнению. (Вспомним диаграмму состояний на Рисунке
6.1).
* Процесс подкачки обнаружил процесс, готовый к загрузке, но в системе не-
достаточно памяти для его размещения. Процесс подкачки пытается загру-
зить другой процесс и в случае успеха перезапускает алгоритм подкачки,
продолжая поиск загружаемых процессов.
Если процессу подкачки нужно выгрузить процесс, он просматривает все
процессы в памяти. Прекратившие свое существование процессы не подходят для
выгрузки, поскольку они не занимают физическую память; также не могут быть
выгружены процессы, заблокированные в памяти, например, выполняющие операции
над областями. Ядро предпочитает выгружать приостановленные процессы, пос-
кольку процессы, готовые к выполнению, имеют больше шансов быть вскоре выб-
ранными на выполнение. Решение о выгрузке процесса принимается ядром на ос-
новании его приоритета и продолжительности его пребывания в памяти. Если в
памяти нет ни одного приостановленного процесса, решение о том, какой из
процессов, готовых к выполнению, следует выгрузить, зависит от значения,
присвоенного процессу функцией nice, а также от продолжительности пребывания
процесса в памяти.
Процесс, готовый к выполнению, должен быть резидентным в памяти в тече-
ние по меньшей мере 2 секунд до того, как уйти из нее, а процесс, загружае-
мый в память, должен по меньшей мере 2 секунды пробыть на устройстве выгруз-
ки. Если процесс подкачки не может найти ни одного процесса, подходящего для
выгрузки, или ни одного процесса, подходящего для загрузки, или ни одного
процесса, перед выгрузкой не менее 2 секунд (**) находившегося в памяти, он
приостанавливает свою работу по причине того, что ему нужно загрузить про-
цесс в память, а в памяти нет места для его размещения. В этой ситуации тай-
мер возобновляет выполнение процесса подкачки через каждую секунду. Ядро
---------------------------------------
(**) В версии 6 системы UNIX процесс не может быть выгружен из памяти с
целью расчистки места для загружаемого процесса до тех пор, пока загру-
жаемый процесс не проведет на диске 3 секунды. Уходящий из памяти про-
цесс должен провести в памяти не менее 2 секунд. Временной интервал та-
ким образом делится на части, в результате чего повышается производи-
тельность системы.
261
+------------------------------------------------------------+
| алгоритм swapper /* загрузка выгруженных процессов, |
| * выгрузка других процессов с целью |
| * расчистки места в памяти */ |
| входная информация: отсутствует |
| выходная информация: отсутствует |
| { |
| loop: |
| для (всех выгруженных процессов, готовых к выполнению)|
| выбрать процесс, находящийся в состоянии выгружен-|
| ности дольше остальных; |
| если (таких процессов нет) |
| { |
| приостановиться (до момента, когда возникнет необ-|
| ходимость в загрузке процессов); |
| перейти на loop; |
| } |
| если (в основной памяти достаточно места для размеще- |
| ния процесса) |
| { |
| загрузить процесс; |
| перейти на loop; |
| } |
| /* loop2: сюда вставляются исправления, внесенные в алго- |
| * ритм */ |
| для (всех процессов, загруженных в основную память, |
| кроме прекративших существование и заблокированных в |
| памяти) |
| { |
| если (есть хотя бы один приостановленный процесс) |
| выбрать процесс, у которого сумма приоритета и|
| продолжительности нахождения в памяти наи- |
| большая; |
| в противном случае /* нет ни одного приостанов- |
| * ленного процесса */ |
| выбрать процесс, у которого сумма продолжи- |
| тельности нахождения в памяти и значения nice|
| наибольшая; |
| } |
| если (выбранный процесс не является приостановленным |
| или не соблюдены условия резидентности) |
| приостановиться (до момента, когда появится воз- |
| можность загрузить процесс); |
| в противном случае |
| выгрузить процесс; |
| перейти на loop; /* на loop2 в исправленном алгорит-|
| * ме */ |
| } |
+------------------------------------------------------------+
Рисунок 9.9. Алгоритм подкачки
также возобновляет работу процесса подкачки в том случае, когда один из про-
цессов переходит в состояние приостанова, так как последний может оказаться
более подходящим для выгрузки процессом по сравнению с ранее рассмотренными.
Если процесс подкачки расчистил место в памяти или если он был приостановлен
по причине невозможности сделать это, он возобновляет свою работу с переза-
пуска алгоритма подкачки (с самого его начала), вновь предпринимая попытку
262
загрузить ожидающие выполнения процессы.
На Рисунке 9.10 показана динамика выполнения пяти процессов с указанием
моментов их участия в реализации алгоритма подкачки. Положим для простоты,
что все процессы интенсивно используют ресурсы центрального процессора и что
они не производят обращений к системным функциям; следовательно, переключе-
ние контекста происходит только в результате возникновения прерываний по
таймеру с интервалом в 1 секунду. Процесс подкачки исполняется с наивысшим
приоритетом планирования, поэтому он всегда укладывается в секундный интер-
вал, когда ему есть что делать. Предположим далее, что процессы имеют одина-
ковый размер и что в основной памяти могут одновременно поместиться только
два процесса. Сначала в памяти находятся процессы A и B, остальные процессы
выгружены. Процесс подкачки не может стронуть с места ни один процесс в те-
чение первых двух секунд, поскольку этого требует условие нахождения переме-
щаемого процесса в течение этого интервала на одном месте (в памяти или на
устройстве выгрузки), однако по истечении 2 секунд процесс подкачки выгружа-
ет процессы A и B и загружает на их место процессы C и D. Он пытается также
загрузить и процесс E, но терпит неудачу, поскольку в основной памяти недос-
таточно места для этого. На 3-секундной отметке процесс E все еще годен для
загрузки, поскольку он находился все 3 секунды на устройстве выгрузки, но
процесс подкачки не может выгрузить из памяти ни один из процессов, ибо они
находятся в памяти менее 2 секунд. На 4-секундной отметке процесс подкачки
выгружает процессы C и D и загружает вместо них процессы E и A.
Процесс подкачки выбирает процессы для загрузки, основываясь на продол-
жительности их пребывания на устройстве выгрузки. В качестве другого крите-
рия может применяться более высокий приоритет загружаемого процесса по срав-
нению с остальными, готовыми к выполнению процессами, поскольку такой про-
цесс более предпочтителен для запуска. Практика показала, что такой подход
"несколько" повышает пропускную способность системы в условиях сильной заг-
руженности (см. [Peachey 84]).
Алгоритм выбора процесса для выгрузки из памяти с целью освобождения
места требуемого объема имеет, однако, более серьезные изъяны. Во-первых,
процесс подкачки производит выгрузку на основании приоритета, продолжитель-
ности нахождения в памяти и значения nice. Несмотря на то, что он производит
выгрузку процесса с единственной целью - освободить в памяти место для заг-
ружаемого процесса, он может выгрузить и процесс, который не освобождает
место требуемого размера. Например, если процесс подкачки пытается загрузить
в память процесс размером 1 Мбайт, а в системе отсутствует свободная память,
будет далеко не достаточно выгрузить процесс, занимающий только 2 Кбайта па-
мяти. В качестве альтернативы может быть предложена стратегия выгрузки групп
процессов при условии, что они освобождают место, достаточное для размещения
загружаемых процессов.Эксперименты с использованием машины PDP 11/23 показа-
ли,что в условиях сильной загруженности такая стратегия может увеличить про-
изводительность системы почти на 10 процентов (см. [Peachey 84]).
Во-вторых, если процесс подкачки приостановил свою работу изза того, что
в памяти не хватило места для загрузки процесса, после возобновления он
вновь выбирает процесс для загрузки в память, несмотря на то, что ранее им
уже был сделан выбор. Причина такого поведения заключается в том, что за
прошедшее время в состояние готовности к выполнению могли перейти другие
выгруженные процессы, более подходящие для загрузки в память по сравнению с
ранее выбранным процессом. Однако от этого мало утешения для ранее выбранно-
го процесса, все еще пытающегося загрузиться в память. В некоторых реализа-
циях процесс подкачки стремится к тому, чтобы перед загрузкой в память одно-
го крупного процесса выгрузить большое количество процессов маленького раз-
мера, это изменение в базовом алгоритме подкачки отражено в комментариях к
алгоритму (Рисунок 9.9).
В-третьих, если процесс подкачки выбирает для выгрузки процесс, находя-
щийся в состоянии "готовности к выполнению", не исключена возможность того,
что этот процесс после загрузки в память ни разу не был запущен на исполне-
ние. Этот случай показан на Рисунке 9.11, из которого видно, что ядро загру-
263
жает процесс D на 2- секундной отметке, запускает процесс C, а затем на
3-секундной отметке процесс D выгружается в пользу процесса E (уступая пос-
леднему в значении nice), несмотря на то, что процессу D так и не был пре-
доставлен ЦП. Понятно, что такая ситуация является нежелательной.
Следует упомянуть еще об одной опасности. Если при попытке выгрузить
процесс на устройстве выгрузки не будет найдено свободное место, в системе
может возникнуть тупиковая ситуация, при которой: все процессы в основной
Время Процесс A B C D E
--+--------------+-----------+-----------+-----------+-----------
0| 0 | 0 | выгружен | выгружен | выгружен
| запущен | | 0 | 0 | 0
| | | | |
| | | | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 1
1| | запущен | | |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 2 | 2 | 2 | 2
2| выгружен | выгружен | загружен | загружен |
| 0 | 0 | 0 | 0 |
| | | запущен | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 3
3| | | | запущен |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 2 | 2 | 2 | 4
4| загружен | | выгружен | выгружен | загружен
| 0 | | 0 | 0 | 0
| | | | | запущен
| | | | |
| | | | |
--+- 1 | 3 | 1 | 1 | 1
5| запущен | | | |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 4 | 2 | 2 | 2
6| выгружен | загружен | загружен | | выгружен
| 0 | 0 | 0 | | 0
| | запущен | | |
| | | | |
v
Рисунок 9.10. Последовательность операций, выполняемых
процессом подкачки
264
Время Процесс A B C D E
--+--------------+-----------+-----------+-----------+-----------
0| 0 | 0 | выгружен | nice 25 | выгружен
| запущен | | 0 | выгружен | 0
| | | | 0 |
| | | | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 1
1| | запущен | | |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 2 | 2 | 2 | 2
2| выгружен | выгружен | загружен | загружен |
| 0 | 0 | 0 | 0 |
| | | запущен | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 3
3| | | | выгружен | загружен
| | | | 0 | 0
| | | | | запущен
| | | | |
| | | | |
--+- 2 | 2 | 2 | 1 | 1
4| загружен | | выгружен | |
| 0 | | 0 | |
| запущен | | | |
| | | | |
| | | | |
--+- 1 | 3 | 1 | 2 | 2
5| | загружен | | | выгружен
| | 0 | | | 0
| | запущен | | |
| | | | |
| | | | |
--+- 2 | 1 | 2 | 3 | 1
6| выгружен | | | загружен |
| 0 | | | 0 |
| | | | запущен |
| | | | |
v
Рисунок 9.11. Загрузка процессов в случае разбивки временных
интервалов на части
памяти находятся в состоянии приостанова, все готовые к выполнению процессы
выгружены, для новых процессов на устройстве выгрузки уже нет места, нет
свободного места и в основной памяти. Эта ситуация разбирается в упражнении
9.5. Интерес к проблемам, связанным с подкачкой процессов, в последние годы
спал в связи с реализацией алгоритмов подкачки страниц памяти.
265
Алгоритм подкачки страниц памяти поддерживается на машинах со страничной
организацией памяти и с ЦП, имеющим прерываемые команды (***). В системах с
подкачкой страниц отсутствуют ограничения на размер процесса, связанные с
объемом доступной физической памяти. Например, в машинах с объемом физичес-
кой памяти 1 и 2 Мбайта могут исполняться процессы размером 4 или 5 Мбайт.
Ограничение на виртуальный размер процесса, связанное с объемом адресуемой
виртуальной памяти, остается в силе и здесь. Поскольку процесс может не по-
меститься в физической памяти, ядру приходится динамически загружать в па-
мять отдельные его части и исполнять их, несмотря на отсутствие остальных
частей. В механизме подкачки страниц все открыто для пользовательских прог-
рамм, за исключением разрешенного процессу виртуального размера.
Процессы стремятся исполнять команды небольшими порциями, которые имену-
ются программными циклами или подпрограммами, используемые ими указатели
группируются в небольшие поднаборы, располагаемые в информационном простран-
стве процесса. В этом состоит суть так называемого принципа "локальности".
Деннингом [Denning 68] было сформулировано понятие рабочего множества про-
цесса как совокупности страниц, использованных процессом в последних n ссыл-
ках на адресное пространство памяти; число n называется окном рабочего мно-
жества. Поскольку рабочее множество процесса является частью от целого, в
основной памяти может поместиться больше процессов по сравнению с теми сис-
темами, где управление памятью базируется на подкачке процессов, что в ко-
нечном итоге приводит к увеличению производительности системы. Когда процесс
обращается к странице, отсутствующей в его рабочем множестве, возникает
ошибка, при обработке которой ядро корректирует рабочее множество процесса,
в случае необходимости подкачивая страницы с внешнего устройства.
На Рисунке 9.12 приведена последовательность используемых процессом ука-
зателей страниц, описывающих рабочие множества с окнами различных размеров
при условии соблюдения алгоритма замещения "стариков" (замещения страниц пу-
тем откачки тех, к которым наиболее долго не было обращений). По мере выпол-
нения процесса его рабочее множество видоизменяется в соответствии с исполь-
зуемыми процессом указателями страниц; увеличение размера окна влечет за со-
бой увеличение рабочего множества и, с другой стороны, сокращение числа оши-
бок в выполнении процесса. Использование неизменного рабочего множества не
практикуется, поскольку запоминание очередности следования указателей стра-
ниц потребовало бы слишком больших затрат. Приблизительное соответствие меж-
ду изменяемым рабочим множеством и пространством процесса достигается путем
установки бита упоминания (reference bit) при обращении к странице памяти, а
также периодическим опросом указателей страниц. Если на страницу была сдела-
на ссылка, эта страница включается в рабочее множество; в противном случае
она "дозревает" в памяти в ожидании своей очереди.
В случае возникновения ошибки из-за обращения к странице, отсутствующей
в рабочем множестве, ядро приостанавливает выполнение процесса до тех пор,
пока страница не будет считана в память и не станет доступной процессу. Ког-
да страница будет загружена, процесс перезапустит ту команду, на которой вы-
полнение процесса было приостановлено из-за ошибки. Таким образом, работа
подсистемы замещения страниц распадается на две части: откачка редко исполь-
зуемых страниц на устройство выгрузки и обработка ошибок из-за отсутствия
нужной страницы. Такое общее толкование механизма замещения страниц, конечно
же, выходит за пределы одной конкретной системы. Оставшуюся часть главы мы
посвятим более детальному рассмотрению особенностей реализации этого меха-
низма в версии V системы UNIX.
---------------------------------------
(***) Если при исполнении команды возникает ошибка, связанная с отсутствием
страницы, после обработки ошибки ЦП обязан перезапустить команду, пос-
кольку промежуточные результаты, полученные к моменту возникновения
ошибки, могут быть утрачены.
266
9.2.1 Структуры данных, используемые подсистемой замещения страниц
Для поддержки функций управления памятью на машинном (низком) уровне и
для реализации механизма замещения страниц ядро использует 4 основные струк-
туры данных: записи таблицы страниц, дескрипторы дисковых блоков, таблицу
содержимого страничных блоков (page frame data table - сокращенно: pfdata) и
таблицу использования области подкачки. Место для таблицы pfdata выделяется
один раз на все время жизни системы, для других же структур страницы памяти
выделяются динамически.
Из главы 6 нам известно, что каждая область располагает своими таблицами
страниц, с помощью которых осуществляется доступ к физической памяти. Каждая
запись таблицы страниц (Рисунок 9.13) состоит из физического адреса страни-
цы, кода защиты, в разрядах которого описываются права доступа процесса к
странице (на чтение, запись и исполнение), а также следующих двоичных полей,
используемых механизмом замещения страниц:
Последователь-
ность указате- Рабочие множества Размеры окон
лей страниц 2 3 4 5
+------------+ +-------+----------+-------------+----------------+
| 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 | - | - |
+------------+ +-------+----------+-------------+----------------+
Рисунок 9.12. Рабочее множество процесса
* бит доступности
* бит упоминания
267
* бит модификации
* бит копирования при записи
* "возраст" страницы
Установка бита доступности свидетельствует о правильности содержимого
страницы памяти, однако из того, что бит доступности выключен, не следует с
необходимостью то, что ссылка на страницу недопустима, в чем мы убедимся
позже. Бит упоминания устанавливается в том случае, если процесс делает
ссылку на страницу, а бит модификации - в том случае, если процесс скоррек-
тировал содержимое страницы. Установка бита копирования при записи, произво-
димая во время выполнения системной функции fork, свидетельствует о том, что
ядру в случае, когда процесс корректирует содержимое страницы, следует соз-
давать ее новую копию. Наконец, "возраст" страницы говорит о продолжитель-
ности ее пребывания в составе рабочего множества процесса. Биты доступности,
копирования при записи и "возраст" страницы устанавливаются ядром, биты упо-
минания и модификации - аппаратным путем; в разделе 9.2.4 рассматриваются
конфигурации, в которых эти возможности не поддерживаются аппаратурой.
+--------+ +->+----------------------+---------------------------+
| | | | | |
| | | +----------------------+---------------------------+
| | | | | |
| | | +----------------------+---------------------------+
| Область| | | | |
| | | +----------------------+---------------------------+
| | | |Записи таблицы страниц|Дескрипторы дисковых блоков|
| ----+-+ +----------------------+---------------------------+
| | | | |
| | +----------------------+---------------------------+
| | | | |
+--------+ +----------------------+---------------------------+
| | |
+----------------------+---------------------------+
| | |
+----------------------+---------------------------+
| | |
+----------------------+---------------------------+
| | |
+----------------------+---------------------------+
Запись таблицы страниц
+-----------------------------+-------+-----+-----+----+-----+---+
| Адрес страницы (физический) |Возраст|Копи-|Моди-|Упо-|До- |За-|
| | |рова-|фика-|ми- |пус- |щи-|
| | |ние |ция |на- |ти- |та |
| | |при | |ние |мость| |
| | |запи-| | | | |
| | |си | | | | |
+-----------------------------+-------+-----+-----+----+-----+---+
Дескриптор дискового блока
+-----------------------+---------------+------------------------+
| Устройство выгрузки | Номер блока | Тип (находится на ус- |
| | | тройстве выгрузки, в |
| | | файле, при обращении |
| | | обнуляется, заполняет- |
| | | ся) |
+-----------------------+---------------+------------------------+
Рисунок 9.13. Записи таблицы страниц и дескрипторы дисковых блоков
268
Каждая запись таблицы страниц связана с дескриптором дискового блока,
описывающим дисковую копию виртуальной страницы (Рисунок 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. Счетчик
ссылок на виртуальную страницу (в записи таблицы использования области под-
качки) свидетельствует о том, что на копию страницы на устройстве выгрузки
269
ссылается только одна запись таблицы страниц.
9.2.1.1 Функция fork в системе с замещением страниц
Как уже говорилось в разделе 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).
9.2.1.2 Функция exec в системе с замещением страниц
Как уже говорилось в главе 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. Выделенные для
размещения страниц за две операции участки области выгрузки могут быть и
несмежными. "Сборщик" сохраняет оставшиеся 12 страниц процесса D в списке
выгружаемых страниц, но не выгружает их до тех пор, пока список не будет за-
полнен до конца. Как только у процессов возникает потребность в подкачке
страниц с устройства выгрузки или если страницы больше не нужны использующим
их процессам (процессы завершились), в области выгрузки освобождается место.
Чтобы подвести итог, выделим в процессе откачки страницы из памяти две
фазы. На первой фазе "сборщик" страниц ищет страницы, подходящие для выгруз-
ки, и помещает их номера в список выгружаемых страниц. На второй фазе ядро
копирует страницу на устройство выгрузки (если на нем имеется место), сбра-
сывает в ноль бит допустимости в соответствующей записи таблицы страниц,
уменьшает значение счетчика ссылок в соответствующей записи таблицы pfdata
Страницы выгружаются группами по 64 страницы
+--------------------+ +-------------------+ +-------------------+
|Процесс A 30 стр-ц | |Процесс B 6 стр-ц | |Процесс D 12 стр-ц |
| | | | | - |
|Процесс B 34 стр-цы| |Процесс C 50 стр-ц| | - |
+--------------------+ | | | - |
- - |Процесс D 8 стр-ц | +-------------------+
- -+-------------------+
- - - -
- - - -
- - - -
- - - -
- - - -
+-------+-------------------+-------+-----------------+----------+
| | A 30 B 34 | | B 6 C 50 D 8 | |
+-------+-------------------+-------+-----------------+----------+
Устройство выгрузки
Рисунок 9.20. Выделение пространства на устройстве выгрузки в
системе с замещением страниц
и если оно становится равным 0, помещает эту запись в конец списка свободных
страниц. Содержимое физической страницы в памяти не изменяется до тех пор,
пока страница не будет переназначена другому процессу.
9.2.3 Отказы при обращениях к страницам
В системе встречаются два типа отказов при обращении к странице: отказы
из-за отсутствия (недоступности) данных и отказы системы защиты. Поскольку
программы обработки прерываний по отказу могут приостанавливать свое выпол-
нение на время считывания страницы с диска в память, эти программы являются
исключением из общего правила, утверждающего невозможность приостанова обра-
ботчиков прерываний. Тем не менее, поскольку программа обработки прерываний
277
по отказу приостанавливается в контексте процесса, породившего фатальную
ошибку памяти, отказ относится к текущему процессу; следовательно, процессы
приостанавливаются не произвольным образом.
9.2.3.1 Обработка прерываний по отказу из-за недоступности данных
Если процесс пытается обратиться к странице, бит доступности для которой
не установлен, он получает отказ из-за отсутствия (недоступности) данных и
ядро запускает программу обработки прерываний по отказу данного типа (Рису-
нок 9.21). Бит доступности не устанавливается ни для тех страниц, которые
располагаются за пределами виртуального адресного пространства процесса, ни
для тех, которые входят в состав этого пространства, но не имеют в настоящий
момент физического аналога в памяти. Фатальная ошибка памяти произошла в ре-
зультате обращения ядра по виртуальному адресу страницы, поэтому ядро выхо-
дит на соответствующую этой странице запись в таблице страниц и дескриптор
дискового блока. Чтобы предотвратить взаимную блокировку, которая может про-
изойти, если "сборщик" попытается выгрузить страницу из памяти, ядро фикси-
рует в памяти область с соответствующей записью таблицы страниц. Если в дес-
крипторе дискового блока отсутствует информация о странице,
сделанная ссылка на страницу является недопустимой и ядро посылает процес-
су-нарушителю сигнал о "нарушении сегментации" (см. Рисунок 7.25). Такой по-
рядок действий совпадает с тем порядком, которого придерживается ядро, когда
процесс обратился по неверному адресу, если не принимать во внимание то обс-
тоятельство, что ядро узнает об ошибке немедленно, так как все "доступные"
страницы являются резидентными в памяти. Если ссылка на страницу сделана
правильно, ядро выделяет физическую страницу в памяти и считывает в нее со-
держимое виртуальной страницы с устройства выгрузки или из исполняемого фай-
ла.
Страница, вызвавшая отказ, находится в одном из пяти состояний:
1. На устройстве выгрузки вне памяти.
2. В списке свободных страниц в памяти.
3. В исполняемом файле.
4. С пометкой "обнуляемая при обращении".
5. С пометкой "заполняемая при обращении".
Рассмотрим каждый случай в подробностях.
Если страница находится на устройстве выгрузки, вне памяти (случай 1),
это означает, что она когда-то располагалась в памяти, но была выгружена от-
туда "сборщиком" страниц. Обратившись к дескриптору дискового блока, ядро
узнает из него номера устройства выгрузки и блока, где расположена страница,
и проверяет, не осталась ли страница в кеше. Ядро корректирует запись табли-
цы страниц так, чтобы она указывала на страницу, которую предполагается счи-
тать в память, включает соответствующую запись таблицы pfdata в хеш-очередь
(облегчая последующую обработку отказа) и считывает страницу с устройства
выгрузки. Допустивший ошибку процесс приостанавливается до момента заверше-
ния ввода-вывода; вместе с ним будут возобновлены все процессы, ожидавшие
загрузки содержимого страницы.
Обратимся к Рисунку 9.22 и в качестве примера рассмотрим запись таблицы
страниц, связанную с виртуальным адресом 66К. Если при обращении к странице
процесс получает отказ из-за недоступности данных, программа обработки отка-
за обращается к дескриптору дискового блока и обнаруживает то, что страница
находится на устройстве выгрузки в блоке с номером 847 (если предположить,
что в системе только одно устройство выгрузки): следовательно, виртуальный
адрес указан верно. Затем программа обработки отказа обращается к кешу, но
не находит информации о дисковом блоке с номером 847. Таким образом, копия
виртуальной страницы в памяти отсутствует и программа обработки отказа долж-
на загрузить ее с устройства выгрузки. Ядро отводит физическую страницу с
номером 1776 (Рисунок 9.23), считывает в нее с устройства выгрузки содержи-
мое виртуальной страницы и перенастраивает запись таблицы страниц на страни-
цу с номером 1776. В завершение ядро корректирует дескриптор дискового бло-
278
+------------------------------------------------------------+
| алгоритм vfault /* обработка отказа из-за отсутствия |
| (недоступности) данных */ |
| входная информация: адрес, по которому получен отказ |
| выходная информация: отсутствует |
| { |
| найти область, запись в таблице страниц, дескриптор дис-|
| кового блока, связанные с адресом, по которому получен |
| отказ, заблокировать область; |
| если (адрес не принадлежит виртуальному адресному прост-|
| ранству процесса) |
| { |
| послать сигнал (SIGSEGV: нарушение сегментации) про- |
| цессу; |
| перейти на out; |
| } |
| если (адрес указан неверно) /* возможно, процесс нахо-|
| дился в состоянии при- |
| останова */ |
| перейти на out; |
| если (страница имеется в кеше) |
| { |
| убрать страницу из кеша; |
| поправить запись в таблице страниц; |
| выполнять пока (содержимое страницы не станет доступ-|
| ным) /* другой процесс получил такой же отказ, |
| * но раньше */ |
| приостановиться; |
| } |
| в противном случае /* страница отсутствует в кеше */|
| { |
| назначить области новую страницу; |
| |
| поместить новую страницу в кеш, откорректировать за- |
| пись в таблице pfdata; |
| если (страница ранее не загружалась в память и имеет |
| пометку "обнуляемая при обращении") |
| очистить содержимое страницы; |
| в противном случае |
| { |
| считать виртуальную страницу с устройства выгруз-|
| ки или из исполняемого файла; |
| приостановиться (до завершения ввода-вывода); |
| } |
| возобновить процессы (ожидающие загрузки содержимого |
| страницы); |
| } |
| установить бит доступности страницы; |
| сбросить бит модификации и "возраст" страницы; |
| пересчитать приоритет процесса; |
| out: снять блокировку с области; |
| } |
+------------------------------------------------------------+
Рисунок 9.21. Алгоритм обработки отказа из-за отсутствия (не-
доступности) данных
279
ка, делая указание о том, что страница загружена, а также запись таблицы
pfdata, отмечая, что на устройстве выгрузки в блоке с номером 847 содержится
дубликат виртуальной страницы.
При обработке отказов из-за недоступности данных ядро не всегда прибега-
ет к выполнению операции ввода-вывода, даже когда из дескриптора дискового
блока видно, что страница загружена (в случае 2). Может случиться так, что
ядро после выгрузки содержимого физической страницы так и не переприсвоило
ее или же какой-то иной процесс в результате отказа загрузил содержимое вир-
туальной страницы в другую физическую страницу. В любом случае программа об-
работки отказа обнаруживает страницу в кеше, в качестве ключа используя но-
мер блока в дескрипторе дискового блока. Она перенастраивает соответствующую
запись в таблице страниц на только что найденную страницу, увеличивает зна-
чение счетчика ссылок на страницу и в случае необходимости убирает страницу
из списка свободных страниц. Предположим, к примеру, что процесс по-
Записи Дескрипторы
таблицы страниц дисковых блоков Страничные блоки
Физи-
ческая Диско-
Виртуаль- стра- Состо- Состо- Стра- вый Счет-
ный адрес ница яние яние Блок ница блок чик
+-----+--------+++-------+---------+ +----+------+----+
0 | | ||| | | | | | |
+-----+--------+++-------+---------+ | | | |
1К | 1648| Недо- |||В файле| 3 | | | | |
| | ступна ||| | | | | | |
+-----+--------+++-------+---------+ | | | |
2К | | ||| | | | | | |
+-----+--------+++-------+---------+ | | | |
3К | Нет | Недо- |||Заполня| 5 | | | | |
| | ступна |||ется | | | | | |
| | |||при об-| | | | | |
| | |||ращении| | | | | |
+-----+--------+++-------+---------+ +----+------+----+
4К | | ||| | | |1036| 387 | 0 |
+-----+--------+++-------+---------+ +----+------+----+
- | | ||| | | | - | | |
- | | ||| | | | - | | |
- | | ||| | | +----+------+----+
- | | ||| | | |1648| 1618 | 1 |
+-----+--------+++-------+---------+ +----+------+----+
64К | 1917| Недо- |||На дис-| 1206 | | - | | |
| | ступна |||ке | | | - | | |
+-----+--------+++-------+---------+ | - | | |
65К | Нет | Недо- |||Обнуля-| | | - | | |
| | ступна |||ется | | | - | | |
| | |||при об-| | | - | | |
| | |||ращении| | | - | | |
+-----+--------+++-------+---------+ +----+------+----+
66К | 1036| Недо- |||На дис-| 847 | |1861| 1206 | 0 |
| | ступна |||ке | | +----+------+----+
+-----+--------+++-------+---------+ | | | |
67К | | ||| | | | | | |
+-----+--------+++-------+---------+ +----+------+----+
Рисунок 9.22. Иллюстрация к отказу из-за недоступности данных
280
лучил отказ при обращении к виртуальному адресу 64К (Рисунок 9.22). Просмат-
ривая кеш, ядро устанавливает, что страничный блок с номером 1861 связан с
дисковым блоком 1206. Ядро перенастраивает запись таблицы страниц с вирту-
альным адресом 64К на страницу с номером 1861, устанавливает бит доступности
и передает управление программе обработки отказа. Таким образом, номер дис-
кового блока связывает вместе записи таблицы страниц и таблицы pfdata, чем и
объясняется его запоминание в обеих таблицах.
Как и ядру, программе обработки отказа не нужно считывать страницу в па-
мять, если какой-то иной процесс уже получил отказ по той же самой странице,
но еще не полностью загрузил ее. Программа находит область с записью таблицы
Записи Дескрипторы
таблицы страниц дисковых блоков Страничные блоки
Физи-
ческая Диско-
Виртуаль- стра- Состо- Состо- Стра- вый Счет-
ный адрес ница яние яние Блок ница блок чик
+-----+--------+++-------+---------+ +----+------+----+
66К | 1776| Доступ-|||На дис-| 847 | |1776| 847 | 1 |
| | на |||ке | | | | | |
+-----+--------+++-------+---------+ +----+------+----+
Рисунок 9.23. Результат загрузки страницы в память
Процесс A Процесс B
+------------------------------------------------------------
| Отказ при обращении к стра- - -
| нице - -
| Виртуальный адрес страницы - -
| верен - -
| Приостанов до завершения - -
| считывания страницы - -
| - - Отказ при обращении к стра-
| - - нице
| - - Виртуальный адрес страницы
| - - верен
| - - Загрузка страницы в память
| - - Приостанов до окончания
| - - загрузки
| - - -
| Выход из приостанова -- - -
| страница в памяти - -
| Страница помечается как - -
| доступная - -
| Выход из приостанова других - -
| процессов - -
| - Выход из приостанова
| Возобновление выполнения - -
| - - -
| - - Возобновление выполнения
| - - -
| - - -
| Время -
v
Рисунок 9.24. Два отказа на одной странице
281
страниц, которую она уже ранее заблокировала. Она дожидается, пока будет за-
кончен цикл обработки предыдущего отказа, после чего обнаруживает, что стра-
ница стала доступной, и завершает свою работу. Эта процедура прослеживается
на Рисунке 9.24.
Если копия страницы находится не на устройстве выгрузки, а в исполняемом
файле (случай 3), ядро загружает страницу из файла. Программа обработки от-
каза обращается к дескриптору дискового блока, ищет соответствующий номер
логического блока внутри файла, содержащего страницу, и индекс, ассоцииро-
ванный с записью таблицы областей. Номер логического блока используется
программой в качестве смещения внутри списка номеров дисковых блоков, присо-
единенного к индексу во время выполнения функции exec. По номеру блока на
диске программа считывает страницу в память. Так, например, дескриптор дис-
кового блока, связанный с виртуальным адресом 1К, показывает, что содержимое
страницы располагается в исполняемом файле, внутри логического блока с номе-
ром 3 (см. Рисунок 9.22).
Если процесс получил отказ при обращении к странице, имеющей пометку
"заполняемая при обращении" или "обнуляемая при обращении" (случаи 4 и 5),
ядро выделяет свободную страницу в памяти и корректирует соответствующую за-
пись таблицы страниц. Если страница "обнуляемая при обращении", ядро также
очищает ее содержимое. В завершение обработки флаги "заполняемая при обраще-
нии" и "обнуляемая при обращении" сбрасываются. Теперь страница находится в
памяти, доступна процессам и ее содержимое не имеет аналогов ни на устройст-
ве выгрузки, ни в файловой системе. Так происходит, если процесс обращается
к страницам с виртуальными адресами 3К и 65К (см. Рисунок 9.22): ни один из
процессов не обращался к этим страницам с тех пор, как файл был запущен на
выполнение функцией exec.
В завершение своей работы программа обработки отказов из-за отсутствия
(недоступности) данных устанавливает бит доступности страницы и сбрасывает
бит модификации. Приоритет процесса при этом пересчитывается, ибо во время
выполнения программы процесс мог приостановить свое выполнение на уровне яд-
ра, получая тем самым по возвращении в режим задачи незаслуженное преимущес-
тво перед другими процессами. И, наконец, возвращаясь в режим задачи, прог-
рамма проверяет, не было ли за время обработки отказа поступления каких-либо
сигналов.
9.2.3.2 Обработка прерываний по отказу системы защиты
Вторым типом отказа, встречающегося при обращении к странице, является
отказ системы защиты, который означает, что процесс обратился к существующей
странице памяти, но судя по разрядам, описывающим права доступа к странице,
доступ к ней со стороны текущего процесса не разрешен. (Вспомним пример,
описывающий попытку процесса произвести запись данных в область команд; см.
Рисунок 7.22). Отказ данного типа имеет место также тогда, когда процесс
предпринимает попытку записать что-то на страницу, для которой во время вы-
полнения системной функции fork был установлен бит копирования при записи.
Ядро должно различать между собой ситуации, когда отказ произошел по причине
того, что страница требует копирования при записи, и когда имело место дейс-
твительно что-то недопустимое.
Программа обработки отказа системы защиты автоматически получает вирту-
альный адрес, по которому произошел отказ, и ведет поиск соответствующей об-
ласти и записи таблицы страниц (Рисунок 9.25). Она блокирует область, чтобы
"сборщик" страниц не мог выгрузить страницу, пока связанный с ней отказ не
будет обработан. Если программа обработки отказа устанавливает, что причиной
отказа послужила установка бита копирования при записи, и если страницу ис-
пользуют сразу несколько процессов, ядро выделяет в памяти новую страницу и
копирует в нее содержимое старой страницы; ссылки других процессов на старую
282
страницу сохраняют свое значение. После копирования и внесения в запись таб-
лицы страниц нового номера страницы ядро уменьшает значение счетчика ссылок
в записи таблицы pfdata, соответствующей старой странице. Вся процедура по-
казана на Рисунке 9.26, где три процесса совместно используют физическую
страницу с номером 828. Процесс B считывает страницу, но поскольку бит копи-
рования при записи установлен, получает отказ системы защиты. Программа об-
работки отказа выделяет страницу с номером 786, копирует в нее содержимое
страницы 828, уменьшает значение счетчика ссылок на скопированную страницу и
перенастраивает соответствующую запись таблицы страниц на страницу с номером
786.
Если бит копирования при записи установлен, но страница используется
только одним процессом, ядро дает процессу возможность воспользоваться физи-
ческой страницей повторно. Оно отключает бит копирования при записи и разры-
вает связь страницы с ее копией на диске (если таковая существует), посколь-
ку не исключена возможность того, что дисковой копией пользуются другие про-
цессы. Затем ядро убирает запись таблицы pfdata из очереди страниц, ибо но-
вая
+------------------------------------------------------------+
| алгоритм pfault /* обработка отказа системы защиты */ |
| входная информация: адрес, по которому получен отказ |
| выходная информация: отсутствует |
| { |
| найти область, запись в таблице страниц, дескриптор дис-|
| кового блока, связанные с адресом, по которому получен |
| отказ, заблокировать область; |
| если (страница недоступна в памяти) |
| перейти на out; |
| если (бит копирования при записи не установлен) |
| перейти на out; /* программная ошибка - сигнал */|
| если (счетчик ссылок на страничный блок > 1) |
| { |
| выделить новую физическую страницу; |
| скопировать в нее содержимое старой страницы; |
| уменьшить значение счетчика ссылок на старый стра- |
| ничный блок; |
| перенастроить запись таблицы страниц на новую физи- |
| ческую страницу; |
| } |
| в противном случае /* убрать страницу, поскольку она |
| * никем больше не используется */ |
| { |
| если (копия страницы имеется на устройстве выгрузки)|
| освободить место на устройстве, разорвать связь|
| со страницей; |
| если (страница находится в хеш-очереди страниц) |
| убрать страницу из хеш-очереди; |
| } |
| в записи таблицы страниц установить бит модификации, |
| сбросить бит копирования при записи; |
| пересчитать приоритет процесса; |
| проверить, не поступали ли сигналы; |
| out: снять блокировку с области; |
| } |
+------------------------------------------------------------+
Рисунок 9.25. Алгоритм обработки отказа системы защиты
283
копия виртуальной страницы располагается не на устройстве выгрузки. Кроме
того, ядро уменьшает значение счетчика ссылок на страницу в таблице исполь-
зования области подкачки, и если это значение становится равным 0, освобож-
дает место на устройстве (см. упражнение 9.11).
Если запись в таблице страниц указывает на то, что страница недоступна,
и ее бит копирования при записи установлен, выступая поводом для отказа сис-
темы защиты, допустим, что система при обращении к странице сначала обраба-
тывает отказ из-за недоступности данных (обратная очередность рассматривает-
ся в упражнении 9.17). Несмотря на это, программа обработки отказа системы
защиты все равно обязана убедиться в доступности страницы, поскольку при ус-
тановке блокировки на область программа может приостановиться, а "сборщик"
страниц тем временем может выгрузить страницу из памяти. Если страница не-
доступна (бит доступности сброшен), программа немедленно завершит работу и
процесс получит отказ из-за недоступности данных. Ядро обработает этот от-
каз, но процесс вновь получит отказ системы защиты. Более чем вероятно, что
заключительный отказ системы защиты будет обработан без каких-либо препятст-
вий и помех, поскольку пройдет довольно значительный период времени, прежде
чем страница достаточно "созреет" для выгрузки из памяти. Описанная последо-
вательность событий показана на Рисунке 9.27.
Запись таблицы страниц - Процесс A
+-----------------------------------------------+
| Страница 828: доступна, копируется при записи +-+
+-----------------------------------------------+ |
|
Запись таблицы страниц - Процесс B | +-----------+
+-----------------------------------------------+ +->| Страничный|
| Страница 828: доступна, копируется при записи +--->| блок 828 |
+-----------------------------------------------+ +->| Счетчик |
| | ссылок 3 |
Запись таблицы страниц - Процесс C | +-----------+
+-----------------------------------------------+ |
| Страница 828: доступна, копируется при записи +-+
+-----------------------------------------------+
(а) Перед тем, как процесс B получил отказ системы защиты
Запись таблицы страниц - Процесс A
+-----------------------------------------------+ +-----------+
| Страница 828: доступна, копируется при записи +-+ | Страничный|
+-----------------------------------------------+ | | блок 828 |
+->| Счетчик |
Запись таблицы страниц - Процесс B +->| ссылок 2 |
+-----------------------------------------------+ | +-----------+
| Страница 828: доступна ++|
+-----------------------------------------------+|| +-----------+
+|->| Страничный|
Запись таблицы страниц - Процесс C | | блок 786 |
+-----------------------------------------------+ | | Счетчик |
| Страница 828: доступна, копируется при записи +-+ | ссылок 1 |
+-----------------------------------------------+ +-----------+
(б) После запуска программы обработки отказа системы защиты
для процесса B
Рисунок 9.26. Отказ системы защиты из-за установки бита копи-
рования при записи
284
Перед завершением программа обработки отказа системы защиты устанавлива-
ет биты модификации и защиты, но сбрасывает бит копирования при записи. Она
пересчитывает приоритет процесса и проверяет, не поступали ли за время ее
работы сигналы, предназначенные процессу, в точности повторяя то, что дела-
ется по завершении обработки отказа из-за недопустимости данных.
Процесс, получающий отказы при
обращении к странице "Сборщик" страниц
+------------------------------------------------------------
| - -
| - Блокирует область
| - -
| Отказ системы защиты -
| Приостанов - область -
| заблокирована -
| - -
| - Выгрузка страницы - бит
| - допустимости сброшен
| - -
| - -
| - Выводит из приостанова
| - процессы, ожидающие
| - снятия с области
| - блокировки
| Выход из приостанова -
| - -
| - -
| Проверка бита доступ- -
| ности - сброшен -
| Выход из программы обра- -
| ботки отказа системы за- -
| щиты -
| - -
| - -
| Отказ из-за недоступ- -
| ности данных -
v
Время
Рисунок 9.27. Взаимодействие отказа системы защиты и отказа
из-за недоступности данных
9.2.4 Замещение страниц на менее сложной технической базе
Наибольшая действенность алгоритмов замещения страниц по запросу (обра-
щению) достигается в том случае, если биты упоминания и модификации устанав-
ливаются аппаратным путем и тем же путем вызывается отказ системы защиты при
попытке записи в страницу, имеющую признак "копирования при записи". Тем не
менее, указанные алгоритмы вполне применимы даже тогда, когда аппаратура
распознает только бит доступности и код защиты. Если бит доступности, уста-
навливаемый аппаратно, дублируется программно-устанавливаемым битом, показы-
вающим, действительно ли страница доступна или нет, ядро могло бы отключить
аппаратно-устанавливаемый бит и проимитировать установку остальных битов
программным путем. Так, например, в машине VAX-11 бит упоминания отсутствует
(см. [Levy 82]). Ядро может отключить аппаратно-устанавливаемый бит доступ-
ности для страницы и дальше работать по следующему плану. Если процесс ссы-
лается на страницу, он получает отказ, поскольку бит доступности сброшен, и
285
в игру вступает программа обработки отказа, исследующая страницу. Поскольку
"программный" бит доступности установлен, ядро знает, что страница действи-
тельно доступна и находится в памяти; оно устанавливает "программный" бит
упоминания и "аппаратный" бит доступности, но ему еще предстоит узнать о
том, что на страницу была сделана ссылка. Последующие ссылки на страницу уже
не встретят отказ, ибо "аппаратный" бит доступности установлен. Когда с ней
будет работать "сборщик" страниц, он вновь сбросит "аппаратный" бит доступ-
ности, вызывая тем самым от-
Аппарат- Программ- Программ- Аппарат- Программ- Программ-
ный бит ный бит ный бит ный бит ный бит ный бит
доступ- доступ- упомина- доступ- доступ- упомина-
ности ности ния ности ности ния
+---------+----------+---------+ +---------+----------+---------+
| Нет | Да | Нет | | Да | Да | Да |
+---------+----------+---------+ +---------+----------+---------+
(а) До модифицирования (б) После модифицирования
страницы страницы
Рисунок 9.28. Имитация установки "аппаратного" бита модифика-
ции программными средствами
казы на все последующие обращения к странице и возвращая систему к началу
цикла. Этот случай показан на Рисунке 9.28.
9.3 СИСТЕМА СМЕШАННОГО ТИПА СО СВОПИНГОМ И ПОДКАЧКОЙ ПО ЗАПРОСУ
Несмотря на то, что в системах с замещением страниц по запросу обращение
с памятью отличается большей гибкостью по сравнению с системами подкачки
процессов, возможно возникновение ситуаций, в которых "сборщик" страниц и
программа обработки отказов из-за недоступности данных начинают мешать друг
другу из-за нехватки памяти. Если сумма рабочих множеств всех процессов пре-
вышает объем физической памяти в машине, программа обработки отказов обычно
приостанавливается, поскольку выделять процессам страницы памяти дальше ста-
новится невозможным. "Сборщик" страниц не сможет достаточно быстро освобо-
дить место в памяти, ибо все страницы принадлежат рабочему множеству. Произ-
водительность системы падает, поскольку ядро тратит слишком много времени на
верхнем уровне, с безумной скоростью перестраивая память.
Ядро в версии V манипулирует алгоритмами подкачки процессов и замещения
страниц так, что проблемы соперничества перестают быть неизбежными. Когда
ядро не может выделить процессу страницы памяти, оно возобновляет работу
процесса подкачки и переводит пользовательский процесс в состояние, эквива-
лентное состоянию "готовности к запуску, будучи зарезервированным". В этом
состоянии одновременно могут находиться несколько процессов. Процесс подкач-
ки выгружает один за другим целые процессы, пока объем доступной памяти в
системе не превысит верхнюю отметку. На каждый выгруженный процесс приходит-
ся один процесс, загруженный в память из состояния "готовности к выполнению,
будучи зарезервированным". Ядро загружает эти процессы не с помощью обычного
алгоритма подкачки, а путем обработки отказов при обращении к соответствую-
щим страницам. На последующих итерациях процесса подкачки при условии нали-
чия в системе достаточного объема свободной памяти будут обработаны отказы,
полученные другими пользовательскими процессами. Применение такого метода
ведет к снижению частоты возникновения системных отказов и устранению сопер-
ничества: по идеологии он близок к методам, используемым в операционной сис-
теме VAX/VMS ([Levy 82]).
286
Прочитанная глава была посвящена рассмотрению алгоритмов подкачки про-
цессов и замещения страниц, используемых в версии V системы UNIX. Алгоритм
подкачки процессов реализует перемещение процессов целиком между основной
памятью и устройством выгрузки. Ядро выгружает процессы из памяти, если их
размер поглощает всю свободную память в системе (в результате выполнения
функций fork, exec и sbrk или в результате естественного увеличения стека),
или в том случае, если требуется освободить память для загрузки процесса.
Загрузку процессов выполняет специальный процесс подкачки (процесс 0), кото-
рый запускается всякий раз, как на устройстве выгрузки появляются процессы,
готовые к выполнению. Процесс подкачки не прекращает своей работы до тех
пор, пока на устройстве выгрузки не останется ни одного такого процесса или
пока в основной памяти не останется свободного места. В последнем случае
процесс подкачки пытается выгрузить что-нибудь из основной памяти, но в его
обязанности входит также слежение за соблюдением требования минимальной про-
должительности пребывания выгружаемых процессов в памяти (в целях предотвра-
щения холостой перекачки); по этой причине процесс подкачки не всегда дости-
гает успеха в своей работе. Возобновление процесса подкачки в случае возник-
новения необходимости в нем производит с интервалом в одну секунду программа
обработки прерываний по таймеру.
В системе с замещением страниц по запросу процессы могут исполняться,
даже если их виртуальное адресное пространство загружено в память не пол-
ностью; поэтому виртуальный размер процесса может превышать объем доступной
физической памяти в системе. Когда ядро испытывает потребность в свободных
страницах, "сборщик" страниц просматривает все активные страницы в каждой
области, помечая для выгрузки те из них, которые достаточно "созрели" для
этого, и в конечном итоге откачивает их на устройство выгрузки. Когда про-
цесс обращается к виртуальной странице, которая в настоящий момент выгружена
из памяти, он получает отказ из-за недоступности данных. Ядро запускает
программу обработки отказа, которая назначает области новую физическую стра-
ницу памяти и копирует в нее содержимое виртуальной страницы.
Повысить производительность системы при использовании алгоритма замеще-
ния страниц по запросу можно несколькими способами. Во-первых, если процесс
вызывает функцию fork, ядро использует бит копирования при записи, тем самым
в большинстве случаев снимая необходимость в физическом копировании страниц.
Во-вторых, ядро может запросить содержимое страницы исполняемого файла прямо
из файловой системы, устраняя потребность в вызове функции exec для незамед-
лительного считывания файла в память. Это способствует повышению производи-
тельности, поскольку не исключена возможность того, что подобные страницы
так никогда и не потребуются процессу, и устраняет излишнюю холостую пере-
качку, имеющую место в том случае, если "сборщик" страниц выгружает эти
страницы из памяти до того, как в них возникает потребность.
1. Набросайте схему реализации алгоритма mfree, который освобождает прост-
ранство памяти и возвращает его таблице свободного пространства.
2. В разделе 9.1.2 утверждается, что система блокирует перемещаемый про-
цесс, чтобы другие процессы не могли его трогать с места до момента
окончания операции. Что произошло бы, если бы система не делала этого ?
3. Предположим, что в адресном пространстве процесса располагаются таблицы
используемых процессом сегментов и страниц. Каким образом ядро может
выгрузить это пространство из памяти?
4. Если стек ядра находится внутри адресного пространства процесса, почему
процесс не может выгружать себя сам ? Какой на Ваш взгляд должна быть
системная программа выгрузки процессов, как она должна запускаться ?
*5. Предположим, что ядро пытается выгрузить процесс, чтобы освободить мес-
287
то в памяти для других процессов, загружаемых с устройства выгрузки.
Если ни на одном из устройств выгрузки для данного процесса нет места,
процесс подкачки приостанавливает свою работу до тех пор, пока место не
появится. Возможна ли ситуация, при которой все процессы, находящиеся в
памяти, приостановлены, а все готовые к выполнению процессы находятся
на устройстве выгрузки ? Что нужно предпринять ядру для того, чтобы ис-
править это положение ?
6. Рассмотрите еще раз пример, приведенный на Рисунке 9.10, при условии,
что в памяти есть место только для 1 процесса.
7. Обратимся к примеру, приведенному на Рисунке 9.11. Составьте подобный
пример, в котором процессу постоянно требуется для работы центральный
процессор. Существует ли какой-нибудь способ снятия подобной напряжен-
ности ?
+----------------------------------+
| main() |
| { |
| f(); |
| g(); |
| } |
| |
| f() |
| { |
| vfork(); |
| } |
| |
| g() |
| { |
| int blast[100],i; |
| for (i = 0; i < 100; i++) |
| blast[i] = i; |
| } |
+----------------------------------+
Рисунок 9.29
8. Что произойдет в результате выполнения программы, приведенной на Рисун-
ке 9.29, в системе BSD 4.2 ? Каким будет стек процесса-родителя ?
9. Почему после выполнения функции fork процесса-потомка предпочтительнее
запускать впереди процесса-родителя, если на разделяемых страницах биты
копирования при записи установлены ? Каким образом ядро может заставить
потомка запуститься первым ?
*10. Алгоритм обработки отказа из-за недоступности данных, изложенный в тек-
сте, загружает страницы поодиночке. Его эффективность можно повысить,
если подготовить к загрузке помимо страницы, вызвавшей отказ, и все со-
седние с ней страницы. Переработайте исходный алгоритм с учетом указан-
ной операции.
11. В алгоритмах работы "сборщика" страниц и программы обработки отказов
из-за недоступности данных предполагается, что размер страницы равен
размеру дискового блока. Что нужно изменить в этих алгоритмах для того,
чтобы они работали и в тех случаях, когда указанное равенство не соблю-
дается ?
*12. Когда процесс вызывает функцию fork (ветвится), значение счетчика ссы-
лок на каждую разделяемую страницу (в таблице pfdata) увеличивается.
Предположим, что "сборщик" страниц выгружает разделяемую страницу на
устройство выгрузки, и один из процессов (скажем, родитель) впоследст-
вии получает отказ при обращении к ней. Содержимое виртуальной страницы
теперь располагается на физической странице. Объясните, почему про-
цесс-потомок всегда имеет возможность получить верную копию страницы,
288
даже после того, как процесс-родитель что-то запишет на нее. Почему,
когда процесс-родитель ведет запись на страницу, он должен немедленно
порвать связь с ее дисковой копией ?
13. Что следует предпринять программе обработки отказов в том случае, если
в системе исчерпаны страницы памяти ?
*14. Составьте алгоритм выгрузки редко используемых компонент ядра. Какие из
компонент нельзя выгружать и как их в таком случае следует обозначить ?
15. Придумайте алгоритм, отслеживающий выделение пространства на устройстве
выгрузки, используя вместо карт памяти, описанных в настоящей главе,
битовый массив. Сравните эффективность обоих методов.
16. Предположим, что в машине нет аппаратно-устанавливаемого бита доступ-
ности, но есть код защиты, устанавливающий права доступа на чтение, за-
пись и "исполнение" содержимого страницы. Смоделируйте работу с помощью
программно-устанавливаемого бита доступности.
17. В машине VAX-11 перед проверкой наличия отказов из-за недоступности
данных выполняется аппаратная проверка наличия отказов системы защиты.
Как это отражается на алгоритмах обработки отказов ?
18. Системная функция plock дает суперпользователю возможность устанавли-
вать и снимать блокировку (в памяти) на областях команд и данных вызы-
вающего процесса. Процесс подкачки и "сборщик" страниц не могут выгру-
жать заблокированные страницы из памяти. Процессам, использующим эту
системную функцию, не приходится дожидаться загрузки страниц, поэтому
им гарантирован более быстрый ответ по сравнению с другими процессами.
Следует ли иметь также возможность блокировки в памяти и области стека
? Что произойдет в том случае, если суммарный объем заблокированных об-
ластей превысит размер доступной памяти в машине ?
19. Что делает программа, приведенная на Рисунке 9.30 ? Подумайте над аль-
тернативной стратегией замещения страниц, в соответствии с которой в
рабочее множество каждого процесса включается максимально-возможное
число страниц.
+------------------------------------------------------------+
| struct fourmeg |
| { |
| int page[512]; /* пусть int занимает 4 байта */ |
| } fourmeg[2048]; |
| |
| main() |
| { for (;;) |
| { |
| switch(fork()) |
| { |
| case -1: /* процесс-родитель не может выполнить |
| * fork --- слишком много потомков */ |
| case 0: /* потомок */ |
| func(); |
| default: |
| continue; |
| } } } |
| |
| func() |
| { int i; |
| |
| for (;;) |
| { |
| printf("процесс %d повторяет цикл\n",getpid()); |
| for (i = 0; i < 2048; i++) |
| fourmeg[i]290ge[0] = i; |
| } } |
+------------------------------------------------------------+
289
Last-modified: Thu, 12 Feb 1998 07:20:20 GMT