Алгоритм WSClock как аппроксимация

Question

У меня есть вопрос относительно алгоритма WSClock, используемого для замены страниц в операционных системах.

Насколько я понимаю, WSClock сочетает в себе черты как рабочий набора (страница находится в WS, если он ссылается в последних интервалах T времени, поэтому последний отсчет время сохраняется в памяти для каждой страницы с R & М бит) и алгоритм «Часы» (таблица фреймов страниц хранится в виде кругового списка, когда происходит ошибка страницы, при переходе списка происходит поиск страниц, отсутствующих в рабочем наборе).

На каждой странице ссылки HW устанавливает свой R бит в 1. На некоторых временных интервалах ОС сбрасывает R биты для всех страниц в 0.

При возникновении неисправности страницы алгоритм проходит по списку и делает Ниже для каждой страницы:

1) If R == 1 : set R = 0, set t = process_t, go further 
2) Else if R == 0 and (t - process_t) <= T, go further 
3) Else if R == 0 and (t - process_t) > T 
     1) If M = 1 - set page for writing to disk, go further 
     2) If M = 0 - this is our victim, evict 

If there are no pages for immediate evict are found - traverse until a disk write for any marked page is finished, then evict. 
If there are no pages scheduled for a disk write - take the one which was referenced to the most time ago. 

алгоритм выглядит просто отлично для меня, за исключением одного:

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

Так что для действительно очень часто используемых страниц, которые, без сомнения, присутствуют в WS процесса, все хорошо: их опорная частота выше частоты события сброса ОС.

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

Итак, из того, что я вижу, похоже, что ОС принимает моментальные снимки рабочего набора только во время событий сбоев страницы. Эти снимки представляют собой рабочий набор страниц, на которые ссылаются интервалы времени между сбросом бит R и ошибками страницы.

Почему это хорошее приближение к реальному набору работ?

Является ли качество приближения (и, следовательно, эффективность алгоритма), определяемым значением временного интервала, когда R бит сбрасываются?

Значит, это значение не должно быть слишком низким, чтобы улавливать большинство этих неудачных страниц, о которых я упомянул выше, но также не слишком большой, чтобы не ловить страницы, которые на самом деле уже не находятся в рабочем наборе?

Answer 1

На самом деле это объяснение: В этом алгоритме используется приближение рабочего набора.

В этом приближении хранится некоторая часть реального фактического рабочего набора процесса. Также он может не хранить некоторую часть этого фактического рабочего набора.

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

Также стоит упомянуть, что параметры могут динамически регулироваться ОС во время работы компьютера, чтобы алгоритм оставался достаточно близким для фактического рабочего набора.