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>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 100:
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 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>
<br> Monitor PeruanosLocos
Monitor PeruanosLocos
<br> var: HayCarretilla: Boolean
var: HayCarretilla: Boolean
<br> CintaOcupada, CintaLibre : condition
CintaOcupada, CintaLibre : condition
<br>
 
<br> Procedure CargarCarretilla
Procedure CargarCarretilla
<br> Begin
Begin
<br> If (HayCarretilla) then
If (HayCarretilla) then
<br> wait(CintaLibre)
wait(CintaLibre)
<br> HayCarretilla = true
HayCarretilla = true
<br> Signal(CintaOcupada)
Signal(CintaOcupada)
<br> End
End
<br>
 
<br> Procedure RetirarCarretilla
Procedure RetirarCarretilla
<br> Begin
Begin
<br> If (!HayCarretilla) then
If (!HayCarretilla) then
<br> wait(CintaOcupada)
wait(CintaOcupada)
<br> HayCarretilla = false
HayCarretilla = false
<br> Signal(CintaLibre)
Signal(CintaLibre)
<br> End
End
<br>
 
<br> Begin Body
Begin Body
<br> HayCarretilla = false
HayCarretilla = false
<br> End
End
<br>
 
<br> End Monitor
End Monitor
<br>
 
<br> Procedure ObreroCargador
Procedure ObreroCargador
<br> Begin
Begin
<br> CargarCarretilla
CargarCarretilla
<br> End
End
<br>
 
<br> Procedure ObreroRetirador
Procedure ObreroRetirador
<br> Begin
Begin
<br> RetirarCarretilla
RetirarCarretilla
<br> End
End
<br>
 
<br> Begin Main
Begin Main
<br> Parbegin
Parbegin
<br> ObreroCargador
ObreroCargador
<br> ObreroRetirador
ObreroRetirador
<br> Parend
Parend
<br> End
End
<br>
 
==Ejercicio 20:==
</pre>
<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>
===Ejercicio 20===
==Ejercicio 21:[*]==
<br>La b) ya que siempre uno llega primero y "espera" y el otro sigue de largo.
<br>Ni idea que quieren
<br>La c) tambien, por la misma razon.
<br>
 
==Ejercicio 22:[*]==
===Ejercicio 21*===
<br>Estoy harto de esos ejercicios que te meten enunciados al pedo== ==
<pre>
<br>
Monitor Lectores-Escritores
==Ejercicio 23:[*]==
var lectores : integer
<br>Por que estamos diciendo que se puede ejecutar en paralelo:
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)»