PRÁCTICAS DE LABORATORIO DE SISTEMAS OPERATIVOS

SEGUNDA PRÁCTICA EVALUABLE (2006-07)

Locomotion

  1. Enunciado.

    Sirva esta práctica como pequeño homenaje a un juego ya clásico, Transport Tycoon (Deluxe) de Chris Sawyer y su sucesor, Locomotion que tan buenos ratos nos ha hecho pasar. Vamos a simular y controlar la circulación de unos trenes por un circuito cerrado. Cada tren será controlado por un proceso UNIX y se usarán mecanismos IPC para coordinarlos. Aunque la práctica requiere de la creación de un buzón de paso de mensajes y de un conjunto de semáforos, podréis usar también una zona de memoria compartida si lo deseáis.

    Los principales problemas que pueden encontrarse una vez se maneja la biblioteca bien, son los accidentes y los interbloqueos. Ocurre un accidente cuando un tren pasa a ocupar una posición ya ocupada por otro (incluso él mismo). Ocurre un interbloqueo cuando varios trenes no pueden evolucionar porque, circularmente, se están impidiendo el paso los unos a los otros. Para que la práctica esté aprobada, es necesario que no se produzcan accidentes con vuestro diseño (ni en la teoría, ni en la práctica). Se valorará bastante, no obstante, si se implementa cualquier mecanismo para que no se produzcan interbloqueos. Esto es más complicado y sólo se debe intentar si disponéis de tiempo para ello.



    El programa constará de un único fichero fuente, lomo.c, cuya adecuada compilación producirá el ejecutable lomo. Respetad las mayúsculas/minúsculas de los nombres.

    Para simplificar la realización de la práctica, se os proporciona una biblioteca estática de funciones (liblomo.a) que debéis enlazar con vuestro módulo objeto para generar el ejecutable. Gracias a ella, algunas de las funciones necesarias para realizar la práctica no las tendréis que programar sino que bastará nada más con incluir la biblioteca cuando compiléis el programa. La línea de compilación del programa podría ser: 
    c89 lomo.c liblomo.a -o lomo
    Disponéis, además, de un fichero de cabeceras, lomo.h, donde se encuentran definidas, entre otras cosas, las macros que usa la biblioteca y las cabeceras de las funciones que ofrece.

    El proceso inicial se encargará de preparar todas las variables y recursos IPC de la aplicación y registrar manejadoras para las señales que necesite. Este proceso, además, debe tomar e interpretar los argumentos de la línea de órdenes y llamar a la función LOMO_inicio con los parámetros adecuados. El proceso será responsable de crear los trenes que van a circular por el circuito (un proceso hijo por cada tren) y de controlar que, si se pulsa CTRL+C la práctica acaba, no dejando procesos en ejecución ni recursos IPCs sin borrar. La práctica devolverá 0 al sistema operativo si todo fue bien, 1 si se produjo cualquier error y 2 si hubo cualquier accidente durante su ejecución.

    La práctica se invocará especificando dos parámetros exactamente desde la línea de órdenes. El primer parámetro será un valor entero mayor o igual que cero. Si es 1 o mayor, la práctica funcionará tanto más lenta cuanto mayor sea el parámetro y no deberá consumir CPU apreciablemente. Si es 0, irá a la máxima velocidad, aunque el consumo de CPU sí será mayor. Por esta razón y para no penalizar en exceso la máquina compartida, no debéis dejar excesivo tiempo ejecutando en el servidor la práctica a máxima velocidad. El segundo parámetro será el número de trenes que van a circular en esta ejecución, un número estrictamente mayor que cero y menor que 100.

    El programa debe estar preparado para que, si el usuario pulsa las teclas CTRL-C desde el terminal, la ejecución del programa termine en ese momento y adecuadamente. Ni en una terminación como esta, ni en una normal, deben quedar procesos en ejecución ni mecanismos IPC sin haber sido borrados del sistema. Este es un aspecto muy importante y se penalizará bastante si la práctica no lo cumple.

    Es probable que necesitéis semáforos para sincronizar adecuadamente la práctica. Se declarará una array de semáforos de tamaño adecuado a vuestros requerimientos, el primero de los cuales se reservará para el funcionamiento interno de la biblioteca. El resto, podéis usarlos libremente.

    Una posición en las vías del tren viene especificada por un par de coordenadas (x,y). Las coordenadas de los puntos singulares (origen, curvas y cruces) del trazado se puede ver en la siguiente figura, junto con las direcciones de circulación de cada tramo:


    Las funciones proporcionadas por la biblioteca liblomo.a son las que a continuación aparecen. De no indicarse nada, las funciones devuelven -1 en caso de error:

    Estad atentos pues pueden ir saliendo versiones nuevas de la biblioteca para corregir errores o dotarla de nuevas funciones.

    La comunicación de los procesos de los trenes con la biblioteca se realiza mediante paso de mensajes. El formato de los mensajes es el de la estructura struct mensaje que aparece en lomo.h. Nada más nacer el proceso, enviará un mensaje al buzón de tipo TIPO_TRENNUEVO. La biblioteca responderá con un mensaje de tipo TIPO_RESPTRENNUEVO. En el campo tren de la estructura, la biblioteca mandará el identificador del tren nuevo (un número entero mayor o igual que cero). Este número se deberá indicar en cualquier mensaje posterior que se envíe a la biblioteca. La longitud del tren creado estará comprendida entre 3 y 19 caracteres.

    El proceso que se debe seguir para que un tren avance consiste en:
    1. El tren debe enviar a la biblioteca un mensaje de tipo TIPO_PETAVANCE. En el campo tren de la estructura debe ir su identificador.
    2. La biblioteca le responderá con un mensaje de tipo TIPO_RESPPETAVANCETREN0+id, siendo id el identificador del tren. La biblioteca devolverá en el campo tren el identificador del tren y en los campos x e y, las coordenadas a las que accederá la cabeza del tren en cuando se dé la orden de ejecutar el avance.
    3. El proceso debe verificar que la posición a la que se va a acceder es segura o, en caso de no serlo, esperarse sin consumo de CPU a que lo sea.
    4. Una vez haya decidido avanzar, el tren envía a la biblioteca un mensaje de tipo TIPO_AVANCE con su identificador.
    5. La biblioteca le responderá con un mensaje de tipo TIPO_RESPAVANCETREN0+id, de modo similar al indicado tres puntos más arriba. Una vez recibido el mensaje, podemos considerar que el avance se ha producido correctamente. Al avanzar el tren, la cola del tren puede que libere una posición (esto ocurrirá siempre, salvo al principio, cuando nace el tren). Las coordenadas de la posición liberada vendrán en los campos x e y del mensaje. Este es un dato fundamental para diseñar un esquema en que los trenes no se choquen. Si no se libera ninguna posición, se devuelve -1 en x e y.
    6. Antes de continuar con el siguiente avance y repetir los pasos anteriores, el proceso responsable del tren debe llamar a la función LOMO_espera indicando cuál es la coordenada y anterior y actual después de realizado el avance.


    La biblioteca crea un proceso internamente que es el que se encarga de atender la cola de mensajes y realizar toda la simulación. Al llamar a la función LOMO_fin, se envía la señal SIGINT al proceso hijo y éste, en una manejadora, envía mensajes con el identificador de tren igual a -1 al buzón. Esto le puede servir a los procesos que estén esperando por un mensaje, recibir este y acabar de un modo razonable.

    Respecto a la sincronización interna de la biblioteca, se usa el semáforo reservado para conseguir atomicidad en la actualización de la pantalla. Para que las sincronizaciones que de seguro deberéis hacer en vuestro código estén en sintonía con las de la biblioteca, os ofrezco ahora un seudocódigo de algunas de las funciones que realiza la biblioteca y están reguladas por el semáforo. S es es semáforo interno que se utiliza y la biblioteca lo inicia a uno. 
        * LOMO_inicio:
         - limpia la pantalla
         - S=1
         - mensaje de bienvenida
         - creación del hijo
         - W(S)
         - dibujar el circuito
         - S(S)

    * petición de avance y avance:
         - comprobación de condiciones y actualización de variables
         - W(S)
         - refresco de la pantalla
         - S(S)

    * LOMO_espera y LOMO_fin:
         - No manejan el semáforo

    * pon_error:
         - W(S)
         - imprimir el error
         - esperar a la pulsación de la tecla
         - S(S)
    En esta práctica no se podrán usar ficheros para nada, salvo que se indique expresamente. Las comunicaciones de PIDs o similares entre procesos, si hicieran falta, se harán mediante mecanismos IPC.

    Siempre que en el enunciado o LPEs se diga que se puede usar sleep(), se refiere a la llamada al sistema, no a la orden de la línea de órdenes.

    Los mecanismos IPC (semáforos, memoria compartida y paso de mensajes) son recursos muy limitados. Es por ello, que vuestra práctica sólo podrá usar un conjunto de semáforos, un buzón de paso de mensajes y una zona de memoria compartida como máximo. Además, si se produce cualquier error o se finaliza normalmente, los recursos creados han de ser eliminados. Una manera fácil de lograrlo es registrar la señal SIGINT para que lo haga y mandársela uno mismo si se produce un error.

    Biblioteca de funciones liblomo.a

    Con esta práctica se trata de que aprendáis a sincronizar y comunicar procesos en UNIX. Su objetivo no es la programación, aunque es inevitable que tengáis que programar. Es por ello que se os suministra una biblioteca estática de funciones ya programadas para tratar de que no debáis 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 propia biblioteca liblomo.a y el fichero de cabecera lomo.h. La biblioteca funciona con los códigos de VT100/xterm, por lo que debéis adecuar vuestros simuladores a este terminal.
    Ficheros necesarios:


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

    Aunque ya deberíais ser capaces de abordar la práctica sin ayuda, aquí van unas guías generales:
    1. Crear los semáforos y el buzón, y comprobad que se crean bien, con ipcs. Es preferible, para que no haya interferencias, que los defináis privados.
    2. Registrar SIGINT para que cuando se pulse ^C se eliminen los recursos IPC. Lograr que si el programa acaba normalmente o se produce cualquier error, también se eliminen los recursos (mandad una señal SIGINT en esos casos al proceso padre).
    3. Llamar a la función LOMO_inicio en main. Debe aparecer la pantalla de bienvenida y, pasados dos segundos, dibujarse la pantalla.
    4. Probad a mandar el mensaje de creación de un tren y ver que efectivamente, recibís un mensaje de respuesta con el identificador del tren nuevo: 0.
    5. Haced que este tren se mueva por el circuito mandando un mensaje de petición de avance y, recibida la respuesta, otro de avance. Dormid durante un segundo y repetid el procedimiento.
    6. Sustituid el sleep por una llamada a LOMO_espera y tened en cuenta el valor que se pasa para el retardo, si es que todavía no lo habéis hecho.
    7. Tened un hijo para que maneje otro tren. Observad que se chocan y se produce un accidente.
    8. Reconvetid el código para que se creen tantos hijos como se indiquen en la línea de órdenes. Podéis hacer que cada uno de ellos comience a avanzar diez segundos después del anterior, para que no se choquen al inicio.
    9. Lograd que, saliendo a la vez, no se choquen, mediante un semáforo.
    10. La parte fundamental de la práctica consiste en pararse ahora y diseñar un sistema que haga que los trenes no tengan accidentes.
    11. Acabad la práctica y probadla a velocidad normal y a velocidad cero. Es seguro que, a velocidad cero, pueden salir a relucir problemas ocultos a velocidades menores.
    12. Diseñad la forma de acabar sin problemas y llamad a la función LOMO_fin.
    13. Pulid los últimos detalles.


  3. Plazo de presentación.

    Hasta el miércoles, 2 de mayo de 2007, inclusive.

  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 semáforos usados, sus valores iniciales y un seudocódigo sencillo para cada proceso con las operaciones wait y signal realizadas sobre ellos. Por ejemplo, si se tratara de sincronizar dos procesos C y V para que produjeran alternativamente consonantes y vocales, comenzando por una consonante, deberíais entregar algo parecido a esto: 
         SEMÁFOROS Y VALOR INICIAL: SC=1, SV=0.

     SEUDOCÓDIGO:

             C                                V
            ===                              ===
       Por_siempre_jamás               Por _siempre_jamás
          {                               {
           W(SC)                           W(SV)
           escribir_consonante             escribir_vocal
           S(SV)                           S(SC)
           }                               }


  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, la corrección en el tratamiento de errores, la cantidad y calidad del trabajo realizado, etc.

    En esta práctica se puede obtener la máxima puntuación sin realizar un esfuerzo para que no se produzcan interbloqueos. No obstante lo dicho y dada la dificultad, se valorará muy positivamente los esfuerzos productivos por conseguir la ausencia de interbloqueos.

  6. LPEs.

    1. ¿Dónde poner un semáforo? Dondequiera que uséis la frase, "el proceso puede llegar a esperar hasta que..." es un buen candidato a que aparezca una operación wait sobre un semáforo. Tenéis que plantearos a continuación qué proceso hará signal sobre ese presunto semáforo y cuál será su valor inicial.
    2. Si ejecutáis la práctica en segundo plano (con ampersand (&)) es normal que al pulsar CTRL+C el programa no reaccione. El terminal sólo manda SIGINT a los procesos que estén en primer plano. Para probarlo, mandad el proceso a primer plano con fg % y pulsad entonces CTRL+C.
    3. Un "truco" para que sea menos penoso el tratamiento de errores consiste en dar valor inicial a los identificadores de los recursos IPC igual a -1. Por ejemplo, int semAforo=-1. En la manejadora de SIGINT, sólo si semAforo vale distinto de -1, elimináis el recurso con semctl. Esto es lógico: si vale -1 es porque no se ha creado todavía o porque al intentar crearlo la llamada al sistema devolvió error. En ambos casos, no hay que eliminar el recurso.
    4. Para evitar que todos los identificadores de recursos tengan que ser variables globales para que los vea la manejadora de SIGINT, podéis declarar una estructura que los contenga a todos y así sólo gastáis un identificador del espacio de nombres globales.
    5. A muchos os da el error "Interrupted System Call". Mirad la sesión quinta, apartado quinto. Allí se explica lo que pasa con wait. A vosotros os pasa con semop, pero es lo mismo. De las dos soluciones que propone el apartado, debéis usar la segunda.
    6. A muchos, la práctica os funciona exasperantemente lenta en encina. Debéis considerar que la máquina cuando la probáis está cargada, por lo que debe ir más lento que en casa o en el linux de clase.
    7. A aquellos que os dé "Bus error (Core dumped)" al dar valor inicial al semáforo, considerad que hay que usar la versión de semctl de Solaris (con union semun), como se explica en la sesión de semáforos y no la de HPUX.
    8. Al acabar la práctica, con CTRL+C, al ir a borrar los recursos IPC, puede ser que os ponga "Invalid argument", pero, sin embargo, se borren bien. La razón de esto es que habéis registrado la manejadora de SIGINT para todos los procesos. Al pulsar CTRL+C, la señal la reciben todos, el padre y los otros procesos. El primero que obtiene la CPU salta a su manejadora y borra los recursos. Cuando saltan los demás, intentan borrarlos, pero como ya están borrados, os da el error.
    9. Hay dos problemas que, aunque no se indique en el enunciado, necesitan sincronización. La salida inicial de los trenes, por ejemplo. Puede haber más.
    10. El compilador de encina tiene un bug. El error típicamente os va a ocurrir cuando defináis una variable entera en memoria compartida. Os va a dar Bus Error. Core dumped si no definís el puntero a esa variable apuntando a una dirección que sea múltiplo de cuatro. El puntero que os devuelve shmat, no obstante, siempre será una dirección múltiplo de cuatro, por lo que solo os tenéis que preocupar con que la dirección sea múltiplo de cuatro respecto al origen de la memoria compartida. La razón se escapa un poco al nivel de este curso y tiene que ver con el alineamiento de direcciones de memoria en las instrucciones de acceso de palabras en el procesador RISC de encina.
    11. Os recuerdo que, si ponéis señales para sincronizar esta práctica, la nota bajará. Usad semáforos que son mejores para este cometido.
    12. Todos vosotros, tarde o temprano, os encontráis con un error que no tiene explicación: un proceso que desaparece, un semáforo que parece no funcionar, etc. La actitud en este caso no es tratar de justificar la imposibilidad del error. Así no lo encontraréis. Tenéis que ser muy sistemáticos. Hay un árbol entero de posibilidades de error y no tenéis que descartar ninguna de antemano, sino ir podando ese árbol. Tenéis que encontrar a los procesos responsables y tratar de localizar la línea donde se produce el error. Si el error es "Segmentation fault. Core dumped", la línea os la dará si aplicáis lo que aparece en la sección Manejo del depurador. En cualquier otro caso, no os quedará más remedio que depurar mediante órdenes de impresión dentro del código.

      Para ello, insertad líneas del tipo:
                           fprintf(stderr,"...",...);
      donde sospechéis que hay problemas. En esas líneas identificad siempre al proceso que imprime el mensaje. Comprobad todas las hipótesis, hasta las más evidentes. Cuando ejecutéis la práctica, redirigid el canal de errores a un fichero con 2>salida.

      Si cada proceso pone un identificador de tipo "P1", "P2", etc. en sus mensajes, podéis quedaros con las líneas que contienen esos caracteres con:
                           grep "P1" salida > salida2


  7. Prácticas propuestas años anteriores.

© 2007 Guillermo González Talaván y Ana Belén Gil González.