Страничное распределение памяти кратко

Обновлено: 04.07.2024

Сегментное, страничное и сегментно-страничное распределение– это распределение с использованием внешней памяти.

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

Вся оперативная память машины также делится на части такого же размера, называемые физическими страницами (или блоками).

Размер страницы обычно выбирается равным степени двойки: 512, 1024 и т.д., это позволяет упростить механизм преобразования адресов.

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

Рис. 2.12. Страничное распределение памяти

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

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

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

- дольше всего не использовавшаяся страница,

- первая попавшаяся страница,

- страница, к которой в последнее время было меньше всего обращений.

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

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

Рассмотрим механизм преобразования виртуального адреса в физический при страничной организации памяти (рисунок 2.13).

Виртуальный адрес при страничном распределении записывается в виде пары чисел (P, Sv) (P – порядковый номер виртуальной страницы, начиная с 0, Sv – смещение в пределах виртуальной страницы).

Физический адрес записывается в виде пары чисел (n, Sf) (n – порядковый номер физической страницы, начиная с 0, Sv – смещение в пределах физической страницы).

Для преобразования адресов исполбзуются особые свойства стпаничной организации:

1) Размер страницы равен 2 k , а значит смещение S можно получить простым отделением разрядов в двоичной записе, а оставшиеся старшие разряды – это двоичная запись номаре страницы.

10 0110011001 2 10 –размер страницы

2) В пределах страницы последовательность виртуальный адресов однозначно отображается с последовательностью физических адресов

Схема преобразования адресов

Произошло обращение к некоторому виртуальному адресу. Процессор выполняет следующие действия:

1) Из специального регистра процессора извлекается адрес AT – таблицы страниц процессов. На основании начального адреса таблицы страниц, номера виртуальной страницы P (старшие разряды) и длины одной записи в таблице страниц (l) определяется адрес нужного дескриптора в таблице

2) Из дескриптора извлекается номер соответствующей физической страницы n.

3) К номеру физической страницы при соединяется смещение S (младшие разряды).

1) Простота пересчета адресов

2) Небольшой объем страниц

3) Относительная простота метода

1) Не учет содержимого разбиваемых данных

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

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

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

Рис. 2.14. Распределение памяти сегментами

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

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

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

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

Рис. 2.15. Схема преобразования виртуального адреса в физический для сегментно-страничной организации памяти

Рис. 2.12. Страничное распределение памяти

- дольше всего не использовавшаяся страница,

- первая попавшаяся страница,

- страница, к которой в последнее время было меньше всего обращений.

Для преобразования адресов исполбзуются особые свойства стпаничной организации:

10 0110011001 2 10 –размер страницы

Схема преобразования адресов

Произошло обращение к некоторому виртуальному адресу. Процессор выполняет следующие действия:

2) Из дескриптора извлекается номер соответствующей физической страницы n.

3) К номеру физической страницы при соединяется смещение S (младшие разряды).

1) Простота пересчета адресов

2) Небольшой объем страниц

3) Относительная простота метода

1) Не учет содержимого разбиваемых данных

Рис. 2.14. Распределение памяти сегментами

Рис. 2.15. Схема преобразования виртуального адреса в физический для сегментно-страничной организации памяти

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

Дескриптор страницы включает в себя следующую информацию:

номер физической страницы, в которую загружена данная виртуальная страница;

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

дольше всего не использовавшаяся страница;

первая попавшаяся страница;

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

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

42. Таблицы страниц для больших объемов памяти.

Размер страницы влияет также на количество записей в таблицах страниц. Чем меньше страница, тем более объемными являются таблицы страниц процессов и тем больше места они занимают в памяти. Учитывая, что в современных процессорах максимальный объем виртуального адресного пространства процесса, как правило, не меньше 4 Гбайт, то при размере страницы 4 Кбайт и длине записи 4 байта для хранения таблицы страниц может потребоваться 4 Мбайт памяти.

1) Многоуровневые таблицы страниц. Достоинства:

не надо иметь в памяти постоянно всю таблицу страниц, а только таблицу разделов; Недостатки:

дополнительный этап преобразования адреса

Рисунок 13. Схема преобразования виртуального адреса для двухуровневой структуризации адресного пространства

1. Путем отбрасывания k+n младших разрядов в виртуальном адресе определяется номер раздела, к которому принадлежит данный виртуальный адрес.

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

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

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

искомый физический адрес.

2) Инвертированные таблицы страниц Достоинства:

гораздо меньше по объёму. Недостатки:

не совсем ясно, как в ней искать виртуальный адрес.

Этот подход применяется на машинах PowerPC, некоторых рабочих станциях Hewlett-Packard,

IBM RT, IBM AS/400 и ряде других.

В этой таблице содержится по одной записи на каждый страничный кадр физической памяти. Существенно, что достаточно одной таблицы для всех процессов. Таким образом, для хранения функции отображения требуется фиксированная часть основной памяти, независимо от разрядности архитектуры, размера и количества процессов. Например, для компьютера Pentium c 256 Мбайт оперативной памяти нужна таблица размером 64 Кбайт строк.

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

43. Алгоритмы замещения страниц.

1) Оптимальный (нереализуемый)

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

2) Исключение недавно использованных страниц

Бит R – бит обращения, бит M – бит модификации. Суть:

при запуске процесса R=0, M=0 для всех страниц.

При каждом прерывании по таймеру бит R сбрасывается

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

Класс 0: ни обращений, ни модификации Класс 1: нет обращений, есть модификация Класс 2: есть обращения, нет модификации Класс 3: есть обращения, есть модификация

Алгоритм удаляет произвольную страницу низшего класса.

Как в FIFO, но если у первой страницы бит R=0, то она удаляется, а если бит R=1, то он сбрасывается, а страница отправляется в конец списка. Если ко всем страницам есть обращение – вырождается в FIFO.

Циклический список. Если R=0, страница выгружается, на её место загружается новая. Если R=1, то R сбрасывается, стрелка идёт дальше.

6) LRU – Least recently used

1 Связанный список всех страниц. Первая страница – только что использованная. Использовали – переместили в начало.

очень долгий даже на аппаратном уровне.

Страничная память — способ организации виртуальной памяти, при котором единицей отображения виртуальных адресов на физические является регион постоянного размера (т. н. страница). [1] Типичный размер страницы — 4096 байт, для некоторых архитектур — до 128 КБ.

Поддержка такого режима присутствует в большинстве 32-битных и 64-битных процессоров. Такой режим является классическим для почти всех современных ОС, в том числе Windows и семейства UNIX. Широкое использование такого режима началось с процессора VAX и ОС VMS с конца 70-х годов (по некоторым сведениям, первая реализация). В семействе x86 поддержка появилась с поколения 386, оно же первое 32-битное поколение.

Содержание

Решаемые задачи

Механизм работы

Логический адрес в страничной системе – упорядоченная пара (p,d), где p – номер страницы в виртуальной памяти(селектор), а d – смещение в рамках страницы p, на которой размещается адресуемый элемент. Разбиение адресного пространства на страницы осуществляется вычислительной системой незаметно для программиста. Поэтому адрес является двумерным лишь с точки зрения операционной системы, а с точки зрения программиста адресное пространство процесса остается линейным. На самом деле адрес в памяти также можно указать другими способами - через константы и значения переменных, но всегда используется пара значений p и d, в явном или неявном виде. Каждый раз, при выполнении команды, процессор производит преобразование логического адреса в линейный адрес - 32-разрядный абсолютный адрес в памяти. После вычисления линейного адреса процессор преобразует его в физический адрес, по которому и производит обращение к памяти.

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

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

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

Управление страничным разбиением памяти обычно возлагается на специальную микросхему MMU (Memory Managment Unit - устройство управления памятью). В микропроцессоре i80486 и выше это устройство встроено в процессор.

Как и сегментация, страничная организация памяти связана с преобразованием виртуального адреса (в данном случае линейного) в физический. В страничном преобразовании базовым объектом памяти является блок фиксированного размера, называемый страницей (page).

В процессе страничного преобразования старшие 20 бит 32-х битного линейного адреса заменяются новым значением - номером физической страницы. Младшие же 12 бит линейного адреса определяют положение байта внутри страницы и остаются неизменными.

Для уменьшения размера таблицы страниц в микропроцессорах x86 предусмотрена двухуровневая схема преобразования адреса. Основой страничного преобразования служит регистр управления CR3, содержащий 20-ти битный физический базовый адрес каталога страниц текущей задачи. Предполагается, что каталог выровнен по границе страничного кадра, постоянно находится в памяти и не участвует в свопинге. Корневая страница, называемая каталогом страниц, содержит 1024 32-х битных дескриптора, называемых элементами каталога страниц PDE (Page Directory Entry). Каждый из них адресует подчиненную таблицу страниц. Каждая из этих таблиц содержит 1024 32-х битных дескриптора, называемая элементами таблицы страниц. PTE (Page Table Entry). Каждый PTE содержит адрес страничного кадра в физической памяти. Собственно преобразование линейных адресов в физические состоит из следующих действий:

Старшие 10 бит 31 - 22 линейного адреса, дополненные двумя младшими нулями, служат индексом PDE.
Средние 10 бит 21 - 12 линейного адреса, дополненные двумя младшими нулями, индексируют таблицу страниц PTE. Элемент PTE содержит 20-битный базовый адрес страничного кадра в физической памяти.

Этот базовый адрес из элемента PTE объединяется с младшими 12-ю битами линейного адреса, образуя 32-х битный физический адрес.

Страничная память x86

Исторически x86 использует 32-битные PTE, 32-битные виртуальные адреса, 4KB-страницы, 1024 записи в таблице, двухуровневые таблицы. Старшие 10 бит виртуального адреса — номер записи в директории, следующие 10 — номер записи в таблице, младшие 12 — адрес внутри страницы. [2]

Начиная с Pentium Pro, процессор поддерживает страницы размером 4Мб. Однако, чтобы система и программы, запущенные в ней, могли использовать страницы такого размера, технология 4-х Мб страниц (hugepages) должна быть соответствующим образом активирована, а приложение настроено на использование страниц такого размера. Процессор x86 в режиме PAE (Physical Address Extension) и в режиме x86_64 (long mode) использует 64-битные PTE (из них реально задействованы не все биты физического адреса, от 36 в PAE до 48 в некоторых x86_64), 32-битные виртуальные адреса, 4KB-страницы, 512 записей в таблице, трехуровневые таблицы с четыремя директориями и четыремя записями в супер-директории. Старшие 2 бита виртуального адреса — номер записи в супер-директории, следующие 9 — в директории, следующие 9 — в таблице. Физический адрес директории или же супер-директории загружен в один из управляющих регистров процессора.

При использовании PAE вместо 4МБ больших страниц используются двухмегзбайтные. В архитектуре x86_64 возможно использовать страницы размером 4 килобайта (4096 байт), 2 мегабайта, и (в некоторых AMD64) 1 гигабайт.

Страничное прерывание

Некоторые процессоры (MIPS) не имеют обращающегося к таблице микрокода, и генерируют отказ страницы сразу после неудачи поиска в TLB, обращение к таблице и её интерпретация возлагаются уже на обработчик отказа страницы. Это лишает таблицы страниц требования соответствовать жёстко заданному на уровне аппаратуры формату.
Причины отказа страницы (page fault):

Алгоритм работы страничного прерывания:

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

Таблицы страниц

Таблица страниц (Page Table) состоит из 4-байтовых элементов (Entries). Эти элементы называются PTE (Page Table Entries) и представляют собой по сути - указатели на страницы, по формату - структуры данных.
Структура таблицы:

Если страница не присутствует в памяти (бит P=0), то процессор не использует все остальные биты элемента PTE и программа может их использовать по своему усмотрению.

Таблицы страниц процессов

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

Работа менеджера памяти Windows

Для управления виртуальной памятью в операционной системе Windows предусмотрен специальный менеджер Virtual Memory Manager (VMM). Он является составной частью ядра операционной системы и представляет собой отдельный процесс, постоянно находящийся в оперативной памяти. Основная задача VMM заключается в управлении страницами виртуальной памяти. [4]

Каждому процессу VMM выделяет часть физической памяти, которая называется рабочим набором (Working Set). Кроме того, VMM создает базу состояния страниц (page-frame database), которая организована как шесть списков страниц одного типа. Выделяют следующие типы страниц:

Свободные страницы могут применяться, однако прежде они подлежат процедуре обнуления (заполнения нулями). Процедурой обнуления страниц занимается специальная подпрограмма менеджера памяти Zero Page Thread;

Zeroed — пустая страница, которая является свободной и обнуленной. Такие страницы готовы к использованию любым процессом;
Bad — страница, которая вызывает аппаратные ошибки и не может применяться ни одним процессом.

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

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

В идеале замещению должна подлежать та страница, к которой в будущем не будет обращений, или страница, которая не будет использоваться дольше других. Однако достоверного способа определить, какая именно страница отвечает перечисленным критериям, нет. Поэтому менеджер памяти применяет следующий алгоритм. Он периодически просматривает список рабочих страниц (Valid) и помечает их как отсутствующие (P = 0). Однако данные страницы не удаляются из рабочего процесса — они остаются на месте и просто переводятся из категории Valid в категорию модифицированных (Modified) или резервных (Standby) страниц ( никаких изменений в содержимом этих страниц не производится). Если измененная таким образом страница требуется какому-нибудь процессу, то происходит обращение к ней и возникает ошибка обращения к странице. Но поскольку в действительности страница находится в физической памяти и ее содержимое не подвергалось изменению, то менеджеру памяти достаточно перевести данную страницу обратно в категорию Valid, сделав ее доступной для процесса. Если же страница не используется в течение длительного времени процессами и обращений к ней не происходит, она со временем переводится в категорию свободных (Free) страниц, а затем обнуляется и переводится в категорию пустых (Zeroed) страниц.

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

Отображаемые в память файлы

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

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

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

Сегментно-страничная виртуальная память

Существуют две другие схемы организации управления памятью: сегментная и сегментно-страничная. [5] Сегменты, в отличие от страниц, могут иметь переменный размер. При сегментной организации виртуальный адрес является двумерным как для программиста, так и для операционной системы, и состоит из двух полей – номера сегмента и смещения внутри сегмента. Главное отличие сегментной организации от страничной в том, что в последней линейный адрес преобразован в двумерный операционной системой для удобства отображения, а сегментной двумерность адреса является следствием представления пользователя о процессе не в виде линейного массива байтов, а как набор сегментов переменного размера.

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

Каждый сегмент – линейная последовательность адресов, начинающаяся с 0. Максимальный размер сегмента определяется разрядностью процессора (при 32-разрядной адресации это 232 байт или 4 Гбайт). Размер сегмента может меняться динамически (например, сегмент стека). В элементе таблицы сегментов помимо физического адреса начала сегмента обычно содержится и длина сегмента. Если размер смещения в виртуальном адресе выходит за пределы размера сегмента, возникает исключительная ситуация.

Логический адрес – упорядоченная пара v=(s,d), номер сегмента и смещение внутри сегмента.

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

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

Аннотация: В лекции рассматриваются: откачка и подкачка (swapping); стратегии динамического распределения памяти; фрагментация; принципы страничной организации; таблица страниц; использование ассоциативной памяти; двухуровневые, иерархические, хешированные и инвертированные таблицы страниц; разделяемые страницы.

Презентацию к данной лекции Вы можете скачать здесь.

Введение

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

Откачка и подкачка

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

Откачка и подкачка (swapping) – это действия операционной системы по откачке (записи) образа неактивного процесса на диск или подкачке (считыванию) активного процесса в основную память . Необходимость выполнения подобных действий вызвана нехваткой основной памяти.

Файл откачки (backing store) - область дисковой памяти, используемая операционной системой для хранения образов откачанных процессов. Файл откачки организуется максимально эффективно: обеспечивается прямой доступ ко всем образам процессов в памяти (например, через таблицу по номеру процесса).

Популярная разновидность стратегии откачки и подкачки – roll out / roll in: откачка и подкачка на базе приоритетов; более приоритетные процессы исполняются, менее приоритетные – откачиваются на диск .

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

В распространенных ОС – UNIX , Linux, Windows и др. – реализованы различные стратегии откачки и подкачки.

Схема откачки и подкачки изображена на рис. 16.1.

Смежное распределение памяти

Наиболее простая и распространенная стратегия распределения памяти – смежное распределение памяти – распределение памяти для пользовательских процессов в одной смежной области памяти. Основная память разбивается на две смежных части ( partitions ), которые "растут" навстречу друг другу: резидентная часть ОС и вектор прерываний – по меньшим адресам. Для пользовательских процессов память распределяется в одном и том же смежном участке памяти. Для каждого процесса регистр перемещения указывает на начало выделенной ему области памяти, регистр границы содержит длину диапазона логических адресов . Каждый логический адрес должен быть меньше содержимого регистра границы. Физический адрес вычисляется аппаратно как сумма логического адреса и значения регистра перемещения. Схема адресации с аппаратной поддержкой регистров перемещения и границы изображена на рис. 16.2.

Общая задача распределения памяти и стратегии ее решения

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

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

Для решения данной задачи применяются следующие стратегии: метод первого подходящего (first-fit), метод наиболее подходящего (best-fit) и метод наименее подходящего (worst-fit).Рассмотрим каждую из них подробнее.

Метод первого подходящего:Выбирается первый по списку свободный участок подходящего размера (не меньшего, чем n ). На первый взгляд, данная стратегия оптимальна, но далее мы увидим, что это не всегда так.

Метод наиболее подходящего:Выбирается из списка наиболее подходящий свободный участок (минимального размера, не меньшего, чем n ). В отличие от предыдущего метода, требует просмотра всего списка, если список не упорядочен по размеру областей. Применение метода приводит к образованию оставшейся части самого маленького размера.

Метод наименее подходящего: Выбирается из списка подходящая область наибольшего размера. Почему наибольшего? Чтобы избежать фрагментации (проблема фрагментации подробно рассмотрена далее в данной лекции).

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

Фрагментация

Фрагментация – это дробление памяти на мелкие не смежные свободные области маленького размера. Фрагментация возникает после выполнения системой большого числа запросов на память , таких, что размеры подходящих свободных участков памяти оказываются немного больше, чем требуемые. Например, если имеется 100 смежных свободных областей памяти по 1000 слов, то после выполнения 100 запросов на память по 999 слов каждый в списке свободной памяти останутся 1000 областей по одному слову.

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

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

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

Читайте также: