Sistemas operativos modernos

Página 0 2 3 0 0 1 1 1 1 0 0 0 0 2 0 0 0 0 3 0 0 0 0 (a) Página 0 1 2 3 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 (b) Página 0 1 2 3 0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 (c) Página 0 1 2 3 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 (d) Página 0 1 2 3 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 (e) 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 (<) 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 (g) 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 (h) 0 1 0 0 0 0 0 0 1 1 0 1 1 1 0 0 (i) 0 1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 (j) Figura 4-18. LRU utilizando una matriz cuando se hace referencia a páginas en el orden O, 1, 2, 3, 2, 1, O, 3, 2, 3. 4.4.7 Simulación de LRU en software Aunque los dos algoritmos LRU anteriores son factibles en principio, pocas máquinas, sino es que ninguna, tienen este hardware, así que no son de mucha utilidad para el diseñador de sis­ temas operativos que está creando un sistema para una máquina que no cuenta con tal hard­ ware. Se necesita una solución que pueda impiementarse en software. Una posibilidad es el algoritmo de página no usada frecuentemente (NFU; not frequently used). NFU requiere un contador de software asociado con cada página, de valor inicial cero. En cada interrupción de reloj, el sistema operativo explora todas las páginas que están en la memoria. Para cada una, el bit /?, que es Oo 1, se suma a su contador. De hecho, los contadores son un intento por llevar la cuenta de qué tanto se hace referencia a una página. Cuando se presenta un fallo de página, se escoge la página con el contador más bajo para ser reemplazada. El problema principal de NFU es que nunca olvida. Por ejemplo, en un compilador de múl­ tiples pasadas, las páginas que se usaron mucho durante la primera pasada podrían seguir te­ niendo una cuenta alta en las posteriores. De hecho, si la primera pasada es la de mayor tiempo de ejecución de todas, las páginas que contienen el código de pasadas subsiguientes podrían te­ ner siempre cuentas más bajas que las de la primera pasada. Eso haría que el sistema operati­ vo desalojara páginas útiles en vez de páginas que ya no se usan. Por fortuna, una pequeña modificación de NFU le permite simular LRU muy bien. Tal modi­ ficación tiene dos partes. Primero, todos los contadores se desplazan un bit a la derecha antes de sumar el bit R. Luego, el bit R se suma al bit de la extrema izquierda, no al de la derecha. La figura 4-19 ilustra el funcionamiento del algoritmo modificado, llamado envejecimien­ to. Supongamos que después del primer tic del reloj los bits R de las páginas Oa 5 tienen los