sábado, 3 de abril de 2010

Encrucijada (I: Enunciado)

Hoy toca un post kilométrico que llevo demasiado tiempo pendiente, no se siquiera dejará publicar entero. Bueno, estoy pensando que, para evitar problemas la parte grande la voy a colocar en el siguiente.
En este caso se trata de la 2º práctica evaluable de la asignatura de Laboratorio de Sistemas Operativos de 2º de ITIS en la Universidad de Salamanca.
La práctica era bastante difícil, no vamos a negarlo, hasta el propio Guillermo se encontró con que era muy compleja. Decía así:

En la práctica anterior hubimos de sufrir la falta de medios para comunicar adecuadamente a los procesos entre sí. En esta práctica pondremos remedio a la situación permitiendo usar los nuevos mecanismos IPC recientemente aprendidos. Se tratará de regular la circulación en un cruce controlado por semáforos de tráfico.

En esta segunda práctica usaréis una biblioteca de enlazado estático que se os proporcionará. El objetivo es doble: por un lado aprender a usar una de tales bibliotecas y por otro descargar parte de la rutina de programación de la práctica para que os podáis centrar en los problemas que de verdad importan en esta asignatura.


El programa constará de un único fichero fuente, cruce.c, cuya adecuada compilación producirá el ejecutable cruce. 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 (libcruce.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:
gcc cruce.c libcruce.a -o cruce
Disponéis, además, de un fichero de cabeceras, cruce.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 CRUCE_inicio con los parámetros adecuados. El proceso será responsable de crear los procesos adicionales necesarios. Cada peatón o cada coche simulado será representado mediante un proceso, hijo del proceso principal. También es responsabilidad del primer proceso el 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 en caso de ejecución satisfactoria o un número mayor que cero, en caso de detectarse un error.

La práctica se invocará especificando dos parámetros obligatorios desde la línea de órdenes. El primer parámetro será el número máximo de procesos que puede haber en ejecución simultánea. El segundo consistirá en 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 modo de lograr esto lo realiza la propia biblioteca. Vosotros no tenéis más que pasar dicho argumento a la función de inicio. 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 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 o buzones para sincronizar adecuadamente la práctica. En ningún caso podréis usar en vuestras prácticas más de un array de semáforos, un buzón de paso de mensajes y una zona de memoria compartida. Se declarará un 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.

La biblioteca requiere memoria compartida. Debéis declarar una única zona de memoria compartida en vuestro programa. Los 256 bytes primeros de dicha zona estarán reservados para la biblioteca. Si necesitáis memoria compartida, reservad más cantidad y usadla a partir del byte bicentésimo quincuagésimo séptimo.

Las funciones proporcionadas por la biblioteca libcruce.a son las que a continuación aparecen. De no indicarse nada, las funciones devuelven -1 en caso de error:
  • int CRUCE_inicio(int ret, int maxProcs, int semAforos, char *zona)
    El primer proceso, después de haber creado los mecanismos IPC que se necesiten y antes de haber tenido ningún hijo, debe llamar a esta función, indicando en ret la velocidad de presentación y en maxProcs el número máximo de procesos permitidos en esta ejecución (parámetros ambos de la línea de órdenes) y pasando además el identificador del conjunto de semáforos que se usará y el puntero a la zona de memoria compartida declarada para que la biblioteca pueda usarlos.
  • int CRUCE_pon_semAforo(int sem, int color)
    Pone el semáforo sem al color color. El primer parámetro puede ser: SEM_P1, SEM_P2, SEM_C1, SEM_C2, para los semáforos de peatones y coches, respectivamente. El segundo parámetro puede valer: ROJO,AMARILLO(solamente para los semáforos de coches) o VERDE. Estas son todas macros definidas en cruce.h.
  • int CRUCE_nuevo_proceso(void)
    El padre, después de haber creado todo lo necesario, se encuentra en un bucle infinito en el que va generando los nuevos procesos, coches o peatones. Esta función le devuelve COCHE o PEAToN para que sepa de qué tipo es el proceso que tiene que crear a continuación.
  • struct posiciOn CRUCE_inicio_coche(void) y struct posiciOn CRUCE_inicio_peatOn(void)
    El nuevo proceso hijo, dependiendo de si es coche o peatón, llamará a una de estas dos funciones. La función correspondiente devolverá las coordenadas de la posición siguiente del objeto recién creado. La funciónCRUCE_inicio_peatOn es desaconsejada. Úsese mejor la siguiente función.
  • struct posiciOn CRUCE_inicio_peatOn_ext(struct posiciOn *posNacimiento)
    El nuevo proceso hijo, si es un peatón, llamará a esta función. La función devolverá las coordenadas de la posición siguiente del peatón recién creado y la posición de nacimiento en el parámetro pasado por referencia. Esta función sustituye a la correspondiente del apartado anterior.
  • struct posiciOn CRUCE_avanzar_coche(struct posiciOn sgte) y struct posiciOn CRUCE_avanzar_peatOn(struct posiciOn sgte)
    El proceso, después de haber llamado a la función anterior, se mete en un bucle de avance. A esta función se le pasa la posición a la que se quiere ir y devuelve la nueva posición siguiente. Del bucle se saldrá cuando en la coordenada y de la posición devuelta haya un valor menor que cero.
  • int pausa_coche(void) e int pausa(void)
    Entre dos avances consecutivos, los coches llaman a la primera función y los peatones a la segunda. La segunda función también sirve para medir las pausas del ciclo semafórico
  • int CRUCE_fin_coche(void) e int CRUCE_fin_peatOn(void)
    El proceso hijo que haya salido del bucle de avance, invoca esta función.
  • int CRUCE_fin(void)
    El padre, una vez sabe que ha acabado la práctica y antes de realizar limpieza de procesos y mecanismos IPC debe llamar a esta función.
  • void pon_error(char *mensaje)
    Pone un mensaje de error en el recuadro azul de la parte inferior de la pantalla y espera a que el usuario pulse "Intro". La podéis usar para depurar.


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

El guión que seguirá el proceso padre será el siguiente:
  1. Tomará los datos de la línea de órdenes y los verificará.
  2. Iniciará las variables, mecanismos IPC, manejadoras de señales y demás.
  3. Llamará a la función CRUCE_inicio.
  4. Creará el proceso gestor semafórico.
  5. Entrará en un bucle infinito del que solamente saldrá si se pulsa CTRL+C. Dentro del bucle:
    1. Si hay tantos procesos como el máximo declarado, se queda esperando, sin consumo de CPU, hasta que muera alguno.
    2. Llamará a la función CRUCE_nuevo_proceso, que responderá indicando de qué tipo será: coche o peatón.
    3. Creará un proceso hijo, que ejecutará las funciones correspondientes a su tipo.
  6. Cuando se pulse CTRL+C, se engargará de finalizar todo ordenadamente.


Por su parte, el proceso gestor semafórico realizará lo que sigue en un bucle infinito:
  1. Establecerá el estado de los semáforos de tráfico según en la fase en que nos encontremos.
  2. Dormirá, sin consumo de CPU, el tiempo correspondiente a esa fase.


Finalmente, los procesos que circulan (peatones o coches), entrarán en un bucle después de llamar a su función de inicio. Dentro del bucle, llamarán a la función de pausa y a la de avance hasta que esta última devuelva un valor menor que cero en la coordenada y. El proceso acaba no sin antes llamar a la función de fin.

Observad que existe mucha sincronización que no se ha declarado explícitamente y debéis descubrir dónde y cómo realizarla. Os desaconsejamos el uso de señales para sincronizar. Una pista para saber dónde puede ser necesaria una sincronización son frases del estilo: "después de ocurrido esto, ha de pasar aquello" o "una vez todos los procesos han hecho tal cosa, se procede a tal otra".

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 y las verificaciones. Para que las sincronizaciones que de seguro deberéis hacer en vuestro código estén en sintonía con las de la biblioteca, debéis saber que sólo las funciones que actualizan valores sobre la pantalla están sincronizadas mediante el semáforo de la biblioteca.

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.

Ciclo semafórico

En la práctica hay cuatro semáforos de tráfico, dos de peatones (P1 y P2) y dos de automóviles (C1 y C2):


El ciclo semafórico pasa por tres fases principales:
  • Primera fase: C1 y P2 en verde. El resto, en rojo. Duración: 6 pausas(*).
  • Segunda fase: C2 en verde. El resto, en rojo. Duración: 8 pausas.
  • Tercera fase: P1 en verde. El resto, en rojo. Duración: 12 pausas.
(*) Una pausa equivale a una llamada a la función pausa().

Biblioteca de funciones libcruce.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 libcruce.a y el fichero de cabeceras cruce.h. La biblioteca funciona con los códigos de VT100/xterm, por lo que debéis adecuar vuestros simuladores a este terminal. También se usa la codificación UTF-8, por lo que necesitáis un programa de terminal que sepa interpretarlos. Los terminales de Linux lo hacen por defecto, pero si usáis Windows, debéis aseguraros de que el programa tiene capacidad para interpretarlos y que esta capacidad está activada. Si no es así notaréis caracteres basura en la salida de modo que no se verá nada.
Ficheros necesarios:
Registro de versiones:
  • 1.0: primera versión
  • 1.1: un error hace que no se reconozca bien al padre en CRUCE_nuevo_proceso
  • 1.2: la biblioteca tenía preferencia por sacar coches en la dirección horizontal
  • 2.0: para controlar el nacimiento de los peatones es necesario conocer no solamente su posición siguiente, sino también, su posición de nacimiento. Para ello, se crea una nueva función: CRUCE_nuevo_peatOn_ext

No hay comentarios: