§4.3. Класс многоуровневых алгоритмов замещения.

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

Наиболее простой по реализации алгоритм РПРУ эффективен только в части быстрого обновления ОП, он не выделяет в списке B_t страницы рабочего тела, обращения к которым происходит чаще, чем к остальным страницам. Алгоритм НДИ также позволяет быстро обновить содержимое ОП. В отличие от РПРУ он изменяет список B_t при обращении к страницам, находящимся в ОП, и при определенных условиях позволяет сохранить в ОП страницы рабочего тела. Однако при НДИ последовательность одиночных обращений достаточной длины к страницам, находящимся в ВП, вытеснит из ОП все страницы рабочего тела. Поскольку только что введенная в ОП страница ставится на первую позицию в списке B_t НДИ, то даже несколько одноразовых обращений к страницам из ВП может привести к вытеснению такого же числа страниц рабочего тела. Аналогичным недостатком обладает алгоритм РК (Рабочий Комплект).

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

Пусть упорядоченный список страниц, определяющий состояние ОП в момент t имеет вид , гдеm_t - объем ОП, отводимый программе в момент t. Для определения алгоритма замещения необходимо указать правила преобразования B_t в B_t+1. Многоуровневый алгоритм замещения из класса в общем случае определяет позицию страницыx_t+1 в списке B_t+1 с помощью h приоритетных подмножеств (списков) M₁,M₂,…,M_h, которые не пересекаются и .

Если страница x_t+1 отсутствует в ОП, то ей (при вводе в ОП) ставится в соответствие первая позиция в списке M_h, если же страница x_t+1 находилась в ОП и имела позицию в подмножестве , то этой странице ставится в соответствие первая позиция в списке более высокого приоритетаM_i-1. Подмножества M₁,M₂,…,M_h задают в общем случае несколько уровней позиций страниц в списках B_t, определяющих состояние ОП. Отсюда и название алгоритмов – многоуровневые.

Для включения в класс алгоритмов замещения типа алгоритма РК вводятся параметрыT_i, i=1,2,…,h, определяющие максимально допустимое время хранения (в пределах активности процесса) страницы в ОП без обращения к ней при условии, что ее позиция содержится в списке М_i , i=1,2,…,h, и параметры , определяющие максимальное число элементов в множествахM_i.

Пусть заданы правила образования подмножества и пустьB_t= (M₁,M₂,…,M_h) – состояние ОП в момент t. Если в момент t+1 произошло обращение к странице x_t+1, то новое состояние ОП при алгоритме определяется посредством следующих шагов:

Шаг 1. Из каждого множества удаляются те страницы, к которым не происходили обращения в течение времени большегоT_r от момента обращения к x_t+1.

Шаг 2. Оставшиеся элементы M_r в множествах перенумеровываются таким образом, чтобы получившееся после первого шага 1 состояние ОП B_t^' имело вид:

B_t^'= (M₁^',M₂^',…,M_h^'),

где M_r^', r=1,2,…,h приведено к виду:

M_r^'= (i_r1,i_r2,…,i_rm),

причем некоторое множество M_r^' может быть пустым.

Шаг 3. Новое состояние ОП B^'_t+1 отличается от B^'_t :

• Только множеством M_h^', если (случай 1);

• Только множеством M_r^', еслии, причем(случай 2);

• Только множествами M_r-1^' и M_r^', , если,(случай 3).

Обозначим через время, прошедшее с момента последнего обращения к странице,и зададимh целых чисел l₁,l₂,…,l_h и h чисел , где, смысл которых разъясняется ниже. Тогда, если имеет место случай 1, тоM_h^' преобразуется в:

Если имеет место случай 2, то M_r^' преобразуется в:

Если имеет место случай 3, то M_r-1^' преобразуется в

а M_r^' преобразуется в:

Класс χ содержит целый ряд алгоритмов замещения, представляющих теоретический и практический интерес. При h=1 и имеет место модифицированный алгоритм РК, который припревращается в алгоритм РК. Параметрпозволяет ограничить объем ОП, отводимый программе. Чем меньше, тем меньше страниц ОП будет занимать программа в худшем случае, когда к каждой из своих страниц она обращается по 1 разу. Аналогично, в общем случае, выбирая параметрможно регулировать размеры списковM_i, не давая им чрезмерно увеличиться.

Полагая иполучаем классалгоритмов замещения, определяемыхh+1 параметром: и, т.е.. Приh=1 и l=m, где имеем алгоритм РПРУ, а приh=l=1 имеем алгоритм НДИ. Алгоритмы 1<l<m являются промежуточными между РПРУ и НДИ и отчасти похоже на известный алгоритм «раньше пришла, если не использовалась, то раньше ушла». Если позиции списка B_t пронумерованы как обычно, слева направо, то при алгоритме до тех пор, пока странице соответствует позиция спискаее изменение происходит так же, как при РПРУ, а притак же как при НДИ. Параметрывходящие в определение алгоритмовинтерпретируются аналогично внутри каждого из множеств,. Рассмотрим случай. Тогда параметрможет принимать единственное значение. При алгоритместранице, только что введенной в ОП соответствуют позицияв спискеB_t. Если до следующего страничного сбоя к этой странице не произойдет ни одного обращения, то она будет замещена. При обращении к странице, находящейся в ОП, ее позиция изменяется на, а страницабудет поставлена на позицию. Перемещение с позициина позицию 1можно уподобить подъему наверх по лестнице изступеней. Отсюда название алгоритма – ЛЕСТН (лестничный). Припозиции спискаB_t разбиваются на h приоритет множеств (M₁,M₂,…,M_h). Странице, только что введенной в ОП, ставится в соответствие первая позиция в множестве младшего приоритета M_h. При каждом новом обращении к этой странице ее позиция будет последовательно перемещаться на 1-е место в множестве все более высокого приоритета.

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