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

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

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

4.4.2. Алгоритм NRU - не использовавшаяся в последнее время страница

Чтобы дать возможность операционной системе собирать полезные статистические данные о том, какие страницы используются, а какие - нет, большинство компьютеров с виртуальной памятью поддерживают два статусных бита, связанных с каждой страницей. Бит R (от Referenced - обращения) устанавливается всякий раз, когда происходит обращение к странице (чтение или запись). Бит М (от Modified - изменение) устанавливается, когда страница записывается (то есть изменяется). Биты содержатся в каждом элементе таблицы страниц, как показано на рис. 4.11. Важно реализовать обновление этих битов при каждом обращении к памяти, поэтому необходимо, чтобы они задавались аппаратно. Если однажды бит был установлен в 1, то он остается равным 1 до тех пор, пока операционная система профаммно не вернет его в состояние 0.

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

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

При возбуждении страничного прерывания операционная система проверяет все страницы и делит их на четыре категории на основании текущих значений битов R и М:

f класс 0: не было обращений и изменений;

f класс 1: не было обращений, страница изменена;

f класс 2: было обращение, страница не изменена;

f класс 3: произошло и обращение, и изменение.

Хотя класс 1 на первый взгляд кажется невозможным, такое случается, когда у страницы из класса 3 бит R сбрасывается во время прерывания по таймеру. Прерывания по таймеру не затирают бит М, поскольку эта информация необходима для того, чтобы знать, нужно ли переписывать страницу на диске или нет. Поэтому если бит R устанавливается на ноль, а М остается нетронутым, страница попадает в класс 1.

Алгоритм NRU (Not Recently Used - не использовавшийся в последнее время) удаляет страницу с помощью случайного поиска в непустом классе с наименьшем номером. Подразумевается, что лучше выгрузить измененную страницу, к которой не было обращений, по крайней мере в течение одного тика системных часов (обычно 20 мс), чем стереть часто используемую. Привлекательность алгоритма NRU заключается в том, что он легок для понимания, умеренно сложен в реализации и дает производительность, которая, конечно, не оптимальна, но бывает вполне достаточной.

4.4.3. Алгоритм FIFO: первым прибыл - первым обслужен

Другим требующим небольших издержек алгоритмом является FIFO (First-In, First-Out - первым прибыл - первым обслужен ). Чтобы проиллюстрировать его работу, рассмотрим универсам, на полках которого можно выставить ровно k различных продуктов. Он предлагает новую удобную пищу: растворимый, глубоко замороженный , экологически чистый йогурт, который можно мгновенно приготовить в микроволновой печи. Покупатели тут же обратили внимание на этот продукт, и наш ограниченный в размерах супермаркет, для того чтобы продавать новинку, должен избавиться от одного из старых товаров.

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

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

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

4.4.4. Алгоритм вторая попытка

в простейшем варианте алгоритма FIFO, который позволяет избежать проблемы вытеснения из памяти часто используемых страниц, у самой старейшей страницы изучается бит R. Если он равен О, значит, страница не только находится в памяти долго, она вдобавок еще и не используется, поэтому немедленно заменяется новой. Если же бит R равен 1, ему присваивается значение О, страница переносится в конец списка, а время ее загрузки обновляется, то есть считается, что страница только что попала в память. Затем процедура продолжается.

Работа этого алгоритма, называемого второй попыткой (second chance), показана на рис. 4.12, а. Здесь изображены страницы от А до Н, хранящиеся в однонаправленном списке и отсортированные по времени их поступления в память. Числа над страницами обозначают их время загрузки в память.

Предположим, что в момент времени 20 происходит страничное прерывание. Самой старшей страницей является страница А, она была загружена в память в момент О, когда начал работу процесс. Если бит R страницы А равен О, она выгружается из памяти или путем записи на диск (если страница грязная ), или просто удаляется (если она чистая ). Во втором случае, если бит R равен 1, страница А передвигается в конец списка, а ее загрузочное время принимает текущее значение (20). При этом бит R сбрасывается. Поиск подходящей страницы продолжается; следующей проверяется страница В.

Алгоритм вторая попытка ищет в списке самую старую страницу, к которой не было обращений в предыдущем временном интервале. Если же происходили ссылки на все страницы, то вторая попытка превращается в обычный алгоритм FIFO. Представьте, что у всех страниц на рис. 4.12, а бит R равен 1. Одну за другой передвигает операционная система страницы в конец списка, очищая бит R каждый раз, когда она перемещает страницу в хвост. Наконец, она вернется к странице А, но теперь уже ее биту R присвоено значение 0. В этот момент страница А выгружается из памяти. Таким образом, алгоритм всегда успешно завершает свою работу.