The design of the UNIX Operating System 59 страница
Как оптимальный алгоритм, так и LRU не страдают от аномалии Билэди. Существует класс алгоритмов, для которых при одной и той же строке обращений множество страниц в памяти для n кадров всегда яв-ляется подмножеством страниц для n+1 кадра. Эти алгоритмы не проявляют аномалии Билэди и называ-ются стековыми (stack) алгоритмами.
Выталкивание редко используемой страницы. Алгоритм NFU
Поскольку большинство современных процессоров не предоставляют соответствующей аппаратной под-держки для реализации алгоритма LRU, хотелось бы иметь алгоритм, достаточно близкий к LRU, но не требующий специальной поддержки.
|
|
|
Программная реализация алгоритма, близкого к LRU, - алгоритм NFU(Not Frequently Used).
Для него требуются программные счетчики , по одному на каждую страницу, которые сначала равны ну-лю. При каждом прерывании по времени (а не после каждой инструкции) операционная система скани - рует все страницы в памяти и у каждой страницы с установленным флагом обращения увеличивает на единицу значение счетчика, а флаг обращения сбрасывает.
|
|
|
Таким образом, кандидатом на освобождение оказывается страница с наименьшим значением счетчика, как страница, к которой реже всего обращались. Главный недостаток алгоритма NFU состоит в том, что
|
|
|
| Основы операционных систем | 93 |
он ничего не забывает. Например, страница, к которой очень часто обращались в течение некоторого времени, а потом обращаться перестали, все равно не будет удалена из памяти, потому что ее счетчик со-держит большую величину. Например, в многопроходных компиляторах страницы, которые активно ис-пользовались во время первого прохода, могут надолго сохранить большие значения счетчика, мешая за-грузке полезных в дальнейшем страниц.
|
|
|
К счастью, возможна небольшая модификация алгоритма, которая позволяет ему "забывать". Достаточно, чтобы при каждом прерывании по времени содержимое счетчика сдвигалось вправо на 1 бит, а уже затем производилось бы его увеличение для страниц с установленным флагом обращения.
Другим, уже более устойчивым недостатком алгоритма является длительность процесса сканирования таблиц страниц.
Другие алгоритмы
Для полноты картины можно упомянуть еще несколько алгоритмов.
Например, алгоритм Second-Chance - модификация алгоритма FIFO, которая позволяет избежать потери часто используемых страниц с помощью анализа флага обращений (бита ссылки) для самой старой стра-ницы. Если флаг установлен, то страница, в отличие от алгоритма FIFO, не выталкивается, а ее флаг сбрасывается, и страница переносится в конец очереди. Если первоначально флаги обращений были ус-тановлены для всех страниц ( на все страницы ссылались), алгоритм Second-Chance превращается в алго-ритм FIFO. Данный алгоритм использовался в Multics и BSD Unix.
В компьютере Macintosh использован алгоритм NRU (Not Recently-Used), где страница-"жертва" выбира-ется на основе анализа битов модификации и ссылки. Интересные стратегии, основанные на буферизации страниц, реализованы в VAX/VMS и Mach.
Имеется также и много других алгоритмов замещения. Объем этого курса не позволяет рассмотреть их подробно. Подробное описание различных алгоритмов замещения можно найти в монографиях [Дейтел,1987], [Цикритис, 1977], [Таненбаум, 2002] и др.
Управление количеством страниц, выделенным процессу. Модель рабочего множества
В стратегиях замещения, рассмотренных в предыдущем разделе, прослеживается предположение о том, что количество кадров , принадлежащих процессу, нельзя увеличить. Это приводит к необходимости вы-талкивания страницы. Рассмотрим более общий подход, базирующийся на концепции рабочего множест-ва, сформулированной Деннингом [Denning, 1996].
Дата добавления: 2021-01-21; просмотров: 101; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!