Стратегии замещения страниц

Организация виртуальной памяти.

Оверлейная организация памяти достигается на стадии разработки прикладных программ за счет разбиения кода надинамически подгружаемые модули оверлей, размер которых расположен таким образом чтобы обновременно существующее ядро ОС, загрузчик оверлея и минимум 1 оверлей (*.ove). При этом подходе програмист сам задавал порядок загрузки и выгрузки оверлеев.

Повешенные требования к квалификации програмиста использующего механизм оверлеев и потенциальные ошибки потребовали другой подход при котором загрузка-выгрузка фрагментов кода осуществляет ОС.

Была предложена виртуальная память основаная на страничной организации. Страницы – это участки кода одинаковой размерности (4 кб и более). Когда при выполнении программы требуется вызов страницы которая расположена на диске возникает страничное прерывание, одна из страниц в оперативной памяти выгружается страница, а на ее место выгружается новая страница. Страницы запущенные в процессы, которые находятся на димске размещаются в файле подкачки. Поскольку все страницы имеют одинаковый размер в среднем на каждый процесс теряется обьем памяти равный половинному обьему памяти страницы. Это называется внутренней фрагментацией.

W(H, t) = W(k)

W(k) = A(1-)

W(k) = A (1- e)

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

Существует также подход 2-х и более уровневые, когда при больших объемах памяти часть таблиц страниц размещается в отдельных страницах и может быть выгружено в файл подкачки.

1. Оптимальное замещение страниц действует следующим образом:

Во время страничного прерывания в памяти находятся рабочее множество страниц к одной из страниц обращается следующая команда процесса на другие страницы не будет ссылок в течении следующих 10-100 тыс. команд. Каждая страница помечена количеством команд которые будут выполнятся перед обращением к ней. Оптимальный алгоритм сообщает что должна быть выгружена страница с наибольшей меткой, при этом на возможно максимальный срок удаляются страничные прерывания которые выгружают страницу назад.

Недостаток: невыполнимость.

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

2. NRU – выгружаются неиспользуемые время страницы. Каждая страница при этом снабжена 2-мя битами (R и M). Бит R – при каждом обращении к странице, бит M – при записи. При возникновении страничного прерывания ОС обращается к биту R и M и выделяет 4 класса по комбинациям:

00 – не было обращений изменений.

01 – не было обращений но страница изменена.

10 – страница не изменена.

11 – и обращение и изменение.

Бит R ставится по системному таймеру. Бит M – только при выгрузке страницы. Загруженная страница имеет R и M нулевые.

Согласно этим классам прежде всего замещается страница класса 0, затем класса 1. В последнюю очередь класса 3. В некоторых системах класс 2 выгружается раньше, чем класс 1 т.к. выгрузка 1-го класса предполагает запись на диск выигрыш по времени.

Достоинства алгоритма: легок для реализации и достаточно надежен.

Алгоритм FIFO (*)

Алгоритм «2-я попытка»

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

Недостаток: громосткость, страницы приходится перезаписывать из памяти в память.

Один из вариантов 2-й попытки является использование признака R – признак обращения.

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

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

Отличительная черта в том, что страницы в памяти не перемещаются, а просто изменяется указатель менеджера памяти. Если оперативная память имеет 1 уровень, то лучше использовать алгоритм «часы», а если 2 уровня (имеется кэш) то лучше алгоритм «вторая попытка».

LRU Least – страница не использующаяся дольше всех. Данный алгоритм приближен к оптимальному алгоритму, дает наиболее быструю работу, однако сложен в реализации. Простейший вариант алгоритма LRU это поддержка списка страниц в начале, которого стоит страница, к которой в последнее время было обращение, а в конец выносится страница, к которой дольше всех не было обращения. Она наиболее вероятный кандидат на замену. Список должен обновляться при каждом обращении к памяти, при этом каждая страница оснащена счетчиком обращения, из которой сбрасывается тот к чьей странице было обращение. Данный вариант достаточно громоздок, его попытались ускорить за счет аппаратных средств, так в одном из способов был использован программный счетчик на 64 разряда. Его значение копировалось в ту страницу, к которой произошло обращение, в случае возникновения прерывания анализируется все записанные показатели счетчиков и для замены выбирается на страницу обращение к которой больше всех.

2-й вариант алгоритма LRU предусматривает поддержание битовой матрицы размерностью nxn где n – количество страниц в системе, изначально n=0. Каждый раз при доступе к к-той странице присваивается всем битам к-значения 1, а затем обнуляются все биты столбца - к. В любой момент времени самой старшей является страница с наименьшим двоичным значением.

(2) 0 1 2 3

(1) 0 1 2 3

	(4) 0 1 2 3

(3) 0 1 2 3

1. Обращение к странице «0»

2. Обращение к странице «1»

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

Достоинства: с привлечением аппаратных средств дает наибольшую производительность.

Алгоритм NFU (редко используемая страница)

Это разновидность программной реализации алгоритма RLU. Этот алгоритм предполагает программный счетчик в каждой странице памяти. Также страница памяти снабжена битом обращения R. Во время каждого прерывания по таймеру значение бита R прибавляется к счетчику патом сбрасуется. Когда возникает страница прерывания, выбирается замена страницы с наименьшим значением счетчика.

Недостатки: нет ослабления памяти. С этим связаны эффекты переполнения счетчика, а так же явным нарушением оптимальности. Т. е. Страницы, которые в начале программы обращались достаточно часто, долго будут сохранять значение счетчика, хотя фактически они не используются, вместо этого планировщик будет удалять используемые страницы, поэтому вместо NFU используется «NFU со старением».

Согласно этого алгоритма старение происходит не только прибавлением R к странице, но и арифметическим сдвигом.

R
	1 0 0 0. 0 0 0 0
	0 0 0 0. 0 0 0 0
	1 0 0 0. 0 0 0 0
	0 0 0 0. 0 0 0 0
	1 0 0 0. 0 0 0 0
	1 0 0 0. 0 0 0 0

В исходном положении счетчика 6-ть страниц равны 0. При возникновении прерывания от таймера все значения счетчиков страниц были сдвинуты в право на единицу и к старшим разрядам этих счетчиков бит 2.

R
	1 1 0 0. 0 0 0 0
	0 0 0 0. 0 0 0 0
	0 1 0 0. 0 0 0 0
	0 0 0 0. 0 0 0 0
	0 1 0 0. 0 0 0 0
	1 1 0 0. 0 0 0 0

Достоинство: ослабление памяти.

Дата добавления: 2013-12-12