§4.4. Модели поведения программ и критерии качества.

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

Простейшая стохастическая модель (независимая модель) описывает обращения x₁,x₂,… последовательностью независимых (одинаково распределенных) случайных величин:

Непосредственным обобщением такой независимой модели является марковская модель, которая описывает обращения x₁,x₂,… однородной эргодической цепью Маркова , заданной на множестве состоянийматрицей переходных вероятностей:

, где

Выделим частную марковскую модель со специальной переходной матрицей с элементами:

Где

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

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

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

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

Модель восстановления задана, если:

а) имеется функций распределения, описывающихнезависимых случайных величин исуществует.

б) интервалы между соседними обращениями к странице независимы и подчиняются распределению.

в) выполняется условие нормировки: .

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

Критерии качества.

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

Определим для любого - элементного подмножествахарактеристическую функцию его дополнения:

Для детерминированной модели критерий качества определяет количество обращений к ВП при применении алгоритма замещения на последовательности обращенийдлины:

Для всех рассмотренных выше стохастических моделей критерий качества зададим в виде:

Такой критерий качества определяет среднюю стационарную частоту обращений к ВП или, иначе говоря, среднюю частоту страничных сбоев.

Адекватность модели.

Для любой стохастической модели поведения программ возникает вопрос,

насколько хорошо, она описывает трассы обращений реальных программ, т.е. вопрос об адекватности модели. Вводится понятие адекватности в сильном, широком и слабом смысле.

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

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

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

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

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

Модель адекватна в слабом смысле, если она отражает указанные три свойства: рабочего тела, локальности и редких обращений.

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

С точки зрения сравнения алгоритмов, можно показать, что:

При этом:

;

Таким образом, алгоритм замещения ЛЕСТН является оптимальным алгоритмом в классе для модели независимых обращений.