Введение

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

Дерево-PLRU

ПЛРУ-дерево — это эффективный алгоритм выбора элемента, к которому, вероятнее всего, не было доступа в последнее время, учитывая набор элементов и последовательность событий доступа к ним. Эта техника используется в кэше процессора Intel 486 и во многих процессорах семейства PowerPC, таких как PowerPC G4 от Freescale, используемый Apple Computer. Алгоритм работает следующим образом: рассмотрим двоичное дерево поиска для рассматриваемых элементов. Каждый узел дерева имеет однобитовый флаг, указывающий направление для вставки псевдо-LRU-элемента: "влево" или "вправо". Для поиска псевдо-LRU-элемента необходимо обойти дерево, следуя значениям флагов. Для обновления дерева при доступе к элементу N, нужно обойти дерево для поиска N и, в процессе обхода, изменить флаги узлов, указав направление, противоположное пройденному. Этот алгоритм может быть неоптимальным, так как является приближенным. Например, на приведенной выше диаграмме с кэш-линиями A, C, B, D, если последовательность доступа была следующей: C, B, D, A, то при вытеснении будет выбран B вместо C. Это происходит потому, что и A, и C находятся в одной половине дерева, и доступ к A направляет алгоритм в другую половину, где отсутствует кэш-линия C.

Битовый PLRU

Бит PLRU хранит один бит состояния для каждой строки кэша. Эти биты называются битами MRU. Каждый доступ к строке устанавливает её бит MRU в 1, указывая на то, что строка была недавно использована. Как только последний оставшийся 0 бит в битах состояния набора устанавливается в 1, все остальные биты сбрасываются в 0. При промахе кэша заменяется самая левая строка, бит MRU которой равен 0.