PRÁCTICAS DE LABORATORIO DE SISTEMAS OPERATIVOS

SEGUNDA PRÁCTICA OBLIGATORIA (2003-04)

The Lord of the Rings II: The two towers


  1. Enunciado.

    En esta práctica vamos a realizar fundamentalmente lo mismo que en la primera práctica obligatoria, salvo lo que se indique a continuación.

    Desaparecen los personajes de Elrond, Celebrian y Arwen. En su lugar, aparecen Gandalf y Saruman. El programa constará de un único fichero fuente, Tolkien2.c, cuya adecuada compilación producirá el ejecutable Tolkien2. Respetad las mayúsculas/minúsculas de los nombres.

    La vida de cada personaje, se describe a continuación:



    El mecanismo de procreación de los hobbits ha evolucionado con el paso de los años. Ya no consumen CPU, aunque en lo esencial todo sigue igual. Para hacer esperas sin consumir CPU usan semáforos. El procedimiento es el siguiente:
    1. La parte masculina espera hasta que la parte femenina muestre su disponibilidad para la procreación.
    2. Una vez la parte femenina lo considere oportuno, le indicará a la parte masculina su deseo de procrear y se esperará sin consumo de CPU a que le responda su compañero.
    3. La parte femenina repite el proceso durante tantos segundos como se haya indicado en el parámetro de Tolkien2.
    4. Una vez satisfecha, y como no necesita más de la parte masculina, le envía la señal SIGTERM. Su pareja muere, por consiguiente.
    5. La parte femenina, finalmente, tiene un proceso hijo.

    La lucha entre los dos magos seguirá las siguientes reglas:
    1. El campo de batalla es una zona de memoria compartida donde se aloja una variable energia de tipo long long.
    2. La variable energia comenzará con el valor de 200000.
    3. Gandalf, cuando tenga la CPU, incrementará la variable energia en pasos de dos en dos.
    4. Por su parte, Saruman, en posesión de la CPU, decrementará la variable energia de uno en uno.
    5. Cuando la variable supere o sea igual a 600000, Gandalf ganará.
    6. Si la variable toma valor negativo, es Saruman el vencedor.
    7. Mientras dure la lucha, se producirá una salida a tiempo real por la pantalla:
      • Se usarán los códigos del terminal VT100 que se han proporcionado en el resumen de las llamadas al sistema.
      • Al principio, se limpiará la pantalla.
      • En la séptima línea, empezando a contar por la parte superior de la pantalla, se escribirá SARUMAN, 62 espacios en blanco para el campo de batalla y GANDALF.
      • Mientras dure la batalla, se posicionará el cursor en los 62 espacios en blanco, según vaya progresando la lucha. Esto es, cuando la variable energia valga 0, el cursor se posicionará sobre el segundo espacio, cerca de SARUMAN. Si alcanza su valor límite, el cursor se pondrá sobre el espacio sexagéximo segundo. En una situación intermedia el cursor se posicionará proporcionalmente al valor de la energía.

    Los procesos tienen que aparecer bajo la orden ps -f con su nombre. Esto significa que será necesario usar una llamada de la familia exec para reemplazar argv[0], aunque vayamos a ejecutar el mismo ejecutable. Esto os servirá también para que vuestro código diferencie qué personaje se está ejecutando en cada momento. En esta práctica no se podrá pasar nada a los procesos hijos a través de los argvs, sólo cambiarles el nombre. Tampoco se podrán usar ficheros para nada. Las comunicaciones de PIDs o similares entre procesos se harán mediante mecanismos IPC.

    Siempre que en el enunciado 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.

  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, la memoria comparida y el buzón, y comprobad que se crean bien, con ipcs.
    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 (mandáos una señal SIGINT en esos casos).
    3. Eliminad a Elrond, Celebrian y Arwen de vuestra práctica original y lograd que funcione.
    4. Eliminar los pasos por argv, ficheros, etc. usad mecanismos IPC en su lugar.
    5. Sustituid el método de procreación de los hobbits.
    6. Añadid el mecanismo de lucha de los magos (salvo la salida por la pantalla).
    7. Introducid la salida por pantalla.
    8. Pulid los últimos detalles.


  3. Plazo de presentación.

    Hasta el lunes 17 de mayo de 2004, 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, etc.

  6. LPEs.

    1. ¿Dónde poner un semáforo? Dondequiera que uséis la frase, "el proceso debe 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. Muchos preguntáis si sobrevive un recurso IPC al hacer un exec. La respuesta obvia es que sí. El problema que tenéis no es ese. El problema es que si hacéis un semget, por ejemplo, almacenáis el identificador de los semáforos en una variable entera. Es esa variable la que no sobrevive al exec. La solución está en usar ftok para crear los semáforos y que los procesos hijos que los necesiten vuelvan a hacer un semget con la misma clave, pero sin especificar IPC_CREAT.
    4. 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.
    5. 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.
    6. 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.
    7. 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. También podéis optimizar la presentación en pantalla. Es una técnica que se usa habitualmente en el desarrollo de videojuegos gráficos. Consiste en no dar órdenes de modificación de la pantalla a no ser que sea estrictamente necesario. Explicándolo mejor: si la posición nueva del cursor coincide con la antigua, ¿para qué vamos a perder tiempo de CPU y ancho de banda en dar la instrucción de posicionado del cursor?
    8. No todos los LPEs iban a ser por problemas vuestros. Había un error en el enunciado y ponía que cuando Gandalf ganaba, el cursor se debía poner en el espacio sexagésimo noveno. Debía poner "sexagésimo segundo". Ya está corregido.
    9. 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.
    10. Os resulta confusa la parte del enunciado que dice que la práctica debe estar preparada para recibir la señal y el mensaje en cualquier orden. Lo explico mejor: vuestra práctica debe funcionar igual de bien, no importa cuándo se reciba la señal SIGUSR2, antes, durante o después de recibir el mensaje de Gandalf y, además, no se puede consumir CPU al solucionarlo.
    11. También preguntáis mucho acerca de la posición exacta del cursor en la lucha entre los dos magos. Es muy sencillo. Mientras están luchando, la variable energia puede tener un valor comprendido entre 0 y 599999. Si dividís su valor por 10000, os queda un número entre 0 y 59. Ese número es la posición del cursor dentro de los 62 espacios, dejando un espacio de margen a cada lado. Si gana SARUMAN, el cursor se pone en el primer espacio (pegado a su nombre). Si gana GANDALF (las apuestas van 100000 a 1), el cursor se pone en el último espacio de los 62, justo antes de su nombre.


  7. Prácticas propuestas años anteriores.


© 2004 Guillermo González Talaván.