Память и отображения, виртуальное адресное пространство.

Способы отображения основной памяти на кэш

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

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

Для кэшей со случайным отображением используется так называемый ассоциа­тивный поиск, при котором сравнение выполняется не последовательно с каж­дой записью кэша, а параллельно со всеми его записями . Признак, по которому выполняется сравнение, называется тегом (tag). В данном случае те­гом является адрес данных в оперативной памяти. Электронная реализация такой схемы приводит к удорожанию памяти, причем стоимость существенно возрас­тает с увеличением объема запоминающего устройства. Поэтому ассоциативная кэш-память используется в тех случаях, когда для обеспечения высокого про­цента попадания достаточно небольшого объема памяти.

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

Второй, детерминированный способ отображения предполагает, что любой эле­мент основной памяти всегда отображается в одно и то же место кэш-памяти. В этом случае кэш-память разделена на строки, каждая из которых предназначе­на для хранения одной записи об одном элементе данных и имеет свой, номер. Между номерами строк кэш-памяти и адресами оперативной памяти устанавли­вается соответствие «один ко многим»: одному номеру строки соответствует не­сколько (обычно достаточно много) адресов оперативной памяти.

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

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

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

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

Виртуальное адресное пространство

Совокупность виртуальных адресов (ВА) процесса называется виртуальным адресным пространством (ВАП).

Способы организации ВАП:

• плоское (линейная последовательность адресов). Адрес = смещение от начала.
• деление на части (сегменты, страницы). Адрес = n+m, где n – номер сегмента, m – смещение в сегменте. (n, l, m – сегмент, страница, смещение).

Способы преобразования ВА в физические:

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

Второй способ более гибкий, позволяет перемещать программу в памяти.

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

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