• Author / Uploaded
• univer

• Categories
• Algoritmos
• Ciencias de la Información
• Computación concurrente
• Tecnología de sistema operativo
• Concurrencia (informática)

Citation preview

II Examen Parcial de Algoritmos Paralelos Kevin Mike Herrera Vega Código: 2012-36144 Universidad Nacional Jorge Basadre Grohmann – Facultad de ingeniería Algoritmo Paralelos 31 – 07 - 2013 I.

Algoritmo de la cena de los filósofos implementado con semáforos.

Algoritmo: 1. Inicio 2. Definición de Proceso Filósofos(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. Señal( Tenedor[numero] ) 2.1.7. Señal( Tenedor[ residuo(numero/N) + 1 ]) 2.1.8. Señal(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 Ejecución concurrente. 6.1. Para i=1 hasta N hacer 6.1.1. Proc_filosofo[ i ]( i ) 6.2. Fin_Para 7. Finalizar ejecución concurrente 8. Fin

Código: Lenguaje de Programación: 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 Definición del proceso usando semáforos: 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 filósofos 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. Definición 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. Palillomon.getpalillo(n) 10.2. Palillomon.putpalillo(n) 11. Fin_Come 12. Definición 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.

Código: Lenguaje de Programación: 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 palillomon.getpalillo(n); sleep(1); palillomon.putpalillo(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)

V

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

V

Resume( okparacomer[ Residuo( ( i + 1 )/5 ) ] )

Si Palillo[ (i+4) mod 5 ] = 2

V

Resume( okparacomer[ Residuo( ( i + 4 )/5 ) ] )

W Para Siempre

Diagrama de definición del monitor

Monitor palillomon

Para i = 0 hasta 4 Palillo[ i ] = 2

Diagrama de otros procedimientos del algoritmo Procedimiento come(n)

Procedimiento piensa

NULL

Palillomon.getpalillo(n) Palillomon.putpalillo(n)

Diagrama del Proceso Filosofo Definición 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 semáforos

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 2.3.1.1. Bandera1 = falso 2.3.1.2. Mientras turno = 2 no hacer nada 2.3.1.3. Bandera1 = verdadero 2.3.2. Fin_Si 2.4. Fin_Mientras 2.5. Ejecutar región critica 2.6. Turno = 2 2.7. Bandera1 = falso 2.8. Señal(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 4.3.1.1. Bandera2 = falso 4.3.1.2. Mientras turno = 1 no hacer nada 4.3.1.3. Bandera2 = verdadero 4.3.2. Fin_Si 4.4. Fin_Mientras 4.5. Ejecutar región critica 4.6. Turno = 1 4.7. Bandera2 = falso 4.8. Señal(mutex) Fin_P2 Inicializar Señal(mutex) Inicializar Bandera1 = falso Inicializar Bandera2 = falso Inicializar turno = 1 Ejecutar de manera concurrente P1 y P2 Fin

Código: Lenguaje de Programación: 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 Señal(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 Señal(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 2.2.1.1. Bandera1 = falso 2.2.1.2. Mientras turno = 2 no hacer nada 2.2.1.3. Bandera1 = verdadero 2.2.2. Fin_Si 2.3. Fin_Mientras 2.4. Ejecutar región 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 4.2.1.1. Bandera2 = falso 4.2.1.2. Mientras turno = 1 no hacer nada 4.2.1.3. Bandera2 = verdadero 4.2.2. Fin_Si 4.3. Fin_Mientras 4.4. Ejecutar región critica 4.5. Turno = 1 4.6. Bandera2 = falso 5. Fin_P2 6. Definición 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 ejecución concurrente 12.1. Proceso1

12.2. Proceso2 13. Fin_ejecucion concurrente 14. Fin

Código: Lenguaje de Programación: 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 definición 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. Aplicación

Problema: Durante un día festivo en Tacna, llegaron muchos turistas a la ciudad y las calles se abarrotaron de personas; después de todo un día de actividades las personas foráneas buscaban un lugar donde dormir ocupando todos los hoteles de la ciudad, un pequeño hostal de solo 5 habitaciones atendía pero con una particularidad, solo alquilaba las habitaciones por 2 horas, después de ese tiempo los huéspedes debían salir y si se querían permanecer en las instalaciones, tenían que volver a registrarse. Realizar un algoritmo que simule el funcionamiento de este hostal.

Solución I: Para darle solución a este problema, hice una adaptación del algoritmo de los filósofos usando semáforos.

Algoritmo: 1. Inicio 2. Definición de Proceso Proceso(numero) 2.1. Repetir 2.1.1. La habitación está desocupada 2.1.2. Esperar(librehabitacion) 2.1.3. Esperar(habitación [numero] ) 2.1.4. Esperar(habitación [ residuo(numero/N) + 1 ] ) 2.1.5. La habitación está ocupada por 2 horas. 2.1.6. Señal(habitación [numero] ) 2.1.7. Señal(habitación [ residuo(numero/N) + 1 ]) 2.1.8. Señal(librehabitacion) 2.2. Para Siempre 3. Para i = 1 hasta N hacer

3.1. Inicializar habitación[ i ] = 1 4. Fin_Para 5. Inicializar librehabitacion = N - 1 6. Iniciar Ejecución concurrente. 6.1. Para i=1 hasta N hacer 6.1.1. procesohabitacion [ i ]( i ) 6.2. Fin_Para 7. Finalizar ejecución concurrente 8. Fin

Código Lenguaje de Programación: 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 habitación 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 Definición del proceso usando semáforos:

Proceso(numero)

La habitación esta desocupada WAIT(librehabitacion) WAIT(habitación [numero] ) WAIT(habitación [ residuo(numero/N) + 1 ] ) La habitación está ocupada por 2 horas. SIGNAL(habitación [numero] ) SIGNAL(habitación [ 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

Solución II: Ahora damos solución al mismo problema usando monitores.

Algoritmo: 1. Inicio 2. Procedimiento adquirirhabitación( i ) 2.1. Si habitación[i] ≠ 2 luego i. Habitación desocupada ii. Dormir listoparausar[i] segundos 2.2. Fin_Si 2.3. habitación [ Residuo( ( i+1 )/5 ) ] = habitación [ Residuo( ( i+1 )/5 ) ] - 1 2.4. habitación [ Residuo( ( i+4 )/5 ) ] = habitación [ Residuo( ( i+4 )/5 ) ] - 1 3. Fin_ adquirirhabitación 4. Procedimiento devolverhabitación( i )

5. 6.

7. 8. 9. 10.

11. 12.

13. 14.

15. 16.

4.1. habitación [ Residuo( ( i+1 )/5 ) ] = habitación [ Residuo( ( i+1 )/5 ) ] + 1 4.2. habitación [ Residuo( ( i+4 )/5 ) ] = habitación [ Residuo( ( i+4 )/5 ) ] + 1 4.3. Si habitación [ Residuo( (i+1)/5) ] = 2 luego 4.3.1. Resume(listoparausar [ Residuo( ( i + 1 )/5 ) ] ) 4.4. Fin_Si 4.5. Si habitación [ Residuo( (i+4)/5) ] = 2 luego 4.5.1. Resume(listoparausar [ Residuo( ( i + 4 )/5 ) ] ) 4.6. Fin_Si Fin_ devolverhabitación Definición de monitor habitacionmoni 6.1. Para i = 0 hasta 4 hacer 6.1.1. habitación [i] = 2 6.2. Fin Para Fin_ habitacionmoni Procedimiento uso 8.1. Null Fin_uso Procedimiento ocupado (n) 10.1. habitacionmoni.adquirirhabitacion(n) 10.2. habitacionmoni.devolverhabitacion(n) Fin_ocupado Definición 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.

Código Lenguaje de Programación: 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 monihabitacion.adquirirhabitacion(n); sleep(1); monihabitacion.devolverhabitacion(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

V

Habitación[i]

2

Habitación Desocupada Sleep( listoparausar[i] )

Habitación[ Residuo( ( i+1 )/5 ) ] = Habitación[ Residuo( ( i+1 )/5 ) ] - 1 Habitación[ Residuo( ( i+4 )/5 ) ] = Habitación[ Residuo( ( i+4 )/5 ) ] - 1

W Para Siempre

devolverhabitacion(i)

Habitación[ Residuo( ( i+1 )/5 ) ] = Habitación[ Residuo( ( i+1 )/5 ) ] + 1 Habitación[ Residuo( ( i+4 )/5 ) ] = Habitación[ Residuo( ( i+4 )/5 ) ] + 1

Si Habitación[ (i+1) mod 5 ] = 2

V

Resume( listoparausar[ Residuo( ( i + 1 )/5 ) ] )

V

Si Habitación[ (i+4) mod 5 ] = 2

Resume( listoparausar[ Residuo( ( i + 4 )/5 ) ] )

W Para Siempre

Diagrama de definición del monitor Monitor monihabitacion

Para i = 0 hasta 4 Habitación[ i ] = 2

Diagrama de otros procedimientos del algoritmo Procedimiento desocupado(n)

Procedimiento uso monihabitacion.adquirirhabitacion(n) monihabitacion.devolverhabitacion(n)

NULL

Diagrama de Proceso proc_habt Definición 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 )