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

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

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

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

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

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

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

' В действительности запись в кэше обычно содержит несколько элементов данных.

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

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

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

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

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

При выполнении запросов к оперативной памяти до многих вычислительных системах используется двухуровневое кэширование (рис. 5.30). Кэш первого уровня имеет меньший объем и более высокое быстродействие, чем кэш второго уровня. Кэш второго уровня играет роль основной памяти по отношению к кэшу первого уровня.

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

Вопросы для самопроверки

109. На какие классы принято разделять алгоритмы распределения памяти?

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

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

112. Возможна ли организация разделяемой памяти при страничном распределении ОП?

Контрольные вопросы

113. Возможна ли ситуация, когда при динамическом способе распределения памяти ОС не принимает процесс на выполнение?

114. Что такое фрагментация ОП?

115. В чем суть процедуры сжатия ОП?

116. Укажите основной недостаток свопинга.

117. Укажите классы структуризации виртуальной памяти.

118. Чем отличается страничное распределение памяти от свопинга?

119. Какая информация содержится в дескрипторе страницы?

120. В какой информационной структуре хранятся адреса таблицы страниц?

121. Какой критерий используется ОС для определения выгружаемой из ОП страницы?

122. Почему в современных ОС предпочтительно сегментное распределение памяти, а не страничное?

123. Какая характеристика ПК определяет максимально возможный размер виртуального адресного пространства?

124. Если несколько процессов использует один и тот же сегмент памяти (общий), то как поступает ОС в этом случае?

125. Укажите основные недостатки сегментного распределения ОП.

126. В чем отличие сегментного распределения ОП от страничного?

127. Для каких целей ОС использует разделяемые сегменты памяти?