ESCUELA DE PREPARACIÓN DE OPOSITORES E. P. O. Cl. La Merced, 8 - Bajo A Telf.: 968 24 85 54 30001 MURCIA INF-17 - SAl17 Sistemas operativos: gestión de memoria. Esquema. ' 1 ll'J"'I"~~l)lJ<:<=:I<:).l'l .•••••.•••.••••.•..••.••..•••••....•..•..•••.•.•.•.• º••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• ~ r 2 ADMINISTRACION DE LA MEMORIA 2 2.1 MONO PROGRAMACIÓN 2 2.2 MULTIPROGRAMACIÓN 2 2.2.1 Multiprogramación con particiones fijas 2 2.2.2 Multiprogramación conparticiones variables 3 Administración de la memoria con mapas de bits 3 Administración de la memoria con listas enlazadas 4 Administración de la memoria con el sistema de los asociados 4 Asignación del hueco de intercambio 5 3 MEMORIA VIRTUAL 5 3.1 PAGTNACIÓN 5 3.1.1 Tablas depáginas 6 3.1.2 Memoria asociativa 7 3.1.3 Tablas depáginas invertidas 8 3.1. 4 Algoritmos de reemplazo depáginas 9 Reemplazo de páginas según el uso no tan reciente (NRU) 9 Reemplazo "Primero en entrar, primero en salir" (FIFO) 9 Reemplazo de páginas de la segunda oportunidad 1 O Reemplazo de páginas del reloj I O 1 Reemplazo de páginas "la de menor uso reciente" (LRU) O 3.2 SEGMENTACIÓN 11 3.3 SISTEMAS COMBINADOS: SEGMENTACIÓN PAGINADA 13 '1- l.J.l'll~ 1'4. 4.1 EL MODELO DE MEMORIA DEUNIX 14 4.2 IMPLANTACIÓN DEL CONTROL DE LA MEMORIA ENUNIX 14 ~ l\1:~-1)()~ 1'4 5.1 EL MODELO DE MEMORIA DE MS-DOS 14 5.1.1 La arquitectura de memoria del 8088 14 5.1.2 El área de memoria alta 16 5.1.3 Memoria extendida 16 5.1. 4 El área superior de la memoria 17 5.1.5 Sobreposiciones (Overlays) 17 5.1.6 Memoria expandida 17 5 .2 IMPLANTACIÓN DE LA ADMINISTRACIÓN DE LA MEMORIA ENMS-DOS 18 6 WINDOWS 2000 18 6.1 CONCEPTOS FUNDAMENTALES 18 6.2 IMPLEMENTACIÓN DE ADMINISTRACIÓN DE MEMORIA 20 6.2.1 Manejo defallos depágina 20 6.2.2 El algoritmo de reemplazo depáginas 21 Escuela de Preparación de Opositores E.P.O. v05.0I INFl 7 - SAil 7. Página 2 6.2.3 Administración dememoriafisica 22 7 CONCLUSIONES 24 1 Introducción. La parte del sistema operativo que administra la memoria se llama administrador de memoria. Su labor consiste en llevar un registro de las partes de memoria que se estén utilizando y aquéllas que no, con el fin de asignar espacio en memoria a los procesos cuando éstos la necesiten y liberarlo cuando terminen, así como administrar el intercambio entre la memoria principal y el disco, en los casos en que la memoria principal no pueda albergar a todos los procesos. En este tema investigaremos varios esquemas de administración de la memoria. Comenzaremos con el sistema de administración de memoria más simple y gradualmente iremos estudiando otros más elaborados. 2 Administración de la memoria. Los sistemas de administración de la memoria se pueden clasificar en dos tipos: los que desplazan los procesos de la memoria principal al disco y viceversa durante la ejecución (intercambio y paginación), y aquellos que no. 2.1 Monoprogramación. La técnica usual de las microcomputadoras es dividir la memoria entre el sistema operativo y el proceso de un solo usuario. El sistema operativo podría estar en la parte inferior de la memoria RAM, o en ROM (Read Only Memory) en la parte superior de la memoria; o bien, los controladores de los dispositivos podrían estar en la parte superior de la memoria en ROM y el resto del sistema operativo en la parte inferior de la memoria. El PC, por ejemplo, utiliza este último esquema, con los controladores de dispositivo en ROM, en un bloque de 8K de la parte superior del espacio de direcciones de lM. El programa en ROM se llama BIOS (Basic Input Output System). Si el sistema está organizado de esta forma, sólo se puede ejecutar un proceso a la vez. El usuario escribe un comando en el terminal y el sistema operativo carga el programa a la memoria y lo ejecuta. Cuando el proceso termina, el sistema operativo espera un comando del terminal para cargar otro proceso que sobrescribirá al anterior. 2.2 Multiprogramación. Con la multiprogramación es necesario mantener el exceso de los procesos en el disco. Por supuesto, para ejecutar esos procesos, deben ser trasladados a la memoria principal. El traslado de los procesos de la memoria principal al disco y viceversa se llama intercambio. 2.2.1 Multiprogramación con particiones fijas. La forma más sencilla de multiprogramación consiste en dividir la memoria en n partes. Cuando llega un trabajo, se coloca en la cola de entrada de la parte de tamaño más pequeño de forma que lo pueda contener. Puesto que las particiones están fijas, cualquier espacio que no sea utilizado por una tarea se pierde. • Escuela de Preparación de Opositores E.P.O. v05.01 INFI 7 - SAI17. Página 3 La desventaja del ordenamiento de las tareas que llegan a la memoria en colas independientes es evidente cuando la cola de una partición grande está vacía pero la cola de una pequeña está completamente ocupada. Otro tipo de organización es el que mantiene una sola cola. Cada vez que se libere una partición, se podría cargar y ejecutar en ella la tarea más cercana al frente de la cola que se ajuste a dicha partición. Puesto que no es deseable que se desperdicie una partición de gran tamaño con una tarea pequeña, otra estrategia consiste en buscar en toda la cola de entrada el trabajo más grande que se ajuste a la partición recién liberada. Este último algoritmo discrimina a las tareas pequeñas. Una forma de salir del problema es tener siempre una pequeña partición. Tal partición permitiría la ejecución de las tareas pequeñas sin tener que asignarles una partición de gran tamaño. Otro punto de vista ~s obedecer como regla que un trabajo elegible para su ejecución no sea excluido más de k veces. Cada vez que se le excluya, obtiene un punto. Cuando adquiera k puntos, ya no podrá ser excluido de nuevo. 2.2.2 Multiprogramación con particiones variables. Al utilizar las particiones variables, el número y tamaño de los procesos en la memoria varía de forma dinámica. Es posible combinar todos los huecos en uno grande, si se mueven todos los procesos hacia la parte inferior, mientras sea posible. Esta técnica se conoce como compactación de la memoria. Por lo general, no se lleva a cabo, porque consume mucho tiempo de CPU. Si los procesos se crean con un tamaño fijo, entonces la asignación es sencilla. Si por el contrario, los segmentos de datos de los procesos pueden crecer, aparece un problema cuando un proceso intenta crecer. Si hay un hueco adyacente al proceso, éste puede ser asignado y el proceso podrá crecer hacia el hueco. Si el proceso es adyacente a otro proceso, el proceso de crecimiento deberá ser desplazado a un hueco de la memoria más grande; o habrá que intercambiar uno o más procesos para crear un hueco grande. Si un proceso no puede crecer dentro de la memoria y el área de intercambio del disco está llena, el proceso deberá esperar o ser aniquilado. Si la mayoría de los procesos crecen conforme se ejecutan, es una buena idea asignar memoria adicional, para reducir el gasto asociado con el traslado o intercambio de procesos. Sin embargo, al realizar el intercambio de los procesos al disco, sólo hay que intercambiar la memoria que realmente se utilice. En términos generales, existen tres formas utilizadas por los sistemas operativos para llevar un registro del uso de la memoria: mapas de bits, listas y sistemas amigables. Administración de la memoria con mavas de bits. L Con un mapa de bits, la memoria se divide en unidades de asignación. A cada unidad de asignación le corresponde un bit en el mapa de bits, el cual toma el valor de O si la unidad está libre y 1 si está ocupada (o viceversa). Si la unidad de asignación es grande, el mapa de bits será pequeño, pero se podría desperdiciar memoria si el tamaño del proceso no es un múltiplo exacto de la unidad de asignación. El tamaño del mapa sólo depende del tamaño de la memoria y el tamaño de la unidad de asignación. El problema principal es que cuando se decide traer a la memoria un proceso de k unidades, el administrador de memoria debe buscar en el mapa una cadena de k ceros consecutivos. La búsqueda en un mapa de bits de ciertas cadenas es una operación lenta, por lo que los mapas no se utilizan con frecuencia. • Escuela de Preparación de Opositores E.P.O. v05.01 INF17 - SAil 7. Página 4 Administración de la memoria con listas enlazadas. La memoria se representa como una lista enlazada de segmentos. Cada entrada de la lista especifica un hueco o un proceso, la dirección donde comienza, su longitud y un puntero a la siguiente entrada. La lista puede estar ordenada por direcciones. Este orden tiene la ventaja de que al terminar o intercambiar un proceso, la actualización de la lista es directa. Puesto que la entrada de la tabla de procesos del proceso que termina apuntará a la entrada de la lista correspondiente al propio proceso, sería más conveniente que la lista fuera doblemente enlazada. Esta estructura facilita la búsqueda de la entrada anterior y la verificación si una fusión es posible. Cuando los procesos y los huecos se mantienen en una lista ordenada por direcciones, se pueden utilizar diversos algoritmos para asignar la memoria para un proceso. Supongamos que el administrador de la memoria conoce la cantidad de memoria por asignar. El algoritmo más simple es el primero en ajustarse. El administrador de memoria revisa toda la lista de segmentos hasta encontrar un espacio lo suficientemente grande. El espacio se divide entonces en dos partes, una para el proceso y otra para la memoria no utilizada, excepto por el caso poco probable de un ajuste perfecto. Este algoritmo es rápido, puesto que busca lo menos posible. Otro algoritmo es el mejor en ajustarse, que busca en toda la lista y toma el mínimo hueco adecuado. En vez de asignar un hueco grande que podría necesitarse más adelante, intenta encontrar un hueco más cercano al tamaño real necesario. Este algoritmo es más lento y tiende a rellenar la memoria con huecos pequeños. Podríamos pensar en el peor ajuste; que toma siempre el hueco más grande disponible, pero tampoco es una buena idea. Estos algoritmos pueden agilizarse si se tienen dos listas independientes, una para los procesos y otra para los huecos. El precio que se paga por ese aumento de velocidad al asignar la memoria es la complejidad adicional y disminución de la velocidad al liberar la memoria. Si se tuvieran listas diferentes para los procesos y los huecos, la lista de huecos podría ordenarse por tamaño, de forma que el algoritmo mejor en ajustarse fuera más rápido. Con una lista de huecos ordenada por tamaños, el primero en ajustarse y el mejor en ajustarse tienen la misma velocidad. Otro algoritmo de asignación es el de ajuste rápido, el cual mantiene listas independientes para algunos de los tamaños que se soliciten más frecuentemente. Por ejemplo, podría tener una tabla con n entradas, donde la primera sería un puntero a la cabeza de una lista de huecos de 4K; la segunda entrada sería un puntero a una lista de huecos de 8K, etc. Con el ajuste rápido, la búsqueda de un hueco es muy rápida, pero al ordenar por tamaño los huecos y terminar o intercambiarse un proceso, la búsqueda de sus vecinos para ver si es posible una fusión es una operación cara. Administración de la memoria con el sistema de los asociados. El administrador de memoria mantiene una lista de los bloques libres de tamaño I, 2, 4, 8, 16, etc. bytes hasta el total de la memoria. Por ejemplo, con una memoria de IM, se necesitan 21 de esas listas. Al principio, toda la memoria está libre y la lista correspondiente tiene una sola entrada, con un solo hueco de IM. Las demás listas están vacías. r Escuela de Preparación de Opositores E.P.O. v05.01 INFl 7 - SAil 7. Página 5 Supongamos que un proceso de 70K se pasa a una memoria de IM completamente libre, puesto que las listas de huecos son sólo de potencias de 2, se solicitan 128K. No hay disponibles bloques de 128K, ni tampoco de 256K o 512K. Así, el bloque de IM se divide en dos bloques de 512K, llamados socios. El bloque inferior se divide en dos bloques asociados de 256K. El bloque inferior se divide en bloques de 128K y el correspondiente a la dirección O se asigna al proceso. Si a continuación se intercambia un proceso de 35K, dividimos el bloque de 128K en dos bloques asociados de 64K. Imaginemos ahora que el bloque de 128K (del que sólo se utilizaron 70K) se libera en este momento. Pasa a la lista de bloques libres de 128K. Entonces están libres un bloque de 128K en O y un bloque de 64K en 128K. No es posible aún la fusión. Al liberarse el bloque de 64K, podemos reconstruir el bloque de 256K en la dirección O, y a continuación regresamos a la configuración inicial de un solo hueco de lM. La ventaja de los sistemas asociados consiste en que cuando se libera un bloque de tamaño r,el administrador de la memoria tan sólo debe buscar en la lista de huecos de 2k para ver si es posible una fusión. El resultado es que el sistema asociado es muy rápido. Por desgracia, también es demasiado ineficiente en términos del uso de memoria, ya que todas las solicitudes deben redondearse a una potencia de 2. Este gasto excesivo se conoce como fragmentación interna, pues la memoria desperdiciada está dentro de los segmentos asignados. Cuando tenemos huecos entre los segmentos, pero no existe hueco desperdiciado dentro de ellos, esta forma de desperdicio se conoce como fragmentación externa. Asignación del hueco de intercambio. Cuando un proceso que se encuentra en la memoria deba intercambiarse, se deberá asignar un hueco para él en el área de intercambio del disco. En algunos sistemas, los algoritmos para la administración del hueco de intercambio son los mismos que se utilizan para la administración de la memoria principal. En otros sistemas, al crearse el proceso, se le asigna un hueco de intercambio en el disco. Cuando el proceso sea intercambiado, siempre pasará al hueco asignado, en vez de ir a otro lugar cada vez. Cuando el proceso concluya, se libera el hueco de intercambio. 3 Memoria virtual. La idea conocida como memoria virtual, consiste en que el tamaño combinado del programa, los datos y la pila puede exceder la cantidad de memoria física disponible para él. El sistema operativo mantiene aquellas partes del programa que se utilicen en cada momento en la memoria principal y el resto permanece en el disco. Por lo general, se usan dos técnicas para la implementación de memoria virtual, estas se conocen como paginación y segmentación. 3.1 Paginación. La mayoría de los sistemas con memoria virtual utilizan paginación. En cualquier computadora, existe un conjunto de direcciones de memoria que pueden producir los programas. Estas direcciones generadas por los programas se llaman direcciones virtuales, y conforman el hueco de direcciones virtuales. Al utilizar la memoria virtual, las direcciones virtuales no pasan de forma directa al bus de memoria, Escuela de Preparación de Opositores E.P.O. v05.0l INF 1 7 - SAI 17. Página 6 sino que van a una unidad de administración de la memoria (MMU), que asocia las direcciones virtuales con las direcciones de la memoria física. El hueco de direcciones virtuales se divide en unidades llamadas páginas. Las unidades correspondientes en la memoria física se llaman marcos para página. Las páginas y los marcos tienen siempre el mismo tamaño. Las transferencias entre la memoria y el disco son siempre por unidades de página. Dado que el hueco de direcciones virtuales es más grande que la memoria física, sólo algunas de las páginas virtuales se asocian con la memoria física. En el hardware, un bit presente/ausente de cada entrada del espacio de direcciones virtuales indica si el registro de la página está asociado o no a la memoria física. Si un programa intenta utilizar una página no asociada, la MMU hace que la CPU ejecute un señalamiento hacia el sistema operativo. Este señalamiento se llama fallo de página. El sistema operativo elige un marco para página de poco uso y escribe su contenido de nuevo en el disco. Después busca la página de referencia al marco liberado, modifica la asociación y reinicia la instrucción señalada. 3.1.1 Tablas de páginas. La finalidad de la tabla de páginas es asociar las páginas virtuales con los marcos. La tabla de páginas es una función, cuyo argumento es el número de página virtual y como resultado da 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, la tabla de páginas puede ser demasiado grande, y además, la asociación debe ser rápida. La necesidad de una asociación de páginas, rápida y de gran tamaño, es una restricción significativa de la forma en que se construyan las computadoras. El diseño más sencillo es tener una sola tabla de páginas, consistente en un array de registros rápidos en hardware, con una entrada por cada página virtual, ordenadas por el número de página virtual. Al iniciar un proceso, el sistema operativo carga los registros con la tabla de páginas del proceso, tomada de una copia que se conserva en la memoria principal. Durante la ejecución del proceso, no son necesarias más referencias a la memoria por parte de la tabla de páginas. Las ventajas de este método residen en que es directo y no necesita de referencias a la memoria durante la asociación. Una desventaja es posiblemente costosa en recursos. El hecho de cargar la tabla de páginas en cada cambio de contexto puede disminuir también el rendimiento. En el otro extremo, la tabla de páginas puede estar totalmente dentro de la memoria principal. Todo lo que necesita el hardware es un solo registro que apunte hacia el inicio de la tabla de páginas. Este diseño permite que el mapa de la memoria sea modificado en un cambio de contexto, volviendo a cargar un registro. Por supuesto, tiene la desventaja de que necesita una o más referencias la memoria para leer las entradas de la tabla de páginas durante la ejecución de cada instrucción. Por esta razón, este punto de vista rara vez se utiliza. Para evitar el problema de tener unas tablas inmensas de páginas en la memoria todo el tiempo, muchas computadoras utilizan una tabla de páginas con varios niveles. El secreto del método de las tablas de páginas de varios niveles consiste en evitar mantener todas las tablas en la memoria todo el tiempo. En particular, aquellas que no sean necesarias no deben mantenerse ahí. • Escuela de Preparacíón de Oposítores E.P.O. v05.01 INFl 7 - SAil 7. Página 7 3 .1.2 Memoria asociativa. La mayoría de los programas tienden a hacer un gran número de referencias a un número pequeño de páginas y no al revés. Así, sólo se leen muy pocos datos de la tabla de páginas; el resto se usa muy poco. La solución consiste en equipar las computadoras con un pequeño dispositivo en hardware para asociar las direcciones virtuales con las direcciones físicas sin tener que ir a la tabla de páginas. El dispositivo, llamado memoria asociativa, generalmente está dentro de la MMU y consta de un número pequeño de entradas. Cada entrada contiene la información relativa a una página; en particular, el número de página virtual, un bit que se activa al modificarse una página, el código de protección (permisos para lectura/escritura/ejecución) y el marco físico donde se localiza la página. Estos campos tienen una correspondencia uno a uno con los campos en la tabla de páginas. Otro bit indica si la entrada es válida (es decir, si está utilizándose) o no. Cuando se presenta una dirección virtual ante la MMU para su traducción, el hardware verifica si su número de página virtual se encuentra en la memoria asociativa al comparar con todos los datos al mismo tiempo (en paralelo). Si coincide con alguno y el acceso no viola los bits de protección, el marco de página se toma directamente de la memoria asociativa, sin necesidad de pasar a la tabla de páginas. Si el número de página virtual está presente en la memoria asociativa, pero la instrucción intenta escribir en una página exclusiva para lectura, se genera un fallo de página, de la misma forma que se generaría a partir de la propia tabla de páginas. Un caso interesante ocurre cuando el número de página virtual no está en la memoria asociativa. La MMU detecta la falta y hace una búsqueda normal en la tabla de páginas. Extrae entonces una entrada de la memoria asociativa y lo reemplaza con el dato determinado en la tabla de páginas. Así, si esa página se vuelve a utilizar pronto, la segunda vez se encontrará con rapidez y no será un faltante. Cuando se extraiga una entrada de la memoria asociativa, el bit modificado se copia de regreso en la entrada de la tabla de páginas en la memoria. Los demás valores ya estaban ahí. Al cargar la memoria asociativa de la tabla de páginas, todos los campos se toman de la memoria. La proporción de referencias a la memoria que pueden ser satisfechas a partir de la memoria asociativa se llama la proporción de encuentros. Mientras mayor sea esta proporción, el rendimiento será mejor. Cuando la dirección virtual consta de varios campos, la memoria asociativa debe conservarlos todos en el campo del número de página virtual. Un ajuste cuenta sólo en caso de que toda la dirección virtual (excepto por el ajuste) sea un encuentro. El ajuste del primer campo no es suficiente. Otro aspecto es el funcionamiento de la memoria asociativa en un sistema con múltiples procesos. Cada proceso tiene su propia tabla de páginas y su propia asociación. Al ejecutarse un nuevo proceso, es esencial que no se intente utilizar las entradas en la memoria asociativa relacionadas con el proceso anterior. En general, existen dos soluciones. La más sencilla es proporcionar una instrucción de máquina que invalide la memoria asociativa; es decir, que borre todos los bits de validación. Al iniciar un nuevo proceso, el sistema operativo puede ejecutar esta instrucción para garantizar que el nuevo proceso no revise las entradas anteriores. La otra solución es desarrollar la memoria asociativa con un campo de identificación del contexto o proceso y añadir un registro en hardware a la máquina, con el identificador del proceso activo. De esta forma, el hardware no sólo puede comparar el número de página virtual, sino Escuela de Preparación de Opositores E.P.O. v05.0I INF 17 - SAI 17. Página 8 también al identificador del proceso. Se ignoran entonces las entradas de los procesos distintos al proceso activo. Este punto de vista requiere hardware adicional, pero ahorra tiempo en cada cambio de contexto. Puesto que los cambios de contexto también incluyen al reloj y otros interruptores, en caso de que la memoria asociativa sea grande, el tiempo puede ser un factor apreciable. 3.1.3 Tablas de páginas invertidas. Hoy en día, muchas computadoras tienen un espacio de direcciones virtuales de 32 bits y una memoria física de 32 bits. Si el tamaño de página es de 4K, cada proceso necesita 220 entradas en su tabla de páginas. Con 4 bytes por entrada, cada proceso necesita 4 Megabytes para su tabla de páginas. Aunque esta cantidad es grande, tampoco es incontrolable. Los diversos esquemas de paginación con varios niveles analizados muestran la forma de almacenamiento y uso de estas tablas. El acceso a estas tablas siempre es a través del número de página virtual. Con el surgimiento de los chips RJSC, con espacios de direcciones virtuales de 64 bits, la situación se modifica en forma drástica. Por primera vez, la cantidad de espacio de direcciones virtuales excede en mucho la cantidad de memoria física. Si el tamaño de la página es de 4K, tal máquina necesita 252 entradas en una tabla de páginas. Este número es enorme. Lo único bueno aquí es que aunque el espacio de direcciones virtuales es inmenso el número de marcos físicos no lo es, puesto que las memorias actuales sólo están en el rango de los Gigabytes o menos. Esta observación condujo a los diseñadores a construir máquinas en las que la tabla de páginas está organizada en tomo a la memoria física en vez de la memoria virtual. En este caso la tabla de páginas no está ordenada por la dirección virtual. En lugar de esto, la i-ésima entrada contiene información relativa a la página que utiliza en ese momento el i-ésimo marco para página. El número de entradas en esta tabla es igual al número de marcos en la memoria física, que es independiente del número de páginas en el espacio de direcciones virtuales. Esta tabla de páginas se llama tabla invertida de paginas. r • Una tabla invertida se utiliza siempre con una memoria asociativa. En un encuentro, la tabla no es necesaria. En un faltante, se debe buscar en la tabla una entrada cuyo número de página virtual coincida con la página virtual de la dirección activa en la memoria. Esta búsqueda puede acelerarse mediante una tabla hashing con todas las entradas de la tabla de páginas. La tabla hashing se puede fabricar en hardware; o bien mediante el sistema operativo. Si la búsqueda se realiza en software, es esencial que no sea frecuente. Si la página necesaria no está en la memoria, el sistema operativo debe buscarla. Para esto, es necesaria una tabla de páginas convencional, que puede ser almacenada en el disco en vez de la memoria. Por supuesto, si se almacena la tabla en disco, el controlador de los fallas de página necesitará llevar a cabo una o más referencias adicionales al disco antes de recuperar la página necesaria. Es probable que este costo excesivo sea inevitable, dado el gran tamaño de la tabla de páginas y la gran cantidad de información necesaria. • Escuela de Preparación de Opositores E.P.O. v05.01 INFl 7 - SAI17. Página 9 3.1.4 Algoritmos de reemplazo de páginas. Cuando ocurre un fallo de página, el sistema operativo debe elegir una página para retirarla de la memoria y hacer espacio para la página por recuperar. Si la página a eliminar fue modificada mientras estaba en la memoria, debe volver a escribirse en el disco para mantener actualizada la copia del disco. Si no ha sido modificada, la copia en disco ya está actualizada, por lo que no es necesario volver a escribirlo. La página a leer sólo escribe encima de la página a retirar. El rendimiento del sistema es mejor si se elige una página de poco uso. Si se elimina una página de uso muy frecuente, es probable que deba recuperarse muy pronto, lo que produce un gasto adicional. Reemplazo de páginas según el uso no tan reciente (NRU). Para que el sistema operativo recoja estadísticas útiles acerca de las páginas que sí se utilizan y las que no, la mayoría de las computadoras con memoria virtual tienen dos bits de estado asociados a cada página. R se activa si se hace referencia a la página (se lee o escribe en ella). M se activa cuando se escribe en la página (cuando se modifica). Los bits están contenidos en cada entrada de la tabla de páginas. Estos bits deben actualizarse en cada referencia a la memoria, por lo que es esencial que sean activados por el hardware. Una vez activado un bit, permanece en ese estado hasta que el sistema operativo lo desactiva en software. Si el hardware no tiene esos bits, se pueden simular por software. Los bits R y M se pueden utilizar para construir un algoritmo de reemplazo: al iniciar un proceso, el sistema operativo asigna un valor O a los dos bits R y M de todas las páginas. Periódicamente (en cada interrupción del reloj), se limpia el bit R, para distinguir las páginas que no tienen referencias recientes de las que sí. En un fallo de página, el sistema operativo inspecciona todas las páginas y las divide en cuatro categorías, según los valores actuales de los bits R y M: • Clase O: no se ha hecho referencia, ni ha sido modificada. • Clase 1 : no se ha hecho referencia, pero ha sido modificada. • Clase 2: se ha hecho referencia, pero no ha sido modificada. • Clase 3: se ha hecho referencia y ha sido modificada. Aunque parece imposible la existencia de las páginas de la clase 1, este caso aparece cuando en una página de clase 3, una interrupción de reloj limpia su bit R. Las interrupciones del reloj no limpian el bit M, puesto que esta información es necesaria para saber si hay que volver a escribir la página en el disco o no. El algoritmo NRU elimina una página de forma aleatoria de la primera clase no vacía con el número más pequeño. Una hipótesis implícita de este algoritmo es que es mejor eliminar una página modificada sin referencias en al menos un intervalo del reloj que una página en blanco de uso frecuente. El principal atractivo de este algoritmo es que es fácil de comprender, de implantación eficiente y con un rendimiento que, sin ser óptimo, es adecuado con mucha frecuencia. Reemplazo "Primero en entrar, primero en salir" (FIFO). Otro algoritmo de reemplazo de bajo costo es el algoritmo FIFO. El sistema operativo tiene una lista de todas las páginas que se encuentran en la memoria, siendo la Escuela de Preparación de Opositores E.P.O. v05.01 INF 1 7 - SAI 17. Página 1 O primera página la más antigua y la última la más reciente. En un fallo de página, se elimina la primera página y se añade la nueva al final de la lista. El problema de este algoritmo es que puede eliminar una página de uso frecuente, por lo que no es muy utilizado. Reemplazo de páginas de la segunda oportunidad. Una modificación simple de FIFO inspecciona el bit R de la página más antigua. Si es O, la página es tanto antigua como no utilizada, por lo que reemplaza en forma inmediata. Si el bit es 1, el bit se limpia, la página se coloca al final de la lista de páginas y su tiempo de carga se actualiza, como si hubiera llegado en ese momento a la memoria. Después continúa la búsqueda. Lo que hace la segunda oportunidad es buscar una página antigua sin referencias durante el anterior intervalo de tiempo. Si todas las páginas tienen alguna referencia, el algoritmo de la segunda oportunidad deriva en un simple FIFO. Reemplazo depáginas del reloi. Aunque la segunda oportunidad es un algoritmo razonable, es ineficiente, puesto que desplaza constantemente las páginas en una lista. Un mejor enfoque es mantener las páginas en una lista circular, manteniendo un puntero (manecilla) hacia la página más antigua. Al ocurrir un fallo de página, se inspecciona la página a la que apunta la manecilla. Si su bit R es O, la página se retira de la memoria, se inserta la nueva página en su lugar en el reloj y la manecilla avanza una posición. Si R es 1, este bit se limpia y la manecilla avanza a la página siguiente. Este proceso continúa hasta encontrar una página con R = O. Este algoritmo difiere de la segunda oportunidad sólo por la implementación. Reemplazo depáginas "la de menor uso reciente" (LRU). Las páginas de uso frecuente en las últimas instrucciones se utilizan con cierta probabilidad en las siguientes. Recíprocamente, es probable que las páginas que no hayan sido utilizadas durante mucho tiempo permanezcan sin uso por bastante tiempo. Esta idea sugiere un algoritmo: al ocurrir un fallo de página, se elimina la página que no haya sido utilizada durante el tiempo más grande. Para implantar LRU, es necesario mantener una lista enlazada de todas las páginas en la memoria, donde la página de uso más reciente está al principio de la lista y la de uso menos reciente al final. La dificultad estriba en que la lista debe actualizarse en cada referencia a la memoria. La búsqueda de una página en la lista, su eliminación y posterior traslado al frente de la misma puede ser una operación que consuma mucho tiempo. La búsqueda y manipulación de una lista enlazada en cada instrucción es prohibitiva por su lentitud por lo que es necesario un hardware especial. Una posibilidad de implementar el algoritmo por software es el uso del algoritmo de uso no frecuente, o NFU, el cual necesita un contador en software asociado a cada página; el contador tiene un valor inicial O. En cada interrupción del reloj, el sistema operativo examina todas las páginas de la memoria. Para cada página, el bit R (O ó 1) se suma al contador. Los contadores son un intento por llevar un registro de la frecuencia de referencia de cada página. Cuando ocurre un fallo de página, se elige la página con el valor mínimo del contador para su reemplazo. Escuela de Preparación de Opositores E.P.O. v05.01 INFl 7 - SAI I7. Página 11 El principal problema del NFU es que nunca olvida. Por fortuna, una ligera modificación del NFU hace posible que simule LRU de forma adecuada. La modificación tiene dos partes. En la primera, los contadores se desplazan a la derecha 1 bit, antes de añadir el bit R. En la segunda, el bit R añade al bit del extremo izquierdo, en vez del extremo derecho. Este algoritmo modificado se conoce con el nombre de maduración. Al ocurrir un fallo de página, se elimina aquella página cuyo contador sea el más pequeño. 3.2 Segmentación. La memoria virtual que hemos analizado hasta ahora es unidimensional, puesto que las direcciones virtuales van desde O hasta una dirección máxima, una después de otra. Para muchos problemas, el hecho de tener dos o más espacios independientes de direcciones virtuales es mucho mejor que tener uno solo. Una solución consiste en dotar a la máquina de varios espacios independientes de direcciones, llamados segmentos. Cada segmento tiene una serie lineal de direcciones, desde O hasta cierto máximo. La longitud de cada segmento puede variar de O hasta un máximo permitido. Los distintos segmentos pueden tener longitudes distintas. Además, la longitud de un segmento puede variar durante la ejecución. Puesto que cada segmento constituye un espacio independiente de direcciones, los distintos segmentos pueden crecer o reducirse de forma independiente, sin afectar a los demás. Por supuesto, un segmento puede ser utilizado en su totalidad, pero lo común es que los segmentos sean grandes, de modo que lo anterior ocurre muy poco. Para especificar una dirección en esta memoria segmentada o bidimensional, el programa debe proporcionar una dirección con dos partes, un número de segmento y una dirección dentro de éste. Conviene enfatizar que un segmento es un objeto lógico, del cual tiene conciencia el programador, por lo que lo utiliza como tal. Un segmento puede contener un procedimiento, un array, una pila, o bien un conjunto de variables escalares, pero, por lo general no contiene una mezcla de varios. Una memoria segmentada tiene otras ventajas, además de hacer más sencilla la administración de las estructuras de datos que crecen o se reducen. Si cada procedimiento ocupa un segmento independiente, con la dirección O como dirección inicial, el enlazado independiente de los procedimientos compilados es mucho más sencillo. Después de compilar y enlazar todos los procedimientos que constituyen un programa, una llamada al procedimiento en el segmento n utilizará la dirección (n, O) para dirigirse a la palabra O (donde está el dato). Si el procedimiento del segmento n se modifica y vuelve a compilar más tarde, no hay que cambiar los demás procedimientos (puesto que no se han modificado las direcciones iniciales), incluso en caso de que la nueva versión sea más grande que la anterior. En una memoria unidimensional, los procedimientos se empaquetan muy cercanos entre sí, sin que exista espacio de direcciones entre ellos. En consecuencia, el cambio de tamaño de un procedimiento puede afectar las direcciones iniciales de otros no relacionados con aquél. Esto, a su vez, requiere modificar todos los procedimientos que cualquiera de los procedimientos desplazados, para poder incorporar sus nuevas direcciones iniciales. Si un programa contiene cientos de procedimientos, todo este proceso puede resultar costoso. Escuela de Preparación de Opositores E.P .O. v05.0l INF 17 - SAI 17. Página 12 La segmentación también facilita el uso de procedimientos o datos compartidos entre varios procesos. Un ejemplo común es la biblioteca compartida. Es frecuente que las estaciones de trabajo modernas que ejecutan sistemas avanzados, con ventanas, tengan bibliotecas gráficas de tamaño muy grande que se compilan casi en todos los programas. En un sistema segmentado, la biblioteca gráfica se puede colocar en un segmento y compartirse entre varios procesos, sin necesidad de tenerla en el espacio de direcciones de cada proceso. Aunque también es posible tener bibliotecas compartidas en los sistemas con paginación pura, es mucho más complejo. De hecho, estos sistemas simulan la segmentación. Puesto que cada segmento es una unidad lógica de la que es consciente el programador, los distintos segmentos pueden tener distintos tipos de protección. Tal protección es útil para determinar errores de programación. En una memoria segmentada, el usuario es consciente del contenido de cada segmento. Generalmente, un segmento no contendrá a la vez un procedimiento y una pila, sino una cosa o la otra puesto que cada segmento sólo contiene un tipo de objeto, el segmento puede tener la protección adecuada para ese tipo particular. La paginación y la segmentación se comparan en la siguiente figura. e id d P · -Òr s -Òr onsi eran o azinacion ezmentación ¿Necesita saber el programador si No Sí está utilizando esta técnica? ¿Cuántos espacios lineales de I Muchos direcciones existen? ¿Puede el espacio total de Sí Sí direcciones exceder el tamaño de la memoria física? ¿Pueden distinguirse los No Sí procedimientos y los datos, además de protegerse en forma independiente? ¿Pueden adecuarse con facilidad las No Sí tablas con tamaños fluctuantes? ¿Se facilita el uso de No Sí procedimientos compartidos entre los usuarios? ¿Para qué se inventó esta técnica? Para obtener un gran Para permitir que los programas y espacio lineal de datos fueran separados en espacios direcciones sin tener que independientes de direcciones y poder adquirir más memoria proporcionar la protección y uso de fisica objetos compartidos Puesto que el usuario de una memoria segmentada tiene la ilusión de que todos los segmentos están dentro de la memoria principal todo el tiempo (puede dirigirse a ellas como si lo estuvieran), puede proteger cada segmento en forma independiente, sin tener que preocuparse por su administración. La implantación de la segmentación difiere del caso de la paginación en un sentido esencial: las páginas tienen un tamaño fijo y los segmentos no. La siguiente figura muestra un ejemplo de memoria física que contiene al principio cinco segmentos. Escuela de Preparación de Opositores E.P.O. v05.0l INFI 7 - SAil 7. Página 13 . o &eg,wnoo o to o o (cJ() ., {«l 7 f"!i( 1 (SIO t 2 CSK) .e <• 3 8 3 • ffKt s I Consideremos ahora lo que ocurre si el segmento 1 se elimina y el segmento 7, que es menor, se coloca en su lugar. Obtenemos la configuración de memoria de (b). Entre el segmento 7 y el 2 está un área no utilizada (es decir, un espacio). Entonces, el segmento 4 se reemplaza por el segmento 5, como en (e) y el segmento 3 se reemplaza con el segmento 6, como en (d). Después de que el sistema esté en ejecución durante cierto tiempo, la memoria quedará dividida en varios bloques, algunos con segmentos y otros con espacios. Este fenómeno de fragmentación externa desperdicia la memoria correspondiente a los espacios. Se puede enfrentar mediante la compactación, como se muestra en (e). 3.3 Sistemas combinados: segmentación paginada. Lo más común es combinar un esquema mixto de segmentación y paginación para evitar la fragmentación externa. Aprovechando las ventajas de la paginación (espacio limitado), los segmentos se pueden dividir en páginas. De esta forma, no es necesario que todas las páginas de un segmento se encuentren en la memoria real simultáneamente. Además, las páginas en almacenamiento virtual no tienen que ser continuas en la memoria principal. La paginación añade otro nivel de división de los programas, todavía más pequeño que el de la segmentación. Este nuevo nivel requiere también una nueva estructura de direcciones. Las direcciones de los datos se forman ahora con tres parámetros (segmento, página, desplazamiento en la página). Las combinaciones entre paginación y segmentación son las siguientes: • Memoria no segmentada y no paginada: La dirección virtual es la misma que la dirección física. • Memoria paginada no segmentada: La memoria es un espacio de direcciones paginado. • Memoria segmentada no paginada: La memoria es un conjunto de direcciones lógicas. • Memoria segmentada paginada: La segmentación define particiones lógicas de memoria y la paginación gestiona la asignación de memoria dentro de las particiones. Escuela de Preparación de Opositores E.P.O. v05.0I INFl 7 - SAI 17. Página 14 4 U'NIX. 4.1 El modelo de memoria de UNIX Cada proceso UNIX tiene un espacio de direcciones, con tres segmentos: texto, datos y pila. El segmento de texto contiene las instrucciones de máquina que conforman el código ejecutable del programa. Es exclusivo para la lectura (no crece ni disminuye ni se modifica de alguna otra manera). El segmento de datos es un espacio para almacenar las variables y otros datos del programa. A diferencia del segmento de texto, el segmento de datos sí puede ser modificado. UNIX permite que el segmento de datos crezca y se reduzca al asignar y liberar la memoria. El tercer segmento es el de la pila. Normalmente, comienza en la parte superior del espacio de direcciones virtuales y crece hacia abajo. Cuando dos usuarios ejecutan el mismo programa, sería ineficiente tener dos copias del texto del programa en la memoria al mismo tiempo. Muchos sistemas UNIX soportan los segmentos de texto compartidos. Los segmentos de datos y de la pila nunca se comparten. Si cualquiera de ellos necesita crecer y no existe espacio adyacente hacia el cual hacerlo, se le desplaza a otra parte de la memoria. 4.2 Implantación del control de la memoria en UNIX Antes de 3BSD, si existían más procesos de los que se podían mantener dentro de la memoria, algunos de ellos se intercambiaban al disco. Un proceso intercambiado se intercambiaba en su totalidad (excepto tal vez el texto compartido). Así, un proceso se encontraba dentro de la memoria o dentro del disco. A partir de 3BSD, Berkeley añadió paginación para manejar programas cada vez más grandes. Tanto 4BSD como el Sistema V implantan la paginación por demanda. La idea fundamental detrás de la paginación es simple: no es necesario que un proceso esté totalmente contenido en la memoria para poderlo ejecutar. Lo que se necesita es la estructura del usuario y las tablas de páginas. Si estos se intercambian del disco a la memoria, el proceso se considera "dentro de la memoria" y se puede planificar su ejecución. Las páginas de los segmentos de texto, datos y pila se recuperan de forma dinámica, una a la vez, cuando se hace referencia a ellas. Si la estructura del usuario y la tabla de páginas no están en la memoria, el proceso no se puede ejecutar hasta que el intercambiador las lleva a la memoria. El demonio para paginación utiliza una versión modificada del algoritmo del reloj. 5 MS-DOS. 5.1 El modelo de memoria deMS-DOS. MS-DOS tiene un modelo de memoria bastante complejo. El espacio de direcciones se divide en cuatro regiones, con tamaños y propiedades diferentes. Esta complejidad se debe totalmente a las peculiaridades de la arquitectura de la máquina subyacente. 5.1.1 La arquitectura de memoria del 8088. El 8088 tiene 12 registros. El primer bloque, AX, BX, CX y DX lo forman registros de 16 bits, cada uno de los cuales consta de una pareja de registros de 8 bits. Existen instrucciones para la carga y almacenamiento de los registros de 16 bits y también para los registros de 8 bits. El segundo bloque, SI, DI, BP y SP son verdaderos Escuela de Preparación de Opositores E.P.O. v05.01 INF17- SAI17. Página 15 registros de 16 bits. SI y DI son registros de índices; BP se utiliza, por lo general, para apuntar a la base del marco de pila activo (para el acceso a variables locales) y SP es el puntero a la pila. Todos estos registros deben contener punteros. El tercer bloque, CS, DS, SS y ES son registros de segmento. Forman el mecanismo mediante el cual las memorias de 1 megabyte y las direcciones de 16 bits pueden coexistir. Cada registro de segmento contiene los 16 bits superiores de una dirección de 20 bits. Los 4 bits inferiores siempre son nulos. Así, un valor de O se refiere a la dirección OxOOOOO, un valor 1 se refiere a la dirección OxOOO 1 O ( 16 decimal), etc. Los registros de segmento contienen direcciones de memoria medidas no en bytes, sino en unidades de 16 bytes, llamadas párrafos. Cada registro de segmento tiene su propio uso. CS, iniciales de segmento de código, se utiliza para reasignar el contador del programa. DS, iniciales de segmento de datos, se utiliza para reasignar direcciones de datos. SS, segmento de pila, se utiliza para reasignar referencias a la pila. Por último, ES, segmento extra es un registro de segmento adicional, que se utiliza con distintos fines. Los segmentos tienen una longitud de 64K bytes y se pueden reasignar en cualquier parte del espacio de direcciones de 1 megabyte (es decir, de 20 bits). .. ' M +655201i-------......f 1 1------------~ H1~ . 7$*(· ..__ ..........,..___ _, Sl2K ,..._~~~~.,..._ DS•327 n,c ....... '--------- ... 9,c....., •• __.. CS• &12 ft'-------~ ·O._ ....._ ...... __. Las instrucciones de máquina en el 8088 contienen direcciones de 16 bits y ajustes de 16 bits. El contador del programa también tiene 16 bits. Así, las referencias a memoria, tanto de datos como de texto, están siempre en el rango de O a 65535. Aquí es donde entran en acción los registros de segmento. Antes de buscar una instrucción en las direcciones de la memoria hacia las que apunta el contador del programa de 16 bits, el hardware del 8088 reasigna de manera automática el contador del programa dentro del segmento de código, sumando la dirección (implícita) del segmento de código de 20 bits al contador del programa, para obtener una dirección completa de memoria física de 20 bits. Escuela de Preparación de Opositores E.P.O. v05.01 INF17-SAI17. Página 16 En consecuencia, el esquema de los registros de segmento cumple con ambas restricciones de diseño. Con los registros de segmento, los programas y los datos se pueden colocar en cualquier parte del espacio de direcciones de lM. El precio que se paga es que sólo se tiene un fácil acceso a 128K. Para tener acceso a un lugar fuera de los segmentos de código o de datos, el programa debe cargar alguno de estos segmentos con un valor distinto o cargar ES y utilizar un tipo especial de direccionamiento que indique a la CPU que utilice ES en vez de DS. De cualquier forma, es mucho más difícil que simplemente tener un tradicional espacio lineal de direcciones desde O hasta la dirección máxima. La arquitectura segmentada del 8088 indica que la escritura de un programa que utilice más de 64K de código o datos es costosa. En consecuencia, se han desarrollado varios modelos distintos de programación para el 8088, según las necesidades de cada programa. 5.1.2 El área de memoria alta. Los registros de segmento con valores entre OxFOOI y OxFFFF tienen parte de sus segmentos por encima de lM. Por ejemplo, si CS es igual a OxFOOl, un salto a OxFFF4 va hacia la dirección Oxl00004, cuatro bytes por arriba de la parte superior de la memoria. De forma similar, si DS es igual a OxFFFF, una instrucción que intente cargar el byte en OxFFFF hará referencia a la dirección OxlOFFEF, igual a 1M+655 I9. Los 65520 bytes entre OxlOOOOO y OxlOFFEF son llamados el área de memoria alta (HMA). En el 8088, el hardware ignora el bit número 21, por lo que las direcciones se asocian desde O a 65519. En el 286 y los siguientes procesadores, su comportamiento depende del tipo de conexión del pin de la dirección A20 en el chip del CPU. Si está conectado de forma que funcione como las demás, HMA se puede utilizar para la memoria y el propio MS- . DOS puede colocarse ahí. Sin embargo, si está conectado a tierra (forzado a O), entonces todas las direcciones entre OxlOOOOO y OxlOFFEF serán asociadas al rango OxOOOOO y OxOFFEF. Para que sea 100% compatible con el 8088, el pin se debe conectar a tierra, puesto que puede existir un software perverso que genere direcciones superiores a IM, con la esperanza de que se encimen en las direcciones inferiores. En teoría, en el 8088, la dirección Oxl 00004 es un sinónimo válido de 4. Esta validez no implica que sea una buena práctica de programación. Así, el vendedor de hardware debe elegir si permite el uso de HMA (y con ello la ejecución de MS-DOS por encima de IM), liberar 64K de memoria convencional o ser compatible con 8088. 5.1.3 Memoria extendida. El 286 y sus sucesores pueden tener memoria por encima de IM. La memoria por encima de 1M se llama memoria extendida. El 286 y sus sucesores pueden tener dos o más modos de funcionamiento, uno de los cuales es el modo real. El modo real es el único que permite la compatibilidad con el 8088. MS-DOS sólo funciona en modo real, lo que dificulta el uso de la memoria extendida. En principio, MS-DOS no utiliza la memoria extendida. Con excepción de los primeros 65520 bytes (la HMA), la memoria extendida sólo se utiliza para los discos RAM y el buffer caché. La estructura de MS-DOS no permite su uso para los programas. Escuela de Preparación de Opositores E.P.O. v05.0l INF 17 - SAI 17. Página 17 5.1.4 El área superior de la memoria Además de todas estas peculiaridades de la CPU, IBM creó algunas otras por la forma en que el PC original utilizaba su memoria. En esta máquina, la memoria entre O y 640K se reservaba para el sistema operativo, los manejadores de dispositivos y los programas ordinarios. Esta región se llama memoria convencional. Los restantes 384K, de 640K a IM, llamados área superior de memoria (UMA), estaban reservadas para video RAM, ROM de BASIC y otras funciones relacionadas con la E/S. No existía RAM por encima de 640K, de modo que el sistema operativo, los manejadores de dispositivos y todos los datos y programas del usuario se restringían a la memoria convencional de 640K. Al pasar el tiempo y agrandarse los programas, esto se convirtió en un problema. A partir de MS-DOS 5.0, Microsoft decidió permitir que los modelos 386 y superiores utilizaran este espacio de direcciones, mediante la asociación de partes de la memoria extendida con los huecos. Así, por ejemplo, si cierta máquina no tiene dispositivos de EIS, ROM o vídeo RAM en las direcciones 640K a 704K, 768K a 800K y 896K a 960K, puede indicar a MS-DOS que asocie 160K de su memoria extendida con estos huecos, para poderlos utilizar como RAM. La asociación de la memoria extendida con los huecos en el área superior de la memoria es sólo un intento por rehacer el daño. El área superior de la memoria está disponible sólo para los usuarios de 386 y 486, puesto que las máquinas más pequeñas no poseen hardware de paginación y no pueden asociar la memoria extendida física con las direcciones virtuales en el rango 640K a IM. Al iniciar MS-DOS, se lee el archivo config.sys, donde el usuario puede especificar que el propio MS-DOS se coloque en el HMA en vez de colocarlo en la memoria convencional. También es posible especificar que los manejadores de dispositivos y los TSR se mantengan en el área superior de la memoria. El efecto de todo esto es liberar memoria adicional por debajo del límite de los 640K. 5.1.5 Sobreposiciones (Overlays) La necesidad de un espacio de direcciones mayor de 640K data desde el 286. En ese momento, se necesitaba una solución compatible con el 8088. Se diseñaron dos soluciones, una software y otra hardware. La solución software es una llamada al sistema que permite a un programa en ejecución cargar en la memoria un archivo com o exe, lo que se denomina una sobreposición (overlays), para recuperar después el control. El programa que hace la llamada llama entonces a un procedimiento que se encuentra en la sobreposición. Después de concluir la sobreposición, el control regresa al programa que hizo la llamada, que puede entonces liberar la memoria de la sobreposición y continuar. El programa tiene la libertad de cargar esa u otras sobreposiciones más adelante. De esta forma, es posible que programas arbitrariamente grandes queden contenidos en una cantidad relativamente pequeña de memoria. 5 .1. 6 Memoria expandida. Las sobreposiciones no funcionan de manera adecuada cuando un programa necesita operar en una gran estructura de datos que no encaje en el espacio de direcciones de 640K. Hace algunos años, tres compañías, Lotus, Intel y Microsoft se reunieron y diseñaron un esquema hardware llamado memoria expandida mediante el cual se podían conectar al 8088 grandes cantidades de memoria para su uso. Aunque el 286 y sus sucesores no necesitan la memoria expandida, puesto que poseen memoria extendida, MS-DOS la soporta y muchas aplicaciones la utilizan. El esquema Escuela de Preparación de Opositores E.P.O. v05.01 INF 17 - SAI 1 7. Página 18 desarrollado por las tres compañías se ha convertido en u11 estándar y se conoce como LIM EMS (Lotus/Intel Mierosoji Expanded Memory System) La idea fundamental detrás de EMS es una antigua técnica. El espacio de direcciones de lM en el PC se divide en 64 páginas de l 6K cada una. La memoria, de hasta 32M, se divide en un máximo de 2048 marcos de página, cada uno de 16K. Un hardware especial en la tarjeta de la memoria expandida asocia las 64 páginas virtuales con cualquier conjunto de marcos físicos de página. Con la paginación, el problema es que no existe la suficiente memoria física como para contener un gran espacio de direcciones virtuales, por lo cual es necesaria la asociación. El problema que intenta resolver la memoria expandida es ajustar programas y estructuras de datos grandes en un espacio de direcciones virtuales de 640K. En contraste con la paginación, que es transparente, la memoria expandida es visible por completo para el programador. 5.2 Implantación de la administración de la memoria en MS-DOS. En MS-DOS la memoria se divide en bloques adyacentes llamados zonas, cada una de las cuales comienza en una frontera de párrafo y contiene un número entero de párrafos. Cada zona comienza con un encabezado de zona de 16 bytes. El encabezado comienza con un número mágico (para verificar que la palabra en cuestión es en realidad el inicio de un encabezado de zona). Después viene un puntero al PSP del proceso que asignó el espacio para la zona, o O si está libre. A continuación está el tamaño de la zona en párrafos. Por último, está un campo que puede contener el nombre del archivo ejecutable en binario que posee la zona, pero sólo para la zona ocupada por el propio programa. Aunque el esquema de zonas funciona para la memoria superior, no sirve para la memoria extendida, puesto que los tamaños de los encabezados de zona son sólo de 16 bits. Para utilizar la memoria por encima de IM, es necesario instalar uno o más manejadores de memoria extendida. La siguiente figura lista algunos de los más comunes y sus funciones. EMM386.EX SMARTORV. SYS RAMDßfVE. SYS MS-DOS no realiza intercambios ni paginación. Si un proceso intenta asignar espacio de memoria y no existe éste, o bien, si un proceso intenta producir un hijo y no existe la memoria suficiente para ello, la llamada al sistema regresa un código de error. La recuperación queda como responsabilidad de quien hizo la llamada. 6 Windows 2000. 6.1 Conceptosfundamentales. En Windows 2000, cada proceso de usuario tiene su propio espacio de direcciones virtual. Las direcciones virtuales son de 32 bits, así que cada proceso tiene 4 GB de espacio de direcciones virtual. Los 2 GB inferiores están disponibles para el Escuela de Preparación de Opositores E.P.O. v05.01 INF 17 - SAI 17. Página 19 código y los datos del proceso; los 2 GB superiores se hacen corresponder con la memoria de kernel en forma protegida. El espacio de direcciones virtual se pagina con un tamaño de página fijo (4 KB en el Pentium). Los 64 KB más bajos y más altos del espacio de direcciones virtual de cada proceso no tienen correspondencia. Esto ayuda a atrapar errores de programación. Los punteros no válidos suelen ser O o -1, así que un intento por usarlos causará una interrupción de sistema inmediata. El código y los datos privados del usuario empiezan en los 64 KB y se extienden casi hasta los 2 GB. El último fragmento de los 2 GB inferiores contiene algunos contadores y temporizadores del sistema que todos los usuarios comparten bajo un régimen de sólo lectura. El hecho de que sean visibles aquí permite a los procesos acceso a ellos sin el gasto adicional de una llamada al sistema. Los 2 GB superiores contienen el sistema operativo. Todos los procesos de usuario comparten los 2 GB superiores, con excepción de las tablas de páginas, que son exclusivas de cada proceso. De este modo cuando un subproceso efectúa una llamada al sistema, salta al modo de kernel y sigue ejecutándose sin perder su identidad, eliminándose así la necesidad de modificar el mapa de memoria o de desalojar la caché cuando el subproceso entra en el kernel. Lo único que hay que hacer es cambiar a la pila de kernel del subproceso. Para Advanced Server y Datacenter Server se ofrece la opción de un espacio de usuario de 3 GB. Una página dada puede estar en uno de tres estados: libre, reservada o comprometida. Una página libre no se está usando y cualquier referencia a ella causa un fallo de página. Cuando se inicia un proceso, todas sus páginas están libres hasta que el programa y los datos iniciales establecen correspondencia con su espacio de direcciones. Una vez que se establece correspondencia entre el código o los datos y una página, se dice que la página está comprometida. Una página también puede estar en estado reservado, lo que significa que no está disponible para hacerse corresponder mientras no se retire de forma explícita la reserva. Por ejemplo, cuando se crea un nuevo subproceso se reserva 1 MB de espacio de pila en el espacio de direcciones virtual del proceso, pero sólo se compromete una página. Esta técnica implica que la pila puede llegar a crecer hasta 1 MB sin que algún otro subproceso asigne el trozo contiguo de espacio de direcciones virtual que necesita. En Windows 2000 no se asigna una página en el disco a las páginas comprometidas que no tienen un lugar natural en el disco (por ejemplo, las páginas de pila), sino hasta el momento en que se hace necesario paginarlas a disco. Este diseño aumenta la complejidad del sistema porque es posible que los mapas de los archivos de paginación tengan que traerse del disco durante un fallo de página, lo cual podría causar uno o más fallos de página adicionales. La ventaja es que no es necesario asignar espacio en disco para páginas que nunca se paginan a disco. Las páginas libres y reservadas nunca tienen páginas sombra en el disco y las referencias a ellas siempre causan fallos de página. Las páginas sombra en el disco se organizan en uno o más archivos de paginación. Podría haber hasta 16 archivos de paginación, quizá repartidos entre 16 discos individuales, para aumentar el ancho de banda de E/S. Cada uno tiene un tamaño inicial y un tamaño máximo hasta el que puede crecer en caso necesario. El sistema operativo lleva el control de qué página virtual corresponde a qué parte de qué archivo de paginación. En el caso de texto de programa (sólo ejecución), el archivo binario Escuela de Preparación de Opositores E.P.O. v05.01 INFl 7 - SAI 17. Página 20 ejecutable contiene las páginas sombra; para las páginas de datos se usan los archivos de . . , pagmacion. 6.2 Implementaciónde administración de memoria. Windows 2000 maneja un solo espacio de direcciones lineal de 4 GB para cada proceso. No se maneja segmentación. En teoría, el tamaño de página puede ser cualquier potencia de dos, hasta 64 KB. En Pentium el tamaño es fijo, de 4 KB. Además, el sistema operativo en sí puede usar páginas de 4 MB para reducir el espacio que ocupa su tabla de páginas. El administrador de memoria trabaja con procesos y no se ocupa de los subprocesos. Después de todo, son procesos, no subprocesos, los que poseen el espacio de direcciones, y eso es lo que maneja el administrador de memoria. Cuando se asigna una región del espacio de direcciones virtual, el administrador de memoria crea un descriptor de dirección virtual (VAD; Virtual Address Descriptor) que indica el intervalo de direcciones a las que se les ha aplicado correspondencia, el archivo que se usará como almacén de respaldo, y el desplazamiento de la correspondencia de éste, así como el código de protección. Cuando se hace referencia a la primera página, se crea el directorio de tablas de páginas y se inserta en el VAD un puntero a él. De hecho, un espacio de direcciones está definido por completo por la lista de sus VADs. Este esquema maneja espacios de direcciones poco llenos porque las áreas desocupadas entre las regiones con correspondencia no consumen recursos. 6.2.1 Manejo de fallos de página. Windows 2000 no utiliza prepaginación. Cuando se inicia un proceso, ninguna de sus páginas está en la memoria. Todas ellas se traen dinámicamente del disco conforme se generan fallos de página. En cada fallo de página se genera una interrupción de sistema para saltar al kernel, el cual construye un descriptor independiente de la máquina que indica lo que sucedió para el administrador de memoria. Si la página solicitada está dentro de una región comprometida o reservada, el administrador de memoria busca su dirección en la lista de VADs, halla (o crea) la tabla de páginas y busca la entrada pertinente. Las entradas de la tabla de páginas son diferentes, dependiendo de la arquitectura. En la siguiente figura se muestra la entrada de una página con correspondencia de un Pentium. Las páginas sin correspondencia también tienen entradas, pero su formato es un poco diferente. Por ejemplo, si la página sin correspondencia debe llenarse de ceros antes de poder usarse, ese hecho se indica en la tabla de páginas. Q: Página global para ttxt>e tœ pc«.ema U: p. . ~-medo·~ Wt Eacdtura oont.nua (.U.CICht) L.: PéQ,navra.• C4MB> O: NQlna modff,œda W:Se p1rmtta ~ enfa ptc,11• k Ya-, 1UYQ.a:eso a pjgfna V: En!mdade tal:!11de o4g1nas 'dJcta e:~de_,.. hab Escuela de Preparación de Opositores E.P.O. v05.01 INF 17 - SAI 17. Página 21 Los bits más importantes de la entrada de tabla de páginas son los bits A y D. El hardware les asigna su valor e indican si se ha hecho referencia a la página y si se ha escrito en ella, respectivamente, desde la última vez que se pusieron en cero. Hay cinco categorías de fallos de página: 1. La página a la que se hizo referencia no está comprometida. 2. Hubo una violación de la protección. 3. Se ha escrito una página compartida. 4. La pila necesita crecer. 5. La página a la que se hizo referencia está comprometida pero no tiene correspondencia. Los dos primeros casos son errores fatales de los que el proceso que produjo el fallo no puede recuperarse. En el tercer caso la solución es copiar la página en un nuevo marco de página fisico y aplicarle correspondencia de lectura/escritura. El cuarto caso requiere asignar un nuevo marco de página y aplicarle correspondencia en memoria. Sin embargo, las reglas de seguridad exigen que la página esté llena de ceros. Por último, el quinto caso es un fallo de página normal. Se localiza la página y se le aplica correspondencia en memoria. Windows 2000 no lee páginas aisladas del disco; más bien, lee series de páginas consecutivas, de uno a ocho, en un intento por reducir las transferencias de disco. El tamaño de la serie es mayor si se trata de páginas de código, y menor si se trata de páginas de datos. 6.2.2 El algoritmo de reemplazo de páginas. El sistema se esfuerza por mantener páginas libres en memoria, de modo que si se presenta un fallo de página pueda ocuparse de inmediato una página libre sin tener que escribir primero alguna otra en el disco. Como consecuencia, casi todos los fallos de página pueden satisfacerse con, al menos, una operación de disco (leer la página), en vez de dos (escribir una página modificada y luego leer la página requerida). En principio, el mecanismo de paginación se apoya en el concepto de conjunto de trabajo (working set). Cada proceso tiene un conjunto de trabajo, que consiste en las páginas con correspondencia que están en la memoria y a las que es posible el acceso sin generar un fallo de página. El conjunto de trabajo de un proceso dado se describe con dos parámetros: el tamaño mínimo y el máximo. Estos límites no son estrictos; un proceso puede tener en memoria menos páginas que su mínimo o más que su máximo. Todos los procesos empiezan con el mismo mínimo y el mismo máximo, pero pueden cambiar con el tiempo. El mínimo inicial predeterminado está dentro del intervalo de 20 a 50 y el máximo inicial predeterminado está dentro del intervalo de 45 a 345, dependiendo de la cantidad total de RAM. Si ocurre un fallo de página y el conjunto de trabajo es más pequeño que el mínimo, se añade la página. En cambio, si se presenta un fallo de página y el conjunto de trabajo es más grande que el máximo, se expulsa una página del conjunto de trabajo (pero no de la memoria) para que quepa la nueva página. Si el sistema se da cuenta de que un proceso está paginando en forma frenética (y los demás no), podría incrementar el tamaño de su conjunto de trabajo máximo. Sin embargo un proceso no puede ocupar las últimas 512 páginas libres, para dejar espacio por si aparecen procesos nuevos. Escuela de Preparación de Opositores E.P.O. v05.01 INF I7 - SAI 17. Página 22 Cada segundo, un subproceso demonio dedicado al kernel, el administrador de conjuntos de equilibrio, verifica si hay suficientes páginas libres. Si no las hay, inicia el subproceso administrador de conjuntos de trabajo para que examine los conjuntos de trabajo y recupere más páginas. Lo primero que hace el administrador de conjuntos de trabajo es determinar en qué orden examinará los procesos. Los procesos grandes que han estado inactivos durante mucho tiempo se examinan antes que los procesos pequeños activos, y el proceso de primer plano es el último que se examina. Luego, el administrador de conjuntos de trabajo inspecciona los procesos en el orden escogido. Si el conjunto de trabajo actual de un proceso es menor que su mínimo, o si ha incurrido en más de cierto número de fallos de página desde la última inspección, no se hace nada. De lo contrario, se le quitan una o más páginas. El número de páginas a quitar es una función del tamaño total de la RAM, de la escasez de memoria actual, de la relación entre el tamaño actual del conjunto de trabajo y los tamaños máximo y mínimo del proceso, entre otros parámetros. En un sistema monoprocesador, si el bit de referencia de una página está apagado, se incrementa un contador asociado con la página. Sin embargo, si está encendido, el contador se establece a cero. Una vez examinadas todas las páginas, las que tienen los valores más altos en su contador se retiran del conjunto de trabajo. El subproceso sigue examinando procesos hasta recuperar suficientes páginas, y luego se detiene. Si ya realizó una pasada completa por todos los procesos y todavía no ha recuperado suficientes páginas, efectuará otra pasada "recortando" de forma más agresiva e incluso podría reducir los conjuntos de trabajo por debajo de sus tamaños mínimos, si es necesario. En un sistema multiprocesador no se examina el bit de referencia porque, aunque la CPU actual no haya hecho referencia recientemente a la página, alguna otra podría haberlo hecho y examinar los bits de referencia de otra CPU resulta demasiado costoso. Por tanto, se eliminan las páginas más antiguas. Cabe señalar que, en lo concerniente al reemplazo de páginas, el sistema operativo mismo se considera como un proceso: posee páginas y también tiene un conjunto de trabajo, que puede recortarse. Sin embargo, ciertas partes del código y la reserva no paginada están fijas en la memoria y no pueden paginarse a disco. 6.2.3 Administración de memoria física. Cada página en la memoria está en uno o más conjuntos de trabajo, o bien, exactamente en una de las cuatro listas, que se ilustran en la siguiente figura. Las listas de reserva (limpia) y modificada contienen páginas que hace poco se expulsaron de un conjunto de trabajo, todavía están en la memoria y asociadas con el proceso que las estaba usando. La diferencia entre ellas es que las páginas limpias tienen una copia válida en disco y pueden abandonarse cuando se desee, mientras que las páginas modificadas no tienen una copia válida en el disco. La lista libre consiste en páginas limpias que ya no están asociadas con ningún proceso. Las páginas de la lista de páginas en ceros no están asociadas con ningún proceso y además ya se han llenado de ceros. Una quinta lista contiene páginas de RAM físicamente defectuosas que pudieran existir, para asegurarse de que no se usen nunca. Escuela de Preparación de Opositores E.P.O. v05.01 INF 17 - SAI 17. Página 23 . . *tiSSS .. -~ i:.,,111" ,wftlQdl. fil:«•• ., Foncto __ __. -- Cuando el administrador de conjuntos de trabajo quita una página de un conjunto de trabajo, ésta se coloca al fondo de la lista de reserva o de la modificada, dependiendo de su estado de limpieza. Esta transición se indica con (1). Las páginas de ambas listas siguen siendo válidas, de modo que si se presenta un fallo de página y se necesita una de estas páginas, se saca de la lista y se vuelve a colocar en el conjunto de trabajo, sin necesidad de efectuar E/S de disco (2). Cuando termina un proceso, ya no puede generar fallos para recuperar sus páginas no compartidas, así que se colocan en la lista libre (3). Estas páginas ya no están asociadas con ningún proceso. Cada 4 segundos se ejecuta el subproceso intercambiador y busca procesos que no hayan tenido ningún subproceso activo durante cierto número de segundos. Si encuentra procesos así, anula la fijación de sus pilas de kernel y sus páginas se pasan a las listas de reserva o modificadas; esto también se indica con (1). El escritor de páginas con correspondencia y el escritor de páginas modificadas, se activan de forma periódica para ver si hay suficientes páginas limpias. Si no hay suficientes, toman páginas de la parte superior de la lista modificada, las escriben en disco y luego las pasan a la lista de reserva (4). El primer subproceso demonio se encarga de las escrituras a archivos con correspondencia, mientras que el segundo maneja las escrituras a archivos de paginación. El resultado de estas escrituras es transformar páginas modificadas en limpias. Si un proceso elimina la correspondencia de una página, ésta deja de estar asociada con un proceso y puede colocarse en la lista libre (5), siempre que no se trate de una página compartida. Si un fallo de página requiere un marco de página para contener la página que va a leerse, el marco se toma de la lista libre (6), si es posible. No importa si la página todavía contiene información confidencial, porque va a sobrescribirse en su totalidad. Cuando crece una pila se necesita un marco de página vacío y las reglas de seguridad exigen que la página esté llena de ceros. Por este motivo, se ejecuta el subproceso de páginas en ceros, con la prioridad más baja, borrando las páginas que están en la lista libre y pasándolas a la lista de páginas en ceros (7). Siempre que la CPU está inactiva y hay páginas libres, más vale borrarlas porque una página en ceros podría ser más útil que una libre. Para llevar el control de todas las páginas y todas las listas, Windows mantiene una base de datos de marcos de página con tantas entradas como páginas de RAM hay, como se muestra en la siguiente figura. Esta tabla está indexada por número de marco de página física. Las entradas tienen longitud fija, pero se usan diferentes formatos para los distintos tipos de entradas. Las entradas válidas mantienen el estado de la página y Escuela de Preparación de Opositores E.P.O. v05.01 INFI7-SAI17. Página 24 un contador que indica cuántas tablas de páginas apuntan a la página, para que el sistema pueda saber cuando ya no se está utilizando una página. Si una página está en un conjunto de trabajo, se indica en cuál. También hay un puntero a la tabla de páginas que apunta a la página, si existe, un enlace a la siguiente página de la lista (si la hay) y varios campos e indicadores, como lectura en curso, escritura en curso, etcétera. 8 1'4 .. .. - . ..- -· ..~- ..,_..,..., i::i . . . 13 . E-J.. .... l ::!iiii j 10 I Moti,,c.¿ï.; ·:'J . " "'• . 7 ... .. e 9 Mod.il. . - 8 .; .J e utn . X t: U)fe ,.. . • s ui.. ~ 4 !f\OICOI . • ) , ... 14 If 3 ~ - 2 Ett... r: •9!!5! , , .. e lmJ!!Sl ..lt 7 Conclusiones. Hemos estudiado la administración de la memoria. Los sistemas más sencillos no realizan intercambio alguno. Una vez que se carga un programa en memoria, permanece ahí hasta terminar. Algunos sistemas operativos sólo permiten que, en cada momento, exista un único proceso en la memoria, a la vez que otros permiten Ia multiprogramación. El siguiente paso es el intercambio. Cuando se utiliza, el sistema puede controlar más procesos de los que caben en la memoria. Los procesos para los que no existe espacio se intercambian con el disco. Se puede llevar un registro del espacio libre en memoria y en disco mediante un mapa de bits, una lista de huecos o un sistema asociado. Con frecuencia, las computadoras más avanzadas tienen cierta forma de memoria virtual. En su forma más simple, el espacio de direcciones de cada proceso se divide en bloques de tamaño uniforme llamados páginas, las cuales se pueden colocar dentro de cualquier marco para página disponible en memoria. Cuando las tablas de páginas son muy grandes, se puede utilizar un esquema de paginación con varios niveles para que las páginas se paginen a sí mismas. Para mejorar el rendimiento, casi todas las computadoras que soportan la paginación tienen una memoria asociativa para una relación rápida del número de página virtual con el número del marco fisico. La tabla de páginas se consulta sólo en caso de algún faltante. Se conocen muchos algoritmos para el reemplazo de páginas. Dos de los mejores y que son realizables son el del reloj y el de maduración. Los algoritmos de paginación se pueden modelar en forma teórica mediante el concepto de distancias de la cadena, el cual permite hacer ciertas predicciones. Una alternativa a la paginación pura es la segmentación, con o sin segmentos paginados. Escuela de Preparación de Opositores E.P.O. v05.0l INFI 7 - SAI 17. Página 25 El modelo de memoria en UNIX consta de un segmento de texto, de datos y de pila para cada proceso. La administración de la memoria se realizaba mediante intercambio, pero hoy en día se utiliza paginación. El mapa central mantiene un registro del estado de cada página y el demonio para paginación utiliza un algoritmo de reloj para mantener un número suficiente de páginas libres. La administración de memoria en MS-DOS está relacionada con cuatro regiones independientes: la memoria convencional (por debajo de 640K), la memoria superior (entre 640K y IM), memoria alta (los 64K justo por encima de IM) y la memoria extendida (por encima de IM). Cada una de ellas tiene distintas propiedades y se utiliza de manera distinta. Sin embargo, los programas ordinarios están restringidos a la memoria convencional, por lo que no pueden exceder los 640K. La sobreposición y la memoria expandida son dos de las técnicas que se utilizan para rebasar este límite en ciertos sentidos.