I. Пусть имеется 4 строки из некоторого множества. Обозначим их как L0, L1, L2 и L3. В этом множестве имеются три бита LRU, обозначенные как B0, B1 и B2. Кроме того, с каждой строкой связан ее бит достоверности D0, D1, D2 и D3 соответственно для L0 – L3.

II. Начальное состояние (при запрещении кэш-памяти или сбросе процессора):

D0=D1=D2=D3=0.

B0=B1=B2=0,

все строки множества очищены.

III. Начало алгоритма.

1. Пока кэш-память функционирует:
2. Если Dx (x=0,1,2,3) = 0, то замещается строка Lx. Переход к 1.
3. Иначе если все Dx=1, то:
4. Если последнее обращение к строке L0 или L1 (x=0 или x=1), то бит B0 устанавливается в состояние 1 (B0=1), а при обращении к строке L2 или L3 (x=2 или x=3)бит B0 сбрасывается в 0 (B1=0).
5. Если последнее обращение в паре L0-L1 было к строке 0 (x=0), то бит B1 устанавливается в состояние 1 (B1=1), а если к строке L1 (x=1), то бит B1 сбрасывается в 0 (B1=0).
6. Если последнее обращение к паре L2-L3 было в строке L2 (x=2), то бит B2 устанавливается в состояние 1 (B2=1) а при обращении к строке L3 (x=3), бит B2 сбрасывается в 0 (B2=0).
7. Далее выбор заменяемой строки (когда все Dx=1) соответствует таблице D.5.I. Далее переход к пункту 1.
8. Конец алгоритма.

Строки кэш-памяти можно по отдельности объявить недостоверными, задавая операцию недостоверности кэш-памяти на шине процессора. Строка объявляется недостоверной, если:

1. Содержимое кэш-памяти и оперативной памяти не совпадает (см. подраздел D.5.1.1.)
2. Строка с указанным физическим адресом не присутствует в физической памяти.
3. По данному адресу запрещен доступ.

Назад...   К оглавлению раздела   Далее...

=== *** === *** === *** ===

Copyright © Юрий А. Денисов. 2000-2002 г.

В настоящее время проект закрыт (в версии 1.00.3 alpha). Автор приносит извинения за прекрашение разработки.