Рисунок 2.  Преобразование виртуального адреса в реальной адрес памяти

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

Стратегия вталкивания, определяющая, когда следует переписать страницу или сегмент из внешней памяти в ОП.

а) вталкивание по запросу - система ожидает ссылки на страницу/сегмент от выполняющегося процесса (прерывание по отсутствию страницы);

аргументы за:

• путь выполнения программы наверняка предсказать невозможно;

• гарантия расположения в ОП только нужных страниц;

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

аргументы против:

• подкачка по одному блоку приводит к увеличению общего времени ожидания.

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

Достоинство: сокращается время ожидания.

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

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

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

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

Рассмотрим процедуры определения блоков для выталкивания из ОП.

а) выталкивание случайной страницы - в реальных системах не применяется;

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

Аргумент: у страницы уже были возможности использовать свой шанс.

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

в) выталкивание дольше всего неиспользованных страниц.

Для реализации необходимо реализовать обновляемые временные метки. Эвристический аргумент: - недавнее прошлое - хороший ориентир на будущее.

Недостаток - существенные издержки: постоянное обновление временных меток.

г) выталкивание реже всего используемых страниц - предполагает наличие счетчиков страниц (менее интенсивно, нежели обновляемые временные метки). Интуитивно оправдано, но тоже может быть не рационально.

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

1.признак обращения 0 - было

1 - не было.

2.признак модификации записи 0 - неизменен.

1 - изменен.

Возможны следующие варианты комбинаций {00,10,01,11}. Если изменений на странице не было, то страницу можно просто переписать, а не сохранять на диске.

Модуль 5. Управление основной памятью

Тема 10. Страничная организация. Сегментная организация. Странично-сегментная организация. Двухуровневая страничная организация

Динамическая страничная организация

Сегментная организация виртуальной памяти

Комбинированная странично-сегментная организация памяти

Двухуровневая страничная организация

Динамическая страничная организация

Динамическая страничная организация памяти - это страничная организация РОП с динамическим размещением страниц процессов по их запросам (Intel 386 – размер страницы 4 Кбайт)

Достоинства:

1. Допустимость максимального объема выполняющихся программ, простота их программирования.

2. Значительное уменьшение временной фрагментации, максимальное использование РОП и максимальный уровень мультипрограммирования.

Недостатки:

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

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

Для решения проблемы пробуксовки страниц важную роль играет не только стратегия выталкивания, но и размер страницы.

На выбор оптимального размера страницы влияют следующие факторы:

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

2.Большой размер страницы приводит к тому, что в ОП здесь помещены команды и данные, к которым не было обращений.

3.Ввод-вывод будет эффективен при больших размерах страниц.

4.Свойство локальности распространяется, как правило, на малые участки программ.

5.При малых размерах страниц потери на внутреннюю фрагментацию уменьшаются.

Вывод: необходимость небольших размеров страницы.

Экспериментальные результаты поведения программы в ВС со страничной организацией ВП показывают:

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

2.При постоянном объеме выделенной ОП с увеличением размера страницы растет число прерываний по отсутствию нужной страницы.

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

4.Число команд, выполненных на странице до передачи управления другой странице, как правило, невелико.

Сегментная организация виртуальной памяти

В системе с сегментной организацией памяти снимается ограничение на фиксированный размер блока и выполняется соответствующее произвольное разбиение АП процесса на сегменты.

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

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

• выполнение E

• чтение R

• запись W

• расширение A

и их различных комбинаций.

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

В сегментной организации все сегменты различного размера и могут размещаться в несмежных участках РОП.

Достоинства:

1.Уменьшение временной фрагментации, так как естественно учитывается свойство локальности программ.

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

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

Недостатки:

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

2.Может возникнуть временная фрагментация для больших размеров процедур и данных.

Комбинированная странично-сегментная организация памяти

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

Трехуровневая адресация использует две таблицы отображения (таблица сегментов + таблица страниц сегментов).

V=(S,P,d)

S - номер сегмента; P- номер страницы; d - смещение.

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

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

Рисунок.6.3 Преобразование адреса страницы при чисто ассоциативном отображении.

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

Достоинства странично-сегментной организации:

1. Комбинированная организация эффективна для больших программ (процедур), имеющих свою локальность.

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

Двухуровневая страничная организация

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

Виртуальный адрес состоит также из трех компонентов (гиперстраница, страница, смещение).

Достоинства:

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

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

Пример: ЕС ЭВМ ряд 2 и IBM PC

Страницы 2 - 4 кб; гиперстраница 64 - 1024 кб

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