Управление замещением страниц в двухуровневой памяти

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

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

1. Случайное замещение (СЗ). В этом случае с заданной на множестве страниц ОП вероятностью замещается любая страница в ОП.

2. Раньше пришла – раньше ушла (РПРУ). При этом замещается страница, которая дольше всех находилась в ОП.

3. Замещение наиболее давно использованной страницы (НДИ). В этом случае замещается страница, которая дольше всех не запрашивалась.

Среди алгоритмов замещения, рассчитанных на переменный объем ОП, выделяемый программе, наиболее известен алгоритм рабочего комплекта (РК). Согласно ему, в любой момент времени в ОП хранятся только те страницы, к которым происходили обращения на интервале (t-τ,t), где τ – фиксированный параметр. При использовании алгоритма РК, в отличие от таких алгоритмов как СЗ, РПРУ, НДИ, можно уменьшать или увеличивать объем ОП, отводимый программе, в зависимости от ее поведения. Поэтому алгоритм РК можно использовать для динамического распределения ОП. Пусть ε=(1,2…,n) – совокупность страниц данной программы. Предположим, что все n страниц постоянно хранятся в ВП и только m<n страниц могут храниться в ОП.

Поведение программы опишем последовательностью страниц х₁, х₂,..., к которым происходят обращения в процессе ее выполнения. Обозначим эту последовательность через ω = (x₁,x₂,…). Если x_t = i, то это означает, что обращение к странице i происходит в момент t. Будем говорить, что при обращении к странице, отсутствующей в ОП, происходит страничный сбой. Пусть – совокупность страниц в ОП в момент t.

Физически реализуемый алгоритм замещения А – это алгоритм, который для любого t = 1,2,… определяет множество в зависимости от наблюдаемой предыстории , и . СЗ, РПРУ, НДИ, РК – физически реализуемы.

Среди всех алгоритмов замещения выделим важный класс – алгоритм замещения по запросу.

Df. Пусть объем ОП, отведенный программе составляет m страниц. Алгоритм замещения A по запросу определяет множество по формуле:

,

где – замещающая граница.

СЗ, РПРУ, НДИ – примеры алгоритмов по запросу.

Упорядочение в любой момент t список страниц будем называть состоянием ОП. Например, если - состояние ОП в момент t-1, то для РПРУ страница - поступила раньше в ОП чем страница , страница раньше чем страница при к>l.

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

Алгоритм замещения А называется марковским с конечной памятью, если . Правило f(.) может быть детерминированным или рандомизированным. Такие алгоритмы удобны при реализации.

Алгоритмы СЗ, РПРУ, НДИ - марковские с конечной памятью. Для РПРУ, НДИ f(.) детерминирована, для СЗ – рандомизирована.

§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-е место в множестве все более высокого приоритета.

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

Дата добавления: 2014-12-26