80. Стратегии управления страничной памятью

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

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

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

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

Глобальные алгоритмы имеют несколько недостатков. Во-первых, они делают одни процессы чувствительными к поведению других процессов.

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

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

Аномалия Belady

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

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

83. Оптимальный алгоритм

Одно из последствий открытия аномалии Belady - поиск оптимального алгоритма.  Этот алгоритм имеет минимальную частоту fault'ов среди всех алгоритмов. Он прост:

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

Каждая страница помечается числом инструкций, которые будут выполнены, прежде чем на эту страницу будет сделана первая ссылка.

Этот алгоритм нереализуем. ОС не знает,  к какой странице будет следующее обращение.  (Ранее такие проблемы были с планированием процессов -  алгоритм SJF).  Для второго обращения уже можно делать прогноз на основе информации собранной после первого обращения.

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