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

«Не использовавшаяся в последнее время страница»

Для каждой страницы поддерживаются 2 статусных бита. Бит R (Referenced) – бит обращения. Бит устанавливается всякий раз, когда происходит обращение к странице (чтение или запись). Бит M (Modified) – бит изменения. Этот бит устанавливается, когда страница записывается, т.е. изменяется. Когда процесс запускается, дескрипторы соответствующих страниц содержат запись о том, что страница отсутствует в памяти (бит присутствия 0). При обращении к странице устанавливается бит R. Далее периодически (например, при каждом прерывании по таймеру) бит R очищается для того, чтобы отличить страницы, к которым давно не происходило обращение. Бит M при этом не очищается, т.к. необходимо знать, перезаписывать страницу на диске или нет. При возникновении страничного прерывания ОС (обработчик страничного прерывания) проверяет все страницы и для удаления выбирает с помощью случайного поиска (обычно выбирается страница с наименьшим номером) такую, к которой, во-первых, не было обращения, по крайней мере, в течение одного тика системных часов, и, во-вторых, которая была изменена. R=0 M=0 R=0 M=1 R=1 M=0 R=1 M=1

Алгоритм «FIFO – первый пришел, первый вышел»

Сравнение с магазином: для размещения на полной витрине нового товара необходимо избавиться от старого. ОС поддерживает список всех страниц, находящихся в данный момент в ОП. ЗАМЕЧАНИЕ. Независимо от таблицы дескрипторов страниц поддерживается дополнительная таблица (в виде списка), в которой хранится информация о страницах. В этом списке первая страница является старейшей. При страничном прерывании из памяти выгружается страница, которая находится в начале списка. Новая страница, соответственно, добавляется в конец списка. Данный алгоритм очень редко используется, так как не является эффективным (старый не означает ненужный, следовательно, могут быть выгружены «полезные» страницы).

 

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

Является по сути усовершенствованием предыдущего. ОС поддерживает все тот же список страниц, и первой в списке является наистарейшая страница. Согласно алгоритму для выгрузки из ОП ищется в списке самая старая страница. Но в отличие от предыдущего алгоритма, выбирается та страница, к которой не было обращений в предыдущем временном интервале. Алгоритм работает следующим образом. У первой страницы проверяется бит R. Если R=0, тогда страница немедленно заменяется новой (самая старая, да еще и не было обращений). Если R=1, то R:= 0, а страница переносится в конец списка (если хранится время обращения, то время обновляется). Так проверяются все страницы списка. Если окажется, что у всех страниц первоначально R=1, то из памяти выгрузится самая первая страница, т.к. ее бит R теперь будет равен 0. Алгоритм также не является эффективным, так как страницы перемещаются по списку (время, память).

 

Алгоритм «Час»

Страницы хранятся в виде кольцевого списка. Указатель (сравнение: стрелка часов) в списке указывает на старейшую страницу. При страничном прерывании проверяется страница, на которую указывает указатель, если бит R=0, то страница выгружается, а на ее место записывается новая. Указатель при этом перемещается к следующей странице. Если R=1, то R:=0, и указатель перемещается к следующей странице. Алгоритм используется на практике.

 

Алгоритм “WS Clock”

В исходном положении кольцевой список пуст По мере загрузки страниц в память формируется кольцевой список. Каждая запись в этом списке (дескриптор страницы) содержит бит R, бит M и поле, которое называется «время последнего использования». Указатель указывает на самую старую страницу. Кроме того, задается время t (тау). Далее, аналогично алгоритму «Часы», при каждом страничном прерывании проверяется страница, на которую указывает указатель: если R=1 (страница используется), R обнуляется, указатель перемещается на следующую страницу; если R=0, вычисляется «возраст страницы» «возраст страницы» = «текущее время» минус «время последнего использования»). Далее «возраст страницы» сравнивается со временем .t Если возраст больше t , то данная страница замещается. Кроме того, конечно же, осуществляется проверка бита М: если бит М установлен в выбранной странице (т.е. ее надо перезаписывать, а это длинная операция), то осуществляется переход на следующую страницу. Если нет ни одной страницы, у которой бит М=0, то осуществляется операция перезаписи. Данный алгоритм широко используется на практике (прост в реализации, хорошая производительность).

22. Алгоритм «Часы»

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

 

23. Понятие «рабочий набор»

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

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

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

Рабочий набор - множество страниц (к), которое процесс использовал до момента времени (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, то эта страница входит в рабочий набор