316

Sistemas operativos. Una visión aplicada

Tabla 5.1 Comparativa de los esquemas de gestión de la memoria del sistema. Esquema de gestión Registros límite Registro base y límite Segmentación Paginación Seg. paginada global Seg. paginada local SASOS

Resolución/R.módulos Compilador/montador Compilador/montador Compilador/montador Compilador/montador Compilador/montador Compilador/montador Compilador/montador

R. regiones R. procesos Montador Cargador Montador MMU MMU (seg) Montador MMU (pág) MMU (seg) MMU (seg) MMU (pág) Montador Cargador

R. global ʊ ʊ ʊ ʊ MMU (pág) ʊ MMU (pág)

Aclaración 5.7. En algunas arquitecturas, las direcciones que se usan para acceder a memoria (llamadas capabilities), además de la referencia a la posición de memoria propiamente dicha, incluyen uno o más bits de información de protección, que, entre otras cosas, identifican que se trata de una dirección de acceso a memoria. El aspecto interesante de las capabilities es que sólo se pueden modificar estando en modo privilegiado. Por tanto, sólo en dicho modo se pueden generar direcciones válidas de acceso a memoria. Un proceso podrá usar las posiciones de memoria que le ha asignado el sistema operativo, puesto que éste le ha proporcionado las capabilities requeridas para acceder a las mismas. Sin embargo, no podrá acceder a otras direcciones, puesto que la unidad de control del procesador asegura que una capability sólo se puede modificar en modo privilegiado. El mecanismo de capabilities asegura la protección requerida, permitiendo usar direcciones físicas directamente, lo que elimina el problema de las autorreferencias. La reubicación necesaria se puede realizar por software. El único problema de este mecanismo, que ha limitado considerablemente su impacto, es que requiere un procesador con una arquitectura muy específica. Para terminar esta sección, se plantea la tabla 5.1, que sirve de recapitulación de la misma y muestra una comparativa de los distintos esquemas de gestión de memoria estudiados, mostrando cómo se llevan a cabo las distintas etapas identificadas en la sección 5.2.5.

5.5. MEMORIA VIRTUAL En prácticamente todos los sistemas operativos de propósito general actuales se usa la técnica de memoria virtual. Hasta el momento, por motivos pedagógicos, se han presentado los diversos esquemas de memoria sin apenas hacer referencia a esta técnica. En esta sección se estudiará esta técnica mostrando cómo se integra con estos esquemas de gestión de memoria. En el primer capítulo ya se presentaron los fundamentos de la memoria virtual, explicando aspectos tales como la jerarquía de memoria o la proximidad de referencias, por lo que no se volverá a incidir en los mismos. Como se apreciará a lo largo de esta sección, la memoria virtual resuelve dos de los objetivos del sistema de memoria identificados al principio del capítulo: ejecutar más procesos de los que caben en la memoria principal, y ejecutar un proceso cuyo mapa no cabe en la memoria. Antes de la aparición de la memoria virtual, esas dos necesidades ya existían y se intentaban resolver de la mejor manera posible, teniendo en cuenta la tecnología presente por entonces. Esta sección, por tanto, comenzará presentando las técnicas de intercambio y de overlays como precedentes de la memoria virtual. A continuación, se analizarán las diversas políticas de administración de la memoria virtual, especialmente, las estrategias de reemplazo y las políticas de reparto de la memoria entre los procesos.

5.5.1. Intercambio Como se comentó previamente, la técnica del intercambio (swapping) significó en su momento una manera de permitir que en los sistemas del tiempo compartido existieran más procesos de los que caben en memoria.

Gestión de memoria

317

Se puede considerar que se trata de un mecanismo antecesor de la memoria virtual. En este apartado se presentarán de forma breve los fundamentos de esta técnica. El intercambio se basa en utilizar un disco o parte de un disco como respaldo de la memoria principal. Esta zona de almacenamiento se denomina dispositivo de swap. Cuando no caben en memoria todos los procesos activos (por ejemplo, debido a que se ha creado uno nuevo), se elige un proceso residente y se copia en swap su imagen en memoria. El criterio de selección puede tener en cuenta aspectos tales como la prioridad del proceso, el tamaño de su mapa de memoria, el tiempo que lleva ejecutando y, principalmente, su estado. Es preferible expulsar (swap out) procesos que estén bloqueados. Cuando se expulsa un proceso, no es necesario copiar toda su imagen al dispositivo de swap. Los huecos en el mapa no es preciso copiarlos, ya que su contenido es intrascendente. Tampoco se tiene que copiar el código, puesto que se puede volver a recuperar directamente del ejecutable. Evidentemente, un proceso expulsado tarde o temprano debe volver a activarse y cargarse en memoria principal (swap in). Sólo se deberían volver a cargar aquellos procesos que estén listos para ejecutar. Esta readmisión en memoria se activará cuando haya espacio de memoria disponible (por ejemplo, debido a que se ha terminado un proceso) o cuando el proceso lleve un cierto tiempo expulsado. Téngase en cuenta que al tratarse de un sistema de tiempo compartido, se debe repartir el procesador entre todos los procesos. Por ello, en numerosas ocasiones hay que expulsar un proceso para poder traer de nuevo a memoria a otro proceso que lleva expulsado un tiempo suficiente. La estrategia que decide cuándo expulsar un proceso a swap y cuándo reincorporarlo a memoria se corresponde con la planificación a medio plazo presentada en el capítulo 4. En cuanto al dispositivo de swap, hay dos alternativas en la asignación de espacio: • Con preasignación: Al crear el proceso ya se reserva espacio de swap suficiente para albergarlo. Si el proceso nunca se expulsa, se desperdicia el espacio asignado. • Sin preasignación. Sólo se reserva espacio de swap cuando se expulsa el proceso. Puede haber problemas si se intenta expulsar un proceso a swap para traer a otro proceso y no hay espacio en el dispositivo. Un último aspecto a tener en cuenta es que no debería expulsarse un proceso mientras se estén realizando operaciones de entrada/salida por DMA vinculadas a su imagen de memoria, ya que provocaría que el dispositivo accediera al mapa de otro proceso.

5.5.2. Overlays En los tiempos en los que todavía no se había propuesto la técnica de memoria virtual y las memorias tenían una capacidad limitada, se presentaba con cierta frecuencia el problema de que un determinado programa no cupiera en memoria. Para resolver dentro de lo posible este problema, se ideó la técnica de los overlays. Se trataba de un esquema que no era transparente al programador, puesto que éste tenía que determinar si ciertos módulos de su programa no requerían estar simultáneamente en memoria en tiempo de ejecución y que, por tanto, podrían usar la misma zona de memoria en distintas fases de ejecución del programa. El programador usaba un lenguaje de definición de overlays para notificar al montador esta información. El montador generaba un fichero ejecutable en el que incluía automáticamente código para cargar y descargar los módulos del programa. En la llamada desde un módulo a una función definida en otro módulo, el montador incluía código que comprobaba si el módulo destino estaba ya cargado en memoria. En caso de no estarlo, el código incluido por el montador cargaba ese módulo, usando para ello, si es necesario, el espacio ocupado por otro módulo cuya presencia no se requiere según indica la información suministrada al montador.

5.5.3. Fundamento de la memoria virtual Como se estudió en el primer capítulo, la memoria en un sistema está organizada como una jerarquía de niveles de almacenamiento entre los que se mueve la información dependiendo de las necesidades de los procesos

318

Sistemas operativos. Una visión aplicada

en un determinado instante. La técnica de memoria virtual se ocupa de la transferencia de información entre la memoria principal y la secundaria. La memoria secundaria está normalmente soportada en un disco (o partición). Dado que, como se verá más adelante, la memoria virtual se implementa sobre un esquema de paginación, este dispositivo se denomina dispositivo de paginación. También se usa el término dispositivo de swap. Aunque este término proviene de la técnica del intercambio, por tradición se usa frecuentemente y se utilizará indistintamente en esta exposición. En cualquier caso, hay que resaltar que la memoria secundaria no sólo está formada por el dispositivo de paginación, sino que también forma parte de la misma el sistema de ficheros. Téngase en cuenta que, como se analizará en esta sección, al ser expulsadas, algunas páginas se transferirán al dispositivo de paginación, mientras que otras lo harán al sistema de ficheros. Es importante recordar en este punto que, como se explicó en el primer capítulo, el buen rendimiento del sistema de memoria virtual está basado en que los procesos presentan la propiedad de proximidad de referencias. Esta propiedad permite que un proceso genere muy pocos fallos aunque tenga en memoria principal sólo una parte de su imagen de memoria (conjunto residente). El objetivo del sistema de memoria virtual es intentar que la información que está usando un proceso en un determinado momento (conjunto de trabajo) esté residente en memoria principal, es decir, que el conjunto residente del proceso contenga su conjunto de trabajo. Algunos beneficios del uso de memoria virtual son los siguientes: • Se produce un aumento del grado de multiprogramación al no ser necesario que todo el mapa de memoria de un proceso esté en memoria principal para poder ejecutarlo. Este aumento implica una mejora en el rendimiento del sistema. Sin embargo, como se analizó en el segundo capítulo, si el grado de multiprogramación se hace demasiado alto, el número de fallos de página se dispara y el rendimiento del sistema baja drásticamente. Esta situación se denomina hiperpaginación y se estudiará más adelante. • Se pueden ejecutar programas más grandes que la memoria principal disponible. Hay que resaltar que el objetivo de la memoria virtual no es acelerar la ejecución de un programa. En algunos casos, puede hacerlo, especialmente, en situaciones donde el proceso no accede a todo su código o a todos sus datos durante su ejecución, no siendo necesario, por tanto, leerlos del ejecutable. Sin embargo, en otras ocasiones, puede incluso ralentizar la ejecución, debido a la sobrecarga asociada a las transferencias entre la memoria principal y la secundaria. Esto hace que esta técnica no sea apropiada para sistemas de tiempo real, además de por hacer que sea poco predecible el comportamiento de los procesos. Como se ha analizado en los apartados anteriores, la memoria virtual se construye generalmente sobre un esquema de paginación, ya sea paginación simple o segmentación paginada. Por tanto, las unidades de información que se transfieren entre la memoria principal y la secundaria son páginas. Las transferencias desde la memoria secundaria hacia la principal se realizan normalmente bajo demanda (paginación por demanda). Cuando un proceso necesita acceder a una página que no está en memoria principal (a lo que se denomina fallo de página), el sistema operativo se encarga de transferirla desde la memoria secundaria. Si al intentar traer la página desde memoria secundaria, se detecta que no hay espacio en la memoria principal (no hay marcos libres), será necesario expulsar una página de la memoria principal y transferirla a la secundaria. Por tanto, las transferencias desde la memoria principal hacia la secundaria se realizan normalmente por expulsión. El algoritmo para elegir qué página debe ser expulsada se denomina algoritmo de reemplazo y se analizará más adelante. Dado que se está usando la paginación para construir un esquema de memoria virtual, se puede usar indistintamente el término de dirección lógica y el de dirección virtual para referirse a las direcciones que genera un programa. Para construir un esquema de memoria virtual sobre un procesador que ofrezca paginación, se utiliza el bit de la entrada de la tabla de páginas que indica si la página es válida. Estarán marcadas como inválidas todas las entradas correspondientes a las páginas que no están residentes en memoria principal en ese instante. Dado que se utiliza el bit validez para marcar la ausencia de una página y este mismo bit también se usa para indicar que una página es realmente inválida (una página que corresponde a un hueco en el mapa), es necesario que el sistema operativo almacene información asociada a la página para distinguir entre esos dos casos. En caso de que la página sea válida pero no residente, el sistema operativo también deberá guardar información de en qué bloque de la memoria secundaria está almacenada la página. De esta forma, cuando se

Gestión de memoria

319

Fichero Fallo Memoria

Expulsión y modificada

Figura 5.67 Ciclo de vida de una página de una región compartida con soporte. produzca un acceso a una de estas páginas, se producirá una excepción (fallo de página) que activará al sistema operativo, que será el encargado de traerla desde la memoria secundaria.

5.5.4. Ciclo de vida de una página Antes de analizar los distintos aspectos vinculados con la memoria virtual, es conveniente analizar cómo evoluciona una página en un sistema con memoria virtual, dependiendo de a qué tipo de región pertenece, fijándose en dos características de la misma: si es privada o compartida y si tiene soporte o es anónima. • Página de una región compartida con soporte en un fichero. Cada vez que se produzca un fallo al acceder a esta página por no estar presente en memoria principal, habrá que leerla del fichero que la contiene. Por otra parte, al ser expulsada estando modificada, habrá que volverla a escribir en el fichero, puesto que los cambios sobre una región compartida deben revertir al fichero. La figura 5.67 muestra cómo es la evolución de este tipo de páginas. • Página de una región privada con soporte en un fichero. Mientras no se modifique la página, estará vinculada al soporte y todos los fallos se servirán leyendo del fichero. En cuanto se modifique una vez, queda desvinculada del soporte original, y al ser expulsada, se escribirá en swap. Los fallos posteriores se servirán de swap, y las expulsiones que encuentren la página modificada la escribirán en swap. Esta es la esencia de una región privada: los cambios sobre la misma no afectan al soporte original. Para entender la utilidad de este modo de operación, recuerde que se utiliza con la región de datos con valor inicial de un programa o de una biblioteca dinámica. Después de acceder a una variable global con valor inicial para modificarla, cuando sea expulsada la página que la contiene, no podemos volver a escribirla en el fichero ejecutable, puesto que estaríamos cambiando el propio programa. La figura 5.68 muestra la evolución de una página de estas características. • Página de una región anónima, ya sea privada o compartida. Por motivos de seguridad, cuando se accede por primera vez a una página de este tipo, se rellena con ceros el marco de página usado para la misma, no requiriendo un acceso a disco. Si la página se expulsa sin ser modificada (lo cual es bastante improbable puesto que, al no tener un valor inicial, lo más habitual es que el primer acceso sea de escritura), no es necesario escribirla en el disco. El siguiente fallo volverá a rellenar el marco elegido con ceros. En cuanto se modifique una vez la página, al ser expulsada, se escribirá en swap. Los fallos posteriores se servirán de swap y las expulsiones que encuentren la página modificada la escribirán en swap. Recuerde que la región de datos sin valor inicial de un programa o de una biblioteca dinámica son de este tipo, teniendo, además, carácter privado. También entra en esta categoría una zona de memoria compartida que no esté basada en un fichero. La figura 5.69 muestra la evolución de una página de este tipo.

5.5.5. Políticas de administración de la memoria virtual Como se analizó en el primer capítulo, el modo de interacción entre dos niveles de la jerarquía queda definido por un conjunto de políticas que establecen de qué forma se realizan las transferencias entre ambos. En el

320

Sistemas operativos. Una visión aplicada Fichero

Fallo (mientras no modificada una vez) Memoria

Fallos y expulsiones una vez modificada

Expulsión y modificada

Swap

Figura 5.68 Ciclo de vida de una página de una región privada con soporte. caso de la memoria virtual, los niveles implicados son la memoria principal y la secundaria, y las políticas que definen el comportamiento de un sistema de memoria virtual son las siguientes: • Política de localización. Permite localizar una determinada página dentro de la memoria secundaria. • Política de extracción. Define cuándo se transfiere una página desde la memoria secundaria a la principal. • Política de ubicación. Si hay varios marcos libres, establece cuál de ellos se utiliza para almacenar la página que se trae a memoria principal. • Política de reemplazo. En caso de que no haya marcos libres, determina qué página debe ser desplazada de la memoria principal para dejar sitio a la página entrante. • Política de actualización. Rige cómo se propagan las modificaciones de las páginas en memoria principal a la memoria secundaria. • Política de reparto de espacio entre los procesos. Decide cómo se reparte la memoria física entre los procesos existentes en un determinado instante. Sobre las políticas de ubicación y de actualización hay poco que comentar. Con respecto a la primera, en principio, se puede usar cualquier marco libre para albergar una página leída de la memoria secundaria. Sin embargo, algunos sistemas operativos intentan seleccionar el marco de manera que se mejore el rendimiento de la memoria caché. Esta técnica, denominada coloración de páginas, intenta que las páginas residentes en memoria en un momento dado estén ubicadas en marcos cuya distribución en las líneas de la caché sea lo más uniforme posible. En cuanto a la política de actualización, dada la enorme diferencia entre la velocidad de transferencia de la memoria principal y la de la secundaria, no es factible usar una política de actualización inmediata, utilizándose, por tanto, una política de escritura diferida: sólo se escribirá una página a memoria secundaria cuando sea expulsada de la memoria principal estando, además, modificada. En las próximas secciones se analizarán las cuatro políticas restantes.

Fallo (mientras no modificada una vez)

Rellenar con ceros Memoria

Expulsión y modificada

Fallos y expulsiones una vez modificada

Swap

Figura 5.69 Ciclo de vida de una página de una región anónima.

Gestión de memoria

321

Fichero F Swap (SW1) 0 8192 R-X Comp. F Bl. inicial 0 8192 8192 RW- Privada F Bl. inicial 2

Mapa de memoria de P1 0 8192 16384 20480

BCP de P1

Región 1 (R-X) Región 2 (RW-)

t. de regiones

16384 4096 RW- Privada Anónima

Fichero DVI 1

Bloq. 0 Bloq. 1 Bloq. 2 Fichero3 Bloq.

.........

.........

Cód. 0 Cód. 1 DVI 0

Memoria Marco 0 Marco 1

t. páginas

Región 3 (RW-) ......... .........

00004 V R-X 00000 I 000 00001 I SW1 00000 I 000 00000 I 000 00000 I 000 .........

Página 0 de P1 .........................

Marco 2 Marco 3 Marco 4 ........

Figura 5.70 Posibles ubicaciones de una página.

5.5.6. Política de localización Como se comentó al principio de esta sección, la paginación por demanda se basa en hacer creer a la MMU que la página no residente es inválida para que produzca una excepción de fallo de página cuando se acceda a la misma. De esta manera, el sistema operativo puede activarse para tratar la excepción y traer la página de memoria secundaria. Sin embargo, es necesario que el sistema operativo pueda saber si la página realmente es válida, y, en caso de serlo, cómo localizarla. Con respecto a la determinación de la validez, la mayoría de los sistemas operativos consultan la tabla de regiones buscando en qué región está englobada la dirección de fallo. Dado que un proceso puede tener un número elevado de regiones, para agilizar la operación de comprobar si la dirección es válida, la tabla de regiones se organiza como una estructura de datos que permita una búsqueda eficiente y elimine la necesidad de un recorrido lineal de la tabla. Habitualmente, se utiliza un árbol binario ordenado por la dirección de comienzo de cada región. De esta forma, el tiempo de búsqueda es logarítmico con respecto al número de regiones del proceso en vez de lineal. Además, esta estructura permite realizar eficientemente operaciones de inserción y borrado de regiones. En caso de que la dirección que provoca el fallo no encaje en ninguna región, se trata de una página inválida, que corresponde a un hueco en el mapa de memoria del proceso, por lo que se abortará el proceso o se le mandará una señal. En el ejemplo mostrado en la figura 5.70, la sexta entrada de la tabla de páginas se corresponde con un hueco en el mapa del proceso. Si el proceso intenta acceder a una dirección incluida en ese hueco, como la 20500, se producirá una excepción de fallo de página, dentro de cuyo tratamiento el sistema operativo determinará que el acceso es inválido, al no estar incluida en ninguna región la dirección de fallo. Para entender el proceso de localización, hay que analizar qué cuatro casos se pueden presentar para una página válida, como se muestra en la figura 5.70. • Página residente en memoria. Se trata de una página a la que se ha accedido y en este momento está residente en memoria. La entrada de la tabla de páginas identifica al marco que contiene la página. La primera entrada de la tabla de páginas de la figura se corresponde con este caso, estando almacenada en el marco 4.

322

Sistemas operativos. Una visión aplicada

• Página no residente almacenada en un fichero. Corresponde a una página no residente cuyo contenido está almacenado en un bloque de un fichero. Cuando se produzca un fallo, el sistema operativo localizará la región a la que pertenece la página y podrá comprobar en el descriptor de la región que se trata de una región con soporte en un fichero, obteniendo información acerca de qué fichero se trata y a qué parte del mismo corresponde la región. Calculando el desplazamiento de la página con respecto al inicio de la región y sabiendo en qué posición del fichero comienza la región, se puede determinar en qué bloque del fichero se ubica la página. La segunda y cuarta entradas de la tabla de páginas de la figura son ejemplos de esta situación. La segunda entrada está vinculada a la región 1. El descriptor de esa región indica que se trata de una región con soporte en el fichero F, estando ubicada al principio del mismo. Dado que se trata de la segunda página de esa región, habrá que leer el bloque 1 del disco para obtener su contenido. En cuanto a la cuarta entrada, está incluida en la región 2, cuyo descriptor indica que también tiene soporte en el fichero F, pero, comenzando en el bloque 2 del mismo. Como se trata de la segunda página de esta región, habrá que leer el bloque 3 del disco para obtener su contenido. • Página no residente de tipo anónima. Se trata de una página no residente perteneciente a una región sin soporte. Cuando se produzca un fallo al acceder a esta página y se detecta que la región es de este tipo, basta con buscar un marco libre y, por motivos de seguridad, rellenarlo con ceros. La quinta entrada de la figura 5.70 corresponde a una página de este tipo. Cuando se produzca un fallo al intentar acceder a la misma, se detectará que pertenece a una región anónima y se procederá a rellenarla con ceros. Es interesante resaltar que en el sistema operativo Linux, en el inicio del sistema y durante todo el tiempo que está arrancado, se reserva un marco de página de sólo lectura relleno con ceros. De esta forma, en vez de rellenar la página con ceros explícitamente, se comparte, usando COW, que será explicado más adelante, hasta que el programa haga alguna modificación sobre la misma. • Página en swap. Como se explicó anteriormente, las páginas de las regiones sin soporte y de las regiones privadas, una vez modificadas, si se expulsan, son escritas en el dispositivo de paginación. En este caso, la información de ubicación de la página en el disco no puede almacenarse en el descriptor de la región, a no ser que habilitemos espacio para cada una de las páginas de la misma. En su lugar, la mayoría de los sistemas operativos optan por almacenar la información de ubicación en el swap dentro de la propia entrada de la tabla de páginas. Esta información suele consistir en un identificador del dispositivo de swap, ya que, normalmente, se permiten múltiples dispositivos de swap en el sistema, junto con un número de bloque dentro del dispositivo. Nótese que, dado que cuando una entrada de la tabla de páginas es inválida el valor de los campos de la misma es intrascendente, se aprovecha para almacenar la información de swap en esos campos. La tercera entrada de la tabla de páginas de la figura 5.70 corresponde a este caso. Se trata de una página de una región privada con soporte en fichero que ya ha sido modificada alguna vez y que, por tanto, está vinculada al swap. Cuando se produzca un fallo sobre esta página, después de realizar la validación de la dirección, se detectará que la entrada de la tabla de páginas tiene un valor distinto de cero (en los demás casos de páginas válidas pero no residentes, se habrán rellenado con ceros todos los campos de la entrada de la tabla de páginas). Se usará el valor almacenando en la entrada (en este caso, dispositivo SW1 y bloque 1 del mismo) para saber qué bloque leer.

5.5.7. Política de extracción La memoria virtual, en su forma ortodoxa, opera bajo demanda: sólo se trae a memoria principal una página cuando el proceso accede a la misma. Sin embargo, casi todos los sistemas operativos implementan algún tipo de agrupamiento de páginas o de lectura anticipada de páginas, de manera que cuando se produce un fallo de página, no sólo se trae a memoria la página involucrada, sino también algunas páginas próximas a la misma, puesto que, basándose en la propiedad de proximidad de referencias que caracteriza a los programas, es posible que el proceso las necesite en un corto plazo de tiempo. Estas técnicas suelen englobarse bajo el término de prepaginación. La efectividad de las mismas va a depender de si hay acierto en esta predicción,

Gestión de memoria

323

es decir, si finalmente las páginas traídas van a ser usadas, puesto que, en caso contrario, se ha perdido tiempo en traerlas, expulsando, además, de la memoria principal a otras páginas que podrían haber sido más útiles. Hay que resaltar que en el sistema de ficheros también se utilizan técnicas de lectura anticipada, lo cual no puede sorprender por la fuerte interacción, y progresiva fusión, entre estos dos componentes. Dado que en la fase de arranque de un programa es donde más se hace patente la sobrecarga de la memoria virtual, al producirse numerosos fallos mientras el conjunto de trabajo del programa va cargándose en memoria, en algunos sistemas operativos se realiza un seguimiento de los primeros segundos de la ejecución del programa, guardando información sobre los fallos de página que provoca. De esta manera, cuando arranca nuevamente un programa, se puede realizar una lectura anticipada dirigida de las páginas que probablemente va a usar el mismo durante su fase inicial. Volviendo a la paginación por demanda, que es la médula espinal de la memoria virtual, la mayor parte de la lógica que controla esta técnica está articulada alrededor de la rutina del tratamiento del fallo de página. A continuación, se analizan con más detalle las operaciones vinculadas con un fallo de página. Tratamiento del fallo de página La paginación por demanda está dirigida por la aparición de excepciones de fallo de página que indican al sistema operativo que debe traer una página de memoria secundaria a primaria, puesto que un proceso la requiere. A continuación, se especifican los pasos típicos en el tratamiento de un fallo de página: • La MMU del procesador produce una excepción, dejando, habitualmente, en un registro especial la dirección que provocó el fallo. • Se activa el sistema operativo que comprueba si se trata de una dirección correspondiente a una página realmente inválida o se corresponde con una página ausente de memoria. Para ello, como se comentó previamente, accederá a la tabla de regiones para encontrar a qué región pertenece la dirección que produjo el fallo. Si no pertenece a ninguna, la página es inválida, por lo que se aborta el proceso o se le manda una señal. En caso contrario, se realizan los pasos que se describen a continuación. Evidentemente, si la dirección es del sistema y el proceso estaba en modo usuario cuando se produjo el fallo, será también inválida. • Se consulta la tabla de marcos para buscar uno libre. • Si no hay un marco libre, se aplica el algoritmo de reemplazo para seleccionar la página que se expulsará. El marco seleccionado se desconectará de la página a la que esté asociado poniendo como inválida la entrada correspondiente. Si la página está modificada, previamente hay que escribir su contenido a la memoria secundaria: ⎯ Si la página pertenece a una región de tipo compartida y con soporte en fichero, hay que escribirla en el bloque correspondiente del fichero. ⎯ En el resto de los casos, hay que escribirla en swap, almacenándose en la entrada de la tabla de páginas la identificación del bloque de swap que contiene la página. • Una vez que se obtiene el marco libre, ya sea directamente o después de una expulsión, se inicia la carga de la nueva página sobre el marco y, al terminar la operación, se rellena la entrada correspondiente a la página para que esté marcada como válida y apunte al marco utilizado. La localización de la página se realizará tal como se explicó en el apartado anterior. Téngase en cuenta que, en el peor de los casos, un fallo de página puede causar dos operaciones de entrada/salida al disco. En contraste, puede no haber ninguna operación sobre el disco si hay marcos libres o la página expulsada no está modificada y, además, la página que causó el fallo se corresponde con una región anónima que todavía no se ha modificado ninguna vez. Para terminar, es conveniente realizar algunas consideraciones sobre el caso de que se produzca un fallo de página cuando el proceso estaba en modo sistema: • Si la dirección de fallo corresponde a una dirección lógica de usuario y se estaba ejecutando una llamada al sistema, el fallo se produce debido a que se ha accedido al mapa de usuario del proceso para leer o escribir algún parámetro de la llamada. El tratamiento del fallo es el habitual (comprobar si está incluido en alguna región, buscar un marco libre, etc.)

324

Sistemas operativos. Una visión aplicada 0 8192 R-X Comp. F Bl. inicial 0 Memoria

8192 8192 RW- Privada F Bl. inicial 2

BCP de P1

.............

Tablas de páginas de segundo nivel V V

t. de regiones

I

t. páginas

I V I

Tabla de páginas de primer nivel

I

I I

I

I I

Figura 5.71 Creación de tablas de páginas por demanda. • En caso de que la dirección de fallo corresponda a una dirección lógica de usuario y se estuviera ejecutando una interrupción, se trataría de un error en el código del sistema operativo, puesto que, dado que una interrupción tiene un carácter asíncrono y no está directamente vinculada con el proceso en ejecución, no debe acceder al mapa de usuario del proceso en ninguna circunstancia. El tratamiento sería el habitual ante un error en el sistema operativo (podría ser, por ejemplo, sacar un mensaje por la consola y realizar una parada ordenada del sistema operativo). • Si la dirección de fallo es una dirección lógica de sistema, a su vez, podrían darse varios casos: ⎯ Si se trata de un sistema operativo que permite que páginas del sistema se expulsen a disco, se comprobaría si la dirección corresponde a una de esas páginas y, si es así, se leería de disco. ⎯ Si se usa un procesador que tiene una tabla única para direcciones de usuario y de sistema, y en el que, por tanto, se duplican las entradas correspondientes al sistema operativo en las tablas de páginas de todos los procesos, el fallo puede deberse a que se ha añadido una nueva entrada del sistema en la tabla de un proceso, pero no se ha propagado a los restantes. De esta forma, la propagación de este cambio se hace también por demanda, no tratándose de un error. ⎯ En todos los demás casos, se correspondería con un error en el código del sistema operativo. Creación de tablas de páginas por demanda Si se analiza el proceso de localización de las páginas explicado previamente, se puede apreciar en el mismo que las entradas de la tabla de páginas sólo se usan cuando las páginas están residentes, o cuando están almacenadas en swap, siendo la tabla de regiones el elemento clave de la gestión. Basándose en este hecho, se puede extender la política de operación bajo demanda a la propia creación de las tablas de páginas intermedias requeridas en los sistemas de paginación multinivel. De la misma manera que cuando se crea una región en un sistema con memoria virtual no es necesario asignarle marcos hasta que no se acceda a las páginas de la región, como se analizará en la sección 5.5.14, se puede diferir la creación de las tablas de páginas intermedias requeridas por la región hasta que se produzca ese acceso. De esta forma, el proceso inicialmente sólo dispone de la tabla de páginas de nivel superior con todas las entradas marcadas como inválidas. Cuando se produce un fallo y se detecta que las tablas de páginas intermedias requeridas por esa página no se han creado todavía, se reserva memoria para las mismas en ese momento, iniciándolas como inválidas. En la figura 5.71 se muestra un ejemplo de uso de este mecanismo. En el mismo, el proceso sólo ha accedido a dos páginas. El primer acceso provocó un fallo que se produ-

Gestión de memoria

325

jo en la tabla de primer nivel. Una vez que se comprueba que la dirección es válida usando la tabla de regiones, se reserva la tabla de segundo nivel, además del propio marco que alojará la página. El segundo acceso ha provocado un fallo en la tabla de segundo nivel, por tanto, sólo requiere reservar el marco para la página. Con este mecanismo, la tabla de regiones es el elemento conductor del proceso y sólo es necesario tener desplegadas las tablas de páginas para las páginas residentes, lo cual resulta especialmente beneficioso para procesos con un espacio de direcciones disperso. Realmente, con el esquema que hemos planteado, también haría falta tener desplegadas las tablas si contienen entradas que se refieren a bloques de swap, aunque este último requisito podría eliminarse si se almacena esta información en otra estructura de datos, como, por ejemplo, la tabla de regiones.

5.5.8. Política de reemplazo Una de las políticas principales de un sistema de memoria virtual, y una de las que puede afectar más a su rendimiento, es la que determina qué página expulsar cuando hay que traer otra de memoria secundaria y no hay espacio libre. Este mismo problema se presenta en todos los niveles de la jerarquía y, aunque, en cierta medida, hay similitudes, en cada nivel se presentan aspectos específicos debido a las diferencias intrínsecas entre los distintos componentes de memoria usados en la jerarquía, en cuanto a su velocidad y capacidad. Por otra parte, hay que resaltar que el problema de gestionar la transferencia de información entre la memoria principal y el disco no se restringe al sistema de memoria virtual, sino que aparece en la gestión de la caché del sistema de ficheros, así como en los sistemas gestores de bases de datos. Aunque muchos algoritmos usados en estos ámbitos son similares a los utilizados en la memoria virtual, hay que tener en cuenta que existe una importante diferencia entre el modo de operación del sistema de ficheros, o de un gestor de base de datos, y el sistema de memoria. En los primeros, existe una petición explícita por parte de la aplicación para acceder a la información, pudiendo, por tanto, el sistema operativo (o el gestor de base de datos) tener control sobre qué accesos se van realizando. En cambio, en la memoria, el proceso accede directamente a la misma sin que el sistema operativo sea consciente de ello. El sistema operativo sólo toma control cuando se produce un fallo de página. Existen numerosos trabajos, tanto teóricos como experimentales, sobre algoritmos de reemplazo de páginas. En esta sección se describirán los algoritmos de reemplazo más habituales, intentando mostrar las últimas tendencias en este campo que, después de un cierto periodo con pocas innovaciones, ha presentando importantes contribuciones en los últimos tiempos. Las estrategias de reemplazo se pueden clasificar en dos categorías: reemplazo global y reemplazo local. Con una estrategia de reemplazo global se puede seleccionar para satisfacer el fallo de página de un proceso un marco que actualmente tenga asociada una página de otro proceso. Esto es, un proceso puede quitarle un marco de página a otro. La estrategia de reemplazo local requiere que para servir el fallo de página de un proceso sólo puedan usarse marcos de páginas libres o marcos ya asociados al proceso. Todos los algoritmos que se describirán a continuación pueden utilizarse tanto para estrategias globales como locales. Cuando se aplica un algoritmo determinado utilizando una estrategia global, el criterio de evaluación del algoritmo se aplicará a todas las páginas en memoria principal. En el caso de una estrategia local, el criterio de evaluación del algoritmo se aplica sólo a las páginas en memoria principal que pertenecen al proceso que causó el fallo de página. La descripción de los algoritmos, por tanto, se realizará sin distinguir entre los dos tipos de estrategias. El objetivo básico de cualquier algoritmo de reemplazo es minimizar la tasa de fallos de página, intentando además que la sobrecarga asociada a la ejecución del algoritmo sea tolerable y que no se requiera una MMU con características específicas. En principio, de manera intuitiva, parece razonable pensar en tres factores a la hora de diseñar un algoritmo de estas características: • Tiempo de residencia. Tener en cuenta el tiempo que lleva la página presente en memoria a la hora de expulsar una página. Como se analizará a continuación, no es un buen criterio. • Frecuencia de uso. Basarse en cuántas veces se ha accedido a una página para decidir cuál reemplazar. Aunque el criterio es razonable, tiene ciertas limitaciones, que se analizarán enseguida.

326

Sistemas operativos. Una visión aplicada

• Frescura de la página. Utilizar como criterio si la página se ha usado recientemente. Como se explicará a continuación, es el criterio básico de este tipo de algoritmos. Algoritmo de reemplazo óptimo El algoritmo óptimo, denominado también MIN, debe generar el mínimo número de fallos de página. Por ello, la página que se debe reemplazar es aquélla que tardará más tiempo en volverse a usar. Evidentemente, este algoritmo es irrealizable, ya que no se puede predecir cuáles serán las siguientes páginas a las que se va a acceder. Este algoritmo sirve para comparar el rendimiento de los algoritmos que sí son factibles en la práctica. Algoritmo FIFO (First Input/First Output, primera en entrar/primera en salir) Una estrategia sencilla e intuitivamente razonable es seleccionar para la sustitución la página que lleva más tiempo en memoria, es decir, basarse en el tiempo de residencia. La implementación de este algoritmo es simple. Además, no necesita ningún apoyo hardware especial. El sistema operativo debe mantener una lista de las páginas que están en memoria, ordenada por el tiempo que llevan residentes. En el caso de una estrategia local, se utiliza una lista por cada proceso. Cada vez que se trae una nueva página a memoria, se pone al final de la lista. Cuando se necesita reemplazar, se usa la página que está al principio de la lista. Sin embargo, el rendimiento del algoritmo no es bueno en muchas ocasiones. La página que lleva más tiempo en memoria puede contener instrucciones o datos a los que se accede con frecuencia. Poniendo un ejemplo extremo, piense en un programa pequeño, cuyo código cabe en una sola página. Lo razonable sería que esa página nunca se expulsase, pero, con el algoritmo FIFO se expulsaría con bastante frecuencia. En determinadas situaciones este algoritmo presenta un comportamiento sorprendente, conocido como la anomalía de Belady. Intuitivamente, parece que cuantos más marcos de página haya en el sistema, menos fallos de página se producirán. Sin embargo, ciertos patrones de referencias causan que este algoritmo tenga un comportamiento opuesto. El descubrimiento de esta anomalía resultó al principio sorprendente y llevó al desarrollo de modelos teóricos para analizar los sistemas de memoria virtual. En la práctica, esta anomalía es sólo una curiosidad, que demuestra que los sistemas pueden tener a veces comportamientos inesperados. Algoritmo LRU (Least Recently Used, menos recientemente usada) El algoritmo LRU está basado en el principio de proximidad temporal de referencias: si es probable que se vuelvan a referenciar las páginas a las que se ha accedido recientemente, la página que se debe reemplazar es aquélla a la que no se ha hecho referencia desde hace más tiempo. Dicho de otra forma, se intenta predecir el futuro próximo usando el pasado reciente. Se basa, por tanto, en un criterio de frescura de la página. El algoritmo LRU no sufre la anomalía de Belady. Pertenece a una clase de algoritmos denominados algoritmos de pila. La propiedad de estos algoritmos es que las páginas residentes en memoria para un sistema con n marcos de página son siempre un subconjunto de las que habría en un sistema con n+1 marcos. Esta propiedad asegura que un algoritmo de este tipo nunca sufrirá la anomalía de Belady. Hay un aspecto sutil en este algoritmo cuando se considera su versión global. A la hora de seleccionar una página no habría que tener en cuenta el tiempo de acceso real, sino el tiempo lógico de cada proceso. O sea, habría que seleccionar la página que haya sido menos recientemente usada teniendo en cuenta el tiempo lógico de cada proceso. El algoritmo LRU se utiliza muy frecuentemente para la gestión de la caché del sistema de ficheros. Sin embargo, una implementación exacta en un sistema de memoria virtual es difícil, ya que requiere un considerable apoyo hardware. Una implementación del algoritmo podría basarse en lo siguiente: • El procesador gestiona un contador que se incrementa en cada referencia a memoria. Cada posición de la tabla de páginas ha de tener un campo de tamaño suficiente para que quepa el contador. • Cuando se hace referencia a una página, la MMU copia el valor actual del contador en la posición de la tabla correspondiente a esa página (realmente, debería ser en la TLB, para evitar un acceso a la tabla por cada referencia). • Cuando se produce un fallo de página, el sistema operativo examina los contadores de todas las páginas residentes en memoria y selecciona como víctima aquélla que tiene el valor menor.

Gestión de memoria

327

Inicio Ref = 1 Ref = 0 Ref = 1

Ref = 1

Ref = 0

Expulsada Ref = 0

Ref = 0

Ref = 1

Ref = 0

Ref = 1

Figura 5.72 Ejemplo del algoritmo del reloj. Esta implementación es factible, aunque requiere un hardware complejo y muy específico, y eso no es una buena idea. Como ya hemos comentado, y reiteraremos, varias veces a lo largo de los diversos capítulos del libro, un sistema operativo, con el fin de facilitar su adaptación a distintos procesadores, debería seguir una política de mínimos requisitos con respecto al hardware. Lo que se precisa es un algoritmo con unas prestaciones similares, pero que no requiera ningún hardware específico. Algoritmo del reloj El algoritmo de reemplazo del reloj (o de la segunda oportunidad) es una modificación sencilla del FIFO, que evita el problema de que una página muy utilizada sea eliminada por llevar mucho tiempo residente, proporcionando unas prestaciones similares a las del algoritmo LRU, sin requerir un hardware específico. En este algoritmo, cuando se necesita reemplazar una página, se examina el bit de referencia de la página más antigua (la primera de la lista en orden FIFO). Si no está activo, se usa esta página para el reemplazo. En caso contrario, se le da una segunda oportunidad a la página, poniéndola al final de la lista y desactivando su bit de referencia. Por tanto, se la considera como si acabara de llegar a memoria. La búsqueda continuará hasta que se encuentre una página con su bit de referencia desactivado. Si todas las páginas tienen activado su bit de referencia, el algoritmo se convierte en FIFO. Para implementar este algoritmo se puede usar una lista circular de las páginas residentes en memoria, en vez de una lineal (en el caso de una estrategia local, se utiliza una lista circular por cada proceso). Existe un puntero que señala en cada instante al principio de la lista. Cuando llega a memoria una página, se coloca en el lugar donde señala el puntero y, a continuación, se avanza el puntero al siguiente elemento de la lista. Cuando se busca una página para reemplazar, se examina el bit de referencia de la página a la que señala el puntero. Si está activo, se desactiva y se avanza el puntero al siguiente elemento. El puntero avanzará hasta que se encuentre una página con el bit de referencia desactivado. Esta forma de trabajo imita al comportamiento de un reloj donde el puntero que recorre la lista se comporta como la aguja del reloj. Debido a ello, esta estrategia se denomina algoritmo del reloj. La figura 5.72 muestra un ejemplo de este algoritmo, donde se puede apreciar que a las dos primeras páginas revisadas se les da una segunda oportunidad por tener el bit de referencia a uno, siendo seleccionada la tercera para la expulsión.

328

Sistemas operativos. Una visión aplicada

Como se comentó previamente, se trata de un algoritmo sencillo, que sólo requiere que el procesador gestione un bit de referencia, que suele ser lo habitual (incluso en procesadores que no gestionan este bit es relativamente sencillo implementarlo, simulándolo por software). Como el algoritmo LRU, también está basado en la frescura de la página, proporcionando un rendimiento similar. Esto ha hecho que, con pequeñas variaciones específicas, sea el algoritmo utilizado en la mayoría de los sistemas operativos actuales. Algoritmo LFU (Least Frequently Used, menos frecuentemente usada) Existe un número incontable de algoritmos de reemplazo en la literatura sobre gestión de memoria, por ello no tiene sentido hacer un repaso exhaustivo de los mismos en esta sección. Sin embargo, se ha considerado conveniente hacer una breve reseña de este algoritmo, puesto que, aunque no proporciona una buena solución al problema, tiene en cuenta un factor que no era tomado en consideración en los algoritmos presentados: la frecuencia de uso. La idea de este algoritmo es expulsar la página residente que menos accesos ha recibido. El problema de esta técnica es que una página que se utilice con mucha frecuencia en un intervalo de ejecución del programa obtendrá un valor del contador muy alto, no pudiendo ser expulsada en el resto de la ejecución del programa. Dada la escasa utilidad del algoritmo, no se entrará más en detalle sobre su implementación, aunque hay que resaltar que, como ocurría con el algoritmo LRU, necesitaría una MMU específica que gestionase un contador de referencias, o bien usar una versión aproximada del mismo, que gestionara el contador mediante muestreos periódicos del bit de referencia. Hay que resaltar que usar únicamente la frecuencia no es una buena estrategia, pero que, como se verá a continuación, olvidarse totalmente de la frecuencia, como sucede con el algoritmo LRU, tampoco es una buena idea. Más allá del LRU Durante mucho tiempo se ha considerado que el algoritmo LRU, y su aproximación práctica, el algoritmo del reloj, era la mejor solución posible al problema del reemplazo. Sin embargo, el estudio de su comportamiento ha detectado algunos problemas de rendimiento ante situaciones relativamente frecuentes. Una de estas situaciones aparece cuando se accede una sola vez a un conjunto de páginas. A estas páginas no se volverá a acceder, pero, sin embargo, se quedarán en memoria hasta que sean expulsadas siguiendo el orden LRU. Este tipo de situaciones aparece con cierta frecuencia, especialmente, cuando se accede a ficheros proyectándolos en memoria, como se analizará en la sección 5.5.15. Imagine, por ejemplo, que en el sistema se ejecuta un programa que realiza una copia de seguridad de un conjunto de ficheros usando la técnica de la proyección en memoria para acceder a los mismos. Aunque sólo se acceda una vez a cada página de cada uno de estos ficheros, va a permanecer en memoria conforme a la estrategia LRU, impidiendo que otras páginas realmente útiles puedan estar en memoria. Se podría decir que ese acceso único a los ficheros planteado en el ejemplo ha contaminado la memoria. El problema surge debido a que el algoritmo LRU se basa sólo en el criterio de frescura de la página, olvidando totalmente la frecuencia de accesos a la misma, que también es un indicador adecuado del interés de la página, siempre que no se use como criterio único. Para intentar adaptarse a esta circunstancia, surgió el algoritmo LRU/2 (realmente, la familia de algoritmos LRU/k), que usa el criterio LRU convencional, pero aplicado al penúltimo acceso (de ahí viene el 2 del nombre), es decir, se expulsa a aquella página cuyo penúltimo acceso ha sido menos reciente. Esta estrategia haría que en el ejemplo planteado las páginas de los ficheros desaparecieran rápidamente de la memoria al no producirse un segundo acceso a las mismas. En los últimos tiempos ha habido una proliferación de algoritmos, tanto en el ámbito de la gestión de memoria como en los de los sistemas de ficheros y las bases de datos, que han intentado conciliar estos criterios de frescura y frecuencia. La mayoría de estos algoritmos son complejos e incluyen algunos parámetros de configuración (tales como plazos de tiempo o tamaños) que son difíciles de ajustar satisfactoriamente en un sistema de propósito general. En cualquier caso, parece que hay un acuerdo general sobre que uno de los mejores algoritmos es el ARC (Adaptive Replacement Cache), que tiene en cuenta la frescura y la frecuencia, no requiriendo fijar

Gestión de memoria

329

parámetros de configuración. Aunque queda fuera del alcance de esta exposición el estudio detallado del mismo, a continuación se plantea un bosquejo de su modo de operación: • Usa dos listas LRU: una de frescura, L1, que incluye las páginas a las que se ha accedido sólo una vez recientemente, y otra de frecuencia, L2, que incorpora aquellas páginas a las que se ha accedido al menos dos veces recientemente. • Estas listas almacenan información histórica. No sólo guardan el orden LRU de las N páginas residentes en memoria, sino también de otras N páginas adicionales, que corresponden a las últimas N páginas expulsadas. • Existe un parámetro de configuración p, que se ajusta automáticamente, y que determina qué tamaño debe tener la lista L1. • El algoritmo de reemplazo selecciona una página de la lista L1 sólo si su tamaño es mayor que p. En caso contrario, se elige una página de la lista L2. En ambos casos, la selección se realiza mediante LRU y la página expulsada pasa a formar parte del histórico de esa lista. • El parámetro p se ajusta automáticamente mediante el uso de la información histórica. Si se produce un fallo de página que corresponde a una página del histórico de la lista L1, se incrementa p, puesto que esto indica que el programa está entrando en una fase donde es más importante la frescura (nótese que si p=N, se convierte directamente en el algoritmo LRU). En caso de que corresponda al histórico de L2, se disminuye el valor de p, dado que esto denota que el programa ha entrado en una fase donde la frecuencia toma mayor importancia. De forma análoga a lo que ocurre con el algoritmo LRU, la implementación exacta del ARC en un sistema de memoria virtual requeriría un hardware específico muy complejo y, posiblemente, ineficiente. Por ello, se han planteado versiones aproximadas del mismo, que pueden implementarse sobre un hardware de gestión de memoria estándar. Entre ellas, se encuentra el algoritmo CAR (Clock with Adaptive Replacement), que, como su nombre indica, se basa en una extensión del algoritmo del reloj para que se ajuste a un comportamiento similar al algoritmo ARC. Buffering de páginas Se puede considerar que el algoritmo de reemplazo también se activa bajo demanda: en el momento que no queda más memoria libre, hay que expulsar alguna página. Sin embargo, esperar a que se llegue a una situación tan crítica de falta total de memoria no parece una buena estrategia, más aún, teniendo en cuenta que si se necesita reservar memoria dentro del contexto de una rutina de interrupción, no se puede bloquear la ejecución de la misma hasta que no se habilite memoria libre. Para incidir más en la problemática de llegar a ese momento extremo, imagine qué ocurriría si se necesitase reservar memoria durante la propia operación de reemplazo para, por ejemplo, llevar a cabo la escritura en disco. Al no haber memoria libre, no podría completarse la misma, quedando el sistema en un interbloqueo. Teniendo en cuenta estas consideraciones, la mayoría de los sistemas operativos mantienen una reserva mínima de marcos libres y realizan las operaciones de reemplazo de forma anticipada, fuera del contexto del tratamiento del fallo de página, sin esperar a que se llegue a la situación crítica de agotamiento de la memoria. Esta estrategia suele denominarse buffering de páginas. Cuando se produce un fallo de página, se usa un marco de página libre, pero no se aplica el algoritmo de reemplazo. Esto es, se consume un marco de página, pero no se libera otro. Cuando el sistema operativo detecta que el número de marcos de página disminuye por debajo de un cierto umbral, aplica repetidamente el algoritmo de reemplazo hasta que el número de marcos libres llegue a otro umbral que corresponda a una situación de estabilidad. Para realizar esta operación, dado que se requiere un flujo de ejecución independiente dentro del sistema operativo, habitualmente, se usa un proceso/thread de núcleo, que se suele denominar demonio de paginación. Hay que resaltar que debido a la complejidad de la gestión de memoria, ésta suele requerir la presencia de diversos procesos de núcleo (por ejemplo, procesos que escriben páginas modificadas a disco o procesos que rellenan de ceros marcos libres para tenerlos preparados para volver a utilizarlos). Según el demonio de paginación va aplicando repetidamente el algoritmo, las páginas liberadas que no están modificadas pasan a una lista de marcos libres, estando listas para poder utilizarse de nuevo, mientras

330

Sistemas operativos. Una visión aplicada

que las páginas que han sido modificadas pasan a una lista de marcos modificados y deberán actualizarse en memoria secundaria antes de poder volver a utilizarse. Las páginas que están en cualquiera de las dos listas pueden recuperarse si se vuelve a acceder a las mismas antes de reutilizarse. En este caso, la rutina de fallo de página recupera la página directamente de la lista y actualiza la entrada correspondiente de la tabla de páginas para conectarla. Este fallo de página no implicaría operaciones de entrada/salida. Las páginas en la lista de modificadas se pueden escribir en tandas al dispositivo para obtener un mejor rendimiento. Cuando la página modificada se ha escrito al dispositivo, se la incluye en la lista de marcos libres. Esta estrategia puede mejorar el rendimiento de algoritmos de reemplazo que no sean muy efectivos. Así, si el algoritmo de reemplazo decide revocar una página que en realidad está siendo usada por un proceso, se producirá inmediatamente un fallo de página que la recuperará de las listas. Este proceso de recuperación de la página plantea un reto: ¿cómo detectar de forma eficiente si la página requerida por un fallo de página está en una de estas listas? La solución es la caché de páginas. Caché de páginas Con el uso de la técnica de memoria virtual, la memoria principal se convierte, a todos los efectos, en una caché de la memoria secundaria. Por otra parte, en diversas circunstancias, el sistema operativo debe buscar si una determinada página está residente en memoria (esa necesidad se acaba de identificar dentro de la técnica del buffering de páginas y volverá a aparecer cuando se estudie el compartimiento de páginas). Por tanto, parece lógico que ese comportamiento de caché se implemente como tal, es decir, que se habilite una estructura de información, la caché de páginas, que permita gestionar las páginas de los procesos que están residentes en memoria y pueda proporcionar una manera eficiente de buscar una determinada página. La organización de la caché se realiza de manera que se pueda buscar eficientemente una página dado un identificador único de la misma. Generalmente, este identificador corresponde al número de bloque dentro del fichero (o dispositivo de swap) que contiene la página. Obsérvese que las páginas anónimas que todavía no están vinculadas con el swap no están incluidas en la caché de páginas. Cada vez que dentro de la rutina del tratamiento del fallo de página se copia una página de un bloque de un fichero o de un dispositivo de swap a un marco, se incluirá en la caché asociándola con dicho bloque. Hay que resaltar que las páginas de la caché están incluidas, además, en otras listas, tales como las gestionadas por el algoritmo de reemplazo o la de marcos libres y modificados. En el sistema de ficheros, como se analizará en el capítulo dedicado al mismo, existe también una caché de similares características, que se suele denominar caché de bloques. Aunque el estudio de la misma se realiza en dicho capítulo, se puede anticipar que, en los sistemas operativos actuales, la tendencia es fusionar ambas cachés para evitar los problemas de coherencia y de mal aprovechamiento de la memoria, debido a la duplicidad de la información en las cachés. Retención de páginas en memoria Para acabar esta sección en la que se han presentado diversos algoritmos de reemplazo, hay que resaltar que no todas las páginas residentes en memoria son candidatas al reemplazo. Se puede considerar que algunas páginas están atornilladas a la memoria principal. En primer lugar, están las páginas del propio sistema operativo. La mayoría de los sistemas operativos tienen su mapa de memoria fijo en memoria principal. El diseño de un sistema operativo en el que las páginas de su propio mapa pudieran expulsarse a memoria secundaria resultaría complejo y, posiblemente, ineficiente. Tenga en cuenta, además, que el código de la rutina de tratamiento del fallo de página, así como los datos y otras partes de código usados desde la misma, deben siempre estar residentes para evitar el interbloqueo. Lo que sí proporcionan algunos sistemas operativos es la posibilidad de que un componente del propio sistema operativo reserve una zona de memoria que pueda ser expulsada, lo que le permite usar grandes cantidades de datos sin afectar directamente a la cantidad de memoria disponible en el sistema. Además, si se permite que los dispositivos de entrada/salida que usan DMA realicen transferencias directas a la memoria de un proceso, será necesario marcar las páginas implicadas como no reemplazables hasta que termine la operación.

Gestión de memoria

331

Por último, algunos sistemas operativos ofrecen servicios a las aplicaciones que les permiten solicitar que una o más páginas de su mapa queden retenidas en memoria (en UNIX existe el servicio mlock para este fin). Este servicio puede ser útil para procesos de tiempo real que necesitan evitar que se produzcan fallos de página imprevistos. Sin embargo, el uso indiscriminado de este servicio puede afectar gravemente al rendimiento del sistema.

5.5.9. Política de reparto de espacio entre los procesos En un sistema con multiprogramación existen varios procesos activos simultáneamente que comparten la memoria del sistema. Es necesario, por tanto, determinar cuántos marcos de página se asignan a cada proceso. Existen dos tipos de estrategias de asignación: asignación fija o asignación dinámica. Asignación fija Con esta estrategia, se asigna a cada proceso un número fijo de marcos de página. Normalmente, este tipo de asignación lleva asociada una estrategia de reemplazo local. El número de marcos asignados no varía, ya que un proceso sólo usa para reemplazo los marcos que tiene asignados. La principal desventaja de esta alternativa es que no se adapta a las diferentes necesidades de memoria de un proceso a lo largo de su ejecución. Habrá fases en la que el espacio asignado se le quedará pequeño, no permitiendo almacenar simultáneamente todas las páginas que está utilizando el proceso en ese intervalo de tiempo. En contraste, existirán fases en las que el proceso no usará realmente los marcos que tiene asignados. Una propiedad positiva de esta estrategia es que el comportamiento del proceso es relativamente predecible, puesto que siempre que se ejecute con los mismos parámetros va a provocar los mismos fallos de página. Existen diferentes criterios para repartir los marcos de las páginas entre los procesos existentes. Puede depender de múltiples factores tales como el tamaño del proceso o su prioridad. Por otra parte, cuando se usa una estrategia de asignación fija, el sistema operativo decide cuál es el número máximo de marcos asignados al proceso. Sin embargo, la arquitectura de la máquina establece el número mínimo de marcos que deben asignarse a un proceso. Por ejemplo, si la ejecución de una única instrucción puede generar cuatro fallos de página y el sistema operativo asigna tres marcos de página a un proceso que incluya esta instrucción, el proceso podría no terminar de ejecutarla. Por tanto, el número mínimo de marcos de página para una arquitectura quedará fijado por la instrucción que pueda generar el máximo número de fallos de página. Asignación dinámica Usando esta estrategia, el número de marcos asignados a un proceso varía según las necesidades que tenga el mismo (y posiblemente el resto de procesos del sistema) en diferentes instantes de tiempo. Con este tipo de asignación se pueden usar estrategias de reemplazo locales y globales. • Con reemplazo local, el proceso va aumentando o disminuyendo su conjunto residente dependiendo de sus necesidades en las distintas fases de ejecución del programa. • Con reemplazo global, los procesos compiten en el uso de memoria quitándose entre sí las páginas. La estrategia de reemplazo global hace que el comportamiento del proceso en tiempo de ejecución no sea predecible. El principal problema de este tipo asignación es que la tasa de fallos de página de un programa puede depender de las características de los otros procesos que estén activos en el sistema. Hiperpaginación Si el número de marcos de página asignados a un proceso no es suficiente para almacenar las páginas a las que hace referencia frecuentemente, se producirá un número elevado de fallos de página. Esta situación se denomina hiperpaginación (thrashing). Cuando se produce la hiperpaginación, el proceso pasa más tiempo en la cola de servicio del dispositivo de swap que en ejecución. Dependiendo del tipo de asignación usado, este problema puede afectar a procesos individuales o a todo el sistema.

Sistemas operativos. Una visión aplicada

Utilización de la UCP

332

Grado de multiprogramación

Figura 5.73 Hiperpaginación. En un sistema operativo que utiliza una estrategia de asignación fija, si el número de marcos asignados al proceso no es suficiente para albergar su conjunto de trabajo en una determinada fase de su ejecución, se producirá hiperpaginación en ese proceso, lo que causará un aumento considerable de su tiempo de ejecución. Sin embargo, el resto de los procesos del sistema no se verán afectados directamente. Con una estrategia de asignación dinámica, el número de marcos asignados a un proceso se va adaptando a sus necesidades, por lo que, en principio, no debería presentarse este problema. No obstante, si el número de marcos de página en el sistema no es suficiente para almacenar los conjuntos de trabajo de todos los procesos, se producirán fallos de página frecuentes y, por tanto, el sistema sufrirá hiperpaginación. La utilización del procesador disminuirá, puesto que el tiempo que dedica al tratamiento de los fallos de página aumenta. Como se puede observar en la figura 5.73, no se trata de una disminución progresiva, sino drástica, que se debe a que al aumentar el número de procesos, por un lado, crece la tasa de fallos de página de cada proceso (hay menos marcos de página por proceso) y, por otro lado, aumenta el tiempo de servicio del dispositivo de paginación (crece la longitud de la cola de servicio del dispositivo). Cuando se produce esta situación se deben suspender uno o varios procesos liberando sus páginas. Es necesario establecer una estrategia de control de carga que ajuste el grado de multiprogramación en el sistema para evitar que se produzca hiperpaginación. Este mecanismo de suspensión tiene similitudes con la técnica del intercambio y, como en dicha técnica, habrá que establecer algún tipo de criterio para decidir qué procesos se deberían suspender (criterios tales como si el proceso está bloqueado, su prioridad, el número de páginas residentes, el tamaño de su mapa de memoria o el tiempo que lleva ejecutando). La reactivación de los procesos seleccionados sólo se realizará cuando haya suficientes marcos de página libres. La estrategia que decide cuándo suspender un proceso y cuándo reactivarlo se corresponde con la planificación a medio plazo presentada en el capítulo 4. A continuación, se plantean algunas políticas de control de carga. Estrategia del conjunto de trabajo Como se comentó previamente, cuando un proceso tiene residente en memoria su conjunto de trabajo, se produce una baja tasa de fallos de página. Una posible estrategia consiste en determinar los conjuntos de trabajo de todos los procesos activos para intentar mantenerlos residentes en memoria principal. Para poder determinar el conjunto de trabajo de un proceso es necesario dar una definición más formal de este término. El conjunto de trabajo de un proceso es el conjunto de páginas a las que ha accedido un proceso en las últimas n referencias. El número n se denomina la ventana del conjunto de trabajo. El valor de n es un factor crítico para el funcionamiento efectivo de esta estrategia. Si es demasiado grande, la ventana podría englobar varias fases de ejecución del proceso, llevando a una estimación excesiva de las necesidades del proceso. Si es demasiado pequeño, la ventana podría no englobar la situación actual del proceso, con lo que se generarían demasiados fallos de página. Suponiendo que el sistema operativo es capaz de detectar cuál es el conjunto de trabajo de cada proceso, se puede especificar una estrategia de asignación dinámica con reemplazo local y control de carga.

tasa de fallos de página

Gestión de memoria

333

límite superior

límite inferior

número de marcos

Figura 5.74 Estrategia de administración basada en la frecuencia de fallos de página. • Si el conjunto de trabajo de un proceso decrece, se liberan los marcos asociados a las páginas que ya no están en el conjunto de trabajo. • Si el conjunto de trabajo de un proceso crece, se asignan marcos para que puedan contener las nuevas páginas que han entrado a formar parte del conjunto de trabajo. Si no hay marcos libres, hay que realizar un control de carga, suspendiendo uno o más procesos y liberando sus páginas. El problema de esta estrategia es cómo poder detectar cuál es el conjunto de trabajo de cada proceso. Al igual que ocurre con el algoritmo LRU, se necesitaría una MMU específica que fuera controlando las páginas a las que ha ido accediendo cada proceso durante las últimas n referencias. Estrategia de administración basada en la frecuencia de fallos de página Esta estrategia busca una solución más directa al problema de la hiperpaginación. Se basa en controlar la frecuencia de fallos de página de cada proceso. Como se ve en la figura 5.74, se establecen una cuota superior y otra inferior de la frecuencia de fallos de página de un proceso. Basándose en esa idea, a continuación se describe una estrategia de asignación dinámica con reemplazo local y control de carga. • Si la frecuencia de fallos de un proceso supera el límite superior, se asignan marcos de página adicionales al proceso. Si la tasa de fallos crece por encima del límite y no hay marcos libres, se suspende algún proceso liberando sus páginas. • Cuando el valor de la tasa de fallos es menor que el límite inferior, se liberan marcos asignados al proceso seleccionándolos mediante un algoritmo de reemplazo. Estrategia de control de carga para algoritmos de reemplazo globales Los algoritmos de reemplazo globales no controlan la hiperpaginación. Incluso aunque se pudiera utilizar el algoritmo óptimo, el problema persistiría, puesto que dicho algoritmo seleccionaría la página menos útil, pero, en estas circunstancias, esa página también es útil. Necesitan trabajar conjuntamente con un algoritmo de control de carga. Normalmente, se usan soluciones de carácter empírico, que detectan síntomas de que el sistema está evolucionando hacia la hiperpaginación. Así, si la tasa de paginación en el sistema es demasiado alta y el número de marcos libres está frecuentemente por debajo del umbral mínimo, se considera que el sistema está en estado de hiperpaginación y se suspende uno o más procesos.

5.5.10. Gestión del espacio de swap Un dispositivo de swap se implementa sobre una unidad de disco o una partición de la misma. Normalmente, los sistemas operativos ofrecen la posibilidad de utilizar múltiples dispositivos de swap, permitiendo, incluso, añadir dispositivos de swap dinámicamente, e incluso usar ficheros como soporte del swap. Sin embargo, hay

334

Sistemas operativos. Una visión aplicada

que tener en cuenta que el acceso a los ficheros es más lento que el acceso directo a los dispositivos. En cualquier caso, esta posibilidad es interesante, ya que alivia al administrador de la responsabilidad de configurar correctamente a priori el dispositivo de swap, puesto que si hay necesidad, se puede añadir más espacio de swap en tiempo de ejecución. Habitualmente, también es posible que el administrador defina el modo de uso de los dispositivos de swap, pudiendo establecer políticas tales como no usar un dispositivo hasta que los otros estén llenos, o repartir cíclicamente las páginas expulsadas entre los dispositivos de swap existentes. La estructura interna de un dispositivo de swap es muy sencilla: una cabecera y un conjunto de bloques. La cabecera incluye algún tipo de información de control, como, por ejemplo, si hay sectores de disco erróneos dentro de la misma. No es necesario que incluya información del estado de los bloques, puesto que el dispositivo de swap sólo se usa mientras el sistema está arrancado. Por tanto, no hay que mantener ninguna información cuando el sistema se apaga. El sistema operativo usa un mapa de bits en memoria para conocer si está libre u ocupado cada bloque del swap. El sistema operativo debe gestionar el espacio de swap reservando y liberando zonas del mismo según evolucione el sistema. Existen básicamente dos alternativas a la hora de asignar espacio de swap durante la creación de una nueva región: • Con preasignación de swap. Cuando se crea una región privada o sin soporte, se reserva espacio de swap para la misma. Con esta estrategia, cuando se expulsa una página ya tiene reservado espacio en swap para almacenar su contenido. En algunos sistemas, más que realizar una reserva explícita de bloques de swap, se lleva una cuenta de cuántos hay disponibles, de manera que al crear una región que requiera el uso del swap, se descuenta la cantidad correspondiente al tamaño de la misma del total de espacio de swap disponible. • Sin preasignación de swap. Cuando se crea una región, no se hace ninguna reserva en el swap. Sólo se reserva espacio en el swap para una página cuando es expulsada por primera vez. La primera estrategia conlleva un peor aprovechamiento de la memoria secundaria, puesto que toda página debe tener reservado espacio en ella. Sin embargo, la preasignación presenta la ventaja de que con ella se detecta anticipadamente si no queda espacio en swap. Si al crear un proceso no hay espacio en swap, éste no se crea. Con un esquema sin preasignación, esta situación se detecta cuando se va a expulsar una página y no hay sitio para ella. En ese momento habría que abortar el proceso aunque ya hubiera realizado parte de su labor. Como se explicó en la sección 5.5.4, sólo las páginas de las regiones privadas o sin soporte usan el swap para almacenarse cuando son expulsadas estando modificadas. En el caso de una página de una región compartida con soporte en un fichero, no se usa espacio de swap para almacenarla, sino que se utiliza directamente el fichero que la contiene como almacenamiento secundario. Dado que puede haber múltiples entradas de tablas de páginas que hacen referencia al mismo bloque de swap, el sistema operativo gestionará un contador de referencias por cada bloque de swap, de manera que cuando el mismo valga cero, el bloque estará libre.

5.5.11. Compartimiento de páginas Como se ha comentado a lo largo del capítulo, los procesos comparten regiones en diversas circunstancias: • Cuando usan explícitamente una zona de memoria compartida. • Cuando utilizan el mismo programa o biblioteca dinámica, comparten implícitamente su código, optimizándose de esta forma el uso de recursos en el sistema. • Cuando proyectan un mismo fichero. • En UNIX, cuando un proceso crea un hijo mediante el servicio fork, el proceso hijo comparte con el padre aquellas regiones de tipo compartido que tenga éste. El compartimiento de las regiones implica, evidentemente, compartir las páginas de la región. Como se analizó en la sección dedicada a la paginación, para ello, basta con que las entradas correspondientes de las tablas de páginas de los procesos involucrados hagan referencia al mismo marco. En la tabla de marcos, se

Gestión de memoria

335

almacenará un contador de referencias que indicará cuántas entradas de tablas de páginas hacen referencia a ese marco, de manera que cuando el mismo valga cero, el marco estará libre. En principio, dado que la memoria virtual se basa en la paginación, la técnica de compartimiento será la misma. Sin embargo, aparecen dos dificultades añadidas: • Cuando la página compartida no está residente en memoria y uno de los procesos accede a la misma provocando un fallo que la trae a memoria, si otro proceso quiere acceder a la página, deberá usar la copia presente en memoria. La pregunta es cómo descubre ese proceso que la página está residente en memoria. La respuesta es consultando la caché de páginas dentro la rutina de tratamiento del fallo de página. Al encontrar la página en la caché, no es preciso leerla de memoria secundaria y sólo hay que hacer que la entrada de la tabla de páginas haga referencia al marco que la contiene. • Si el algoritmo de reemplazo decide expulsar una página compartida, habrá que invalidar todas las referencias a ese marco en todas las entradas de las tablas de páginas que la comparten. Esto requiere guardar información que permita realizar la traducción inversa a la que se usa normalmente: dado un marco, se requiere conocer qué entradas hacen referencia al mismo. La gestión de esta información puede causar una sobrecarga apreciable en tiempo y espacio, por lo que algunos sistemas operativos no la proporcionan y sólo pueden expulsar páginas no compartidas. En Linux se utiliza una técnica denominada rmap para gestionar la información necesaria para la traducción inversa, pero intentando minimizar esta sobrecarga. Además del compartimiento propiamente dicho, existe otro tipo de situaciones en las que se comparte información, aunque sea inicialmente. Se trata de situaciones en las que dos o más procesos usan una región cuyo contenido inicial es el mismo, pero tal que cada uno debe trabajar de forma independiente, de manera que las modificaciones que realice un proceso no sean visibles por el resto. Este modo de trabajo corresponde con la operación duplicar_región, y puede requerirse en distintas circunstancias: • Cuando utilizan el mismo programa o biblioteca dinámica, inicialmente, los procesos comparten de forma implícita su región de datos con valor inicial. • En UNIX, cuando un proceso crea un hijo mediante el servicio fork, inicialmente, el proceso hijo comparte con el padre aquellas regiones de tipo privado que tenga éste. • Cuando dos o más procesos proyectan un mismo fichero, pero en modo privado. De la misma manera que la paginación por demanda retarda la carga de una página desde la memoria secundaria hasta que realmente se accede a la misma, se puede plantear realizar un duplicado por demanda, es decir, diferir la copia de cada página de la región hasta que el proceso la intente modificar. Esta técnica se denomina copy-on-write (COW). Con esta técnica, en vez de copiar la región original, se comparte, pero marcándola de tipo COW. Mientras los procesos que usan esta región sólo la lean pueden seguir compartiéndola. Pero cuando un proceso intenta modificar una página de esta región, el sistema operativo se encarga de crear una copia privada de la página para ese proceso. Habitualmente, para forzar la activación del sistema operativo, se modifica la protección de la página en la entrada correspondiente para que sea sólo de lectura, produciéndose una excepción de fallo de protección, en cuyo tratamiento se realiza la copia. No obstante, en la tabla de regiones se sigue manteniendo la protección real de la región. Tratamiento de la excepción de COW Las dos excepciones que regulan el comportamiento del sistema de memoria virtual son la del fallo de página, que permite implementar la paginación por demanda y que ya se ha estudiado anteriormente, y la del fallo de protección, que permite implementar la técnica del COW. A continuación, se especifican los pasos habituales en el tratamiento de un fallo de protección: • La MMU produce una excepción, dejando, habitualmente, en un registro especial la dirección que provocó el fallo.

336

Sistemas operativos. Una visión aplicada

• Se activa el sistema operativo que busca en la tabla de regiones a qué región pertenece la dirección que produjo el fallo, verificando si realmente se trata de un fallo de tipo COW. Para ello, comprueba la protección de la región. Si no tiene permiso de escritura, se trata de un acceso inválido, por lo que se aborta el proceso o se le envía una señal. En caso contrario, se realizan los pasos que se describen a continuación. • Si el contador de referencias del marco es mayor que 1 (varios procesos todavía comparten la página), se realizan las siguientes acciones: ⎯ Se reserva un marco libre (gracias al buffering de páginas siempre lo habrá). ⎯ Se copia el contenido de la página. ⎯ Se asocia la entrada de la tabla de páginas con este nuevo marco y se le devuelve el permiso de escritura. ⎯ Se resta una unidad al contador de referencias del marco. La nueva página no se incluye en la caché de páginas, puesto que, por el momento, no está vinculada con ningún soporte. • Si el contador de referencias del marco ya es igual a 1 (es el único proceso asociado a ese marco), sólo hay que devolver los permisos a la página, que quedará asignada únicamente a este proceso. Asimismo, hay que eliminar la página de la caché de páginas, rompiendo con ello su vinculación con el soporte actual de la misma (no queremos que un fallo de página de otro proceso que compartía esta página la encuentre en la caché de páginas y la utilice, puesto que se trata de una nueva copia). • Si la página ya tenía un bloque de swap asignado, hay que romper también esta asociación, restando una unidad al contador de referencias del bloque de swap, puesto que ya no está asociado a la página asignada al proceso como resultado del COW. Cuando se expulse la página, se le asignará un nuevo bloque de swap.

5.5.12. Gestión de la memoria del sistema operativo En esta sección se analiza cómo se lleva a cabo la gestión de memoria desde el punto de vista del sistema operativo, mostrando cómo gestiona la memoria física, así como su mapa de memoria lógico. Asimismo, se revisarán los distintos esquemas de asignación de espacio proporcionados por el sistema operativo. Gestión de la memoria física En su fase de iniciación, el sistema operativo recibe información (normalmente, invocando alguna rutina del firmware) sobre las características de la memoria física disponible. A priori, puede parecer que es suficiente con que sepa cuánta memoria existe. Sin embargo, las cosas son bastante más complejas y necesita conocer mucha más información, puesto que la memoria física no es algo uniforme o contiguo. Puede haber huecos en el espacio de direcciones de la memoria y zonas de memoria ROM. Además, puede haber restricciones en el uso de ciertas partes de la memoria. Por ejemplo, en algunos sistemas, por limitaciones del hardware, sólo se puede hacer DMA sobre determinadas zonas de la memoria, de lo cual debe ser consciente el sistema operativo a la hora de asignar espacio (en Linux, se utiliza el concepto de zona para gestionar este tipo de restricciones). Asimismo, si se trata de un sistema multiprocesador NUMA, será necesario que el sistema operativo conozca la topología del sistema, de manera que cuando un proceso necesite memoria, se le pueda asignar de la parte asociada al procesador donde está ejecutando (en Linux, se usa el concepto de nodo para implementar esta característica). Una vez que el sistema operativo averigua las características de la memoria disponible en el sistema, crea una tabla de marcos del tamaño adecuado e inicia las entradas de la misma, de manera que los marcos donde está ubicado el sistema operativo se ponen como ocupados y los restantes como libres. Gestión del mapa de memoria del sistema operativo El sistema operativo posee su propio mapa de memoria definido por la tabla de páginas del sistema. En el arranque del sistema, el hardware de gestión de memoria estará desactivado. En su fase de iniciación, el sis-

Gestión de memoria

337

tema operativo construirá su tabla de páginas y activará el hardware de gestión de memoria. Normalmente, en el proceso de arranque del computador, se carga el sistema operativo en una zona contigua de la memoria física. Por tanto, se iniciarán las primeras entradas de la tabla de páginas del sistema de manera que hagan referencia a esos marcos contiguos que ocupa inicialmente el sistema operativo, creando un espacio lógico para el mismo. Gracias a esa contigüidad, se pueden usar superpáginas para dar cobertura al espacio ocupado por el sistema operativo, lo que minimiza el número de entradas requeridas. Las entradas restantes de la tabla de páginas del sistema se quedarán sin usar (marcadas como inválidas). Una vez terminada la fase de iniciación, todos los marcos libres disponibles quedan a disposición de los procesos y de las necesidades internas del propio sistema operativo (cachés, memoria dinámica, etc.). Cuando el sistema operativo quiera usar un marco de página libre, deberá crear una asociación al mismo, iniciando una entrada de la tabla de páginas del sistema que esté sin usar, de forma que haga referencia a ese marco. Si se trata de una página para un proceso, se producirá una asociación temporal mientras el sistema operativo carga el contenido de la página, que desaparecerá cuando la página se asigne al proceso incluyéndola en su tabla de páginas. En caso de que la página sea para el propio sistema operativo (por ejemplo, para reservar dinámicamente espacio para un nuevo BCP), se establecerá una asociación que se mantendrá hasta que se libere explícitamente ese espacio reservado. Hay que resaltar que cualquier modificación en una entrada de la tabla de páginas del sistema conlleva una cierta sobrecarga, puesto que, como se verá en la próxima sección, requiere operaciones sobre la TLB (además, en el caso de que el procesador no use tablas de usuario y sistema independientes, habría una sobrecarga debida a la propagación del cambio a todas las copias de la tabla de páginas del sistema). Algunos sistemas operativos usan una solución alternativa: incluyen toda la memoria física en el espacio del sistema. En vez de crear un mapa inicial del sistema que incluya sólo las regiones del sistema operativo y usar asociaciones para acceder al resto de la memoria, como se acaba de explicar, establecen un mapa del sistema que cubre toda la memoria física: la primera página del mapa del sistema operativo se hace corresponder con el primer marco, la segunda con el segundo, y así sucesivamente. Esta solución, usada en Linux, permite que el sistema operativo manipule directamente toda la memoria física, sin necesidad de realizar asociaciones. Esta solución elimina la sobrecarga asociada a los cambios en la tabla de páginas del sistema y permite usar superpáginas para representar toda la memoria física. En este tipo de sistemas es inmediato el cálculo de a qué dirección física corresponde una dirección lógica del sistema: basta con restar el valor de la primera dirección lógica del sistema (en una configuración con 3GB de usuario y 1GB de sistema, la primera dirección lógica de sistema es C0000000, que es el valor que hay que restar a una dirección lógica de sistema para obtener la dirección física que representa). Las entradas restantes de la tabla de páginas del sistema se usan para poder asignar espacio lógico contiguo usando espacio físico que no lo es. Esta solución tiene la limitación de que sólo se puede manejar tanta memoria física como tamaño tenga el espacio lógico del sistema (si hay un espacio lógico de 1GB, sólo se puede gestionar directamente esa cantidad de memoria física, que es claramente insuficiente actualmente). Por ello, en este tipo de sistemas suele ser habitual una mezcla de las dos técnicas, es decir, establecer un mapa de sistema que cubra toda la memoria física posible, dejando una cantidad suficiente de entradas de la tabla de páginas de sistema sin usar para manejar el resto de la memoria (denominada en Linux high memory) mediante asociaciones. Esquemas de asignación de espacio Antes de presentar los diversos tipos esquemas de asignación de memoria que proporciona habitualmente el sistema operativo para su uso interno, es conveniente comparar dos soluciones a la hora de satisfacer una solicitud de memoria de algún componente del sistema operativo que necesita una zona contigua que ocupe varias páginas: • Una alternativa es reservar un conjunto de marcos cualesquiera, aunque no sean contiguos, y crear entradas en la tabla de páginas del sistema para que aparezcan como contiguos en el espacio lógico. • La otra opción es reservar un conjunto contiguo de marcos. Esta puede ser la única opción posible si el espacio se necesita para realizar una operación de DMA sobre el mismo. Además, en caso de usar un sistema que incluya la memoria física dentro del mapa del sistema, como Linux, la operación es más eficiente, ya que no requiere manipular la tabla de páginas para establecer asociaciones.

338

Sistemas operativos. Una visión aplicada

Habitualmente, el sistema operativo ofrece distintos tipos de gestores de memoria internos, que intentan adaptarse a las diversas necesidades del propio sistema operativo y de los procesos. • En ocasiones, el sistema operativo necesita reservar una o más páginas contiguas en memoria en el espacio físico. Un manejador de un dispositivo puede necesitar reservar un buffer de varias páginas como almacenamiento intermedio de datos del dispositivo. Otro ejemplo aparece en el tratamiento de un fallo de página, donde el sistema operativo necesita reservar una página para el proceso. Linux utiliza un sistema buddy binario para gestionar los marcos libres, con tamaños que van desde 1 página hasta 1024 páginas, y ofrece un conjunto de operaciones para reservar marcos de página, con funciones tales como get_free_pages. • El código del sistema operativo puede necesitar reservar memoria dinámica igual que cualquier aplicación. De hecho, para que no quepa duda de la similitud, en Linux la función interna se llama kmalloc. En Linux, este componente de reserva dinámica se construye directamente sobre el sistema de asignación de páginas explicado en el punto anterior, y usa un esquema de múltiples listas con particiones estáticas cuyos tamaños son potencias de 2, desde 32 bytes hasta 128KB. Este subsistema funciona como una caché. Cuando se realiza una petición y no hay espacio libre asociado a este subsistema, se solicitan páginas al sistema de asignación de páginas. Sin embargo, cuando se libera, no se devuelve al sistema de asignación de páginas. • El código del sistema operativo requiere frecuentemente reservar y liberar objetos del mismo tipo (por ejemplo, espacio para un BCP). Para agilizar esta labor, el sistema operativo permite crear cachés específicas para cada tipo de objeto. De esta forma, para crear un nuevo BCP se puede usar directamente uno disponible en la caché, eliminando la necesidad de la reserva. En Linux se usa el gestor de slabs para este fin, construyéndose también sobre el sistema de asignación de páginas. • Por último, como ya se comentó antes, se ofrecen funciones para reservar memoria contigua en el espacio lógico, aunque no contigua en el físico. En Linux, se usa la función vmalloc para tal fin. En algunos sistemas operativos toda la memoria del sistema está residente en memoria física. Sin embargo, otros sistemas operativos, como Windows, permiten reservar memoria que puede ser expulsada (memoria que puede ser paginada al disco). Esta opción puede ser interesante para un módulo del sistema operativo que requiera usar una gran cantidad de memoria, pero no de forma simultánea. Téngase en cuenta que, a excepción de esta modalidad de reserva de memoria que puede ser paginada, en todos los demás casos cada byte de memoria que utiliza cualquier componente del sistema operativo es un byte que deja de estar disponible para los procesos Como se ha podido apreciar en este apartado, el sistema operativo utiliza numerosas cachés (por ejemplo, en Linux las correspondientes a los slabs y a las listas de particiones estáticas del kmalloc). Estas cachés van creciendo y, en principio, nunca reducen su tamaño por iniciativa propia. Por tanto, cuando el demonio de paginación se activa para liberar marcos de página, deberá considerar por un lado las páginas de usuario, aplicando el algoritmo de reemplazo correspondiente, y, por otro lado, el espacio libre de las diversas cachés. Buscar un equilibrio en el uso de la memoria por parte de estas dos entidades es un asunto complejo, que requiere ajustes de carácter empírico. Un último aspecto a tener en cuenta es que en sistemas multiprocesadores hay que intentar minimizar la congestión en la reserva de memoria reduciendo dentro de lo posible el uso de los cerrojos que se requieren para la manipulación de las estructuras de datos que reflejan el estado de la memoria. Por ello, suele ser habitual que las diversas cachés presentes en el sistema tengan una prerreserva de elementos para cada procesador. Mientras haya elementos en la prerreserva de un procesador, se pueden usar en ese procesador sin necesidad de utilizar el cerrojo. En el caso de Linux, hay una prerreserva de marcos de página libre por procesador y una para los slabs.

5.5.13. Coherencia de la jerarquía de memoria La jerarquía de memoria es un sistema complejo formado por múltiples niveles y componentes, donde se presentan numerosos problemas de coherencia, más aún en el caso de un sistema multiprocesador. Depen-

Gestión de memoria

339

diendo del tipo de problema y de las características específicas del hardware del sistema, el componente encargado de mantener la coherencia puede ser distinto. En algunos casos, será el propio hardware el que resuelva el problema, pero, en otros, tendrá que ser el sistema operativo. El objetivo de esta sección es tratar todos estos problemas de una manera integrada, a pesar de su enorme variedad. Para ello, se presenta un modelo general original que permite identificar aquellos aspectos de la jerarquía de memoria que influyen en el mantenimiento de la coherencia en un sistema de estas características. De acuerdo con este modelo, cada nivel en una jerarquía se caracteriza por los siguientes aspectos: • La función de traducción requerida para, dado un identificador único del objeto que se pretende acceder, encontrar en qué bloque de ese nivel está almacenada, en caso de que esté presente en el mismo. • La necesidad, por motivos de eficiencia, de, a su vez, una jerarquía de niveles en el propio esquema de traducción de un nivel. Este es el caso del mecanismo de traducción del nivel de memoria principal, que requiere el uso de dos niveles de traducción: la TLB y la tabla de páginas. • La existencia de múltiples componentes de memoria en ese nivel. En un sistema multiprocesador, en el nivel de caché hay múltiples componentes: una caché por cada procesador. También en un sistema uniprocesador pueden existir múltiples componentes en un nivel. Así, en el nivel de caché puede haber una caché de instrucciones y una de datos, cuyos contenidos no son totalmente disjuntos, ya que a las instrucciones también se accede como datos cuando se carga un programa en memoria. • Las entidades que pueden acceder a ese nivel. A algunos niveles de la jerarquía, además de los procesos, también pueden acceder dispositivos de entrada/salida mediante DMA, tal como se estudiará en el capítulo 8. • El tipo de multiplexación que se realiza para que un componente pueda almacenar información de varios procesos. Como se vio al principio del capítulo, puede usarse una multiplexación temporal o espacial. En cuanto a la función de traducción de un nivel, debería recibir un identificador único del objeto que se pretende acceder. Retomando la notación de la sección 5.2.5 y el proceso de transformación de direcciones, en un sistema de memoria virtual, no se puede usar la dirección física como identificador único de un objeto, puesto que puede variar a lo largo de la ejecución del programa. Básicamente, se presentan dos opciones dependiendo de si se trata de un sistema con un espacio lógico por proceso o global. En el primer caso, el identificador estaría formado por una dirección lógica en el contexto de un proceso ([P, Dp]), mientras que en el segundo correspondería con una dirección lógica en un espacio global ([Dg]). A continuación, se aplica este modelo a los niveles habituales de la jerarquía, de manera ascendente, obviando el nivel de registros para no alargar innecesariamente la exposición. Ese nivel de registros lo gestiona directamente el sistema de compilación y no incumbe al sistema operativo, pero, en cualquier caso, se le puede aplicar perfectamente el modelo. Nivel de memoria secundaria Tanto si es un sistema con un espacio lógico por proceso como si es global, la traducción de la dirección lógica al bloque de memoria secundaria que la contiene se llevaría a cabo usando las tablas del esquema de memoria virtual (tablas de páginas y de regiones). Dado que sólo se requiere localizar el bloque en memoria secundaria cuando no está en la principal, no es necesario que este proceso de localización sea especialmente eficiente, no requiriendo, por tanto, una jerarquía de traducción. Se trata de un nivel formado por un único componente, que realiza una multiplexación espacial para repartir el espacio entre los procesos. Nivel de memoria principal Se corresponde también con un nivel formado por un único componente, que lleva a cabo una multiplexación espacial para repartir el espacio entre los procesos (aunque también temporal puesto que a un marco se le asignan distintas páginas a lo largo del tiempo). La traducción en este nivel la realiza la tabla de páginas, que permite encontrar el marco de página que contiene el dato requerido. Dado que esta traducción debe ser extremadamente eficiente, como se explicó previamente, se usa la TLB.

340

Sistemas operativos. Una visión aplicada

Existe, por tanto, a su vez, una jerarquía de traducción, a cuyos niveles se accede con el mismo identificador, pero para buscar la localización del dato en vez del dato propiamente dicho. Existen, habitualmente, dos niveles: las tablas de páginas y la TLB. Como se comentó previamente, la TLB puede incluir información de proceso, en cuyo caso realiza una multiplexación espacial del espacio dedicado a almacenar información de traducciones, o no incluirla, realizando una multiplexación temporal (es decir, no podrá existir información de varios procesos simultáneamente). En el caso de un multiprocesador, el nivel de TLB presenta múltiples componentes: una TLB por procesador. Además del procesador, a este nivel también acceden los dispositivos de E/S basados en DMA. En la mayoría de los sistemas, los dispositivos realizan operaciones de DMA usando direcciones físicas. Nivel de caché Para simplificar, sólo se considera un nivel de caché, pero se puede extrapolar a cualquier número de niveles. Se trata de un nivel que está formado por múltiples componentes. En el caso de un sistema multiprocesador, hay una caché por procesador. Incluso en un sistema monoprocesador puede haber múltiples componentes en el mismo nivel si se usa un procesador con caché de datos e instrucciones separadas (tenga en cuenta que no se trata de cachés disjuntas, puesto que una instrucción también es un dato cuando se está cargando en memoria). No requiere una jerarquía de traducción puesto que la información requerida para la traducción se maneja eficientemente al estar incluida en la propia lógica de control de la caché. En cuanto a la función de traducción planteada por el modelo, hay dos alternativas que establecen dos arquitecturas diferentes en el diseño de la caché: • Caché virtual. A este tipo de caché se accede con una dirección lógica, ya sea en el contexto de un proceso ([P, Dp]) o en un espacio global ([Dg]). El acceso a esta caché se realiza en paralelo con el de la memoria principal (con el acceso a la TLB, que comprueba aspectos como los permisos de acceso). La caché puede incluir información de proceso o no (multiplexación espacial o temporal, respectivamente). • Caché física. A este tipo de caché se accede con una dirección física ([Df]). Dado que en un sistema de memoria virtual la dirección física asociada a un objeto puede cambiar, esta caché requiere que se realice primero la etapa de traducción en el nivel de memoria principal (en el mejor de los casos, un acceso a la TLB) antes de poder realizar el acceso a la caché, para poder determinar cuál es la dirección física actual del objeto de memoria requerido. Esto provoca una falta de paralelismo en los accesos a memoria, puesto que no se puede consultar simultáneamente la caché y la TLB. Para paliar este problema, se puede usar una caché tal que el índice de selección que se utiliza para acceder a la misma corresponda con la parte de la dirección lógica que representa el desplazamiento dentro de la página, puesto que este valor sigue siendo el mismo en la dirección física. Con esta estrategia, se puede realizar la etapa de selección del conjunto de la caché que contiene el dato deseado mientras está trabajando la TLB, de manera que cuando termine la TLB, quede sólo por realizar la comparación de etiquetas. Esta solución, sin embargo, limita el tamaño máximo de la caché (una caché con correspondencia directa estaría limitada al tamaño de la página; una asociativa por conjuntos con dos líneas de caché por conjunto tendría un tamaño máximo de dos veces el tamaño de la página y, así sucesivamente). cia.

Una vez aplicado el modelo, en los siguientes apartados se analizan los posibles problemas de coheren-

Problemas de coherencia entre niveles adyacentes Este problema surge cuando se produce una actualización de un objeto de memoria en un nivel y hay una lectura de dicho objeto en otro nivel adyacente, no habiéndose propagado la actualización. A continuación, se plantean varias situaciones en las que se presenta este problema. En primer lugar, consideremos el problema de coherencia entre la caché y la memoria principal si un dispositivo realiza DMA directamente sobre la memoria principal. El problema puede presentarse en ambas direcciones:

Gestión de memoria

341

• Actualización en el nivel más rápido. Un proceso escribe datos en un buffer y se arranca una operación de DMA. Si la caché no usa write-through, algunos datos pueden no haberse actualizado en memoria principal y, por tanto, la operación de DMA estará leyendo datos incorrectos. En algunos sistemas, este problema lo resuelve directamente el hardware, pero, en otros, debe hacerlo el sistema operativo, forzando que se actualicen en memoria principal todos los datos del buffer. • Actualización en el nivel más lento. Una vez que se completa una operación de DMA sobre un buffer, un proceso puede seguir leyendo datos obsoletos presentes en la caché, puesto que no se han actualizado. Si el hardware no soluciona este problema, cuando concluya la operación de DMA, habrá que invalidar de la caché las direcciones correspondientes a ese buffer. Además de en la jerarquía de datos, pueden producirse problemas de este tipo en una jerarquía de traducción. Concretamente, existirán problemas de coherencia si se actualiza la información de la tabla de páginas (nivel más lento) y se usa información de la TLB ya obsoleta. Este problema atañe exclusivamente al sistema operativo y es labor del mismo resolverlo. Cada vez que el sistema operativo modifique algún campo de una entrada de la tabla de páginas que potencialmente pueda estar incluida en la TLB, debe solicitar la invalidación de dicha entrada en la TLB. Eso incluye cambios en la protección de una página, como sucede con la técnica del COW, cambios en los bits de referencia o de modificado, la invalidación de una página en la tabla de páginas, ya sea debido a que se expulsa o a que deja de ser válida al eliminarse la región que la contiene, etcétera. Problemas de coherencia entre componentes del mismo nivel En un multiprocesador existen niveles en los que hay múltiples componentes, uno por procesador. Es preciso asegurar que no se producen problemas de coherencia cuando se realiza una actualización de un dato en un componente y una consulta del mismo en otro componente de ese mismo nivel. Se presentan dos situaciones de este tipo: • Coherencia entre múltiples cachés. Normalmente, el hardware del multiprocesador resuelve este problema. • Coherencia entre múltiples TLB. De esta labor se tiene que encargar el sistema operativo. Dado que la TLB es básicamente un componente de consulta, los problemas de coherencia se restringen a cuando se invalida una entrada de la TLB. En un multiprocesador, es necesario invalidar todas las entradas que puedan existir en el sistema correspondientes a esa página. Habitualmente, esta invalidación se implementa usando IPI (interrupciones entre procesadores): desde el procesador donde se invalida la TLB se envía una IPI a todos los procesadores cuyas TLB puedan contener esa entrada. Dada la sobrecarga de esta operación, algunos sistemas operativos utilizan algoritmos de reemplazo que no actualizan el bit de referencia en su versión para multiprocesadores (poner a 0 el bit de referencia implicar invalidar entradas de las TLB). Como se comentó anteriormente, en un sistema monoprocesador también pueden aparecer este tipo de problemas si existen cachés de instrucciones y de datos separadas. Cuando se está cargando en memoria el código de un programa, éste pasa a través de la caché de datos. Sin embargo, a la hora de comenzar la ejecución, las instrucciones se leen de las cachés de instrucciones. Algunos procesadores mantienen de forma automática la coherencia de estas cachés. Sin embargo, en otros, debe ser el sistema operativo el encargado de llevarla a cabo. Para ello, después de completarse la carga del programa en memoria, el sistema operativo debe volcar a memoria las entradas de la caché de datos vinculadas con el rango de direcciones donde se ha cargado el código, así como invalidar las entradas de la caché de instrucciones correspondientes a dicho rango. Problemas de coherencia debidos al uso de homónimos Un homónimo se produce cuando un mismo nombre hace referencia a dos objetos diferentes. En el caso de la jerarquía de memoria, esta situación sólo se puede producir en sistemas que usan un espacio lógico por cada proceso, puesto que en ellos una misma dirección lógica se refiere a distintos objetos dependiendo de qué proceso la use. En cualquier caso, los homónimos sólo generan problemas de coherencia en sistemas donde

342

Sistemas operativos. Una visión aplicada

se realice una multiplexación temporal del componente de memoria, es decir, en aquéllos en los que no se gestiona información de proceso. Eso ocurre en la caché virtual y en la TLB cuando no incluyen información de proceso. El sistema operativo debe encargarse de resolver este problema, invalidando el componente de memoria (la TLB o la caché virtual) en cada cambio de contexto. Dentro de este apartado también se podría considerar el problema que surge en los accesos por DMA a memoria si el sistema operativo asigna otra página a un marco involucrado en la operación de DMA, que en la mayoría de los procesadores, usa directamente direcciones físicas. Se trata de un problema de homónimos que el sistema operativo resuelve reteniendo en memoria las páginas involucradas, tal como se explicó en la sección 5.5.8. Problemas de coherencia debidos al uso de sinónimos Un sinónimo se produce cuando dos o más nombres diferentes se refieren al mismo objeto. Esta situación es habitual en un sistema de memoria, puesto que va unida intrínsicamente al compartimiento de información. El problema surge cuando en un determinado nivel no se detecta que dos direcciones lógicas corresponden a un mismo objeto, gestionando dos copias independientes del mismo dato, con los problemas de coherencia asociados. En el nivel de memoria principal este problema queda resuelto mediante la caché de páginas, que asegura que las referencias a una página compartida utilizan el mismo marco. Tampoco se produce en la memoria secundaria, donde se usa un único bloque swap para la página compartida. En caso de utilizar una caché virtual con información de proceso, sí puede presentarse este problema de duplicidad de memoria en ese nivel, existiendo distintas alternativas para resolverlo: • El hardware de la caché lo detecta y resuelve automáticamente. • El sistema operativo establece restricciones en el alineamiento de las regiones compartidas (por ejemplo, que empiecen en una dirección que sea múltiplo de 64KB), asegurando que dos sinónimos ocupan la misma línea de la caché y, por tanto, nunca pueden almacenarse simultáneamente en la memoria caché. • El sistema operativo se asegura de que cuando ejecuta un proceso, no haya ninguna entrada en la caché asociada a otro proceso que sea un sinónimo de las usadas por el proceso actual, invalidando previamente las entradas conflictivas. • Se usa un esquema que utiliza un único espacio global, eliminado directamente el problema, puesto que no existen los sinónimos.

5.5.14. Operaciones del nivel de procesos y de regiones Añadir la técnica de memoria virtual a un esquema de paginación básicamente sólo cambia un aspecto en cuanto a la implementación de las operaciones de estos niveles: toda reserva de memoria del sistema se retrasa hasta justo el momento en el que se accede a la misma, realizándose en el contexto de la rutina de tratamiento del fallo de página o del fallo de protección. Las operaciones en el nivel de procesos son idénticas a las usadas en un esquema de paginación sin memoria virtual, que se estudiaron en la sección dedicada a este esquema. Las operaciones de regiones, vistas también en esa sección, sólo cambian en el aspecto reseñado en el párrafo anterior. A continuación, se analiza cómo se realizan las diversas operaciones sobre las regiones en un sistema con memoria virtual. Creación de una región Toda la gestión correspondiente al nivel de regiones es idéntica a la usada en un sistema de paginación sin memoria virtual. La variación se corresponde con la labor en el nivel de procesos, puesto que, en este caso, cuando se crea una región, no se le asigna memoria principal, dado que se cargará por demanda. Si se usa la técnica de la creación de páginas por demanda, ni siquiera hay que modificar la tabla de páginas. Si en el sistema hay preasignación de swap y se trata de una región privada o sin soporte, hay que reservar en el momento de la creación la zona correspondiente del swap. En un sistema sin preasignación, se reservará espacio en swap para una página cuando se expulse por primera vez estando modificada.

Gestión de memoria

343

En la creación de la imagen inicial del proceso durante la activación de un programa, se crean todas las regiones iniciales siguiendo el procedimiento que se acaba de describir. Por tanto, en un sistema que utilice tablas de páginas multinivel, basta con asignar una tabla del nivel superior con todas las entradas inválidas. Dado que la memoria virtual gestiona la información usando páginas completas y el sistema de ficheros utiliza bloques completos, la forma natural de asignar los bloques de un fichero ejecutable a las regiones del proceso sería la siguiente: • El primer bloque (bloque 0) del ejecutable corresponde con la cabecera del ejecutable, que no se carga en memoria durante la ejecución del programa. • A la región de código se le asignará un número entero de bloques en el fichero y un número entero de páginas en el mapa. Si la región ocupa C bloques, se almacenará en los bloques del ejecutable desde el 1 hasta el C. • La región de datos con valor inicial comienza justo después, ocupando también un número entero de bloques y de páginas. El problema de esta solución es que dedica un bloque completo a la cabecera, aunque normalmente sólo ocupa un centenar de bytes. Además, asigna más espacio del requerido a la región de código y de datos con valor inicial, al tener que redondear su tamaño a un número entero de bloques. Con esa estrategia, incluso un ejecutable muy pequeño ocuparía tres bloques. Ante esta deficiencia, algunos sistemas operativos usan este esquema alternativo, que optimiza el uso del disco haciendo que toda la información se almacene de forma contigua en el fichero: • La cabecera y el principio del código comparten el primer bloque del fichero. Por tanto, cuando se carga la primera página del mapa, se trae a memoria también la cabecera, aunque ésta no se necesite. • La región de código y de datos están dispuestas en el fichero de forma contigua. Por tanto, puede haber un bloque que contenga una primera parte de código y una segunda de datos con valor inicial. Dado que ese bloque debe ser visto a la vez como una página de código, con permiso de lectura y ejecución, y de datos con valor inicial, con permiso de lectura y escritura, habrá dos páginas diferentes, contiguas en el mapa, que se corresponderán con ese bloque. Se trata, por tanto, de un objeto compartido por el mismo proceso, pero con distinta protección. Dicho de otra forma, en la tabla de regiones, el último bloque del fichero ejecutable asociado a la región de código es el mismo que el primero de la región de datos con valor inicial. Obsérvese que el proceso sólo accederá a la primera parte de la última página de código y a la segunda parte de la primera página de la región de datos con valor inicial, quedando una zona sin usar en el mapa del proceso del tamaño de una página (aunque no alineada en memoria). Esta solución ahorra espacio en disco, presentando únicamente dos aspectos negativos, perfectamente tolerables: la sobrecarga de leer la cabecera del disco y el espacio en memoria que ocupa, a pesar de que su presencia en memoria no sea necesaria, y la pérdida de protección de la última página de código, que puede modificarse por error a través de la primera página de la región de datos sin que se detecte. El único detalle que falta por aclarar es dónde se crea el contenido inicial de la pila, formado por los argumentos y las variables de entorno que recibe el programa. Las dos opciones habituales son almacenarlo en marcos de página y hacer que la tabla de páginas inicial haga referencia a esos marcos, o bien guardarlo en bloques de swap, indicándolo en las entradas de la tabla de páginas involucradas. En la figura 5.75 se muestra cómo es la imagen de memoria inicial de un proceso en un sistema donde se usa la segunda opción de implementación de pila planteada. Para simplificar, se ha supuesto que se utiliza una tabla de páginas de un solo nivel. En esta figura se muestra, con zonas sombreadas, cómo la cabecera ocupa una primera parte de la región de código, y cómo la última parte de la segunda página de código y la primera de la de datos con valor inicial no son utilizadas. La tabla de regiones muestra el compartimiento del bloque 1 del fichero por parte de la región de código y la de datos con valor inicial. Eliminación de una región Nuevamente, las acciones son iguales que en un sistema de paginación sin memoria virtual. Además, si se trata de una región privada, hay que liberar los bloques de swap asociados a la región.

344

Sistemas operativos. Una visión aplicada 0 8192 R-X Comp. F Bl. inicial 0 8192 8192 RW- Privada F Bl. inicial 1

Fichero F Swap (SW1) Bloq. 0 Bloq. 1 Bloq. 2

Bloq. 0 Bloq. 1 Bloq. 2

Fichero

Fichero

.........

Mapa de memoria inicial 0 8192 16384 20480 BFFFF000 C0000000

BCP

Código t. de regiones Datos con valor inicial Datos sin valor inicial

t. páginas

.........

16384 4096 RW- Privada Anónima BFFFF000 4096 RW- Privada Anónima

Memoria Marco 0 Marco 1

......... Pila

00000 I 000 00000 I 000 00000 I 000 00000 I 000 00000 I 000 ......... 00000 I 000 ................

.........................

Marco 2 Marco 3 Marco 4 ........

00002 I SW1

Figura 5.75 Estado inicial de ejecución de un programa. Cambio del tamaño de una región Vuelve a ser muy similar a cómo se realiza en un esquema de paginación sin memoria virtual. Con respecto a una disminución de tamaño en una región, si se trata de una región privada, habrá que liberar los bloques de swap asociados a la misma. Por lo que se refiere a un aumento de tamaño, la única diferencia con el sistema sin memoria virtual es que, como en la creación de una región, no hay que asignar marcos ni actualizar la tabla de páginas. Sólo se necesita ajustar el tamaño en la tabla de regiones. Si en el sistema hay preasignación de swap y se trata de una región privada o sin soporte, hay que reservar el espacio requerido en el swap. El tratamiento de la expansión de la pila es algo más complejo, ya que no proviene de una solicitud del proceso, sino de la propia evolución de la pila. Cuando se produce una expansión de pila, se genera un fallo de página asociado a una dirección que se corresponde con un hueco. El sistema operativo podría pensar, en principio, que se trata de un acceso erróneo, puesto que no corresponde a ninguna región. Para diferenciarlo, debe comparar la dirección que causó el fallo con el puntero de pila. Si la dirección es mayor, está dentro de la pila. Se trata de una expansión de la pila que implica simplemente actualizar la tabla de regiones, reservar espacio de swap si hay preasignación, y servir el fallo de página de manera convencional. En caso contrario, se trata de un acceso erróneo. Tenga en cuenta que si hay un hueco de una sola página entre la pila y la región anterior, no se permitirá la expansión, ya que si se llevara a cabo, la próxima expansión usaría directamente una página de la otra región sin avisar al sistema operativo (este hueco actúa como una página de seguridad). Duplicado de una región Esta operación sí cambia de manera considerable al aplicar en este caso la técnica de copia diferida basada en el COW, tal como se explicó en la sección 5.5.11. Con esta técnica, la operación de duplicado no requiere reservar marcos de página ni realizar una copia del contenido de las páginas de la región. Basta con duplicar las entradas de la tabla de páginas que corresponden con la región, marcándolas como de sólo lectura tanto en la tabla de páginas origen como en la destino. Asimismo, habrá que incrementar los contadores de referencias de los bloques de swap y de los marcos de página asociados a la región. Con esta técnica, se optimiza considerablemente la ejecución de un servicio fork, ya que sólo es necesario duplicar su tabla de páginas, en vez de su mapa. En la figura 5.76 se muestra cómo se llevaría a cabo una operación fork. En ella se puede apreciar como esta operación implica duplicar tanto la tabla de regiones como la de páginas. Obsérvese como se ha eliminado el permiso de escritura en la quinta entrada de ambas tablas de páginas. Para simplificar, se ha supuesto que se utiliza una tabla de páginas de un solo nivel.

Gestión de memoria

345

Mapa de memoria de P1 0 8192 16384 20480 BFFFF000 C0000000

Código Datos con valor inicial Datos sin valor inicial ......... Pila

BCP de P1 t. de regiones

Mapa de memoria de P2 0 8192 16384 20480 BFFFF000 C0000000

t. páginas

Código Datos con valor inicial Datos sin valor inicial

0 8192 R-X Comp. F Bl. inicial 0

0 8192 R-X Comp. F Bl. inicial 0

8192 8192 RW- Privada F Bl. inicial 1

8192 8192 RW- Privada F Bl. inicial 1

16384 4096 RW- Privada Anónima

BCP de P2 t. de regiones t. páginas

Bloq. 0 Bloq. 1 Bloq. 2

Bloq. 0 Bloq. 1 Bloq. 2

Fichero

Fichero

.........

.........

16384 4096 RW- Privada Anónima

BFFFF000 4096 RW- Privada Anónima

BFFFF000 4096 RW- Privada Anónima

00004 V R-X 00000 I 000 00001 I SW1 00000 I 000 00004 V R-......... 00000 I 000 ................

00004 V R-X 00000 I 000 00001 I SW1 00000 I 000 00004 V R-......... 00000 I 000 ................

00002 I SW1

00002 I SW1

......... Pila

Fichero F Swap (SW1)

Memoria Marco 0 Página 4 de P1 P2 Marco 1 Marco 2 Marco 3 Página 0 de P1 P2 Marco 4 ........ .........................

Figura 5.76 Resultado de la llamada fork.

5.5.15. Ficheros proyectados en memoria La generalización de la técnica de memoria virtual permite ofrecer a los usuarios una forma alternativa de acceder a los ficheros. Como se ha visto en la sección anterior, en un sistema de memoria virtual, se hacen corresponder entradas de la tabla de páginas con bloques del fichero ejecutable. La técnica de proyección de ficheros en memoria plantea usar esa misma idea, pero aplicada a cualquier fichero. El sistema operativo va a permitir que un programa solicite que se haga corresponder una zona de su mapa de memoria con los bloques de un fichero cualquiera, ya sea completo o parte del mismo. En la solicitud, el programa especifica el tipo de protección asociada a la región y si la región será compartida o privada. El sistema operativo simplemente realiza una operación de crear región, tal como se ha explicado en la sección previa. Una vez que el fichero está proyectado, si el programa accede a una dirección de memoria perteneciente a la región asociada al fichero, estará accediendo al fichero. El programa ya no tiene que usar los servicios del sistema operativo para leer (read) y escribir (write) en el fichero. La figura 5.77 muestra un ejemplo de una proyección de un fichero de 40.000 bytes. Como se puede apreciar en la misma, existe una entrada en la tabla de regiones que representa la proyección y que almacena las características de la misma; en este caso, es una proyección compartida de lectura y escritura. En el ejemplo de la figura, si el programa lee un byte de la dirección de memoria 20480, estará leyendo el primer byte del fichero, mientras que si escribe un byte en la dirección 20481, estará escribiendo en el segundo byte del fichero. En la figura, se ha supuesto que ya se ha producido este acceso y, por ello, el primer bloque del fichero está residente en el marco 4 de la memoria. La proyección de un fichero no implica que se le asigne memoria principal. El propio mecanismo de memoria virtual será el que se encargue de ir trayendo a memoria principal los bloques del fichero cuando se produzca un fallo de página al intentar acceder a la región asociada al mismo, y de escribirlos cuando la página sea expulsada estando modificada. El acceso a un fichero mediante su proyección en memoria presenta numerosas ventajas sobre el acceso convencional basado en los servicios de lectura y escritura. A continuación, se detallan algunas de estas ventajas:

346

Sistemas operativos. Una visión aplicada ............ ............ ............ ............ ............

Mapa de memoria

20480 40000 RW- Comp F Bl. inicial 0

Código Datos con valor inicial Datos sin valor inicial

Fichero F Bloq. 0 Bloq. 1 Bloq. 2 Fichero

.........

............

BCP 20480

Fichero proyectado F

t. de regiones t. páginas

............ ............ ............ ............

Memoria Marco 0 Marco 1

......... Pila

......... 00000 II 000 ................ 00000 000 00004 V RW00000 I 000 00000 I 000 ......... 00000 I 000 ................

Bloque 0 de F .........................

Marco 2 Marco 3 Marco 4 ........

Figura 5.77 Proyección de un fichero. • Se disminuye considerablemente el número de llamadas al sistema necesarias para acceder a un fichero. Con esta nueva técnica, una vez que el fichero está proyectado, no hay que realizar ninguna llamada adicional. Esta reducción implica una mejora considerable en los tiempos de acceso, puesto que, como ya es conocido, la activación de una llamada al sistema tiene asociada una considerable sobrecarga. • Se evitan copias intermedias de la información. Esto repercute también en un acceso más eficiente. Con esta técnica, el sistema operativo transfiere directamente la información entre la memoria y el fichero. Con la forma de acceso convencional, todas las transferencias se realizan pasando por la caché de bloques del sistema de ficheros. • Se facilita la forma de programar los accesos a los ficheros. Una vez proyectado el fichero, se accede al mismo igual que a cualquier estructura de datos en memoria que haya declarado el programa. No es necesario utilizar ningún servicio especial del sistema operativo para acceder al mismo. Así, por ejemplo, dado un programa que realiza un cierto tratamiento sobre una matriz de datos almacenada en memoria, su modificación para que leyera la matriz de un fichero sólo implicaría añadir al principio del programa la proyección del fichero. No sería necesario modificar el código restante.

5.6. SERVICIOS DE GESTIÓN DE MEMORIA Como se ha podido apreciar a lo largo del capítulo, las labores que lleva a cabo el sistema de gestión de memoria son más bien de carácter interno. Más que proporcionar una colección de servicios explícitos a las aplicaciones, el objetivo del sistema de memoria tiene un carácter más implícito: dotar a las aplicaciones de un espacio de almacenamiento para su ejecución que satisfaga las necesidades de las mismas. Además, algunos servicios de gestión de memoria usados por los programas, como, por ejemplo, los vinculados con el uso de memoria dinámica, no son labor directa del sistema operativo, sino que los suministra el propio lenguaje de programación. Debido a todo ello, este componente del sistema operativo apenas ofrece servicios directos a las aplicaciones. Entre ese número relativamente reducido de servicios, en esta sección se ha considerado que los de mayor interés se pueden agrupar en dos categorías:

Gestión de memoria

347

• Servicios de proyección de ficheros, que permiten incluir en el mapa de memoria de un proceso un fichero o parte del mismo. Bajo esta categoría existirán, básicamente, dos servicios: ⎯ Proyección de un fichero. Con esta operación se crea una región asociada al objeto de memoria almacenado en el fichero. Normalmente, se pueden especificar algunas propiedades de esta nueva región. Por ejemplo, el tipo de protección o si la región es privada o compartida. ⎯ Desproyección de un fichero. Este servicio elimina una proyección previa o parte de la misma. • Servicios de montaje explícito de bibliotecas, que permiten que un programa cargue en tiempo de ejecución una biblioteca dinámica y use la funcionalidad proporcionada por la misma, tal como se analizó en la sección 5.3.2. En esta categoría se englobarían, básicamente, tres servicios: ⎯ Carga de la biblioteca. Este servicio realiza la carga de la biblioteca, llevando a cabo todas las operaciones de montaje requeridas. ⎯ Acceso a un símbolo de la biblioteca. Con esta operación, el programa puede tener acceso a uno de los símbolos exportados por la biblioteca, ya sea éste una función o una variable. ⎯ Descarga de la biblioteca. Este servicio elimina la biblioteca del mapa del proceso. En las siguientes secciones, se muestran los servicios proporcionados por UNIX y Windows dentro de estas dos categorías.

5.6.1. Servicios UNIX de proyección de ficheros Los servicios de gestión de memoria más frecuentemente utilizados son los que permiten la proyección y desproyección de ficheros (mmap, munmap). ž caddr_t mmap (caddr_t direccion, size_t longitud, int protec, int indicadores, int descriptor, off_t despl);

Este servicio proyecta el fichero especificado creando una región con las características indicadas en la llamada. El primer parámetro indica la dirección del mapa donde se quiere que se proyecte el fichero. Generalmente, se especifica un valor nulo para indicar que se prefiere que sea el sistema el que decida donde proyectar el fichero. En cualquier caso, la función devolverá la dirección de proyección utilizada. El parámetro descriptor corresponde con el descriptor del fichero que se pretende proyectar (que debe estar previamente abierto), y los parámetros despl y longitud establecen qué zona del fichero se proyecta: desde la posición despl hasta desp + longitud. El argumento protec establece la protección de la región, que puede ser de lectura (PROT_READ), de escritura (PROT_WRITE), de ejecución (PROT_EXEC), o cualquier combinación de ellas. Esta protección debe ser compatible con el modo de apertura del fichero. Por último, el parámetro indicadores permite establecer ciertas propiedades de la región: • MAP_SHARED. La región es compartida. Las modificaciones sobre la región afectarán al fichero. Un proceso hijo compartirá esta región con el padre. • MAP_PRIVATE. La región es privada. Las modificaciones sobre la región no afectarán al fichero. Un proceso hijo no compartirá esta región con el padre, sino que obtendrá un duplicado de la misma. • MAP_FIXED. El fichero debe proyectarse justo en la dirección especificada en el primer parámetro. Esta opción se utiliza, por ejemplo, para cargar el código de una biblioteca dinámica, si en el sistema se utiliza un esquema de gestión de bibliotecas dinámicas, tal que cada biblioteca tiene asignado un rango de direcciones fijo. En el caso de que se quiera proyectar una región sin soporte (región anónima), en algunos sistemas se puede especificar el valor MAP_ANON en el parámetro indicadores. Otros sistemas UNIX no ofrecen

348

Sistemas operativos. Una visión aplicada

esta opción, pero permiten proyectar el dispositivo /dev/zero para lograr el mismo objetivo. Esta opción se puede usar para cargar la región de datos sin valor inicial de una biblioteca dinámica. ž int munmap(caddr_t direccion, size_t longitud); Este servicio elimina una proyección previa o parte de la misma. Los parámetros direccion y longitud definen la región (o la parte de la región) que se quiere eliminar del mapa del proceso. Antes de presentar ejemplos del uso de estos servicios, hay que aclarar que se utilizan conjuntamente con los servicios de manejo de ficheros que se presentarán en el capítulo que trata este tema. Por ello, para una buena comprensión de los ejemplos, se deben estudiar también los servicios explicados en ese capítulo. A continuación, se muestran dos ejemplos del uso de estas funciones. El primero es el programa 5.5 que cuenta cuántas veces aparece un determinado carácter en un fichero utilizando la técnica de proyección en memoria. Programa 5.5 Programa que cuenta el número de apariciones de un carácter en un fichero. #include #include #include #include #include #include int main(int argc, char *argv[]) { int i, fd, contador=0; char caracter; char *org, *p; struct stat bstat; if (argc!=3) { fprintf (stderr, ”Uso: %s caracter fichero\n”, argv[0]); return 1; } /* Para simplificar, se supone que el carácter a contar corresponde con el primero del primer argumento */ caracter=argv[1][0]; /* Abre el fichero para lectura */ if ((fd=open(argv[2], O_RDONLY))