Every people has right on left  
Chia ulo havas rajton sur levo  

Каждый человек имеет право на лево  
(Н. Фоменко)  

CopyLeft (L) Юрий А. Денисов  
(yudenisov)  
Все права защищены  

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. По данному адресу запрещен доступ.

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