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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Защита на уровне страниц

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

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

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

§ при попытке записи в страницу с атрибутом "только чтение";

§ при попытке обращения к странице ядра из режима пользователя;

§ при попытке чтения или записи страницы с атрибутом "только выполнение";

§ при любом обращении к отсутствующей странице.

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

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

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

1. Что такое виртуальная память?

2. Для чего нужно преобразование памяти? Какие существуют этапы такого преобразования и какими системами они выполняются?

3. От чего зависит размер виртуальной памяти? Может ли он отличаться от размера памяти физической? Как именно?

4. Каковы достоинства и недостатки простого непрерывного распределения памяти?

5. Может ли при мультипрограммном режиме использоваться аналог простого непрерывного распределения для каждой из помещённых в память программ?

6. Для чего могут использоваться оверлейные структуры? В каких ОС они применяются – в однопрограммных или мультипрограммных?

7. Какое из преобразований более эффективно – страничное или сегментное?

8. Какое из преобразований вызывает большую фрагментацию памяти и почему?

9. Каковы недостатки сегментного преобразования памяти?

10. Какие алгоритмы существуют для размещения задачи в памяти? Какой из них эффективнее – размещение задачи в самом подходящем участке или в самом неподходящем и почему?

11. Для чего может потребоваться выталкивание страниц из памяти и куда они при этом попадают?

12. Какой из алгоритмов вталкивания работает эффективнее – вталкивание по запросу или с упреждением – и почему?

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

14. Как организована защита страниц в мультипрограммных системах?

 

 

Приложение