Выбор блока кэш-памяти для замещения

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

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

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

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

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

Достоинство случайного способа заключается в том, что его проще реализовать в аппаратуре. Когда количество блоков для поддержания трассы увеличивается, алгоритм LRU становится все более дорогим и часто только приближенным.

Эффективности случайной и LRU стратегий отличаются незначительно. При разработке кэш-памяти, как правило, предпочтение отдается более простой стратегии LRU.