6. Перечислите известные алгоритмы замещения страниц. Как соотносятся между собой алгоритм замещения "первым вошел – первым вышел" и часовой алгоритм.

Имеется ряд основных алгоритмов, используемых для выбора замещаемой страницы:

− оптимальный алгоритм;

− алгоритм дольше всех неиспользовавшегося (least recently used – LRU);

− алгоритм "первым вошел – первым вышел" (first in first out – FIFO);

− часовой алгоритм.

Алгоритм "первым вошел – первым вышел" (first in first out FIFO) рассматривает кадры

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

Часовой алгоритм использует для каждого кадра дополнительный бит – бит использования. Когда страница впервые загружается в кадр, бит использования устанавливается в 1. При последующих обращениях к странице, бит устанавливается в 1. При работе алгоритма замещения множество кадров, являющихся кандидатами на замещение, рассматривается как циклический буфер, с которым связан указатель. При замещении страницы указатель перемещается к следующему кадру в буфере. Когда наступает время замещения страницы, ОС сканирует буфер для поиска кадра, бит использования которого равен 0; если в процессе поиска встречается кадр с битом использования, равным 1, он сбрасывается в 0. Если все кадры имеют бит использования, равный 1, указатель совершает полный круг и возвращается к начальному положению, заменяя страницу в этом кадре. Часовой алгоритм, в отличие от алгоритма FIFO, распознает страницы, которые использовались чаще других, и пытается сохранить их.