Paginación En Memoria Virtual Por: Edgar A

Transcript

1 Paginación en Memoria Virtual Por: Edgar A. Mendieta I. Gestión de Memoria. En un sistema con multiprogramación, el sistema operativo debe encargarse de realizar un reparto transparente, eficiente y seguro de los distintos recursos de la máquina entre los diversos procesos, de forma que cada uno de ellos crea que «tiene una máquina para él solo». Esto es, el sistema operativo debe permitir que los programadores desarrollen sus aplicaciones sin verse afectados por la posible coexistencia de su programa con otros durante su ejecución. En el caso de la memoria, el sistema operativo, con el apoyo del hardware de gestión de memoria del procesador, debe repartir el almacenamiento existente proporcionando un espacio de memoria independiente para cada proceso y evitando la posible interferencia voluntaria o involuntaria de cualquier otro proceso. Se podría considerar que, en el caso del procesador, se realiza un reparto en el tiempo, mientras que en el de la memoria, se trata de un reparto en el espacio La acción combinada de estos dos mecanismos ofrece a los programas una abstracción de procesador virtual que les independiza del resto de los procesos. 1. Requisitos de la Gestión de Memoria. Sea cual sea la política de gestión de memoria empleada en un determinado sistema, se pueden destacar las siguientes características como objetivos deseables del sistema de gestión de memoria: • Ofrecer a cada proceso un espacio lógico propio. • Proporcionar protección entre los procesos. • Permitir que los procesos compartan memoria. • Dar soporte a las distintas regiones del proceso. • Maximizar el rendimiento del sistema. • Proporcionar a los procesos mapas de memoria muy grandes. 1.1. Reubicación. Paginación en Memoria Virtual Edgar A. Mendieta 2 En un sistema operativo multiprogramado de propósito general no se puede conocer a priori la posición de memoria que ocupará un programa cuando se cargue en memoria para proceder a su ejecución, puesto que dependerá del estado de ocupación de la memoria, pudiendo variar, por tanto, en sucesivas ejecuciones del mismo. El código máquina de un programa contenido en un archivo ejecutable incluirá referencias a memoria, utilizando los diversos modos de direccionamiento del juego de instrucciones del procesador, tanto para acceder a sus operandos como para realizar bifurcaciones en la secuencia de ejecución. Estas referencias típicamente estarán incluidas en un intervalo desde 0 hasta un valor máximo N. 1.2. Protección. En un sistema con monoprogramación es necesario proteger al sistema operativo de los accesos que realiza el programa en ejecución para evitar que, voluntaria o involuntariamente, pueda interferir en el correcto funcionamiento del mismo. Todos los usuarios que han trabajado en un sistema que no cumple este requisito de protección, como por ejemplo MS-DOS, han experimentado cómo un error de programación en una aplicación puede causar que todo el sistema se colapse durante la ejecución de la misma al producirse una alteración imprevista del código o las estructuras de datos del sistema operativo. En un sistema con multiprogramación el problema se acentúa ya que no sólo hay que proteger al sistema operativo sino también a los procesos entre sí. El mecanismo de protección en este tipo de sistemas necesita del apoyo del hardware puesto que es necesario validar cada una de las direcciones que genera un programa en tiempo de ejecución. Este mecanismo está típicamente integrado en el mecanismo de traducción: la función de traducción debe asegurar que los espacios lógicos de los procesos sean disjuntos entre sí y con el del propio sistema operativo. Observe que en el caso de un sistema que use un procesador con mapa de memoria y E/S común, el propio mecanismo de protección integrado en el proceso de traducción permite impedir que los procesos accedan directamente a Paginación en Memoria Virtual Edgar A. Mendieta 3 los dispositivos de E/S, haciendo simplemente que las direcciones de los dispositivos no formen parte del mapa de ningún proceso. 1.3. Compartición. Para cumplir el requisito de protección, el sistema operativo debe crear espacios lógicos independientes y disjuntos para los procesos. Sin embargo, en ciertas situaciones, bajo la supervisión y control del sistema operativo, puede ser provechoso que los procesos puedan compartir memoria. Esto es, la posibilidad de que direcciones lógicas de dos o más procesos, posiblemente distintas entre sí, se correspondan con la misma dirección física. 1.4. Soporte de las regiones del proceso. Como se analizará con más detalle en secciones posteriores, el mapa de un proceso no es homogéneo sino que está formado por distintos tipos de regiones con diferentes características y propiedades. Dado que el sistema operativo conoce qué regiones incluye el mapa de memoria de cada proceso, el gestor de memoria con el apoyo del hardware debería dar soporte a las características específicas de cada región. Así, por ejemplo, el contenido de la región que contiene el código del programa no debe poder modificarse. Se debería detectar cualquier intento de escritura sobre una dirección incluida en dicha región y tratarlo adecuadamente (p. ej.: mandando una señal al proceso). Otro aspecto a resaltar es que el mapa del proceso no es estático. Durante la ejecución de un programa puede variar el tamaño de una región o, incluso, pueden crearse nuevas regiones o eliminarse regiones existentes. El sistema de memoria debe controlar qué regiones están presentes en el mapa de memoria y cuál es el tamaño actual de cada una. 1.5. Maximizar el rendimiento. El gestor de memoria debe, por tanto, realizar un reparto de la memoria entre los procesos intentando que quepa el mayor número de ellos en memoria y minimizando el desperdicio inherente al reparto. Para ello, debe establecerse Paginación en Memoria Virtual Edgar A. Mendieta 4 una política de asignación adecuada. La política de asignación determina qué direcciones de memoria se asignan para satisfacer una determinada petición. Hay que resaltar que la propia gestión de la memoria requiere un gasto en espacio de almacenamiento para que el sistema operativo almacene las estructuras de datos implicadas en dicha gestión. Así, será necesario guardar la tabla de regiones y la función de traducción asociada a cada proceso (normalmente implementadas como tablas), así como una estructura que refleje qué partes de la memoria permanecen libres y cuáles están ocupadas. Dado que el almacenamiento de estas estructuras resta espacio de memoria para los procesos, es importante asegurar que su consumo se mantiene en unos términos razonables. II. Memoria Virtual. 1. Estructura de Control y Hardware. Si se comparan la paginación y segmentación simple con la partición estática y dinámica, se pueden ver los avances fundamentales en la gestión de memoria. Las claves de estos avances son las siguientes características. • Los procesos pueden ser descargados y cargados a memoria principal de memoria principal en cualquier instante a lo largo de la ejecución. Ya que las referencias a memoria de un proceso son lógicas; las cuales son traducidas a direcciones físicas, dinámicamente durante la ejecución del proceso. • Gracias a la combinación de la traducción dinámica de direcciones de memoria y el uso de tablas de páginas o de segmentos los procesos pueden dividirse en varias partes sin que sea necesario que dichas partes estén contiguas en memoria principal. Si las características mencionadas anteriormente están presentes no será necesario que todas las páginas de o todos los segmentos de un proceso estén en la memoria principal durante la ejecución. Bastara con la parte que contiene los datos a acceder. Paginación en Memoria Virtual Edgar A. Mendieta 5 Los métodos de administración de la memoria principal, que no utilizan Memoria Virtual y esquemas de Paginación y Segmentación, es decir que llevan a las direcciones directamente al bus de la memoria, tienen un inconveniente: producen lo que se denomina fragmentación. La fragmentación, que son huecos en la memoria que no pueden usarse debido a lo pequeño de su espacio, provoca un desperdicio de memoria principal. Al utilizar la memoria virtual, las direcciones no pasan en forma directa al bus de memoria, sino que van a una unidad administradora de la memoria (MMU – Memory Management Unit). Estas direcciones generadas por los programas se llaman direcciones virtuales y conforman el hueco de direcciones virtuales. Este hueco se divide en unidades llamadas páginas. Las unidades correspondientes en la memoria física se llaman marcos para página o frames. Las páginas y los marcos tienen siempre el mismo tamaño. Al momento de querer traer un proceso a memoria en un instante dado. El sistema operativo comienza trayendo solo unos fragmentos, incluyendo el que tiene el comienzo del programa. Se llamará conjunto residente del proceso a la parte que está realmente en la memoria principal. Si el procesador encuentra una dirección lógica que no está en la memoria principal, genera una interrupción que indica un fallo de acceso a la memoria. El S.O pone al proceso interrumpido en estado Bloqueado y toma el control. Para que la ejecución de este proceso siga más tarde, el S.O necesita traer a la memoria principal el fragmento del proceso que contiene la dirección. Para ello se emite una solicitud de Lectura de E/S al disco; luego se expide otro proceso para que se ejecute mientras se realiza la operación. Una vez que el fragmento deseado se ha traído a la memoria principal y se ha emitido la interrupción de E/S, se devuelve el control al S.O, que coloca el proceso afectado en el estado de Listo. Como los procesos se ejecutan sólo en memoria principal, a esta memoria se le llama memoria real. Un programado o usuario puede ver la ejecución de dicho Paginación en Memoria Virtual Edgar A. Mendieta 6 proceso en espacios de memoria mayores a la memoria real; esta memoria será espacios disco que tomara dicho proceso para ejecutarse. Está memoria residente o que hace uso de espacio en disco es denominada memoria virtual. 2. Memoria Virtual. La memoria virtual es una técnica para proporcionar la simulación de un espacio de memoria mucho mayor que la memoria física de una máquina. Esta "ilusión" permite que los programas se hagan sin tener en cuenta el tamaño exacto de la memoria física. La ilusión de la memoria virtual está soportada por el mecanismo de traducción de memoria, junto con una gran cantidad de almacenamiento rápido en disco duro. Así en cualquier momento el espacio de direcciones virtual hace un seguimiento de tal forma que una pequeña parte de él, está en memoria real y el resto almacenado en el disco, y puede ser referenciado fácilmente. Debido a que sólo la parte de memoria virtual que está almacenada en la memoria principal, es accesible a la CPU, según un programa va ejecutándose, la proximidad de referencias a memoria cambia, necesitando que algunas partes de la memoria virtual se traigan a la memoria principal desde el disco, mientras que otras ya ejecutadas, se pueden volver a depositar en el disco (archivos de paginación). La memoria virtual ha llegado a ser un componente esencial de la mayoría de los S.O actuales. Y como en un instante dado, en la memoria sólo se tienen unos pocos fragmentos de un proceso dado, se pueden mantener más procesos en la memoria. Es más, se ahorra tiempo, porque los fragmentos que no se usan no se cargan ni se descargan de la memoria. Sin embargo, el S.O debe saber cómo gestionar este esquema. La memoria virtual también simplifica la carga del programa para su ejecución llamado reubicación, este procedimiento permite que el mismo programa se ejecute en cualquier posición de la memoria física. En un estado estable, prácticamente toda la memoria principal estará ocupada con fragmentos de procesos, por lo que el procesador y el S.O tendrán acceso Paginación en Memoria Virtual Edgar A. Mendieta 7 directo a la mayor cantidad de procesos posibles, y cuando el S.O traiga a la memoria un fragmento, deberá expulsar otro. Si expulsa un fragmento justo antes de ser usado, tendrá que traer de nuevo el fragmento de manera casi inmediata. Demasiados intercambios de fragmentos conducen a lo que se conoce como hiperpaginación; donde el procesador consume más tiempo intercambiando fragmentos que ejecutando instrucciones de usuario. Para evitarlo el S.O intenta adivinar, en función de la historia reciente, qué fragmentos se usarán con menor probabilidad en un futuro próximo. Los argumentos anteriores se basan en el principio de cercanía o principio de localidad que afirma que las referencias a los datos y el programa dentro de un proceso tienden a agruparse. Por lo tanto, es válida la suposición de que, durante cortos períodos de tiempo, se necesitarán sólo unos pocos fragmentos de un proceso. Una manera de confirmar el principio de cercanía es considerar el rendimiento de un proceso en un entorno de memoria virtual. El principio de cercanía sugiere que los esquemas de memoria virtual pueden funcionar. Para que la memoria virtual sea práctica y efectiva, se necesitan dos ingredientes. Primero, tiene que existir un soporte de hardware y, en segundo lugar, el S.O debe incluir un software para gestionar el movimiento de páginas o segmentos entre memoria secundaria y memoria principal. Justo después de obtener la dirección física y antes de consultar el dato en memoria principal se busca en memoria cache, si esta entre los datos recientemente usados la búsqueda tendrá éxito, pero si falla, la memoria virtual consulta memoria principal, ó, en el peor de los casos se consulta de disco (swapping). Lo dicho anteriormente lo podemos resumir en la siguiente expresión: Memoria Virtual = Memoria Física + Área de Swapping en Disco Paginación en Memoria Virtual Edgar A. Mendieta 8 3. Paginación. 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. Paginación en Memoria Virtual Edgar A. Mendieta 9 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. 3.1 Tabla de Páginas. Cada página tiene un número que se utiliza como índice en la tabla de páginas, lo que da por resultado el número del marco correspondiente a esa página virtual. Si el bit presente / ausente es 0, se provoca un señalamiento (trap) hacia el sistema operativo. Si el bit es 1, el número de marco que aparece en la tabla de páginas se copia en los bits de mayor orden del registro de salida, junto con el ajuste (offset) de 12 bits, el cual se copia sin modificaciones de la dirección virtual de entrada. Juntos forman una dirección física de 15 bits. El registro de salida se coloca entonces en el bus de la memoria como la dirección en la memoria física. Paginación en Memoria Virtual Edgar A. Mendieta 10 En teoría, la asociación de las direcciones virtuales con las físicas se efectúa según lo descrito. El número de página virtual se divide en un número de página virtual (los bits superiores)y un ajuste (los bits inferiores). El número de página virtual se utiliza como un índice en la tabla de páginas para encontrar la entrada de esa página virtual. El número de marco (si existe) se determina a partir de la tabla de páginas. El número de marco se asocia al extremo superior del ajuste y reemplaza al número de página virtual para formar una dirección física que se puede enviar a la memoria. La finalidad de la tabla de páginas es asociar las páginas virtuales con los marcos. En términos matemáticos, la tabla de páginas es una función, cuyo argumento es el número de página virtual y como resultado el número del marco físico. Mediante el resultado de esta función, se puede reemplazar el campo de la página virtual de una dirección virtual por un campo de marco, lo que produce una dirección en la memoria física. Sin embargo hay que enfrentar dos aspectos fundamentales: • La tabla de páginas puede ser demasiado grande. • La asociación debe ser rápida. El primer punto proviene del hecho de que las computadoras modernas utilizan direcciones virtuales de al menos 32 bits. Por ejemplo, si el tamaño de página es de 4K, un hueco de direcciones de 32 bits tiene un millón de páginas; en el caso de un hueco de direcciones de 64 bits, se tendría más información de la que uno quisiera contemplar. El segundo punto es consecuencia del hecho de que la asociación virtual – física debe hacerse en cada referencia a la memoria. Una instrucción común tiene una palabra de instrucción y también un operando de memoria. Entonces es necesario hacer una, dos o más referencias a la tabla de páginas por cada instrucción. Muchos sistemas como los AS/400 de IBM y las estaciones de trabajo RISC Sistemas/600 de IBM son usados tablas de paginas invertidas. Con este metodo la parte del número de página virtual se contrasta en una tabla de dispersión por medio de una función de dispersión simple. La tabla de dispersión contiene un Paginación en Memoria Virtual Edgar A. Mendieta 11 puntero a la tabla de páginas invertidas, que contienen a su vez las entradas de la tabla de páginas. 3.2 Buffer de traducción adelantada. Cada referencia a la memoria virtual puede generar dos accesos a la memoria: uno para obtener la entrada de la tabla de páginas correspondientes y otro para obtener el dato deseado. Un esquema sencillo de memoria virtual podría tener el efecto de doblar el tiempo de acceso a la memoria. Para solucionar este problema, la mayoría de los esquemas de memoria virtual hacen uso de una cache especial para las entradas de la tabla de páginas, llamada generalmente buffer de traducción adelantada (TLB,Translation Lookaside Buffer) que contiene aquellas entradas de la tabla de páginas usadas hace menos tiempo. La organización de hardware de paginación resultante se muestra en la figura siguiente. Paginación en Memoria Virtual Edgar A. Mendieta 12 Dada una dirección virtual, el procesador examinará primero la TLB. Si la entrada de la tabla de páginas buscada está presente se obtiene el número de marco y se forma la dirección real. Si no se encuentra, el procesador emplea el número de página como índice para buscar en la tabla de páginas del proceso y examinar la entrada correspondiente de la tabla de páginas. Si no se encuentra activo el bit de presencia, es que la página está en la memoria principal y el procesador puede obtener el número de marco de la entrada de la tabla de páginas para formar la dirección real. El procesador, además, actualiza la TLB para incluir esta nueva entrada de la tabla de páginas. Si el bit de presencia no está activo, es que la página buscada no está en la memoria principal y se produce un fallo en el acceso a la memoria, llamado fallo de página. Existe una serie de detalles adicionales sobre la organización real de la TLB. Puesto que la TLB contiene sólo algunas de las entradas de la tabla de páginas Paginación en Memoria Virtual Edgar A. Mendieta 13 completa, no se puede indexar simplemente la TLB por el número de páginas. Cada entrada debe incluir el número de página, además de la entrada completa a la tabla de páginas. El procesador estará equipado con un hardware que permita consultar simultáneamente varias entradas de la TLB para determinar si hay coincidencia en el número de página. Esta técnica se denomina correspondencia asociativa y contrasta con la correspondencia directa, que se emplea para buscar en la tabla de páginas de la figura de Búsqueda directa y asociativa. El diseñador de la TLB también debe considerar la forma en que se organiza las entradas en la TLB y que entrada reemplazar cuando se introduce una nueva. Por último, el mecanismo de la memoria virtual debe interactuar con el sistema de cache de la memoria principal. La de traducción con buffer ilustra esta interacción. Una dirección virtual estará formada por el número de página más el desplazamiento. Una vez que se ha generado la dirección real, que está en forma de etiqueta (formada por los bits más significativos de la dirección real) y un resto, se consulta la cache para ver si está presente el bloque que contiene Paginación en Memoria Virtual Edgar A. Mendieta 14 dicha palabra. Si lo está, es devuelto a la CPU. Si no, se toma la palabra de la memoria principal. 3.3 Tamaño de Página. Hay varios factores que considerar. Uno es la fragmentación interna. Sin duda, cuanto menor sea el tamaño de página, menor será la cantidad de fragmentación interna. Para optimizar el uso de la memoria principal, es positivo reducir la fragmentación interna. Por otro lado, cuanto menor sea la página, mayor será el número de páginas que se necesitan por proceso. Un número mayor de páginas por proceso significa que las tablas de páginas que se necesitan por proceso serán mayores. Así pues, pueden suceder dos fallos de página para una única referencia a la memoria: primero, para traer la parte necesaria de la tabla de páginas y, segundo, para traer la página del proceso. Se puede considerar el efecto que tiene el tamaño de página en el porcentaje de fallos de página y se basa en el principio de cercanía. Si el tamaño de página es muy pequeño, normalmente estarán disponibles en la memoria principal un gran número de páginas para cada proceso. Después de un tiempo, todas las páginas de la memoria contendrán parte de las referencias más recientes del Paginación en Memoria Virtual Edgar A. Mendieta 15 proceso y la tasa de fallos de página será menor. Cuando de incrementa el tamaño de la página, cada página individual contendrá posiciones cada vez más distantes de cualquier referencia reciente; se atenúa el efecto de principio de cercanía y comienza a aumentar la tasa de fallos de página, que comenzará a bajar cuando, finalmente, el tamaño de página se aproxime al tamaño de todo el proceso. Cuando una sola página abarca todo el proceso, no hay fallos de página. Una dificultad más es que la tasa de fallos de página viene determinada también por el número de marcos asignados a un proceso. Por último el diseño del tamaño de página está relacionado con el tamaño de la memoria física principal. Al mismo tiempo que la memoria principal se hace mayor, el espacio de direcciones que emplean las aplicaciones también crece. Esta tendencia es más evidente en las computadoras personales y estaciones de trabajo, donde las aplicaciones se hacen cada vez más complejas. 3.4 Ventajas y Desventajas de la Paginación. Ventajas: • mejor utilización de la memoria física (programas implantados por fragmentos, en páginas no consecutivas). • Posibilidad de cargar páginas solamente cuando éstas son referenciadas (cargado bajo demanda). • Independencia del espacio virtual y de la memoria física (memoria virtual generalmente más grande). • Posibilidad de llevar al disco solamente páginas modificadas. • Posibilidad de cobertura dinámica (emparejamiento). Desventajas: • Fragmentación interna (todas las páginas no son llenadas). • Imposibilidad de relacionar dos (o varios) procesos relacionados a las mismas direcciones en el espacio virtual. 4. Algoritmos de Reemplazo de Paginas. Con el uso del método de paginación se puede llegar a saturar la memoria si se incrementa demasiado el nivel de multiprogramación. Por ejemplo, si se corren Paginación en Memoria Virtual Edgar A. Mendieta 16 seis procesos, cada uno con un tamaño de diez páginas de las cuales en realidad sólo utiliza cinco, se tiene un mayor uso del CPU y con marcos de sobra. Pero pudiera suceder que cada uno de esos procesos quiera usar las diez páginas resultando en una necesidad de 60 marcos, cuando solo hay 40 disponibles. Esto provoca sobre-asignación y mientras un proceso de usuario se está ejecutando, ocurre un fallo de página. El hardware se bloquea con el sistema operativo, el cual checa en sus tablas internas y se da cuenta que es un fallo de página y no un acceso ilegal de memoria. El sistema operativo determina si la página está residiendo en disco, pero también determina que no hay marcos de memoria disponibles en la lista de marcos libres. Al ocurrir el fallo de página, el sistema operativo debe elegir una página para retirarla de la memoria y usar el espacio para la página que se necesita para desbloquear el sistema y que el hardware pueda seguir trabajando. Si la página por eliminar de la memoria fue modificada, se debe volver a escribir al disco para mantener la información actualizada; de lo contrario, si la página no fue modificada no es necesario rescribir la información a disco y la página que se carga simplemente se escribe sobre la página a borrar en memoria. Paginación en Memoria Virtual Edgar A. Mendieta 17 4.1. Algoritmo aleatorio Este algoritmo consiste simplemente en reemplazar aleatoriamente cualquier página de la memoria principal, sin hacer ningún esfuerzo de predicción. Es el algoritmo más sencillo dado que no requiere tener ninguna información, sin embargo, por no hacer uso de dicha información sobre el comportamiento del proceso, no puede lograr un buen desempeño. 4.2. Algoritmo de reemplazo de páginas óptimo Este algoritmo debe de tener el menor índice de fallos de página de todos los algoritmos. En teoría, este algoritmo debe de reemplazar la página que no va a ser usada por el periodo más largo de tiempo. Desafortunadamente, el algoritmo de reemplazo óptimo es fácil en teoría, pero prácticamente imposible de implementar, dado que requiere conocer a futuro las necesidades del sistema. Tal algoritmo existe y ha sido llamado OPT o MIN, pero se usa únicamente para estudios de comparaciones. Por ejemplo, puede resultar muy útil saber que aunque algún nuevo algoritmo no sea óptimo, está entre el 12.3% del óptimo y entre el 4.7% en promedio. 4.3. Algoritmo de reemplazo de páginas según el uso no tan reciente. Este algoritmo hace uso de los dos bits de estado que están asociados a cada página. Estos bits son: R, el cual se activa cuando se hace referencia (lectura / escritura) a la página asociada; y M, que se activa cuando la página asociada es modificada (escritura). Estos bits deben de ser actualizado cada vez que se haga referencia a la memoria, por esto es de suma importancia que sean activados por el hardware. Una vez activado el bit, permanece en ese estado hasta que el sistema operativo, mediante software, modifica su estado. Estos bits pueden ser utilizados para desarrollar un algoritmo de reemplazo que cuando inicie el proceso, el sistema operativo asigne un valor de 0 a ambos bits en todas las páginas. En cada interrupción de reloj, limpie el bit R para distinguir cuáles páginas tuvieron referencia y cuáles no. Paginación en Memoria Virtual Edgar A. Mendieta 18 Cuando ocurre un fallo de página, el sistema operativo revisa ambos bits en todas las páginas y las clasifica de la siguiente manera: Clase 0: La página no ha sido referenciada, ni modificada. Clase 1: La página no ha sido referenciada, pero ha sido modificada. Clase 2: La página ha sido referenciada, pero no ha sido modificada. Clase 3: La página ha sido referenciada y también modificada. Una vez obtenida la clasificación, elimina una página de manera aleatoria de la primera clase no vacía con el número más pequeño. Esto porque para el algoritmo es mejor eliminar una página modificada sin referencias en al menos un intervalo de reloj, que una página en blanco de uso frecuente. A pesar de que este algoritmo no es el óptimo, es fácil de implementar y de comprender y con mucha frecuencia es el más adecuado. 4.4. Algoritmo de reemplazo “Primero en entrar, primero en salir” (FIFO) El algoritmo más sencillo para remplazo de páginas es el FIFO (First In – First Out). Este algoritmo asocia a cada página el momento en que ésta fue traída a memoria. Cuando una página debe ser reemplazada se selecciona a la más antigua. No es estrictamente necesario registrar el momento de entrada de la página a memoria, sino que se puede crear una cola en la que se van agregando las páginas conforme van llegando a la memoria. Cuando se debe eliminar una página, se selecciona la que está al frente de la lista (o sea, la más antigua de la lista). Cuando llega una página nueva, se inserta en la parte trasera de la cola. Al igual que el algoritmo aleatorio, este algoritmo es fácil de comprender y de programar. Sin embargo, su desempeño no siempre es del todo bueno. La página reemplazada puede ser un módulo de inicialización que fue usado hace mucho tiempo y ya no se tiene necesidad de él. Por otro lado, puede contener Paginación en Memoria Virtual Edgar A. Mendieta 19 una variable de uso muy frecuente que fue inicializada de manera temprana y está en uso constante. 4.5. Algoritmo de reemplazo de páginas de la segunda oportunidad Este algoritmo es una modificación del FIFO. El algoritmo hace uso del bit de referencia de la página. Cuando una página ha sido seleccionada para reemplazo, se revisa el bit de referencia. Si tiene valor de 0, se procede a reemplazar la página. Si por el contrario, el bit de referencia es 1 se le da a la página una segunda oportunidad. Cuando esto sucede, se le cambia el bit de referencia a 0 y se actualiza su tiempo de llegada al tiempo actual para que la página se colocada al final de la cola. De esta manera, la página espera todo un ciclo completo de páginas para ser entonces reemplazada. Si la página tiene un uso muy frecuente, el bit de referencia se mantendría constantemente en 1 y la página no sería reemplazada. En la figura 10 se puede apreciar el funcionamiento del algoritmo. 4.6. Algoritmo de reemplazo de páginas del reloj Modificando el algoritmo de la segunda oportunidad (que a su vez es una modificación de FIFO) obtenemos el algoritmo aumentado de la segunda oportunidad o algoritmo del reloj. Usamos la misma clasificación vista en el algoritmo de uso no tan reciente. Este algoritmo organiza las páginas en una lista circular; se usa un apuntador (o manecilla) que señala a la página más antigua. Paginación en Memoria Virtual Edgar A. Mendieta 20 4.7 Algoritmo de reemplazo de páginas “la de menor uso reciente” (LRU) Este algoritmo es una buena aproximación al óptimo y se basa en al observación de que las páginas de uso frecuente en las últimas instrucciones se utilizan con cierta probabilidad en las siguientes. De la misma manera, es probable que las páginas que no hayan sido utilizadas durante mucho tiempo permanezcan sin uso por bastante tiempo. Implementando el algoritmo con esta base, al ocurrir un fallo de página, se elimina la página que no haya sido utilizada durante el tiempo más grande. De ahí su denominación: menor uso reciente (LRU - Least Recent Use). A diferencia de los algoritmos anteriores, el LRU tiene un mejor rendimiento en cuanto al tiempo de aprovechamiento del CPU y del uso de la memoria. Sin embargo, el problema con este algoritmo es que su implementación es muy cara, ya que requiere de una asistencia considerable de hardware. Otro problema es el de determinar un orden para los marcos definido por el tiempo de menor uso. Para éste último hay dos posibles implementaciones: Contadores: En el caso más sencillo, se asocia cada entrada tabla-página un campo de tiempo-de-uso y se le agrega al CPU un reloj lógico o contador. Este reloj es incrementado en cada referencia de memoria. Siempre que se hace referencia a una página, el contenido del registro del reloj es copiado al campo de tiempo-de-uso en la tabla de páginas para esa página. De esta forma, siempre se dispone del “tiempo” de la última referencia a cada página. La página que se reemplaza es la del menor valor de tiempo. Este esquema requiere de una búsqueda en toda la tabla de páginas para encontrar la página LRU, y una escritura en memoria al campo de tiempo-de-uso en la tabla de páginas por cada acceso a memoria. Los tiempos también se deben de mantener cuando las Paginación en Memoria Virtual Edgar A. Mendieta 21 tablas de páginas son alteradas (debido a organización del CPU). Se debe considerar la posibilidad de sobrecarga en el reloj. Pilas: Otra aproximación para implementar el reemplazo LRU es la de tener una pila con los números de páginas. Siempre que se hace referencia a una página, se quita de la pila y se pone en la parte superior. De esta manera, la parte superior de la pila es la página de uso más reciente y la de abajo es la LRU. III. GESTION DE MEMORIA EN UNIX Y SOLARIS Las primeras versiones de Unix sólo utilizaban particiones variables sin ningún esquema de memoria virtual., pero en las implementaciones actuales, incluidas SVR4 y Solaris 2.x, utilizan memoria virtual paginada. En SVR4 y Solaris, tienen dos esquemas de memoria separados. El sistema de paginación ofrece una memoria virtual que asigna marcos de pagina en la memoria principal a los procesos y también asigna marcos de pagina a las memorias intermedias de los bloques de disco. Un esquema de memoria virtual paginado se adapta peor a la gestión de la asignación de memoria para el núcleo, por lo que se utiliza un asignador de memoria del núcleo. 1. SISTEMA DE PAGINACIÓN Paginación en Memoria Virtual Edgar A. Mendieta 22 1.1 Estructuras de datos Para la memoria virtual paginada, UNIX, hace uso de una serie de estructuras de datos que son independientes de la maquina: Tabla de páginas: posee una tabla por proceso, con una entrada para cada página de la memoria virtual en proceso. Descriptor de bloques de disco: asociado a cada página del proceso hay una entrada en la tabla que describe la copia en el disco de la página virtual. Tabla de marcos de página: describe cada marco de la memoria real y está indexada por el número de marco. Tabla de uso de intercambios: existe una tabla por cada dispositivo de intercambio. 1.2 Reemplazo de páginas La tabla de marcos de página se utiliza en el reemplazo de páginas, utilizando varios punteros para crear listas dentro de esta tabla. El algoritmo de reemplazo de páginas utilizado en SVR4 es conocido como algoritmo del reloj de dos agujas, ya que utiliza un bit de referencia para cada pagina de la memoria que reúne los requisitos (no bloqueada) para ser expulsada. Este bit se pone a 0 cuando la página entra por primera vez y a 1 cuando se hace referencia a la pagina para una lectura o escritura. La aguja frontal recorre la lista y pone el bit de referencia a 0, así en algún tiempo la aguja trasera recorre la misma lista y comprueba el bit de referencia. Si el bit está a 1, entonces la página se ha referenciado y se ignora el marco, en cambio, si el bit está todavía 0, entonces la página no se ha referenciado en el intervalo y se pone a estas páginas en una lista para ser reemplazadas. Dos parámetros determinan la operación del algoritmo: Velocidad de recorrido: la velocidad con la que las agujas se mueven a través de la lista de páginas, en páginas por segundo. Alcance entre agujas: el espacio entre la aguja frontal y la trasera. IV. GESTION DE MEMORIA EN LINUX Paginación en Memoria Virtual Edgar A. Mendieta 23 Linux comparte algunas características de UNIX, pero su esquema de gestión de memoria es bastante complejo. 1. MEMORIA VIRTUAL DE LINUX 1.1 Direccionamiento de memoria virtual Linux hace uso de una estructura de tabla de páginas con tres niveles: • Directorio de páginas: un proceso activo tiene sólo un directorio de páginas, donde cada entrada en el mismo, señala a una página del directorio intermedio de páginas. Para un proceso activo, el directorio debe estar en la memoria principal. • Directorio intermedio de páginas: es el que puede ocupar varias páginas y donde cada entrada al directorio señala a una página de la tabla de páginas. • Tabla de páginas: ésta también puede ocupar varias páginas y en cada entrada se hace referencia a una página virtual del proceso. Para utilizar esta estructura de la tabla de páginas a tres niveles, una dirección virtual en Linux se ve como un conjunto de cuatro campos. El campo más a la izquierda (el más significativo) se utiliza como índice en el directorio de páginas; el siguiente se utiliza como índice en el directorio intermedio de páginas; el tercero como índice en la tabla de páginas y el cuarto campo indica el desplazamiento dentro de la página seleccionada de la memoria. 1.2 Asignación de páginas. Desde la memoria principal, Linux define un mecanismo para tratar bloques de páginas contiguos correspondientes a bloques de marcos de páginas contiguos, para ello, se utiliza el sistema de colegas donde el núcleo mantiene una lista de grupos de marcos de página contiguos de tamaño fijo. 1.3 Algoritmo de reemplazo de páginas. El algoritmo de reemplazo de páginas de Linux se basa en el algoritmo del reloj, que, en caso de ser el sencillo, se asocia un bit de uso y un bit de modificación a cada página de la memoria principal. En Linux utiliza una variable edad que, cada vez que se accede a la página, se incrementa la variable y recorre periódicamente la reserva de paginas globales y disminuye la variable de edad Paginación en Memoria Virtual Edgar A. Mendieta 24 de cada página cuando rota por todas las páginas de la memoria principal. Una página con un envejecimiento 0 es una página “vieja” que no se ha referenciado en bastante tiempo y es la mejor candidata para el reemplazo, y cuanto mayor valor de edad, más frecuentemente se ha usado la página recientemente y menos elegible es para el reemplazo. V. GESTION DE MEMORIA EN WINDOWS 2000 El gestor de memoria virtual de Windows 2000 (W2K) controla como se asigna la memoria y como se realiza la paginación. 1. Mapa de Direcciones Virtuales de W2K Cada proceso de usuario de W2K dispone de un espacio de direcciones separado de 32 bits, lo que permite 4 Gbytes de memoria por proceso. Por lo que, una parte de esta memoria esta reservada para el sistema operativo y cada usuario tiene 2 Gbytes de espacio de direcciones virtual disponible. 1.1 Paginación en W2K Cuando se crea un proceso en principio puede hacer uso de todo el espacio de usuario de 2 Gbytes. Este espacio se divide en paginas de tamaño fijo, y cualquiera puede cargarse en la memoria principal. En la práctica una página puede estar en uno de estos tres estados: • Disponible: las páginas no usadas actualmente por este proceso. • Reservada: un conjunto de paginas contiguas que el gestor de la memoria virtual separa para un proceso pero no cuentan para la cuota de memoria del proceso hasta que se usan. • Confirmada: paginas para las cuales el gestor de memoria virtual mantiene un conjunto de espacio separado en su archivo de paginación. La distinción entre memoria confirmada y reservada es que la primera permite a procesos o hilos declarar una cantidad de memoria que puede asignarse rápidamente cuando sea necesaria; y la otra, minimiza la cantidad de espacio en el disco separada para un proceso particular dejando ese espacio en disco para otros procesos. Paginación en Memoria Virtual Edgar A. Mendieta 25 Conclusión Así como la memoria es una de las partes más importantes de un sistema informático, su administración tendrá la misma importancia; aunque los sistemas de computación modernos contengan gran cantidad de memoria real, será necesario expandir la misma o ocupar más espacio el cual será asignado en disco. Los Sistemas Operativos actuales están diseñados para manejar cada día más procesos que necesitaran gran cantidad de memoria para su ejecución, luego entonces, es necesario asignar o reservar este espacio virtual de memoria en lugares como el disco duro. Gracias a los estudios realizados se puede entender de forma detallada que el uso de la memoria virtual a ayudado y seguirá ayudando a los programadores de Sistemas Operativos y de cualquier tipo de aplicación para que los mismos tengan un mejor desempeño a la hora de ejecutarse. Desde que surgieron los primeros Sistemas Operativos se buscó la forma de ayudar al desempeño de los procesos en ejecución, es de esta forma que para nuestro tiempo podemos contar con la memoria virtual y su técnica de paginación, que mas que todo ayudara a la multiprogramación, multiproceso y sobre todo nos dará un mejor soporte a aplicaciones sobre sistemas que trabajen en redes. Paginación en Memoria Virtual Edgar A. Mendieta 26 Bibliografía 1. Stallings, William (1998) Sistemas Operativos. España: Prentices Hall. Segunda Edición. 707 páginas. 2. Magister David Luis la Red Martinez (2001). “Paginación de Memoria Virtual con Sistemas Expertos”. Universidad Nacional del Nordeste de Argentina. http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO0.h tm#IG. Consulta 10/2004. 3. Magister David Luis la Red Martinez (2001). “Memoria Virtual”. Universidad Nacional del Nordeste de Argentina. http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/Mono gSO/MEMVIR02.htm . 14/2004. Paginación en Memoria Virtual Edgar A. Mendieta