Алгоритм распределения страничных рамок

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

FIFO (first in first out). Наиболее простым алгоритмом замещения страниц является алгоритм FIFO. Этот алгоритм ассоциирует с каждой страницей время, когда эта страница была помещена в память. Для замещения выбирается наиболее старая страница.

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

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

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

Алгоритм LRU (least recently used). Алгоритм выбирает для замещения ту страницу, на которую не было ссылки на протяжении наиболее длинного периода времени. Он ассоциирует с каждой страницей время последнего использования этой страницы. Для замещения выбирается та страница, которая дольше всех не использовалась. Обычно применяются два подхода при внедрении этого алгоритма:

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

- подход на основе стека номеров страниц – стек номеров страниц хранит номера страниц, упорядоченных в соответствии с историей их использования, на «вершине» стека располагается только что использованная страница, а на «дне» дольше всех не используемая страница. Как только осуществляется ссылка на страницу, она перемещается на вершину стека, а номера всех страниц сдвигаются вниз.

Сегментная организация памяти.

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

1. Исходный текст, сохраненный для печати листинга (в пакетных системах).

2. Символьная таблица с именами и атрибутами переменных.

3. Таблица со всеми используемыми константами: целыми и с плавающей точкой.

4. Дерево грамматического разбора с результатами синтаксического анализа программы.

5. Стек, используемый для процедурных вызовов внутри компилятора.

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

Простое и предельно обобщенное решение заключается в том, чтобы обеспечить машину множеством полностью независимых адресных пространств, называемых сегментами. Каждый сегмент содержит линейную последовательность адресов от 0 до некоторого максимума. Длина каждого сегмента может быть любой от нуля до разрешенного максимума. Различные сегменты могут быть различной длины. Более того, длины сегментов могут меняться во время выполнения программы. Длина сегмента стека может увеличиваться всякий раз, когда что-либо помещается в стек, и уменьшаться при выборке данных из стека.

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

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