16.4. Комбинация сегментации и страничной организации

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

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

16.5. Алгоритмы управления виртуальной памятью

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

Стратегия выборки

Стратегия выборки определяет, когда страница должна быть передана в ОП. Два основных варианта – по требованию и предварительно.

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

Стратегия размещения.

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

Стратегия замещения

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

• какое количество кадров должно быть выделено каждому активному процессу;

• должно ли множество страниц, которые потенциально могут быть замещены загружаемыми страницами, ограничиваться одним процессом или в качестве кандидатов на замещение могут рассматриваться все кадры ОП;

• какие именно страницы из рассматриваемого множества следует выбрать для замещения.

Первые для вопроса относятся к управлению резидентным множеством. Ниже рассматривается третий вопрос.

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

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

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

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

Часовая стратегия является компромиссом между стратегией дольше всех неиспользовавшегося элемента (близкой к оптимальной, но сложной в реализации) и стратегией "первым вошел – первым вышел" (простой в реализации, но далекой от оптимальной).

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

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

2 3 2 1 5 2 4 5 3 2 5 2

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