Edición de «Práctica Programación Concurrente (Sistemas Operativos)»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.

Revisión actual Tu texto
Línea 1: Línea 1:
{{Back|Sistemas Operativos}}
==Ejercicio 01:==
 
<br>||S1 a = b+c ||R(S1) = {b,c} ||W(S1) = {a} ||
===Ejercicio 1===
<br>||S2 d = b+e ||R(S2) = {b,e} ||W(S2) = {d} ||
 
<br>||S3 f = c+e ||R(S3) = {c,e} ||W(S3) = {f} ||
{| class="wikitable" style="text-align:center"
<br>||S4 g = fun1[a,d,f] ||R(S4) = {a,d,f} ||W(S4) = {g} ||
|
<br>||S5 f = sen[w] ||R(S5) = {w} ||W(S5) = {f} ||
{| border="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}
|-
|}
|}
 
<br>Condiciones de Bernstein: R(Si) n W(Sj) = W(Si) n R(Sj) = W(Si) n W(Sj) = {}  
<br>Condiciones de Bernstein: R(Si) n W(Sj) = W(Si) n R(Sj) = W(Si) n W(Sj) = {}  
<br>Se pueden ejecutar concurrentemente:
<br>Se pueden ejecutar concurrentemente S1 y S2, S1 y S3, S1 y S5, S2 y S5  
<br>S1 y S2,  
<br>S1 y S3,  
<br>S1 y S5,  
<br>S2 y S3,
<br>S2 y S5
 
===Ejercicio 2*===
a)
<pre>
    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
</pre>
b)
<pre>
s1
parbegin
begin
parbegin
s2
s3
parend
s5
end
s4
parend
s6
 
</pre>
 
===Ejercicio 3*===
<br>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.
<br>
<br>
La definición de ''' join var''' es:
==Ejercicio 02:[*]==
<br>a)
<br> count2 = 2
<br> count = 3
<br> s1
<br> fork L2
<br> fork L3
<br> fork L4
<br> jump Sigo
<br> L2:
<br> s2
<br> jump Sigo2
<br> L3:
<br> s3
<br> Sigo2:
<br> join count2
<br> jump Sigo
<br> L4:
<br> s4
<br> Sigo:
<br> join count
<br>
<br>
1 ) var - - ;
<br>b)
<br> s1
<br> parbegin
<br> begin
<br> parbegin
<br> s2
<br> s3
<br> parend
<br> s5
<br> end
<br> s4
<br> parend
<br> s6
<br>
<br>
2 ) if (var =! 0) then wait;
==Ejercicio 03:[*]==
<br>Que es indivisible? --> Indivisible es que es atomica. Que 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.
<br>
<br>
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
==Ejercicio 04:[*]==
tu programa queda en wait para siempre.
<br>a) Me parece que es el tipo de grafos que no pueden ser representados con parbegin/parend. PREGUNTAR
 
<br>b) PREGUNTAR ESTO TB
<br>
<br>
 
==Ejercicio 05:==
===Ejercicio 4*===
<br>a) Agarramos el grafo de antes, sacamos la flecha de S5 a S6 y ponemos una flecha de S5 a S7, de S6 a S7 y de S4 a S7...
<br>a) Es el tipo de grafos que no pueden ser representados con parbegin/parend, ya que no se puede dividirlo en subgrafos disjuntos concurrentes.
<br>b)  
<br>b)  
<pre>
<br>
var a,b,c,d,e,f,g,h: semaforo;
==Ejercicio 06:==
init(todos,0);
<br>a)
 
<br>b)
Parbegin
<br>
Begin S1;V(a);V(b);V(c); End
<br>NOTA: Ejercicios del 7 al 10. Preguntar estos... Tienen pinta de entrar seguro :)  
Begin P(a);S2;V(d);V(e); End
<br>
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
 
</pre>
 
===Ejercicio 5===
<br>a) Aca lo tienen:
<pre>
 
  __S1__
/  |  \
S2  S3  S4
\  /    |
  S5    S6
    \  /
    S7
 
</pre>
<br>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.
<br>c)
<pre>
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
</pre>
 
===Ejercicio 6===
a) Si no lo hice mal, es una cosa mas o menos asi:
<pre>
S1
    ____________
  /    |      \
S2      S3    S7
  \    /      /  \
    S4      S8  S9
  /    \    |    |
S5    S6  S10    |
  \    /    \    /
  (x1)      (x2)
    \_________/
        S11
</pre>
b)
<pre>
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
</pre>
c) S1, S7, S8 (porque son los unicos de los que depende S10)


===Ejercicio 7===
==(NOTA: PREMISAS DE DIJKSTRA:)==


<pre>
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.
(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.
2) No deben hacerse suposiciones sobre la velocidad de los procesos.
Línea 208: Línea 72:
4) La decisión de qué procesos entran a una parte crítica no puede ser pospuesta indefinidamente.
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.
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.
</pre>


Similar al Alg. 2, no se asegura que un solo proceso este en la zona critica, ej:
5)- Debe existir un límite al número de veces que otros procesos están habilitados a entrar a secciones críticas
<br> T0 Tarea1 encuentra C2 = 1,<br>  T1 Tarea2 encuentra C1 = 1,<br>  T2 Tarea2 pone C2 = 0,<br>  T3 Tarea1 pone C1 = 0
después que un proceso haya hecho su pedido.


===Ejercicio 8===
==Ejercicio 07:==
Similar al Alg. 3, no cumple 4) ya que ambos procesos pueden quedar en espera indefinida, ej:
<br>
<br> T0 Tarea1 encuentra C1 = 0,<br>  T1 Tarea2 encuentra C2 = 0


===Ejercicio 9===
==Ejercicio 08:==
Similar al Alg. 4, no cumple 4) ya que ambos procesos pueden quedar en espera indefinida (por el while)
<br>
 
==Ejercicio 09:==
===Ejercicio 10===
<br>
<br> No cumple 4), ya que si no hace el while suficientemente rapido siempre entra el proceso i en vez de j.
==Ejercicio 10:==
 
<br>
===Ejercicio 11===
==Ejercicio 11:==
Creo que podrian ser asi (cualquier cosa corrijan):
<br>a)
<br>a)
<pre>
<br>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
</pre>
<br>
<br>
<br>b)
==Ejercicio 12:[*]==
<pre>
Procedure Pi
Do
while(TestAndSet(lock));
seccion critica
lock = F;
seccion no critica
End
 
Begin Main
lock = F;
Parbegin
P0;P1;...;Pn
Parend
End
</pre>
 
===Ejercicio 12*===
<br>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  
<br>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  
<br>
<br>
===Ejercicio 13===
==Ejercicio 13:==
<br>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.  
<br>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.  
<br> Solucion de Andy:
<br>
<pre>
==Ejercicio 14:[*]==
x=1, y=0, gentelado1=gentelado2=0
<br> Monitor ej14
 
<br> var: bandera : condicion
Proc CruzarLado1
<br>
P(exc)
<br> procedure P(x)  
P(X)
<br> begin
gentelado1++
<br> x = x-1
V(exc)
<br> if (x<0) then
cruzar
<br> Wait(bandera)  
P(exc)
<br> endif
gentelado1--
<br> end
if (gentelado2>0 || gentelado1==0)
<br>
V(Y)
<br> procedure V(x)  
else
<br> begin
V(X)
<br> x = x+1
endif
<br> if (x<=0) then
V(exc)
<br> Signal(Bandera)  
 
<br> endif
Proc CruzarLado2
<br> end
P(exc)
<br>
P(Y)
<br>ver pag 19 al final
gentelado2++
<br>
V(exc)
==Ejercicio 15:[*]==
cruzar
<br>a)
P(exc)
<br> E = 1; S = 0
gentelado2--
<br>
if (gentelado1>0 || gentelado2==0)
<br> procedure Productor
V(X)
<br> begin
else
<br> P(E)  
V(Y)
<br> ....
endif
<br> V(S)  
V(exc)
<br> end  
</pre>
<br>
 
<br> procedure Consumidor
===Ejercicio 14*===
<br> begin  
<pre>
<br> P(S)  
Monitor ej14
<br> ....
var: bandera : condicion
<br> V(E)  
 
<br> end
procedure P(x)  
<br>
begin
<br>b)
x = x-1
<br>Esta el mismo Ejercicio en la pagina 19 del capitulo 19.
if (x<0) then
<br>
Wait(bandera)
==Ejercicio 16:[*]==
endif
<br>[Diego Edit: esta mal. La idea es que cuando hay alguien escribiendo no puede haber nadie leyendo. Lo hicieron en clase a este programa [Multiples Lectores, un solo escritor]. ]
end  
<br>
 
<br> X = 1
procedure V(x)
<br>
begin  
<br> procedure Leer
x = x+1
<br> begin  
if (x<=0) then
<br> //leo el archivo
Signal(Bandera)
<br> end  
endif
<br>
end
<br> procedure Escribir
 
<br> begin
</pre>
<br> P(X)  
(Ver pag 19 al final)
<br> //escribo el archivo
 
<br> V(X)
===Ejercicio 15*===
<br> end
a)
<br>
<pre>
<br> begin Prog-Principal(operacion)  
E = 1; S = 0
<br> if (operacion == "Leer") then
 
<br> Leer
procedure Productor
<br> else
begin
<br> Escribir
P(E)
<br> endif
....
<br> end
V(S)
<br>
end
==Ejercicio 17:==
 
<br>
procedure Consumidor
==Ejercicio 18:==
begin  
<br>a)
P(S)
<br> // en este esquema cualquiera de los dos puede entrar primero, si entra deshabilita al otro el acceso:
....
<br> x=1
V(E)
<br> Procedure Romanos
end  
<br> Begin
</pre>
<br> P(x)
 
<br> .....
b)
<br> V(x)
<pre>
<br> End
programa Productor_Consumidor;
<br> Procedure Egipcios
MAX = ......;
<br> Begin
 
<br> P(x)
Monitor M;
<br> .....
var: buffer : Array (0..MAX-1);
<br> V(x)
in, out, n; enteros;
<br> End
buff_lleno, buff_vacío: condición;
<br> Do forever
<br> Parbegin
procedure Almacenar (v);
<br> Egipcio;Romanos
begin
<br> End
if n = MAX then Wait (buff_vacío);
<br>
buffer (in) = v;
<br>b)
in = (in + 1) mod MAX;
<br> x=1
n = n + 1;
<br> colaegipcios=0
Signal (buff_lleno)
<br> w=1-colaegipcios
end;
<br> Procedure Romanos
<br> Begin
procedure Retirar (v);
<br> P(excl)//este semaforo no se si hace falta ay que analizarlo
begin
<br> P(w)
if n = 0 then Wait (buff_lleno);
<br> P(x)
v = buffer (out);
<br> V(excl)
out = (out + 1) mod MAX;
<br> .....
n = n - 1;
<br> P(excl)
Signal (buff_vacio)
<br> V(x)
end;
<br> V(w)
<br> P(excl)
begin (* Cuerpo del monitor *)
<br>
in, out, n = 0;
<br> End
end; (* fin monitor *)
<br> Procedure Egipcios
<br> Begin
procedure Productor;
<br> P(excl)
begin
<br> // en esta parte incremento la cola, que hace que w sea negativo y los romanos se queden esperando
v = "dato producido"
<br> V(colaegipcios)
Almacenar (v)
<br> P(x)
end;
<br> P(excl)
<br> .......
procedure Consumidor;
<br> P(excl)
begin
<br> V(x)
Retirar (v);
<br> P(colaegipcios)
Hacer algo con v
<br> P(excl)
end;
<br>
<br> End
begin Programa-Principal
<br> Do forever
Begin;
<br> Parbegin
cobegin
<br> Egipcios
Productor;
<br> Romanos
Consumidor
<br> End
coend
<br>c)
end.
<br>
</pre>
==Ejercicio 19:[*]==
 
<br> Monitor PeruanosLocos
===Ejercicio 16*===
<br> var: HayCarretilla: Boolean
La idea es que cuando hay alguien escribiendo no puede haber nadie leyendo. (Multiples Lectores, un solo escritor)
<br> CintaOcupada, CintaLibre : condition
<pre>
<br>
Escr = 1
<br> Procedure CargarCarretilla
 
<br> Begin
procedure Leer
<br> If (HayCarretilla) then
begin
<br> wait(CintaLibre)
P(X)
<br> HayCarretilla = true
CantLectores++
<br> Signal(CintaOcupada)
if (CantLectores == 1) then P(Escr)
<br> End
V(X)
<br>
//leo el archivo
<br> Procedure RetirarCarretilla
P(X)
<br> Begin
CantLectores--
<br> If (!HayCarretilla) then
if (CantLectores == 0) then V(Escr)
<br> wait(CintaOcupada)
V(X)
<br> HayCarretilla = false
end
<br> Signal(CintaLibre)
<br> End
procedure Escribir
<br>
begin
<br> Begin Body
P(Escr)  
<br> HayCarretilla = false
//escribo el archivo
<br> End
V(Escr)
<br>
end
<br> End Monitor
<br>
begin Prog-Principal(operacion)  
<br> Procedure ObreroCargador
if (operacion == "Leer") then
<br> Begin
Leer
<br> CargarCarretilla
else
<br> End
Escribir
<br>
endif
<br> Procedure ObreroRetirador
end
<br> Begin
 
<br> RetirarCarretilla
</pre>
<br> End
 
<br>
===Ejercicio 17===
<br> Begin Main
<br> (Hay que darle prioridad a un solo lado del puente)
<br> Parbegin
<pre>
<br> ObreroCargador
x = 1, sentido = izq, autosizq  = ?, autosder = ?
<br> ObreroRetirador
Proc Cruzar
<br> Parend
if (sentido == izq)
<br> End
if (autosizq > 0)
<br>
P(x)
==Ejercicio 20:==
cruzar
<br>La b). Ya que siempre uno llega primero y "espera" y el otro sigue de largo. La c tambien. Por la misma razon.
V(x)
<br>
P(exc)
==Ejercicio 21:[*]==
if (--autosizq == 0)
<br>Ni idea que quieren
sentido = der
<br>
V(exc)
==Ejercicio 22:[*]==
else
<br>Estoy harto de esos ejercicios que te meten enunciados al pedo== ==
sentido = der
<br>
actualiza(autos)
==Ejercicio 23:[*]==
endif
<br>Por que estamos diciendo que se puede ejecutar en paralelo:
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
</pre>
 
===Ejercicio 18===
a)
<pre>
// 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
</pre>
 
b)
<pre>
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
</pre>
Esta es otra forma (Cortesia Papa Noel)
<pre>
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
</pre>
c)
 
===Ejercicio 19*===
<pre>
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
 
</pre>
 
===Ejercicio 20===
<br>La b) ya que siempre uno llega primero y "espera" y el otro sigue de largo.
<br>La c) tambien, por la misma razon.
 
===Ejercicio 21*===
<pre>
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
</pre>
 
===Ejercicio 22*===
<pre>
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
</pre>
 
===Ejercicio 23*===
<br>Porque estamos diciendo que se puede ejecutar en paralelo:
<br>a = b + c  y
<br>a = b + c  y
<br>e = a / b + n * n
<br>e = a / b + n * n
<br>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.  
<br>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.  
<br>
<br>
[[Category:Prácticas]]
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantilla usada en esta página:

Obtenido de «https://www.cubawiki.com.ar/index.php/Práctica_Programación_Concurrente_(Sistemas_Operativos)»