PRÁCTICAS DE LABORATORIO DE SISTEMAS OPERATIVOS

PRIMERA PRÁCTICA OBLIGATORIA (2004-05)

El efecto dominó

  1. Enunciado.

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

    La ejecución del programa creará una serie de procesos cuya vida simulará la caída de una ristra de fichas de dominó. En concreto, el árbol de procesos que hay que crear es el siguiente:


    Los procesos han sido colocados para reflejar la colocación espacial de las fichas que representan. Las relaciones paterno-filiales son las indicadas por las líneas sólidas. El valor y el orden de los PIDs puede variar debido lo último al reparto de CPU de cada ejecución.

    Los procesos, una vez creados, deben permanecer bloqueados, sin consumir CPU. Cuando se mande la señal SIGTERM al proceso original, se originará una cascada de señales que, al final, deberán resultar en la finalización de todos los procesos. Siendo más específicos, las señales que se deben mandar son las indicadas en la siguiente figura:


    Por ejemplo, cuando el proceso 38 recibe la señal del 37, antes de morir, debe mandar la señal SIGTERM al 39. Y todos así. Nótese que el 51, el 53 y el 55 se encargan de matar a procesos que no son sus hijos. Para ello, deben conocer el PID de las víctimas. Para poder comunicarlos, debéis usar un único fichero proyectado en memoria. Dicho fichero será único y servirá para transmitir cualquier información entre procesos, su formato es libre y sólo se podrá usar mediante proyección en memoria.

    Si se requiere sincronizar alguna acción, se pueden usar señales, pero la espera se debe realizar sin consumo de CPU. Para simplificar el problema, podéis suponer que al ser mandada la señal inicial manualmente, ya ha habido tiempo suficiente para que todos los procesos hayan sido creados para cuando el primer proceso la reciba. Sin embargo, esta concesión en aras de simplificación, no implica suponer ninguna condición, incluida ésta, en ninguna otra parte de la práctica.

    Para ver si habéis conseguido crear el árbol de procesos correctamente, podéis descargaros el siguiente ejecutable: Arbol_dominO. No os va a funcionar en Linux, pues es un ejecutable binario. Desde el servidor, para ver el árbol de procesos que habéis generado, usad la orden: ps -f | grep "dom$" | grep -v grep | sort | Arbol_dominO. Si os aparece el mensaje "Árbol con múltiples raíces. Se aborta.", significa que habéis corrido varias veces vuestra práctica sin matar los procesos de la anterior. Esta puede ser una salida correcta del programa: 
             19417
           |
         19418
           |
         19419
     /¯¯¯¯¯¯¯¯¯¯¯\
   19420       19428
  /¯¯¯¯¯\     /¯¯¯¯¯\
19421 19429 19430 19436
  |     |     |     |
19422 19431 19432 19437
  |     |     |     |
19423 19433 19434 19438
  |           |
19424       19435
  |
19425
  |
19426
  |
19427
    En el caso de Linux, podéis usar la opción -f de la orden ps.

  2. Restricciones



  3. Plazo de presentación.

    Hasta el viernes, 15 de abril de 2005, inclusive.

  4. Normas de presentación.

    Acá están.

  5. 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 (los números de los procesos se refieren al PID que aparece en el ejemplo de las figuras de más arriba):
      1. Haced un pequeño programa que cree los procesos 37, 38 y 39. Compiladlo, ejecutadlo, comprobadlo con Arbol_dominO y depuradlo, si fuera necesario.
      2. Repetid el procedimiento con los procesos 40 y 41 primero, 42, 43, 44 y 45, después. Alternativamente, podéis intentar generarlos todos de golpe.
      3. Continuad con los procesos del 42 al 53.
      4. Finalizad con la ristra 54, 56, 57 y 58, y el proceso 55.
      5. Una vez el árbol esté bien generado, comprobad que los procesos no consumen CPU con top.
      6. Llega el momento de matar. De nuevo, hacedlo por partes. Primero, que mueran sólo 37, 38 y 39. Es fácil, basta con registrar una manejadora para SIGTERM, donde se mande la señal SIGTERM al siguiente proceso.
      7. No es mucho más difícil irse cargando del 40 al 53.
      8. El problema llega para que el 51 elimine al 54. Si solucionáis bien este caso, lo podéis generalizar para las parejas (53,55) y (55,56). El problema es más sutil de lo que a primera vista parece. Para que 51 pueda matar a 54 en su manejadora, necesita conocer el PID de 54, lo que es algo difícil al no ser un ascendiente suyo o un hijo suyo. 54 se lo tiene que decir de algún modo. La manera de hacerlo es mediante el fichero proyectado en memoria que se puede usar. 54 escribe su PID en el fichero y 51 lo lee. Pero ahí no acaban los problemas. Si resulta que 51 nace antes y trata de leer el fichero antes de que 54 lo haya escrito, leerá basura y no mandará la señal correctamente. Ni se os ocurra colocar cero en el fichero y que 51 vaya leyendo hasta que aparezca un valor distinto de cero, sería espera ocupada y la práctica estaría suspensa. De algún modo, 54 debe avisar a 51 de que ya ha escrito en el fichero y puede leer. Para ello, nada mejor que enviarle una señal a 51, SIGUSR1, por ejemplo. 51 se quedará esperando, sin consumir CPU, a que 54 se la mande. La llamada al sistema sigsuspend es una buena candidata para hacerlo. Perfecto, ¿verdad?

        Pues va a ser que no. Las trampas de la programación en paralelo nos esperan a la vuelta de cada esquina. Para que 54 pueda mandar la señal a 51, debe conocer el PID de 51. Vuelta a empezar el razonamiento. Mejor usar el fichero para transferir el PID de 51. Pero tampoco se debe adelantar 54 a leer... Parece un círculo vicioso, pero no es así. El esquema que debéis plantear con estas ideas que os he dado ha de ser global considerando los dos procesos a la vez.
      Podéis ya acabar la práctica siguiendo un esquema similar al expuesto, una vez superada esta última dificultad.
    2. Para matar los procesos después de cada ejecución, hay una manera muy cómoda. Si habéis usado "dom &" para ejecutar la práctica, podéis usar "kill %" para matar a todos los procesos de golpe.
    3. No se puede usar sleep() o similares para sincronizar los procesos. Hay que usar otros mecanismos.
    4. 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 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.
    5. Evitad, en lo posible, el uso de variables globales. Tenéis la posibilidad de declarar variables estáticas.
    6. Tened cuidado con el uso de pause(). Salvo en bucles infinitos de pauses, su uso puede estar mal. Mirad lo nuevo que hay en la sesión quinta acerca de él o el siguiente LPE.
    7. Hay que tener cuidado en Solaris, pues en su configuración por defecto, en la página de manual tanto mmap como munmap pone que admiten punteros comodín (void *). Sin embargo, en la práctica, exigen char *. No tiene mayor problema. Haced un casting para evitar el warning del compilador para solucionarlo.
    8. Es conveniente que, antes de entregar la práctica, comprobéis que los kills están enviando la señal a los procesos correctos. Si al imprimirlo resulta que a veces mandan la señal al proceso "0", es que está mal. Lo que ocurre es que el proceso que realiza el kill recibe la señal SIGTERM y salta a la manejadora antes de actualizar la variable que contiene el pid de su hijo. Por eso la variable tiene 0. La solución consiste en que el patriarca bloquee SIGTERM y cada proceso la desbloquee justo antes de quedarse parado y después de haber hecho todas sus tareas. Dependiendo de cómo hayáis programado SIGUSR1 puede ser necesario un esquema parecido o no.
    9. No debéis esperar la muerte de los hijos con wait. Se trata precisamente de que, en lo posible, los procesos vayan muriendo de arriba a abajo como fichas de dominó que caen.
    10. Tened cuidado con dónde enviáis la señal SIGUSR1, si usáis ese esquema. Si no lo hace el proceso 54, puede ocurrir que, si no sois cuidadosos, 51 lea antes de que 54 escriba. Cuidad de que 40 reciba la señal una vez esté garantizado que 54 ha escrito su pid. Y lo mismo para el resto de ramas.
    11. 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.
    12. ¿Qué hago cuando mi programa se desboca para no perjudicar el funcionamiento de la máquina?
      Solución.
    13. Puede ser necesario que el patriarca de todos los procesos escriba algo en el fichero auxiliar, aunque sólo sea para que el resto de procesos puedan hacer la proyección (que el fichero no esté vacío). Si no lo hacéis así, la llamada mmap os dará error.
    14. Es necesario que respetéis la forma del árbol exactamente. Quiere esto decir que el primer hijo del primer biznieto del patriarca es del que debe partir la ristra larga y el primer hijo del segundo biznieto es del que debe partir la segunda ristra más larga. Para ver si lo habéis hecho bien, comprobad los PIDs de los tataranietos (el de menor PID es el más joven, o sea, el primero).


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

© 2005 Guillermo González Talaván y Susana Álvarez Rosado.