Глава 4 (Методическое пособие по Операционным системам), страница 9

Последние два алгоритма используют рабочий набор. Алгоритм «рабочий на­бор» обладает приемлемой производительностью, но дорог в реализации. Алго­ритм WSClock — это вариант, который не только дает достойную производитель­ность, но его также достаточно просто реализовать.

В итоге двумя наилучшими алгоритмами являются «старение» и WSClock. Они основаны на алгоритме LRU и понятии рабочего набора соответственно. Оба обес­печивают хорошую постраничную подкачку и могут быть реализованы за разумную цену. Существует еще несколько алгоритмов, но для практических целей эти два являются, вероятно, наиболее важными.

Моделирование алгоритмов замещения страниц

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

Аномалия Билэди

И
нтуитивно может показаться, что чем больше страничных блоков имеет память, тем меньше будет происходить страничных прерываний. Достаточно удивителен тот факт, что это не всегда так. Билэди (Belady) и другие исследователи в своей работе [23] описали обнаруженный ими контрпример, в котором алгоритм FIFO вызывал больше страничных прерываний при четырех страничных блоках, чем при трех. Эта странная ситуация стала известна как аномалия Билэди. Она проиллюст­рирована на рис. 4.22 для программы с пятью виртуальными страницами, пронуме­рованными от 0 до 4. Буквы «Р» показывают, какие обращения вызывают странич­ные прерывания. Обращения к страницам происходят в следующем порядке:

012301401234

На рис. 4.22, а показано, как при наличии трех страничных блоков вызывается в целом девять страничных прерываний. На рис. 4.22,5 изображены десять странич­ных прерываний при работе с четырьмя страничными блоками.

Магазинные алгоритмы

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

Вся работа началась с наблюдения, что каждый процесс с момента запуска фор­мирует последовательность обращений к памяти. Любая ссылка к памяти соответ­ствует определенной виртуальной странице. Таким образом, концептуально дос­туп процесса к памяти можно описать (упорядоченным) списком номеров страниц. Этот список называется последовательностью или строкой обращений (reference string) и играет главную роль во всей теории. Для простоты далее мы будем рассмат­ривать вариант машины с одним процессом, то есть когда каждая машина имеет единственную определенную последовательность обращений (при нескольких процессах мы должны были бы принять во внимание чередование их строк обра­щений вследствие многозадачности).

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

1. Последовательность обращений для выполняемого процесса.

2. Алгоритм замещения страниц.

3. Количество доступных в памяти страничных блоков т.

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

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

Чтобы прояснить функционирование интерпретатора, рассмотрим конкретный пример, использующий алгоритм замещения страниц LRU. Виртуальное адресное пространство имеет восемь страниц, а в физической памяти есть четыре странич­ных блока. Сверху на рис. 4.23 изображена последовательность обращений, состо­ящая из 24 страниц:

021354637473355311171341

Ниже последовательности обращений расположена таблица из 25 столбцов и 8 строк. Первый столбец не заполнен, так как он отражает состояние массива М до запуска процесса. Каждый следующий столбец демонстрирует массив М по­сле того, как одна из страниц была извлечена обращением к ней и обработана алго­ритмом подкачки страниц. Жирный контур отделяет верхнюю часть массива М, то есть первые четыре элемента, соответствующие страничным блокам в памяти. Страницы внутри жирной рамки находятся в памяти, страницы, расположенные ниже, были выгружены на диск.

Первой в последовательности обращений является страница 0, поэтому она по­мещается на самый верх памяти, как показано во втором столбце. Следующая стра­ница под номером 2 попадает в верхнюю ячейку третьего столбца. Это действие сдвигает вниз страницу 0. В данном примере заново загружаемая страница всегда занимает верхнюю ячейку, а все остальное по необходимости сдвигается вниз.

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

Второе обращение к странице 3 не вызывает страничного прерывания, потому что она уже находится в памяти. Тем не менее интерпретатор убирает ее с того места, где она располагалась, и помещает в верхнюю ячейку столбца, как показано на рисунке. Процесс продолжает работу некоторое время, до тех пор, пока не происходит обращение к странице 5. Эта страница переносится из нижней части массива Мв верхнюю (то есть она загружается в память с диска). Всякий раз, когда страница, к которой обращается процесс, не находится внутри рамки, очерченной жирной линией, происходит страничное прерывание, что отмечено буквами «П» в строке под таблицей.

Свойства этой модели:

1. При обращении к странице, она перемещается в верхнюю часть массива М.

2. Если страница находится в массиве, то все остальные в массиве сдвигаются на позицию вниз.

3. Страницы ниже объекта обращения не перемещаются.

Этот алгоритм, как и мрогие другие, в частности LRU, обладают следующим свойством:

M (m,r ) с M (m+1,r),

Где m-кол-во страничных блоков, r –индекс в последовательности обращений. Алгоритмы, удовлетворяющие условию М, называются магазинными, Они не подвержены аномалии Билэди.