25 Страничная организация памяти. Организация, хранение, использование страничных таблиц. Стратегия замещения страниц.

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

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

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

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

Интерпретация логического адреса показана на рисунке. Если выполняемый процесс обращается к логическому адресу v = (p,d), механизм отображения ищет номер страницы p в таблице страниц и определяет, что эта страница находится в страничном кадре p', формируя реальный адрес из p' и d.

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

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

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

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

Адресное пространство бывает: пользовательское(уровень ОП,вирт.память) и компьютера.

Вирт.АП (ОП) => Физ. АП (ОП и Жест.Диск)

Виртуальная память (ее емкость) – емкость ОП, состоит из емкости всех ЗУ (ОП и HDD)

Процессор формирует всегда виртуальные адреса. MMU – устройство управления памятью, преобразующее виртуальные адреса в физические. Механизм виртуальной памяти реализуется через страничную организацию при этом вся память (В и Ф) делится на страницы одного размера. Средние потери при страничной организации ОП на программу – 0,5 страницы. Таблицы страниц могут располагаться: в ОП, но уменьшается производительность из-за частого обращения к ОП, поэтому хранят в кэше. См. Рис: Атрибут (дескриптор страницы) содержит ее ФА. Дескриптор страницы – одно слово.

Размер страницы от 1 КБ до 16 КБ (распространен 4 КБ) Чем меньше размер страницы, тем меньше потери памяти, однако больше размер таблицы. Обмен между HDD и ОП происходит страницами. Для каждого процессора дескриптор страницы имеет свой формат, но есть общие свойства: есть бит присутствия P: 1 – если страница в ОП; 0 – если нет

Если P=0, то возникает страничное прерывание. В страничной организации памяти используется TLB – буфер быстрого преобразования адресов, где хранятся дескрипторы страниц, которые загр. в ОП.

У каждой таблицы в дескрипторе хранятся биты: активности, изменения, защиты.

При страничном прерывании необходимо заместить страницу в памяти:

1)                  Удаляется страница, которая дольше всего находится в ОП

2)                  Удаляется страница, которая меньше всех находилась в ОП

3)                  FIFO

LIFO (3 и 4 требуют подсчета времени пребывания в ОП)

Виртуальная память разбивается на логические блоки. На такие же размером блоки разбивается и ОП.

 Происходит преобразование:

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

Как только страница становится активной она помещается в TLB (Translation Lookside Buffer). Для каждой страницы вводится флаг присутствия Р. Р=1 если страница находится в ОП, Р=0 если она на HDD. Если обращение идёт к странице, находится на HDD организуется страничное прерывание и осуществляется подкачка.

Организация данной таблицы решается программно. Сама таблица – аппаратно (буфер на 16-64 дескрипторов).

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

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

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

Стратегия замещения страниц.

Все способы делятся на:

1.       Физически нереализуемые.

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

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

2.       Физически реализуемые.

а). Алгоритм случайного замещения.

б). Выгружается странница наиболее давно использовавшаяся (по времени пребывания в ОП либо с использованием бита активности (А))

в). FIFO

г). LIFO

д). Приоритетный FIFO. (Алг. "Карабкающейся” стр.)

е). Страницы без изменений (М=0) – первые кандидаты на удаление.

Т.к. страницы предоставляются пользователю целиком. Если o - ?? -1 байт – размер страницы. Тогда среднее число потерянных битов будет ???? Чем меньше размер стр тем меньше битов потери, но нужны большие страничные таблицы. Поэтому остановились на страницах размером 4к.