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