Алгоритм LRU (Least Recently Used - использовавшаяся реже всего)

Первый метод:

Чтобы реализовать этот алгоритм, можно поддерживать список, в котором выстраивать страницы по количеству использования. Эта реализация очень дорога.

Второй метод:

В таблице страниц добавляется запись - счетчик обращений к странице. Чем меньше значение счетчика, тем реже она использовалась.

7.1.6 Алгоритм "рабочий набор"

Замещение страниц по запросу - когда страницы загружаются по требованию, а не заранее, т.е. процесс прерывается и ждет загрузки страницы.

Буксование - когда каждую следующую страницу приходится процессу загружать в память.

Чтобы не происходило частых прерываний, желательно чтобы часто запрашиваемые страницы загружались заранее, а остальные подгружались по необходимости.

Рабочий набор - множество страниц (к), которое процесс использовал до момента времени (t). Т.е. можно записать функцию w(k,t).

Зависимость рабочего набора w(k,t) от количества запрошенных страниц

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

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

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

В принципе можно использовать множество страниц, к которым обращался процесс за последние t секунд.

Текущее виртуальное время (Tv) - время работы процессора, которое реально использовал процесс.

Время последнего использования (Told) - текущее время при R=1, т.е. все страницы проверяются на R=1, и если да то текущее время записывается в это поле.

Теперь можно вычислить возраст страницы (не обновления) Tv-Told, и сравнить с t, если больше, то страница не входит в рабочий набор, и страницу можно выгружать.

Получается три варианта:

o если R=1, то текущее время запоминается в поле время последнего использования

o если R=0 и возраст > t, то страница удаляется

o если R=0 и возраст =< t, то эта страница входит в рабочий набор

Алгоритм WSClock

Алгоритм основан на алгоритме "часы", но использует рабочий набор.

Используются битов R и M, а также время последнего использования.

Работа алгоритма WSClock

Это достаточно реальный алгоритм, который используется на практике.