2018-02-13
875
Существует большое количество разнообразных алгоритмов замещения страниц. Все они делятся на локальные и глобальные.
Локальные алгоритмы распределяют страницы для каждого процесса, а когда процесс израсходует все свои страницы, ОС будет удалять из физической памяти одну из его страниц, а не из страниц других процессов. Для локальных алгоритмов требуется хранение списка физических кадров, выделенных каждому процессу, называемого резидентным множеством процесса.
Глобальный алгоритм замещения в случае возникновения исключительной ситуации освобождает любую физическую страницу, независимо от того, какому процессу она принадлежала. Глобальные алгоритмы имеют ряд недостатков, т.к. они делают одни процессы чувствительными к поведению других процессов, т.к. некорректно работающее приложение может подорвать работу всей системы.
Если обнаруживается попытка обращения к отсутствующей странице, то в ОС генерируется сигнал отсутствия страницы (page fault), информируя ее о том, что доступ к памяти невозможен. Эффективность алгоритма оценивается на конкретной последовательности ссылок к памяти, для которой подсчитывается число возникающих page faults.
Имеется довольно много алгоритмов замещения страниц. Рассмотрим некоторые из них:
§ Алгоритм FIFO - выталкивание первой пришедшей страницы
Простейший алгоритм. Каждой странице присваивается временная метка. Для замещения выбирается старейшая страница. К сожалению, эта стратегия с будет приводить к замещению активно используемых страниц. Необходимо отметить, что при замещении активных страниц все работает корректно, но page fault происходит немедленно.
На первый взгляд кажется очевидным, что чем больше в памяти страничных кадров, тем реже будут иметь место page faults. Однако, это не всегда так. Как установил Билэди с коллегами, определенные последовательности обращений к страницам в действительности приводят к увеличению числа page faults при увеличении кадров, выделенных процессу. Это явление носит название «аномалии FIFO» или «аномалии Билэди» ( см. рисунок В2.17.1).
Рисунок В2.17.1 - Аномалия Билэди
Как видно на рисунке В2.17.1.а система с тремя страничными кадрами (9 раз имеет место page faults) оказывается более производительной, чем с четырьмя страничными кадрами (10раз имеет место page faults), для строки обращений к памяти 0 1 2 3 0 1 4 0 1 2 3 4 при выборе стратегии FIFO.
§ Оптимальный алгоритм (OPT)
Аномалия Билэди иллюстрирует сложность ОС, где интуитивный подход не всегда приемлем. Одним из последствий открытия аномалии Билэди стал поиск оптимального алгоритма, который при заданной строке обращений имел бы минимальную частоту page faults среди других алгоритмов.
Такой алгоритм был найден – необходимо замещать страницу, которая не будет использоваться в течение самого длительного периода времени. Этот алгоритм легко описать, но реализовать практически невозможно. ОС не знает, к какой странице будет следующее обращение.
§ Алгоритм LRU - выталкивание дольше всего не использовавшейся страницы
Одним из приближений к алгоритму OPT является алгоритм замещения страницы, которая не использовалась в течение самого долгого времени. Работа алгоритма проиллюстрирована на рисунке В2.17.2 Сравнивая рисунки В2.17.1 В2.17.2, можно увидеть, что использование алгоритма LRU позволяет сократить количество page faults.
Рисунок В2.17.2 - Пример работы алгоритма LRU
LRU - хороший, но труднореализуемый алгоритм. Необходимо иметь связанный список всех страниц в памяти, в начале которого будут хранится недавно использованные страницы. Причем этот список должен обновляться при каждом обращении к памяти. Много времени нужно также и на поиск страниц в таком списке.
Как оптимальный алгоритм, так и LRU не страдают от аномалии Билэди.
§ Алгоритм NFU - выталкивание редко используемой страницы
Поскольку большинство современных процессоров не предоставляют соответствующей аппаратной поддержки для реализации алгоритма LRU, хотелось бы иметь алгоритм, достаточно близкий к LRU, но не требующий специальной поддержки. Программная реализация алгоритма, близкого к LRU - алгоритм NFU(Not Frequently Used). Для него требуются программные счетчики, по одному на каждую страницу, которые сначала равны нулю. При каждом прерывании по времени ОС сканирует все страницы в памяти и у каждой страницы с установленным флагом обращения увеличивает на единицу значение счетчика, а флаг обращения сбрасывает. Т.о, освобождается страница с наименьшим значением счетчика, как страница, к которой реже всего обращались. Довольно устойчивым недостатком алгоритма является длительность процесса сканирования таблиц страниц.
§ Working Set Page Replacement - стратегия рабочего множества
В современных ОС популярен алгоритм, основанный на управлении количеством страниц, выделенным процессу - модель рабочего множества. Рассмотрим более общий подход, базирующийся на концепции рабочего множества: необходимо решить, что делать, если в распоряжении процесса имеется недостаточное число кадров, т.е. нужно ли его приостановить с освобождением всех кадров, и что следует понимать под достаточным количеством кадров.
Теоретически возможно уменьшить число кадров процесса до минимума, однако существует какое-то число активно используемых страниц, без которого процесс часто генерирует page faults.
Высокая частота генерации page faults - страничных нарушений называется thrashing, иногда употребляется русский термин «пробуксовка» (см. рисунок В2.17.3).
Рисунок В2.17.3 - Зависимость частоты page faults от количества кадров
Процесс находится в состоянии thrashing, если при его работе больше времени уходит на подкачку страниц, нежели на выполнение команд. Такого рода критическая ситуация возникает вне зависимости от конкретных алгоритмов замещения.
Результатом thrashing является резкое снижение производительности вычислительной системы. Например, при глобальном алгоритме замещения процесс, которому не хватает кадров, начинает отбирать кадры у других процессов, которые в свою очередь начинают заниматься тем же. В результате все процессы попадают в очередь запросов к устройству вторичной памяти. Загрузка процессора резко снижается. ОС реагирует на это увеличением степени мультипрограммирования, что приводит к еще большему thrashing и дальнейшему снижению загрузки процессора.
Эффект thrashing, возникающий при использовании глобальных алгоритмов, может быть ограничен за счет применения локальных алгоритмов замещения, при которых если даже один из процессов попал в thrashing, это не сказывается на других процессах. Однако он много времени проводит в очереди к устройству выгрузки, затрудняя подкачку страниц остальных процессов.
Итак, thrashing - это высокая частота страничных нарушений, которую надо контролировать. Очевидно, когда она высока, процесс нуждается в дополнительных кадрах. Можно, устанавливая желаемую частоту page faults, регулировать размер процесса, добавляя или отнимая у него кадры. Может оказаться целесообразным выгрузить процесс целиком. Освободившиеся кадры выделяются другим процессам с высокой частотой page faults.
Для предотвращения thrashing требуется выделять процессу столько кадров, сколько ему нужно, поэтому необходимо попытаться выяснить, как много кадров процесс реально использует. Для решения этой задачи и используется модель рабочего множества.
При рассмотрении поведения реальных процессов можно заметить, что процессы начинают работать, не имея в памяти необходимых страниц и в результате при выполнении первой инструкции возникает page fault, требующий подкачки нужной страницы, следующий page fault происходит при локализации глобальных переменных и еще один - при выделении памяти для стека. После того как процесс собрал большую часть необходимых ему страниц, page faults возникают редко.
Т.о., существует набор страниц, который позволяет процессу в течение некоторого периода времени производительно работать, избегая большого количества page faults. Этот набор страниц называется рабочим множеством (working set) процесса. Число страниц в нем относительно невелико.
Важное свойство рабочего множества - его размер. ОС должна выделить процессу число кадров, в которое поместилось бы его рабочее множество.
Если кадры еще остались, то может быть инициирован другой процесс. Если рабочие множества процессов не помещаются в память и начинается thrashing, то один из процессов можно выгрузить на диск.
Т.о., решение о размещении процессов в памяти должно базироваться на размере его рабочего множества.
Один из способов реализации данного подхода заключается в том, что для впервые инициируемых процессов это решение м.б принято эвристически. Во время работы процесса ОС должна уметь определять: расширяет процесс свое рабочее множество или перемещается на новое рабочее множество.
Другой способ реализации данного подхода может быть основан на отслеживании количества страничных нарушений, вызываемых процессом. Если процесс часто генерирует page faults и память не слишком заполнена, то система может увеличить число выделенных ему кадров. Если же процесс не вызывает page faults в течение некоторого времени и уровень генерации ниже какого-то порога, то число кадров процесса может быть урезано. Этот способ регулирует лишь размер множества страниц, принадлежащих процессу, и должен быть дополнен какой-либо стратегией замещения страниц. Несмотря на то что система при этом может «пробуксовывать» в моменты перехода от одного рабочего множества к другому, предлагаемое решение в состоянии обеспечить наилучшую производительность для каждого процесса, не требуя никакой дополнительной настройки системы.
Подсистема виртуальной памяти работает производительно при наличии резерва свободных страничных кадров. Алгоритмы, обеспечивающие поддержку системы в состоянии отсутствия thrashing, реализованы в составе фоновых процессов (их часто называют демонами или сервисами), которые периодически «просыпаются» и инспектируют состояние памяти. Если свободных кадров оказывается мало, они могут сменить стратегию замещения. Их задача - поддерживать систему в состоянии наилучшей производительности.
Примером такого рода процесса может быть фоновый процесс - сборщик страниц, реализующий облегченный вариант алгоритма откачки, основанный на использовании рабочего набора. Он начинает активно работать, когда количество страниц в списке свободных страниц достигает установленного нижнего порога. Но если возникает требование страницы в условиях, когда список свободных страниц пуст, то начинает работать механизм свопинга, поскольку простое отнятие страницы у любого процесса потенциально вело бы к ситуации thrashing, и разрушало бы рабочий набор некоторого процесса.
Такой демон применяется во многих клонах ОС Unix.
В ОС Windows 2000/* такую роль играет менеджер балансного набора (Working set manager), который вызывается раз в секунду или тогда, когда размер свободной памяти опускается ниже определенного предела, и отвечает за суммарную политику управления памятью и поддержку рабочих множеств.
Тестовые задания
