PRÁCTICAS DE LABORATORIO DE SISTEMAS OPERATIVOS

TERCERA PRÁCTICA OBLIGATORIA (2003-04)

Aparcando

  1. Enunciado.

    El programa propuesto constará de un único fichero fuente, parking.cpp, cuya adecuada compilación producirá el ejecutable parking. Se trata de simular mediante un programa que realice llamadas a la API de WIN32 la gestión de memoria de un sistema operativo que use particiones de tamaño dinámico. Para ello, se establece el símil con el problema de elegir el mejor aparcamiento para un coche de todos los posibles en una acera. Según se va ejecutando el programa, se ha de ver una imagen parecida a la siguiente:



    En la imagen puede observarse de color marrón lo que simulan ser cuatro aceras. El algoritmo que se usa para aparcar los coches en cada una corresponde, de arriba a abajo, al primer ajuste, siguiente ajuste, mejor ajuste y peor ajuste, tal y como se vio en la primera parte de la asignatura. Cada acera consta de ochenta caracteres (0-79) y los coches tienen longitud entera, medida en caracteres.

    Quizá de los cuatro algoritmos el que mayor dificultad presente sea el del siguiente ajuste. Cuando un coche llega a aparcar, de todos los huecos en los que cabe el coche, se elige el primero que aparece a partir de la posición en la que aparcó el último coche. Si se llega al final de la acera, se vuelve a empezar por el principio. El algoritmo no presenta mayor problema salvo cuando el último coche que aparcó ya se ha ido. En ese caso, si el extremo izquierdo que ocupó ese último coche pertenece actualmente a un hueco, dicho hueco será elegido sólo en el caso de que no haya otro disponible. Si dicho extremo corresponde con un coche aparcado, se empezará a considerar huecos a partir del final de ese coche.

    En el caso de los algoritmos del mejor ajuste y del peor ajuste, si hay empate entre dos o más huecos, se elegirá entre ellos siguiendo el criterio del primer ajuste.

    Una vez elegido un hueco con espacio suficiente para aparcar el coche, se aparcará ajustando el coche a la izquierda del hueco en cualquiera de los algoritmos.

    Si cuando llega un coche, no existe un hueco de tamaño suficiente para que aparque, el coche se pondrá en una cola a la espera de que otro coche salga del aparcamiento. Esta cola seguirá una disciplina FIFO.

    La simulación durará 30 segundos, terminados los cuales el programa presentará una serie de estadísticas resultantes de la simulación para cada uno de los algoritmos. Las estadísticas se referirán sólo a los coches totalmente atendidos (aquellos que han aparcado y ya han consumido su tiempo de espera aparcando y están dispuestos para salir). En concreto, se pedirá:
    1. Media de la longitud de los coches
    2. Media del tiempo de servicio requerido (tiempo que cada coche desea permanecer aparcado)
    3. Media de los intervalos de tiempo que han transcurrido entre la llegada de dos coches consecutivos
    4. Número total de coches atendidos
    5. Media del tiempo de espera antes de conseguir aparcar
    6. Media del tiempo de retorno normalizado
    7. Media del tamaño de la cola de espera
    8. Porcentaje de ocupación medio de la memoria
    Para que en las estadísticas de cada algoritmo no influya la suerte, en cada ejecución concreta llegarán los mismos coches, con idéntico tiempo de servicio e intervalo de llegada entre ellos a cada una de las cuatro aceras. Para el tiempo de servicio y el intervalo de llegada entre coches, se usará una distribución exponencial. Para la longitud de los coches, la distribución será uniforme, con una longitud mínima de cuatro caracteres.

    Parking acepta un máximo de dos argumentos por la línea de órdenes. Si no se introducen argumentos, se imprimirá un mensaje con la forma de uso del programa por el canal de error estándar. En el caso de teclear un argumento, dicho argumento será un número entero mayor o igual que cero relacionado con la rapidez con que se producen los acontecimientos en el programa. Cero indica la máxima rapidez y números mayores suponen una rapidez progresivamente menor. Finalmente, si son dos los parámetros introducidos, el primero es idéntico al caso anterior y el segundo será una "D", indicando que se desea que el programa produzca información de depuración por el canal de errores estándar.

    Para facilitar la tarea, tenéis a vuestra disposición una biblioteca de funciones de enlazado dinámico parking.dll y un fichero de cabeceras, parking.h. Gracias a la biblioteca, muchas de las funciones no las tendréis que programar sino que invocarlas a la DLL, tal como se explica en la sesión decimoquinta. La biblioteca creará dos hilos adicionales a los vuestros para su funcionamiento interno, de los cuales no tendréis que ocuparos. Una descripción detallada de las funciones de la biblioteca aparece más abajo en esta misma página.

    El programa, desde vuestro punto de vista, se simplifica bastante. Se ha de llamar a la función inicio de la DLL. El hilo dormirá 30 segundos e invocará a la función fin, para acabar con la simulación. Cuando la función fin retorne, se llamará a la función poner_estadIsticas (nótese la I mayúscula) para que se contrasten las estadísticas que habéis tomado con las calculadas por la DLL. Ahí acabará el programa. Además, se programarán cuatro funciones que serán llamadas por la DLL cada vez que un coche llegue y cuatro funciones a las que la DLL llamará cuando un coche tenga que marcharse. Dichas funciones de rellamada son registradas en la función inicio de la DLL.

    Los prototipos de las dos tipo de funciones de rellamada, se describen aquí:

    Características adicionales que programar



    Biblioteca parking.dll

    Con estra práctica se trata de que aprendáis a sincronizar y comunicar hilos en WIN32. Su objetivo no es la programación. Es por ello que se os suministra una biblioteca dinámica de funciones ya programadas para tratar de que no tengáis que preocuparos por la presentación por pantalla, la gestión de estructuras de datos (colas, pilas, ...) , etc. También servirá para que se detecten de un modo automático errores que se produzcan en vuestro código. Para que vuestro programa funcione, necesitáis la biblioteca parking.dll y el fichero de cabeceras parking.h.
    Ficheros necesarios:


    Las funciones que la biblioteca exporta para que las uséis son:

    Sincronización interna de la DLL

    La sincronización interna de la DLL está basada en un mutex. El esquema de sincronización interna es el siguiente: 
        Mutex Mu;
    Mu=1;
    [...]
    Llegada de un coche:
    ===================
    Wait(Mu);
    Calcular la posición buena;
    Imprimir información de depuración;
    Llamada función rellamada usuario;
    Comprobación de errores;
    Marcar la zona de la acera como reservada;
    ReleaseMutex(Mu);

    Salida de un coche:
    ==================
    Poner el coche más oscuro;
    Wait(Mu);
    Imprimir información de depuración;
    Llamada función rellamada usuario;
    Calcular estadísticas;
    ReleaseMutex(Mu);

    Función aparcar:
    ===============
    Llevar el coche justo sobre la línea de donde tiene que aparcar
        a falta de su último movimiento;
    Wait(Mu);
    Realizar el último movimiento;
    Marcar como ocupada esa parte de la acera;
    ReleaseMutex(Mu);
    
    Función desaparcar:
    ==================
    Comprobación de rango y existencia de coche;
    Wait(Mu);
    Sacar el coche del aparcamiento y poner sobre la línea;
    Liberar esa parte de la acera;
    ReleaseMutex(Mu);
    Completar la salida del coche;

  2. Pasos recomendados para la realización de la práctica

    En esta tercera práctica, no os indicaré los pasos que podéis seguir. El proceso de aprendizaje es duro, y ya llega el momento en que debéis andar vuestros propios pasos sin ayuda, aunque exista la posibilidad de caerse al principio.

  3. Plazo de presentación.

    Hasta el 17 de junio de 2004, inclusive e improrrogable.

  4. Normas de presentación.

    Acá están. Además de estas normas, en esta práctica se debe entregar un esquema donde aparezcan los mecanismos de sincronización usados, sus valores iniciales y un seudocódigo sencillo para cada hilo con las operaciones realizadas sobre ellos. Por ejemplo, si se tratara de sincronizar con eventos dos hilos C y V para que produjeran alternativamente consonantes y vocales, comenzando por una consonante, deberíais entregar algo parecido a esto: 
         EVENTOS Y VALOR INICIAL: EC* (automático), EV (automático).

     SEUDOCÓDIGO:

             C                                V
            ===                              ===
       Por_siempre_jamás               Por _siempre_jamás
          {                               {
           W(EC)                           W(EV)
           escribir_consonante             escribir_vocal
           Set(EV)                         Set(EC)
           }                               }
    Debéis indicar, asimismo, en el caso de que las hayáis realizado, las optimizaciones de código realizadas.

  5. Evaluación de la práctica.

    Dada la dificultad para la corrección de programación en paralelo, el criterio que se seguirá para la evaluación de la práctica será: si
    1. la práctica cumple las especificaciones de este enunciado y,
    2. la práctica no falla en ninguna de las ejecuciones a las que se somete y,
    3. no se descubre en la práctica ningún fallo de construcción que pudiera hacerla fallar, por muy remota que sea esa posibilidad...
    se aplicará el principio de "presunción de inocencia" y la práctica estará aprobada. La nota, a partir de ahí, dependerá de la simplicidad de las técnicas de sincronización usadas, de las optimizaciones realizadas para producir más aparcamientos, etc.

  6. LPEs.

    1. No debéis usar la función TerminateThread para acabar con los hilos. El problema de esta función es que está diseñada para ser usada sólo en condiciones excepcionales y el hilo muere abruptamente. Puede dejar estructuras colgando e ir llenando la memoria virtual del proceso con basura.
    2. Cuando ejecuto la práctica depurando me aparece Se ha producido un choque.... Cuando examino la casilla, compruebo que todo es correcto. ¿A qué puede ser debido?

      Este mensaje u otros similares que parecen estar equivocados tienen su razón en que estáis "manchando" la pantalla con mensajes propios o de depuración. Para evitar este tipo de mensajes, mejor depurad la práctica enviando la información de trazado a un fichero añadiendo al final de la línea de órdenes 2>salida. De este modo, toda la información aparecerá en el fichero salida.
    3. Tengo muchos problemas a la hora de llamar a la función inicio de la biblioteca. No consigo de ningún modo acceder a ella.

      El proceso detallado viene en la última sesión. De todos modos, soléis tener problemas en una conversión de tipos, aunque no os deis cuenta de ello. No voy a deciros qué es lo que tenéis que poner para que funcione, pues lo pondríais y no aprenderíais nada. Sin embargo y dada la cantidad de personas con problemas, aquí viene una pequeña guía:
      1. Primero debéis definir una variable puntero a función. El nombre de la variable es irrelevante, pero podemos llamarle inicio por lo que veremos más abajo. Para definir el tipo de esta variable correctamente, debéis conocer cómo son los punteros a función. En la sesión quinta, se describe una función, atexit. Dicha función en sí no es importante para lo que nos traemos entre manos, pero sí el argumento que tiene. Ese argumento es un puntero a función. Fijándoos en ese argumento, no os resultará difícil generalizarlo para poner un puntero a funciones que admiten un (TIPO_FUNCION_LLEGADA *, TIPO_FUNCION_SALIDA *, LONG,BOOL) y devuelven un BOOL. Notad, además, que, al contrario que ocurre con las variables "normales", la definición de una variable puntero a función es especial por cuanto su definición no va sólo antes del nombre de la variable, sino que lo rodea. Tenéis que poner algo similar a: #$%&%$ inicio $%&$·@;, es decir, algo por delante y algo por detrás.
      2. Después de cargar la biblioteca como dice en la última sesión, debéis dar valor al puntero de función. Dicho valor lo va a proporcionar GetProcAddress. Pero, ¡cuidado!, GetProcAddress devuelve un FARPROC, que sólo funciona con punteros a funciones que devuelven int y no se les pasa nada (void). Debéis hacer el correspondiente casting. Para ello, de la definición de vuestro puntero, quitáis el nombre, lo ponéis todo entre paréntesis y lo añadís delante de GetProcAddress, como siempre.
      3. Ya podéis llamar a la función como si de una función normal se tratara. Ponéis el nombre del puntero y los argumentos entre paréntesis. Como os advertí más arriba, si habéis puesto inicio como nombre al puntero, ahora no se diferenciarán en nada vuestras llamadas a la función respecto a si dicha función no perteneciera a una DLL y la hubierais programado vosotros.
    4. Os puede dar errores en el fichero de cabecera parking.h si llamáis a vuestro fichero fuente parking.c. Llamadlo parking.cpp.
    5. Algunos os sorprendéis porque la simulación parece que aparca los coches donde quiere y la DLL no dice ni mu. Es normal. Tened en cuenta que aunque vosotros veáis un hueco libre donde debiera ir un coche, puede que ese hueco ya esté reservado por otro coche que esté a la espera del semáforo para poder aparcar. En general, si la DLL no protesta, no os preocupéis.


  7. Prácticas propuestas años anteriores.

© 2004 Guillermo González Talaván.