D.5.1.2. Описание алгоритма "псевдо-LRU".

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

 

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

 

Гостевая книга Обсуждение в блоге. Отправить E-mail Автору проекта.

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

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

Hosted by uCoz