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

На рис. 4.15 продемонстрировано, как работает видоизмененный алгоритм, известный под названием старения (aging). Предположим, что после первого тика часов биты R для страниц от О до 5 имеют значения 1,0, 1,0, 1, 1 соответственно (у страницы О бит R равен 1, у страницы 1 - R = О, у страницы 2 - R = 1 и т. д.). Другими словами, между тиком О и тиком 1 произошло обращение к страницам О, 2, 4 и 5, их биты R приняли значение 1, остальные сохранили значение 0. После того как шесть соответствующих счетчиков сдвинулись на разряд и бит R занял крайнюю слева позицию, счетчики получили значения, показанные на рис. 4Л5, а. Остальные четыре колонки рисунка изображают шесть счетчиков после следующих четырех тиков часов.

Рис. 4.15. Алгоритм старения программно моделирует алгоритм LRU. Здесь изображены шесть страниц после пяти тиков часов от (а) до (д)

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

Эта схема отличается от алгоритма LRU в двух случаях. Рассмотрим страницы 3 и 5 на рис. 4.15, д. Ни к одной из них не было обращений за последние

два тика, к обеим было обращение за предшествующий тик. Следуя алгоритму LRU, при удалении страницы из памяти мы должны выбрать одну из двух. Проблема в том, что мы не знаем, к какой из них позже имелось обращение в интервале времени между тиками 1 и 2. Записывая только один бит за промежуток времени, мы теряем возможность отличить более ранние от более поздних обращений в этом интервале времени. Все, что мы можем сделать, - это выгрузить страницу 3, так как к странице 5 также обращались двумя тиками раньше, а к странице 3 - нет.

Второе отличие между алгоритмами LRU и старения заключается в том, что в последнем счетчик имеет конечное число разрядов, например 8. Предположим, что каждая из двух страниц получила нулевое значение своего счетчика.

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

9 тиков назад, а к другой - 1000 тиков назад. И мы не имеем возможности увидеть это. На практике, однако, обычно достаточно 8 бит при тике системных часов около 20 мс. Если к странице не обращались в течение 160 мс, очень вероятно, что она не важна.

4.5. Разработка систем со страничной организацией памяти

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

4.5.1. Модель рабочий набор

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

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

Множество страниц, которое процесс использует в данный момент, называется рабочим набором [22]. Если рабочий набор целиком находится в памяти, процесс будет выполняться, не вызывая большого количества ошибок, до тех пор пока он не перейдет к другой фазе выполнения (то есть к следующему проходу компилятора). Если доступная память слишком мала для того, чтобы содержать полный рабочий набор, процесс инициирует много страничных прерываний и будет работать медленнее, так как выполнение инструкции занимает несколько наносекунд, а чтение страницы с диска обычно требует 10 мс. При скорости одна или две команды на 10 мс для завершения программы понадобятся века. Говорят, что программа, вызывающая страничное прерывание каждые несколько команд, пробуксовывает (thrashing) [23].

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

Поэтому многие системы со страничной организацией пытаются отслеживать рабочий набор каждого процесса и обеспечивают его нахождение в памяти еще до запуска процесса. Такой подход носит название модели рабочего набора [24]. Он разработан для того, чтобы значительно снизить процент страничных прерываний. Загрузка страниц перед тем, как разрешить процессу работать, также называется опережающей подкачкой страниц (prepaging). Заметьте, что рабочий набор изменяется с течением времени.

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