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

При адресации с помощью страничной организации возможно, что логический адрес сформирован неверно, и его номер страницы выходит за пределы логической памяти процесса. Защита от неверной адресации может быть реализована хранением и проверкой дополнительного бита 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) [24 (не найдено)] - целочисленной функции 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. Инвертированные таблицы страниц.