Práctica Programación Concurrente (Sistemas Operativos)

Ejercicio 1

/ Instrucciones Conj. Lectura Conj. Escritura S1 a = b+c R(S1) = {b,c} W(S1) = {a} S2 d = b+e R(S2) = {b,e} W(S2) = {d} S3 f = c+e R(S3) = {c,e} W(S3) = {f} S4 g = fun1[a,d,f] R(S4) = {a,d,f} W(S4) = {g} S5 f = sen[w] R(S5) = {w} W(S5) = {f}

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 S3,
S2 y S5

Ejercicio 2*

a)

	    Count5 = Count6 = 2

	    s1 
	    fork L1 
	    fork L2 
	    s2 
	    goto L3
	L2: s3
	L3: join Count5
	    s5
	    goto L4
	L1: s4
        L4: join Count6
            S6

b)

	s1 
	parbegin 
		begin 
			parbegin 
				s2 
				s3 
			parend 
			s5 
		end 
		s4 
	parend 
	s6 

Ejercicio 3*

La instrucción Join debe ser atómica ya que mantiene una cuenta de cuantos procesos esta esperando, y si no fuera atómica, podría funcionar mal, y por ejemplo "matar" a, los dos o mas procesos que tenían que unirse ahi.
La definición de join var es:
1 ) var - - ;
2 ) if (var =! 0) then wait;
si justo es interrumpida después de 1) y antes de 2) y para ejecutar otro join con la misma variable. supongamos que var valia 0, y ahora se decrementa y pasa a varler -1, chau tu programa queda en wait para siempre.

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 </br>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 </br>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</br> 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
		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

b)

	Procedure Pi
	Do
		while(TestAndSet(lock));
		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.
Solucion de Andy:

x=1, y=0, gentelado1=gentelado2=0

Proc CruzarLado1
P(exc)
	P(X)
	gentelado1++
V(exc)
cruzar
P(exc)
	gentelado1--
	if (gentelado2>0 || gentelado1==0)
		V(Y)
	else
		V(X)
	endif
V(exc)

Proc CruzarLado2
P(exc)
	P(Y)
	gentelado2++
V(exc)
cruzar
P(exc)
	gentelado2--
	if (gentelado1>0 || gentelado2==0)
		V(X)
	else
		V(Y)
	endif
V(exc)

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)
		CantLectores--
		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)

x = 1, sentido = izq, autosizq  = ?, autosder = ?
Proc Cruzar
if (sentido == izq)
	if (autosizq > 0)
		P(x)
		cruzar
		V(x)
		P(exc)
		if (--autosizq == 0)
			sentido = der
		V(exc)
	else
		sentido = der
		actualiza(autos)
	endif
elseif (sentido == der)
	if (autosder > 0)
		P(x)
		cruzar
		V(x)
		P(exc)
		if (--autosder == 0)
			sentido = izq
		V(exc)
	else
		sentido = izq
		actualiza(autos)
	endif
endif

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*

	Monitor SuperTormino

	Var:	ocupado :boolean;
		no_ocupado :condition;

	Procedure	Cliente
	Begin
		if ocupado then wait(no_ocupado);
		ocupado = V;
	End

	Procedure	Balanza
	Begin
		ocupado = F;
		pesar
		signal(no_ocupado);
	End

	Begin Monitor
		ocupado = F;
	End

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.