Организация ЭВМ и систем. Однопроцессорные ЭВМ. Часть 3



АЛГОРИТМЫ УПРАВЛЕНИЯ МНОГОУРОВНЕВОЙ ПАМЯТЬЮ - часть 3


Алгоритмы замещения можно разделить на две группы:

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

    Физически нереализуемые алгоритмы

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

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

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

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

    Физически реализуемые (эвристические) алгоритмы замещения

    Был предложен ряд алгоритмов этого класса.

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

    НДИ-алгоритм. Из памяти верхнего уровня отсылается страница, наиболее давно использовавшаяся.




    Содержание  Назад  Вперед