Práctica Programación Concurrente (Sistemas Operativos)
Ejercicio 1
|
Condiciones de Bernstein: R(Si) n W(Sj) = W(Si) n R(Sj) = W(Si) n W(Sj) = {}
Se pueden ejecutar concurrentemente S1 y S2, S1 y S3, S1 y S5, S2 y S5
Ejercicio 2*
a)
Count5 = Count6 = 2 s1 fork L3 fork L4 s2 jump Join5 L3: s3 jump Join5 Join5: join Count5 s5 jump Join6 L4: s4 jump Join6 Join6: join Count6 S6
b)
s1 parbegin begin parbegin s2 s3 parend s5 end s4 parend s6
Ejercicio 3*
La instruccion Join es indivisible porque debe ser atomica. Es decir, no puede ser interrumpida a la mitad. Esto es necesario ya que join mantiene una cuenta de cuantos procesos esta esperando, y si no fuera atomica, podria funcionar mal, y por ejemplo "matar" a todos los dos o mas procesos que tenian que unirse ahi.
Ejercicio 4*
a) Es el tipo de grafos que no pueden ser representados con parbegin/parend, ya que no se puede dividirlo en subgrafos disjuntos concurrentes.
b)
var a,b,c,d,e,f,g,h: semaforo; init(todos,0); Parbegin Begin S1;V(a);V(b);V(c); End Begin P(a);S2;V(d);V(e); End Begin P(b);S3;V(f); End Begin P(c);S4;V(h); End Begin P(d);P(f);S5;V(e); End Begin P(g);P(h);S6:End Parend
Ejercicio 5
a) Aca lo tienen:
__S1__ / | \ S2 S3 S4 \ / | S5 S6 \ / S7
b) Se puede construir el grafo de manera "secuencial", es decir, S1-S2-S3-S5-S4-S6-S7 (Claramente no tiene el mayor grado de concurrencia posible).
O simplemente basta con borrar algun Parbegin con su Parend correspondiente y decir que las instrucciones que habia en medio se podrian haber ejecutado concurrentemente.
c)
Count5 = Count7 = 2 S1 fork L3 fork L4 S2 jump Join5 L3: S3 jump Join5 L4: S4 S6 jump Join7 Join5: join Count5 S5 jump Join7 Join7: join Count7 S7
Ejercicio 6
a) Si no lo hice mal, es una cosa mas o menos asi:
S1 ____________ / | \ S2 S3 S7 \ / / \ S4 S8 S9 / \ | | S5 S6 S10 | \ / \ / (x1) (x2) \_________/ S11
b)
s1 parbegin begin parbegin s2 s3 parend s4 parbegin s5 s6 parend (x1) end begin s7 parbegin begin s8 s10 end s9 parend (x2) end parend s11
c) S1, S7, S8 (porque son los unicos de los que depende S10)
Ejercicio 7
(NOTA PARA EJS 7-11) PREMISAS DE DIJKSTRA: 1) No deben hacerse suposiciones sobre las instrucciones de máquina ni la cantidad de procesadores. Sin embargo, se supone que las instrucciones de máquina (Load, Store, Test) son ejecutadas atómicamente, o sea que si son ejecutadas simultáneamente el resultado es equivalente a su ejecución secuencial en un orden desconocido. 2) No deben hacerse suposiciones sobre la velocidad de los procesos. 3) Cuando un proceso no está en su región crítica no debe impedir que los demás ingresen a su región crítica. 4) La decisión de qué procesos entran a una parte crítica no puede ser pospuesta indefinidamente. Los puntos 3) y 4) evitan bloqueos mutuos. 5) Debe existir un límite al número de veces que otros procesos están habilitados a entrar a secciones críticas después que un proceso haya hecho su pedido.
Similar al Alg. 2, no se asegura que un solo proceso este en la zona critica, ej:
T0 Tarea1 encuentra C2 = 1, T1 Tarea2 encuentra C1 = 1, T2 Tarea2 pone C2 = 0, T3 Tarea1 pone C1 = 0
Ejercicio 8
Similar al Alg. 3, no cumple 4) ya que ambos procesos pueden quedar en espera indefinida, ej: T0 Tarea1 encuentra C1 = 0, T1 Tarea2 encuentra C2 = 0
Ejercicio 9
Similar al Alg. 4, no cumple 4) ya que ambos procesos pueden quedar en espera indefinida (por el while)
Ejercicio 10
No cumple 4), ya que si no hace el while suficientemente rapido siempre entra el proceso i en vez de j.
Ejercicio 11
Creo que podrian ser asi (cualquier cosa corrijan):
a)
Procedure Pi Do while(TestAndSet(lock)); seccion critica lock = F; seccion no critica End Begin Main lock = F; Parbegin P0;P1;...;Pn Parend End
b)
Procedure Pi Do key = T; while(key) Swap(lock, key); seccion critica lock = F; seccion no critica End Begin Main lock = F; Parbegin P0;P1;...;Pn Parend End
Ejercicio 12*
Porque como cambian el valor del semaforo y despues lo evalua, al haber concurrencia se pueden quedar en WAIT dos ejecuciones de P. Ver Test-And-Set
Ejercicio 13
Si alguien llega al puente, y no hay nadie esperando de ninguno de los dos lados, se lo pone a cruzar. Si hay alguien cruzando o esperando, y alguien llega, esa persona espera. Cuando una persona termina de cruzar el puente, si hay alguien esperando del lado que llego, le dice che, ahora cruza vos. Y si no, mira para atras, y si del otro lado hay alguien esperando para cruzar le grita cheeeeeeeeeee cruza vooooooooosss.
Ejercicio 14*
Monitor ej14 var: bandera : condicion procedure P(x) begin x = x-1 if (x<0) then Wait(bandera) endif end procedure V(x) begin x = x+1 if (x<=0) then Signal(Bandera) endif end
(Ver pag 19 al final)
Ejercicio 15*
a)
E = 1; S = 0 procedure Productor begin P(E) .... V(S) end procedure Consumidor begin P(S) .... V(E) end
b)
programa Productor_Consumidor; MAX = ......; Monitor M; var: buffer : Array (0..MAX-1); in, out, n; enteros; buff_lleno, buff_vacío: condición; procedure Almacenar (v); begin if n = MAX then Wait (buff_vacío); buffer (in) = v; in = (in + 1) mod MAX; n = n + 1; Signal (buff_lleno) end; procedure Retirar (v); begin if n = 0 then Wait (buff_lleno); v = buffer (out); out = (out + 1) mod MAX; n = n - 1; Signal (buff_vacio) end; begin (* Cuerpo del monitor *) in, out, n = 0; end; (* fin monitor *) procedure Productor; begin v = "dato producido" Almacenar (v) end; procedure Consumidor; begin Retirar (v); Hacer algo con v end; begin Programa-Principal Begin; cobegin Productor; Consumidor coend end.
Ejercicio 16*
La idea es que cuando hay alguien escribiendo no puede haber nadie leyendo. (Multiples Lectores, un solo escritor)
Escr = 1 procedure Leer begin P(X) CantLectores++ if (CantLectores == 1) then P(Escr) V(X) //leo el archivo P(X) if (CantLectores == 0) then V(Escr) V(X) end procedure Escribir begin P(Escr) //escribo el archivo V(Escr) end begin Prog-Principal(operacion) if (operacion == "Leer") then Leer else Escribir endif end
Ejercicio 17
(Hay que darle prioridad a un solo lado del puente)
Ejercicio 18
a)
// en este esquema cualquiera de los dos puede entrar primero, si entra deshabilita al otro el acceso: x=1 Procedure Romanos Begin P(x) ..... V(x) End Procedure Egipcios Begin P(x) ..... V(x) End Do forever Parbegin Egipcio;Romanos End
b)
x=1 colaegipcios=0 w=1-colaegipcios Procedure Romanos Begin P(excl)//este semaforo no se si hace falta, hay que analizarlo P(w) P(x) V(excl) ..... P(excl) V(x) V(w) P(excl) End Procedure Egipcios Begin P(excl) // en esta parte incremento la cola, que hace que w sea negativo y los romanos se queden esperando V(colaegipcios) P(x) P(excl) ....... P(excl) V(x) P(colaegipcios) P(excl) End Do forever Parbegin Egipcios Romanos End
Esta es otra forma (Cortesia Papa Noel)
CantEgipcios = 0 Procedure Romanos If (CantEgipcios > 0) then P(X) .... V(X) End Procedure Egipcios CantEgipcios++ If (CantEgipcios > 0) then P(X) P(Y) .... V(Y) CantEgipcios-- If (CantEgipcios == 0) then V(X) End
c)
Ejercicio 19*
Monitor PeruanosLocos var: HayCarretilla: Boolean CintaOcupada, CintaLibre : condition Procedure CargarCarretilla Begin If (HayCarretilla) then wait(CintaLibre) HayCarretilla = true Signal(CintaOcupada) End Procedure RetirarCarretilla Begin If (!HayCarretilla) then wait(CintaOcupada) HayCarretilla = false Signal(CintaLibre) End Begin Body HayCarretilla = false End End Monitor Procedure ObreroCargador Begin CargarCarretilla End Procedure ObreroRetirador Begin RetirarCarretilla End Begin Main Parbegin ObreroCargador ObreroRetirador Parend End
Ejercicio 20
La b) ya que siempre uno llega primero y "espera" y el otro sigue de largo.
La c) tambien, por la misma razon.
Ejercicio 21*
Monitor Lectores-Escritores var lectores : integer escribiendo : boolean sePuedeLeer, sePuedeEscribir : condition; Procedure Inicio_Lectores if (escribiendo or novacio (sePuedeEscribir)) wait(sePuedeLeer) endif lectores ++; signal(sePuedeLeer); end Procedure Fin_Lectores lectores - - if (lectores = 0 ) signal(sePuedeEscribir); endif end Procedure Inicio_Escritores if (lectores <> 0 or escribiendo) wait(sePuedeEscribir) endif escribiendo := TRUE end Procedure Fin_Escritores escribiendo := FALSE; if (novacio (sePuedeLeer)) signal(sePuedeLeer) else signal(sePuedeEscribir) end Begin Monitor lectores = 0 escribiendo = FALSE End Procedure LECTOR Do Forever Inicio_Lectores; //Leer Fin_Lectores; End End
Ejercicio 22*
(Tendria que salir con Lectores-Escritores)
Ejercicio 23*
Porque estamos diciendo que se puede ejecutar en paralelo:
a = b + c y
e = a / b + n * n
y no es lo mismo ejecutarlas en paralelo, que en forma secuencial ya que la 2nda instruccion tiene una dependencia de datos con la primera.