Enunciado.
En esta práctica vamos a simular, mediante procesos de UNIX,
una carrera automovilística.
El programa constará de un único fichero fuente,
falonso.c, cuya adecuada compilación producirá
el ejecutable falonso. 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 (libfalonso.a)
que debéis enlazar con vuestro módulo objeto para generar el
ejecutable. Gracias a ella, muchas de las funciones 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 falonso.c libfalonso.a -o falonso
Disponéis, además, de un fichero de cabeceras,
falonso.h, donde se encuentran definidas las
macros que usa la biblioteca.
El proceso inicial se encargará de preparar todas las variables
y recursos IPC de la aplicación. También se encargará de
crear todos los procesos que gobernarán los coches. Manejará
así mismo, los semáforos del circuito. El circuito tiene forma
de lemniscata y posee dos carriles por los que se circula en
el mismo sentido. Los denominaremos carril derecho (CD) y carril
izquierdo (CI). La posición de un coche en el circuito viene
completamente determinada dando su carril y el desplazamiento
dentro de él. El desplazamiento es un número entero comprendido
entre 0 y 136, ambos incluídos. Sendos planos del circuito, uno
para cada carril, con los desplazamientos indicados se pueden
observar a continuación:
CARRIL_DERECHO
XXXX###################XXXX
XXXX# #XXXX
XXXX# 0 - - - - 1 - - #XXXX
XXXX# /60123456789012345\ #XXXX
XXX# |5 ############### 6\ #XXXX
XXX# |4 #~~~&~~~&~~~&~~# 7\ #XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXX# |3 #~&~~~&~~~&~~~&~# 8\ #XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXX# |2 #~~&~~~&~~~&~~~&~# 9\2 #XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXX# |1 ################### 0\ ########################################XXXX
XXX# \09876543210987654321 1 54321098765432109876543210987654321098 #XXXX
XXXX# 3 - - - - 2 - - - -1- 2 - -0- - - - -9- - - - -8- - - - -7- 7 #XXXX
XXXX# 1 1 1 3 1 \6 #XXXX
XXXX########################## 4\ ############################### |5 #XXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX# 5\ #~~~&~~~&~~~&~~~&~~~&~~~&~~~&~# |4 #XXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX# 6\ ############################# |3 #XXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX# 7\ /2 #XXXX
XXXX# 8-3- - - - -4- - - - -5- - - - -61 #XXXX
XXXX# 90123456789012345678901234567890 #XXXX
XXXX###################################XXXX
CARRIL_IZQUIERDO
XXXX###################XXXX
XXXX# 60123456789012345 #XXXX
XXXX# 5 0 - - - - 1 - - 6 #XXXX
XXXX# 4/ \7 #XXXX
XXX# 3| ############### \8 #XXXX
XXX# 2| #~~~&~~~&~~~&~~# \9 #XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXX# 1| #~&~~~&~~~&~~~&~# \0 #XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXX# 031 #~~&~~~&~~~&~~~&~# 2\1 #XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXX# 9| ################### \2 ########################################XXXX
XXX# 8 \ 1 1 1 3 #XXXX
XXXX# 7 - - -2- - - - -1- - 0 4 - - - - 9 - - - - 8 - - - - 7 - - - #XXXX
XXXX# 6543210987654321098765432 5 654321098765432109876543210987654 \ #XXXX
XXXX########################## \6 ############################### 3| #XXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX# \7 #~~~&~~~&~~~&~~~&~~~&~~~&~~~&~# 2| #XXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX# \8 ############################# 1| #XXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX# \90123456789012345678901234567890/ #XXXX
XXXX# -3- - - - -4- - - - -5- - - - -6 #XXXX
XXXX# #XXXX
XXXX###################################XXXX
La práctica se invocará especificando dos parámetros exactamente
desde la línea de órdenes. El primero es el número de coches
que van a participar en la carrera. El segundo puede ser 0 ó 1.
Si es 1, la práctica funcionará a velocidad normal. Si es 0, irá
a la máxima velocidad.
Los coches, al principio, se pueden colocar como se desee, siempre
que dos coches no compartan la misma posición. Una vez en
movimiento, ningún coche podrá chocar con otro de la pista.
La velocidad y los cambios de carril se dejan a vuestra discreción.
La función de cambio de carril hace que un coche cambie su
carril y el desplazamiento según la siguiente tabla:
| Der -> Izq |
|
Izq -> Der |
| 0..13 | 0..13 | |
0..15 | 0..15 |
| 14..28 | 15..29 | |
16..28 | 15..27 |
| 29..60 | 29..60 | |
29..58 | 29..58 |
| 61..62 | 60..61 | |
59..60 | 60..61 |
| 63..65 | 61..63 | |
61..62 | 63..64 |
| 66..67 | 63..64 | |
63..64 | 67..68 |
| 68 | 64 | |
65..125 | 70..130 |
| 69..129 | 64..124 | |
126 | 130 |
| 130 | 127 | |
127..128 | 130..131 |
| 131..134 | 129..132 | |
129..133 | 131..135 |
| 135..136 | 134..135 | |
134..136 | 136 |
Así, por ejemplo, un coche situado en (CD,80) pasa a (CI,75) al
cambiar de carril. Uno que esté en (CI,126) pasa a (CD,130), por
su parte.
Existe un cruce cerca del centro del circuito que está regulado
mediante un par de semáforos. El funcionamiento de los semáforos
lo realiza el proceso primero y deberá ser razonable (no se puede
mantenerlos apagados o siempre en verde, o siempre en rojo, por
ejemplo). Si un semáforo está en rojo, ningún coche deberá
sobrepasarlo.
El circuito también cuenta con un contador automático situado en
las posiciones (CD,133) y (CI,131). La aplicación desarrollada
llevará cuenta, por su parte, en una variable compartida del
número de pasos por el contador. Esto es, cada coche, al pasar
por el contador, incrementará la variable compartida. Al finalizar
el programa, se deberá pasar la dirección de memoria a la
biblioteca para que esta compruebe que vuestra cuenta y la de
ella coinciden. El programa estará en continua ejecución hasta
que el usuario pulse las teclas CTRL+C desde el terminal. En
ese momento, todos los coches deben parar (en un estado
consistente) y morirse. El proceso primero esperará por su
muerte. Informará a la biblioteca de que ha acabado,
proporcionándole vuestra cuenta de vueltas y destruirá los
mecanismos IPC utilizados.
Para que cualquier proceso pueda conocer en todo momento el
estado del sistema, se va a usar una zona de memoria compartida.
Los procesos no escribirán nunca en las partes controladas por
la biblioteca. Son sólo informaciones.
El mapa de la zona, expresado en bytes, es:
- 0-136: estado del carril derecho (' '<=>libre,
otro valor <=> ocupado por un coche)
- 137-273: idem carril izquierdo
- 274: estado del semáforo para la dirección horizontal
(ROJO, AMARILLO, VERDE ó NEGRO, macros de
falonso.h)
- 275: idem para la dirección vertical
- 276-300: reservado biblioteca
- 301-: libre para vuestras necesidades, en particular
para que contéis las vueltas
Siguiendo la misma filosofía, deberéis crear un array de semáforos,
el primero de los cuales se reservará para el funcionamiento
interno de la biblioteca. El resto, podéis usarlos libremente.
Para simplificar la realización de la práctica, se os proporciona
una biblioteca estática de funciones (libfalonso.a)
que debéis enlazar con vuestro módulo objeto para generar el
ejecutable. Disponéis, además, de un fichero de cabeceras,
falonso.h, donde se encuentran definidas las
macros que usa la biblioteca. Las funciones proporcionadas por
la biblioteca son las que a continuación aparecen. De no
indicarse nada, las funciones devuelven -1 en caso de error:
int inicio_falonso(int ret, int semAforos,
char *z)
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 si desea velocidad normal (1) o
no (0) y pasando el identificador del conjunto de
semáforos y el puntero a la zona de memoria
compartida recién creados.
int inicio_coche(int *carril, int *desp,
int color)
Esta función se debe invocar cuando se cree un
nuevo coche. Se pasarán por referencia las variables
para indicar el carril y desplazamiento del coche
y por valor, su color. La variable carril
podrá tener los valores CARRIL_DERECHO o
CARRIL_IZQUIERDO, macros definidas en
falonso.h. Los colores disponibles se
encuentran definidos en el fichero de cabeceras
falonso.h. No está permitido un coche
azul porque no se ve. Podéis añadir 8 al código de
color, si deseáis un tono más tenue o 16, si lo queréis
más vivo. Si la posición donde queremos
colocar el coche ya está ocupada, también se producirá
un error.
int avance_coche(int *carril, int *desp,
int color)
Dado un coche situado en la posición del circuito
indicada por las variables enteras carril
y desp, esta función le hará avanzar una
posición en el circuito, modificando dichas variables
de un modo acorde.
int cambio_carril(int *carril, int *desp,
int color)
Igual que la función anterior, pero el coche se mantiene
en la misma posición y sólo cambia de carril.
int luz_semAforo(int direcciOn, int color)
Pone el semáforo indicado en direcciOn al
color señalado en color (ROJO, AMARILLO,
VERDE o NEGRO).
int pausa(void)
Hace una pausa de aproximadamente una décima de
segundo, sin consumir CPU.
int velocidad(int v, int carril, int desp)
Dado un coche situado en (carril,
desp), y que marcha a una velocidad
v, esta función ejecuta una pausa, sin
consumo de CPU, del tamaño justo que hay entre dos
avances del coche. La velocidad v estará
comprendida entre 1 y 99, reservándose al valor 100
para la máxima velocidad que permite el ordenador
(pausa efectiva nula).
int fin_falonso(int *cuenta)
Se llama a esta función después de muertos los hijos
y haber esperado por ellos
y antes de destruir los recursos IPC. El
parámetro es la dirección de memoria compartida
donde se ha llevado la cuenta de las vueltas de los
coches (pasos por línea de meta).
Respecto a la sincronización interna de la biblioteca, se
usa el semáforo reservado bien para poder actualizar la
pantalla, bien para el manejo de la memoria compartida. Seguro que
necesitaréis hacer sincronizaciones adicionales para que la
práctica funcione. Para que esas sincronizaciones estén en
sintonía con la biblioteca, os ofrezco ahora un seudocódigo de
las funciones que realiza la biblioteca. S es es semáforo
interno que utiliza.
* inicio_falonso:
- limpia la pantalla
- S=1
- mensaje de bienvenida
- dibuja el circuito
* inicio_coche:
- comprobación de parámetros
- W(S)
- si posición ocupada, S(S), poner error, volver.
- pintar el coche y actualizar la memoria compartida
- S(S)
* avance_coche:
- comprobación de parámetros
- W(S)
- borrar el coche y actualizar la memoria compartida
- avanzar una posición
- si hay choque, S(S), poner error, volver.
- pintar el coche y actualizar la memoria compartida
- si pasamos por el contador, incrementarlo y pintarlo
- S(S)
- si nos hemos saltado un semáforo en rojo, poner error, volver.
* cambio_carril:
- comprobación de parámetros
- W(S)
- borrar el coche y actualizar la memoria compartida
- cambiar de carril
- si hay choque, S(S), poner error, volver.
- pintar el coche y actualizar la memoria compartida
- S(S)
- si nos hemos saltado un semáforo en rojo, poner error, volver.
* luz_semAforo:
- comprobación de parámetros
- W(S)
- dibujar semáforo y actualizar memoria compartida
- S(S)
* fin_falonso:
- si no coinciden las vueltas, poner error, volver.
Cada vez que se pone un error, se pone W(S) y S(S) rodeando la impresión
en pantalla. Las funciones pausa() y velocidad() no usan el semáforo.
En cuanto al consumo de CPU, no debe consumirse CPU cuando
un coche espere a que el semáforo de su carril se ponga en
verde. Tampoco en los instantes iniciales cuando, después de
haber colocado todos, deis el pistoletazo de salida. Podéis,
aunque evidentemente se premiará al que logre hacerlo bien
siendo como es difícil, consumir CPU para evitar choques
o alcances o los coches que estén esperando a la cola de un
semáforo en rojo. En estos casos, y para ser respetuosos con
el ordenador, se realizará en todo caso "semiespera ocupada",
intercalando en el sondeo una pausa de una décima de segundo.
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 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 libfalonso
Con esta práctica se trata de que aprendáis a sincronizar y
comunicar procesos en UNIX. Su objetivo no es la programación.
Es por ello que se os suministra una biblioteca estática de
funciones ya programadas para tratar de que no tengáis que
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 libfalonso.a
y el fichero de cabecera falonso.h. La biblioteca
funciona con los códigos de VT100/xterm, por lo que debéis adecuar
vuestros simuladores a este terminal.
Ficheros necesarios: