Страница:
достаточно памяти для его размещения. Процесс подкачки пытается загру-
зить другой процесс и в случае успеха перезапускает алгоритм подкачки,
продолжая поиск загружаемых процессов.
Если процессу подкачки нужно выгрузить процесс, он просматривает все
процессы в памяти. Прекратившие свое существование процессы не подходят для
выгрузки, поскольку они не занимают физическую память; также не могут быть
выгружены процессы, заблокированные в памяти, например, выполняющие операции
над областями. Ядро предпочитает выгружать приостановленные процессы, пос-
кольку процессы, готовые к выполнению, имеют больше шансов быть вскоре выб-
ранными на выполнение. Решение о выгрузке процесса принимается ядром на ос-
новании его приоритета и продолжительности его пребывания в памяти. Если в
памяти нет ни одного приостановленного процесса, решение о том, какой из
процессов, готовых к выполнению, следует выгрузить, зависит от значения,
присвоенного процессу функцией nice, а также от продолжительности пребывания
процесса в памяти.
Процесс, готовый к выполнению, должен быть резидентным в памяти в тече-
ние по меньшей мере 2 секунд до того, как уйти из нее, а процесс, загружае-
мый в память, должен по меньшей мере 2 секунды пробыть на устройстве выгруз-
ки. Если процесс подкачки не может найти ни одного процесса, подходящего для
выгрузки, или ни одного процесса, подходящего для загрузки, или ни одного
процесса, перед выгрузкой не менее 2 секунд (**) находившегося в памяти, он
приостанавливает свою работу по причине того, что ему нужно загрузить про-
цесс в память, а в памяти нет места для его размещения. В этой ситуации тай-
мер возобновляет выполнение процесса подкачки через каждую секунду. Ядро
---------------------------------------
(**) В версии 6 системы UNIX процесс не может быть выгружен из памяти с
целью расчистки места для загружаемого процесса до тех пор, пока загру-
жаемый процесс не проведет на диске 3 секунды. Уходящий из памяти про-
цесс должен провести в памяти не менее 2 секунд. Временной интервал та-
ким образом делится на части, в результате чего повышается производи-
тельность системы.
261
+------------------------------------------------------------+
| алгоритм swapper /* загрузка выгруженных процессов, |
| * выгрузка других процессов с целью |
| * расчистки места в памяти */ |
| входная информация: отсутствует |
| выходная информация: отсутствует |
| { |
| loop: |
| для (всех выгруженных процессов, готовых к выполнению)|
| выбрать процесс, находящийся в состоянии выгружен-|
| ности дольше остальных; |
| если (таких процессов нет) |
| { |
| приостановиться (до момента, когда возникнет необ-|
| ходимость в загрузке процессов); |
| перейти на loop; |
| } |
| если (в основной памяти достаточно места для размеще- |
| ния процесса) |
| { |
| загрузить процесс; |
| перейти на loop; |
| } |
| /* loop2: сюда вставляются исправления, внесенные в алго- |
| * ритм */ |
| для (всех процессов, загруженных в основную память, |
| кроме прекративших существование и заблокированных в |
| памяти) |
| { |
| если (есть хотя бы один приостановленный процесс) |
| выбрать процесс, у которого сумма приоритета и|
| продолжительности нахождения в памяти наи- |
| большая; |
| в противном случае /* нет ни одного приостанов- |
| * ленного процесса */ |
| выбрать процесс, у которого сумма продолжи- |
| тельности нахождения в памяти и значения nice|
| наибольшая; |
| } |
| если (выбранный процесс не является приостановленным |
| или не соблюдены условия резидентности) |
| приостановиться (до момента, когда появится воз- |
| можность загрузить процесс); |
| в противном случае |
| выгрузить процесс; |
| перейти на loop; /* на loop2 в исправленном алгорит-|
| * ме */ |
| } |
+------------------------------------------------------------+
Рисунок 9.9. Алгоритм подкачки
также возобновляет работу процесса подкачки в том случае, когда один из про-
цессов переходит в состояние приостанова, так как последний может оказаться
более подходящим для выгрузки процессом по сравнению с ранее рассмотренными.
Если процесс подкачки расчистил место в памяти или если он был приостановлен
по причине невозможности сделать это, он возобновляет свою работу с переза-
пуска алгоритма подкачки (с самого его начала), вновь предпринимая попытку
262
загрузить ожидающие выполнения процессы.
На Рисунке 9.10 показана динамика выполнения пяти процессов с указанием
моментов их участия в реализации алгоритма подкачки. Положим для простоты,
что все процессы интенсивно используют ресурсы центрального процессора и что
они не производят обращений к системным функциям; следовательно, переключе-
ние контекста происходит только в результате возникновения прерываний по
таймеру с интервалом в 1 секунду. Процесс подкачки исполняется с наивысшим
приоритетом планирования, поэтому он всегда укладывается в секундный интер-
вал, когда ему есть что делать. Предположим далее, что процессы имеют одина-
ковый размер и что в основной памяти могут одновременно поместиться только
два процесса. Сначала в памяти находятся процессы A и B, остальные процессы
выгружены. Процесс подкачки не может стронуть с места ни один процесс в те-
чение первых двух секунд, поскольку этого требует условие нахождения переме-
щаемого процесса в течение этого интервала на одном месте (в памяти или на
устройстве выгрузки), однако по истечении 2 секунд процесс подкачки выгружа-
ет процессы A и B и загружает на их место процессы C и D. Он пытается также
загрузить и процесс E, но терпит неудачу, поскольку в основной памяти недос-
таточно места для этого. На 3-секундной отметке процесс E все еще годен для
загрузки, поскольку он находился все 3 секунды на устройстве выгрузки, но
процесс подкачки не может выгрузить из памяти ни один из процессов, ибо они
находятся в памяти менее 2 секунд. На 4-секундной отметке процесс подкачки
выгружает процессы C и D и загружает вместо них процессы E и A.
Процесс подкачки выбирает процессы для загрузки, основываясь на продол-
жительности их пребывания на устройстве выгрузки. В качестве другого крите-
рия может применяться более высокий приоритет загружаемого процесса по срав-
нению с остальными, готовыми к выполнению процессами, поскольку такой про-
цесс более предпочтителен для запуска. Практика показала, что такой подход
"несколько" повышает пропускную способность системы в условиях сильной заг-
руженности (см. [Peachey 84]).
Алгоритм выбора процесса для выгрузки из памяти с целью освобождения
места требуемого объема имеет, однако, более серьезные изъяны. Во-первых,
процесс подкачки производит выгрузку на основании приоритета, продолжитель-
ности нахождения в памяти и значения nice. Несмотря на то, что он производит
выгрузку процесса с единственной целью - освободить в памяти место для заг-
ружаемого процесса, он может выгрузить и процесс, который не освобождает
место требуемого размера. Например, если процесс подкачки пытается загрузить
в память процесс размером 1 Мбайт, а в системе отсутствует свободная память,
будет далеко не достаточно выгрузить процесс, занимающий только 2 Кбайта па-
мяти. В качестве альтернативы может быть предложена стратегия выгрузки групп
процессов при условии, что они освобождают место, достаточное для размещения
загружаемых процессов.Эксперименты с использованием машины PDP 11/23 показа-
ли,что в условиях сильной загруженности такая стратегия может увеличить про-
изводительность системы почти на 10 процентов (см. [Peachey 84]).
Во-вторых, если процесс подкачки приостановил свою работу изза того, что
в памяти не хватило места для загрузки процесса, после возобновления он
вновь выбирает процесс для загрузки в память, несмотря на то, что ранее им
уже был сделан выбор. Причина такого поведения заключается в том, что за
прошедшее время в состояние готовности к выполнению могли перейти другие
выгруженные процессы, более подходящие для загрузки в память по сравнению с
ранее выбранным процессом. Однако от этого мало утешения для ранее выбранно-
го процесса, все еще пытающегося загрузиться в память. В некоторых реализа-
циях процесс подкачки стремится к тому, чтобы перед загрузкой в память одно-
го крупного процесса выгрузить большое количество процессов маленького раз-
мера, это изменение в базовом алгоритме подкачки отражено в комментариях к
алгоритму (Рисунок 9.9).
В-третьих, если процесс подкачки выбирает для выгрузки процесс, находя-
щийся в состоянии "готовности к выполнению", не исключена возможность того,
что этот процесс после загрузки в память ни разу не был запущен на исполне-
ние. Этот случай показан на Рисунке 9.11, из которого видно, что ядро загру-
263
жает процесс D на 2- секундной отметке, запускает процесс C, а затем на
3-секундной отметке процесс D выгружается в пользу процесса E (уступая пос-
леднему в значении nice), несмотря на то, что процессу D так и не был пре-
доставлен ЦП. Понятно, что такая ситуация является нежелательной.
Следует упомянуть еще об одной опасности. Если при попытке выгрузить
процесс на устройстве выгрузки не будет найдено свободное место, в системе
может возникнуть тупиковая ситуация, при которой: все процессы в основной
Время Процесс A B C D E
--+--------------+-----------+-----------+-----------+-----------
0| 0 | 0 | выгружен | выгружен | выгружен
| запущен | | 0 | 0 | 0
| | | | |
| | | | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 1
1| | запущен | | |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 2 | 2 | 2 | 2
2| выгружен | выгружен | загружен | загружен |
| 0 | 0 | 0 | 0 |
| | | запущен | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 3
3| | | | запущен |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 2 | 2 | 2 | 4
4| загружен | | выгружен | выгружен | загружен
| 0 | | 0 | 0 | 0
| | | | | запущен
| | | | |
| | | | |
--+- 1 | 3 | 1 | 1 | 1
5| запущен | | | |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 4 | 2 | 2 | 2
6| выгружен | загружен | загружен | | выгружен
| 0 | 0 | 0 | | 0
| | запущен | | |
| | | | |
v
Рисунок 9.10. Последовательность операций, выполняемых
процессом подкачки
264
Время Процесс A B C D E
--+--------------+-----------+-----------+-----------+-----------
0| 0 | 0 | выгружен | nice 25 | выгружен
| запущен | | 0 | выгружен | 0
| | | | 0 |
| | | | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 1
1| | запущен | | |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 2 | 2 | 2 | 2
2| выгружен | выгружен | загружен | загружен |
| 0 | 0 | 0 | 0 |
| | | запущен | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 3
3| | | | выгружен | загружен
| | | | 0 | 0
| | | | | запущен
| | | | |
| | | | |
--+- 2 | 2 | 2 | 1 | 1
4| загружен | | выгружен | |
| 0 | | 0 | |
| запущен | | | |
| | | | |
| | | | |
--+- 1 | 3 | 1 | 2 | 2
5| | загружен | | | выгружен
| | 0 | | | 0
| | запущен | | |
| | | | |
| | | | |
--+- 2 | 1 | 2 | 3 | 1
6| выгружен | | | загружен |
| 0 | | | 0 |
| | | | запущен |
| | | | |
v
Рисунок 9.11. Загрузка процессов в случае разбивки временных
интервалов на части
памяти находятся в состоянии приостанова, все готовые к выполнению процессы
выгружены, для новых процессов на устройстве выгрузки уже нет места, нет
свободного места и в основной памяти. Эта ситуация разбирается в упражнении
9.5. Интерес к проблемам, связанным с подкачкой процессов, в последние годы
спал в связи с реализацией алгоритмов подкачки страниц памяти.
265
Алгоритм подкачки страниц памяти поддерживается на машинах со страничной
организацией памяти и с ЦП, имеющим прерываемые команды (***). В системах с
подкачкой страниц отсутствуют ограничения на размер процесса, связанные с
объемом доступной физической памяти. Например, в машинах с объемом физичес-
кой памяти 1 и 2 Мбайта могут исполняться процессы размером 4 или 5 Мбайт.
Ограничение на виртуальный размер процесса, связанное с объемом адресуемой
виртуальной памяти, остается в силе и здесь. Поскольку процесс может не по-
меститься в физической памяти, ядру приходится динамически загружать в па-
мять отдельные его части и исполнять их, несмотря на отсутствие остальных
частей. В механизме подкачки страниц все открыто для пользовательских прог-
рамм, за исключением разрешенного процессу виртуального размера.
Процессы стремятся исполнять команды небольшими порциями, которые имену-
ются программными циклами или подпрограммами, используемые ими указатели
группируются в небольшие поднаборы, располагаемые в информационном простран-
стве процесса. В этом состоит суть так называемого принципа "локальности".
Деннингом [Denning 68] было сформулировано понятие рабочего множества про-
цесса как совокупности страниц, использованных процессом в последних n ссыл-
ках на адресное пространство памяти; число n называется окном рабочего мно-
жества. Поскольку рабочее множество процесса является частью от целого, в
основной памяти может поместиться больше процессов по сравнению с теми сис-
темами, где управление памятью базируется на подкачке процессов, что в ко-
нечном итоге приводит к увеличению производительности системы. Когда процесс
обращается к странице, отсутствующей в его рабочем множестве, возникает
ошибка, при обработке которой ядро корректирует рабочее множество процесса,
в случае необходимости подкачивая страницы с внешнего устройства.
На Рисунке 9.12 приведена последовательность используемых процессом ука-
зателей страниц, описывающих рабочие множества с окнами различных размеров
при условии соблюдения алгоритма замещения "стариков" (замещения страниц пу-
тем откачки тех, к которым наиболее долго не было обращений). По мере выпол-
нения процесса его рабочее множество видоизменяется в соответствии с исполь-
зуемыми процессом указателями страниц; увеличение размера окна влечет за со-
бой увеличение рабочего множества и, с другой стороны, сокращение числа оши-
бок в выполнении процесса. Использование неизменного рабочего множества не
практикуется, поскольку запоминание очередности следования указателей стра-
ниц потребовало бы слишком больших затрат. Приблизительное соответствие меж-
ду изменяемым рабочим множеством и пространством процесса достигается путем
установки бита упоминания (reference bit) при обращении к странице памяти, а
также периодическим опросом указателей страниц. Если на страницу была сдела-
на ссылка, эта страница включается в рабочее множество; в противном случае
она "дозревает" в памяти в ожидании своей очереди.
В случае возникновения ошибки из-за обращения к странице, отсутствующей
в рабочем множестве, ядро приостанавливает выполнение процесса до тех пор,
пока страница не будет считана в память и не станет доступной процессу. Ког-
да страница будет загружена, процесс перезапустит ту команду, на которой вы-
полнение процесса было приостановлено из-за ошибки. Таким образом, работа
подсистемы замещения страниц распадается на две части: откачка редко исполь-
зуемых страниц на устройство выгрузки и обработка ошибок из-за отсутствия
нужной страницы. Такое общее толкование механизма замещения страниц, конечно
же, выходит за пределы одной конкретной системы. Оставшуюся часть главы мы
посвятим более детальному рассмотрению особенностей реализации этого меха-
низма в версии V системы UNIX.
---------------------------------------
(***) Если при исполнении команды возникает ошибка, связанная с отсутствием
страницы, после обработки ошибки ЦП обязан перезапустить команду, пос-
кольку промежуточные результаты, полученные к моменту возникновения
ошибки, могут быть утрачены.
266
Для поддержки функций управления памятью на машинном (низком) уровне и
для реализации механизма замещения страниц ядро использует 4 основные струк-
туры данных: записи таблицы страниц, дескрипторы дисковых блоков, таблицу
содержимого страничных блоков (page frame data table - сокращенно: pfdata) и
таблицу использования области подкачки. Место для таблицы pfdata выделяется
один раз на все время жизни системы, для других же структур страницы памяти
выделяются динамически.
Из главы 6 нам известно, что каждая область располагает своими таблицами
страниц, с помощью которых осуществляется доступ к физической памяти. Каждая
запись таблицы страниц (Рисунок 9.13) состоит из физического адреса страни-
цы, кода защиты, в разрядах которого описываются права доступа процесса к
странице (на чтение, запись и исполнение), а также следующих двоичных полей,
используемых механизмом замещения страниц:
Последователь-
ность указате- Рабочие множества Размеры окон
лей страниц 2 3 4 5
+------------+ +-------+----------+-------------+----------------+
| 24 | | 24 | 24 | 24 | 24 |
+------------+ | | | | |
| 15 | | 15 24 | 15 24 | 15 24 | 15 24 |
+------------+ | | | | |
| 18 | | 18 15 | 18 15 24 | 18 15 24 | 18 15 24 |
+------------+ | | | | |
| 23 | | 23 18 | 23 18 15 | 23 18 15 24 | 23 18 15 24 |
+------------+ | | | - | - |
| 24 | | 24 23 | 24 23 18 | - | - |
+------------+ | | | - | - |
| 17 | | 17 24 | 17 24 23 | 17 24 23 18 | 17 24 23 18 15 |
+------------+ | | | - | - |
| 18 | | 18 17 | 18 17 24 | - | - |
+------------+ | | - | - | - |
| 24 | | 24 18 | - | - | - |
+------------+ | | - | - | - |
| 18 | | 18 24 | - | - | - |
+------------+ | | - | - | - |
| 17 | | 17 18 | - | - | - |
+------------+ | | - | - | - |
| 17 | | | - | - | - |
+------------+ | | - | - | - |
| 15 | | 15 17 | 15 17 18 | 15 17 18 24 | - |
+------------+ | | | - | - |
| 24 | | 24 15 | 24 15 17 | - | - |
+------------+ | | - | - | - |
| 17 | | 17 24 | - | - | - |
+------------+ | | - | - | - |
| 24 | | 24 17 | - | - | - |
+------------+ | | - | - | - |
| 18 | | 18 24 | 18 24 17 | - | - |
+------------+ +-------+----------+-------------+----------------+
Рисунок 9.12. Рабочее множество процесса
* бит доступности
* бит упоминания
267
* бит модификации
* бит копирования при записи
* "возраст" страницы
Установка бита доступности свидетельствует о правильности содержимого
страницы памяти, однако из того, что бит доступности выключен, не следует с
необходимостью то, что ссылка на страницу недопустима, в чем мы убедимся
позже. Бит упоминания устанавливается в том случае, если процесс делает
ссылку на страницу, а бит модификации - в том случае, если процесс скоррек-
тировал содержимое страницы. Установка бита копирования при записи, произво-
димая во время выполнения системной функции fork, свидетельствует о том, что
ядру в случае, когда процесс корректирует содержимое страницы, следует соз-
давать ее новую копию. Наконец, "возраст" страницы говорит о продолжитель-
ности ее пребывания в составе рабочего множества процесса. Биты доступности,
копирования при записи и "возраст" страницы устанавливаются ядром, биты упо-
минания и модификации - аппаратным путем; в разделе 9.2.4 рассматриваются
конфигурации, в которых эти возможности не поддерживаются аппаратурой.
+--------+ +->+----------------------+---------------------------+
| | | | | |
| | | +----------------------+---------------------------+
| | | | | |
| | | +----------------------+---------------------------+
| Область| | | | |
| | | +----------------------+---------------------------+
| | | |Записи таблицы страниц|Дескрипторы дисковых блоков|
| ----+-+ +----------------------+---------------------------+
| | | | |
| | +----------------------+---------------------------+
| | | | |
+--------+ +----------------------+---------------------------+
| | |
+----------------------+---------------------------+
| | |
+----------------------+---------------------------+
| | |
+----------------------+---------------------------+
| | |
+----------------------+---------------------------+
Запись таблицы страниц
+-----------------------------+-------+-----+-----+----+-----+---+
| Адрес страницы (физический) |Возраст|Копи-|Моди-|Упо-|До- |За-|
| | |рова-|фика-|ми- |пус- |щи-|
| | |ние |ция |на- |ти- |та |
| | |при | |ние |мость| |
| | |запи-| | | | |
| | |си | | | | |
+-----------------------------+-------+-----+-----+----+-----+---+
Дескриптор дискового блока
+-----------------------+---------------+------------------------+
| Устройство выгрузки | Номер блока | Тип (находится на ус- |
| | | тройстве выгрузки, в |
| | | файле, при обращении |
| | | обнуляется, заполняет- |
| | | ся) |
+-----------------------+---------------+------------------------+
Рисунок 9.13. Записи таблицы страниц и дескрипторы дисковых блоков
268
Каждая запись таблицы страниц связана с дескриптором дискового блока,
описывающим дисковую копию виртуальной страницы (Рисунок 9.13). Поэтому про-
цессы, использующие разделяемую область, обращаются к общим записям таблицы
страниц и к одним и тем же дескрипторам дисковых блоков. Содержимое вирту-
альной страницы располагается либо в отдельном блоке на устройстве выгрузки,
либо в исполняемом файле, либо вообще отсутствует на устройстве выгрузки.
Если страница находится на устройстве выгрузки, в дескрипторе дискового бло-
ка содержится логический номер устройства и номер блока, по которым можно
отыскать содержимое страницы. Если страница содержится в исполняемом файле,
в дескрипторе дискового блока располагается номер логического блока в файле
с содержимым страницы; ядро может быстро преобразовать этот номер в адрес на
диске. В дескрипторе дискового блока также имеется информация о двух уста-
навливаемых функцией exec особых условиях: страница при обращении к ней за-
полняется ("demand fill") или обнуляется ("demand zero"). Разъяснения по
этому поводу даются в разделе 9.2.1.2.
В таблице pfdata описывается каждая страница физической памяти. Записи
таблицы проиндексированы по номеру страницы и состоят из следующих полей:
* Статус страницы, указывающий на то, что страница располагается на уст-
ройстве выгрузки или в исполняемом файле, что к странице произведено об-
ращение по прямому доступу в память (путем считывания информации с уст-
ройства выгрузки), или на то, что страница может быть переназначена.
* Количество процессов, ссылающихся на страницу. Счетчик ссылок хранит
число записей в таблице страниц, имеющих ссылку на текущую страницу. Это
значение может отличаться от количества процессов, использующих разделя-
емую область с данной страницей, в чем мы убедимся чуть позже, когда бу-
дем снова обращаться к алгоритму функции fork.
* Логический номер устройства (устройства выгрузки или файловой системы) и
номер блока, указывающие расположение содержимого страницы.
* Указатели на другие записи таблицы pfdata в соответствии со списком сво-
бодных страниц или с хеш-очередью страниц.
По аналогии с буферным кешем ядро связывает записи таблицы pfdata в спи-
сок свободных страниц и хеш-очередь. Список свободных страниц представляет
собой буфер, который содержит страницы, доступные для переназначения, однако
процесс, обратившийся к этим страницам, может столкнуться с ошибкой адреса-
ции, так и не получив соответствующую страницу из списка. Этот список дает
ядру возможность сократить число операций чтения с устройства выгрузки. Ядро
зить другой процесс и в случае успеха перезапускает алгоритм подкачки,
продолжая поиск загружаемых процессов.
Если процессу подкачки нужно выгрузить процесс, он просматривает все
процессы в памяти. Прекратившие свое существование процессы не подходят для
выгрузки, поскольку они не занимают физическую память; также не могут быть
выгружены процессы, заблокированные в памяти, например, выполняющие операции
над областями. Ядро предпочитает выгружать приостановленные процессы, пос-
кольку процессы, готовые к выполнению, имеют больше шансов быть вскоре выб-
ранными на выполнение. Решение о выгрузке процесса принимается ядром на ос-
новании его приоритета и продолжительности его пребывания в памяти. Если в
памяти нет ни одного приостановленного процесса, решение о том, какой из
процессов, готовых к выполнению, следует выгрузить, зависит от значения,
присвоенного процессу функцией nice, а также от продолжительности пребывания
процесса в памяти.
Процесс, готовый к выполнению, должен быть резидентным в памяти в тече-
ние по меньшей мере 2 секунд до того, как уйти из нее, а процесс, загружае-
мый в память, должен по меньшей мере 2 секунды пробыть на устройстве выгруз-
ки. Если процесс подкачки не может найти ни одного процесса, подходящего для
выгрузки, или ни одного процесса, подходящего для загрузки, или ни одного
процесса, перед выгрузкой не менее 2 секунд (**) находившегося в памяти, он
приостанавливает свою работу по причине того, что ему нужно загрузить про-
цесс в память, а в памяти нет места для его размещения. В этой ситуации тай-
мер возобновляет выполнение процесса подкачки через каждую секунду. Ядро
---------------------------------------
(**) В версии 6 системы UNIX процесс не может быть выгружен из памяти с
целью расчистки места для загружаемого процесса до тех пор, пока загру-
жаемый процесс не проведет на диске 3 секунды. Уходящий из памяти про-
цесс должен провести в памяти не менее 2 секунд. Временной интервал та-
ким образом делится на части, в результате чего повышается производи-
тельность системы.
261
+------------------------------------------------------------+
| алгоритм swapper /* загрузка выгруженных процессов, |
| * выгрузка других процессов с целью |
| * расчистки места в памяти */ |
| входная информация: отсутствует |
| выходная информация: отсутствует |
| { |
| loop: |
| для (всех выгруженных процессов, готовых к выполнению)|
| выбрать процесс, находящийся в состоянии выгружен-|
| ности дольше остальных; |
| если (таких процессов нет) |
| { |
| приостановиться (до момента, когда возникнет необ-|
| ходимость в загрузке процессов); |
| перейти на loop; |
| } |
| если (в основной памяти достаточно места для размеще- |
| ния процесса) |
| { |
| загрузить процесс; |
| перейти на loop; |
| } |
| /* loop2: сюда вставляются исправления, внесенные в алго- |
| * ритм */ |
| для (всех процессов, загруженных в основную память, |
| кроме прекративших существование и заблокированных в |
| памяти) |
| { |
| если (есть хотя бы один приостановленный процесс) |
| выбрать процесс, у которого сумма приоритета и|
| продолжительности нахождения в памяти наи- |
| большая; |
| в противном случае /* нет ни одного приостанов- |
| * ленного процесса */ |
| выбрать процесс, у которого сумма продолжи- |
| тельности нахождения в памяти и значения nice|
| наибольшая; |
| } |
| если (выбранный процесс не является приостановленным |
| или не соблюдены условия резидентности) |
| приостановиться (до момента, когда появится воз- |
| можность загрузить процесс); |
| в противном случае |
| выгрузить процесс; |
| перейти на loop; /* на loop2 в исправленном алгорит-|
| * ме */ |
| } |
+------------------------------------------------------------+
Рисунок 9.9. Алгоритм подкачки
также возобновляет работу процесса подкачки в том случае, когда один из про-
цессов переходит в состояние приостанова, так как последний может оказаться
более подходящим для выгрузки процессом по сравнению с ранее рассмотренными.
Если процесс подкачки расчистил место в памяти или если он был приостановлен
по причине невозможности сделать это, он возобновляет свою работу с переза-
пуска алгоритма подкачки (с самого его начала), вновь предпринимая попытку
262
загрузить ожидающие выполнения процессы.
На Рисунке 9.10 показана динамика выполнения пяти процессов с указанием
моментов их участия в реализации алгоритма подкачки. Положим для простоты,
что все процессы интенсивно используют ресурсы центрального процессора и что
они не производят обращений к системным функциям; следовательно, переключе-
ние контекста происходит только в результате возникновения прерываний по
таймеру с интервалом в 1 секунду. Процесс подкачки исполняется с наивысшим
приоритетом планирования, поэтому он всегда укладывается в секундный интер-
вал, когда ему есть что делать. Предположим далее, что процессы имеют одина-
ковый размер и что в основной памяти могут одновременно поместиться только
два процесса. Сначала в памяти находятся процессы A и B, остальные процессы
выгружены. Процесс подкачки не может стронуть с места ни один процесс в те-
чение первых двух секунд, поскольку этого требует условие нахождения переме-
щаемого процесса в течение этого интервала на одном месте (в памяти или на
устройстве выгрузки), однако по истечении 2 секунд процесс подкачки выгружа-
ет процессы A и B и загружает на их место процессы C и D. Он пытается также
загрузить и процесс E, но терпит неудачу, поскольку в основной памяти недос-
таточно места для этого. На 3-секундной отметке процесс E все еще годен для
загрузки, поскольку он находился все 3 секунды на устройстве выгрузки, но
процесс подкачки не может выгрузить из памяти ни один из процессов, ибо они
находятся в памяти менее 2 секунд. На 4-секундной отметке процесс подкачки
выгружает процессы C и D и загружает вместо них процессы E и A.
Процесс подкачки выбирает процессы для загрузки, основываясь на продол-
жительности их пребывания на устройстве выгрузки. В качестве другого крите-
рия может применяться более высокий приоритет загружаемого процесса по срав-
нению с остальными, готовыми к выполнению процессами, поскольку такой про-
цесс более предпочтителен для запуска. Практика показала, что такой подход
"несколько" повышает пропускную способность системы в условиях сильной заг-
руженности (см. [Peachey 84]).
Алгоритм выбора процесса для выгрузки из памяти с целью освобождения
места требуемого объема имеет, однако, более серьезные изъяны. Во-первых,
процесс подкачки производит выгрузку на основании приоритета, продолжитель-
ности нахождения в памяти и значения nice. Несмотря на то, что он производит
выгрузку процесса с единственной целью - освободить в памяти место для заг-
ружаемого процесса, он может выгрузить и процесс, который не освобождает
место требуемого размера. Например, если процесс подкачки пытается загрузить
в память процесс размером 1 Мбайт, а в системе отсутствует свободная память,
будет далеко не достаточно выгрузить процесс, занимающий только 2 Кбайта па-
мяти. В качестве альтернативы может быть предложена стратегия выгрузки групп
процессов при условии, что они освобождают место, достаточное для размещения
загружаемых процессов.Эксперименты с использованием машины PDP 11/23 показа-
ли,что в условиях сильной загруженности такая стратегия может увеличить про-
изводительность системы почти на 10 процентов (см. [Peachey 84]).
Во-вторых, если процесс подкачки приостановил свою работу изза того, что
в памяти не хватило места для загрузки процесса, после возобновления он
вновь выбирает процесс для загрузки в память, несмотря на то, что ранее им
уже был сделан выбор. Причина такого поведения заключается в том, что за
прошедшее время в состояние готовности к выполнению могли перейти другие
выгруженные процессы, более подходящие для загрузки в память по сравнению с
ранее выбранным процессом. Однако от этого мало утешения для ранее выбранно-
го процесса, все еще пытающегося загрузиться в память. В некоторых реализа-
циях процесс подкачки стремится к тому, чтобы перед загрузкой в память одно-
го крупного процесса выгрузить большое количество процессов маленького раз-
мера, это изменение в базовом алгоритме подкачки отражено в комментариях к
алгоритму (Рисунок 9.9).
В-третьих, если процесс подкачки выбирает для выгрузки процесс, находя-
щийся в состоянии "готовности к выполнению", не исключена возможность того,
что этот процесс после загрузки в память ни разу не был запущен на исполне-
ние. Этот случай показан на Рисунке 9.11, из которого видно, что ядро загру-
263
жает процесс D на 2- секундной отметке, запускает процесс C, а затем на
3-секундной отметке процесс D выгружается в пользу процесса E (уступая пос-
леднему в значении nice), несмотря на то, что процессу D так и не был пре-
доставлен ЦП. Понятно, что такая ситуация является нежелательной.
Следует упомянуть еще об одной опасности. Если при попытке выгрузить
процесс на устройстве выгрузки не будет найдено свободное место, в системе
может возникнуть тупиковая ситуация, при которой: все процессы в основной
Время Процесс A B C D E
--+--------------+-----------+-----------+-----------+-----------
0| 0 | 0 | выгружен | выгружен | выгружен
| запущен | | 0 | 0 | 0
| | | | |
| | | | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 1
1| | запущен | | |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 2 | 2 | 2 | 2
2| выгружен | выгружен | загружен | загружен |
| 0 | 0 | 0 | 0 |
| | | запущен | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 3
3| | | | запущен |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 2 | 2 | 2 | 4
4| загружен | | выгружен | выгружен | загружен
| 0 | | 0 | 0 | 0
| | | | | запущен
| | | | |
| | | | |
--+- 1 | 3 | 1 | 1 | 1
5| запущен | | | |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 4 | 2 | 2 | 2
6| выгружен | загружен | загружен | | выгружен
| 0 | 0 | 0 | | 0
| | запущен | | |
| | | | |
v
Рисунок 9.10. Последовательность операций, выполняемых
процессом подкачки
264
Время Процесс A B C D E
--+--------------+-----------+-----------+-----------+-----------
0| 0 | 0 | выгружен | nice 25 | выгружен
| запущен | | 0 | выгружен | 0
| | | | 0 |
| | | | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 1
1| | запущен | | |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 2 | 2 | 2 | 2
2| выгружен | выгружен | загружен | загружен |
| 0 | 0 | 0 | 0 |
| | | запущен | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 3
3| | | | выгружен | загружен
| | | | 0 | 0
| | | | | запущен
| | | | |
| | | | |
--+- 2 | 2 | 2 | 1 | 1
4| загружен | | выгружен | |
| 0 | | 0 | |
| запущен | | | |
| | | | |
| | | | |
--+- 1 | 3 | 1 | 2 | 2
5| | загружен | | | выгружен
| | 0 | | | 0
| | запущен | | |
| | | | |
| | | | |
--+- 2 | 1 | 2 | 3 | 1
6| выгружен | | | загружен |
| 0 | | | 0 |
| | | | запущен |
| | | | |
v
Рисунок 9.11. Загрузка процессов в случае разбивки временных
интервалов на части
памяти находятся в состоянии приостанова, все готовые к выполнению процессы
выгружены, для новых процессов на устройстве выгрузки уже нет места, нет
свободного места и в основной памяти. Эта ситуация разбирается в упражнении
9.5. Интерес к проблемам, связанным с подкачкой процессов, в последние годы
спал в связи с реализацией алгоритмов подкачки страниц памяти.
265
Алгоритм подкачки страниц памяти поддерживается на машинах со страничной
организацией памяти и с ЦП, имеющим прерываемые команды (***). В системах с
подкачкой страниц отсутствуют ограничения на размер процесса, связанные с
объемом доступной физической памяти. Например, в машинах с объемом физичес-
кой памяти 1 и 2 Мбайта могут исполняться процессы размером 4 или 5 Мбайт.
Ограничение на виртуальный размер процесса, связанное с объемом адресуемой
виртуальной памяти, остается в силе и здесь. Поскольку процесс может не по-
меститься в физической памяти, ядру приходится динамически загружать в па-
мять отдельные его части и исполнять их, несмотря на отсутствие остальных
частей. В механизме подкачки страниц все открыто для пользовательских прог-
рамм, за исключением разрешенного процессу виртуального размера.
Процессы стремятся исполнять команды небольшими порциями, которые имену-
ются программными циклами или подпрограммами, используемые ими указатели
группируются в небольшие поднаборы, располагаемые в информационном простран-
стве процесса. В этом состоит суть так называемого принципа "локальности".
Деннингом [Denning 68] было сформулировано понятие рабочего множества про-
цесса как совокупности страниц, использованных процессом в последних n ссыл-
ках на адресное пространство памяти; число n называется окном рабочего мно-
жества. Поскольку рабочее множество процесса является частью от целого, в
основной памяти может поместиться больше процессов по сравнению с теми сис-
темами, где управление памятью базируется на подкачке процессов, что в ко-
нечном итоге приводит к увеличению производительности системы. Когда процесс
обращается к странице, отсутствующей в его рабочем множестве, возникает
ошибка, при обработке которой ядро корректирует рабочее множество процесса,
в случае необходимости подкачивая страницы с внешнего устройства.
На Рисунке 9.12 приведена последовательность используемых процессом ука-
зателей страниц, описывающих рабочие множества с окнами различных размеров
при условии соблюдения алгоритма замещения "стариков" (замещения страниц пу-
тем откачки тех, к которым наиболее долго не было обращений). По мере выпол-
нения процесса его рабочее множество видоизменяется в соответствии с исполь-
зуемыми процессом указателями страниц; увеличение размера окна влечет за со-
бой увеличение рабочего множества и, с другой стороны, сокращение числа оши-
бок в выполнении процесса. Использование неизменного рабочего множества не
практикуется, поскольку запоминание очередности следования указателей стра-
ниц потребовало бы слишком больших затрат. Приблизительное соответствие меж-
ду изменяемым рабочим множеством и пространством процесса достигается путем
установки бита упоминания (reference bit) при обращении к странице памяти, а
также периодическим опросом указателей страниц. Если на страницу была сдела-
на ссылка, эта страница включается в рабочее множество; в противном случае
она "дозревает" в памяти в ожидании своей очереди.
В случае возникновения ошибки из-за обращения к странице, отсутствующей
в рабочем множестве, ядро приостанавливает выполнение процесса до тех пор,
пока страница не будет считана в память и не станет доступной процессу. Ког-
да страница будет загружена, процесс перезапустит ту команду, на которой вы-
полнение процесса было приостановлено из-за ошибки. Таким образом, работа
подсистемы замещения страниц распадается на две части: откачка редко исполь-
зуемых страниц на устройство выгрузки и обработка ошибок из-за отсутствия
нужной страницы. Такое общее толкование механизма замещения страниц, конечно
же, выходит за пределы одной конкретной системы. Оставшуюся часть главы мы
посвятим более детальному рассмотрению особенностей реализации этого меха-
низма в версии V системы UNIX.
---------------------------------------
(***) Если при исполнении команды возникает ошибка, связанная с отсутствием
страницы, после обработки ошибки ЦП обязан перезапустить команду, пос-
кольку промежуточные результаты, полученные к моменту возникновения
ошибки, могут быть утрачены.
266
Для поддержки функций управления памятью на машинном (низком) уровне и
для реализации механизма замещения страниц ядро использует 4 основные струк-
туры данных: записи таблицы страниц, дескрипторы дисковых блоков, таблицу
содержимого страничных блоков (page frame data table - сокращенно: pfdata) и
таблицу использования области подкачки. Место для таблицы pfdata выделяется
один раз на все время жизни системы, для других же структур страницы памяти
выделяются динамически.
Из главы 6 нам известно, что каждая область располагает своими таблицами
страниц, с помощью которых осуществляется доступ к физической памяти. Каждая
запись таблицы страниц (Рисунок 9.13) состоит из физического адреса страни-
цы, кода защиты, в разрядах которого описываются права доступа процесса к
странице (на чтение, запись и исполнение), а также следующих двоичных полей,
используемых механизмом замещения страниц:
Последователь-
ность указате- Рабочие множества Размеры окон
лей страниц 2 3 4 5
+------------+ +-------+----------+-------------+----------------+
| 24 | | 24 | 24 | 24 | 24 |
+------------+ | | | | |
| 15 | | 15 24 | 15 24 | 15 24 | 15 24 |
+------------+ | | | | |
| 18 | | 18 15 | 18 15 24 | 18 15 24 | 18 15 24 |
+------------+ | | | | |
| 23 | | 23 18 | 23 18 15 | 23 18 15 24 | 23 18 15 24 |
+------------+ | | | - | - |
| 24 | | 24 23 | 24 23 18 | - | - |
+------------+ | | | - | - |
| 17 | | 17 24 | 17 24 23 | 17 24 23 18 | 17 24 23 18 15 |
+------------+ | | | - | - |
| 18 | | 18 17 | 18 17 24 | - | - |
+------------+ | | - | - | - |
| 24 | | 24 18 | - | - | - |
+------------+ | | - | - | - |
| 18 | | 18 24 | - | - | - |
+------------+ | | - | - | - |
| 17 | | 17 18 | - | - | - |
+------------+ | | - | - | - |
| 17 | | | - | - | - |
+------------+ | | - | - | - |
| 15 | | 15 17 | 15 17 18 | 15 17 18 24 | - |
+------------+ | | | - | - |
| 24 | | 24 15 | 24 15 17 | - | - |
+------------+ | | - | - | - |
| 17 | | 17 24 | - | - | - |
+------------+ | | - | - | - |
| 24 | | 24 17 | - | - | - |
+------------+ | | - | - | - |
| 18 | | 18 24 | 18 24 17 | - | - |
+------------+ +-------+----------+-------------+----------------+
Рисунок 9.12. Рабочее множество процесса
* бит доступности
* бит упоминания
267
* бит модификации
* бит копирования при записи
* "возраст" страницы
Установка бита доступности свидетельствует о правильности содержимого
страницы памяти, однако из того, что бит доступности выключен, не следует с
необходимостью то, что ссылка на страницу недопустима, в чем мы убедимся
позже. Бит упоминания устанавливается в том случае, если процесс делает
ссылку на страницу, а бит модификации - в том случае, если процесс скоррек-
тировал содержимое страницы. Установка бита копирования при записи, произво-
димая во время выполнения системной функции fork, свидетельствует о том, что
ядру в случае, когда процесс корректирует содержимое страницы, следует соз-
давать ее новую копию. Наконец, "возраст" страницы говорит о продолжитель-
ности ее пребывания в составе рабочего множества процесса. Биты доступности,
копирования при записи и "возраст" страницы устанавливаются ядром, биты упо-
минания и модификации - аппаратным путем; в разделе 9.2.4 рассматриваются
конфигурации, в которых эти возможности не поддерживаются аппаратурой.
+--------+ +->+----------------------+---------------------------+
| | | | | |
| | | +----------------------+---------------------------+
| | | | | |
| | | +----------------------+---------------------------+
| Область| | | | |
| | | +----------------------+---------------------------+
| | | |Записи таблицы страниц|Дескрипторы дисковых блоков|
| ----+-+ +----------------------+---------------------------+
| | | | |
| | +----------------------+---------------------------+
| | | | |
+--------+ +----------------------+---------------------------+
| | |
+----------------------+---------------------------+
| | |
+----------------------+---------------------------+
| | |
+----------------------+---------------------------+
| | |
+----------------------+---------------------------+
Запись таблицы страниц
+-----------------------------+-------+-----+-----+----+-----+---+
| Адрес страницы (физический) |Возраст|Копи-|Моди-|Упо-|До- |За-|
| | |рова-|фика-|ми- |пус- |щи-|
| | |ние |ция |на- |ти- |та |
| | |при | |ние |мость| |
| | |запи-| | | | |
| | |си | | | | |
+-----------------------------+-------+-----+-----+----+-----+---+
Дескриптор дискового блока
+-----------------------+---------------+------------------------+
| Устройство выгрузки | Номер блока | Тип (находится на ус- |
| | | тройстве выгрузки, в |
| | | файле, при обращении |
| | | обнуляется, заполняет- |
| | | ся) |
+-----------------------+---------------+------------------------+
Рисунок 9.13. Записи таблицы страниц и дескрипторы дисковых блоков
268
Каждая запись таблицы страниц связана с дескриптором дискового блока,
описывающим дисковую копию виртуальной страницы (Рисунок 9.13). Поэтому про-
цессы, использующие разделяемую область, обращаются к общим записям таблицы
страниц и к одним и тем же дескрипторам дисковых блоков. Содержимое вирту-
альной страницы располагается либо в отдельном блоке на устройстве выгрузки,
либо в исполняемом файле, либо вообще отсутствует на устройстве выгрузки.
Если страница находится на устройстве выгрузки, в дескрипторе дискового бло-
ка содержится логический номер устройства и номер блока, по которым можно
отыскать содержимое страницы. Если страница содержится в исполняемом файле,
в дескрипторе дискового блока располагается номер логического блока в файле
с содержимым страницы; ядро может быстро преобразовать этот номер в адрес на
диске. В дескрипторе дискового блока также имеется информация о двух уста-
навливаемых функцией exec особых условиях: страница при обращении к ней за-
полняется ("demand fill") или обнуляется ("demand zero"). Разъяснения по
этому поводу даются в разделе 9.2.1.2.
В таблице pfdata описывается каждая страница физической памяти. Записи
таблицы проиндексированы по номеру страницы и состоят из следующих полей:
* Статус страницы, указывающий на то, что страница располагается на уст-
ройстве выгрузки или в исполняемом файле, что к странице произведено об-
ращение по прямому доступу в память (путем считывания информации с уст-
ройства выгрузки), или на то, что страница может быть переназначена.
* Количество процессов, ссылающихся на страницу. Счетчик ссылок хранит
число записей в таблице страниц, имеющих ссылку на текущую страницу. Это
значение может отличаться от количества процессов, использующих разделя-
емую область с данной страницей, в чем мы убедимся чуть позже, когда бу-
дем снова обращаться к алгоритму функции fork.
* Логический номер устройства (устройства выгрузки или файловой системы) и
номер блока, указывающие расположение содержимого страницы.
* Указатели на другие записи таблицы pfdata в соответствии со списком сво-
бодных страниц или с хеш-очередью страниц.
По аналогии с буферным кешем ядро связывает записи таблицы pfdata в спи-
сок свободных страниц и хеш-очередь. Список свободных страниц представляет
собой буфер, который содержит страницы, доступные для переназначения, однако
процесс, обратившийся к этим страницам, может столкнуться с ошибкой адреса-
ции, так и не получив соответствующую страницу из списка. Этот список дает
ядру возможность сократить число операций чтения с устройства выгрузки. Ядро