Алгоритм планирования использования процессорного времени, рассмотренный в предыдущей главе, в сильной степени зависит от выбранной стратегии управления памятью. Процесс может выполняться, если он хотя бы частично присутствует в основной памяти; ЦП не может исполнять процесс, полностью выгруженный во внешнюю память. Тем не менее, основная память — чересчур дефицитный ресурс, который зачастую не может вместить все активные процессы в системе. Если, например, в системе имеется основная память объемом 8 Мбайт, то девять процессов размером по 1 Мбайту каждый уже не смогут в ней одновременно помещаться. Какие процессы в таком случае следует размещать в памяти (хотя бы частично), а какие нет, решает подсистема управления памятью, она же управляет участками виртуального адресного пространства процесса, не резидентными в памяти. Она следит за объемом доступного пространства основной памяти и имеет право периодически переписывать процессы на устройство внешней памяти, именуемое устройством выгрузки, освобождая в основной памяти дополнительное место. Позднее ядро может вновь поместить данные с устройства выгрузки в основную память.

В ранних версиях системы UNIX процессы переносились между основной памятью и устройством выгрузки целиком и, за исключением разделяемой области команд, отдельные независимые части процесса не могли быть объектами перемещения. Такая стратегия управления памятью называется свопингом (подкачкой). Такую стратегию имело смысл реализовывать на машине типа PDP-11, где максимальный размер процесса составлял 64 Кбайта. При использовании этой стратегии размер процесса ограничивается объемом физической памяти, доступной в системе. Система BSD (версия 4.0) явилась главным полигоном для применения другой стратегии, стратегии "подкачки по обращению" (demand paging), в соответствии с которой основная память обменивается с внешней не процессами, а страницами памяти; эта стратегия поддерживается и в последних редакциях версии V системы UNIX. Держать в основной памяти весь выполняемый процесс нет необходимости, и ядро загружает в память только отдельные страницы по запросу выполняющегося процесса, ссылающегося на них. Преимущество стратегии подкачки по обращению состоит в том, что благодаря ей отображение виртуального адресного пространства процесса на физическую память машины становится более гибким: допускается превышение размером процесса объема доступной физической памяти и одновременное размещение в основной памяти большего числа процессов. Преимущество стратегии свопинга состоит в простоте реализации и облегчении "надстроечной" части системы. Обе стратегии управления памятью рассматриваются в настоящей главе.

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

Устройство выгрузки является устройством блочного типа, которое представляет собой конфигурируемый раздел диска. Тогда как обычно ядро выделяет место для файлов по одному блоку за одну операцию, на устройстве выгрузки пространство выделяется группами смежных блоков. Пространство, выделяемое для файлов, используется статическим образом; поскольку схема назначения пространства под файлы действует в течение длительного периода времени, ее гибкость понимается в смысле сокращения числа случаев фрагментации и, следовательно, объемов неиспользуемого пространства в файловой системе. Выделение пространства на устройстве выгрузки, напротив, является временным, в сильной степени зависящим от механизма диспетчеризации процессов. Процесс, размещаемый на устройстве выгрузки, в конечном итоге вернется в основную память, освобождая место на внешнем устройстве. Поскольку время является решающим фактором и с учетом того, что ввод-вывод данных за одну мультиблочную операцию происходит быстрее, чем за несколько одноблочных операций, ядро выделяет на устройстве выгрузки непрерывное пространство, не беря во внимание возможную фрагментацию.

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

Каждая строка в карте памяти состоит из адреса распределяемого ресурса и количества доступных единиц ресурса; ядро интерпретирует элементы строки в соответствии с типом карты. В самом начале карта памяти состоит из одной строки, содержащей адрес и общее количество ресурсов. Если карта описывает распределение памяти на устройстве выгрузки, ядро трактует каждую единицу ресурса как группу дисковых блоков, а адрес — как смещение в блоках от начала области выгрузки. Первоначальный вид карты памяти для устройства выгрузки, состоящего из 10000 блоков с начальным адресом, равным 1, показан на Рисунке 9.1. Выделяя и освобождая ресурсы, ядро корректирует карту памяти, заботясь о том, чтобы в ней постоянно содержалась точная информация о свободных ресурсах в системе.

На Рисунке 9.2 представлен алгоритм выделения пространства с помощью карт памяти (malloc). Ядро просматривает карту в поисках первой строки, содержащей количество единиц ресурса, достаточное для удовлетворения запроса. Если запрос покрывает все количество единиц, содержащееся в строке, ядро удаляет строку и уплотняет карту (то есть в карте становится на одну строку меньше). В противном случае ядро переустанавливает адрес и число оставшихся единиц в строке в соответствии с числом единиц, выделенных по запросу. На Рисунке 9.3 показано, как меняется вид карты памяти для устройства выгрузки после выделения 100, 50 и вновь 100 единиц ресурса. В конечном итоге карта памяти принимает вид, показывающий, что первые 250 единиц ресурса выделены по запросам, и что теперь остались свободными 9750 единиц, начиная с адреса 251.

Рисунок 9.1. Первоначальный вид карты памяти для устройства выгрузки

алгоритм malloc /* алгоритм выделения пространства с использованием карты памяти */

входная информация:

 (1) адрес /* указывает на тип используемой карты */

 (2) требуемое число единиц ресурса

выходная информация:

 адрес — в случае успешного завершения

 0 — в противном случае

{

 for (каждой строки карты) 

{

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

{

   if (требуемое число == числу единиц в строке)

    удалить строку из карты;

   else 

отрегулировать стартовый адрес в строке;

   return (первоначальный адрес строки);

  }

 }

 return (0);

}

Рисунок 9.2. Алгоритм выделения пространства с помощью карт памяти

Освобождая ресурсы, ядро ищет для них соответствующее место в карте по адресу. При этом возможны три случая:

1. Освободившиеся ресурсы полностью закрывают пробел в карте памяти. Другими словами, они имеют смежные адреса с адресами ресурсов из строк, непосредственно предшествующей и следующей за данной. В этом случае ядро объединяет вновь освободившиеся ресурсы с ресурсами из указанных строк в одну строку карты памяти.

2. Освободившиеся ресурсы частично закрывают пробел в карте памяти. Если они имеют адрес, смежный с адресом ресурсов из строки, непосредственно предшествующей или непосредственно следующей за данной (но не с адресами из обеих строк), ядро переустанавливает значение адреса и числа ресурсов в соответствующей строке с учетом вновь освободившихся ресурсов. Число строк в карте памяти остается неизменным.

3. Освободившиеся ресурсы частично закрывают пробел в карте памяти, но их адреса не соприкасаются с адресами каких-либо других ресурсов карты. Ядро создает новую строку и вставляет ее в соответствующее место в карте.

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

Возвращаясь к предыдущему примеру, отметим, что если ядро освобождает 50 единиц ресурса, начиная с адреса 101, в карте памяти появится новая строка, поскольку освободившиеся ресурсы имеют адреса, не соприкасающиеся с адресами существующих строк карты. Если же затем ядро освободит 100 единиц ресурса, начиная с адреса 1, первая строка карты будет расширена, поскольку освободившиеся ресурсы имеют адрес, смежный с адресом первой строки. Эволюция состояний карты памяти для данного случая показана на Рисунке 9.4.

Предположим, что ядру был сделан запрос на выделение 200 единиц (блоков) пространства устройства выгрузки. Поскольку первая строка карты содержит информацию только о 150 единицах, ядро привлекает для удовлетворения запроса информацию из второй строки (см. Рисунок 9.5). Наконец, предположим, что ядро освобождает 350 единиц пространства, начиная с адреса 151. Несмотря на то, что эти 350 единиц были выделены ядром в разное время, не существует причины, по которой ядро не могло бы освободить их все сразу. Ядро узнает о том, что освободившиеся ресурсы полностью закрывают разрыв между первой и второй строками карты, и вместо прежних двух создает одну строку, в которую включает и освободившиеся ресурсы.

Рисунок 9.4. Освобождение пространства на устройстве выгрузки

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

В традиционной реализации системы UNIX используется одно устройство выгрузки, однако в последних редакциях версии V допускается уже наличие множества устройств выгрузки. Ядро выбирает устройство выгрузки по схеме "кольцевого списка" при условии, что на устройстве имеется достаточный объем непрерывного адресного пространства. Администраторы могут динамически создавать и удалять из системы устройства выгрузки. Если устройство выгрузки удаляется из системы, ядро не выгружает данные на него; если же данные подкачиваются с удаляемого устройства, сначала оно опорожняется и только после освобождения принадлежащего устройству пространства устройство может быть удалено из системы.

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

1. Произведено обращение к системной функции fork, которая должна выделить место в памяти для процесса-потомка.

2. Произведено обращение к системной функции brk, увеличивающей размер процесса.

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

4. Ядру нужно освободить в памяти место для подкачки ранее выгруженных процессов.

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

Когда ядро принимает решение о том, что процесс будет выгружен из основной памяти, оно уменьшает значение счетчика ссылок, ассоциированного с каждой областью процесса, и выгружает те области, у которых счетчик ссылок стал равным 0. Ядро выделяет место на устройстве выгрузки и блокирует процесс в памяти (в случаях 1–3), запрещая его выгрузку (см. упражнение 9.12) до тех пор, пока не закончится текущая операция выгрузки. Адрес места выгрузки областей ядро сохраняет в соответствующих записях таблицы областей.

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

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

На Рисунке 9.6 приведен пример отображения образа процесса в памяти на адресное пространство устройства выгрузки[25]. Процесс располагает тремя областями: команд, данных и стека. Область команд заканчивается на виртуальном адресе 2К, а область данных начинается с адреса 64К, таким образом в виртуальном адресном пространстве образовался пропуск в 62 Кбайта. Когда ядро выгружает процесс, оно выгружает содержимое страниц памяти с адресами 0, 1К, 64К, 65К, 66К и 128К; на устройстве выгрузки не будет отведено место под пропуск в 62 Кбайта между областями команд и данных, как и под пропуск в 61 Кбайт между областями данных и стека, ибо пространство на устройстве выгрузки заполняется непрерывно. Когда ядро загружает процесс обратно в память, оно уже знает из карты памяти процесса о том, что процесс имеет в своем пространстве неиспользуемый участок размером 62К, и с учетом этого соответственно выделяет физическую память. Этот случай проиллюстрирован с помощью Рисунка 9.7. Сравнение Рисунков 9.6 и 9.7 показывает, что физические адреса, занимаемые процессом до и после выгрузки, не совпадают между собой; однако, на пользовательском уровне процесс не обращает на это никакого внимания, поскольку содержимое его виртуального пространства осталось тем же самым.

Теоретически все пространство памяти, занятое процессом, в том числе его личное адресное пространство и стек ядра, может быть выгружено, хотя ядро и может временно заблокировать область в памяти на время выполнения критической операции. Однако практически, ядро не выгружает содержимое адресного пространства процесса, если в нем находятся таблицы преобразования адресов (адресные таблицы) процесса. Практическими соображениями так же диктуются условия, при которых процесс может выгрузить самого себя или потребовать своей выгрузки другим процессом (см. упражнение 9.4).

Рисунок 9.6. Отображение пространства процесса на устройство выгрузки

Рисунок 9.7. Загрузка процесса в память

В описании системной функции fork (раздел 7.1) предполагалось, что процесс-родитель получил в свое распоряжение память, достаточную для создания контекста потомка. Если это условие не выполняется, ядро выгружает процесс из памяти, не освобождая пространство памяти, занимаемое его (родителя) копией. Когда процедура выгрузки завершится, процесс-потомок будет располагаться на устройстве выгрузки; процесс-родитель переводит своего потомка в состояние "готовности к выполнению" (см. Рисунок 6.1) и возвращается в режим задачи. Поскольку процесс-потомок находится в состоянии "готовности к выполнению", программа подкачки в конце концов загрузит его в память, где ядро запустит его на выполнение; потомок завершит тем самым свою роль в выполнении системной функции fork и вернется в режим задачи.

Если процесс испытывает потребность в дополнительной физической памяти, либо в результате расширения стека, либо в результате запуска функции brk, и если эта потребность превышает доступные резервы памяти, ядро выполняет операцию выгрузки процесса с расширением его размера на устройстве выгрузки. На устройстве выгрузки ядро резервирует место для размещения процесса с учетом расширения его размера. Затем производится перенастройка таблицы преобразования адресов процесса с учетом дополнительного виртуального пространства, но без выделения физической памяти (в связи с ее отсутствием). Наконец, ядро выгружает процесс, выполняя процедуру выгрузки обычным порядком и обнуляя вновь выделенное пространство на устройстве (см. Рисунок 9.8). Когда несколько позже ядро будет загружать процесс обратно в память, физическое пространство будет выделено уже с учетом нового состояния таблицы преобразования адресов. В момент возобновления у процесса уже будет в распоряжении память достаточного объема.

Рисунок 9.8. Перенастройка карты памяти в случае выгрузки с расширением

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

Как уже вкратце говорилось в главе 8, программа обработки прерываний по таймеру измеряет время нахождения каждого процесса в памяти или в состоянии выгрузки. Когда процесс подкачки возобновляет свою работу по загрузке процессов в память, он просматривает все процессы, находящиеся в состоянии "готовности к выполнению, будучи выгруженными", и выбирает из них один, который находится в этом состоянии дольше остальных (см. Рисунок 9.9). Если имеется достаточно свободной памяти, процесс подкачки загружает выбранный процесс, выполняя операции в последовательности, обратной выгрузке процесса. Сначала выделяется физическая память, затем с устройства выгрузки считывается нужный процесс и освобождается место на устройстве.

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

• На устройстве выгрузки больше нет ни одного процесса, готового к выполнению. Процесс подкачки приостанавливает свою работу до тех пор, пока не возобновится процесс на устройстве выгрузки или пока ядро не выгрузит процесс, готовый к выполнению. (Вспомним диаграмму состояний на Рисунке 6.1).

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

Если процессу подкачки нужно выгрузить процесс, он просматривает все процессы в памяти. Прекратившие свое существование процессы не подходят для выгрузки, поскольку они не занимают физическую память; также не могут быть выгружены процессы, заблокированные в памяти, например, выполняющие операции над областями. Ядро предпочитает выгружать приостановленные процессы, поскольку процессы, готовые к выполнению, имеют больше шансов быть вскоре выбранными на выполнение. Решение о выгрузке процесса принимается ядром на основании его приоритета и продолжительности его пребывания в памяти. Если в памяти нет ни одного приостановленного процесса, решение о том, какой из процессов, готовых к выполнению, следует выгрузить, зависит от значения, присвоенного процессу функцией nice, а также от продолжительности пребывания процесса в памяти.

Процесс, готовый к выполнению, должен быть резидентным в памяти в течение по меньшей мере 2 секунд до того, как уйти из нее, а процесс, загружаемый в память, должен по меньшей мере 2 секунды пробыть на устройстве выгрузки. Если процесс подкачки не может найти ни одного процесса, подходящего для выгрузки, или ни одного процесса, подходящего для загрузки, или ни одного процесса, перед выгрузкой не менее 2 секунд[26] находившегося в памяти, он приостанавливает свою работу по причине того, что ему нужно загрузить процесс в память, а в памяти нет места для его размещения. В этой ситуации таймер возобновляет выполнение процесса подкачки через каждую секунду. Ядро также возобновляет работу процесса подкачки в том случае, когда один из процессов переходит в состояние приостанова, так как последний может оказаться более подходящим для выгрузки процессом по сравнению с ранее рассмотренными. Если процесс подкачки расчистил место в памяти или если он был приостановлен по причине невозможности сделать это, он возобновляет свою работу с перезапуска алгоритма подкачки (с самого его начала), вновь предпринимая попытку загрузить ожидающие выполнения процессы.

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

входная информация: отсутствует

выходная информация: отсутствует

{

loop:

 for (всех выгруженных процессов, готовых к выполнению)

  выбрать процесс, находящийся в состоянии выгруженности дольше остальных;

 if (таких процессов нет) 

{

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

  goto loop;

 }

 if (в основной памяти достаточно места для размещения процесса) 

{

  загрузить процесс;

  goto loop;

 }

 /* loop2: сюда вставляются исправления, внесенные в алгоритм */

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

{

  if (есть хотя бы один приостановленный процесс)

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

  else

  /* нет ни одного приостановленного процесса */

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

 }

 if (выбранный процесс не является приостановленным или не соблюдены условия резидентности)

  приостановиться (до момента, когда появится возможность загрузить процесс);

 else

 выгрузить процесс;

 goto loop; /* на loop2 в исправленном алгоритме */

}

Рисунок 9.9. Алгоритм подкачки

На Рисунке 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, из которого видно, что ядро загружает процесс D на 2-секундной отметке, запускает процесс C, а затем на 3-секундной отметке процесс D выгружается в пользу процесса E (уступая последнему в значении nice), несмотря на то, что процессу D так и не был предоставлен ЦП. Понятно, что такая ситуация является нежелательной.

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

Рисунок 9.10. Последовательность операций, выполняемых процессом подкачки

Рисунок 9.11. Загрузка процессов в случае разбивки временных интервалов на части

Алгоритм подкачки страниц памяти поддерживается на машинах со страничной организацией памяти и с ЦП, имеющим прерываемые команды[27]. В системах с подкачкой страниц отсутствуют ограничения на размер процесса, связанные с объемом доступной физической памяти. Например, в машинах с объемом физической памяти 1 и 2 Мбайта могут исполняться процессы размером 4 или 5 Мбайт. Ограничение на виртуальный размер процесса, связанное с объемом адресуемой виртуальной памяти, остается в силе и здесь. Поскольку процесс может не поместиться в физической памяти, ядру приходится динамически загружать в память отдельные его части и исполнять их, несмотря на отсутствие остальных частей. В механизме подкачки страниц все открыто для пользовательских программ, за исключением разрешенного процессу виртуального размера.

Процессы стремятся исполнять команды небольшими порциями, которые именуются программными циклами или подпрограммами, используемые ими указатели группируются в небольшие поднаборы, располагаемые в информационном пространстве процесса. В этом состоит суть так называемого принципа "локальности". Деннингом [Denning 68] было сформулировано понятие рабочего множества процесса как совокупности страниц, использованных процессом в последних n ссылках на адресное пространство памяти; число n называется окном рабочего множества. Поскольку рабочее множество процесса является частью от целого, в основной памяти может поместиться больше процессов по сравнению с теми системами, где управление памятью базируется на подкачке процессов, что в конечном итоге приводит к увеличению производительности системы. Когда процесс обращается к странице, отсутствующей в его рабочем множестве, возникает ошибка, при обработке которой ядро корректирует рабочее множество процесса, в случае необходимости подкачивая страницы с внешнего устройства.

На Рисунке 9.12 приведена последовательность используемых процессом указателей страниц, описывающих рабочие множества с окнами различных размеров при условии соблюдения алгоритма замещения "стариков" (замещения страниц путем откачки тех, к которым наиболее долго не было обращений). По мере выполнения процесса его рабочее множество видоизменяется в соответствии с используемыми процессом указателями страниц; увеличение размера окна влечет за собой увеличение рабочего множества и, с другой стороны, сокращение числа ошибок в выполнении процесса. Использование неизменного рабочего множества не практикуется, поскольку запоминание очередности следования указателей страниц потребовало бы слишком больших затрат. Приблизительное соответствие между изменяемым рабочим множеством и пространством процесса достигается путем установки бита упоминания (reference bit) при обращении к странице памяти, а также периодическим опросом указателей страниц. Если на страницу была сделана ссылка, эта страница включается в рабочее множество; в противном случае она "дозревает" в памяти в ожидании своей очереди.

В случае возникновения ошибки из-за обращения к странице, отсутствующей в рабочем множестве, ядро приостанавливает выполнение процесса до тех пор, пока страница не будет считана в память и не станет доступной процессу. Когда страница будет загружена, процесс перезапустит ту команду, на которой выполнение процесса было приостановлено из-за ошибки. Таким образом, работа подсистемы замещения страниц распадается на две части: откачка редко используемых страниц на устройство выгрузки и обработка ошибок из-за отсутствия нужной страницы. Такое общее толкование механизма замещения страниц, конечно же, выходит за пределы одной конкретной системы. Оставшуюся часть главы мы посвятим более детальному рассмотрению особенностей реализации этого механизма в версии V системы UNIX.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В ходе выполнения функции fork в системе BSD создается физическая копия страниц родительского процесса. Однако, учитывая наличие ситуаций, в которых создание физической копии не является обязательным, в системе BSD существует также функция 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 и завершается[28]. Система гарантирует, что процесс-родитель приостанавливается до того момента, когда потомок исполнит функции exec или exit. Возобновив в конечном итоге свое выполнение, процесс-родитель обнаружит, что значения двух его переменных не совпадают с теми значениями, которые были у них до обращения к функции vfork! Еще больший эффект может произвести возвращение процесса-потомка из функции, вызвавшей функцию vfork (см. упражнение 9.8).

Как уже говорилось в главе 7, когда процесс обращается к системной функции exec, ядро считывает из файловой системы в память указанный исполняемый файл. Однако в системе с замещением страниц по запросу исполняемый файл, имеющий большой размер, может не уместиться в доступном пространстве основной памяти. Поэтому ядро не назначает ему сразу все пространство, а отводит место в памяти по мере надобности. Сначала ядро назначает файлу таблицы страниц и дескрипторы дисковых блоков, помечая страницы в записях таблиц как "заполняемые при обращении" (для всех данных, кроме имеющих тип bss) или "обнуляемые при обращении" (для данных типа bss). Считывая в память каждую страницу файла по алгоритму read, процесс получает ошибку из-за отсутствия (недоступности) данных. Подпрограмма обработки ошибок проверяет, является ли страница "заполняемой при обращении" (тогда ее содержимое будет немедленно затираться содержимым исполняемого файла и поэтому ее не надо очищать) или "обнуляемой при обращении" (тогда ее следует очистить). В разделе 9.2.3 мы увидим, как это происходит. Если процесс не может поместиться в памяти, "сборщик" страниц освобождает для него место, периодически откачивая из памяти неиспользуемые страницы.

В этой схеме видны явные недостатки. Во-первых, при чтении каждой страницы исполняемого файла процесс сталкивается с ошибкой из-за обращения к отсутствующей странице, пусть даже процесс никогда и не обращался к ней. Во-вторых, если после того, как "сборщик" страниц откачал часть страниц из памяти, была запущена функция exec, каждая только что выгруженная и вновь понадобившаяся страница потребует дополнительную операцию по ее загрузке. Чтобы повысить эффективность функции exec, ядро может востребовать страницу непосредственно из исполняемого файла, если данные в файле соответствующим образом настроены, что определяется значением т. н. "магического числа". Однако, использование стандартных алгоритмов доступа к файлу (например, bmap) потребовало бы при обращении к странице, состоящей из блоков косвенной адресации, больших затрат, связанных с многократным использованием буферного кэша для чтения каждого блока. Кроме того, функция bmap не является реентерабельной, отсюда возникает опасность нарушения целостности данных. Во время выполнения системной функции read ядро устанавливает в пространстве процесса значения различных параметров ввода-вывода. Если при попытке скопировать данные в пространство пользователя процесс столкнется с отсутствием нужной страницы, он, считывая страницу из файловой системы, может затереть содержащие эти параметры поля. Поэтому ядро не может прибегать к использованию обычных алгоритмов обработки ошибок данного рода. Конечно же алгоритмы должны быть в обычных случаях реентерабельными, поскольку у каждого процесса свое отдельное адресное пространство и процесс не может одновременно исполнять несколько системных функций.

Для того, чтобы считывать страницы непосредственно из исполняемого файла, ядро во время исполнения функции exec составляет список номеров дисковых блоков файла и присоединяет этот список к индексу файла. Работая с таблицами страниц такого файла, ядро находит дескриптор дискового блока, содержащего страницу, и запоминает номер блока внутри файла; этот номер позже используется при загрузке страницы из файла. На Рисунке 9.17 показан пример, в котором страница имеет адрес расположения в логическом блоке с номером 84 от начала файла. В области имеется указатель на индекс, в котором содержится номер соответствующего физического блока на диске (279).

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

"Сборщик" страниц (page stealer) является процессом, принадлежащим ядру операционной системы и выполняющим выгрузку из памяти тех страниц, которые больше не входят в состав рабочего множества пользовательского процесса. Этот процесс создается ядром во время инициализации системы и запускается в любой момент, когда в нем возникает необходимость. Он просматривает все активные незаблокированные области и увеличивает значение "возраста" каждой принадлежащей им страницы (заблокированные области пропускаются, но впоследствии, по снятии блокировки, тоже будут учтены). Когда процесс при работе со страницей, принадлежащей области, получает ошибку, ядро блокирует область, чтобы "сборщик" не смог выгрузить страницу до тех пор, пока ошибка не будет обработана.

Страница в памяти может находиться в двух состояниях: либо "дозревать", не будучи еще готовой к выгрузке, либо быть готовой к выгрузке и доступной для привязки к другим виртуальным страницам. Первое состояние означает, что процесс обратился к странице и поэтому страница включена в его рабочее множество. При обращении к странице в некоторых машинах аппаратно устанавливается бит упоминания, если же эта операция не выполняется, соответственно, и программные методы скорее всего используются другие (раздел 9.2.4). Если страница находится в первом состоянии, "сборщик" сбрасывает бит упоминания в ноль, но запоминает количество просмотров множества страниц, выполненных с момента последнего обращения к странице со стороны пользовательского процесса. Таким образом, первое состояние распадается на несколько подсостояний в соответствии с тем, сколько раз "сборщик" страниц обратился к странице до того, как страница стала готовой для выгрузки (см. Рисунок 9.18). Когда это число превышает некоторое пороговое значение, ядро переводит страницу во второе состояние — состояние готовности к выгрузке. Максимальная продолжительность пребывания страницы в первом состоянии зависит от условий конкретной реализации и ограничивается числом отведенных для этого поля разрядов в записи таблицы страниц.

На Рисунке 9.19 показано взаимодействие между процессами, работающими со страницей, и "сборщиком" страниц. Цифры обозначают номер обращения "сборщика" к странице с того момента, как страница была загружена в память. Процесс, обратившийся к странице после второго просмотра страниц "сборщиком", сбросил ее "возраст" в 0. После каждого просмотра пользовательский процесс обращался к странице вновь, но в конце концов "сборщик" страниц осуществил три просмотра страницы с момента последнего обращения к ней со стороны пользовательского процесса и выгрузил ее из памяти.

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

Если область используется совместно не менее, чем двумя процессами, все они работают с битами упоминания в одном и том же наборе записей таблицы страниц. Таким образом, страницы могут включаться в рабочие множества нескольких процессов, но для "сборщика" страниц это не имеет никакого значения. Если страница включена в рабочее множество хотя бы одного из процессов, она остается в памяти; в противном случае она может быть выгружена. Ничего, что одна область, к примеру, имеет в памяти страниц больше, чем имеют другие: "сборщик" страниц не пытается выгрузить равное количество страниц из всех активных областей.

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

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

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

1. Если на устройстве выгрузки есть копия страницы, ядро "планирует" выгрузку страницы: "сборщик" страниц помещает ее в список выгруженных страниц и переходит дальше; выгрузка считается логически завершившейся. Когда число страниц в списке превысит ограничение (определяемое возможностями дискового контроллера), ядро переписывает страницы на устройство выгрузки.

2. Если на устройстве выгрузки уже есть копия страницы и ее содержимое ничем не отличается от содержимого страницы в памяти (бит модификации в записи таблицы страниц не установлен), ядро сбрасывает в ноль бит доступности (в той же записи таблицы), уменьшает значение счетчика ссылок в таблице pfdata и помещает запись в список свободных страниц для будущего переназначения.

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

"Сборщик" страниц копирует страницу на устройство выгрузки, если имеют место случаи 1 и 3.

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

"Сборщик" страниц заполняет список выгруженных страниц, которые в принципе могут принадлежать разным областям, и по заполнении списка откачивает их на устройство выгрузки. Нет необходимости в том, чтобы все страницы одного процесса непременно выгружались: к примеру, некоторые из страниц, возможно, недостаточно "созрели" для этого. В этом видится различие со стратегией выгрузки процессов, согласно которой из памяти выгружаются все страницы одного процесса, вместе с тем метод переписи данных на устройство выгрузки идентичен тому методу, который описан для системы с замещением процессов в разделе 9.1.2. Если на устройстве выгрузки недостаточно непрерывного пространства, ядро выгружает страницы по отдельности (по одной странице за операцию), что в конечном итоге обходится недешево. В системе с замещением страниц фрагментация на устройстве выгрузки выше, чем в системе с замещением процессов, поскольку ядро выгружает блоки страниц, но загружает в память каждую страницу в отдельности.

Когда ядро переписывает страницу на устройство выгрузки, оно сбрасывает бит доступности в соответствующей записи таблицы страниц и уменьшает значение счетчика ссылок в соответствующей записи таблицы pfdata. Если значение счетчика становится равным 0, запись таблицы pfdata помещается в конец списка свободных страниц и запоминается для последующего переназначения. Если значение счетчика отлично от 0, это означает, что страница (в результате выполнения функции fork) используется совместно несколькими процессами, но ядро все равно выгружает ее. Наконец, ядро выделяет пространство на устройстве выгрузки, сохраняет его адрес в дескрипторе дискового блока и увеличивает значение счетчика ссылок на страницу в таблице использования области подкачки. Если в то время, пока страница находится в списке свободных страниц, процесс обнаружил ее отсутствие, получив соответствующую ошибку, ядро может восстановить ее в памяти, не обращаясь к устройству выгрузки. Однако, страница все равно будет считаться выгруженной, если она попала в список "сборщика" страниц.

Предположим, к примеру, что "сборщик" страниц выгружает 30, 40, 50 и 20 страниц из процессов A, B, C и D, соответственно, и что за одну операцию выгрузки на дисковое устройство откачиваются 64 страницы. На Рисунке 9.20 показана последовательность имеющих при этом место операций выгрузки при условии, что "сборщик" страниц осуществляет просмотр страниц процессов в очередности: A, B, C, D. "Сборщик" выделяет на устройстве выгрузки место для 64 страниц и выгружает 30 страниц процесса A и 34 страницы процесса B. Затем он выделяет место для следующих 64 страниц и выгружает оставшиеся 6 страниц процесса B, 50 страниц процесса C и 8 страниц процесса D. Выделенные для размещения страниц за две операции участки области выгрузки могут быть и несмежными. "Сборщик" сохраняет оставшиеся 12 страниц процесса D в списке выгружаемых страниц, но не выгружает их до тех пор, пока список не будет заполнен до конца. Как только у процессов возникает потребность в подкачке страниц с устройства выгрузки или если страницы больше не нужны использующим их процессам (процессы завершились), в области выгрузки освобождается место.

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

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

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

Если процесс пытается обратиться к странице, бит доступности для которой не установлен, он получает отказ из-за отсутствия (недоступности) данных и ядро запускает программу обработки прерываний по отказу данного типа (Рисунок 9.21). Бит доступности не устанавливается ни для тех страниц, которые располагаются за пределами виртуального адресного пространства процесса, ни для тех, которые входят в состав этого пространства, но не имеют в настоящий момент физического аналога в памяти. Фатальная ошибка памяти произошла в результате обращения ядра по виртуальному адресу страницы, поэтому ядро выходит на соответствующую этой странице запись в таблице страниц и дескриптор дискового блока. Чтобы предотвратить взаимную блокировку, которая может произойти, если "сборщик" попытается выгрузить страницу из памяти, ядро фиксирует в памяти область с соответствующей записью таблицы страниц. Если в дескрипторе дискового блока отсутствует информация о странице, сделанная ссылка на страницу является недопустимой и ядро посылает процессу-нарушителю сигнал о "нарушении сегментации" (см. Рисунок 7.25). Такой порядок действий совпадает с тем порядком, которого придерживается ядро, когда процесс обратился по неверному адресу, если не принимать во внимание то обстоятельство, что ядро узнает об ошибке немедленно, так как все "доступные" страницы являются резидентными в памяти. Если ссылка на страницу сделана правильно, ядро выделяет физическую страницу в памяти и считывает в нее содержимое виртуальной страницы с устройства выгрузки или из исполняемого файла.

Страница, вызвавшая отказ, находится в одном из пяти состояний:

1. На устройстве выгрузки вне памяти.

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

3. В исполняемом файле.

4. С пометкой "обнуляемая при обращении".

5. С пометкой "заполняемая при обращении".

Рассмотрим каждый случай в подробностях.

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

Обратимся к Рисунку 9.22 и в качестве примера рассмотрим запись таблицы страниц, связанную с виртуальным адресом 66К. Если при обращении к странице процесс получает отказ из-за недоступности данных, программа обработки отказа обращается к дескриптору дискового блока и обнаруживает то, что страница находится на устройстве выгрузки в блоке с номером 847 (если предположить, что в системе только одно устройство выгрузки): следовательно, виртуальный адрес указан верно. Затем программа обработки отказа обращается к кэшу, но не находит информации о дисковом блоке с номером 847. Таким образом, копия виртуальной страницы в памяти отсутствует и программа обработки отказа должна загрузить ее с устройства выгрузки. Ядро отводит физическую страницу с номером 1776 (Рисунок 9.23), считывает в нее с устройства выгрузки содержимое виртуальной страницы и перенастраивает запись таблицы страниц на страницу с номером 1776. В завершение ядро корректирует дескриптор дискового блока, делая указание о том, что страница загружена, а также запись таблицы pfdata, отмечая, что на устройстве выгрузки в блоке с номером 847 содержится дубликат виртуальной страницы.

алгоритм vfault /* обработка отказа из-за отсутствия (недоступности) данных */

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

выходная информация: отсутствует

{

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

 if (адрес не принадлежит виртуальному адресному пространству процесса)

 {

  послать сигнал (SIGSEGV: нарушение сегментации) процессу;

  goto out;

 }

 if (адрес указан неверно) goto out;/* возможно, процесс находился в состоянии приостанова */

 if (страница имеется в кэше) 

{

  убрать страницу из кэша;

  поправить запись в таблице страниц;

  do 

while (содержимое страницы не станет доступным) /* другой процесс получил такой же отказ, но раньше */

   sleep;

 }

 else { /* страница отсутствует в кэше */

  назначить области новую страницу;

  поместить новую страницу в кэш, откорректировать запись в таблице pfdata;

  if (страница ранее не загружалась в память и имеет пометку "обнуляемая при обращении")

   очистить содержимое страницы;

  else

 {

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

   sleep (до завершения ввода-вывода);

  }

  возобновить процессы (ожидающие загрузки содержимого страницы);

 }

 установить бит доступности страницы;

 сбросить бит модификации и "возраст" страницы;

 пересчитать приоритет процесса;

out:

 снять блокировку с области;

}

Рисунок 9.21. Алгоритм обработки отказа из-за отсутствия (недоступности) данных

При обработке отказов из-за недоступности данных ядро не всегда прибегает к выполнению операции ввода-вывода, даже когда из дескриптора дискового блока видно, что страница загружена (в случае 2). Может случиться так, что ядро после выгрузки содержимого физической страницы так и не переприсвоило ее или же какой-то иной процесс в результате отказа загрузил содержимое виртуальной страницы в другую физическую страницу. В любом случае программа обработки отказа обнаруживает страницу в кэше, в качестве ключа используя номер блока в дескрипторе дискового блока. Она перенастраивает соответствующую запись в таблице страниц на только что найденную страницу, увеличивает значение счетчика ссылок на страницу и в случае необходимости убирает страницу из списка свободных страниц. Предположим, к примеру, что процесс получил отказ при обращении к виртуальному адресу 64К (Рисунок 9.22). Просматривая кэш, ядро устанавливает, что страничный блок с номером 1861 связан с дисковым блоком 1206. Ядро перенастраивает запись таблицы страниц с виртуальным адресом 64К на страницу с номером 1861, устанавливает бит доступности и передает управление программе обработки отказа. Таким образом, номер дискового блока связывает вместе записи таблицы страниц и таблицы pfdata, чем и объясняется его запоминание в обеих таблицах.

Рисунок 9.22. Иллюстрация к отказу из-за недоступности данных

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

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

Рисунок 9.24. Два отказа на одной странице

Если копия страницы находится не на устройстве выгрузки, а в исполняемом файле (случай 3), ядро загружает страницу из файла. Программа обработки отказа обращается к дескриптору дискового блока, ищет соответствующий номер логического блока внутри файла, содержащего страницу, и индекс, ассоциированный с записью таблицы областей. Номер логического блока используется программой в качестве смещения внутри списка номеров дисковых блоков, присоединенного к индексу во время выполнения функции exec. По номеру блока на диске программа считывает страницу в память. Так, например, дескриптор дискового блока, связанный с виртуальным адресом 1К, показывает, что содержимое страницы располагается в исполняемом файле, внутри логического блока с номером 3 (см. Рисунок 9.22).

Если процесс получил отказ при обращении к странице, имеющей пометку "заполняемая при обращении" или "обнуляемая при обращении" (случаи 4 и 5), ядро выделяет свободную страницу в памяти и корректирует соответствующую запись таблицы страниц. Если страница "обнуляемая при обращении", ядро также очищает ее содержимое. В завершение обработки флаги "заполняемая при обращении" и "обнуляемая при обращении" сбрасываются. Теперь страница находится в памяти, доступна процессам и ее содержимое не имеет аналогов ни на устройстве выгрузки, ни в файловой системе. Так происходит, если процесс обращается к страницам с виртуальными адресами 3К и 65К (см. Рисунок 9.22): ни один из процессов не обращался к этим страницам с тех пор, как файл был запущен на выполнение функцией exec.

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

Вторым типом отказа, встречающегося при обращении к странице, является отказ системы защиты, который означает, что процесс обратился к существующей странице памяти, но судя по разрядам, описывающим права доступа к странице, доступ к ней со стороны текущего процесса не разрешен. (Вспомним пример, описывающий попытку процесса произвести запись данных в область команд; см. Рисунок 7.22). Отказ данного типа имеет место также тогда, когда процесс предпринимает попытку записать что-то на страницу, для которой во время выполнения системной функции fork был установлен бит копирования при записи. Ядро должно различать между собой ситуации, когда отказ произошел по причине того, что страница требует копирования при записи, и когда имело место действительно что-то недопустимое.

Программа обработки отказа системы защиты автоматически получает виртуальный адрес, по которому произошел отказ, и ведет поиск соответствующей области и записи таблицы страниц (Рисунок 9.25). Она блокирует область, чтобы "сборщик" страниц не мог выгрузить страницу, пока связанный с ней отказ не будет обработан. Если программа обработки отказа устанавливает, что причиной отказа послужила установка бита копирования при записи, и если страницу используют сразу несколько процессов, ядро выделяет в памяти новую страницу и копирует в нее содержимое старой страницы; ссылки других процессов на старую страницу сохраняют свое значение. После копирования и внесения в запись таблицы страниц нового номера страницы ядро уменьшает значение счетчика ссылок в записи таблицы pfdata, соответствующей старой странице. Вся процедура показана на Рисунке 9.26, где три процесса совместно используют физическую страницу с номером 828. Процесс B считывает страницу, но поскольку бит копирования при записи установлен, получает отказ системы защиты. Программа обработки отказа выделяет страницу с номером 786, копирует в нее содержимое страницы 828, уменьшает значение счетчика ссылок на скопированную страницу и перенастраивает соответствующую запись таблицы страниц на страницу с номером 786.

Если бит копирования при записи установлен, но страница используется только одним процессом, ядро дает процессу возможность воспользоваться физической страницей повторно. Оно отключает бит копирования при записи и разрывает связь страницы с ее копией на диске (если таковая существует), поскольку не исключена возможность того, что дисковой копией пользуются другие процессы. Затем ядро убирает запись таблицы pfdata из очереди страниц, ибо новая копия виртуальной страницы располагается не на устройстве выгрузки. Кроме того, ядро уменьшает значение счетчика ссылок на страницу в таблице использования области подкачки, и если это значение становится равным 0, освобождает место на устройстве (см. упражнение 9.11).

Если запись в таблице страниц указывает на то, что страница недоступна, и ее бит копирования при записи установлен, выступая поводом для отказа системы защиты, допустим, что система при обращении к странице сначала обрабатывает отказ из-за недоступности данных (обратная очередность рассматривается в упражнении 9.17). Несмотря на это, программа обработки отказа системы защиты все равно обязана убедиться в доступности страницы, поскольку при установке блокировки на область программа может приостановиться, а "сборщик" страниц тем временем может выгрузить страницу из памяти. Если страница недоступна (бит доступности сброшен), программа немедленно завершит работу и процесс получит отказ из-за недоступности данных. Ядро обработает этот отказ, но процесс вновь получит отказ системы защиты. Более чем вероятно, что заключительный отказ системы защиты будет обработан без каких-либо препятствий и помех, поскольку пройдет довольно значительный период времени, прежде чем страница достаточно "созреет" для выгрузки из памяти. Описанная последовательность событий показана на Рисунке 9.27.

алгоритм pfault /* обработка отказа системы защиты */

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

выходная информация: отсутствует

{

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

 if (страница недоступна в памяти)

 goto out;

 if (бит копирования при записи не установлен)

 goto out; /* программная ошибка — сигнал */

 if (счетчик ссылок на страничный блок › 1) 

{

  выделить новую физическую страницу;

  скопировать в нее содержимое старой страницы;

  уменьшить значение счетчика ссылок на старый страничный блок;

  перенастроить запись таблицы страниц на новую физическую страницу;

 }

 else { /* убрать страницу, поскольку она никем больше не используется */

  if (копия страницы имеется на устройстве выгрузки)

   освободить место на устройстве, разорвать связь со страницей;

  if (страница находится в хеш-очереди страниц)

   убрать страницу из хеш-очереди;

 }

 в записи таблицы страниц установить бит модификации, сбросить бит копирования при записи;

 пересчитать приоритет процесса;

 проверить, не поступали ли сигналы;

out:

 снять блокировку с области;

}

Рисунок 9.25. Алгоритм обработки отказа системы защиты

Рисунок 9.26. Отказ системы защиты из-за установки бита копирования при записи

Перед завершением программа обработки отказа системы защиты устанавливает биты модификации и защиты, но сбрасывает бит копирования при записи. Она пересчитывает приоритет процесса и проверяет, не поступали ли за время ее работы сигналы, предназначенные процессу, в точности повторяя то, что делается по завершении обработки отказа из-за недопустимости данных.

Рисунок 9.27. Взаимодействие отказа системы защиты и отказа из-за недоступности данных

Наибольшая действенность алгоритмов замещения страниц по запросу (обращению) достигается в том случае, если биты упоминания и модификации устанавливаются аппаратным путем и тем же путем вызывается отказ системы защиты при попытке записи в страницу, имеющую признак "копирования при записи". Тем не менее, указанные алгоритмы вполне применимы даже тогда, когда аппаратура распознает только бит доступности и код защиты. Если бит доступности, устанавливаемый аппаратно, дублируется программно-устанавливаемым битом, показывающим, действительно ли страница доступна или нет, ядро могло бы отключить аппаратно-устанавливаемый бит и проимитировать установку остальных битов программным путем. Так, например, в машине VAX-11 бит упоминания отсутствует (см. [Levy 82]). Ядро может отключить аппаратно-устанавливаемый бит доступности для страницы и дальше работать по следующему плану. Если процесс ссылается на страницу, он получает отказ, поскольку бит доступности сброшен, и в игру вступает программа обработки отказа, исследующая страницу. Поскольку "программный" бит доступности установлен, ядро знает, что страница действительно доступна и находится в памяти; оно устанавливает "программный" бит упоминания и "аппаратный" бит доступности, но ему еще предстоит узнать о том, что на страницу была сделана ссылка. Последующие ссылки на страницу уже не встретят отказ, ибо "аппаратный" бит доступности установлен. Когда с ней будет работать "сборщик" страниц, он вновь сбросит "аппаратный" бит доступности, вызывая тем самым от казы на все последующие обращения к странице и возвращая систему к началу цикла. Этот случай показан на Рисунке 9.28.

Рисунок 9.28. Имитация установки "аппаратного" бита модификации программными средствами

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

Ядро в версии V манипулирует алгоритмами подкачки процессов и замещения страниц так, что проблемы соперничества перестают быть неизбежными. Когда ядро не может выделить процессу страницы памяти, оно возобновляет работу процесса подкачки и переводит пользовательский процесс в состояние, эквивалентное состоянию "готовности к запуску, будучи зарезервированным". В этом состоянии одновременно могут находиться несколько процессов. Процесс подкачки выгружает один за другим целые процессы, пока объем доступной памяти в системе не превысит верхнюю отметку. На каждый выгруженный процесс приходится один процесс, загруженный в память из состояния "готовности к выполнению, будучи зарезервированным". Ядро загружает эти процессы не с помощью обычного алгоритма подкачки, а путем обработки отказов при обращении к соответствующим страницам. На последующих итерациях процесса подкачки при условии наличия в системе достаточного объема свободной памяти будут обработаны отказы, полученные другими пользовательскими процессами. Применение такого метода ведет к снижению частоты возникновения системных отказов и устранению соперничества: по идеологии он близок к методам, используемым в операционной системе VAX/VMS ([Levy 82]).

Прочитанная глава была посвящена рассмотрению алгоритмов подкачки процессов и замещения страниц, используемых в версии V системы UNIX. Алгоритм подкачки процессов реализует перемещение процессов целиком между основной памятью и устройством выгрузки. Ядро выгружает процессы из памяти, если их размер поглощает всю свободную память в системе (в результате выполнения функций fork, exec и sbrk или в результате естественного увеличения стека), или в том случае, если требуется освободить память для загрузки процесса. Загрузку процессов выполняет специальный процесс подкачки (процесс 0), который запускается всякий раз, как на устройстве выгрузки появляются процессы, готовые к выполнению. Процесс подкачки не прекращает своей работы до тех пор, пока на устройстве выгрузки не останется ни одного такого процесса или пока в основной памяти не останется свободного места. В последнем случае процесс подкачки пытается выгрузить что-нибудь из основной памяти, но в его обязанности входит также слежение за соблюдением требования минимальной продолжительности пребывания выгружаемых процессов в памяти (в целях предотвращения холостой перекачки); по этой причине процесс подкачки не всегда достигает успеха в своей работе. Возобновление процесса подкачки в случае возникновения необходимости в нем производит с интервалом в одну секунду программа обработки прерываний по таймеру.

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

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

1. Набросайте схему реализации алгоритма mfree, который освобождает пространство памяти и возвращает его таблице свободного пространства.

2. В разделе 9.1.2 утверждается, что система блокирует перемещаемый процесс, чтобы другие процессы не могли его трогать с места до момента окончания операции. Что произошло бы, если бы система не делала этого?

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

4. Если стек ядра находится внутри адресного пространства процесса, почему процесс не может выгружать себя сам? Какой на Ваш взгляд должна быть системная программа выгрузки процессов, как она должна запускаться?

5. *Предположим, что ядро пытается выгрузить процесс, чтобы освободить место в памяти для других процессов, загружаемых с устройства выгрузки. Если ни на одном из устройств выгрузки для данного процесса нет места, процесс подкачки приостанавливает свою работу до тех пор, пока место не появится. Возможна ли ситуация, при которой все процессы, находящиеся в памяти, приостановлены, а все готовые к выполнению процессы находятся на устройстве выгрузки? Что нужно предпринять ядру для того, чтобы исправить это положение?

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) увеличивается. Предположим, что "сборщик" страниц выгружает разделяемую страницу на устройство выгрузки, и один из процессов (скажем, родитель) впоследствии получает отказ при обращении к ней. Содержимое виртуальной страницы теперь располагается на физической странице. Объясните, почему процесс-потомок всегда имеет возможность получить верную копию страницы, даже после того, как процесс-родитель что-то запишет на нее. Почему, когда процесс-родитель ведет запись на страницу, он должен немедленно порвать связь с ее дисковой копией?

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].page[0] = i;

 }

}

Рис. 9.30

Примечания:

2

А что же версия IV? Модификация внутреннего варианта системы получила название «версия V».

25

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

26

В версии 6 системы UNIX процесс не может быть выгружен из памяти с целью расчистки места для загружаемого процесса до тех пор, пока загружаемый процесс не проведет на диске 3 секунды. Уходящий из памяти процесс должен провести в памяти не менее 2 секунд. Временной интервал таким образом делится на части, в результате чего повышается производительность системы.

27

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

28

Функция exit используется в варианте _exit, потому что она "очищает" структуры данных, передаваемые через стандартный ввод-вывод (на пользовательском уровне), для обоих процессов, так что оператор printf, используемый родителем, не даст правильный результат — еще один нежелательный побочный эффект от применения функции vfork.