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

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

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

Итак, виртуальный адрес состоит из виртуального номера страницы (high-order bits) и смещения (low-order bits). Номер виртуальной страницы используется как индекс в таблице страниц для нахождения записи (entry) о виртуальной странице. Из этой записи в таблице страниц находится номер кадра (page frame number), затем прибавляется смещение и формируется физический адрес. Помимо этого запись в таблице страниц содержит информацию об атрибутах страницы, в частности биты защиты.

Основную проблему для эффективной реализации таблицы страниц создают большие размеры виртуальных адресных пространств современных компьютеров, которые обычно определяются разрядностью архитектуры процессора. Самыми распространенными на сегодняшний день являются 32-разрядные процессоры, позволяющие создавать виртуальные адресные пространства такого размером 4 Гб (для 64-разрядных компьютеров эта величина равна 2**64б).

Подсчитаем примерный размер таблицы страниц. В 32-битном адресном пространстве при размере страницы 4К (Intel) получаем 1М страниц, а в 64-битном и того более. Т.о. таблица должна иметь 1М строк (entry), причем запись в строке состоит из нескольких байт. Заметим, что каждый процесс, нуждается в своей таблице страниц (а в случае сегментно-страничной схемы по одной на каждый сегмент). Итак, в этом случае таблица страниц может быть слишком большой.

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

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

Рассмотрим модельный пример (см. рис. 9.4). Предположим, что 32-разрядный адрес делится на 10-разрядное поле Рtr1, 10-разрядное поле Рtr2 и 12-разрядное смещение Offset. 12 разрядов смещения позволяют локализовать байт внутри страницы размером 4К (2**12), а всего имеем 2**20 страниц. Как видно из рис. 9.4 1024 строки в таблице верхнего уровня при помощи поля Ptr1 ссылаются на 1024 таблицы второго уровня, каждая из которых содержит также 1024 строки. При помощи поля Ptr2 каждая строка таблицы второго уровня указывает на конкретную страницу. Смысл такой организации в том, чтобы избежать поддержки всех таблиц второго уровня (а их 1024) в памяти постоянно. Рассмотрим пример с круглыми цифрами. Допустим, что процессу нужны 12М памяти: 4М в нижней части памяти для кода, 4М в нижней части для данных и 4М в верхней части памяти для стека. Между дном стека и верхом данных гигантское пространство размером 4Gb-12Mb, которое не используется. Для этого случая необходимы лишь 1 таблица верхнего уровня и 3 таблицы второго уровня.

Рис. 9.4 Пример двухуровневой таблицы страниц.

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

Рассмотрим одну из записей таблицы страниц. Ее размер колеблется от системы к системе, но 32 бита - наиболее общий случай. Самое важное поле - номер кадра. Цель страничного отображения - локализовать эту величину. Далее бит присутствия. Далее биты защиты (например, 0 - read/write, 1 - read only...) Есть еще биты модификации (если на нее писали) и биты ссылки, которые помогают выделить мало используемые страницы, биты разрешающие кэширование. Заметим, что адреса страниц на диске не являются частью таблицы страниц.

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

Количество уровней в таблице страниц зависит от конкретных особенностей архитектуры. Можно привести примеры реализации одноуровневого (DEC PDP-11), двухуровневого (Intel, DEC VAX), трехуровневого (Sun SPARC, DEC Alpha) paging'а, а также paging'а с задаваемым количеством уровней (Motorola). Функционирование RISC процессора MIPS R2000 осуществляется вообще без таблицы страниц. Здесь поиск нужной страницы, если эта страница отсутствует в ассоциативной памяти, должна взять на себя ОС (так называемый zero level paging).

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

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

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

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

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

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

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

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

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

Например, предположим, что для доступа к таблице страниц необходимо 100 нс, а для доступа к ассоциативной памяти 20 нс. С 90% hit ratio среднее время доступа - 0.9*20+0.1*100 = 28 нс.

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

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

Дата добавления: 2014-12-16