Buscar este blog

martes, 18 de enero de 2011

4.1GESTIÓN DE MEMORIA
La memoria es uno de los principales recursos de la computadora, la cual debe de administrarse con mucho cuidado. Aunque actualmente la mayoría de los sistemas de cómputo cuentan con una alta capacidad de memoria, de igual manera las aplicaciones actuales tienen también altos requerimientos de memoria, lo que sigue generando escasez de memoria en los sistemas multitarea y/o multiusuario.
La parte del sistema operativo que administra la memoria se llama administrador de memoria y su labor consiste en llevar un registro de las partes de memoria que se estén utilizando y aquellas que no, con el fin de asignar espacio en memoria a los procesos cuando éstos la necesiten y liberándola cuando terminen, así como administrar el intercambio entre la memoria principal y el disco en los casos en los que la memoria principal no le pueda dar capacidad a todos los procesos que tienen necesidad de ella.
Memoria real
La memoria real o principal es en donde son ejecutados los programas y procesos de una computadora y es el espacio real que existe en memoria para que se ejecuten los procesos. Por lo general esta memoria es de mayor costo que la memoria secundaria, pero el acceso a la información contenida en ella es de más rápido acceso. Solo la memoria cachees más rápida que la principal, pero su costo es a su vez mayor.
Memoria virtual
El término memoria virtual se asocia a dos conceptos que normalmente a parecen unidos:
1.    El uso de almacenamiento secundario para ofrecer al conjunto de las aplicaciones la ilusión de tener más memoria RAM de la que realmente hay en el sistema. Esta ilusión de existe tanto a nivel del sistema, es decir, teniendo en ejecución mas aplicaciones de las que realmente caben en la memoria principal, sin que por ello cada aplicación individual pueda usar mas memoria de la que realmente hay o incluso de forma mas general, ofreciendo a cada aplicación mas memoria de la que existe físicamente en la maquina.
2.    Ofrecer a las aplicaciones la ilusión de que están solas en el sistema, y que por lo tanto, pueden usar el espacio de direcciones completo. Esta técnica facilita enormemente la generación de código, puesto que el compilador no tiene porque preocuparse sobre dónde residirá la aplicación cuando se ejecute.
Espacio De Direcciones
Los espacios de direcciones involucrados en el manejo de la memoria son de tres tipos:
·         Direcciones físicas: son aquellas que referencian alguna posición en la memoria física.
·         Direcciones lógicas: son las direcciones utilizadas por los procesos. Sufren una serie de transformaciones, realizadas por el procesador (la MMU), antes de convertirse en direcciones físicas.
·         Direcciones lineales: direcciones lineales se obtienen a partir de direcciones lógicas tras haber aplicado una transformación dependiente de la arquitectura.
Los programas de usuario siempre tratan con direcciones virtuales; nunca ven las direcciones físicas reales.
Unidad De Manejo De Memoria
La unidad de manejo de memoria (MMU) es parte del procesador. Sus funciones son:
·         Convertir las direcciones lógicas emitidas por los procesos en direcciones físicas.
·         Comprobar que la conversión se puede realizar. La dirección lógica podría no tener un dirección física asociada. Por ejemplo, la página correspondiente a una dirección se puede haber trasladado a una zona de almacenamiento secundario temporalmente.
·         Comprobar que el proceso que intenta acceder a una cierta dirección de memoria tiene permisos para ello.
·         La MMU se Inicializa para cada proceso del sistema. Esto permite que cada procesos pueda usar el rango completo de direcciones lógicas (memoria virtual), ya que las conversiones de estas direcciones serán distintas para cada proceso.
·         En todos los procesos se configura la MMU para que la zona del núcleo solo se pueda acceder en modo privilegiado del procesador.
·         La configuración correspondiente al espacio de memoria del núcleo es idéntica en todos los procesos.

RAM: Memoria de acceso arbitrario.
• Dinámica: DRAM (requiere refresco)
• Estática: SRAM
• Flash: RAM de larga vida

􀂉 ROM: Memoria de solo lectura
• ROM: suele utilizarse para referirse a la RAM de solo lectura
• PROM: una escritura
• EPROM: Erasable PROM (luz ultraviolete)
• EEPROM: Electricaly EPROM

􀂉 Caché: Antememoria
Acelera los accesos a memoria desde la UCP
El Administrador De Memoria se refiere a los distintos métodos y operaciones que se encargan de obtener la máxima utilidad de la memoria, organizando los procesos y programas que se ejecutan de manera tal que se aproveche de la mejor manera posible el espacio disponible.
Para poder lograrlo, la operación principal que realiza es la de trasladar la información que deberá ser ejecutada por el procesador, a la memoria principal. Actualmente esta administración se conoce como Memoria Virtual ya que no es la memoria física del procesador sino una memoria virtual que la representa. Entre algunas ventajas, esta memoria permite que el sistema cuente con una memoria más extensa teniendo la misma memoria real, con lo que esta se puede utilizar de manera más eficiente. Y por supuesto, que los programas que son utilizados no ocupen lugar innecesario.
Las técnicas que existen para la carga de programas en la memoria son: partición fija, que es la división de la memoria libre en varias partes (de igual o distinto tamaño) y la partición dinámica, que son las particiones de la memoria en tamaños que pueden ser variables, según la cantidad de memoria que necesita cada proceso.
Entre las principales operaciones que desarrolla la administración de memoria se encuentran la reubicación, que consiste en trasladar procesos activos dentro y fuera e la memoria principal para maximizar la utilización del procesador; la protección, mecanismos que protegen los procesos que se ejecutan de interferencias de otros procesos; uso compartido de códigos y datos, con lo que el mecanismo de protección permite que ciertos procesos de un mismo programa que comparten una tarea tengan memoria en común.
ADMINISTRADOR DE LA MEMORIA
La administración de memoria se refiere a los distintos métodos y operaciones que se encargan de obtener la máxima utilidad de la memoria, organizando los procesos y programas que se ejecutan de manera tal que se aproveche de la mejor forma posible el espacio disponible. Existen cuatro tipos de esquema s de asignación de memoria, estos esquemas de la administración de la memoria rara vez se utilizan en los sistemas operativos actuales.
Configuración de un solo usuario
·         Particiones fijas
·         Particiones dinámicas
·         Particiones dinámicas reubicables

Se conoce como jerarquía de memoria a la organización piramidal de la memoria en niveles, que tienen los ordenadores. Su objetivo es conseguir el rendimiento de una memoria de gran velocidad al coste de una memoria de baja velocidad, basándose en el principio de cercanía de referencias.
Los puntos básicos relacionados con la memoria pueden resumirse en:
  • Cantidad
  • Velocidad
  • Coste
La cuestión de la cantidad es simple, cuanto más memoria haya disponible, más podrá utilizarse. La velocidad óptima para la memoria es la velocidad a la que el procesador puede trabajar, de modo que no haya tiempos de espera entre cálculo y cálculo, utilizados para traer operados o guardar resultados. En suma, el costo de la memoria no debe ser excesivo, para que sea factible construir un equipo accesible.
Como puede esperarse los tres factores compiten entre sí, por lo que hay que encontrar un equilibrio. Las siguientes afirmaciones son válidas:
  • A menor tiempo de acceso mayor coste
  • A mayor capacidad mayor coste
  • A mayor capacidad menor velocidad.
Se busca entonces contar con capacidad suficiente de memoria, con una velocidad que sirva para satisfacer la demanda de rendimiento y con un coste que no sea excesivo. Gracias a un principio llamado cercanía de referencias, es factible utilizar una mezcla de los distintos tipos y lograr un rendimiento cercano al de la memoria más rápida.
Los niveles que componen la jerarquía de memoria habitualmente son:
Para incrementar la utilización de un sistema de computación se deben mantener varios procesos en memoria.

• Esto conduce a la necesidad de establecer algún esquema de administración de la memoria.
• La unidad de memoria solo ve un flujo de direcciones de memoria, no conoce como son generadas ni para que son.
Asociación de direcciones (address binding)
• Dependiendo del esquema de administración de memoria, durante su ejecución, un proceso puede ser movido entre disco y memoria.
• La mayoría de los sistemas permiten que un proceso de usuario resida en cualquier parte de la memoria física.
• En la mayoría de los casos, un programa pasará por una serie de etapas antes de ser ejecutado
• En cada etapa las direcciones pueden tener distinta representación.
• El binding de instrucciones y datos a direcciones de memoria puede ser hecho en cualquiera de las etapas:
– tiempo de compilación
– tiempo de carga
– tiempo de ejecución
Espacio de direcciones lógicas vs. Físicas
• Una dirección generada por la CPU es comúnmente referenciada como dirección lógica, mientras que desde el punto de vista de la unidad de memoria la dirección es referenciada como dirección física.
• El conjunto de direcciones lógicas generadas por un programa es referenciado como espacio de direcciones lógicas. El conjunto de direcciones físicas correspondiente a cada dirección lógica es referenciado como espacio de direcciones físicas.
• El mapping de direcciones virtuales a físicas está a cargo de la
Unidad de Administración de Memoria (disp. de hardware). Asignación con partición única
• La memoria se divide en una parte para el S.O., otra para los programas de usuario y otra no utilizada.
• Se debe proteger el código y los datos del S.O. de cambios (intencionados o accidentales) ocasionados por los procesos de usuarios
Asignación con particiones variables
• La memoria se divide en un número de particiones fijas donde cada una puede contener un proceso.
• El S.O. mantiene una tabla indicando que partes de memoria están disponibles y cuales están ocupadas.
• Cuando arriba un proceso, se busca una cavidad suficientemente grande para ese proceso
• Si se encuentra una, se asigna la memoria requerida, manteniendo el resto disponible para satisfacer futuros requerimientos.
• Así, la memoria es asignada a los procesos hasta que el requerimiento del próximo proceso no pueda ser satisfecho.
• En general hay, en cualquier instante, un conjunto de huecos, de varios tamaños, dispersos en la memoria.
• Cuando un proceso termina, libera su bloque de memoria y lo devuelve al conjunto de huecos.
• El problema de satisfacer el requerimiento de memoria con una lista de huecos libres se conoce asignación dinámica de almacenamiento.
• Las tres estrategias más comunes son:
– First-fit (Primer ajuste)
– Best-fit (Mejor ajuste)
– Worst-fit (Peor ajuste)

Multiprogramación con particiones fijas
Para poder implementar la multiprogramación, se puede hacer uso de particiones fijas o variables en la memoria. En el caso de las particiones fijas, la memoria se puede organizar dividiéndose en diversas partes, las cuales pueden variar en tamaño. Esta partición la puede hacer el usuario en forma manual, al iniciar una sesión con la máquina.
Una vez implementada la partición, hay dos maneras de asignar los procesos a ella. La primera es mediante el uso de una cola única (figura 2a) que asigna los procesos a los espacios disponibles de la memoria conforme se vayan desocupando. El tamaño del hueco de memoria disponible es usado para localizar en la cola el primer proceso que quepa en él. Otra forma de asignación es buscar en la cola el proceso de tamaño mayor que se ajuste al hueco, sin embargo hay que tomar en cuenta que tal método discrimina a los procesos más pequeños. Dicho problema podría tener solución si se asigna una partición pequeña en la memoria al momento de hacer la partición inicial, el cual sería exclusivo para procesos pequeños.

Particiones fijas en memoria con colas exclusivas para cada tamaño diferente de la partición. El espacio asignado a la partición 2 está en desuso.
Esta idea nos lleva a la implementación de otro método para particiones fijas, que es el uso de diferentes colas independientes (figura 2b) exclusivas para cierto rango en el tamaño de los procesos. De esta manera al llegar un proceso, éste sería asignado a la cola de tamaño más pequeño que la pueda aceptar. La desventaja en esta organización es que si una de las colas tiene una larga lista de procesos en espera, mientras otra cola esta vacía, el sector de memoria asignado para ese tamaño de procesos estaría desperdiciándose.
CON INTERCAMBIO
1.2.1.- Multiprogramación con particiones variables
Este esquema fue originalmente usado por el sistema operativo IBM OS/360 (llamado MFT), el cual ya no está en uso.
El sistema operativo lleva una tabla indicando cuáles partes de la memoria están disponibles y cuáles están ocupadas. Inicialmente, toda la memoria está disponible para los procesos de usuario y es considerado como un gran bloque o hueco único de memoria. Cuando llega un proceso que necesita memoria, buscamos un hueco lo suficientemente grande para el proceso. Si encontramos uno, se asigna únicamente el espacio requerido, manteniendo el resto disponible para futuros procesos que requieran de espacio.
Consideremos el ejemplo de la figura 3, en donde se cuenta un espacio reservado para el sistema operativo en la memoria baja de 400K y un espacio disponible para procesos de usuario de 2160K, siendo un total de memoria del sistema de 2560K. Dada la secuencia de procesos de la figura y usando un algoritmo de First Come – First Served (FCFS) se puede asignar de inmediato memoria a los procesos P1, P2 y P3, creando el mapa de memoria de la figura 4(a) en el cual queda un hueco de 260K que ya no puede ser utilizado por el siguiente proceso dado que no es suficiente para abarcarlo.


Administración de la memoria con mapas de bits
Este tipo de administración divide la memoria en unidades de asignación, las cuales pueden ser tan pequeñas como unas cuantas palabras o tan grandes como varios kilobytes. A cada unidad de asignación le corresponde un bit en el mapa de bits, el cual toma el valor de 0 si la unidad está libre y 1 si está ocupada (o viceversa). La figura 6 muestra una parte de la memoria y su correspondiente mapa de bits.
Para ver el grafico, utilice la opción "Bajar trabajo" del menú superior
Fig. 6. Ejemplo de un mapa de bits para la administración de la memoria.
Un mapa de bits es una forma sencilla para llevar un registro de las palabras de la memoria en una cantidad fija de memoria, puesto que el tamaño del mapa sólo depende del tamaño de la memoria y el tamaño de la unidad de asignación.
Mantiene una lista enlazada de segmentos de memoria asignados y libres, donde un segmento es un proceso o un hueco entre dos procesos.
•Si la lista se ordena por dirección es más fácil su actualización.
•Si hay dos listas, una para memoria usada y otra para huecos, la asignación es más rápida, pero la liberación es más lenta
•Ocurre lo mismo para  asignar hueco de intercambio.

En algunos sistemas, cuando un proceso esta en la memoria, no se le puede asignar espacio en disco. Cuando deba intercambiarse, puede colocarse en alguna otra parte del disco.los algoritmos para administrar el espacio de intercambio son los mismos que se emplean para administrar la memoria principal.
En otros sistemas, cuando se crea un proceso, el espacio para intercambio se asigna para el en disco. Cada ves que el proceso se intercambia, siempre se cambia a su espacio asignado, en lugar de dirigirse a un lugar diferente en cada ocasión. Cuando el proceso sale, se desasigna el espacio para el intercambio.
La única diferencia es que el espacio en el disco para un proceso debe asignarse como un número integral de bloques de disco. por lo tanto, un proceso de tamaño 13.5 k que utiliza un disco con bloques de 1k se redondeara a 14k antes de que se busquen las estructuras de datos del espacio en el disco.

La memoria virtual es una técnica de administración de la memoria real que permite al sistema operativo brindarle al software de usuario y a sí mismo un espacio de direcciones mayor que la memoria real o física.
La mayoría de los ordenadores tienen cuatro tipos de memoria: registros en la CPU, la memoria caché (tanto dentro como fuera del CPU), la memoria física (generalmente en forma de RAM, donde la CPU puede escribir y leer directa y razonablemente rápido) y el disco duro que es mucho más lento, pero también más grande y barato.
Muchas aplicaciones requieren el acceso a más información (código y datos) que la que se puede mantener en memoria física. Esto es así sobre todo cuando el sistema operativo permite múltiples procesos y aplicaciones ejecutándose simultáneamente. Una solución al problema de necesitar mayor cantidad de memoria de la que se posee consiste en que las aplicaciones mantengan parte de su información en disco, moviéndola a la memoria principal cuando sea necesario. Hay varias formas de hacer esto. Una opción es que la aplicación misma sea responsable de decidir qué información será guardada en cada sitio (segmentación), y de traerla y llevarla. La desventaja de esto, además de la dificultad en el diseño e implementación del programa, es que es muy probable que los intereses sobre la memoria de dos o varios programas generen conflictos entre sí: cada programador podría realizar su diseño teniendo en cuenta que es el único programa ejecutándose en el sistema. La alternativa es usar memoria virtual, donde la combinación entre hardware especial y el sistema operativo hace uso de la memoria principal y la secundaria para hacer parecer que el ordenador tiene mucha más memoria principal (RAM) que la que realmente posee. Este método es invisible a los procesos. La cantidad de memoria máxima que se puede hacer ver que hay tiene que ver con las características del procesador. Por ejemplo, en un sistema de 32 bits, el máximo es 232, lo que da 4096 Megabytes (4 Gigabytes). Todo esto hace el trabajo del programador de aplicaciones mucho más fácil, al poder ignorar completamente la necesidad de mover datos entre los distintos espacios de memoria.
Aunque la memoria virtual podría estar implementada por el software del sistema operativo, en la práctica casi siempre se usa una combinación de hardware y software, dado el esfuerzo extra que implicaría para el procesador.
El término memoria virtual se asocia normalmente con sistemas que emplean paginación, aunque también se puede usar memoria virtual basada en la segmentación. El uso de la paginación en la memoria virtual fue presentado por primera vez en el computador Atlas.
Cada proceso tiene su propia tabla de páginas y cuando carga todas sus páginas en la memoria principal, se crea y carga en la memoria principal una tabla de páginas. Cada entrada de la tabla de páginas contiene el número de marco de la página correspondiente en la memoria principal. Puesto que sólo algunas de las páginas de un proceso pueden estar en la memoria principal, se necesita un bit en cada entrada de la tabla para indicar si la página correspondiente está presente (P) en la memoria principal o no. Si el bit indica que la página está en la memoria, la entrada incluye también el número de marco para esa página.
Otro bit de control necesario en la entrada de la tabla de páginas es el bit de modificación (M), para indicar si el contenido de la página correspondiente se ha alterado desde que la página se cargó en la memoria principal. Si no ha habido cambios, no es necesario escribir la página cuando sea sustituida en el marco que ocupa actualmente.

Estructura de la tabla de páginas

El mecanismo básico de lectura de una palabra de la memoria supone la traducción por medio de la tabla de páginas de una dirección virtual o lógica, formada por un número de página y un desplazamiento, a una dirección física que está formada por un número de marco y un desplazamiento.
Con la memoria virtual, la CPU produce direcciones virtuales que son traducidas por una combinación de hardware y software a direcciones físicas, pues pueden ser utilizadas para acceder a memoria principal. Este proceso se denomina correspondencia de memoria o traducción de direcciones. Actualmente los dos niveles de la jerarquía de memoria controlados por la memoria virtual son las DRAM y los Discos magnéticos.
Puesto que la tabla de páginas es de longitud variable, en función del tamaño del proceso, no es posible suponer que quepa en los registros.


Implicaciones de la memoria virtual

La segmentación permite al programador contemplar  la memoria como si constara de varios espacios de direcciones o segmentos. Los segmentos pueden ser de distintos tamaños, incluso de forma dinámica. Las referencias a la memoria constan de una dirección de la forma (número de segmento, desplazamiento).
Esta organización ofrece al programador varias ventajas sobre un espacio de direcciones no segmentado:
1.        1.          Simplifica la gestión de estructuras de datos crecientes. Si el programador no conoce a priori cuán larga puede llegar a ser una estructura de datos determinada, es necesario suponerlo a menos que se permitan  tamaños de segmentos dinámicos. Con memoria virtual segmentada, a la estructura de datos se le puede asignar a su propio segmento y el S.O expandirá o reducirá el segmento cuando se necesite.
2.        2.          Permite modificar y recopilar los programas independientemente, sin que sea necesario recopilar o volver  a montar el conjunto de programas por completo.
3.        3.          Se presta a la compartición entre procesos. Un programador puede situar un programa de utilidades o una tabla de datos en un segmento que puede ser referenciado por otros procesos.
4.        4.          Se presta a la protección. Puesto que un segmento puede ser construido para albergar un conjunto de procedimientos y datos bien definido, el programador o el administrador del sistema podrá asignar los permisos de acceso de la forma adecuada.

Organización

En el estudio de la segmentación simple, se llegó a la conclusión de que cada proceso tiene su propia tabla de segmento y que, cuando todos los segmentos se encuentran en la memoria principal, la tabla de segmentos del proceso se crea y se carga en la memoria. Cada entrada de la tabla contiene la dirección de comienzo del segmento correspondiente de la memoria principal, así como su longitud. La misma estructura se necesitará al hablar de un esquema de memoria virtual basado en la segmentación donde las entradas de la tabla de segmentos pasan a ser más complejas. Puesto que sólo algunos de los segmentos de un proceso estarán en la memoria principal, se necesita un bit en cada entrada de la tabla de segmentos para indicar si el segmento correspondiente está presente en la memoria principal. Si el bit indica que el segmento está en la memoria, la entrada incluye también la dirección de comienzo y la longitud del segmento.
Otro bit de control necesario en la entrada de la tabla de segmentos es un bit de modificación que indique si el contenido del segmento correspondiente ha sido modificado desde que se cargó por última vez en la memoria principal. Si no ha habido cambios, no será necesario escribir en el disco el segmento cuando llegue el momento de reemplazarlo en el espacio que ocupa actualmente.

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 sobrescribe 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, 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.
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.
En las secciones anteriores hemos explicado cómo funciona la paginación y hemos presentado algunos de los algoritmos de reemplazo de páginas básicos. Sin embargo, no basta con conocer los aspectos mecánicos del funcionamiento. Para diseñar un sistema, necesitamos saber mucho más si queremos lograr que funcione bien. La diferencia es similar a la que existe entre saber cómo se mueven la torre, el caballo, el alfil y las demás piezas de ajedrez, y ser un buen jugador En las siguientes secciones examinaremos otros aspectos que los diseñadores de sistemas operad deben considerar detenidamente si quieren obtener un buen rendimiento de un sistema de paginación
El modelo de conjunto de trabajo
En la forma más pura de paginación, los procesos se inician con ninguna de sus páginas en la memoria. Tan pronto como la CPU trata de obtener la primera instrucción, detecta una falla página que hace que el sistema operativo traiga a la memoria la página que contiene dicha instrucción. Por lo regular, pronto ocurren otras fallas de página al necesitarse variables globales y la pila. Después de un tiempo, el proceso tiene la mayor parte de las páginas que necesita y se dedica a ejecutarse con relativamente pocas fallas de página. Tal estrategia se denomina paginación por demanda porque las páginas se cargan sólo cuando se piden, no por adelantado.
Desde luego, es fácil escribir un programa de prueba que lea sistemáticamente todas páginas de un espacio de direcciones grande, causando tantas fallas de página que no habrá suficiente memoria para contenerlas todas. Por fortuna, la mayor parte de los procesos no funcionan así; exhiben una localidad de referencia, lo que significa que durante cualquier fase de ejecución, el proceso sólo hace referencia a una fracción relativamente pequeña de sus páginas. Cada pasada de un compilador de múltiples pasadas, por ejemplo, sólo hace referencia a fracción de todas las páginas, que es diferente en cada pasada. El conjunto de páginas que un proceso está usando actualmente es su conjunto de trabajo (Denning, 1968a; Denning, 1980). Si todo el conjunto de trabajo está en la memoria, el proceso ejecutará sin causar muchas fallas hasta que pase a otra fase de su ejecución (p. ej., la siguiente pasada de un compilador). Si la memoria disponible es demasiado pequeña para contener todo conjunto de trabajo, el proceso causará muchas fallas de página y se ejecutará lentamente, ya que la ejecución de una instrucción normalmente toma unos cuantos nanosegundos, y la lectura; una página de disco suele tomar decenas de milisegundos. Si ejecuta sólo una o dos instrucción cada 20 milisegundos, el proceso tardará muchísimo en terminar. Se dice que un programa q causa fallas de página repetidamente después de unas cuantas instrucciones se está “sacudiendo (en inglés, thrashing, que es el término que utilizaremos) (Denning, 1968b).
En un sistema de tiempo compartido, los procesos a menudo se transfieren al disco (esto es, todas sus páginas se eliminan de la memoria) para que otro proceso tenga oportunidad de usar la CPU. Surge la pregunta de qué hacer cuando se vuelve a traer un proceso a la memoria. Técnicamente, no hay que hacer nada. El proceso simplemente causará fallas de página hasta que haya cargado su conjunto de trabajo. El problema es que tener 20, 50 o incluso 100 fallas de página cada vez que se carga un proceso hace lento el funcionamiento y además desperdicia mucho tiempo de CPU, pues el sistema operativo requiere unos cuantos milisegundos de tiempo de CPU para procesar una falla de página. Por ello, muchos sistemas de paginación tratan de seguir la pista al conjunto de trabajo de cada proceso y se aseguran de que esté en la memoria antes de dejar que el proceso se ejecute. Este enfoque se denomina modelo de conjunto de trabajo (Denning, 1970) y está diseñado para reducir considerablemente la tasa de fallas de página. La carga de las páginas antes de dejar que los procesos se ejecuten también se denomina pre paginación. A fin de implementar el modelo de conjunto de trabajo, el sistema operativo tiene que saber cuáles páginas están en el conjunto de trabajo. Una forma de seguir la pista a esta información es usar el algoritmo de maduración que acabamos de explicar. Cualquier página que contenga un bit 1 entre los n bits de orden alto del contador se considera miembro del conjunto de trabajo. Si no se ha hecho referencia a una página en n tics de reloj consecutivos, se omite del conjunto de trabajo. El parámetro n se debe determinar experimentalmente para cada sistema, pero por lo regular el rendimiento del sistema no es muy sensible al valor exacto. La información relativa al conjunto de trabajo puede servir para mejorar el rendimiento del algoritmo del reloj. Normalmente, cuando la manecilla apunta a una página cuyo bit R es O, esa página se desaloja. La mejora consiste en verificar si esa página forma parte del conjunto de trabajo del proceso en curso. Si lo es, se le perdona la vida. Este algoritmo se conoce como wsclock.
4.3.5 Liberación de Página
Un proceso usuario puede emitir una “liberación voluntaria de página” para liberar el marco de página cuando ya no necesitara esa página.
Se puede eliminar el “desperdicio” y acelerar la ejecución.
El inconveniente es que la incorporación de mandatos de liberación de páginas dentro de los programas de usuarios puede ser peligroso y retrasar el desarrollo de aplicaciones.
“Los compiladores y S. O. deberían detectar automáticamente situaciones de liberación de página mucho antes de lo que es posible con estrategias de conjuntos de trabajo”.