II Examen Parcial de Algoritmos Paralelos
Kevin Mike Herrera Vega
Cdigo: 2012-36144
Universidad Nacional Jorge Basadre Grohmann Facultad de ingeniera
Algoritmo Paralelos
31 07 - 2013
I.
Algoritmo de la cena de los filsofos implementado con
semforos.
Algoritmo:
1. Inicio
2. Definicin de Proceso Filsofos(numero)
2.1. Repetir
2.1.1. Pensar de 1 a 5 segundos.
2.1.2. Esperar( Sillas_libres )
2.1.3. Esperar( Tenedor[numero] )
2.1.4. Esperar( Tenedor[ residuo(numero/N) + 1 ] )
2.1.5. Comer de 1 a 5 segundos.
2.1.6. Seal( Tenedor[numero] )
2.1.7. Seal( Tenedor[ residuo(numero/N) + 1 ])
2.1.8. Seal(Sillas_libres)
2.2. Para Siempre
3. Para i = 1 hasta N hacer
3.1. Inicializar Tenedor[ i ] = 1
4. Fin_Para
5. Inicializar Sillas_libres = N - 1
6. Iniciar Ejecucin concurrente.
6.1. Para i=1 hasta N hacer
6.1.1. Proc_filosofo[ i ]( i )
6.2. Fin_Para
7. Finalizar ejecucin concurrente
8. Fin
Cdigo:
Lenguaje de Programacin: Pascal FC
program Filosofos_semaforos;
const
N = 5;
var
palillo : array [1..N] of semaphore; (* binario *)
sillaslibre : semaphore; (* general *)
I : integer;
process type filosofos(numero : integer);
begin
repeat
writeln('Pensando el ',numero:2);
sleep(random(5)); (* PENSANDO *)
wait(sillaslibre);
wait(palillo[numero]);
wait(palillo[(numero mod N) + 1]);
writeln('Comiendo el ',numero:2);
sleep(random(5)); (* COMIENDO *)
signal(palillo[numero]);
signal(palillo[(numero mod N) + 1]);
signal(sillaslibre)
forever
end; (* filosofos *)
var
procfil: array[1..N] of filosofos;
begin
for I := 1 to N do
initial(palillo[I],1);
initial(sillaslibre,N - 1);
cobegin
for I := 1 to N do
procfil[I](I);
coend
end.
Diagrama de flujo
Definicin del proceso usando semforos:
Proc_filosofo(numero)
Pensar de 1 a 5 segundos.
WAIT( Sillas_libres )
WAIT( Tenedor[numero] )
WAIT( Tenedor[ residuo(numero/N) + 1 ] )
Comer de 1 a 5 segundos.
SIGNAL( Tenedor[numero] )
SIGNAL( Tenedor[ residuo(numero/N) + 1 ])
SIGNAL(Sillas_libres)
W
Para Siempre
Diagrama Principal
Inicio
Para i = 1 hasta N
Tenedor[ i ] = 1
Sillas_libres = N - 1
Proc_filosofo[1]( 1 )
Proc_filosofo[2]( 2 )
Proc_filosofo[3]( 3 )
Proc_filosofo[4]( 4 )
Proc_filosofo[ 5]( 5 )
Fin
II.
Algoritmo de la cena de filsofos implementado con
monitores.
Algoritmo:
1. Inicio
2. Procedimiento Getpalillo( i )
2.1. Si palillo[i] 2 luego
2.1.1. Mensaje de espera
2.1.2. Dormir okparacomer[i] segundos
2.2. Fin_Si
2.3. Palillo[ Residuo( ( i+1 )/5 ) ] = Palillo[ Residuo( ( i+1 )/5 ) ] - 1
2.4. Palillo[ Residuo( ( i+4 )/5 ) ] = Palillo[ Residuo( ( i+4 )/5 ) ] - 1
3. Fin_Getpalillo
4. Procedimiento Putpalillo( i )
4.1. Palillo[ Residuo( ( i+1 )/5 ) ] = Palillo[ Residuo( ( i+1 )/5 ) ] + 1
4.2. Palillo[ Residuo( ( i+4 )/5 ) ] = Palillo[ Residuo( ( i+4 )/5 ) ] + 1
4.3. Si Palillo[ Residuo( (i+1)/5) ] = 2 luego
4.3.1. Resume( okparacomer[ Residuo( ( i + 1 )/5 ) ] )
4.4. Fin_Si
4.5. Si Palillo[ Residuo( (i+4)/5) ] = 2 luego
4.5.1. Resume( okparacomer[ Residuo( ( i + 4 )/5 ) ] )
4.6. Fin_Si
5. Fin_Putpalillo
6. Definicin de monitor palillomon
6.1. Para i = 0 hasta 4 hacer
6.1.1. Palillo[i] = 2
6.2. Fin Para
7. Fin_palillomon
8. Procedimiento Piensa
8.1. Null
9. Fin_Piensa
10. Procedimiento Come (n)
10.1.
[Link](n)
10.2.
[Link](n)
11. Fin_Come
12. Definicin de proceso Filosofol(n)
12.1.
Repetir
12.1.1. Piensa
12.1.2. Come(n)
12.2.
Para Siempre
13. Fin_Filosofo
14. Iniciar concurrencia
14.1.
Para num = 0 hasta 4 hacer
14.1.1. Filosofo[num](num)
14.2.
Fin_Para
15. Finalizar concurrencia
16. Fin.
Cdigo:
Lenguaje de Programacin: Pascal FC
program Filosofos_monitores;
var
j, num: integer;
monitor palillomon;
export
getpalillo,
putpalillo;
var
palillo: array [0..4] of integer;
okparacomer: array [0..4] of condition;
i: integer;
procedure getpalillo(i: integer);
begin
if palillo[i] <> 2 then
begin
writeln('Filosofo ',i:2,' esta esperando');
delay(okparacomer[i])
end;
palillo[(i+1) mod 5] := palillo[(i+1) mod 5] - 1;
palillo[(i+4) mod 5] := palillo[(i+4) mod 5] - 1;
writeln('Filosofo ',i:2,' come')
end; (* getpalillo *)
procedure putpalillo(i: integer);
begin
writeln('Filosofo ',i:2,' termina');
palillo[(i+1) mod 5] := palillo[(i+1) mod 5] + 1;
palillo[(i+4) mod 5] := palillo[(i+4) mod 5] + 1;
if palillo[(i+1) mod 5] = 2 then
resume(okparacomer[(i+1) mod 5]);
if palillo[(i+4) mod 5] =2 then
resume(okparacomer[(i+4) mod 5])
end; (* putpalillo *)
begin (* cuerpo del monitor *)
for i := 0 to 4 do
palillo[i] := 2
end; (* palillomon *)
procedure piensa;
begin
null
end; (* piensa *)
procedure come(n: integer);
begin
[Link](n);
sleep(1);
[Link](n)
end; (* come *)
process type tipofil(n: integer);
begin
repeat
piensa;
come(n)
forever
end; (* filosofo *)
var
filosofo: array[0..4] of tipofil;
begin (* principal *)
cobegin
for num := 0 to 4 do
filosofo[num](num)
coend
end.
Diagrama de flujo
Diagrama de los procedimientos del monitor
Getpalillo(i)
Si
palillo[i] 2
Mensaje de espera
Sleep( okparacomer[i] )
Palillo[ Residuo( ( i+1 )/5 ) ] = Palillo[ Residuo( ( i+1 )/5 ) ] - 1
Palillo[ Residuo( ( i+4 )/5 ) ] = Palillo[ Residuo( ( i+4 )/5 ) ] - 1
W
Para Siempre
Putpalillo(i)
Palillo[ Residuo( ( i+1 )/5 ) ] = Palillo[ Residuo( ( i+1 )/5 ) ] + 1
Palillo[ Residuo( ( i+4 )/5 ) ] = Palillo[ Residuo( ( i+4 )/5 ) ] + 1
Si
Palillo[ (i+1) mod 5 ] = 2
Resume( okparacomer[ Residuo( ( i + 1 )/5 ) ] )
Si
Palillo[ (i+4) mod 5 ] = 2
Resume( okparacomer[ Residuo( ( i + 4 )/5 ) ] )
W
Para Siempre
Diagrama de definicin del monitor
Monitor palillomon
Para i = 0 hasta 4
Palillo[ i ] = 2
Diagrama de otros procedimientos del algoritmo
Procedimiento come(n)
Procedimiento piensa
NULL
[Link](n)
[Link](n)
Diagrama del Proceso Filosofo
Definicin de Filosofo
Piensa
Come(n)
W
Para Siempre
Diagrama Principal
Inicio
Filosofo[1]( 1 )
Filosofo[2]( 2 )
Filosofo[3]( 3 )
Filosofo[4]( 4 )
Fin
III.
Algoritmo de Dekker implementado con semforos
Algoritmo
1. Inicio
2. Proceso P1
2.1. Esperar(mutex)
2.2. Bandera 1 = verdadero
2.3. Mientras Bandera2 = verdadero hacer
2.3.1. Si turno = 2 luego
[Link]. Bandera1 = falso
[Link]. Mientras turno = 2 no hacer nada
[Link]. Bandera1 = verdadero
2.3.2. Fin_Si
2.4. Fin_Mientras
2.5. Ejecutar regin critica
2.6. Turno = 2
2.7. Bandera1 = falso
2.8. Seal(mutex)
3. Fin_P1
4. Proceso P2
4.1. Esperar(mutex)
Filosofo[ 5]( 5 )
5.
6.
7.
8.
9.
10.
11.
4.2. Bandera 2 = verdadero
4.3. Mientras Bandera1 = verdadero hacer
4.3.1. Si turno = 1 luego
[Link]. Bandera2 = falso
[Link]. Mientras turno = 1 no hacer nada
[Link]. Bandera2 = verdadero
4.3.2. Fin_Si
4.4. Fin_Mientras
4.5. Ejecutar regin critica
4.6. Turno = 1
4.7. Bandera2 = falso
4.8. Seal(mutex)
Fin_P2
Inicializar Seal(mutex)
Inicializar Bandera1 = falso
Inicializar Bandera2 = falso
Inicializar turno = 1
Ejecutar de manera concurrente P1 y P2
Fin
Cdigo:
Lenguaje de Programacin: Pascal FC
PROGRAM AlgoritmoDeDekker;
VAR
bandera1, bandera2: boolean;
turno: integer;
mutex: semaphore;
PROCEDURE P1;
BEGIN
wait(mutex);
bandera1 := true;
WHILE bandera2=true DO
BEGIN
IF turno = 2 THEN
BEGIN
bandera1 := false;
WHILE turno = 2 DO null;
bandera1 := true;
END;
END;
(*** Region Critica ***)
writeln('Se ejecuta el proceso 1');
turno := 2;
bandera1 := false;
signal(mutex);
END;
PROCEDURE P2;
BEGIN
wait(mutex);
bandera2 := true;
WHILE bandera1 = true DO
BEGIN
IF turno = 1 THEN
BEGIN
bandera2 := false;
WHILE turno = 1 DO;
bandera2 := true;
END;
END;
(*** Region Critica ***)
writeln('Se ejecuta el proceso 2');
turno := 1;
bandera2 := false;
signal(mutex);
END;
BEGIN
signal(mutex);
bandera1 := false;
bandera2 := false;
turno := 1;
COBEGIN
P1;
P2;
COEND
END.
Diagrama de flujo
Diagrama del proceso 1
Wait(mutex) P1
Bandera1 = verdadero
W
Bandera2 = verdadero
Si
Turno = 2
Bandera1 = falso
W
Turno = 2
Bandera1 = verdadero
Turno = 2
Bandera1 = falso
Seal(mutex)
Diagrama del proceso 2
Wait(mutex) P1
Bandera2 = verdadero
W
Bandera1 = verdadero
Si
Turno = 1
Bandera2 = falso
W
Turno = 1
Bandera2 = verdadero
Turno = 1
Bandera2 = falso
Seal(mutex)
Diagrama principal
Inicio
Bandera1 = falso
Bandera2 = falso
Turno = 1
Signal(mutex)
P1
P2
Fin
IV.
Algoritmo de Dekker implementado con monitores
Algoritmo:
1. Inicio
2. Procedimiento P1
2.1. Bandera 1 = verdadero
2.2. Mientras Bandera2 = verdadero hacer
2.2.1. Si turno = 2 luego
[Link]. Bandera1 = falso
[Link]. Mientras turno = 2 no hacer nada
[Link]. Bandera1 = verdadero
2.2.2. Fin_Si
2.3. Fin_Mientras
2.4. Ejecutar regin critica
2.5. Turno = 2
2.6. Bandera1 = falso
3. Fin_P1
4. Procedimiento P2
4.1. Bandera 2 = verdadero
4.2. Mientras Bandera1 = verdadero hacer
4.2.1. Si turno = 1 luego
[Link]. Bandera2 = falso
[Link]. Mientras turno = 1 no hacer nada
[Link]. Bandera2 = verdadero
4.2.2. Fin_Si
4.3. Fin_Mientras
4.4. Ejecutar regin critica
4.5. Turno = 1
4.6. Bandera2 = falso
5. Fin_P2
6. Definicin de monitor control
6.1. Bandera1 = falso
6.2. Bandera2 = falso
6.3. Turno = 1
7. Fin_monitor
8. Proceso 1
8.1. Repetir
8.1.1. Control.P1
8.2. Para siempre
9. Fin_Proceso1
10. Proceso 2
10.1. Repetir
10.1.1. Control.P2
10.2. Para siempre
11. Fin_Proceso2
12. Iniciar ejecucin concurrente
12.1. Proceso1
12.2. Proceso2
13. Fin_ejecucion concurrente
14. Fin
Cdigo:
Lenguaje de Programacin: Pascal FC
PROGRAM AlgoritmoDeDekker;
monitor control;
export
P1;
P2;
VAR
bandera1, bandera2: boolean;
turno: integer;
PROCEDURE P1;
BEGIN
bandera1 := true;
WHILE bandera2=true DO
BEGIN
IF turno = 2 THEN
BEGIN
bandera1 := false;
WHILE turno = 2 DO null;
bandera1 := true;
END;
END;
(*** Region Critica ***)
writeln('Se ejecuta el proceso 1');
turno := 2;
bandera1 := false;
END;
PROCEDURE P2;
BEGIN
bandera2 := true;
WHILE bandera1 = true DO
BEGIN
IF turno = 1 THEN
BEGIN
bandera2 := false;
WHILE turno = 1 DO;
bandera2 := true;
END;
END;
(*** Region Critica ***)
writeln('Se ejecuta el proceso 2');
turno := 1;
bandera2 := false;
END;
begin
bandera1 := false;
bandera2 := false;
turno := 1;
end;
process proceso1;
begin
REPEAT
control.P1
FOREVER
end;
process proceso2;
begin
REPEAT
control.P2
FOREVER
end;
BEGIN
COBEGIN
proceso1;
proceso2;
COEND
END.
Diagrama de flujo
Diagrama del procedimiento del monitor P1
P1
Bandera1 = verdadero
W
Bandera2 = verdadero
Si
Turno = 2
Bandera1 = falso
W
Turno = 2
Bandera1 = verdadero
Turno = 2
Bandera1 = falso
Diagrama del procedimiento del monitor P2
P2
Bandera2 = verdadero
W
Bandera1 = verdadero
Si
Turno = 1
Bandera2 = falso
W
Turno = 1
Bandera2 = verdadero
Turno = 1
Bandera2 = falso
Diagrama de la definicin del monitor
Monitor
Control
Bandera1 = falso
Bandera2 = falso
Turno = 1
Diagrama de los procesos del algoritmo
Proceso 1
Proceso 2
Control.P1
Control.P2
W
Para Siempre
W
Para Siempre
Diagrama Principal
Inicio
Proceso1
Proceso2
Fin
15. Aplicacin
Problema:
Durante un da festivo en Tacna, llegaron muchos turistas a la ciudad y las
calles se abarrotaron de personas; despus de todo un da de actividades las
personas forneas buscaban un lugar donde dormir ocupando todos los
hoteles de la ciudad, un pequeo hostal de solo 5 habitaciones atenda pero
con una particularidad, solo alquilaba las habitaciones por 2 horas, despus
de ese tiempo los huspedes deban salir y si se queran permanecer en las
instalaciones, tenan que volver a registrarse.
Realizar un algoritmo que simule el funcionamiento de este hostal.
Solucin I:
Para darle solucin a este problema, hice una adaptacin del algoritmo de los
filsofos usando semforos.
Algoritmo:
1. Inicio
2. Definicin de Proceso Proceso(numero)
2.1. Repetir
2.1.1. La habitacin est desocupada
2.1.2. Esperar(librehabitacion)
2.1.3. Esperar(habitacin [numero] )
2.1.4. Esperar(habitacin [ residuo(numero/N) + 1 ] )
2.1.5. La habitacin est ocupada por 2 horas.
2.1.6. Seal(habitacin [numero] )
2.1.7. Seal(habitacin [ residuo(numero/N) + 1 ])
2.1.8. Seal(librehabitacion)
2.2. Para Siempre
3. Para i = 1 hasta N hacer
3.1. Inicializar habitacin[ i ] = 1
4. Fin_Para
5. Inicializar librehabitacion = N - 1
6. Iniciar Ejecucin concurrente.
6.1. Para i=1 hasta N hacer
6.1.1. procesohabitacion [ i ]( i )
6.2. Fin_Para
7. Finalizar ejecucin concurrente
8. Fin
Cdigo
Lenguaje de Programacin: Pascal FC
program Aplicacion;
const
N=5;
var
habitacion : array [1..N] of semaphore; (* Semaforo Binario*)
librehabitacion : semaphore; (* Semaforo *)
I : integer;
process type proceso(numero : integer);
begin
repeat
writeln('Desocupada la habitacion Numero ',numero:2);
sleep(random(2)); (* Tiempo que una habitacion esta
desocupada *)
wait(librehabitacion);
wait(habitacion[numero]);
wait(habitacion[(numero mod N) + 1]);
writeln('Ocupada la habitacin numero ',numero:2);
sleep(2); (* Representa las 2 horas que la habitacion esta
ocupada *)
signal(habitacion[numero]);
signal(habitacion[(numero mod N) + 1]);
signal(librehabitacion)
forever
end;
var
procesohabitacion: array[1..N] of proceso;
begin
for I := 1 to N do
initial(habitacion[I],1);
initial(librehabitacion,N - 1);
cobegin
for I := 1 to N do
procesohabitacion[I](I); (*Este proceso representa
cada habitacion*)
coend
end.
Diagrama de flujo
Definicin del proceso usando semforos:
Proceso(numero)
La habitacin esta desocupada
WAIT(librehabitacion)
WAIT(habitacin [numero] )
WAIT(habitacin [ residuo(numero/N) + 1 ] )
La habitacin est ocupada por 2 horas.
SIGNAL(habitacin [numero] )
SIGNAL(habitacin [ residuo(numero/N) + 1 ])
SIGNAL(librehabitacion)
W
Para Siempre
Diagrama Principal
Inicio
Para i = 1 hasta N
Tenedor[ i ] = 1
Sillas_libres = N - 1
procesohabitacion [1]( 1 )
procesohabitacion [2]( 2 )
procesohabitacion [3]( 3 )
procesohabitacion [4]( 4 )
procesohabitacion [ 5]( 5 )
Fin
Solucin II:
Ahora damos solucin al mismo problema usando monitores.
Algoritmo:
1. Inicio
2. Procedimiento adquirirhabitacin( i )
2.1. Si habitacin[i] 2 luego
i. Habitacin desocupada
ii. Dormir listoparausar[i] segundos
2.2. Fin_Si
2.3. habitacin [ Residuo( ( i+1 )/5 ) ] = habitacin [ Residuo( ( i+1 )/5 ) ] - 1
2.4. habitacin [ Residuo( ( i+4 )/5 ) ] = habitacin [ Residuo( ( i+4 )/5 ) ] - 1
3. Fin_ adquirirhabitacin
4. Procedimiento devolverhabitacin( i )
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
4.1. habitacin [ Residuo( ( i+1 )/5 ) ] = habitacin [ Residuo( ( i+1 )/5 ) ] + 1
4.2. habitacin [ Residuo( ( i+4 )/5 ) ] = habitacin [ Residuo( ( i+4 )/5 ) ] + 1
4.3. Si habitacin [ Residuo( (i+1)/5) ] = 2 luego
4.3.1. Resume(listoparausar [ Residuo( ( i + 1 )/5 ) ] )
4.4. Fin_Si
4.5. Si habitacin [ Residuo( (i+4)/5) ] = 2 luego
4.5.1. Resume(listoparausar [ Residuo( ( i + 4 )/5 ) ] )
4.6. Fin_Si
Fin_ devolverhabitacin
Definicin de monitor habitacionmoni
6.1. Para i = 0 hasta 4 hacer
6.1.1. habitacin [i] = 2
6.2. Fin Para
Fin_ habitacionmoni
Procedimiento uso
8.1. Null
Fin_uso
Procedimiento ocupado (n)
10.1. [Link](n)
10.2. [Link](n)
Fin_ocupado
Definicin de proceso proc_habitacion(n)
12.1. Repetir
12.1.1. uso
12.1.2. ocupado(n)
12.2. Para Siempre
Fin_ proc_habitacion
Iniciar concurrencia
14.1. Para num = 0 hasta 4 hacer
14.1.1. Ppoc_habitacion[num](num)
14.2. Fin_Para
Finalizar concurrencia
Fin.
Cdigo
Lenguaje de Programacin: Pascal FC
program Aplicacion;
const
N=5;
var
j, num: integer;
monitor monihabitacion;
export
adquirirhabitacion,
devolverhabitacion;
var
habitacion: array [0..4] of integer;
listoparausar: array [0..4] of condition;
i: integer;
procedure adquirirhabitacion(i: integer);
begin
if habitacion[i] <> 2 then
begin
writeln('Habitacion ',i:2,' esta desocupada');
delay(listoparausar[i])
end;
habitacion[(i+1) mod N] := habitacion[(i+1) mod N] - 1;
habitacion[(i+4) mod N] := habitacion[(i+4) mod N] - 1;
writeln('Habitacion ',i:2,' ocupada')
end;
procedure devolverhabitacion(i: integer);
begin
writeln('Habitacion ',i:2,' desocupada');
habitacion[(i+1) mod N] := habitacion[(i+1) mod N] + 1;
habitacion[(i+4) mod N] := habitacion[(i+4) mod N] + 1;
if habitacion[(i+1) mod N] = 2 then
resume(listoparausar[(i+1) mod N]);
if habitacion[(i+4) mod N] =2 then
resume(listoparausar[(i+4) mod N])
end;
begin (* cuerpo del monitor *)
for i := 0 to 4 do
habitacion[i] := 2
end; (* monihabitacion *)
procedure uso;
begin
null
end;
procedure ocupado(n: integer);
begin
[Link](n);
sleep(1);
[Link](n)
end;
process type habitacion(n: integer);
begin
repeat
uso;
ocupado(n)
forever
end;
var
prochabitacion: array[0..4] of habitacion;
begin (* principal *)
cobegin
for num := 0 to 4 do
prochabitacion[num](num)
coend
end.
Diagrama de flujo
Diagrama de los procedimientos del monitor
adquirirhabitacion(i)
Si
Habitacin[i]
Habitacin Desocupada
Sleep( listoparausar[i] )
Habitacin[ Residuo( ( i+1 )/5 ) ] = Habitacin[ Residuo( ( i+1 )/5 ) ] - 1
Habitacin[ Residuo( ( i+4 )/5 ) ] = Habitacin[ Residuo( ( i+4 )/5 ) ] - 1
W
Para Siempre
devolverhabitacion(i)
Habitacin[ Residuo( ( i+1 )/5 ) ] = Habitacin[ Residuo( ( i+1 )/5 ) ] + 1
Habitacin[ Residuo( ( i+4 )/5 ) ] = Habitacin[ Residuo( ( i+4 )/5 ) ] + 1
Si
Habitacin[ (i+1) mod 5 ] = 2
Resume( listoparausar[ Residuo( ( i + 1 )/5 ) ] )
Si
Habitacin[ (i+4) mod 5 ] = 2
Resume( listoparausar[ Residuo( ( i + 4 )/5 ) ] )
W
Para Siempre
Diagrama de definicin del monitor
Monitor monihabitacion
Para i = 0 hasta 4
Habitacin[ i ] = 2
Diagrama de otros procedimientos del algoritmo
Procedimiento desocupado(n)
Procedimiento uso
[Link](n)
[Link](n)
NULL
Diagrama de Proceso proc_habt
Definicin de proc_habt
uso
desocupado(n)
W
Para Siempre
Diagrama principal
Inicio
proc_habt [1]( 1 )
proc_habt [2]( 2 )
proc_habt [3]( 3 )
Fin
proc_habt [4]( 4 )
proc_habt[ 5]( 5 )
