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 59:
parbegin  
parbegin  
begin  
begin  
parbegin  
parbegin  
s2  
s2  
s3  
s3  
parend  
parend  
s5  
s5  
end  
end  
s4  
s4  
Línea 69: Línea 71:
</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>
<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...
2 ) if (var =! 0) then wait;
<br>b)
<br>c)
<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
tu programa queda en wait para siempre.


==Ejercicio 06:==
<br>a)
<br>b)
<br>
<br>


===Ejercicio 4*===
==Ejercicio 07:==
<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
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__
'''NOTA 1: Preguntar ejercicios del 7 al 10... Tienen pinta de entrar seguro :) '''
/  |  \
S2  S3  S4
\  /    |
  S5    S6
    \  /
    S7


</pre>
'''NOTA 2: PREMISAS DE DIJKSTRA:'''
<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
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.
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 103:
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 08:==
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 09:==
 
<br>
===Ejercicio 9===
==Ejercicio 10:==
Similar al Alg. 4, no cumple 4) ya que ambos procesos pueden quedar en espera indefinida (por el while)
<br>
 
==Ejercicio 11:==
===Ejercicio 10===
<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)
<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 144:


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


===Ejercicio 15*===
==Ejercicio 15:[*]==
a)
a)
<pre>
<pre>
Línea 353: Línea 170:
programa Productor_Consumidor;
programa Productor_Consumidor;
MAX = ......;
MAX = ......;
 
monitor M;
Monitor M;
buffer : Array (0..MAX-1);
var: buffer : Array (0..MAX-1);
in, out, n; enteros;
in, out, n; enteros;
buff_lleno, buff_vacío: condición;
buff_lleno, buff_vacío: condición;
Línea 402: Línea 218:
</pre>
</pre>


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


procedure Leer  
procedure Leer  
begin  
begin  
P(X)
CantLectores++
if (CantLectores == 1) then P(Escr)
V(X)
//leo el archivo  
//leo el archivo  
P(X)
CantLectores--
if (CantLectores == 0) then V(Escr)
V(X)
end  
end  
procedure Escribir  
procedure Escribir  
begin  
begin  
P(Escr)  
P(X)  
//escribo el archivo  
//escribo el archivo  
V(Escr)  
V(X)  
end  
end  
Línea 437: Línea 245:
</pre>
</pre>


===Ejercicio 17===
==Ejercicio 17:==
<br> (Hay que darle prioridad a un solo lado del puente)
<br>
<pre>
==Ejercicio 18:==
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===
a)
a)
<pre>
<pre>
Línea 501: Línea 277:
Procedure Romanos
Procedure Romanos
Begin
Begin
P(excl)//este semaforo no se si hace falta, hay que analizarlo
P(excl)//este semaforo no se si hace falta ay que analizarlo
P(w)
P(w)
P(x)
P(x)
Línea 530: Línea 306:
Egipcios
Egipcios
Romanos
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
End
</pre>
</pre>
c)
c)


===Ejercicio 19*===
==Ejercicio 19:[*]==
<pre>
<pre>
Monitor PeruanosLocos
Monitor PeruanosLocos
Línea 601: Línea 357:
</pre>
</pre>


===Ejercicio 20===
==Ejercicio 20:==
<br>La b) ya que siempre uno llega primero y "espera" y el otro sigue de largo.
<br>La b). Ya que siempre uno llega primero y "espera" y el otro sigue de largo. La c tambien. Por la misma razon.  
<br>La c) tambien, por la misma razon.
<br>
==Ejercicio 21:[*]==
<br>Ni idea que quieren
<br>
==Ejercicio 22:[*]==
<br>Estoy harto de esos ejercicios que te meten enunciados al pedo!!
<br>


===Ejercicio 21*===
==Ejercicio 23:[*]==
<pre>
<br>Por que estamos diciendo que se puede ejecutar en paralelo:
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)»