Вытеснение по давности использования (LRU)

Удаляется страница, к которой самое продолжительное время не было обращений (не было обращений в недавнем прошлом, не будет и в будущем).

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

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

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

LRU – наиболее распространенная стратегия вытеснения страниц.

Вытеснение редко используемых страниц (LFU)

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

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

Оптимальный алгоритм (OPT)

Алгоритм строится по следующему принципу: замещается та страница, которая наиболее долго не потребуется. Алгоритм предложен Биледи в 1966 г. Его оптимальность доказана Меттсоном в 1970 г. При использовании этого алгоритма отношение числа страничных отказов к числу ссылок минимально.

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

Аномалии в алгоритмах страничной реализации

Толкотня» в памяти

Когда замена страниц в ОП или рабочем пространстве задачи ведется чересчур интенсивно, усилившееся движение страниц может привести к опасному вырождению деятельности системы. (Более 90% времени процесса тратится на ожидание ввиду страничного отказа). Такое явление называется «толкотней» в памяти, пробуксовыванием или трэшингом (thrashing). Трэшинг характеризуется, с одной стороны, интенсивным страничным обменом, а с другой стороны, очень низкими показателями использования (utilization) и пропускной способности (throughput) центрального процессора.

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

Вообще виртуальная память дает хорошие результаты, если около 1/3 активного процесса размещается в ОП. Поэтому настоящую оперативную память заменить невозможно. Большим программам в любых системах требуется много ОП.

Рисунок 12.1 иллюстрирует зависимость полезной работы центрального процессора от степени мультизадачности в системе со страничной виртуальной памятью.

 

 

Рисунок 12.1 - Зависимость полезной работы центрального процессора от степени мультизадачности в системе со страничной виртуальной памятью

 

Точка А характеризует критический уровень мультипрограммирования, за которым начинается трэшинг.

Аномалия Биледи

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

Пример

Пусть некоторая программа состоит из пяти страниц (с номерами от 0 до 4). Для вытеснения страниц используется стратегия FIFO. Программа обращается к страницам в следующем порядке: 0-1-2-3-0-1-4-0-1-2-3-4.

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

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