Страничная организация памяти

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

Введение

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

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

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

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

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

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

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

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

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

(рис 16.1) Схема откачки и подкачки.

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

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

(рис 16.2) Адресация с аппаратной поддержкой регистров перемещения и границы.

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

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

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

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

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

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

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

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

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

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

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

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

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

Страничная организация

Страничная организация (paging) – стратегия управления памятью, при которой:

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

Цели страничной организации – обеспечить возможность не смежного распределения физической памяти для процессов, а также расширить пространство логической памяти.

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

Архитектура трансляции адресов при страничной организации изображена на рис 16.3.

(рис 16.3) Архитектура трансляции адресов при страничной организации.

На рис 16.4 приведен пример страничной организации, который демонстрирует, что, в отличие от непрерывной логической памяти процесса, соответствующие фреймы страниц в основной памяти могут быть расположены не смежно: логической странице 0 соответствует фрейм 1, странице 1 – фрейм 4, странице 2 – фрейм 3, странице 3 – фрейм 7.

(рис 16.4) Пример страничной организации.

На рис 16.5 приведен другой возможный пример страничной организации: логическая и физическая память разбита на блоки по 4 страницы подряд; в таблице страниц хранится не номер страницы, а номер блока страниц. Например, в элементе 0 таблицы страниц хранится номер блока 5, по которому адрес начала блока вычисляется домножением содержимого элемента таблицы страниц на размер блока, равный 4 (результат – 20).

(рис 16.5) Пример страничной организации блоками по 4 страницы.

Использования списка свободных фреймов иллюстрируется на рис 16.6.

(рис 16.6) Список свободных фреймов.

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

Реализация таблицы страниц

Использование ассоциативной памяти.Таблица страниц – непрерывная область физической памяти. В системе имеется базовый регистр таблицы страниц (page table base register – PTBR),указывающий на таблицу страниц и хранящий ее длину.

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

В системах с теговой архитектурой, например, "Эльбрус", регистр таблицы страниц ( регистр таблицы страниц пользователя – РТСП) содержит дескриптор таблицы страниц, который, кроме ее адреса, содержит также ее длину.

Проблема двух обращений решается введением ассоциативной памяти (cache) страниц,называемой также буфер трансляции адресов (translation lookaside buffer – TLB).Ассоциативная память, по существу, является ассоциативным списком пар вида: (номер страницы, номер фрейма).Ее быстродействие значительно выше, чем у основной памяти и у регистров.

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

Модифицированная схема трансляции адресов с использованием TLB иллюстрируется рис 16.7.

(рис 16.7) Схема трансляции адресов с использованием ассоциативной памяти.

Оценка среднего времени доступа к памяти с использованием TLB

Предположим, что ассоциативный поиск в среднем требует $$\varepsilon$$ единиц времени. Цикл памяти примем за 1. Введем также еще один показатель – число $$\alpha$$ от 0 до 1 ( hit ratio ), характеризующее, сколько раз (в среднем) номер страницы будет найден в TLB, - эмпирическую вероятность нахождения номера страницы в ассоциативной памяти.

Вычислим математическое ожидание времени доступа – Effective Access Time (EAT).Вероятность того, что номер страницы не будет найден в TLB, равна 1 – $$\alpha$$. Тогда получим:

$$EAT = (1 + \varepsilon ) \alpha + (1 + \varepsilon + 1) (1 – \alpha ) = 2 + \varepsilon – \alpha$$

Защита памяти

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

Организация защиты памяти процесса с помощью бита valid-invalid иллюстрируется на рис 16.8.

(рис 16.8) Бит valid-invalid в таблице страниц.

В примере процесс имеет 6 логических страниц с номерами от 0 до 5. Таблица страниц имеет длину 8 (с элементами от 0 до 7). Элементы 6 и 7 не соответствуют логическим страницам процесса, поэтому в них биты valid-invalid установлены в значение invalid. Поэтому при попытке обращения по логическому адресу с номером страницы 6 или 7 произойдет прерывание по неверной адресации.

Структура таблицы страниц

Иерархические таблицы страниц.Таблицы страниц в операционных системах могут быть по-разному организованы, при сохранении общих принципов их использования, описанных ранее. Рассмотрим далее три основных способа организации таблиц страниц – иерархические таблицы страниц, хешированные таблицы страниц и инвертированные таблицы страниц.

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

При обычной организации таблицы страниц, логический адрес (для 32-разрядной архитектуры, при размере страницы 4 килобайта = 4096 байтов) разбивается на номер страницы (20 битов) и смещение внутри страницы (12 битов).

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

Организация двухуровневых таблиц страниц изображена на рис 16.9.

(рис 16.9) Организация двухуровневых таблиц страниц.

Схема адресной трансляции по двухуровневой таблице страниц иллюстрируется рис 16.10.

(рис 16.10) Схема адресной трансляции по двухуровневой таблице страниц.

Хешированные таблицы страниц

Структура таблицы страниц, описанная в данном разделе, базируется на понятии хеш-функции (hash function) - целочисленной функции hash, определенной на элементах s некоторого пространства поиска S (строках, больших числах и др.) и принимающей значения из отрезка [0, H-1] где H – натуральное число. Общая идея поиска с помощью хеш-функций заключается в следующем: пространство поиска разбивается на H непересекающихся подмножеств (списков) Sh, в каждом из которых хранятся элементы, имеющие одинаковое значение хеш-функции, равное h. Таким образом, применение хеш-функции позволяет сократить поиск в среднем в H раз: при поиске элемента s сначала вычисляем hash(s),а затем выполняем поиск только в списке Shash(s) Для облегчения доступа к хеш-спискам хранится также хеш-оглавление – таблица, индексируемая значением хеш-функции, каждый элемент которой содержит ссылку на начало соответствующего списка.

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

(рис 16.11) Хешированные таблицы страниц.

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

Данный способ организации таблиц страниц предназначен для сокращения размеров таблиц страниц. В таблице страниц хранится один элемент для каждой реальной страницы, находящейся в памяти. К логическому адресу добавляется номер процесса (pid) владеющего данной страницей. По паре (номер процесса = pid, номер страницы = p) выполняется ассоциативный поиск в таблице страниц. Индекс найденного элемента таблицы i конкатенируется со смещением d внутри страницы, в результате получается физический адрес. Инвертированные таблицы страниц иллюстрируются рис 16.12.

(рис 16.12) Инвертированные таблицы страниц.

Разделяемые страницы

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

Пример использования разделяемых страниц тремя процессами приведен на рис 16.13. Три процесса используют одни и те же коды трех редакторов ed1, ed2, ed3, логические страницы которых имеют для обоих процессов номера 0, 1 и 2. Кроме того, каждый процесс использует свои индивидуальные данные data1, data2, data3.

(рис 16.13) Разделяемые страницы.

Ключевые термины

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

Ассоциативная память (кэш) страниц, буфер трансляции адресов (translation lookaside buffer – TLB) – сверхбыстродействующая ассоциативная память, содержащая номера наиболее часто используемых страниц и их адреса в основной памяти.

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

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

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

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

Инвертированная таблица страниц – таблица страниц, при обращении к которой выполняется поиск требуемой физической страницы по номеру процесса и логическому номеру страницы.

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

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

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

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

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

Откачка (swap out) - запись образа неактивного процесса на диск.

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

Подкачка (swap in) - считывание активного процесса с диска в основную память.

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

Регистр таблицы страниц (page table base register – PTBR) – регистр, указывающий на таблицу страниц и хранящий ее длину.

Регистр таблицы страниц пользователя (РТСП) – в системе " Эльбрус ": регистр, содержащий дескриптор таблицы страниц.

Cмежное распределение памяти – распределение памяти для пользовательских процессов в одной смежной области основной памяти.

Среднее время доступа (Effective Access Time - EAT) – оценка математического ожидания числа обращений к памяти при страничной организации.

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

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

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

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

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

Фрейм – образ страницы в основной памяти.

Хешированная таблица страниц – таблица страниц, при обращении к которой выполняется поиск, основанный на хешировании номера логической страницы.

Краткие итоги

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

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

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

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

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

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

Для ускорения трансляции адресов используется ассоциативная память страниц (TLB).

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

Таблицы страниц бывают различной структуры – иерархические, хешированные и инвертированные. Хешированные таблицы страниц требуют поиска нужной страницы по хеш-списку. Инвертированные таблицы страниц требуют поиска нужной физической страницы по номеру процесса и логическому номеру страницы.

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

Набор для практики

Вопросы

Упражнения

Темы для курсовых работ, рефератов, эссе