Algorytm zastępowania stron zegara - już istniejące strony

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]

?

Myślę, że ten przykład może wyjaśnić wszystkie twoje wątpliwości.

Na przykład:
Zakłada się, że pamięć główna jest pusta w sekwencji odniesienia strony początkowej:
3 2 3 0 8 4 2 5 0 9 8 3 2jeden bit odniesienia na ramkę (zwany bitem „używanym”)

  PU 3 PU 2 PU 3 PU 0 PU 8 PU 4
+ --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- +
| | 0 | * | 3 | 1 | | 3 | 1 | | 3 | 1 | | 3 | 1 | | 3 | 1 |
+ --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- +
| | 0 | | | 0 | * | 2 | 1 | | 2 | 1 | | 2 | 1 | | 2 | 1 |
+ --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- +
| | 0 | | | 0 | | | 0 | * | | 0 | * | 0 | 1 | | 0 | 1 |
+ --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- +
| | 0 | | | 0 | | | 0 | | | 0 | | | 0 | * | 8 | 1 |
+ --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- +
| | 0 | | | 0 | | | 0 | | | 0 | | | 0 | | | 0 | *
+ --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + ----  


  PU 2 PU 5 PU 0 PU 9 PU 8 PU 3
+ --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- +
| 3 | 1 | * | 3 | 1 | * | 5 | 1 | | 5 | 1 | | 5 | 1 | | 5 | 1 |
+ --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- +
| 2 | 1 | | 2 | 1 | | 2 | 0 | * | 2 | 0 | * | 9 | 1 | | 9 | 1 |
+ --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- +
| 0 | 1 | | 0 | 1 | | 0 | 0 | | 0 | 1 | | 0 | 1 | * | 0 | 1 | *
+ --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- +
| 8 | 1 | | 8 | 1 | | 8 | 0 | | 8 | 0 | | 8 | 0 | | 8 | 1 |
+ --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- +
| 4 | 1 | | 4 | 1 | | 4 | 0 | | 4 | 0 | | 4 | 0 | | 4 | 0 |
+ --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + --- + + --- + ----  


  PU 2 PU   
+ --- + --- + + --- + --- + 
| 5 | 1 | * | 5 | 0 |
+ --- + --- + + --- + --- + 
| 9 | 1 | | 9 | 0 |
+ --- + --- + + --- + --- +
| 0 | 0 | | 2 | 1 |   
+ --- + --- + + --- + --- +  
| 8 | 0 | | 8 | 0 | *
+ --- + --- + + --- + --- + 
| 3 | 1 | | 3 | 1 |  
+ --- + --- + + --- + --- +  

* = wskazuje wskaźnik wskazujący kolejną lokalizację do skanowania 
P = strona # zapisana w tej ramce 
U = używana flaga, 
0 = ostatnio nie używane 
1 = ostatnio odwołany

Nazywa się to algorytmem skanowania liniowego lub algorytmem drugiej szansy, stosowanym w BSD Linux. 
Zasadniczo jest implementowany jako kolejka cykliczna.

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:

1. Obecny w pamięci, a recently-usedbit jest true. W takim przypadku nie wystąpi błąd strony, gdy nastąpi dostęp do strony, więc żadne bity się nie zmienią.
2. Obecny w pamięci, ale tak recently-usedjest false. 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 na recently-used.)
3. Strona nie jest obecna w pamięci. W tym przypadku patrzymy na clock-hand. Podczas gdy clock-handsymbol wskazuje na stronę z recently-usedustawionym bitem true, odwracamy recently-usedbit do false, a następnie zwiększamy, clock-handaby wskazywać na następną stronę. Kiedy znajdziemy stronę z recently-usedjuż wyczyszczoną, to jest to strona, którą zastępujemy. Następnie zaznaczamy nową stronę jako recently-usedi przechodzimy clock-handdo 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-handpowrotu strony do tej samej strony, istnieje duże prawdopodobieństwo, że strona zostanie oznaczona recently-used. Jeśli tempo, w jakim strona jest udostępniana jest niska w porównaniu do szybkości, z jaką clock-handwraca dookoła, wówczas strona jest bardziej prawdopodobne, aby być w stanie nie recently-used . Ostatnio używana strona nigdy nie zostanie zastąpiona. (Dlaczego?)