Сегментация в сочетании со страничной памятью

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

Логические адреса состоят из трех: [ s, p, d ]. Первая компонента – номер сегмента s. Вход в таблицу сегментов осуществляется через регистр таблицы сегментов; s -я ячейка таблицы сегментов содержит базовый адрес и длину (то есть границу) таблицы страниц для этого сегмента. Вторая компонента адреса р определяет запись в таблице страниц, которая указывает на р -юстраницу сегмента s. Затем, чтобы добраться до искомого слова, надо смещение d прибавить к базовому адресу страницы.

На такую трехкомпонентную ссылку требуется три цикла обращения к памяти; это создает недопустимо большую задержку, даже, если поиск слова по адресу выполняется с помощью аппаратного оборудования. Эту трудность можно обойти, если использовать группу ячеек памяти с быстрым доступом, называемых ассоциативными регистрами. Эти регистры сопоставляют комбинациям [ s, p ]физические места страниц. Основное свойство ассоциативных регистров — то, что их можно просматривать параллельно. По заданной ссылке [ s, p, d ]ассоциативная память порождает указатель страницы [ s, p ], если он имеется в одном из ассоциативных регистров. Таким образом, количество требуемых циклов памяти сводится к двум. Если комбинации [ s, p ]нет ни в одном ассоциативном регистре, то происходит прерывание и супервизор заменяет содержимое од­ного из ассоциативных регистров новой ссылкой [ s, p ].Наблюдения показывают, что ссылки распределяются в памяти неравномерно, концентрируясь на нескольких интенсивно используемых страницах. Поэтому для большинства адресных ссылок соответствующая комбинация [ s, p ]будет найдена в ассоциативных регистрах.

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

Контрольные вопросы

1. В чем преимущества динамического связывания по сравнению со статическим?

2. В какой момент времени виртуальный адрес преобразуется в физический?

3. Поясните разницу между внутренней и внешней фрагментацией.

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

5. Сравните сегментный и страничный способы организации виртуальной памяти. Перечислите достоинства и недостатки каждого.

6. Почему размер страницы выбирается равным степени двойки (1024, 2048 и т.д.)?

7. Укажите недостаток сегментного распределения памяти.

 

УПРАВЛЕНИЕ ВИРТУАЛЬНОЙ ПАМЯТЬЮ

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

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

Виртуальная память чаще всего реализуется на базе подкачки страниц, что удобно и при страничной и при сегментно-страничной организации памяти. Возможна виртуальная память и на базе сегментов, например в компьютерах фирмы Burroughs или IBM OS/2.

Подкачка страниц

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

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

Для учета распределения страниц между внешней и основной памятью каждая строка таблицы страниц дополняется признаком местонахождения страницы (битом принадлежности, valid-invalid bit).

Опишем последовательность действий при переносе страниц в ОП.

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

­ Если процесса в памяти нет (значение бита принадлежности равно false), то возникает страничный отказ (page fault) – прерывание по отсутствию страниц в памяти. Управление передается операционной системе.

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

­ После завершения загрузки страницы редактируется соответствующая строка таблицы страниц (базовый адрес и бит принадлежности).

­ Управление возвращается прерванномупроцессу.

Алгоритмы вытеснения страниц

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

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

Рассмотрим наиболее известные правила вытеснения.

Случайный выбор (Random)

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

12.2.2 «Первым пришел ¾ первым ушел» (FIFO)

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

Стратегию FIFO можно применять и локально и глобально. Ее легко реализовать: физические страницы (пусть их количество равно k) образуют список из k элементов, упорядоченный по времени подкачки страниц. Указатель списка показывает самую новую страницу. Каждый раз, когда нужно подгрузить какую-то новую страницу, содержимое указателя складывается по модулю k с единицей, и, страница, на которую указывает полученное значение, замещается.

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