Алгоритмы листания

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

В настоящее время наработано множество реализуемых алгоритмов листания. Наиболее известными из них являются алгоритмы:

· случайного замещения,

· удаления страницы, дольше других находившейся в ОП,

· удаления страницы, меньше других находившейся в ОП,

· удаления страницы из последней позиции в списке страниц, причем, при каждом обращении к странице ее место в списке перемещается на одну позицию к началу списка (алгоритм "карабкающейся страницы"),

Наиболее известными являются варианты алгоритма "рабочий комплект".

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

Вопросы для самопроверки:

1. Использование регистра базового адреса таблицы физических таблиц.

2. Вход в каталог программы.

3. Содержание и использование каталога программы.

4. Вход в раздел таблицы физических страниц.

5. Содержание и использование раздела таблицы физических страниц.

6. Поля строк и назначение TLB.

7. Процедура преобразования адресов с использованием каталога разделов и таблиц физических страниц раздела.

8. Определение страничного промаха.

9. Действия при страничном промахе.

10. Основные биты строк TLB.

11. Алгоритм листания.