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
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===
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.
 
<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)
<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]. ]
<pre>
<br>
Escr = 1  
<br> X = 1  
 
<br>
procedure Leer  
<br> procedure Leer  
begin  
<br> begin  
P(X)
<br> //leo el archivo  
CantLectores++
<br> end  
if (CantLectores == 1) then P(Escr)
<br>
V(X)
<br> procedure Escribir  
//leo el archivo  
<br> begin  
P(X)
<br> P(X)  
CantLectores--
<br> //escribo el archivo  
if (CantLectores == 0) then V(Escr)
<br> V(X)  
V(X)
<br> end  
end  
<br>
<br> begin Prog-Principal(operacion)  
procedure Escribir  
<br> if (operacion == "Leer") then  
begin  
<br> Leer  
P(Escr)  
<br> else
//escribo el archivo  
<br> Escribir
V(Escr)  
<br> endif  
end  
<br> end
<br>
begin Prog-Principal(operacion)  
==Ejercicio 17:==
if (operacion == "Leer") then  
<br>
Leer  
==Ejercicio 18:==
else
<br>a)
Escribir
<br> // en este esquema cualquiera de los dos puede entrar primero, si entra deshabilita al otro el acceso:
endif
<br> x=1
end
<br> Procedure Romanos
 
<br> Begin
</pre>
<br> P(x)
 
<br> .....
===Ejercicio 17===
<br> V(x)
<br> (Hay que darle prioridad a un solo lado del puente)
<br> End
<pre>
<br> Procedure Egipcios
x = 1, sentido = izq, autosizq  = ?, autosder = ?
<br> Begin
Proc Cruzar
<br> P(x)
if (sentido == izq)
<br> .....
if (autosizq > 0)
<br> V(x)
P(x)
<br> End
cruzar
<br> Do forever
V(x)
<br> Parbegin
P(exc)
<br> Egipcio;Romanos
if (--autosizq == 0)
<br> End
sentido = der
<br>
V(exc)
<br>b)
else
<br> x=1
sentido = der
<br> colaegipcios=0
actualiza(autos)
<br> w=1-colaegipcios
endif
<br> Procedure Romanos
elseif (sentido == der)
<br> Begin
if (autosder > 0)
<br> P(excl)//este semaforo no se si hace falta ay que analizarlo
P(x)
<br> P(w)
cruzar
<br> P(x)
V(x)
<br> V(excl)
P(exc)
<br> .....
if (--autosder == 0)
<br> P(excl)
sentido = izq
<br> V(x)
V(exc)
<br> V(w)
else
<br> P(excl)
sentido = izq
<br>
actualiza(autos)
<br> End
endif
<br> Procedure Egipcios
endif
<br> Begin
</pre>
<br> P(excl)
 
<br> // en esta parte incremento la cola, que hace que w sea negativo y los romanos se queden esperando
===Ejercicio 18===
<br> V(colaegipcios)
a)
<br> P(x)
<pre>
<br> P(excl)
// en este esquema cualquiera de los dos puede entrar primero, si entra deshabilita al otro el acceso:
<br> .......
x=1
<br> P(excl)
Procedure Romanos
<br> V(x)
Begin
<br> P(colaegipcios)
P(x)
<br> P(excl)
.....
<br>
V(x)
<br> End
End
<br> Do forever
Procedure Egipcios
<br> Parbegin
Begin
<br> Egipcios
P(x)
<br> Romanos
.....
<br> End
V(x)
<br>c)
End
<br>
Do forever
==Ejercicio 19:[*]==
Parbegin
<br> Monitor PeruanosLocos
Egipcio;Romanos
<br> var: HayCarretilla: Boolean
End
<br> CintaOcupada, CintaLibre : condition
</pre>
<br>
 
<br> Procedure CargarCarretilla
b)
<br> Begin
<pre>
<br> If (HayCarretilla) then
x=1
<br> wait(CintaLibre)
colaegipcios=0
<br> HayCarretilla = true
w=1-colaegipcios
<br> Signal(CintaOcupada)
Procedure Romanos
<br> End
Begin
<br>
P(excl)//este semaforo no se si hace falta, hay que analizarlo
<br> Procedure RetirarCarretilla
P(w)
<br> Begin
P(x)
<br> If (!HayCarretilla) then
V(excl)
<br> wait(CintaOcupada)
.....
<br> HayCarretilla = false
P(excl)
<br> Signal(CintaLibre)
V(x)
<br> End
V(w)
<br>
P(excl)
<br> Begin Body
<br> HayCarretilla = false
End
<br> End
Procedure Egipcios
<br>
Begin
<br> End Monitor
P(excl)
<br>
// en esta parte incremento la cola, que hace que w sea negativo y los romanos se queden esperando
<br> Procedure ObreroCargador
V(colaegipcios)
<br> Begin
P(x)
<br> CargarCarretilla
P(excl)
<br> End
.......
<br>
P(excl)
<br> Procedure ObreroRetirador
V(x)
<br> Begin
P(colaegipcios)
<br> RetirarCarretilla
P(excl)
<br> End
<br>
End
<br> Begin Main
Do forever
<br> Parbegin
Parbegin
<br> ObreroCargador
Egipcios
<br> ObreroRetirador
Romanos
<br> Parend
End
<br> End
</pre>
<br>
Esta es otra forma (Cortesia Papa Noel)
==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.  
CantEgipcios = 0
<br>
 
==Ejercicio 21:[*]==
Procedure Romanos
<br>Ni idea que quieren
If (CantEgipcios > 0) then P(X)
<br>
....
==Ejercicio 22:[*]==
V(X)
<br>Estoy harto de esos ejercicios que te meten enunciados al pedo== ==
End
<br>
 
==Ejercicio 23:[*]==
Procedure Egipcios
<br>Por que estamos diciendo que se puede ejecutar en paralelo:
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)»