Algoritmos De Sustitucion De Paginas

Algoritmos De Sustitucion De Paginas

ALGORITMOS DE SUSTITUCIÓN DE PÁGINAS

Cuando ocurre una falla de página, el sistema operativo tiene que escoger la página que sacará de la memoria para que pueda entrar la nueva página. Si la página que se eliminará fue modificada mientras estaba en la memoria, se debe reescribir en el disco a fin de actualizar la copia del disco, pero si no fue así (p. ej., si la página contenía texto de programa), la copia en disco ya estará actualizada y no será necesario reescribirla. La nueva página simplemente sobreescribe la que está siendo desalojada.

Si bien sería posible escoger una página al azar para ser desalojada cuando ocurre una falla de página, el rendimiento del sistema es mucho mejor si se escoge una página que no se usa mucho. Si se elimina una página de mucho uso, probablemente tendrá que traerse pronto a la memoria otra vez, aumentando el gasto extra. Se ha trabajado mucho sobre el tema de los algoritmos de reemplazo de páginas, tanto teórica como experimentalmente. A continuación describimos algunos de los algoritmos más importantes.

El algoritmo de sustitución de páginas óptimo

El mejor algoritmo de reemplazo de páginas posible es fácil de describir pero imposible de implementar. En el momento en que ocurre una falla de páginas, algún conjunto de páginas está en la memoria. A una de estas páginas se hará referencia en la siguiente instrucción (la página que contiene esa instrucción). Otras páginas podrían no necesitarse sino hasta 10, 100 o tal vez 1000 instrucciones después. Cada página puede rotularse con el número de instrucciones que se ejecutarán antes de que se haga referencia a esa página.

El algoritmo de reemplazo de páginas óptimo simplemente dice que se debe eliminar la página que tenga el rótulo más alto. Si una página no se va a usar sino hasta después de 8 millones de instrucciones y otra página no se usará sino hasta después de 6 millones de instrucciones, el desalojo de la primera postergará la falla de página que la traerá de nuevo a la memoria lo más lejos hacia el futuro que es posible. Las computadoras, al igual que las personas, tratan de aplazar los sucesos desagradables el mayor tiempo que se puede.

El único problema con este algoritmo es que no se puede poner en práctica. En el momento en que ocurre la falla de página, el sistema operativo no tiene manera de saber cuándo se hará referencia a cada una de las páginas. (Vimos una situación similar antes con el algoritmo de planificación del primer trabajo más corto; ¿cómo puede el sistema saber cuál trabajo es el más corto?) No obstante, si se ejecuta un programa en un simulador y se toma nota de todas las referencias a páginas, es posible implementar el reemplazo de páginas óptimo en la segunda ejecución utilizando la información recabada durante la primera.

De este modo, es posible comparar el rendimiento de los algoritmos realizables con el mejor posible. Si un sistema operativo logra un rendimiento, digamos, sólo 1 % peor que el algoritmo óptimo, los esfuerzos dedicados a buscar un mejor algoritmo redundarán cuando más en una mejora del 1%. Para evitar confusiones, debemos dejar sentado que esta bitácora de referencias a páginas sólo es válido para el programa que acaba de medirse. El algoritmo de reemplazo de páginas derivado de él es específico para ése y sólo ese programa. Aunque este método es útil para evaluar los algoritmos de reemplazo de páginas, no sirve de nada en los sistemas prácticos. A continuación estudiaremos algoritmos que sí son útiles en los sistemas reales.

El algoritmo de sustitución de páginas no usadas recientemente

Para que el sistema operativo pueda recabar datos estadísticos útiles sobre cuáles páginas se están usando y cuáles no, la mayor parte de las computadoras con memoria virtual tienen dos bits de situación asociados a cada página. R se enciende cada vez que se hace referencia a la página (lectura o escritura). M se enciende cuando se escribe la página (es decir, se modifica). Los bits están contenidos en cada entrada de la tabla de páginas, como se muestra en la Fig. 4–11. Es importante darse cuenta de que estos bits se deben actualizar en cada referencia a la memoria, así que es vital que sea el hardware quien los ajuste. Una vez puesto en 1 un bit, seguirá siendo 1 hasta que el sistema operativo lo ponga en O en software. Si el hardware no tiene estos bits, pueden simularse como sigue. Cuando se inicia un proceso, todas sus entradas de la tabla de páginas se marcan como que no están en la memoria. Tan pronto como se haga referencia a cualquier página, ocurrirá una falla de página. Entonces, el sistema operativo enciende el bit R (en sus tablas internas), modifica la entrada de la tabla de páginas de modo que apunte a la página correcta, con el modo SÓLO LECTURA, y reinicia la instrucción. Si subsecuentemente se escribe en la página, ocurrirá otra falla de página, lo que permitirá el sistema operativo encender el bit M y cambiar el modo de la página a LECTURA/ESCRITURA.

Los bits R y M pueden servir para construir un algoritmo de paginación sencillo como sigue Cuando se inicia un proceso, el sistema operativo pone en O los dos bits de todas sus páginas Periódicamente (p. ej., en cada interrupción de reloj), se apaga el bit R, a fin de distinguir páginas a las que no se ha hecho referencia recientemente de las que sí se han leído.

Cuando ocurre una falla de página, el sistema operativo examina todas las páginas y las divide en cuatro categorías con base en los valores actuales de sus bits R y M:

Clase 0: no referida, no modificada.

Clase 1: no referida, modificada.

Clase 2: referida, no modificada.

Clase 3: referida, modificada.

Aunque a primera vista las páginas de clase 1 parecen imposibles, ocurren cuando una interrupción del reloj apaga el bit R de una página de clase 3. Las interrupciones de reloj no borran el bit M esta información se necesita para determinar si hay que reescribir en disco la página o no.

El algoritmo NRU (no utilizada recientemente) elimina una página al azar de la clase no vacía que tiene el número más bajo. Este algoritmo supone que es mejor eliminar una página modificada a la que no se ha hecho referencia en por lo menos un tic del reloj (por lo regular 20 ms) que una página limpia que no se está usando mucho. El atractivo principal de NRU es que es fácil de entender, eficiente de implementar y tiene un rendimiento que, si bien ciertamente no es óptimo, a menudo es adecuado.

El algoritmo de sustitución de páginas de primera que entra, primera que sale (FIFO) Otro algoritmo de paginación con bajo gasto extra es el algoritmo FIFO (primera que entra, primera que sale). Para ilustrar su funcionamiento, consideremos un supermercado que tiene suficientes anaqueles para exhibir exactamente k productos distintos. Un día, alguna compañía introduce un nuevo alimento: yogurt orgánico liofilizado instantáneo que puede reconstituirse en un homo de microondas. Su éxito es inmediato, así que nuestro supermercado finito tiene que deshacerse de un producto viejo para poder tener el nuevo en exhibición.

Una posibilidad consiste en encontrar el producto que el supermercado ha tenido en exhibición durante más tiempo (es decir, algo que comenzó a vender hace 120 años) y deshacerse de él bajo el supuesto de que a nadie le interesa ya. En efecto, el supermercado mantiene una lista enlazada de todos los productos que vende en el orden en que se introdujeron. El nuevo se coloca al final de la lista; el que está a la cabeza de la lista se elimina.

Como algoritmo de reemplazo de páginas, puede aplicarse la misma idea. El sistema operativo mantiene una lista de todas las páginas que están en la memoria, siendo la página que está a la cabeza de la lista la más vieja, y la del final, la más reciente. Cuando hay una falla de página, se elimina la página que está a la cabeza de la lista y se agrega la nueva página al final. Cuando FIFO se aplica a una tienda, el producto eliminado podría ser cera para el bigote, pero también podría ser harina, sal o mantequilla. Cuando FIFO se aplica a computadoras, surge el mismo problema. Por esta razón, casi nunca se usa FIFO en su forma pura.

El algoritmo de sustitución de páginas de segunda oportunidad

Una modificación sencilla de FIFO que evita el problema de desalojar una página muy utilizada consiste en inspeccionar el bit R de la página más vieja. Si es O, sabremos que la página, además de ser vieja, no ha sido utilizada recientemente, así que la reemplazamos de inmediato. Si el bit R es 1, se apaga el bit, se coloca la página al final de la lista de páginas, y se actualiza su tiempo de carga como si acabara de ser traída a la memoria. Luego continúa la búsqueda.

El funcionamiento de este algoritmo, llamado de segunda oportunidad, se muestra en la Fig. 4- 13. En la Fig. 4–13(a) vemos que se mantienen las páginas de la A a la H en una lista enlazada ordenadas según el momento en que se trajeron a la memoria.

Supongamos que ocurre una falla de página en el tiempo 20. La página más antigua es A, que legó en el tiempo O, cuando se inició el proceso. Si A tiene el bit R apagado, es desalojada de la memoria, ya sea escribiéndose en el disco (si está sucia) o simplemente abandonándose (si está limpia). En cambio,

334 ADMINISTRACIÓN DE MEMORIA CAP. 4

si el bit R está encendido, A se coloca al final de la lista y su “tiempo de carga” se ajusta al tiempo actual (20). También se apaga su bit R. La búsqueda de una página apropiada continúa con B. Lo que hace el algoritmo de segunda oportunidad es buscar una página vieja a la que no se, haya hecho referencia en el intervalo de reloj anterior. Si se ha hecho referencia a todas las páginas, este algoritmo pasa a ser FIFO puro. Específicamente, imaginemos que todas las páginas de la Fig. 4–13(a) tienen su bit R encendido. Una por una, el sistema operativo pasará’ páginas al final de la lista, apagando el bit R cada vez que anexa una página al final de la lista. Tarde o temprano, regresará a la página A, que ahora tiene su bit R apagado. En este punto, A será desalojada. Así, el algoritmo siempre termina.

El algoritmo de sustitución de páginas por reloj

Aunque el algoritmo de segunda oportunidad es razonable, es innecesariamente eficiente porque constantemente cambia de lugar páginas dentro de su lista. Un enfoque mejor consiste en mantener todas las páginas en una lista circular con forma de reloj, como se muestra en la Fig. 4–14. Una manecilla apunta a la página más vieja.

Cuando ocurre una falla de página, se inspecciona la página a la que apunta la manecilla. Si su bit R es O, se desaloja la página, se inserta la nueva página en el reloj en su lugar, y la manecilla avanza una posición. Si R es 1, se pone en O y la manecilla se avanza a la siguiente página. Este proceso se repite hasta encontrar una página con R = 0. No resulta sorprendente que este algoritmo se llame de reloj. La única diferencia respecto al de segunda oportunidad es la implementación.

4.4.6 El algoritmo de sustitución de páginas menos recientemente usadas (LRU) Una buena aproximación al algoritmo óptimo se basa en la observación de que las páginas que han usado mucho en las últimas instrucciones probablemente se usarán mucho en las siguientes. Por otro lado, las páginas que hace mucho no se usan probablemente seguirán sin usarse durante largo tiempo. Esta idea sugiere un algoritmo factible: cuando ocurra una falla de página, se desalojará la página que haya estado más tiempo sin usarse. Esta estrategia se denomina paginación LRN (menos recientemente utilizada). Aunque LRU es factible en teoría, no es barato. Si queremos implementar LRU plenamente, necesitamos mantener una lista enlazada de todas las páginas que están en la memoria, con la página más recientemente utilizada al frente y la menos recientemente utilizada al final. El problema es que hay que actualizar la lista en cada referencia a la memoria. Encontrar una página en la lista, eliminarla y luego pasarla al frente es una operación que consume mucho tiempo, incluso en hardware (suponiendo que pudiera construirse tal hardware). Sin embargo, hay otras formas de implementar LRU con hardware especial. Consideremos primero la forma más sencilla. Este método requiere equipar el hardware con un contador de 64 bits, C, que se incrementa automáticamente después de cada instrucción. Además, cada entrada de la tabla de páginas debe tener un campo con el tamaño suficiente para contener el contador. Después de cada referencia a la memoria, el valor actual de C se almacena en la entrada correspondiente a la página a la que se acaba de hacer referencia. Cuando ocurre una falla de página, el sistema operativo examina todos los contadores de la tabla de páginas hasta encontrar el más bajo. Esa página es la menos recientemente utilizada. Examinemos ahora un segundo algoritmo LRU en hardware. Para una máquina con n marcos de página, el hardware de LRU puede mantener una matriz de n x n bits, que inicialmente son cero. Cada vez que se hace referencia al marco de página k, el hardware pone primero en 1 todos los bits de la fila k, y luego pone en O todos los bits de la columna k. En un instante dado, la fila cuyo valor binario sea el más bajo, será la de la página menos recientemente utilizada; la fila cuyo valor sea el siguiente más bajo será la de la siguiente página menos recientemente utilizada, etc. El funcionamiento de este algoritmo se muestra en la Fig. 4–15 para cuatro marcos de página y referencias a páginas en el orden 0123210323 Después de que se hace referencia a la página O tenemos la situación de la Fig. 4–15(a), y así sucesivamente.

Simulación de LRU en software Aunque los dos algoritmos LRU anteriores son factibles en principio, pocas máquinas, y tal ninguna, cuentan con este hardware, así que no sirven de mucho al diseñador de sistemas operad que está creando un sistema para una máquina que no tiene este hardware. Se necesita solución que pueda implementarse en software. Una posibilidad es el algoritmo NFU (no utiliza frecuentemente), el cual requiere un contador en software asociado a cada página y que inicialmente vale 0. En cada interrupción del reloj, el sistema operativo examina todas las páginas que estañe memoria. Para cada página, el bit R, que es O o 1, se suma al contador. En efecto, los contados son un intento por contabilizar la frecuencia con que se hace referencia a cada página. Cuando ocurre una falla de página, se escoge para reemplazar la página que tiene el contador más bajo. El problema con NFU es que nunca olvida nada. Por ejemplo, en un compilador de múltiples pasadas, las páginas que se usaron mucho durante la pasada 1 podrían tener todavía una cuenta alta durante varias pasadas posteriores. De hecho, si sucede que la pasada 1 tiene el tiempo ejecución más largo de todas, las páginas que contienen el código de pasadas subsecuentes podrían tener siempre cuentas más bajas que las de la primera pasada. Por tanto, el sistema operativo desalojará páginas útiles en lugar de páginas que ya no se están usando. Por fortuna, una pequeña modificación de NFU hace que pueda simular LRU de forma satisfactoria. La modificación tiene dos partes. Primera, todos los contadores se desplazan a la derecha un bit antes de sumarles el bit R. Segunda, el bit R se suma al bit de la extrema izquierda al de la extrema derecha. En la Fig. 4–16 se ilustra el funcionamiento del algoritmo modificado, llamado de maduración. Supongamos que después del primer tic del reloj los bits R de las páginas O a 5 tienen los

valores 1, O, 1, O, 1 y 1 respectivamente (la página O es 1, la página 1 es O, la página 2 es 1, etc.). Dicho de otro modo, entre el tic O y el tic 1 se hizo referencia a las páginas 0,2,4 y 5, así que sus bits R se pusieron en 1, mientras que los demás siguieron en 0. Después de que los seis contadores correspondientes se desplazan a la derecha y se les inserta el bit R por la izquierda,. Las cuatro columnas restantes muestran los seis contadores después de los siguientes cuatro tics del reloj. Cuando ocurre una falla de página, se elimina la página con el contador más bajo. Es evidente que una página a la que no se ha hecho referencia durante, digamos, cuatro tics del reloj tiene cuatro ceros a la izquierda en su contador, y por tanto tiene un valor más bajo que el contador de una página a la que no se ha hecho referencia durante tres tics del reloj. Este algoritmo difiere de LRU en dos aspectos. Consideremos las páginas 3 y 5 en la Fig. 4–16(e). A ninguna de las dos se ha hecho referencia durante dos tics del reloj; a las dos se hizo referencia en el tic anterior. Según LRU, si es preciso reemplazar una página, deberíamos escoger una de estas dos. El problema es que no sabemos cuál de ellas es a la que se hizo referencia por última vez en el intervalo entre el tic 1 y el 2. Al registrar sólo un bit por intervalo de tiempo, hemos perdido la capacidad para distinguir entre las referencias al principio del intervalo de reloj y aquellas que ocurren posteriormente. Lo único que podemos hacer es eliminar la página 3, porque la página 5 también tuvo una referencia dos tics antes, y la página 3 no. La segunda diferencia entre LRU y maduración es que en esta última los contadores tienen un número finito de bits, ocho en nuestro ejemplo. Supongamos que dos páginas tienen un valor de cero en el contador. Lo único que podemos hacer es escoger una de ellas al azar. En realidad, bien puede ser que a una de ellas se haya hecho referencia por última vez hace nueve tics y que otra se haya hecho referencia por última vez hace 1000 tics. No tenemos forma de saber esto no obstante, en la práctica generalmente bastan ocho bits si un tic de reloj tiene alrededor de 20 Si no se ha hecho referencia a una página en 160 ms, probablemente no es muy importante.

ITSAO


Mis sitios nuevos:
Emprendedores
Politica de Privacidad