Práctica DSO: memon

Práctica de carácter obligatorio que se corresponde con el 20% de la nota total de la asignatura.

Plazos de entrega

Se determina como plazo máximo para la entrega de esta práctica la fecha del examen de la asignatura en cada convocatoria.

Objetivo

El principal objetivo es llevar a la práctica algunos de los conceptos estudiados en el tema teórico de gestión de memoria. Concretamente, la práctica abarcará aspectos de gestión de memoria tales como los siguientes:

  • Estructuras de datos del gestor de memoria: tablas de regiones, tablas de páginas y tablas de marcos.
  • Tratamiento del fallo de página.
  • Algoritmos de reemplazo.
  • Análisis del uso de memoria de los programas.

La práctica va a consistir en el desarrollo de una aplicación (“memon”) que permita conocer el comportamiento de un programa con respecto a su uso de memoria dependiendo de la cantidad de memoria física disponible y del algoritmo de reemplazo utilizado.

Como se irá viendo paulatinamente, el desarrollo de este monitor va a implicar enfrentarse a situaciones muy similares a las que tiene que afrontar el gestor de memoria de un sistema operativo real. Además, el monitor que se pretende desarrollar tiene interés por sí mismo, ya que se trata de una herramienta que, por un lado, permite comparar diversos algoritmos de reemplazo y, por otro, facilita el análisis de cómo usan los programas reales la memoria dependiendo de sus características específicas. Nótese que el monitor no tendrá un carácter “intrusivo” en la ejecución del programa: el programa se completará realizando la labor para la que estaba programado. Simplemente, la ejecución habrá sido más lenta debido a la sobrecarga de la monitorización.

Por último, hay que resaltar que, por simplicidad, el estudio del uso de memoria de los programas no va a abarcar la región de de pila, centrándose en las regiones de código, datos con y sin valor inicial, heap y las correspondientes a archivos proyectados, ya sea con proyección privada o compartida.

Debido a cambios en el código de apoyo de la práctica con respecto a cursos anteriores, se recomienda que aquellos alumnos que quieran realizar la práctica basándose en el material de cursos previos se instalen el nuevo material de apoyo y copien de la versión del curso pasado sólo los ficheros que modifica el alumno durante la práctica.

Si no funciona correctamente en su máquina el material de apoyo proporcionado, pruebe a ejecutar previamente el siguiente mandato:

ulimit -s unlimited

Descripción

Cualquier programador que trabaje en el entorno C-UNIX conoce y “teme” el clásico mensaje: ”Segmentation fault (core dumped)”. Detrás de este mensaje está la detección por parte del sistema operativo de un acceso a memoria inválido (ya sea un acceso a una dirección no asignada o un intento de realizar una operación no permitida sobre una determinada dirección de memoria) y la consiguiente generación de la señal “SEGV” que, al no ser normalmente capturada por el programa, causa la terminación anómala del mismo.

Los programas convencionales generalmente no capturan esta señal. Sin embargo, su captura y tratamiento, junto con el uso de la llamada al sistema “mprotect”, conforman el punto de arranque de esta práctica.

La llamada al sistema “mprotect” permite establecer unos determinados permisos de acceso (o sea, especificar la protección, de ahí proviene su nombre) sobre un rango de direcciones del mapa del proceso que corresponda con un número entero de páginas. Se puede especificar permiso de lectura (“PROT_READ”), de ejecución (“PROT_EXEC”) y de escritura (“PROT_WRITE”). Como es habitual en UNIX, se puede especificar una combinación de permisos uniéndolos con el operador “|”. Además, se pueden quitar todos los permisos especificando “PROT_NONE”.

Nótese que con “mprotect” podemos modificar los permisos originales (y razonables) que estableció el sistema operativo. Así, por ejemplo, podríamos hacer que una determinada página de código tuviera permisos de escritura. Para más detalles sobre esta llamada, se recomienda consultar el manual. Sin embargo, conviene resaltar un último aspecto: los permisos no son acumulativos. Por ejemplo, si sobre una página que tenía previamente permiso de lectura se realiza un “mprotect” especificando sólo “PROT_WRITE”, la página sólo quedará con permiso de escritura.

Mediante la captura de la señal “SEGV” y el uso de “mprotect”, el monitor puede supervisar la ejecución de un programa suponiendo que existe cierto número de marcos disponibles para el mismo y que se usa un determinado algoritmo de reemplazo. Esta supervisión se basa en las siguientes pautas:

  • Inicialmente, se inhabilita el acceso a la página mediante el uso de “mprotect”. Podría decirse que “cubrimos” la página para que no pueda accederse.
  • Cuando el programa intenta acceder a la página, se produce la señal “SEGV”. Es en el tratamiento de esta señal donde el monitor es consciente de que el programa ha accedido a la página y, por tanto, puede anotar este hecho. Es importante resaltar que, como parte de este tratamiento, el monitor debe devolver los permisos originales a la página mediante “mprotect” (o sea, “destapar” la página). Si no fuera así, el programa entraría en un bucle infinito, ya que, después de tratar la señal, se vuelve a ejecutar de nuevo la instrucción que la causó y, por tanto, si no se ha habilitado el acceso vuelve a producirse la señal. Esta repetición de la ejecución de la instrucción después del tratamiento de la señal es lo que hace que el monitor no sea “intrusivo”, puesto que todas las instrucciones del programa original se ejecutan. Es interesante hacer notar que la ejecución de una misma instrucción puede generar varias señales de este tipo: tanto cuando se lee la instrucción como cuando se accede a cada uno de los operandos en memoria que pueda tener la misma, ya que pueden residir en páginas distintas.
  • Nótese que puede ocurrir que el programa que se monitoriza sea erróneo y genere un error de acceso, ya sea por intentar acceder a una dirección inválida o debido a que intenta realizar una operación no permitida sobre una dirección válida (por ejemplo, intenta escribir sobre la región de código). Esta situación también causaría una señal “SEGV”, pero el monitor debe darse cuenta de que realmente se trata de un error de acceso, por lo que debe terminar la monitorización (no tiene sentido continuar supervisando un programa erróneo). Para poder distinguir si el acceso es válido, el monitor debe mantener estructuras de datos que reflejen el estado del mapa del programa que se supervisa. Estas estructuras van a ser similares, hasta cierto punto, a las tablas de regiones y tablas de páginas usadas por el gestor de memoria de un sistema operativo.
  • Con respecto al número de marcos disponibles para la ejecución del proceso, este valor va a establecer el número máximo de páginas que pueden tener sus permisos habilitadas. Siguiendo con el símil, este número determina cuántas páginas como mucho pueden estar “destapadas”. Cada vez que se produce una señal “SEGV”, además de actualizar sus estadísticas de accesos, el monitor comprobará si el número de páginas habilitadas ha llegado a este límite (o sea, si se ha llenado la memoria). Si ocurre esta situación, habrá que inhabilitar mediante “mprotect” (“expulsar”) la página seleccionada por el algoritmo de reemplazo elegido. Nótese que esta gestión implica que el monitor debe almacenar una estructura de datos, similar a la tabla de marcos de un sistema operativo, que refleje qué marcos están libres y cuáles usados y por qué página. Como resultado de la aplicación de estas pautas, el monitor puede obtener exactamente los mismos resultados que ocurrirían en un sistema real que dedicara el número de marcos especificados a la ejecución del proceso y que usara el algoritmo de reemplazo indicado. El monitor presenta muchas similitudes con el gestor de memoria de un sistema operativo. De hecho, el alumno podrá darse cuenta de que se trata de otra aplicación de la idea del hardware virtual usada en el minikernel: un fallo de página real producido por un acceso inválido a una página con acceso inhabilitado (generado por la MMU del procesador), el sistema operativo lo convierte en una señal “SEGV”, que el monitor trata como un fallo de página del programa que supervisa. A continuación, para incidir en esta similitud entre el monitor y el gestor de memoria de un sistema operativo, se exponen de forma comparada diversos aspectos de su modo de operación:
    • En un sistema operativo real con memoria virtual basada en paginación por demanda, cuando se crea una región todas sus páginas se marcan como no residentes. De manera similar, en el monitor se dejarán inaccesibles mediante el uso de “mprotect”.
    • Cuando se accede a una página no residente en un sistema operativo real, se produce un fallo de página. En este caso se generará la señal “SEGV”. El tratamiento de “SEGV” tendrá muchos aspectos en común con el tratamiento de un fallo de página real.
    • Cuando se trae una página a memoria en un sistema real, se marca como residente y, por tanto, los siguientes accesos no causarán fallos de página. En el monitor se usará “mprotect” para habilitar los próximos accesos.
    • En un sistema real la memoria física disponible limita el número de páginas que pueden estar residentes. Si hay un fallo y no hay ningún marco libre, se aplica un algoritmo de reemplazo que elige una página residente que se expulsa de memoria. De manera similar, el monitor prohibirá el acceso a la página seleccionada como “víctima” por el algoritmo de reemplazo. Nótese que el monitor se encargará de que en cada momento sólo pueda estar habilitado el acceso a, como mucho, tantas páginas como marcos tenga la memoria física.
    • Ambos usan estructuras de datos de similares características:
      • Una tabla de regiones, que contenga las características de cada región. Téngase en cuenta que, por ejemplo, es necesario saber qué rango de direcciones ocupa cada región para poder diferenciar dentro del tratamiento de “SEGV” si se trata realmente de un fallo de página o en verdad se ha producido un acceso inválido (o sea, un verdadero “SEGV”).
      • Una tabla de páginas por cada región. Es necesario saber el estado de cada página de la región. Por ejemplo, hace falta conocer qué páginas están residentes y cuáles no.
      • Una tabla de marcos. Esta estructura permite conocer qué marcos están libres y cuáles ocupados, especificando qué página contienen (para poder invalidarla en caso de reemplazo).

Para llevar a cabo su labor, el monitor cuenta con la colaboración de un módulo de apoyo que se encargará en cada momento de informar al monitor de qué regiones forman el mapa del proceso y cuáles son sus características (dirección inicial, tamaño, protección, si está vinculada a un archivo o es anónima y si es compartida o privada). Este módulo se dedica a interceptar las llamadas del programa que puedan afectar al mapa de memoria del proceso para informar de ello al monitor. En concreto, el entorno de apoyo detecta e informa cuando se crea una nueva región en el mapa, cuando cambia el tamaño de una región existente y cuando se elimina una región. Hay que resaltar que el sistema operativo real se encargará de llevar a cabo todas esta operaciones sobre el mapa del proceso. El módulo de apoyo simplemente detecta cuando se producen y avisa al monitor del hecho. Por tanto, una vez arrancado el programa cuya ejecución se pretende supervisar, el monitor sólo tomará el control debido a cuatro posibles eventos: se ha producido una señal “SEGV”, se ha creado una región, ha cambiado el tamaño de una región o se ha eliminado una región:

  • Como se comentó previamente, en el caso de la creación, el monitor debe anotar las características de la región e inhabilitar el acceso a sus páginas.
  • Cuando se trata de una eliminación, el monitor debe anotar este hecho en sus estructuras de datos, liberando además los marcos que contuvieran páginas de una región, siempre que ésta fuera de tipo privado. Nótese que, siguiendo la estrategia que usan la mayoría de los sistemas operativos, cuando se elimina una región compartida del mapa del proceso, no se van a eliminar de memoria física sus páginas residentes, dando así oportunidad para que puedan usarlas otros procesos que compartiesen esa misma región (se mantiene esta estrategia aunque, evidentemente, esto no puede ocurrir en la práctica ya que sólo hay un proceso). Es importante resaltar que la operación de eliminar una región no conlleva el uso de “mprotect”, puesto que el sistema operativo ya eliminó la región y si se hace un “mprotect” daría error.
  • Con respecto a la operación de cambio de tamaño, su tratamiento dependerá de si trata de una expansión de la región o de una contracción. Si el tamaño aumenta, la zona añadida a la región tiene un tratamiento similar, hasta cierto punto, al que se realiza en la creación de una nueva región (hay que inhabilitar el acceso a esta zona expandida). En caso de que disminuya, el tratamiento de la zona que desaparece tendrá puntos en común con el que se realiza en la eliminación de una región (se deben liberar los marcos que contenían esta zona que ha desaparecido).
  • Por lo que se refiere al tratamiento de la señal “SEGV”, será muy similar al tratamiento del fallo de página que se estudia en la teoría de la asignatura, pero donde validar e invalidar una página se corresponde con dar y quitar permisos con “mprotect”, y se sustituyen los accesos reales a los dispositivos para traer y llevar páginas por la obtención de estadísticas sobre dichos accesos.

Organización del software del monitor

Dada la extensión y complejidad del monitor planteado, “las buenas noticias” son que una parte bastante apreciable del trabajo ya se proporciona como código de apoyo inicial. A continuación, se describen los distintos módulos que forman parte de este software de apoyo.

Fichero "memon.c"

Este fichero contiene el programa principal del monitor. El alumno NO debe modificar este fichero, puesto que ya posee la funcionalidad requerida. Se encarga de realizar las siguientes operaciones:

  • Instalar la función de tratamiento de “SEGV”
  • Inicializar la función de reemplazo dependiendo del nombre que tenga el programa (si el nombre del programa contiene la palabra “FIFO”, se usará el algoritmo FIFO, mientras que si contiene la palabra “reloj”, se utilizará el del reloj)
  • Averiguar el tamaño de la página (mediante la llamada “sysconf”)
  • Iniciar la tabla de marcos (llamando a la función “crear_tabla_marcos” del módulo que gestiona los marcos)
  • Invocar el programa a monitorizar (llamando a la función “ejecutar_programa” del módulo de apoyo)
  • Imprimir las estadísticas obtenidas por el monitor

El módulo apoyo

Este módulo, que es dependiente del sistema operativo y está contenido en el fichero “apoyo.o”, se encarga de ofrecer la función que permite arrancar la ejecución del programa a monitorizar (“ejecutar_programa”), que, como se comentó previamente, es invocada desde “memon.c”. Además, proporciona la función que permite instalar la función de tratamiento de “SEGV” (“tratar_SEGV”).

Asimismo, se dedica a interceptar las llamadas del programa a monitorizar que puedan afectar al mapa de memoria del proceso para informar de ello al monitor. En concreto, el entorno de apoyo detecta e informa de las siguientes situaciones:

  • Creación de una nueva región en el mapa. Este evento se produce cuando el entorno de apoyo detecta que se ha creado una nueva región e invocará a la rutina “creacion_region” del módulo “mapa” para informarle de este evento y de las características de la nueva región. La creación de una nueva región puede estar asociada a tres situaciones:
    • En la creación del programa a supervisar (realizada en la rutina de apoyo “ejecutar_programa”) se crean las regiones iniciales del proceso y se informa de ello al monitor.
    • El programa a supervisar realiza una llamada “mmap”.
    • El programa a supervisar realiza una primera reserva de memoria dinámica que causa la creación del heap. Nótese que en esta práctica se considera al heap como una región inicialmente vacía que es independiente de la región de datos sin valor inicial.
  • Eliminación de una región. El entorno ha detectado que se ha eliminado una región e informa al monitor invocando la función “eliminacion_region” del módulo “mapa” para informarle de este evento. Este evento va a ser consecuencia de que el programa ha ejecutado la llamada “munmap” o de que ha terminado su ejecución.
  • Cambio del tamaño de una región existente. El entorno detecta un cambio de tamaño en una región y le informa el monitor llamando a su función “cambio_tam_region”. Este cambio de tamaño estará asociado a la evolución de la región del heap. Hay que resaltar que en la mayoría de los sistemas reales nunca disminuye el tamaño del heap, aunque el programa libere memoria dinámica previamente reservada, para evitar que la rutina de liberación tenga que realizar cada vez una serie de comprobaciones que pueden afectar a su eficiencia. En el módulo de apoyo de la práctica, sin embargo, si se detecta esta situación y se informa al monitor cuando disminuye el tamaño del heap.

A continuación, se incluyen los prototipos de estas funciones usadas por el entorno de apoyo para notificar los cambios en el mapa del proceso:

/* se informa de que se ha creado una región
 
    dir: dirección de comienzo de la región
    nodoi: archivo al que está vinculada (0 si es anónima)
    prot: permisos de acceso a la región
    tamano: tamaño de la región
    compartida: ¿es una región de tipo compartida?
*/
void creacion_region(void *dir, int nodoi, int prot,
	int tamano, int compartida);
 
/* se informa de que se ha eliminado una región
    dir: dirección de comienzo de la región
*/
void eliminacion_region(const void *dir);
 
/* se informa de que ha cambiado el tamaño de una región
 
    dir: dirección de comienzo de la región
    tamano: nuevo tamaño de la región
*/
void cambio_tam_region(void *dir, int tam);

En el fichero “apoyo.h”, además de los prototipos de “ejecutar_programa” y “tratar_SEGV”, se ofrecen unas macros que facilitan la gestión de la máscara de protección usada por “mprotect”.

Módulo "marcos"

Contiene la gestión de una tabla de marcos, incluyendo un algoritmo de reemplazo FIFO. El alumno sólo debe modificar este módulo para incluir el algoritmo del reloj (rutina “reemplazo_reloj”). Se debe mantener la interfaz del módulo. No se modificará, por tanto, el fichero de cabecera “marcos.h”.

El módulo proporciona las siguientes funciones:

  • “crear_tabla_marcos”: Invocada desde el programa principal.
  • “reservar_marco_libre”: Se invocará desde la rutina de tratamiento del fallo. Busca y reserva un marco libre, devolviendo un valor de -1 si no encuentra ninguno.
  • Rutinas de reemplazo. Se invocarán desde la rutina de tratamiento del fallo, en el caso de que no haya marcos libres. La rutina de tratamiento del fallo (incluida en el módulo “fallo”) invocará directamente a la función “reemplazo”, que en verdad, dependiendo del nombre del ejecutable del monitor, se corresponderá con la rutina “reemplazo_FIFO”, si el ejecutable se denomina “memon_FIFO”, o con “reemplazo_reloj”, en caso de que se llame “memon_reloj”. Estas rutinas de reemplazo devuelven el marco elegido como “víctima”. Nótese que este marco retornado ya está reservado, por lo que no debe usarse en esta situación la función “reservar_marco_libre”.
    Es importante resaltar que “reemplazo_reloj” ES LA ÚNICA RUTINA DE ESTE MÓDULO QUE DEBE PROGRAMAR EL ALUMNO.
  • “rellenar_entrada_marco”: Permite especificar qué página tiene almacenada un determinado marco. Se invocará desde la rutina de tratamiento del fallo.
  • “leer_entrada_marco”: Permite obtener qué página hay almacenada en un determinado marco. Se invocará desde la rutina de tratamiento del fallo.
  • “eliminar_pagina_de_marco”: Libera un marco debido a que la página que contiene ya no existe. Se invocará cuando se elimine una región de carácter privado.
  • “imprimir_tabla_marcos”: Rutina de utilidad para la depuración.

Módulo "mapa"

Este módulo contiene las operaciones relacionadas con la gestión del mapa del proceso, tanto de sus regiones como las páginas contenidas en las mismas. Contiene la definición completa de la tabla de regiones y algunas de las funciones que la gestionan. Así, ya están programadas las funciones de interfaz “creacion_region” y “eliminacion_region”, así como las funciones internas que las soportan. Sin embargo, no está programada la función “cambio_tam_region”, que deberá desarrollar el alumno.

Con respecto a las tablas de páginas, incluye una definición inicial (evidentemente, incompleta) y sólo parte de su gestión. Ya están incluidas la creación y eliminación de las tablas de páginas. EL ALUMNO DEBE COMENZAR COMPLETANDO LAS RUTINAS “iniciar_entrada_tpag” (incluyendo el “mprotect” correspondiente) y “liberar_entrada_tpag”. Además, deberá ir completando sucesivamente la definición de la entrada de la tabla de páginas.

Nótese que la tabla de regiones es un vector con un tamaño estático, mientras que las tablas de páginas se reservan en memoria dinámica y su tamaño varía cuando cambia el de la región.

Este módulo también exporta tres funciones que pueden ser útiles para otros módulos:

  • “regnum”: Dada la dirección de una entrada de la tabla de regiones, devuelve su posición en la tabla (o sea, el número de la región).
  • “pagnum”: Dada la dirección de una entrada de una tabla de páginas, devuelve su posición en la tabla (o sea, el número de la página dentro de la región).
  • “entrada_pagina”: Dado el número de página de una región, devuelve la dirección de la entrada en la tabla de páginas correspondiente.

Aunque queda a discreción del alumno, se recomienda incluir en este módulo funciones que tengan que ver con la gestión de las regiones y páginas del mapa. Así, en la solución que he desarrollado, he incluido funciones tales como una que busca a qué página corresponde una determinada dirección u otra que activa el bit de modificado.

Módulo "fallo"

Este módulo incluye la rutina de tratamiento del “fallo de página” que se encargará de tratar este evento y de actualizar las estadísticas de acuerdo con el mismo. En la versión inicial está prácticamente vacío.

Ejecución del monitor

En esta sección se explica cómo se ejecuta el monitor y se muestra qué salida produce. El monitor recibirá como argumentos el algoritmo de reemplazo que debe utilizar, el número de marcos disponibles (o sea, el tamaño de la memoria física) y el nombre del programa que se pretende ejecutar de forma supervisada, junto con sus argumentos.

La información sobre el algoritmo de reemplazo estará contenida en el propio nombre del programa. Así, aunque sólo habrá un ejecutable, denominado “memon”, existirán enlaces a este ejecutable, de manera que el nombre del enlace haga referencia al algoritmo de reemplazo (“memon_FIFO”, para un algoritmo FIFO, y “memon_reloj”, para el algoritmo del reloj).

Nótese que la versión inicial de la práctica ya realiza todo el procesado de los argumentos que se acaba de describir.

Supóngase, por ejemplo, que se desea monitorizar en un sistema con 8 marcos usando un algoritmo de reemplazo FIFO, el programa “prueba1” que recibe como argumentos dos archivos (“vector_resultado” y “vector_operando”). Suponiendo que tanto al ejecutable como los archivos residen en el directorio “programas”, se ejecutaría el siguiente mandato:

./memon_FIFO 8 programas/prueba1 programas/vector_resultado programas/vector_operando

Si se pretende usar el algoritmo del reloj, habrá que ejecutar lo siguiente:

./memon_reloj 8 programas/prueba1 programas/vector_resultado programas/vector_operando

Con respecto a la salida producida por el monitor, una vez que esté completada la funcionalidad del mismo, ésta será como la siguiente (nótese que los valores impresos no son significativos):

Fallos de página 41
Fallos no forzados 27
Fallos forzados 14
Fallos sin reemplazo 10
Fallos con reemplazo 31
Fallos sin lectura 3
Fallos con lectura archivo 25
Fallos con lectura swap 13
Escrituras en archivo 5
Escrituras en swap 12

Descripción de la funcionalidad pedida y evaluación de la práctica

En este apartado se expone de forma evolutiva qué funcionalidad se pide concretamente en esta práctica, describiendo tres versiones sucesivas del monitor con una complejidad incremental.

Versión inicial: aplicación directa de la idea básica

Esta primera versión va a plasmar las ideas planteadas en las secciones anteriores para construir un monitor que obtenga algunas estadísticas básicas sobre el uso de memoria de un programa, usando un algoritmo de reemplazo sencillo como el FIFO. Esta primera versión del monitor deberá obtener las siguientes estadísticas:

  • Número total de fallos de página causados por el programa.
  • Número de fallos “no forzados” (causados por la falta de memoria física) y “forzados” (no son causados por la falta de memoria física, se deben simplemente al uso de paginación por demanda).
  • Número de fallos que conllevan reemplazo (no se encuentra un marco libre) y número de fallos que no generan reemplazo.

En la versión inicial que se proporciona del módulo “mapa”, ya está implementada la funcionalidad de las rutinas “creacion_region” y “eliminacion_region” que son invocadas por el módulo “apoyo” cuando se produce el evento correspondiente. Estas rutinas invocan a su vez (aunque de forma indirecta) a las rutinas “iniciar_entrada_tpag” y “liberar_entrada_tpag”, que son las encargadas de iniciar cada página de la región que se crea o destruye, respectivamente. Estas rutinas no están implementadas en la versión inicial de este módulo y constituyen el punto por el que se debería iniciar la programación de esta práctica. Asimismo, habrá que programar la función “cambio_tam_region”, que debe redimensionar adecuadamente la tabla de páginas asociada, iniciando o liberando entradas dependiendo de si se trata de un aumento o de una disminución de tamaño, respectivamente.

Para realizar esta primera parte, se deberá incluir en la definición de la entrada de la tabla de páginas aquellos campos requeridos por la funcionalidad reducida de esta primera versión (por ejemplo, la información necesaria para distinguir los fallos forzados y no forzados).

Por último, en el módulo “fallo”, habrá que realizar la primera versión de la rutina de fallo de página que deberá tener la estructura típica de una rutina de este tipo. Por lo que se refiere a las estadísticas, sólo se calcularán los fallos totales, los fallos forzados y no forzados, y los fallos con y sin reemplazo. Además, habrá que detectar los accesos a direcciones de memoria inválidas. En caso de que se produzcan, se sacará un mensaje por la salida de error que contenga el texto ”“acceso a memoria inválido”” y se terminará inmediatamente la ejecución del programa (“_exit(1)”).

Evaluación de la versión inicial

Esta primera parte se calificará con una nota máxima de 4,5 (“error_acceso” 0,5 puntos + “prueba1” 3 puntos + “prueba2” 1 punto).

En primer lugar, se comprobará que el programa detecta adecuadamente los accesos inválidos a memoria usando para ello el programa “error_acceso” (nuevamente, los números no son significativos):

> ./memon_FIFO 8 programas/error_acceso
	acceso a memoria inválido 0x40018000

Nótese que, dado que existe un corrector automático de la práctica, los mensajes generados por la misma deben respetar estrictamente el formato especificado.

A continuación, se probará un programa que realiza distintos tipos de proyecciones de archivos (“prueba1”) (esta prueba no realiza cambios en el tamaño de las regiones):

> ./memon_FIFO 8 programas/prueba1 programas/vector_resultado programas/vector_operando
	Fallos de página 41
	Fallos no forzados 27
	Fallos forzados 14
	Fallos sin reemplazo 10
	Fallos con reemplazo 31
	Fallos sin lectura 0
	Fallos con lectura fichero 0
	Fallos con lectura swap 0
	Escrituras en fichero 0
	Escrituras en swap 0

Evidentemente, en esta salida sólo aparecerá información relevante para aquellas estadísticas que estén ya implementadas. Recuérdese, además, que los valores incluidos en el listado anterior no son significativos.

Hay que tener en cuenta que cada vez que se ejecuta el programa “prueba1”, se modifica el fichero “vector_resultado”. Por tanto, para repetir exactamente la misma prueba, se debe restaurar dicho fichero a partir del original.

Para probar la funcionalidad vinculada con el cambio de tamaño de una región, se usa un segundo programa (“prueba2”), que se ejecuta sin especificar ningún argumento:

> ./memon_FIFO 6 programas/prueba2
	Fallos de página 25
	Fallos no forzados 16
	Fallos forzados 9
	Fallos sin reemplazo 9
	Fallos con reemplazo 16
	Fallos sin lectura 0
	Fallos con lectura fichero 0
	Fallos con lectura swap 0
	Escrituras en fichero 0
	Escrituras en swap 0

Para poder validar el resultado, se puede usar la versión terminada del monitor (“solucion_FIFO”) que se proporciona como material de apoyo y comparar los resultados.

Para facilitar la depuración, el programa (“solucion_FIFO”) tiene un modo de ejecución donde imprime información de cómo va evolucionando la monitorización del programa. Para ello, debe definirse una variable de entorno que se llame “VERBORREA”.

Por último, hay que resaltar que el monitor nos permite apreciar en la práctica la influencia del número de marcos asignados a un proceso (su conjunto residente) con el número de fallos de página. Para ello, es recomendable ejecutar el monitor sobre un programa de prueba variando el número de marcos disponible:

  • Aumentar el número de marcos hasta que desaparezcan los fallos no forzados.
  • Disminuir el número de marcos para comprobar cómo se dispara exponencialmente el número de fallos de página (como nos enseña la teoría, lo que está ocurriendo es que el conjunto de trabajo del proceso no cabe en el conjunto residente). ¿Qué ocurre cuando especificamos un solo marco? Intente analizar lo que está ocurriendo.

Versión intermedia. Control de la modificación de las páginas

Se puede mejorar la funcionalidad del monitor y conseguir estadísticas más detalladas del uso de memoria si logramos llevar la cuenta de cuáles de las páginas residentes han sido modificadas y cuáles no.

Se trata, por tanto, de gestionar una información equivalente a la que proporciona el bit de modificado de una MMU. La estrategia que se va a utilizar no es nueva. Es la misma que se ha usado en sistemas operativos reales cuando la MMU del procesador no incluía un bit de modificado. A continuación, se describe esta estrategia:

  • Cuando en un fallo de página (o sea, en el tratamiento del “SEGV” en el caso de nuestro monitor) se trae una página a memoria (o sea, se habilita su acceso con “mprotect”), se le especifica una protección que corresponde con la de la región pero quitándole el permiso de escritura.
  • Si se produce un fallo y se comprueba que la página ya estaba residente, esto implicaría que se ha intentado escribir sobre ella. Por tanto, se considerará activado el bit de modificado y se establecerá directamente la protección original de la región. Nótese que, antes de activar el bit de modificado y restaurar la protección original, habría que comprobar que realmente la región tiene permiso de escritura, ya que, en caso contrario, se trataría de un acceso inválido (por ejemplo, un programa que escribe sobre su región de código). En caso de que se produzca, se sacará un mensaje por la salida de error y se terminará inmediatamente la ejecución del programa. Un aspecto importante es que el monitor no incluirá en ninguna de sus estadísticas este fallo ya que se trata de un fallo “artificial” usado para la gestión del bit de modificado.

Conviene resaltar que, con la inclusión de este nuevo mecanismo, una única escritura en memoria puede causar 2 fallos. En el primero “se trae la página a memoria”, pero no se habilita permiso de escritura. Al repetirse la misma instrucción (nótese que después de tratar “SEGV” se repite la misma instrucción ya que el contador de programa sigue apuntando a la instrucción que causó el fallo), produce un segundo fallo, que el monitor no incluye en sus estadísticas, activándose el bit de modificado. La gestión de este bit de modificado permite obtener más estadísticas del comportamiento del programa:

  • Número de fallos de página que no implican lectura, número de fallos que producen una lectura de archivo y número de fallos que provocan una lectura del swap.
  • Número de escrituras a archivo y número de escrituras a swap.

Hay que tener en cuenta el comportamiento diferente que tiene una página dependiendo de si pertenece a una región privada o compartida. A continuación, se repasan los aspectos teóricos vinculados con este tema:

  • Si pertenece a una región privada, los fallos de página se sirven del soporte original (ya sea de un fichero o anónima sin soporte) mientras que la página no se modifique. En cuanto se modifique una vez, a partir de ese momento se usará siempre el swap como soporte de la página.
  • Si pertenece a una región compartida, siempre se usa el archivo como soporte.

Para implementar esta funcionalidad, en el módulo de gestión del mapa se deberán incluir campos adicionales en la definición de la entrada de la tabla de páginas (como mínimo el propio bit de modificado) y añadir nuevas funciones si se considera oportuno.

En la rutina de fallo habrá que incluir la lógica de gestión del bit de modificación e implementar las nuevas estadísticas. Para ello, habrá que tener en cuenta si la página pertenece a una región anónima o vinculada a archivo y si es privada o compartida.

Asimismo, habrá que detectar los errores debidos a operaciones de memoria no permitidas. Concretamente, los accesos de escritura a regiones que no lo permiten. En caso de que se produzcan, se sacará un mensaje por la salida de error que contenga el texto ”“escritura en memoria inválida”” y se terminará inmediatamente la ejecución del programa (“_exit(2)”).

Evaluación de la versión intermedia

Esta parte se calificará con una nota máxima de 3,5 (“error_escritura” 0,5 puntos + “prueba1” 2 puntos + “prueba2” 1 punto).

En primer lugar, se comprobará que el programa detecta adecuadamente los errores debidos a operaciones de memoria no permitidas (concretamente, una escritura en la región de código) usando para ello el programa “error_escritura”:

> ./memon_FIFO 8 programas/error_escritura
	escritura en memoria inválida 0x40015830

A continuación, se probará un programa que realiza distintos tipos de proyecciones de archivos (“prueba1”):

> ./memon_FIFO 8 programas/prueba1 programas/vector_resultado programas/vector_operando
	Fallos de página 41
	Fallos no forzados 27
	Fallos forzados 14
	Fallos sin reemplazo 10
	Fallos con reemplazo 31
	Fallos sin lectura 3
	Fallos con lectura fichero 25
	Fallos con lectura swap 13
	Escrituras en fichero 5
	Escrituras en swap 12

En esta ocasión, todas las estadísticas son relevantes, aunque los valores incluidos en el listado no son significativos.

Para probar la funcionalidad vinculada con el cambio de tamaño de una región, se usa un segundo programa (“prueba2”), que se ejecuta sin especificar ningún argumento:

> ./memon_FIFO 6 programas/prueba2
	Fallos de página 25
	Fallos no forzados 16
	Fallos forzados 9
	Fallos sin reemplazo 9
	Fallos con reemplazo 16
	Fallos sin lectura 8
	Fallos con lectura fichero 4
	Fallos con lectura swap 13
	Escrituras en fichero 0
	Escrituras en swap 11

Para poder validar el resultado, se puede usar la versión terminada del monitor (“solucion_FIFO”), que se proporciona como material de apoyo, y comparar los resultados.

Versión final. Algoritmo del reloj

De todos son conocidas las limitaciones del algoritmo FIFO y las buenas prestaciones del algoritmo del reloj, a pesar de su relativa simplicidad. Por tanto, en esta última versión de memon se plantea la inclusión de este nuevo algoritmo de reemplazo. Además de su programación, la implementación de este algoritmo presenta una dificultad adicional: requiere el uso de un bit de referencia.

Hasta ahora no se había planteado este requisito dado que el algoritmo FIFO no usa este bit. Para conseguir implementar este bit de referencia tenemos que recurrir nuevamente a un algoritmo similar al usado para el bit de modificado. Como curiosidad, es interesante resaltar que la MMU del procesador VAX donde se implementó el UNIX BSD original no tenía bit de referencia y, por tanto, se usó una estrategia similar a la descrita a continuación.

  • Cuando se “trae” una página a memoria, se marca como residente y referenciada.
  • Cuando el algoritmo del reloj solicita desactivar el bit de referencia de una página, habrá que deshabilitar el acceso con “mprotect”, pero manteniendo la página como residente.
  • Si llega un fallo y la página está residente y no referenciada, se activa el bit de referencia y se habilita el acceso oportuno. Como ocurría con la implementación del bit de modificado, el monitor no incluirá en ninguna de sus estadísticas este fallo ya que se trata de un fallo “artificial”.

Nótese que esta estrategia tiene que funcionar de manera conjunta con la correspondiente a la gestión del bit de modificado.

La inclusión del algoritmo del reloj implica, en primer lugar, modificar el archivo “marcos.c”, para incluir el algoritmo del reloj, en concreto, la función “reemplazo_reloj”.

Además, en el módulo de gestión del mapa se deberán incluir campos adicionales en la definición de la entrada de la tabla de páginas (como mínimo el propio bit de referencia) y añadir nuevas funciones si se considera oportuno. Asimismo, en la rutina de fallo habrá que incluir la lógica de gestión del bit de referencia.

Evaluación de la versión final

Esta parte se calificará con una nota máxima de 2 puntos (“prueba1” 1 punto + “prueba2” 1 punto).

Para probar la práctica se debe tener en cuenta, en primer lugar, que el nombre de ejecutable que hay que usar es “memon_reloj”. Por lo demás, se usarán los dos programas de prueba de la práctica (“prueba1” y “prueba2”):

> ./memon_reloj 8 programas/prueba1 programas/vector_resultado programas/vector_operando
	Fallos de página 34
	Fallos no forzados 20
	Fallos forzados 14
	Fallos sin reemplazo 10
	Fallos con reemplazo 24
	Fallos sin lectura 3
	Fallos con lectura fichero 23
	Fallos con lectura swap 8
	Escrituras en fichero 4
	Escrituras en swap 8
> ./memon_reloj 6 programas/prueba2
	Fallos de página 23
	Fallos no forzados 14
	Fallos forzados 9
	Fallos sin reemplazo 9
	Fallos con reemplazo 14
	Fallos sin lectura 8
	Fallos con lectura fichero 3
	Fallos con lectura swap 12
	Escrituras en fichero 0
	Escrituras en swap 11

Para poder validar el resultado, se puede usar la versión terminada del monitor (“solucion_reloj”) y comparar los resultados.

Código de apoyo

El material de apoyo está contenido en el fichero ”memon.tgz”. Al extraer su contenido desde el directorio “home” de la cuenta del alumno, se crea el directorio donde se debe desarrollar la práctica. Dentro de este directorio se habrán incluido los siguientes ficheros:

  • “Makefile”. Makefile del monitor. Genera un ejecutable denominado “memon”.
  • “memon.c”. Fichero principal del monitor. Ya contiene la funcionalidad requerida. Este fichero no debe ser modificado.
  • “apoyo.o”. Fichero objeto que contiene las funciones de apoyo.
  • “apoyo.h”. Fichero que contiene los prototipos de las funciones de apoyo, así como unas macros de utilidad. No debe ser modificado.
  • “marcos.h”. Fichero que contiene los prototipos del módulo de gestión de marcos. No debe ser modificado.
  • “marcos.c”. Fichero que contiene el módulo de gestión de marcos. Debe ser modificado, pero sólo para incluir el algoritmo del reloj.
  • “mapa.h”. Fichero que contiene los prototipos del módulo de gestión del mapa, así como las definiciones vinculadas con las tablas de regiones y páginas. Debe ser modificado para completar la definición de la entrada de la tabla de páginas. Además, se puede modificar para incluir funciones adicionales.
  • “mapa.c”. Fichero que contiene el módulo de gestión del mapa del proceso. Se debe modificar para incluir la funcionalidad pedida.
  • “fallo.c”. Fichero que contiene la rutina que trata el fallo de página. Se debe modificar para incluir la funcionalidad pedida.
  • “memon_FIFO”. Enlace al ejecutable “memon”. Será el nombre usado para ejecutar el monitor cuando se desea aplicar el algoritmo FIFO.
  • “memon_reloj”. Enlace al ejecutable “memon”. Será el nombre usado para ejecutar el monitor cuando se desea aplicar el algoritmo del reloj.
  • “solucion_FIFO”. Ejecutable que invoca una versión terminada del monitor, especificando que se aplique el algoritmo FIFO.
  • “solucion_reloj”. Ejecutable que invoca una versión terminada del monitor, especificando que se aplique el algoritmo del reloj.
  • “programas”. Directorio que contiene un conjunto de programas de prueba:
    • “Makefile”. Makefile de los programas de prueba.
    • “memon.h”. Fichero de cabecera usado por los programas de prueba.
    • “error_acceso.c”. Programa que prueba si el monitor detecta los accesos a direcciones de memoria inválidas.
    • “error_escritura.c”. Programa que prueba si el monitor detecta los errores debidos a operaciones de memoria no permitidas.
    • “prueba1.c”. Programa de prueba del monitor que recibe como argumentos dos ficheros. Como resultado de la ejecución, el primer fichero queda modificado pero no el segundo.
    • “prueba2.c”. Programa de prueba del monitor que realiza operaciones en el heap que provocan el cambio de tamaño de la región.
    • “vector_resultado”. Fichero especificado como primer argumento de “prueba1.c” en la evaluación de la práctica. Después de la ejecución quedará modificado.
    • “vector_resultado.orig”. Fichero que contiene una copia del contenido original de “vector_resultado”. Permite restaurar el fichero después de hacer una prueba.
    • “vector_operando”. Fichero especificado como segundo argumento de “prueba1.c” en la evaluación de la práctica. Después de la ejecución no se modifica.

Documentación que se debe entregar

El mandato a ejecutar es:

entrega.dso4 memon.201X

Este mandato realizará la recolección de los siguientes ficheros:

  • “autores” Fichero con los datos de los autores:
DNI APELLIDOS NOMBRE MATRÍCULA
  • “memoria.txt” Memoria de la práctica. En ella se deben comentar los aspectos del desarrollo de su práctica que considere más relevantes. Asimismo, puede exponer los comentarios personales que considere oportuno.
  • “mapa.h”. Cabecera del módulo de gestión del mapa.
  • “mapa.c”. Módulo de gestión del mapa.
  • “fallo.c”. Módulo que gestiona un fallo.
  • “marcos.c”. Módulo de gestión de marcos.
 
docencia/asignaturas/dso/practicas/memom.txt · Última modificación: 2013/10/18 17:16 por fperez
 
Recent changes RSS feed Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki