Sistemas operativos modernos

Primera página que se cargó 0 3 7 8 12 14 15 18 A B C D E F G H (a) 3 7 8 12 14 15 18 20 B C D E F Q H A Página cargada más recientemente A se trata como página recién cargada (b) Figura 4-16. Operación del algoritmo de segunda oportunidad, a) Páginas en orden FIFO. b) Lista de páginas si hay un fallo de página en el tiempo 20 y el bit R de la página A está encendido. Los números arriba de las páginas son sus horas de carga. pia). Pero si el bit R está encendido, A se coloca al final de la lista y su “hora de carga” se cam­ bia al tiempo actual (20). También se apaga el bit R. La búsqueda de una página apropiada con­ tinúa con B. Lo que este algoritmo está haciendo es buscar una página antigua a la que no se haya he­ cho referencia durante el intervalo de reloj anterior. Si se ha hecho referencia a todas las pági­ nas, el algoritmo de segunda oportunidad degenera en FIFO puro. De manera específica, imaginemos que los bits R de todas las páginas de la figura 4-16 están encendidos. El sistema operativo pasa las páginas una por una al final de la lista, apagando el bit R cada vez que ane­ xa una página al final. Por último, el sistema volverá a examinar la página A, que ahora tiene su bit R apagado. En ese momento, se desalojará A. Así, el algoritmo siempre termina. 4.4.5 El algoritmo de reemplazo de páginas tipo reloj Aunque el algoritmo de segunda oportunidad es razonable, es menos eficiente de lo que debe­ ría porque en forma continua cambia páginas de lugar dentro de su lista. Una mejor estrategia sería mantener todas las páginas en una lista circular parecida a un reloj, como se muestra en la figura 4-17. Una manecilla apunta a la página más anügua. Cuando se presenta un fallo de página, se examina la página a la que apunta la manecilla. Si su bit R es O, dicha se desaloja, la nueva se inserta en su lugar y la manecilla se adelanta una po­ sición. Si R es 1, se cambia a Oy la manecilla se adelanta a la siguiente página. Este proceso se repite hasta hallar una página con /? = 0. No es sorpresa que a este algoritmo se le llame reloj. La única diferencia respecto al de segunda oportunidad radica en la implementación. 4.4.6 El algoritmo de reemplazo de página menos recientemente usada Una buena aproximación al algoritmo óptimo se basa en la observación de que es probable que las páginas que se han usado mucho en las últimas instrucciones se usarán mucho otra vez en las siguientes. En cambio, es probable que las páginas que no se han usado en años seguirán sin usar-