ЛЕКЦИЯ №9 Сегментная, страничная и сегментно-страничная организация памяти

1. Сегментный способ организации памяти

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

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

Физически имя (или порядковый номер) сегмента будет соответствовать некоторому адресу, с которого этот сегмент начинается при его размещении в памяти, и смещение должно прибавляться к этому базовому адресу.

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

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

Достоинства сегментного метода:

– программу можно загружать не целиком, а по мере необходимости;

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

Недостатки сегментного метода:

– замедление доступа к требуемой ячейке памяти;

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

В качестве примера операционной системы, применяющей сегментное преобразование памяти, можно назвать OS/2.

2. Страничный способ организации памяти

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

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

Виртуальный адрес
Номер виртуальной страницы	Смещение внутри страницы
	Таблица страниц
	Атрибуты	Физ. страница
Номер физической страницы	Смещение внутри страницы
Физический адрес

Поскольку размер страницы – величина фиксированная, то существует проблема его правильного выбора. Чем больше размер страницы, тем меньше будет размер структуры данных, обслуживающих преобразование адресов, но и тем больше будут потери, связанные с тем, что память можно выделять только постранично (возникает фрагментация). На некоторых архитектурах размер страниц задан аппаратно, например, на Intel – это 4 Кбайт, на DEC PDP-11 – 8 Кбайт, а на других архитектурах, таких, как Motorola 68030, размер страниц задается программно.

Важными характеристиками архитектуры процессора являются размеры физического и виртуального адресных пространств, определяющих соответственно ограничение на размер физической памяти и пределы, в которых может меняться виртуальный адрес. Размеры адресных пространств обычно определяются разрядностью архитектуры процессора. Самыми распространенными сейчас являются 32-разрядные процессоры, позволяющие создавать виртуальные адресные пространства размером 2³² байт (4 Гбайта).

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

Основным достоинством страничного способа распределения памяти является минимально возможная фрагментация.

Недостатки страничного преобразования:

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

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

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

3. Стратегии управления

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

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

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

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

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

Выталкивание случайной страницы. Данная стратегия проста, но неэффективна.

Алгоритм FIFO (First In – First Out) – для освобождения выбирается страница, дольше всего находившаяся в физической памяти. Реализуется созданием очереди страниц. Недостаток – могут быть удалены активно используемые страницы.

Алгоритм LRU (Least Recently Used – дольше всего неиспользуемый) – в памяти освобождается страница, к которой наиболее долго не обращались. Существуют разные реализации алгоритма: основанные на связном списке страниц в памяти, отсортированном по давности обращений; использующие таймер; использующие специальную матрицу. Эти алгоритмы требуют специальной аппаратной поддержки.

Алгоритм LFU (Least Frequently Used) – выталкивание реже всего используемой страницы, т.е. страницы, к которой было меньше всего обращений. Недостаток – может быть вытолкнута только что записанная страница, поскольку как раз к ней и было меньше обращений.

NUR (Not Used Recently) – выталкивание страницы, не использовавшейся в последнее время. Он предусматривает введение двух битов-признаков на страницу: бита-признака обращения и бита-признака модификации. Биты-признаки обращений периодически сбрасываются в ноль, чтобы давно неиспользуемые страницы не задерживались в памяти. В первую очередь для замещения выбирается страница без обращений, а из них – страница без модификаций.

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

В большинстве современных ОС используется дисциплина LRU как наиболее эффективная. Примеры – операционные системы OS/2, Linux. Но в некоторых ОС, разработчики которых стремились сделать систему максимально независимой от аппаратных возможностей процессора, применяются другие дисциплины. Например, в ОС Windows NT используется правило FIFO. Для того, чтобы устранить его недостатки, применяется "буферизация" тех страниц, которые предназначены к выгрузке, как некоторый промежуточный этап. Т.е., прежде чем выгрузить выбранную страницу, ее помечают как кандидата на выгрузку. Если в следующий раз к ней происходит обращение, то она никуда не выгружается, а уходит в конец списка FIFO. В противном случае ее выгружают, а в кандидаты на выгрузку выбирают следующую страницу. Поскольку величина такого "буфера" не может быть большой, эффективность страничной реализации памяти в Windows NT ниже, чем у вышеназванных ОС, и даже при существенно большем объеме памяти начинается явление пробуксовки.

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