60
⎩
⎨
⎧
+−
=
+
,qvS
,S
S
ttt
t
1t
tt
tt
Sqесли
Sqесли
∉
.
В первом случае обращение производится к странице, которая находится в па-
мяти верхнего уровня, и поэтому состояние этой памяти не меняется.
Во втором случае происходит обращение к странице, отсутствующей в памяти
верхнего уровня. Эта ситуация называется страничным сбоем, так как программа не
может дальше выполняться, пока нужная страница q
t
не будет переписана из памяти
нижнего уровня в память верхнего уровня, что сопряжено с потерями времени. По-
скольку в памяти верхнего уровня нет свободного места, из нее приходится удалять
некоторую страницу v
t
с тем, чтобы на ее место можно было поместить страницу q
t
.
Если во время пребывания страницы v
t
в памяти верхнего уровня в нее производи-
лась запись, эта страница при замещении должна переписываться в память нижнего
уровня. Такая процедура называется процессом замещения страниц, а правило, по
которому при возникновении страничного сбоя выбирается страница v
t
∈ S
t
для уда-
ления из памяти верхнего уровня, – алгоритмом замещения.
Для данной программы, порождающей некоторый поток обращений к памяти,
существует, по крайней мере, одна такая последовательность замещений страниц,
которая дает минимальное для этой программы число страничных сбоев – мини-
мально возможную последовательность замещений. При конструировании алгорит-
ма замещений стремятся приблизить реализуемую этим
алгоритмом последова-
тельность замещений к минимальной.
Оптимизация процесса замещений страниц упрощается, если известно, в каком
порядке в будущем будут происходить обращения к памяти или, по крайней мере,
вероятности обращений в будущем к отдельным страницам программы. Ясно, на-
пример, что в первую очередь из памяти верхнего уровня следует удалить страницу,
к которой
обращений больше не будет (вероятность обращений в будущем равна 0).
Трудность состоит в том, что, как правило, при выполнении программы отсутст-
вуют информация о потоке обращений или сколько-нибудь достоверные сведения о
вероятности обращений к отдельным страницам в будущие моменты времени.
Алгоритмы замещения можно разделить на две группы:
• физически нереализуемые,
использующие информацию (реально отсутст-
вующую) о потоке обращений в будущие моменты времени;
• физически реализуемые или эвристические, использующие только информа-
цию об обращениях к памяти в прошедшие моменты времени, т.е. только ис-
торию процесса.
Хотя алгоритмы первой группы на практике применить нельзя, они играют важ-
ную роль в теории алгоритмов
замещения, позволяя производить оценки (в том чис-
ле экспериментальные), в какой степени характеристики эвристических алгоритмов
приближаются к предельно возможным оптимальным.
Физически нереализуемые алгоритмы
Алгоритм Михновского-Шора. При каждом замещении страницы из памяти
верхнего уровня отсылается в память нижнего уровня страница, очередное обраще-
ние к которой произойдет позже, чем к любой другой странице в памяти верхнего
уровня.
Справедливо следующее предложение. Число замещений страниц в памяти
верхнего уровня (число страничных сбоев) при выполнении замещений по алгоритму
Михновского-Шора
является минимальным для заданных потока обращений и ис-
ходного распределения памяти, что имеет теоретическое доказательство.
Таким образом, алгоритм Михновского-Шора реализует минимально возможную
для данной программы последовательность замещений, поэтому этот алгоритм на-
зывают МИН-алгоритмом.