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

В настоящее время реализованы следующие алгоритмы:

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

Эффективность всех алгоритмов замещения страниц оценивается по числу их перемещения на ВЗУ. В этом алгоритме такое количество перемещений можно оценить формально. Количество замещений страниц в этом алгоритме определяется как количество требуемых страниц минус количество страниц в буфере кадров. Если содержимое перемещаемой на ВЗУ страницы не изменилось, то необходимость реализации этого процесса отсутствует, поскольку на ВЗУ находится ее точная копия, в этом случае страница просто перезаписывается без перемещения на ВЗУ. Это в определенной степени повышает эффективность работы алгоритма FIFO. Такая модификация FIFO называется SC. Для реализации SC в информативные биты дискриптора страницы в большинстве ВС добавляется бит М (D). Устанавливается в 1 после изменения ее содержимого.

2. NFU/LRU. Полностью аналогичны таким же алгоритмам для сегментного типа ВП. Реализовано в Windows

3. Часовые алгоритмы. Существует два таких алгоритма: с одной стрелкой и двумя стрелками. Эти алгоритмы реализованы в ОС Linux. Все страницы, к которым обращается процесс представляются в виде кольцевого буфера (циферблата) по которому перемещается указатель (стрелка). Основное назначение этого указателя - это сброс бита обращения А. В случае необходимости замещения страницы, замещению подлежит та, на которую указывает указатель и для которой А изначально равен 0. Иными словами, замещается страница, не востребованная за время оборота.

Часовые алгоритмы с двумя стрелками. В этом алгоритме функции одной стрелки разделены между двумя. Первая стрелка сбрасывает биты обращения в 0, вторая стрелка определяет кандидатов на замещение.

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

4. WS (рабочего набора). Реализован в Unix подобных ОС. С каждой из страниц ассоциируется время ее последнего использования (некоторая переменная, сохраняющая системное время обращения к этой странице), кроме того с каждой из страниц ассоциируется ее "возраст", если " возраст" страницы не превышает какого то заданного значения, то считается, что эта страница используется процессом. В противном случае, она является кандидатом на замещение. При относительно малых интервалах времени алгоритм является достаточно эффективным.

08.10.2014

5. Часовой WS. Реализован в ОС Linux. Представляет собой логичпскую совокупность часового алгоритма и алгоритма рабочего набора. В этом алгоритме замещению подлежит страница, для которой бит А изначально равен 0 што есть, за время оборота стрелки к этой странице не было реализовано обращение) и которая уже не подлежит рабочему набору. То есть ее возрас превышает некоторую заданную величину.

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

 

КЭШ - память

Предназначена для сокращения времени обращения к страницам. В современных системах существует кэш-память первого уровня и второго. КЭШ-память первого уровня сохраняет дискрипторы используемых страниц. Кэш-память второго уровня сохраняет внутристраничную информацию. Кэш-память находится на кристале процессора, является сверхоперативной памятью с ассоциативным поиском. Структура кэш память первого уровня выглядит следующим образом:

 

Состоит из памяти признаков и памяти данных. Память данных сохраняет дискрипторы использовавшихся страниц. Память признаков сохраняет признаки дискрипторов страниц. Признаком является старшие разряды ЛА. Поле с номером набора определяет набор памяти признаков, с которым осуществляется взаимодействие. Взаимодействие осуществляется в ассоциативном поиске. В случае равенства признака содержимому какой то из записей набора ПП, фиксируется случай кэш-попадания. В этом случае из соответствующего набора памяти данных считывается дикриптор страницы, из него выделяется БА, и к нему прибывляется внутристраничное смещение, образуя тем самым физический адрес. В случае кэш-промаха реализуются относительно длительные этапы индексирования страничных таблиц. Дискриптор страницы считывается только в том случае, если его содержимое является достоверным, в этом случае содержимое бита корректности равен (v0-v3) 1. Разряды занятости (b0-b2) позволяют выбрать запись памяти данных, в которою будет записан дискриптор новой страницы.