При прямом отображении каждом блоку ОП соответствует определённая строка КЭШа, и никакой выбор здесь невозможен. Для полностью ассоциативной КЭШ-памяти ситуация иная.
Основная цель стратегии замещения – удержание в КЭШ строки, к которым наиболее вероятны обращения в дальнейшем будущемь и заменять строки, доступ к которым произойдёт в отдалённым будущем либо вообще не случится.
Наиболее эффективный алгоритм – LRU (Least Recently Used) – замещается строка КЭШ, к которой дольше всего не было обращений.
При обращении к строке счётчик обнуляется.
Вариант без счётчика: реализуется очередь, куда в порядке заполнения КЭШ заносятся ссылки на эти строки; при каждом обращении ссылка помещается в конец очереди, т.о. первая в очереди – ссылка на стройку, к которой дольше всего не было обращений.
Алгоритм FIFO.
Алгоритм LFU (Least Frequency Used) – меньше всего обращений
Random – произвольный выбор строки для замены.