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

Алгоритм FIFO (первая прибыла - первая выгружена)

Алгоритм NRU (Not Recently Used - не использовавшаяся в последнее время страница)

Используются биты обращения (R-Referenced) и изменения (M-Modified) в таблице страниц.

При обращении бит R выставляется в 1, через некоторое время ОС не переведет его в 0.

M переводится в 0, только после записи на диск.

Благодаря этим битам можно получить 4-ре класса страниц:

1. не было обращений и изменений (R=0, M=0)

2. не было обращений, было изменение (R=0, M=1)

3. было обращение, не было изменений (R=1, M=0)

4. было обращений и изменений (R=1, M=1)

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

7.1.3 Алгоритм "вторая попытка"

Подобен FIFO, но если R=1, то страница переводится в конец очереди, если R=0, то страница выгружается.

Алгоритм "вторая попытка"

В таком алгоритме часто используемая страница никогда не покинет память.

Но в этом алгоритме приходится часто перемещать страницы по списку.

7.1.4 Алгоритм "часы"

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

Алгоритм "часы"

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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