Czy podczas symulacji algorytmu zastępowania strony zegara, gdy pojawia się odwołanie, które jest już w pamięci, wskazówka zegara wciąż rośnie?
Oto przykład:
Z 4 miejscami, wykorzystując algorytm zastępowania strony zegara
Lista referencyjna: 1 2 3 4 1 2 5 1 3 2 4 5
Początkowa lista wyglądałaby następująco:
-> [1][1]
[2][1]
[3][1]
[4][1]
Następnym odniesieniem do wstawienia byłoby 1, a następnie 2. Czy ręka nadal wskazywałaby 1 po 1, a po 2? Innymi słowy, po wstawieniu 5 zegar wyglądałby tak:
-> [5][1]
[2][0]
[3][0]
[4][0]
?
Jeśli pojawi się odwołanie do strony już znajdującej się w pamięci, algorytm zastępujący w ogóle się nie wywołuje.
Algorytm wymiana zegar stara się osiągnąć niektóre z korzyści płynących z wymiany LRU, ale bez ogromnego narzutu manipulowania bity LRU na każdej stronie przeboju.
Strona może znajdować się w jednym z trzech stanów:
recently-used
bit jesttrue
. W takim przypadku nie wystąpi błąd strony, gdy nastąpi dostęp do strony, więc żadne bity się nie zmienią.recently-used
jestfalse
. W takim przypadku strona jest również oznaczona w tabeli stron w taki sposób, że jeśli strona zostanie otwarta, wystąpi błąd strony. (A jeśli w tym przypadku wystąpi błąd strony, jedyną rzeczą, którą robi moduł obsługi błędów strony, jest zmiana stanu narecently-used
.)clock-hand
. Podczas gdyclock-hand
symbol wskazuje na stronę zrecently-used
ustawionym bitemtrue
, odwracamyrecently-used
bit dofalse
, a następnie zwiększamy,clock-hand
aby wskazywać na następną stronę. Kiedy znajdziemy stronę zrecently-used
już wyczyszczoną, to jest to strona, którą zastępujemy. Następnie zaznaczamy nową stronę jakorecently-used
i przechodzimyclock-hand
do następnej strony.Zegar jest w istocie algorytmem probabilistycznym do przybliżania LRU. Jeśli szybkość uzyskiwania dostępu do strony jest znacznie wyższa niż szybkość
clock-hand
powrotu strony do tej samej strony, istnieje duże prawdopodobieństwo, że strona zostanie oznaczonarecently-used
. Jeśli tempo, w jakim strona jest udostępniana jest niska w porównaniu do szybkości, z jakąclock-hand
wraca dookoła, wówczas strona jest bardziej prawdopodobne, aby być w stanie nierecently-used
. Ostatnio używana strona nigdy nie zostanie zastąpiona. (Dlaczego?)źródło