Операционные системы. Теория и практика. Замятин А.В. - 115 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

115
Такая сравнительно высокая производительность современных ОС
показывает эффективность использования ассоциативной памяти. Высо-
кое значение вероятности нахождения данных в ассоциативной памяти
связано с наличием у данных таких объективных свойств как простран-
ственная и временная локальность.
Следует обратить внимание на то, что при переключении контекста
процессов нужно добиться того, чтобы новый процесс «не видел» в ас-
социативной памяти информацию, относящуюся к предыдущему про-
цессу, поэтому требуется ее «очистка». Очевидно, что это ведет к
дополнительным затратам на переключения контекста процесса при ис-
пользовании ассоциативной памяти.
Инвертированная таблица страниц. Несмотря на многоуровне-
вую организацию, хранение нескольких таблиц страниц большого раз-
мера по-прежнему представляют собой проблему. Особенно это акту-
ально для 64-разрядных архитектур, где число виртуальных страниц
очень велико. Одним из вариантов решения этой проблемы, позволяю-
щей существенно уменьшить объем памяти, занятый под таблицы стра-
ниц, является применение инвертированной таблицы страниц (inverted
page table). Этот подход применяется на машинах PowerPC, некоторых
рабочих станциях Hewlett-Packard, IBM RT, IBM AS/400 и других.
В этой таблице содержится по одной записи на каждый страничный
кадр физической памяти. Достаточно одной таблицы для всех процес-
сов. Для хранения функции отображения требуется фиксированная
часть основной памяти, независимо от разрядности архитектуры, разме-
ра и количества процессов. Например, для компьютера Pentium c 256
Мбайт оперативной памяти нужна таблица размером 64 Кбайт строк.
Несмотря на экономию ОП, применение инвертированной таблицы
имеет существенный минус – записи в ней (как и в ассоциативной памя-
ти) не отсортированы по возрастанию номеров виртуальных страниц,
что усложняет трансляцию адреса. Один из способов решения данной
проблемы – использование хеш-таблицы
12
виртуальных адресов. Часть
виртуального адреса, представляющая собой номер страницы, отобра-
жается в хеш-таблицу с использованием функции хеширования
13
. Каж-
дой странице физической памяти здесь соответствует одна запись в хеш-
таблице и инвертированной таблице страниц. Виртуальные адреса,
имеющие одно значение хеш-функции, сцепляются друг с другом, при
этом длина цепочки обычно не превышает двух записей.
12
Хеш-таблица – структура данных вида ассоциативный массив, которая ассоциирует ключи со зна-
чениями. При этом хэш – число фиксированной длины, которое ставится в соответствие данным про-
извольной длины таким образом, чтобы вероятность появления различных данных с одинаковым хе-
шем стремилась к нулю, а восстановить данные по их хешу было крайне трудно.
13
Хеш-функция – функция, выполняющая одностороннее преобразование (хеширование) входных
данных.

Страницы