Алгоритмы замещения

Правило, по которому при возникновении страничного сбоя выбирается страница для удаления из ОЗУ, называется алгоритмом замещения.

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

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

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

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

(Страница137)

Эффективность эвристического алгоритма можно характеризовать отношением:

где N₀ — число страничных сбоев при решении данной задачи с применением физически нереализуемого алгоритма; — то же с применением исследуемого эвристического алгоритма.

Эвристический алгоритм можно считать выбранным удачно (для данного класса задач), если коэффициент k близок к 1. Значение N₀ может быть получено путем моделирования решения задачи (повторное) с предварительно зафиксированным потоком обращений к страницам.

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

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

Некоторые алгоритмы замещения учитывают одновременно несколько параметров прошлого потока обращений.

Алгоритм "Карабкающаяся страница" (КС-алгоритм) поддерживает последовательность номеров страниц, находящихся в ОЗУ. При любом обращении к странице ее номер в последовательности перемещается на одну позицию в направлении начала, меняясь местами с предыдущим в последовательности номером (исключение — обращение к странице, номер которой стоит в начале последовательности). При возникновении страничного сбоя из ОЗУ удаляется страница, номер которой расположен в конце последовательности, а номер вновь поступившей страницы помещается в конец последовательности. КС-алгоритм учитывает как время пребывания страницы в ОЗУ, так и интенсивность обращения к странице, причем не требует значительных аппаратных затрат, а при страничном сбое — времени на поиск.

Алгоритм "Рабочий комплект" (РК-алгоритм) более сложен в реализации, но позволяет адаптировать свои параметры под конкретный класс задач. Все страницы ОЗУ, к которым было обращение в течение отрезка времени Т, образуют т. н. рабочий комплект и не подлежат удалению из ОЗУ. Остальные страницы (не вошедшие в рабочий комплект) образуют две очереди кандидатов на замещение, причем в первую очередь попадают страницы, на которые не было записи во время пребывания их в ОЗУ. При страничном сбое удаляется страница из первой очереди (FIFO — первый пришел из рабочего комплекта — первый ушел из ОЗУ), а если первая очередь пуста, то — из второй. Из очереди страница может опять попасть в рабочий комплект, если к ней будет обращение. Для реализации РК-алгоритма каждой странице ставится в соответствие таймер на T, причем каждое обращение к странице сбрасывает таймер (и переводит страницу в рабочий комплект, если она там отсутствовала), а переполнение таймера выводит страницу из рабочего комплекта. Подбором величины T можно оптимизировать РК-алгоритм под конкретный класс задач.