Телекоммуникационный портал GateWay

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

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

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

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

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