PRÁCTICAS DE LABORATORIO DE SISTEMAS OPERATIVOS

PRIMERA PRÁCTICA EVALUABLE (2007-08)

Pistoleros de Kentucky

  1. Enunciado.

    El programa que hay que presentar constará de un único fichero fuente de nombre pistolos.c. La correcta compilación de dicho programa, producirá un fichero ejecutable, cuyo nombre será obligatoriamente pistolos. Respetad las mayúsculas/minúsculas de los nombres, si las hubiere.

    La ejecución del programa creará una serie de procesos que representarán una partida del problema del pistolero.

    En dicho problema, un número determinado de pistoleros del oeste norteamericano se colocan en círculo. Cada uno de ellos elige al azar a un compañero. A la de tres, disparan todos al unísono. Algunos pistoleros se libran, algunos reciben uno o más disparos. Se retiran los cadáveres, los supervivientes cierran el corro y comienza una nueva ronda de elección y disparos. La historia puede acabar de dos únicos modos, con la supervivencia de uno o de ningún pistolero. Matemáticamente, lo interesante es calcular la probabilidad de que sobreviva un pistolero dependiendo del número inicial de ellos. Esto no nos interesará en esta práctica.

    En la práctica, cada pistolero vendrá representado por un proceso, hijos todos del proceso original, que ejecuta main. A este proceso original se le pasará por la línea de órdenes un número entero, correspondiente con el número inicial de pistoleros que forman la partida. El número estará comprendido entre 3 y 128.

    A continuación, tendrá tantos hijos como indique dicho número. El padre regula el funcionamiento de las rondas hasta llegar al final de ellas. En el caso de que, al final, quede un proceso pistolero vivo, lo matará, tomará su código de retorno y pondrá el resultado final de la partida. El padre sólo matará, de tener que hacerlo, a este último pistolero. No participa en las rondas disparando.

  2. Funcionamiento de una ronda de disparos

    En cada ronda de disparos, el proceso padre imprime en un fichero los PIDs de los pistoleros que están vivos para que ellos lo puedan leer y sepan a quién pueden disparar. Escribe en la pantalla lo equivalente a este ejemplo: 
    *** COMIENZA LA RONDA NUMERO 7 ***
*** PIDs: 1234 1689 1748 2222
    Acto seguido, enviará una señal SIGUSR1 a cada uno de ellos para indicarles que pueden elegir al compañero y dispararle.

    Los pistoleros eligen, entonces, a otro pistolero al azar. No pueden dispararse a sí mismos. Anuncian el PID del pistolero elegido por la pantalla y envian una señal SIGTERM a dicho pistolero, para matarlo.


    La salida por la pantalla siguiendo el ejemplo anterior podría ser: 
    1234->1689
2222->1689
1748->2222
1689->1748
    Debe aparecer, por lo tanto, una línea por cada proceso indicando a qué proceso ha disparado. No tienen por qué aparecer en orden. Dependerá de cómo reparta el Sistema Operativo la CPU. Y también deben disparar todos los pistoleros, incluso aunque les haya llegado un disparo antes.

    El proceso padre hará tantas llamadas al sistema waits como procesos pistoleros había antes de disparar y, de este modo, sabrá qué procesos han muerto a causa de los disparos.

    Como puede que algún proceso quede vivo y, para que el proceso padre no espere eternamente, se necesita algo que le despierte de la espera bloqueante en que le sumen los waits. Esto lo logra el propio proceso padre, mediante una llamada previa a a alarm antes de dormirse. La llamada hará que el Sistema Operativo le envíe una señal SIGALRM cuando pase un segundo.

    El proceso padre sabe, al final, cuántos procesos han quedado vivos y puede iniciar una nueva ronda en el caso de que sea necesario.

  3. Restricciones



  4. Plazo de presentación.

    Hasta el jueves, 3 de abril de 2008, inclusive.

  5. Normas de presentación.

    Acá están.

  6. LPEs.

    1. Las tareas que tiene que realizar el programa son variadas. Os recomiendo que vayáis programándolas y comprobándolas una a una. No es muy productivo hacer todo el programa de seguido y corregir los errores al final. El esquema que os recomiendo seguir para facilitaros la labor se os muestra a continuación:
      1. Haced un pequeño programa que cree un pistolero y deje a padre e hijo en un pause(). Compiladlo, ejecutadlo, comprobadlo con ps -fu y depuradlo, si fuera necesario.
      2. El siguiente paso es modificar el programa para que tenga 7 pistoleros.
      3. Si todo va bien, lograr que se tengan tantos pistoleros como los especificados en una variable.
      4. Es el momento de que se creen tantos procesos pistoleros como se indique en la línea de órdenes.
      5. El siguiente esfuerzo se centrará en lograr que una ronda se ejecute correctamente.
      6. Podemos comenzar consiguiendo que el padre ponga los PIDs de los hijos en la pantalla y los escriba en un fichero. Los hijos deben leer del fichero.
      7. Aquí nos vamos a encontrar con el primer problema de concurrencia. Debemos garantizar que el padre haya escrito por completo el fichero antes de que ningún hijo lo lea. La solución nos la brinda el propio enunciado al decirnos que el padre va a enviar SIGUSR1 después de escribir los PIDs en el fichero. Debemos conseguir que el padre envíe la señal a todos los hijos y que estos no se mueran al recibirla, cosa que harán si no cambiamos el comportamiento por defecto de la señal con sigaction.
      8. Pero si pensábamos que ahí iban a acabar nuestros malos sueños, nos equivocábamos: la pesadilla no ha hecho más que empezar. Debemos plantearnos en qué lugares del código del hijo se puede recibir la señal y si la solución que planteamos es válida se reciba donde se reciba. Si no fuera así, una solución es bloquear con sigprocmask SIGUSR1 en la zona conflictiva y desbloquearla cuando no tenga peligro el recibirla (quizá en un sigsuspend).
      9. El resto del camino es algo más fácil. Debemos sustituir el pause de padre por llamadas a wait para que recoja el código de retorno de los pistoleros muertos.
      10. Los pistoleros deben ahora seleccionar a un compañero e imprimir por la pantalla a quién van a disparar. Para elegir al pistolero, usad la función de generación de números aleatorios del C rand(). Con cuidado, pues todos los procesos deben llamar a srand() para iniciar el generador y lo suyo es que cada pistolero, cuando nació haya llamado a esa función con un argumento diferente de modo que obtengan números diferentes y no todos maten al mismo. Una idea es que el PID del proceso participe en la fórmula que pongáis como argumento a srand().
      11. Llega el momento de disparar. Se manda la señal SIGTERM al pistolero elegido. Observad en la compilación y ejecución de este paso que mueren los que deben morir (es decir, los que han sido anunciados).
      12. ¿No ocurre así? Vuestra intuición ya os debería haber avisado... ¿Qué ocurre si un pistolero recibe un disparo antes de que le haya dado tiempo a disparar él mismo? Pues eso. Similarmente a como hicimos antes, SIGTERM es evidente que debe estar bloqueada en ciertas zonas para que la cosa funcione...
      13. En nuestra situación anterior, dejamos al padre esperando por los hijos en waits y algunos hijos muertos y otros que se han librado. A no ser que dé la casualidad de que se mueran todos, el padre se va a quedar atrapado en los waits para siempre. Como dice el enunciado que la espera es como máximo de 1 segundo, la mejor solución es usar alarm para que, al cabo de un segundo, el sistema operativo despierte al padre con un SIGALRM
      14. Ya os habréis dado cuenta de que tanto "despierta" el sistema operativo al hijo que, literalmente, lo mata, pues SIGALRM tiene ese comportamiento por defecto. Tenéis que evitar que eso ocurra y tenéis que diferenciar el despertar del padre de un wait debido a que recibe SIGALRM del despertar debido a que se ha muerto un hijo.
      15. Si vuestra intuición se va desarrollando puede que hayáis pensado qué ocurre si mueren todos los hijos. El padre seguiría adelante y recibiría el SIGALRM en cualquier momento, seguro que cuando no fuera conveniente. La solución a esto pasa por desarmar el alarm en ese caso (muerte de todos).
      16. La parte difícil del programa está hecha. Os queda hacer varias rondas. El padre debe ver qué procesos hay vivos y ver si acaba o comienza una nueva ronda...
    2. No se puede usar sleep() o similares para sincronizar los procesos. Hay que usar otros mecanismos.
    3. Sabéis que si usáis espera ocupada en lugares donde explícitamente no se haya dicho que se puede usar, la práctica está suspensa. No obstante, existe una variedad de espera ocupada que podríamos denominar espera semiocupada. Consiste en introducir una espera de algún segundo en cada iteración del bucle de espera ocupada. Con esto el proceso no consume tanta CPU como en la espera ocupada, pero persisten los demás problemas de la técnica del sondeo, en particular el relativo a la elección del periodo de espera. Aunque la práctica no estará suspensa si hacéis espera semiocupada, se penalizará en la nota bastante si la usáis. En conveniente que la evitéis.
    4. Evitad, en lo posible, el uso de variables globales. Tenéis la posibilidad de declarar variables estáticas.
    5. Tened cuidado con el uso de pause(). Salvo en bucles infinitos de pauses, su uso puede estar mal. Mirad la solución a la práctica propuesta en la sesión quinta acerca de él o el siguiente LPE.
    6. El programa que he hecho se para a veces. O en mi casa se para, pero en clase, no. O en clase sí, pero en casa, no.
      Solución.
    7. ¿Qué hago cuando mi programa se desboca para no perjudicar el funcionamiento de la máquina?
      Solución.
    8. Para abrir el fichero, escribir y cerrarlo, debéis usar las llamadas al sistema open o creat, read, write y close. No debéis usar las de la familia de fopen. Si necesitáis escribir o leer algo con formato, usad las funciones sprintf y sscanf como intermediarias.
    9. ¡Muy importante! Para que se pueda pasar a la ronda siguiente es necesario que el proceso se "entere" de si ha sobrevivido o no. Esta información solamente la tiene el padre (pues es el que comprueba quién queda vivo pasado un segundo). Es conveniente que los hijos, una vez matan a uno de sus hermanos, se esperen o bien a que les maten o bien a que el padre les diga que han sobrevivido. El padre puede avisar de esto enviando a los hijos que sobreviven SIGUSR2. El esquema del código del hijo podría quedar así: 
         fork(); []
   ...
   bucle_de_rondas:
     sigsuspend();        [SIGUSR1]
     elegir_hermano();    []
     disparar_hermano();  []
     sigsuspend();        [SIGTERM, SIGUSR2]
   fin_bucle_de_rondas;
      Entre corchetes se han puesto las señales que se permiten en cada instrucción. Si aparece vacío es que todas están bloqueadas.
    10. ¡Muy importante! Un compañero relata cómo tiene problemas con el esquema anterior debido a lo siguiente. Puede ocurrir que, pasado el segundo de cortesía que ofrece el padre, se disponga este a enviar SIGUSR2 a los procesos que han sobrevivido. El padre continúa, escribe el fichero de PIDs y manda SIGUSR1. Pero puede ocurrir que tengamos un pistolero "rápido como el rayo" que pase el sigsuspend de SIGUSR2 primero y el de SIGUSR1 después antes de que los demás hayan pasado del de SIGUSR2. El resultado es que dispara y esa bala, que es de la siguiente ronda, no lo olvidemos, impacta en el pistolero en la ronda anterior y la cosa falla. Como solución, que podéis usar, propone el compañero que el padre espere otro segundo, con alarm antes de volver a mandar SIGUSR1. Podéis ver con esta práctica lo mala que es efectivamente la sincronización con señales. Todos estos problemas se solucionarán asépticamente con los mecanismos que veremos a partir de las siguientes sesiones.


  7. Prácticas propuestas en años anteriores.

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