Doctora

PROGRAMACIÓN CONCURRENTE – TEMA 2.2

Sincronización con Semáforos
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA INFORMÁTICA DEPARTAMENTO DE CIENCIAS DE LA COMPUTACIÓN

El problema de la cena de los filósofos
• 5 Filósofos piensan libremente y comen en una mesa con 5 platos. • Cada plato está asignado a un filósofo. • Los platos se reponen continuamente • Hay 5 tenedores, uno entre cada par deplatos adyacentes

El problema de la cena de los filósofos
• Comer:
El filósofo se sienta delante de su plato y toma de uno en uno los tenedores situados a ambos lados de su plato (Preprotocolo) Come Cuando finaliza, deja los dos tenedores en su posición original (Postprotocolo) Todo filósofo que come, en algún momento se sacia y termina
3

El problema de la cena de los filósofos
•Requisitos:
Un filósofo sólo puede comer cuando tenga los dos tenedores Los tenedores se cogen y se dejan de uno en uno Dos filósofos no pueden tener el mismo tenedor simultáneamente (EM de acceso al tenedor) Si varios filósofos tratan de comer al mismo tiempo, uno de ellos debe conseguirlo. (Ausencia Interbloqueo) Si un filósofo desea comer y tiene competencia, en algún momento lo deberá poder hacer.(Ausencia de Inanición) En ausencia de competencia, un filósofo que quiera comer deberá hacerlo sin retrasos innecesarios (Ausencia retrasos)
4

Problema de la cena de los filósofos
Solución con semáforos. 1er intento. Interbloqueo
PROCESS TYPE tFílosofo (Id:INTEGER; VAR Tenedor:tTenedor); BEGIN REPEAT Pensar; VAR WAIT (Tenedor[Id]); Tenedor:tTenedor; Filosofo:ARRAY [1..NFilosofos] OF WAIT(Tenedor[Id MOD Nfilosofos +1]); Comer; SIGNAL(Tenedor[Id MOD Nfilosofos +1]); tFilosofo; i:INTEGER; SIGNAL (Tenedor[Id]); BEGIN FOREVER FOR i:=1 to Nfilosofos DO END; INITIAL(Tenedor[i], 1);
COBEGIN FOR i:=1 TO Nfilosofos DO Filosofo[i](i,Tenedor); COEND; END.

CONST NFilosofos=5; TYPE tTenedor = ARRAY [1..NFilosofos] OF SEMAPHORE

Problema de la cena de los filósofos
Solución con semáforos.1er intento. Interbloqueo
fil. 0
pensar; Wait(tenedor[i]); Wait(tenedor[Id MOD Nfilosofos +1];

fil. 1
pensar; Wait(tenedor[i]);

fil. 2

fil. 3

fil. 4

pensar; pensar(); pensar; semWait(tenedor Wait(tenedor[i] Wait(tenedor[i] [i]); ); );

t[0] t[1] t[2] t[3] t[4] 1 1 1 1 1 0 0 0 0 0

X

X

X

X

X

Problema de la cena de los filósofos
Solución con semáforos. 2ºintento. Limitar la entrada
PROCESS TYPE tFílosofo (Id:INTEGER; VAR Tenedor:tTenedor; VAR: Comedor); BEGIN REPEAT Pensar; VAR WAIT (Comedor); Comedor: SEMAPHORE; Tenedor:tTenedor; WAIT (Tenedor[Id]); Filosofo:ARRAY [1..NFilosofos] OF WAIT (Tenedor[Id MOD Nfilosofos +1]); tFilosofo; Comer; i:INTEGER; SIGNAL(Tenedor[Id MOD Nfilosofos +1]); BEGIN SIGNAL (Tenedor[Id]); INITIAL (Comedor,4); SIGNAL(Comedor); FOR i:=1 to Nfilosofos DO FOREVER INITIAL(Tenedor[i], 1); COBEGIN END; CONST NFilosofos=5; TYPE tTenedor = ARRAY [1..NFilosofos] OF SEMAPHORE
FOR i:=1 TO Nfilosofos DO Filosofo[i](i,Tenedor,Comedor); COEND; END.

Problema de la cena de los filósofos
Solución con semáforos. 2º intento. Limitar la entrada
filósofo 0 filósofo 1 filósofo 2 filósofo 3 filósofo 4 come t[0 t[1 t[2 t[3 t[4 d. ] ]] ] ]

4
pensar(); semWait(comedor); pensar(); semWait(comedor); pensar(); semWait(comedor); pensar(); semWait(comedor); pensar(); semWait(comed or) semWait(tenedor[i]); semWait(tenedor[i]); semWait(tenedor[i]); semWait(tenedor[i]);

1 1 1 1 1

3 2 1 0

X
semWait(tenedo r[(i+1)%5]);

0

0

0

0 0 1 1

semWait(tenedor[(i+1) semWait(tenedor[(i+1) semWait(tenedor[(i+1)semWait(tenedor[(i+1) %5]) %5]) %5]) %5]

X

X

X

comer(); semSignal(tenedor[(i+1) %5]) semSignal(tenedor[i]); semSignal(comedor);

1

Problema de la cena de los filósofos
Solución con semáforos. 3er intento. 4 zurdos y 1 diestro
PROCESS TYPE tFilosofoDiestro (Id:INTEGER; VAR Tenedor:tTenedor); BEGIN REPEAT Pensar; WAIT (Tenedor[Id MOD Nfilosofos +1]); (*1º Drcho.*) WAIT (Tenedor[Id]);...