Программирование на JAVA

Поэтому, когда требуется освободить место для нового блока, имеет смысл удалить из кэша тот блок, к которому дольше всего не было обращений. Алгоритм работы этого блока называется алгоритмом удаления наи­более давно использовавшихся элементов (Least Recently Used, LRU).

Для использования алгоритма LRU контроллер кэша должен отслеживать об­ращения ко всем блокам кэша. Предположим, что ему нужно следить за обраще­ниями к блоку LRU из четырехблочного множества множественно-ассоциатив­ного кэша. Для каждого блока может использоваться 2-разрядный счетчик. При попадании в кэш счетчик соответствующего блока устанавливается в 0. Счетчи­ки, значения которых были больше значения данного счетчика, увеличиваются на 1. Когда в кэше не оказывается нужного блока, а в множестве еще есть место, счетчик нового блока устанавливается в 0, а значения других счетчиков увеличи­ваются на 1. Если же множество заполнено, блок, счетчик которого равен 3, уда­ляется, а на его место помещается новый блок. Значения остальных трех счетчи­ков увеличиваются на 1. Нетрудно убедиться, что при использовании такого ал­горитма значения счетчиков четырех блоков всегда будут разными.


<< назад вперед >>