Алгоритм замены данных в кэш-памяти существенно влияет на ее эффективность. Алгоритм должен, во-первых, быть максимально быстрым, чтобы не замедлять работу кэш-памяти, а во-вторых, обеспечивать максимально возможную вероятность кэш-попаданий. Поскольку из-за непредсказуемости вычислительного процесса ни один алгоритм замещения данных в кэш- памяти не может гарантировать идеальный результат, разработчики ограничиваются рациональными решениями, которые по крайней мере, не сильно замедляют работу кэш. Наличие в ЭВМ двух копий данных - в основной памяти и в кэш -
порождает проблему согласования данных. Если происходит запись в основную память по некоторому адресу, а содержимое этой ячейки находится в кэш, то в результате соответствующая запись в кэш становится недостоверной.
Сквозная запись (write through). При каждом запросе к основной памяти, в том числе и при записи, просматривается кэш. Если строка с запрашиваемым адресом отсутствует в кэш(для этого просматривают поле тегов), то запись выполняется только в основную память. Если же адрес, по которому выполняется обращение, находится и в КЭШе, то запись производится одновременно в кэш и основную память. Такая операция по времени равносильна обращению в основную (оперативную) память и не дает большого выигрыша от применения кэш-памяти.
|
|
Обратная запись (write back). Аналогично, при возникновении запроса к памяти выполняется просмотр кэш, и если строка с запрашиваемым адресом там отсутствует, то запись выполняется только в основную память. В противном же случае запись производится только в кэш-память, при этом в поле управления делается специальная отметка (признак модификации), которая указывает на то, что при вытеснении этих данных из кэш необходимо переписать их в подходящий момент в основную память, чтобы обновить устаревшее содержимое основной памяти. Очевидно, что в этом случае в соответствии с принципами временной и пространственной локальности, обращения будут происходить преимущественно к кэш-памяти, а малая их доля упадёт на основную память. Поэтому временная эффективность метода обратной записи высокая, хотя требует применения более сложных алгоритмов согласования данных. Контроллер кэш-памяти осуществляет копирование модифицированной строки при любых замещениях строки. Модифицированные данные могут выгружаться не только при освобождении места в кэш-памяти для новых данных, но и в «фоновом режиме», то есть в промежутках, когда шинный интерфейс не занят процессором или другими устройствами. В некоторых алгоритмах замещения предусматривается первоочередная выгрузка модифицированных, или, как еще говорят, «грязных» данных.
|
|
Когда кэш-память заполнена, занесение в нее нового блока связано с замещением содержимого одной из строк. При прямом отображении каждому блоку основной памяти соответствует только одна определенная строка в кэш-памяти, и никакой иной выбор удаляемой строки здесь невозможен. При полностью и частично ассоциативных способах отображения требуется какой-либо алгоритм замещения (выбора удаляемой из кэш-памяти строки). Основная цель стратегии замещения — удерживать в кэш-памяти строки, к которым наиболее вероятны обращения в ближайшем будущем, и заменять строки, доступ к которым произойдет в более отдаленном времени или вообще не случится. Очевидно, что оптимальным будет алгоритм, который замещает ту строку, обращение к которой в будущем произойдет позже, чем к любой другой строке кэша. К сожалению, такое предсказание практически нереализуемо, и приходится использовать алгоритмы, уступающие оптимальному. Существует множество алгоритмов замещения, которые кратко рассмотрены ниже:
Наиболее эффективным является алгоритм замещения на основе наиболее давнего использования (LRU — Least Recently Used), при котором замещается та строка кэш-памяти, к которой дольше всего не было обращения. Общая реализация производит отслеживание наименее использованной строки. Этот алгоритм реализуется путем добавления дополнительных бит «возраста», а отслеживание сделано при помощи сравнения этих бит.
Алгоритм замещения на основе наименее давнего использования (MRU - Most Recently Used), в отличие от LRU, в первую очередь вытесняется последний использованный элемент. Для схем случайного доступа и циклического сканирования больших наборов данных (схемы циклического доступа), алгоритмы кэширования MRU – имеют больше попаданий по сравнению с LRU за счет из стремления к сохранению старых данных. Алгоритмы MRU наиболее полезны в случаях, когда чем старше элемент, тем больше обращений к нему происходит. [20]
Сегментированный LRU (SLRU – Segmented LRU) – SLRU кэш состоит из двух секций: пробной и защищенной. Пробная секция реализована по алгоритму LRU, защищенная - по алгоритму MRU. При промахе, данные сначала поступают в пробную секцию. Из этой секции, в результате редкого использования данные попадают в защищенную секцию. Такой перенос строки из пробного сегмента в защищенный сегмент может вызвать перенос последней использованной (LRU) строки в защищенном сегменте в MRU-область пробного сегмента, давая этой линии второй шанс быть использованной перед вытеснением.
Кэш прямого отображения (Direct-mapped cache) используется для высокоскоростных кэшей процессора, где не хватает быстродействия 2-канального ассоциативного кэширования. Адрес нового элемента используется для вычисления местонахождения в кэше (в отведенной для этого области). Все, что было ранее, — вытесняется.
Другой возможный алгоритм замещения-алгоритм, работающий по принципу «первый вошел-первый вышел»(FIFO-First In-First Out). Здесь заменяется строка, дольше всего находившаяся в кэш-памяти.
Виртуальная (от virtual - "кажущийся") память (ВП) - это система организации памяти, при которой процессору (программе) предоставляется адресное пространство, превышающее физическое адресное пространство ОЗУ системы за счет внешней памяти. Задачей построения ВП является сведение к минимуму потерь производительности при вынужденном обращении к внешней памяти. ВП может быть организована программно, программно - аппаратно и аппаратно. Как правило, в современных ВС программно-аппаратная организация ВП заключается в использовании операционной системой аппаратной поддержки ВП, заложенной в процессорах общего назначения.
ВП может иметь страничную, сегментную или странично–сегментную организацию. При страничной организации память представляется совокупностью страниц фиксированной длины (2-16 Кбайт). При сегментной организации память представляет собой набор сегментов, то есть логически связанных блоков памяти различного размера.
|
|
Методы распределения памяти не требуют непрерывных областей пространства для размещения задачи, но они требуют для реализации соответствующей аппаратной поддержки в виде относительной адресации. При такой адресации адрес программы состоит из двух частей – базового адреса (фактический адрес начала размещения программы в памяти) и смещения (множества адресов ячеек программы, отсчитываемого от базового адреса).