PRÁCTICAS DE LABORATORIO DE SISTEMAS OPERATIVOS

SEGUNDA PRÁCTICA EVALUABLE (2005-06)

Cambios de grupo


  1. Enunciado.

    En esta práctica vamos a simular, mediante procesos de UNIX, las solicitudes y concesión (o no) de cambios de grupo en esta asignatura.

    El programa constará de un único fichero fuente, cambios.c, cuya adecuada compilación producirá el ejecutable cambios. 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 (libcambios.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 cambios.c libcambios.a -o cambios
    Disponéis, además, de un fichero de cabeceras, cambios.h, donde se encuentran definidas, entre otras cosas, las macros que usa la biblioteca.

    El proceso inicial se encargará de preparar todas las variables y recursos IPC de la aplicación. Este proceso creará 32 procesos hijos. Cada proceso hijo, representa a una persona. Los nombres de las personas, junto con las abreviaturas usadas para referirse a ellas, se muestran en la siguiente tabla:
    (A) Ana(I) Ignacio (a) Alberto(i) Ildefonsa
    (B) Benito(J) Juan (b) Bonifacia(j) Josefa
    (C) Carla(L) Laura (c) Conrado(l) Luis
    (D) Daniela(M) Manuel (d) David(m) María
    (E) Emilio(N) Nicanor (e) Eulalia(n) Natalia
    (F) Flor(O) Olvido (f) Federico(o) Olegario
    (G) Gonzalo(P) Pedro (g) Gracia(p) Pilar
    (H) Honoria(R) Rosa (h) Hilario(r) Ramón


    En la asignatura hay cuatro grupos (I, II, III y IV) y se ha establecido inicialmente que los grupos se formarán en atención a la inicial del nombre de la persona. La partición se ha efectuado siguiendo el criterio: A-D, E-H, I-M, N-R, para los grupos I, II, III y IV, respectivamente. Cada proceso, según nace, ha de ir al grupo que le corresponde.

    La vida de los procesos transcurre plácida y tranquila. Duermen un tiempo y, pasado este, deciden que quieren cambiar de grupo. Se lo solicitan al proceso padre, que por cierto se llama Zacarías(Z). Z, viendo las solicitudes que hay en cada momento, decide conceder el cambio inmediatamente o hacerlo más tarde. El criterio que se mantiene es que cualquier cambio no debe implicar variación en el número de alumnos por grupo. Por ejemplo, si hay un alumno que quiere ir del grupo I al II y otro que quiere ir del II al I, es un cambio correcto. Si hay un alumno que quiere ir del I al II, otro del II al III y otro del I al IV, es un cambio incorrecto.

    La práctica se mantiene en ejecución hasta que pasan 15 segundos (en el caso de que funcione a máxima velocidad) o 30 segundos en otro caso. Al finalizar la práctica, deben morir los hijos y Z debe esperar por su muerte. Cuantos más cambios de grupo haya sido capaz de gestionar Z, mejor solucionada estará la práctica.

    La pertenencia de un alumno a un grupo determinado se establece en una zona de memoria compartida. Se trata de 80 caracteres consecutivos asociados en parejas. Cada pareja puede estar en uno de dos estados:
    1. El primer carácter es un espacio (ASCII 32) y el segundo es cualquiera. En este caso, ahí no hay ninguna persona
    2. El primer carácter es una letra de entre "ABCDEFGHIJLMNOPRabcdefghijlmnopr" y el segundo tiene un código ASCII comprendido entre 1 y 4, ambos incluidos. Si esto es así, significa que ahí está la persona que se especifica en el primer carácter y que quiere ir al grupo que se corresponde con el segundo carácter. Si dicho grupo coincide con su grupo actual, significa que no quiere cambiarse.
    Las parejas de la primera a la décima, corresponden al grupo I. Las siguientes decenas corresponden al II, al III y al IV, respectivamente. Es evidente que, una vez situadas todas las personas inicialmente en sus puestos, no puede desaparecer una persona de la zona de memoria compartida ni puede estar en dos sitios a la vez.

    Cada vez que una persona logra satisfactoriamente cambiar de grupo, debe incrementar un contador. Este contador, de tipo entero, está situado en la zona de memoria compartida a continuación de donde se encuentran las parejas del párrafo anterior, es decir, con un desplazamiento de 84 bytes respecto al principio de la zona. También debe la persona que logra cambiarse de grupo invocar la correspondiente función de la biblioteca para incrementar el contador interno de verificación. El objetivo de esto es que, al final, deben, como es obvio, casar las veces que ha contado la biblioteca con el valor de los cambios de la variable en la zona de memoria compartida.

    Para que los procesos hagan una solicitud y para recibir la aceptación de Z, se usará un único buzón de paso de mensajes. El formato de los mensajes enviados se deja libre.

    La práctica se invocará especificando un parámetros exactamente desde la línea de órdenes. El 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. El tiempo de ejecución en este caso será de 30 segundos. 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, el tiempo de ejecución será de 15 segundos.

    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.

    Las funciones proporcionadas por la biblioteca libcambios.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.

    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.
        * inicioCambios:
             - limpia la pantalla
             - S=1
             - mensaje de bienvenida
             - refrescar
    
        * finCambios:
             - refrescar
             - comprobaciones varias antes de acabar
    
        * refrescar:
             - comprobación de valores de letras y grupos
             - W(S)
             - refrescar la presentación
             - S(S)
             - comprobación de la consistencia
    
        * 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 libcambios.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 libcambios.a y el fichero de cabecera cambios.h. La biblioteca funciona con los códigos de VT100/xterm, por lo que debéis adecuar vuestros simuladores a este terminal.
    Ficheros necesarios:

    NOTA: en el caso de los ficheros de Solaris, casi es preferible que hagáis un enlace simbólico en lugar de copiarlos o bajarlos desde el servidor:
    ln -s /home/labssoo/public_html/CAMBIOS/libcambios.a libcambios.a
    ln -s /home/labssoo/public_html/CAMBIOS/cambios.h cambios.h
    Si así lo hacéis, además de ahorrar espacio de almacenamiento en el disco del servidor, como ya sabéis, las posibles actualizaciones de la biblioteca son automáticas y no tenéis que bajarlas de nuevo cuando se produzcan.

  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. 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 inicio_cambios en main. Debe aparecer la pantalla de bienvenida y, pasados dos segundos, dibujarse la pantalla.
    4. Probad a hacer algunos cambios manuales en la zona de memoria y llamad a refrescar. Probad también la función de incremento del contador.
    5. Cread los hijos y ponedles a ejecutar su ciclo de vida. Al final todos tienen que solicitar un cambio, pero el padre no los atiende.
    6. Que el padre tenga algo de inteligencia y atienda algunos de los cambios solicitados.
    7. Acabad la práctica y probadla a velocidad normal y a velocidad cero.
    8. Diseñad la forma de acabar sin problemas y llamad a la función finCambios().
    9. Pulid los últimos detalles.


  3. Plazo de presentación.

    Hasta el martes, 2 de mayo de 2006, 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.

  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. 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.
    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 puesta inicial de los procesos en cada grupo y cuando un proceso quiere ir (tiene permiso) a una clase llena. 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. A muchos de vosotros os aparece el siguiente error cuando llamáis a la función refrescar:
      Grupo Incorrecto: (g=1,pos=1): grupo preferido=49
      La razón está en la confusión entre el carácter cuyo código ASCII es uno y el carácter '1', cuyo código ASCII es 49. La biblioteca espera que pongáis el grupo al que quiere ir una persona como un carácter cuyo código ASCII esté comprendido entre uno y cuatro. Recordad que una variable de tipo char, desde el punto de vista del C, es también una variable entera y poner 'A' es lo mismo que poner 65 y poner '1' es lo mismo que poner 49.
    12. 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.
    13. Muy importante: la colocación inicial de las personas y el paso de una clase a otra de una persona que tiene concedido el cambio, lo tiene que hacer el proceso que se encarga de dicha persona, nunca el proceso Z. El proceso que tiene un cambio concedido, buscará un hueco en la clase de destino y, una vez localizado, se borrará de la clase de origen y se escribirá en la clase de destino.
    14. Había un error en el enunciado. El desplazamiento del contador debe ser 84 bytes respecto del inicio de la zona de memoria compartida y no 80, como ponía.
    15. 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
    16. ¿Puede un grupo estar lleno cuando un proceso busque un hueco para cambiarse? Pues en realidad, sí. Imaginad dos grupos, el uno y el dos. En el uno hay tres personas que quieren ir al dos y en el dos hay otras tres que quieren ir al uno. Las dos primeras personas del grupo dos van al uno. Sin embargo, las dos personas del uno por las que se cambian, aún no han obtenido CPU. Cuando va la tercera persona del grupo dos a cambiarse, se encuentra el grupo uno lleno. Tened cuidado con esto. No podéis usar espera ocupada para esperar a conseguir un hueco. La práctica estaría suspensa. La solución pasa por usar semáforos para controlar esto también. Mirad la teoría, en el apartado del productor/ consumidor de búffer limitado, pues es el mismo problema.
    17. Tened cuidado con el esquema que usáis para conceder los cambios. No es válido que cuando Z recibe una petición del 1 al 2, espere un mensaje de alguien que quiera ir del 2 al 1 y tenga esperando a otras personas en la cola. Huid también de los esquemas que ciclan infinitamente en el buzón hasta localizar el cambio posible. Si no hay cambios posibles, Z no debe consumir CPU.


  7. Prácticas propuestas años anteriores.


© 2006 Guillermo González Talaván.