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


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
Línea 27: Línea 25:


<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*===
==Ejercicio 02:[*]==
a)
a)
<pre>
<pre>
    Count5 = Count6 = 2
count2 = 2
count = 3
s1
fork L2
fork L3
fork L4
jump Sigo
L2:
s2
jump Sigo2
L3:
s3
Sigo2:
join count2
jump Sigo
L4:
s4
Sigo:
join count


    s1
    fork L1
    fork L2
    s2
    goto L3
L2: s3
L3: join Count5
    s5
    goto L4
L1: s4
        L4: join Count6
            S6
</pre>
</pre>
b)
b)
Línea 57: Línea 56:
parbegin  
parbegin  
begin  
begin  
parbegin  
parbegin  
s2  
s2  
s3  
s3  
parend  
parend  
s5  
s5  
end  
end  
s4  
s4  
Línea 69: Línea 68:
</pre>
</pre>


===Ejercicio 3*===
==Ejercicio 03:[*]==
<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>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>
La definición de ''' join var''' es:
==Ejercicio 04:[*]==
<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>
1 ) var - - ;
==Ejercicio 05:==
<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>b)
<br>c)
<br>
<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.


==Ejercicio 06:==
<br>a)
<br>b)
<br>
<br>
<br>NOTA: Ejercicios del 7 al 10. Preguntar estos... Tienen pinta de entrar seguro :)


===Ejercicio 4*===
'''(PREMISAS DE DIJKSTRA:)'''
<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
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.
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>
 
===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===
 
<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.
2) No deben hacerse suposiciones sobre la velocidad de los procesos.
Línea 208: Línea 97:
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 después que un proceso haya hecho su pedido.
<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===
==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
 
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)
</pre>
 
===Ejercicio 14*===
<pre>
<pre>
Monitor ej14  
Monitor ej14  
Línea 327: Línea 141:


</pre>
</pre>
(Ver pag 19 al final)
ver pag 19 al final


===Ejercicio 15*===
==Ejercicio 15:[*]==
a)
<br>a)
<pre>
<br> E = 1; S = 0
E = 1; S = 0  
<br>
<br> procedure Productor
<br> begin
<br> P(E)
<br> ....
<br> V(S)
<br> end
<br>
<br> procedure Consumidor
<br> begin
<br> P(S)  
<br> ....
<br> V(E)
<br> end
<br>
<br>b)
<br>programa Productor_Consumidor;
<br>MAX = ......;
<br>monitor M;
<br>buffer : Array (0..MAX-1);
<br>in, out, n; enteros;
<br>buff_lleno, buff_vacío: condición;
<br>procedure Almacenar (v);
<br>begin
<br>if n = MAX then Wait (buff_vacío);
<br>buffer (in) = v;
<br>in = (in + 1) mod MAX;
<br>n = n + 1;
<br>Signal (buff_lleno)
<br>end;
<br>procedure Retirar (v);
<br>begin
<br>if n = 0 then Wait (buff_lleno);
<br>v = buffer (out);
<br>out = (out + 1) mod MAX;
<br>n = n - 1;
<br>Signal (buff_vacio)
<br>end;
<br>begin (* Cuerpo del monitor *)
<br>in, out, n = 0;
<br>end; (* fin monitor *)
<br>procedure Productor;
<br>begin
<br>v = "dato producido"
<br>Almacenar (v)
<br>end;
<br>procedure Consumidor;
<br>begin
<br>Retirar (v);
<br>Hacer algo con v
<br>end;
<br>begin Programa-Principal
<br>Begin;
<br>cobegin
<br>Productor;
<br>Consumidor
<br>coend
<br>end.


procedure Productor
==Ejercicio 16:[*]==
begin
<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]. ]
P(E)
<br>
....
<br> X = 1  
V(S)
<br>
end
<br> procedure Leer  
 
<br> begin  
procedure Consumidor
<br> //leo el archivo  
begin
<br> end  
P(S)
<br>
....
<br> procedure Escribir  
V(E)
<br> begin  
end
<br> P(X)  
</pre>
<br> //escribo el archivo  
 
<br> V(X)  
b)
<br> end  
<pre>
<br>
programa Productor_Consumidor;
<br> begin Prog-Principal(operacion)  
MAX = ......;
<br> if (operacion == "Leer") then  
 
<br> Leer  
Monitor M;
<br> else
var: buffer : Array (0..MAX-1);
<br> Escribir
in, out, n; enteros;
<br> endif  
buff_lleno, buff_vacío: condición;
<br> end
<br>
procedure Almacenar (v);
==Ejercicio 17:==
begin
<br>
if n = MAX then Wait (buff_vacío);
==Ejercicio 18:==
buffer (in) = v;
<br>a)
in = (in + 1) mod MAX;
<br> // en este esquema cualquiera de los dos puede entrar primero, si entra deshabilita al otro el acceso:
n = n + 1;
<br> x=1
Signal (buff_lleno)
<br> Procedure Romanos
end;
<br> Begin
<br> P(x)
procedure Retirar (v);
<br> .....
begin
<br> V(x)
if n = 0 then Wait (buff_lleno);
<br> End
v = buffer (out);
<br> Procedure Egipcios
out = (out + 1) mod MAX;
<br> Begin
n = n - 1;
<br> P(x)
Signal (buff_vacio)
<br> .....
end;
<br> V(x)
<br> End
begin (* Cuerpo del monitor *)
<br> Do forever
in, out, n = 0;
<br> Parbegin
end; (* fin monitor *)
<br> Egipcio;Romanos
<br> End
procedure Productor;
<br>
begin
<br>b)
v = "dato producido"
<br> x=1
Almacenar (v)
<br> colaegipcios=0
end;
<br> w=1-colaegipcios
<br> Procedure Romanos
procedure Consumidor;
<br> Begin
begin
<br> P(excl)//este semaforo no se si hace falta ay que analizarlo
Retirar (v);
<br> P(w)
Hacer algo con v
<br> P(x)
end;
<br> V(excl)
<br> .....
begin Programa-Principal
<br> P(excl)
Begin;
<br> V(x)
cobegin
<br> V(w)
Productor;
<br> P(excl)
Consumidor
<br>
coend
<br> End
end.
<br> Procedure Egipcios
</pre>
<br> Begin
 
<br> P(excl)
===Ejercicio 16*===
<br> // en esta parte incremento la cola, que hace que w sea negativo y los romanos se queden esperando
La idea es que cuando hay alguien escribiendo no puede haber nadie leyendo. (Multiples Lectores, un solo escritor)
<br> V(colaegipcios)
<pre>
<br> P(x)
Escr = 1  
<br> P(excl)
 
<br> .......
procedure Leer  
<br> P(excl)
begin  
<br> V(x)
P(X)
<br> P(colaegipcios)
CantLectores++
<br> P(excl)
if (CantLectores == 1) then P(Escr)
<br>
V(X)
<br> End
//leo el archivo  
<br> Do forever
P(X)
<br> Parbegin
CantLectores--
<br> Egipcios
if (CantLectores == 0) then V(Escr)
<br> Romanos
V(X)
<br> End
end  
<br>c)
<br>
procedure Escribir  
==Ejercicio 19:[*]==
begin  
<br> Monitor PeruanosLocos
P(Escr)  
<br> var: HayCarretilla: Boolean
//escribo el archivo  
<br> CintaOcupada, CintaLibre : condition
V(Escr)  
<br>
end  
<br> Procedure CargarCarretilla
<br> Begin
begin Prog-Principal(operacion)  
<br> If (HayCarretilla) then
if (operacion == "Leer") then  
<br> wait(CintaLibre)
Leer  
<br> HayCarretilla = true
else
<br> Signal(CintaOcupada)
Escribir
<br> End
endif
<br>
end
<br> Procedure RetirarCarretilla
 
<br> Begin
</pre>
<br> If (!HayCarretilla) then
 
<br> wait(CintaOcupada)
===Ejercicio 17===
<br> HayCarretilla = false
<br> (Hay que darle prioridad a un solo lado del puente)
<br> Signal(CintaLibre)
<pre>
<br> End
x = 1, sentido = izq, autosizq  = ?, autosder = ?
<br>
Proc Cruzar
<br> Begin Body
if (sentido == izq)
<br> HayCarretilla = false
if (autosizq > 0)
<br> End
P(x)
<br>
cruzar
<br> End Monitor
V(x)
<br>
P(exc)
<br> Procedure ObreroCargador
if (--autosizq == 0)
<br> Begin
sentido = der
<br> CargarCarretilla
V(exc)
<br> End
else
<br>
sentido = der
<br> Procedure ObreroRetirador
actualiza(autos)
<br> Begin
endif
<br> RetirarCarretilla
elseif (sentido == der)
<br> End
if (autosder > 0)
<br>
P(x)
<br> Begin Main
cruzar
<br> Parbegin
V(x)
<br> ObreroCargador
P(exc)
<br> ObreroRetirador
if (--autosder == 0)
<br> Parend
sentido = izq
<br> End
V(exc)
<br>
else
==Ejercicio 20:==
sentido = izq
<br>La b). Ya que siempre uno llega primero y "espera" y el otro sigue de largo. La c tambien. Por la misma razon.  
actualiza(autos)
<br>
endif
==Ejercicio 21:[*]==
endif
<br>Ni idea que quieren
</pre>
<br>
 
==Ejercicio 22:[*]==
===Ejercicio 18===
<br>Estoy harto de esos ejercicios que te meten enunciados al pedo== ==
a)
<br>
<pre>
==Ejercicio 23:[*]==
// en este esquema cualquiera de los dos puede entrar primero, si entra deshabilita al otro el acceso:
<br>Por que estamos diciendo que se puede ejecutar en paralelo:
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)»