ENUNCIADO
Windows NT no tiene la posibilidad de decrementar en más de una
unidad un semáforo atómicamente. UNIX sí. Con esto es casi trivial
hacer la práctica. Sin ello, hay que pensar un poco :).
Cuando construyeron el edificio de usos múltiples de Volrejas
no lo hicieron con ascensor. Ahora ya lo instalaron. En el
cartel pone "Para tres personas", pero eso es porque no
conocen a los gemelos Robustines.
Con sus 163.5 kg por barba, cada uno ocupa por dos. Eso por no
comentar su afición a subir por el ascensor continuamente.
Toda la mañana se pasan subiendo por el ascensor y bajando
por la escalera, para volver a subir.
Esta compulsión la comparte con Muzzala y Mocosette.
Haced un programa que, durante un minuto muestre cómo suben
y bajan los personajes descritos. Considerad que el viaje
en ascensor tarda 3 s y que en bajar por las escaleras tardan
1 s.
La salida por pantalla ha de consistir en líneas como esta:
Esperando: Mu R2 Ascensor: Mo Escalera: R1
Esperando: Mu R1 R2 Ascensor: Mo Escalera:
Esperando: Mu R1 R2 Ascensor: Escalera: Mo
etc.
COMENTARIOS
Para no complicar la solución en exceso, podemos suponer que
existe una función montar_ascensor() que se
bloquea en el caso de que el ascensor no esté en el piso hasta
que llegue. De modo parecido suponemos que existe otra,
salir_ascensor(), para lo que su nombre indica.
Puestas así las cosas, el ascensor es una
zona de exclusión mutua donde puede haber tres procesos como
máximo bien entendido que los gemelos Robustines cuentan cada
uno como dos.
Si se pidiera resolver la práctica con semáforos de tipo Unix,
la solución sería trivial. El esquema más simple consistiría
en la repetición infinta de:
Ssitio=3
Mo y Mu Robustines
======= ==========
W(Ssitio); W(Ssitio,Ssitio);
montar_ascensor(); montar_ascensor();
sleep(3); sleep(3);
bajar_ascensor(); bajar_ascensor();
S(Ssitio); S(Ssitio,Ssitio);
sleep(1); sleep(1);
Con la notación W(x,x) indicamos que se ha de
hacer dos operaciones wait sobre el semáforo x de un
modo atómico (en el caso de Unix, con un único semop).
La solución para Windows NT no es trivial y, la que obtiene el
premio en esta ocasión, tampoco es fácilmente generalizable a
ascensores más grandes o diferente número de personas. Los autores
son Gurú y Capitán y su esquema es el siguiente:
ascensor=2 (máximo 2) robus=1 (máximo 1)
Mo y Mu Robustines
======= ==========
W(robus);
W(ascensor); W(ascensor);
montar_ascensor(); montar_ascensor();
sleep(3); sleep(3);
bajar_ascensor(); bajar_ascensor();
S(ascensor); S(ascensor);
S(robus);
sleep(1); sleep(1);
Incluyen, además, otro semáforo para que la salida por pantalla
de los hilos no se entremezcle y que se ha omitido en el esquema
por simplicidad. El esquema de Gurú y Capitán saca partido de
que, dados los datos en concreto de este problema, las reglas
son equivalentes a estas otras:
- En el ascensor sólo pueden ir dos personas como máximo.
- No pueden montar dos Robustines a la vez.
Podéis observar que esto lo logran haciendo dos secciones críticas.
Una interna que afecta a todos los procesos y que hace cumplir la
primera regla y otra externa, que sólo afecta a los Robustines
y que impone la segunda regla. Aquí está el código para Win32:
#include <stdio.h>
#include <string.h>
#include <windows.h>
#define PERROR(a)\
{\
LPVOID lpMsgBuf;\
FormatMessage(FORMAT_MESSAGE_ALLOCATE_BUFFER|FORMAT_MESSAGE_FROM_SYSTEM\
|FORMAT_MESSAGE_IGNORE_INSERTS,NULL,GetLastError(),\
MAKELANGID (LANG_NEUTRAL, SUBLANG_DEFAULT),\
(LPTSTR) &lpMsgBuf, 0, NULL);\
fprintf (stderr, "%s:%s\n", a, lpMsgBuf);\
LocalFree (lpMsgBuf);\
}
DWORD WINAPI Muzzala (LPVOID param);
DWORD WINAPI Mocosette (LPVOID param);
DWORD WINAPI Robustines1 (LPVOID param);
DWORD WINAPI Robustines2 (LPVOID param);
void escribir (struct datos *info);
struct datos
{HANDLE ascensor, robus, control;
int EspMu,EspMo,EspR1,EspR2;
int AscMu,AscMo,AscR1,AscR2;
int EscMu,EscMo,EscR1,EscR2;
};
int main (int argc, char *argv[])
{struct datos *info;
HANDLE Mu,Mo,R1,R2;
DWORD IdMu,IdMo,IdR1,IdR2;
DWORD salidaprocess;
if (argc!=1)
{fprintf(stderr,"Numero de parametros incorrecto\n");}
info=(struct datos *)malloc(sizeof(struct datos));
if (info==NULL)
{PERROR ("Error al reservar memoria"); exit(2);}
info->EspMu=1;
info->EspMo=1;
info->EspR1=1;
info->EspR2=1;
info->ascensor=CreateSemaphore(NULL,2,2,NULL);
if (info->ascensor==NULL)
{printf("Error al crear semaforo ascensor\n"); exit(3);}
info->robus=CreateSemaphore(NULL,1,1,NULL);
if (info->robus==NULL)
{PERROR("Error al crear semaforo robus"); exit(4);}
info->control=CreateSemaphore(NULL,1,1,NULL);
if (info->control==NULL)
{PERROR("Error al crear semaforo control"); exit(5);}
escribir(info);
Mu=CreateThread(NULL,0,&Muzzala,info,0,&IdMu);
if (Mu==NULL)
{PERROR("Error al crear el hilo Mu"); exit(6);}
Mo=CreateThread(NULL,0,&Mocosette,info,0,&IdMo);
if (Mo==NULL)
{PERROR("Error al crear el hilo Mo"); exit(7);}
R1=CreateThread(NULL,0,&Robustines1,info,0,&IdR1);
if (R1==NULL)
{PERROR("Error al crear el hilo R1"); exit(8);}
R2=CreateThread(NULL,0,&Robustines2,info,0,&IdR2);
if (R2==NULL)
{PERROR("Error al crear el hilo R2"); exit(9);}
Sleep(60000);
return 0;}
DWORD WINAPI Muzzala (LPVOID param)
{int val;
struct datos *info;
info=(struct datos *)param;
for(;;)
{val=WaitForSingleObject(info->ascensor,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo ascensor en Mu"); exit(11);}
val=WaitForSingleObject(info->control,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo control en Mu 1"); exit(12);}
info->EspMu=0; info->AscMu=1; info->EscMu=0;
escribir(info);
val=ReleaseSemaphore(info->control,1,NULL);
if(!val)
{PERROR("Incrementar semaforo control en Mu 1"); exit(13);}
Sleep(3000);
val=WaitForSingleObject(info->control,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo control en Mu 2"); exit(14);}
info->AscMu=0; info->EscMu=1;
escribir(info);
val=ReleaseSemaphore(info->control,1,NULL);
if(!val)
{PERROR("Incrementar semaforo control en Mu 2"); exit(15);}
val=ReleaseSemaphore(info->ascensor,1,NULL);
if(!val)
{PERROR("Incrementar semaforo ascensor en Mu"); exit(16);}
Sleep(1000);
val=WaitForSingleObject(info->control,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo control en Mu 3"); exit(17);}
info->EscMu=0; info->EspMu=1;
escribir(info);
val=ReleaseSemaphore(info->control,1,NULL);
if(!val)
{PERROR("Incrementar semaforo control en Mu 3\n"); exit(18);}
}
}
DWORD WINAPI Mocosette (LPVOID param)
{int val;
struct datos *info;
info=(struct datos *)param;
for(;;)
{val=WaitForSingleObject(info->ascensor,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo ascensor en Mo"); exit(19);}
val=WaitForSingleObject(info->control,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo control en Mo 1"); exit(20);}
info->EspMo=0; info->AscMo=1; info->EscMo=0;
escribir(info);
val=ReleaseSemaphore(info->control,1,NULL);
if(!val)
{PERROR("Incrementar semaforo control en Mo 1"); exit(21);}
Sleep(3000);
val=WaitForSingleObject(info->control,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo control en Mo 2"); exit(22);}
info->AscMo=0; info->EscMo=1;
escribir(info);
val=ReleaseSemaphore(info->control,1,NULL);
if(!val)
{PERROR("Incrementar semaforo control en Mo 2"); exit(23);}
val=ReleaseSemaphore(info->ascensor,1,NULL);
if(!val)
{PERROR("Incrementar semaforo ascensor en Mu"); exit(24);}
Sleep(1000);
val=WaitForSingleObject(info->control,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo control en Mo 3"); exit(25);}
info->EscMo=0; info->EspMo=1;
escribir(info);
val=ReleaseSemaphore(info->control,1,NULL);
if(!val)
{PERROR("Incrementar semaforo control en Mo 3\n"); exit(26);}
}
}
DWORD WINAPI Robustines1 (LPVOID param)
{int val;
struct datos *info;
info=(struct datos *)param;
for(;;)
{val=WaitForSingleObject(info->robus,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo robus en R1"); exit(27);}
val=WaitForSingleObject(info->ascensor,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo ascensor en R1"); exit(28);}
val=WaitForSingleObject(info->control,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo control en R1 1"); exit(29);}
info->EspR1=0; info->AscR1=1; info->EscR1=0;
escribir(info);
val=ReleaseSemaphore(info->control,1,NULL);
if(!val)
{PERROR("Incrementar semaforo control en R1 1"); exit(30);}
Sleep(3000);
val=WaitForSingleObject(info->control,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo control en R1 2"); exit(31);}
info->AscR1=0; info->EscR1=1;
escribir(info);
val=ReleaseSemaphore(info->control,1,NULL);
if(!val)
{PERROR("Incrementar semaforo control en R1 2"); exit(32);}
val=ReleaseSemaphore(info->ascensor,1,NULL);
if(!val)
{PERROR("Incrementar semaforo ascensor en R1"); exit(33);}
val=ReleaseSemaphore(info->robus,1,NULL);
if(!val)
{PERROR("Incrementar semaforo robus en R1"); exit(34);}
Sleep(1000);
val=WaitForSingleObject(info->control,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo control en R1 3"); exit(35);}
info->EscR1=0; info->EspR1=1;
escribir(info);
val=ReleaseSemaphore(info->control,1,NULL);
if(!val)
{PERROR("Incrementar semaforo control en R1 3"); exit(36);}
}
}
DWORD WINAPI Robustines2 (LPVOID param)
{int val;
struct datos *info;
info=(struct datos *)param;
for(;;)
{val=WaitForSingleObject(info->robus,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo robus en R2"); exit(37);}
val=WaitForSingleObject(info->ascensor,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo ascensor en R2"); exit(38);}
val=WaitForSingleObject(info->control,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo control en R2 1"); exit(39);}
info->EspR2=0; info->AscR2=1; info->EscR2=0;
escribir(info);
val=ReleaseSemaphore(info->control,1,NULL);
if(!val)
{PERROR("Incrementar semaforo control en R2 1"); exit(40);}
Sleep(3000);
val=WaitForSingleObject(info->control,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo control en R2 2"); exit(41);}
info->AscR2=0; info->EscR2=1;
escribir(info);
val=ReleaseSemaphore(info->control,1,NULL);
if(!val)
{PERROR("Incrementar semaforo control en R2 2"); exit(42);}
val=ReleaseSemaphore(info->ascensor,1,NULL);
if(!val)
{PERROR("Incrementar semaforo ascensor en R2"); exit(43);}
val=ReleaseSemaphore(info->robus,1,NULL);
if(!val)
{PERROR("Incrementar semaforo robus en R2"); exit(44);}
Sleep(1000);
val=WaitForSingleObject(info->control,INFINITE);
if(val==WAIT_FAILED)
{PERROR("Decrementar semaforo control en R2 3"); exit(45);}
info->EscR2=0; info->EspR2=1;
escribir(info);
val=ReleaseSemaphore(info->control,1,NULL);
if(!val)
{PERROR("Incrementar semaforo control en R2 3"); exit(46);}
}
}
void escribir (struct datos *info)
{printf ("Esperando: ");
if (info->EspMu==1) printf("Mu ");
if (info->EspMo==1) printf("Mo ");
if (info->EspR1==1) printf("R1 ");
if (info->EspR2==1) printf("R2 ");
printf("\tAscensor: ");
if (info->AscMu==1) printf("Mu ");
if (info->AscMo==1) printf("Mo ");
if (info->AscR1==1) printf("R1 ");
if (info->AscR2==1) printf("R2 ");
printf("\tEscalera: ");
if (info->EscMu==1) printf("Mu ");
if (info->EscMo==1) printf("Mo ");
if (info->EscR1==1) printf("R1 ");
if (info->EscR2==1) printf("R2 ");
printf("\n"); fflush(stdout);
}
LPEs
- Los propios autores de la práctica premiada cometen un
error al terminar la función
main:
int val;
[...]
val=GetExitCodeProcess(GetCurrentProcess(),&salidaprocess);
if(!val)
{printf("Error al obtener codigo de salida de proceso\n"); exit(7);}
ExitProcess(salidaprocess);
return 0;
Parece evidente que en este caso no se conoce cómo funciona
el mecanismo de devolución de valores de los procesos. En
Windows NT, el mecanismo es muy parecido al de UNIX. Si
queremos que un proceso acabe y devuelva un valor,
podemos devolverlo a través de un
return del main. Alternativamente,
podemos invocar ExitProcess desde cualquier
lugar de nuestro código. No obstante, la función
GetExitCodeProcess se debe usar para coger
el valor devuelto por otro proceso una vez muerto.
Por inercia, tendéis a pensar que es equivalente a
wait de UNIX y no es así.
GetExitCodeProcess sólo debe ser invocada
cuando el proceso haya muerto, o sea, cuando el proceso
pase al estado de señalado.
- No hubiera estado de más el realizar la práctica con
alguna función menos. Una sola función para los dos gemelos
y otra para los dos restantes estaría mejor.
- Se os puede ocurrir que el orden de la sección crítica
de los Robustines no importa y proponer un esquema como
este:
ascensor=2 (máximo 2) robus=1 (máximo 1)
Mo y Mu Robustines
======= ==========
W(ascensor); W(ascensor);
W(robus);
montar_ascensor(); montar_ascensor();
sleep(3); sleep(3);
bajar_ascensor(); bajar_ascensor();
S(robus);
S(ascensor); S(ascensor);
sleep(1); sleep(1);
Esto no sería correcto. Podría ocurrir que un Robustín
estuviera dentro del ascensor y el otro tuviera cogido
el semáforo ascensor y estuviera esperando por el
semáforo robus. Él no podría pasar como es
lógico, pero está impidiendo hacerlo a quién sí podría:
Mo o Mu y esto no es aceptable.
- Si habéis pensado, como muchos de vosotros, en la siguiente
solución:
ascensor=3 (máximo 3) SC1=1 (máximo 1) SC2=1 (máximo 1)
Mo y Mu R1 R2
======= ========== ==========
W(SC1); W(SC2);
W(ascensor); W(ascensor); W(ascensor);
W(ascensor); W(ascensor);
S(SC1); S(SC2);
montar_ascensor(); montar_ascensor(); montar_ascensor();
sleep(3); sleep(3); sleep(3);
bajar_ascensor(); bajar_ascensor(); bajar_ascensor();
S(ascensor); S(ascensor);
S(ascensor); S(ascensor); S(ascensor);
sleep(1); sleep(1); sleep(1);
...olvidaros de ella. Supongamos que Mo está dentro del ascensor.
R1 puede tomar un ascensor de los dos que quedan.
En ese momento, le quitan la CPU. R2 puede tomar el otro
ascensor y que también le quiten la CPU. Llega
ahora Mu y no puede entrar porque R1 y R2 tienen ocupados
dos ascensores y no los usan. Es más, el de R2
es inútil tenerlo porque nunca podría llegar a usarlo si
no acaba R1. Además, si hubiera un R3 se podría producir interbloqueo,
con lo que tampoco es una solución general. Se daría
interbloqueo cuando R1, R2 y R3 tuvieran cada uno un
ascensor y esperaran por el segundo.
- No os rendís, ¿eh? Parece que lo volvéis a intentar con:
ascensor=3 (máximo 3) SC=1 (máximo 1)
Mo y Mu Robustines
======= ==========
W(SC);
W(ascensor); W(ascensor);
W(ascensor);
S(SC);
montar_ascensor(); montar_ascensor();
sleep(3); sleep(3);
bajar_ascensor(); bajar_ascensor();
S(ascensor);
S(ascensor); S(ascensor);
sleep(1); sleep(1);
...pero sin éxito. R1 puede estar dentro del ascensor
y R2 haber tomado SC, pues recordemos que R1 ya está montado,
y un ascensor. Es
evidente que no puede tomar el segundo semáforo
ascensor. Sin embargo, está impidiendo que Mo o
Mu puedan montar. Esto no es razonable. Además, por si a alguien
el argumento del punto anterior no le convenció mucho, este
argumento, más claro, también es aplicable a aquél.
¿Se anima alguien a encontrar una solución generalizable a
cualquier número de Robustines y flacos y cualquier capacidad
del ascensor, tal y como se puede hacer en Unix?
© 2003 Guillermo González Talaván.