Sistemas operativos modernos

Al presentarse un fallo de página, se examina la página a ia que apunta la manecilla. La acción efectuada depende del bit R: R = 0: Desalojar la página R = 1: Apagar R y adelantar la manecilla Figura 4-17. El algoritmo de reemplazo de páginas tipo reloj. se mucho tiempo. Esta idea sugiere un algoritmo factible: cuando se presente un fallo de página, desalojar la que tiene más tiempo sin usarse. Tal estrategia se denomina paginación de menos re­ cientemente usada (LRU; least recently used). Aunque LRU es factible en teoría, tiene un costo elevado. Para implementarlo cabalmente es preciso mantener una lista enlazada de todas las páginas que están en la memoria, con la que se usó más recientemente al principio y la menos recientemente usada al final. La dificultad ra­ dica en que la lista debe actualizarse cada vez que se hace referencia a la memoria. Hallar una página en la lista, borrarla y reinsertarla al frente es una operación muy tardada, incluso en hardware (suponiendo que pudiera construirse tal hardware). No obstante, hay otras formas de implementar LRU con hardware especial. Consideremos primero el método más sencillo, que requiere equipar el hardware con un contador de 64 bits, C, que se incrementa en forma automática después de cada instrucción. Además, cada entrada de la tabla de páginas debe tener un campo lo bastante grande como para contener al contador. Después de cada referencia a la memoria, el valor actual de C se almacena en la entrada co­ rrespondiente a la página a la que se acaba de hacer referencia. Cuando se presenta un fallo de página, el sistema operativo examina todos los contadores de la tabla de páginas hasta hallar el más bajo. Esa página es la menos recientemente usada. Ahora examinemos un segundo algoritmo LRU en hardware. En una máquina con n mar­ cos de página, el hardware de LRU puede mantener una matriz á c n x n bits, los cuales son ce­ ro al principio. Cada vez que se hace referencia al marco de página k, el hardware enciende primero todos los bits de la fila k y luego apaga todos los bits de la columna k. En cualquier ins­ tante, la fila cuyo valor binario sea el más bajo será la del marco menos recientemente usado, la fila con el siguiente valor más bajo será la del siguiente marco menos recientemente usado, y así en forma sucesiva. El funcionamiento de este algoritmo se ilustra en la figura 4-18 para cua­ tro marcos de página y referencias a páginas en el orden 0 1 2 3 2 1 0 3 2 3 Después de la primera referencia a la página O, tenemos la,situación de la figura 4-18a. Des­ pués de la referencia a la l, tenemos la situación de la figura 4-18b, y así en forma sucesiva.