Hay muchos algoritmos para el reemplazo de páginas, y sin duda algunos estudiantes de doctorado en sistemas están ocupados en este momento soñando con uno nuevo. Estos algoritmos especifican cuáles de las páginas disponibles en la memoria se reutilizan (“reemplazan” con datos nuevos).
LRU significa Menos utilizado recientemente. Siempre que se necesita una nueva página, se elige la página que no ha sido tocada (leída o escrita) por más tiempo. Puede modelar esto como una lista de páginas. Cada vez que se accede a una página y ya está en la lista, se elimina de su posición actual y se coloca al frente de la lista. Cada vez que se necesita una nueva página, se elige la que se encuentra al final de la lista.
FIFO significa primero en entrar, primero en salir. Una vez más, puede ver esto como una lista de páginas, pero la regla es aún más simple: siempre que se necesite una nueva página, tome la que se encuentra al final de la lista (y agregue nuevas páginas al principio de la lista).
- ¿Qué tan importante es el DS y Algo?
- ¿Cuál es la relación entre el análisis probabilístico y el algoritmo aleatorio?
- ¿Cómo visualizo el laberinto que estoy creando?
- He resuelto unos 52 problemas en SPOJ. ¿Debería mudarme a Codeforces ahora?
- Dado que solo quedan 2 meses para las regiones regionales de ACM ICPC, ¿cuántos problemas podría resolver allí si comenzara a practicar ahora, teniendo solo la idea más básica sobre algoritmos?
Un ejemplo de un algoritmo más avanzado es ARC, el caché de reemplazo adaptativo. Es similar a LRU pero tiene dos listas, una para capturar datos a los que se accedió recientemente y una segunda lista para capturar datos a los que se accede con frecuencia.
Los algoritmos de reloj (hay varias variedades) funcionan como LRU, pero en realidad no mantienen una lista. En cambio, solo tienen un bit por página para rastrear si se ha accedido a la página. Un recorrido periódico de todas las páginas (la “manecilla del reloj”) borra el bit. Si el agoritmo visita una página y no se ha accedido a él desde el último iterador (es decir, el bit no está configurado), entonces esa página es candidata para su reemplazo.
