12. Особенности эффективного использования таблицы страниц: многоуровневые таблицы страниц, ассоциативная память, инвертированная таблица страниц, хеширование.

Особенности эффективного использования таблицы страниц

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

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

Многоуровневые таблицы страниц

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

В 32-битном адресном пространстве при размере страницы 4 Кбайт (Intel) получаем 2³²/2¹²=2²⁰, то есть приблизительно 10⁶ страниц – таблица должна иметь примерно 10⁶ строк, а запись в строке состоит из нескольких байтов. Каждый процесс нуждается в своей таблице страниц.

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

В ОП хранят лишь некоторые, необходимые для конкретного момента исполнения фрагмента таблицы страниц.

В силу свойства локальности число таких фрагментов относительно невелико.

Локальность – способность в течение ограниченного отрезка времени работать с небольшим набором адресов памяти.

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

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

При помощи одной таблицы второго уровня можно охватить 4Мбайт ОП. Для размещения процесса с большим объемом занимаемой памяти достаточно иметь в ОП одну таблицу первого уровня и несколько таблиц второго уровня. Очевидно, что суммарное количество строк в этих таблицах много меньше 2²⁰.

Количество уровней в таблице страниц зависит от конкретных особенностей архитектуры.

Примером реализации одноуровневого (DEC PDP-11), двухуровневого (Intel, DEC VAX), трехуровневого (Sun SPARC, DEC Alpha) пейджинга, а также пейджинга с заданным количеством уровней (Motorola).

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

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

Например, для Pentium с 256 Мбайт ОП нужна таблица размером 64 Кбайт строк.

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

Один из способов решения данной проблемы – использование хеш-таблицы виртуальных адресов.

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

Хеш и хеш-функция

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

Хеш-функции – функция, выполняющая одностороннее преобразование (хеширование) входных данных.

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

Каждой странице физической памяти соответствует одна запись в хеш-таблице и инвертированной таблице страниц.

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

Ассоциативная память

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

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

Это устройство называют ассоциативной памятью или буфером поиска трансляции (translation lookaside buffer - TLB).

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

Структура кэш памяти

Адрес данных в ОП	Данные	Управл. информация
		бит модиф.	бит обращ.

Общая схема функционирования

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

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

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

Число удачных поисков номера страницы в ассоциативной памяти по отношению к общему числу поисков называется hit ratio («процент попаданий в кэш»).

Обращение к одним и тем же страницам повышает hit ratio (чем больше hit ratio, тем меньше среднее время доступа к данным, находящимся в ОП).

Пример: Если для доступа к памяти через таблицу страниц необходимо 100 нс, а для доступа через ассоциативную память – 20 нс. Если hit ratio = 90%, то среднее время доступа -> 0,9x20+0,1x100=28нс.

Минус: При переключении контекста процесса при использовании ассоциативной памяти требуется ее «очистка», что ведет к увеличению времени переключения контекста.