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

9

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]

?

ubić
źródło

Odpowiedzi:

9

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.
Siva Krishna Aleti
źródło
Czy możesz wyjaśnić, co to znaczy, pod względem tekstu? To fajny schemat, ale takie diagramy są bezużyteczne, gdy nie wiemy, co to znaczy.
Dyskretna jaszczurka
7

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?)

Wędrująca logika
źródło