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: ==


===Ejercicio 1===
== Ejercicio 02: ==  


{| class="wikitable" style="text-align:center"
a.
|
count2 = 2
{| 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) = {}
count = 3
<br>Se pueden ejecutar concurrentemente:
<br>S1 y S2,
<br>S1 y S3,
<br>S1 y S5,
<br>S2 y S3,
<br>S2 y S5


===Ejercicio 2*===
s1
a)
<pre>
    Count5 = Count6 = 2


    s1
fork L2
    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>
fork L3


===Ejercicio 3*===
fork L4
<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>
La definición de ''' join var''' es:
<br>
1 ) var - - ;
<br>
2 ) if (var =! 0) then wait;
<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
tu programa queda en wait para siempre.


<br>
jump Sigo


===Ejercicio 4*===
L2:
<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)
<pre>
var a,b,c,d,e,f,g,h: semaforo;
init(todos,0);


Parbegin
s2
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


</pre>
jump Sigo2


===Ejercicio 5===
L3:
<br>a) Aca lo tienen:
<pre>


  __S1__
s3
/  |  \
S2  S3  S4
\  /    |
  S5    S6
    \  /
    S7


</pre>
Sigo2:
<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
join count2
fork L3
 
fork L4
jump Sigo
S2
 
jump Join5
L4:
 
s4
 
Sigo:
 
join count
 
 
b.
 
s1
 
parbegin
 
begin
 
parbegin
 
s2


L3:
s3
S3
jump Join5


L4:
parend
S4
S6
jump Join7


Join5:
s5
join Count5
S5
        jump Join7


Join7:
end
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
s4
parbegin
s5
s6
parend
(x1)
end


begin
parend
s7
 
parbegin
s6
 
 
 
== Ejercicio 03: ==
 
Que es indivisible?
 
 
 
== Ejercicio 04: ==
 
a. Me parece que es el tipo de grafos que no pueden ser representados con parbegin/parend. PREGUNTAR
 
 
 
== Ejercicio 05: ==
 
 
 
== Ejercicio 06: ==
 
 
 
== Ejercicio 07: ==
 
 
 
== Ejercicio 08: ==
 
 
 
== Ejercicio 09: ==
 
 
 
== Ejercicio 10: ==
 
 
 
== Ejercicio 11: ==
 
 
 
 
 
== 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 Set-And-Test
 
 
 
== Ejercicio 13: ==
 
 
 
 
 
== 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
begin
s8
 
s10
x = x+1
 
if (x<=0) then
 
Signal(Bandera)
 
endif
 
end
end
s9
parend
(x2)
end
parend
s11
</pre>
c) S1, S7, S8 (porque son los unicos de los que depende S10)


===Ejercicio 7===


<pre>
(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.
== Ejercicio 15: ==


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.
a.


4) La decisión de qué procesos entran a una parte crítica no puede ser pospuesta indefinidamente.
E = 1; S = 0
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:
<br> T0 Tarea1 encuentra C2 = 1,<br>  T1 Tarea2 encuentra C1 = 1,<br>  T2 Tarea2 pone C2 = 0,<br>  T3 Tarea1 pone C1 = 0


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


===Ejercicio 9===
begin
Similar al Alg. 4, no cumple 4) ya que ambos procesos pueden quedar en espera indefinida (por el while)


===Ejercicio 10===
P(E)
<br> 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):
<br>a)
<pre>
Procedure Pi
Do
key = T;
while(key)
Swap(lock, key);
seccion critica
lock = F;
seccion no critica
End


Begin Main
V(S)
lock = F;
Parbegin
P0;P1;...;Pn
Parend
End
</pre>
<br>
<br>b)
<pre>
Procedure Pi
Do
while(TestAndSet(lock));
seccion critica
lock = F;
seccion no critica
End


Begin Main
end
lock = F;
 
Parbegin
P0;P1;...;Pn
Parend
End
</pre>


===Ejercicio 12*===
procedure Consumidor
<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>
===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> Solucion de Andy:
<pre>
x=1, y=0, gentelado1=gentelado2=0


Proc CruzarLado1
begin
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(S)
P(exc)
P(Y)
gentelado2++
V(exc)
cruzar
P(exc)
gentelado2--
if (gentelado1>0 || gentelado2==0)
V(X)
else
V(Y)
endif
V(exc)
</pre>


===Ejercicio 14*===
....
<pre>
Monitor ej14
var: bandera : condicion


procedure P(x)  
V(E)
begin
x = x-1
if (x<0) then
Wait(bandera)
endif
end


procedure V(x)
end
begin
x = x+1
if (x<=0) then
Signal(Bandera)
endif
end  


</pre>
(Ver pag 19 al final)


===Ejercicio 15*===
a)
<pre>
E = 1; S = 0


procedure Productor
b.
begin
P(E)
....
V(S)
end


procedure Consumidor
Esta el mismo ejercicio en la pagina 19 del capitulo 19.
begin
P(S)
....
V(E)
end
</pre>


b)
<pre>
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.
</pre>


===Ejercicio 16*===
== Ejercicio 16: ==
La idea es que cuando hay alguien escribiendo no puede haber nadie leyendo. (Multiples Lectores, un solo escritor)
 
<pre>
X = 1
Escr = 1  


procedure Leer  
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


</pre>
begin


===Ejercicio 17===
//leo el archivo
<br> (Hay que darle prioridad a un solo lado del puente)
<pre>
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
</pre>


===Ejercicio 18===
end
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
procedure Escribir
If (CantEgipcios > 0) then P(X)
....
V(X)
End


Procedure Egipcios
begin
CantEgipcios++
If (CantEgipcios > 0) then P(X)
P(Y)
....
V(Y)
CantEgipcios--
If (CantEgipcios == 0) then V(X)
End
</pre>
c)


===Ejercicio 19*===
P(X)
<pre>
Monitor PeruanosLocos
var: HayCarretilla: Boolean
CintaOcupada, CintaLibre : condition


Procedure CargarCarretilla
//escribo el archivo
Begin
If (HayCarretilla) then
wait(CintaLibre)
HayCarretilla = true
Signal(CintaOcupada)
End


Procedure RetirarCarretilla
V(X)
Begin
If (!HayCarretilla) then
wait(CintaOcupada)
HayCarretilla = false
Signal(CintaLibre)
End


Begin Body
end
HayCarretilla = false
End


End Monitor


Procedure ObreroCargador
Begin
CargarCarretilla
End


Procedure ObreroRetirador
begin Prog-Principal(operacion)
Begin
RetirarCarretilla
End


Begin Main
if (operacion == "Leer) then
Parbegin
ObreroCargador
ObreroRetirador
Parend
End


</pre>
Leer


===Ejercicio 20===
else
<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.
Escribir


===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
endif
lectores ++;
 
signal(sePuedeLeer);
end
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
== Ejercicio 17: ==
Begin
 
if ocupado then wait(no_ocupado);
 
ocupado = V;
 
End
== Ejercicio 18: ==
 
 
 
== Ejercicio 19: ==  
 
Muy largo como para leerlo
 
 
 
== Ejercicio 20: ==
 
 
 
== Ejercicio 21: ==
 
Ni idea que quieren
 
 
 
== Ejercicio 22: ==


Procedure Balanza
Estoy harto de esos ejercicios que te meten enunciados al pedo!!
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>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>


== Ejercicio 23: ==


[[Category:Prácticas]]
Roberto hablo de unas reglas en clase... pero no las encuentro
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)»