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

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

9.2 ПОДКАЧКА ПО ЗАПРОСУ

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

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

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

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

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

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

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

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

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

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

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

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

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