Алгоритмы замещения страниц

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

Алгоритм 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)

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

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

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

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

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

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

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

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

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

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

В таблице страниц добавляется запись - счетчик обращений к странице. Чем меньше значение счетчика, тем реже она использовалась. Алгоритм "рабочий набор" Замещение страниц по запросу - когда страницы загружаются по требованию, а не заранее, т.е. процесс прерывается и ждет загрузки страницы. Буксование - когда каждую следующую страницу приходится процессу загружать в память. Чтобы не происходило частых прерываний, желательно чтобы часто запрашиваемые страницы загружались заранее, а остальные подгружались по необходимости. Рабочий набор - множество страниц (к), которое процесс использовал до момента времени (t). Т.е. можно записать функцию w(k,t).

Т.е. рабочий набор выходит в насыщение, значение w(k,t) в режиме насыщения может служить для рабочего набора, который необходимо загружать до запуска процесса. Алгоритм заключается в том, чтобы определить рабочий набор, найти и выгрузить страницу, которая не входит в рабочий набор. Этот алгоритм можно реализовать, записывая, при каждом обращении к памяти, номер страницы в специальный сдвигающийся регистр, затем удалялись бы дублирующие страницы. Но это дорого. В принципе можно использовать множество страниц, к которым обращался процесс за последние t секунд. Текущее виртуальное время (Tv) - время работы процессора, которое реально использовал процесс. Время последнего использования (Told) - текущее время при R=1, т.е. все страницы проверяются на R=1, и если да то текущее время записывается в это поле. Теперь можно вычислить возраст страницы (не обновления) Tv-Told, и сравнить с t, если больше, то страница не входит в рабочий набор, и страницу можно выгружать.

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

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

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

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

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

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

Дата добавления: 2015-06-25