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

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

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

Например, в 32-битном адресном пространстве при размере страницы 4 Кбайт (Intel) получаем 23²/21² = 2²⁰, т.е. приблизительно миллион страниц, а в 64-битном и того более. Таким образом, таблица должна иметь примерно миллион строк, а запись в строке состоит из нескольких байтов.

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

В силу свойства локальности число таких фрагментов относительно невелико. Выполнить разбиение таблицы страниц на части можно по-разному. Наиболее распространенный способ разбиения – организация так называемой многоуровневой таблицы страниц.

Для примера рассмотрим двухуровневую таблицу с размером стра- ниц 4 Кбайт, реализованную в 32-разрядной архитектуре Intel (рис. 31).

Таблица, состоящая из 2²⁰ строк, разбивается на 2¹⁰ таблиц второго уровня по 2¹⁰ строк. Эти таблицы второго уровня объединены в общую структуру при помощи одной таблицы первого уровня, состоящей из 2¹⁰ строк. 32-разрядный адрес делится на 10-разрядное поле p1, 10- разрядное поле p2 и 12-разрядное смещение d. Поле p1 указывает на нужную строку в таблице первого уровня, поле p2 – второго, а поле d локализует нужный байт внутри указанного страничного кадра.

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

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

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

Общие принципы функционирования кэш-памяти

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

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

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

Инвертированная таблица страниц.Несмотря на многоуровневую организацию, хранение нескольких таблиц страниц большого размера по-прежнему представляют собой проблему. Особенно это актуально для 64-разрядных архитектур, где число виртуальных страниц очень велико. Одним из вариантов решения этой проблемы, позволяющей существенно уменьшить объем памяти, занятый под таблицы страниц, является применение инвертированной таблицы страниц (inverted page table). Этот подход применяется на машинах PowerPC, некоторых рабочих станциях Hewlett-Packard, IBM RT, IBM AS/400 и других.

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

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

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

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

4.2.9 Сегментно-страничное распределение

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

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

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

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

Вопросы

1. На какие виды разделяют запоминающие устройства компьютера?

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

3. В чем заключается особая роль памяти компьютера?

4. Какие функции необходимы ОС для управлению памятью в мультипрограммной системе?

5. Что подразумевается под пространством символьных имен программы?

6. Что подразумевается под виртуальным адресным пространством программы

(процесса)?

7. Какова схема отображения пространства имен на физическую память компьютера?

8. Какие существуют варианты перехода (отображения) пространства символьных

имен на физическую память? В чем суть каждого из вариантов?

9. Какие существуют виды (методы) распределения памяти, характерные для однопрограммных и мультипрограммных ОС?

10. В чем отличие сегмента кода и сегмента данных и как учитывается это отличие при распределении памяти?

11. Каковы особенности организации управления памятью в мультипрограммных ОС?

12. Чем характеризуется распределение памяти фиксированными разделами? Какие задачи при этом решает подсистема управления памятью ОС?

13. Чем характеризуется распределение памяти динамическими разделами? Какие задачи при этом решает подсистема управления памятью ОС?

14. В чем заключается распределение памяти перемещаемыми разделами? В какие моменты в данном случае можно выполнять сжатие памяти?

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

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

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

18. Какие существуют варианты организации и использования таблиц страниц?

19. В чем заключается сегментно-сегментное распределение памяти?