Algoritmo de reemplazo de página de reloj: páginas ya existentes

9

Al simular el algoritmo de reemplazo de la página del reloj, cuando aparece una referencia que ya está en la memoria, ¿la manecilla del reloj todavía se incrementa?

Aquí hay un ejemplo:

Con 4 ranuras, usando el algoritmo de reemplazo de la página del reloj

Lista de referencia: 1 2 3 4 1 2 5 1 3 2 4 5

La lista inicial se vería así: 

-> [1][1]
   [2][1]
   [3][1]
   [4][1]

La siguiente referencia para insertar sería 1, luego 2. ¿La mano todavía apuntaría a 1 después de 1 y después de 2? En otras palabras, después de insertar el 5, el reloj se vería así:

-> [5][1]
   [2][0]
   [3][0]
   [4][0]

?

algorithms paging virtual-memory sacrificar
fuente

Respuestas:

9

Creo que este ejemplo puede aclarar todas sus dudas.

Por ejemplo:
Asume que la memoria principal está vacía en la secuencia de referencia de la página de inicio es:
3 2 3 0 8 4 2 5 0 9 8 3 2un bit de referencia por cuadro (llamado el bit "usado")

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


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


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

* = indica el puntero que identifica la siguiente ubicación para escanear 
P = página # almacenada en ese marco 
U = bandera usada, 
0 = no utilizado recientemente 
1 = referenciado recientemente

Esto se llama algoritmo de exploración lineal o algoritmo de segunda oportunidad, utilizado en BSD Linux. 
Generalmente se implementa como una cola circular.
Siva Krishna Aleti
fuente
¿Podría dar una explicación de lo que esto significa, en términos de texto? Es un buen diagrama, pero tales diagramas son inútiles cuando no sabemos lo que significa.
Lagarto discreto
7

Si llega una referencia para una página que ya está en la memoria, el algoritmo de reemplazo no se invoca en absoluto.

El algoritmo de reemplazo de reloj está tratando de lograr algunos de los beneficios del reemplazo de LRU, pero sin la sobrecarga masiva de manipular los bits de LRU en cada golpe de página.

Una página puede estar en uno de tres estados:

  1. Presente en la memoria y el recently-usedbit es true. En este caso, no habrá falla de página cuando ocurra un acceso a la página, por lo que no cambiará ningún bit.
  2. Presente en la memoria pero el recently-usedbit es false. En este caso, la página también está marcada en la tabla de páginas de tal manera que si se accede a la página se producirá un error de página. (Y si la falla de la página ocurre en este caso, lo único que hace el manejador de falla de la página es cambiar el estado a recently-used).
  3. La página no está presente en la memoria. En este caso nos fijamos en el clock-hand. Mientras clock-handapunta a una página con el recently-usedbit establecido true, volteamos el recently-usedbit falsey luego lo incrementamos clock-handpara apuntar a la página siguiente. Cuando encontramos una página que recently-usedya está borrada, esa es la página que reemplazamos. A continuación marcamos la nueva página, recently-usedy el incremento de la clock-handa la próxima página.

El reloj es, en el fondo, un algoritmo probabilístico para aproximar LRU. Si la velocidad a la que se accede a la página es mucho mayor que la velocidad a la clock-handque regresa a la misma página, entonces la página tiene una alta probabilidad de ser marcada recently-used. Si la velocidad a la que se accede a la página es baja en comparación con la velocidad a la clock-handque regresa, entonces es más probable que la página esté en estado no recently-used . La página utilizada más recientemente nunca será reemplazada. (¿Por qué?)

Lógica Errante
fuente