Universidad Tecnológica Nacional Facultad Regional Buenos Aires.
Sistemas Operativos Guía Práctica nº 2 Sincronización
Realizada por los Profesores: Lic. Graciela E. De Luca Ing. Nicanor Casas Con la colaboración del Ing. Néstor Esquivel
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
Guía nº 2 Sincronización
Sincronización Consideraciones Previas Definición: Dos sentencias cualesquiera Si y Sj pueden ejecutarse concurrentemente produciendo el mismo resultado que si se ejecutaran secuencialmente sí solo si se cumplen las siguientes condiciones: (Reglas de Berstein) 1. R(Si) ∩ W(Sj) = (∅) 2. W(Si) ∩ R(Sj) = (∅) 3. W(Sj) ∩ W(Sj) = (∅) Según las condiciones de Berstein: R(A) = {b,d,c,f,g,} W(A) = {c,h}
R(B) = {x,k,m,c} W(B) = {m}
Entonces: R(A) ∩ W(B) =Ø W(A) ∩ W(B) =Ø
R(B) ∩ W(A) = {c}
Este grupo de sentencias no se pueden ejecutar en paralelo
Ejercitación 1. De un ejemplo donde el algoritmo que utiliza TSL produce inanición (Starvation) Supongamos que tenemos tres procesos A, B y C y la variable ocupado = 0.
READY
A
B C BLOCK
En este instante A que está en ejecución hace TSL (ocupado) dejando ocupado = 1
READY
B
C, A
BLOCK Luego pasa B a ejecución y hace TSL (ocupado) quedando en espera activa. Luego bloqueados a Listos, ubicándose detrás de A en la cola.
-2-
C pasa de
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
Guía nº 2 Sincronización
Cuando se le acaba el quantum de tiempo a B pasa a Listos y A a ejecución. READY
B, C
A
BLOCK A coloca ocupado = 0 Cuando C pasa a ejecución hace TSL(ocupado) como ocupado estaba en 0 lo coloca en 1 y pasa a utilizar la región critica, ingresando a esta antes que B y si esta situación se repite B puede padecer inanición. 2. Dados los procesos A y B con variables compartidas, se pide verificar si pueden ejecutar en paralelo. De no ser así en que orden podrían ejecutar. A c=b+d h=c+f+g print c
B m=6*x+k print m/c
c=b+d
h=c+f+g print c
m=6*x+k print m/c
3. Dado el siguiente grafo de precedencia, colocar los semáforos para asegurar la ejecución de los procesos en ese orden.
Valores Iniciales de los semáforos a=1
b1=b2=b3=c1=c2=d1=d2=d3=d4=0
-3-
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas S1 P(a) ----V(b1) V(b2) V(b3)
S2 P(b1) ----V(c1) V(c2)
S3 P(b2) ----V(d3)
S4 P(b3) ----V(d4)
S5 P(c1) ----V(d1)
S6 P(c2) ----V(d2)
Guía nº 2 Sincronización
S7 P(d1) P(d2) P(d3) P(d4) -----V(a)
4. Sincronizar A y B de tal manera que: a) Siempre el resultado de la ejecución sea 50 y 200 o 200 y 50. b) Siempre el resultado de la ejecución sea 50 y 200 A
B
X=199 X=x+1 Print (X)
X=500 X=X/10 Print(X)
a) Como no se necesita darle un orden a la ejecución sólo se debe poner mutua exclusión, por lo tanto con un semáforo basta. A
B
P(mutex) X=199 X=x+1 Print (X) V(mutex)
P(mutex) X=500 X=X/10 Print(X) V(mutex)
b) Aquí se necesita darle un orden a la ejecución por lo tanto se utilizará semáforos cruzados. A P(s) X=199 X=x+1 Print (X) V(k)
B P(k) X=500 X=X/10 Print(X) V(s)
Para que B se ejecute primero el valor del semáforo k debe estar en 1 y s en 0 k=1 s=0 5. Colocar los semáforos de tal manera que los procesos A, B, C ejecuten siempre en la secuencia ABCABC… A P(s) -------------V(k)
B P(k) ---------V(r)
C P(r) ---------V(s)
Para que A ejecute primero s=1, k=0, r=0 6. Colocar los semáforos de tal manera que los procesos A, B, C ejecuten siempre en la secuencia BACABACA…
-4-
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
B P(b) -------
C P(c) -------
V(c)
V(b)
Guía nº 2 Sincronización
Para comenzar con B el valor inicial de b=k=1, c=s=0
A P(s) -------
B P(b) P(k) ------V(c) V(s)
V(k)
C P(c) P(k) ------V(b) V(s)
Prueba de Escritorio Para comprobar si el orden de semáforos es correcto, hacemos la prueba de escritorio con una secuencia distinta a la indicada. Si funciona de todas formas, los semáforos fueron correctamente ubicados. En este caso usaremos BABCA. k 1 0
b 1
c 0
s
A
C
Q
P(b) P(k) ----V(c) V(s)
0 1 1 0 1
P(s) ----V(k)
-1
P(b) 0
0 1 0
B->Qb P(c) P(k) ------V(b) V(s)
0
1
B
0
BQc (Blocked) P3Qp (Blocked)
U(C) D(P)
-1 0 1
P6 D(K) U(A) D(I) U(I) D(M) U(K)
D(G) U(G) 0
D(K) U(A) D(I)
1 -1 0
D(M) U(A) D(I)
2 -2 1 0
P2->Qi (Ready) D(A) D(A) U(I) D(K)
-1 -1
P6Qk (Blocked) U(I) P2Qm (Blocked)
0 -1 1
U(I) D(K)
-2 0 1 -2
P6->Qi (Blocked)
P2->Qk (Blocked)
D(I) U(I) D(P)
P1->Qp (Blocked)
Bloqueados: Deadlock: P2, P6, P1, P5 Starvation: P4 Termina: P3 18.Final 29/12/01 Resuelva la siguiente tabla sabiendo que el semáforos C esta inicializado en 1 y el resto se encuentran en 0.
P1 D(M) D(I) U(R) U(J) U(I) U(P)
P2 D(E) D(B) D(A) U(E) D(L) U(A)
P3 D(R) D(I) D(J) U(E) U(I) U(B)
-12-
P4 D(B) D(C) D(O) U(E) D(P) U(L)
P5 D(C) U(A) U(I) U(C) U(M) U(O)
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
A B C 0 0 1 0 1
E 0
I 0
J 0
L M O P R 0 0 0 0 0
P1
P2
P3
Guía nº 2 Sincronización
P4
D(C) U(A) U(I) U(C) U(M) U(O)
1 1 1 1 -1
D(R)
-1
P3->Qr P2->Qe
D(E) 0 0 0 1 1 1
D(M) D(I) U(R) U(J) U(I) U(P)
P3Qb
P2, P4 quedan bloqueados P1, P3 y P5 terminan. 19.Final 17/02/2001 De existir, muestre una secuencia de eventos para los cuales P1, y P2 entran en DEADLOCK. Los semáforos son: s1, s2 (Semáforos Mutex). Void P1() { While(1) { Down (s1); Down (s2); Printf(“Bambu”); Up (s1); Up (s2); } }
Void P2() { While(1) { Down (s2); Printf(“Guetzel”); Down (s1); Up (s2); Up (s1); } }
El enunciado nos dice que ambos semáforos (s1 y s2) son Mutex. Esto quiere decir que se encuentran inicializados en 1. Ambos procesos (p1 y p2) se ejecutan al mismo tiempo. Cuando P1 ejecuta la sentencia: Down (s1); S1 que estaba en 1 pasa a estar en 0 y supongamos que en ese instante se le acaba el quantum de tiempo y ejecuta P2 haciendo un Down (s2); S2 estaba en 1 pasa a estar en 0 y cuando P2 ejecute S1 queda bloqueado. Cuando le vuelve a tocar el procesador a P1 ejecuta S2 y queda bloqueado Entonces ambos procesos quedan en DEADLOCK
-13-
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
Guía nº 2 Sincronización
20.En un sistema de computación real, ni los recursos disponibles ni los requerimientos de los procesos por recursos se mantienen por largo tiempo. Los recursos se rompen o son reemplazados, los procesos vienen y van, se agregan nuevos recursos al sistema, etc. Si en tal sistema, los bloqueos se controlan con el algoritmo del banquero, ¿cuáles de los siguientes cambios se puede hacer con seguridad (sin introducir posibilidad de bloqueos) y bajo qué circunstancias?: Incrementar AVAILABLE (se agregan nuevos recursos). Decrementar AVAILABLE (se eliminan recursos del sistema). Incrementar MAX para un proceso (el proceso necesita más recursos que los permitidos). Decrementar MAX para un proceso (el proceso decide que no va a necesitar algunos recursos). Incrementar el número de procesos. Decrementar el número de procesos.
Consideraciones Previas: Algoritmo de comprobación de un estado seguro: • • •
Buscar fila F cuyas necesidades de recursos sean menores que lso recursos disponibles. Si no hay => estado no seguro, el sistema se puede interbloquear, se necesitan más de los disponibles Suponer que el proceso de la fila F pide todos los recursos y termina. Marcar el proceso como terminado y añadir sus recursos al vector de recursos disponibles. Repetir los dos pasos anteriores hasta terminar todos los procesos. Si se puede terminar => estado seguro.
21.Hallar la matriz de necesidad. Tener en cuenta que el sistema usa el “Algoritmo del Banquero” para bloquear a los procesos que piden más recursos que los disponibles. Solo se asignara a un proceso los recursos que necesite, si estos son todos los que va a necesitar para completar la ejecución. El número de los procesos corresponde con el orden de llegada. Se deberá utilizar el algoritmo de planificación FCFS. Además indicar si el sistema es seguro o no (o sea verificar si ningún proceso queda sin los recursos necesarios).
P1 P2 P3 P4 P5
Peticiones Máximas R1 R2 R3 R4 2 3 2 5 1 2 6 3 0 2 4 5 3 0 5 2 3 4 5 4
R1 1
Disponibles R2 R3 0 9
R4 4
P1 P2 P3 P4 P5
La Matriz de necesidad = M Peticiones Máximas – M Recursos Asignados
P1 P2 P3 P4 P5
R1 2 0 0 1 2
Necesidad R2 R3 0 1 1 3 0 3 0 3 1 0
R4 2 1 5 2 2
Y el vector de recursos es:
-14-
Recursos Asignados R1 R2 R3 R4 0 3 1 3 1 1 3 2 0 2 1 0 2 0 2 0 1 3 5 2
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
R1 5
Guía nº 2 Sincronización
Recursos R2 R3 R4 9 21 11
Debemos encontrar una secuencia en la que se terminen de ejecutar todos los procesos para que no haya deadlock. Si utilizamos el algogitmo FCFS, el primer proceso que debería ser atendido es P1 pero si esto sucede provocará interbloqueo. Ya que necesita 2 unidades de R1 y sólo hay una disponible. Si buscamos otra secuencia, a simple vista nos parece que P4, P1, P5, P3, P2 es un estado seguro. Vamos a comprobarlo. Luego de ejecutar P4 la matriz de asignación es la siguiente:
P1 P2 P3 P4 P5
R1 0 1 0 0 1
R2 3 1 2 0 3
R3 1 3 1 0 5
R4 3 2 0 0 2
Cuando P4 devuelve sus recursos luego de ejecutar, la matriz de recursos disponibles es la siguiente: R1 3
R2 0
R3 11
R4 4
Luego de ejecutar P1 la matriz de asignación es la siguiente:
P1 P2 P3 P4 P5
R1 0 1 0 0 1
R2 0 1 2 0 3
R3 0 3 1 0 5
R4 0 2 0 0 2
Cuando P1 devuelve sus recursos luego de ejecutar, la matriz de recursos disponibles es la siguiente: R1 3
R2 3
R3 12
R4 7
Luego de ejecutar P5 la matriz de asignación es la siguiente:
P1 P2 P3 P4 P5
R1 0 1 0 0 0
R2 0 1 2 0 0
R3 0 3 1 0 0
R4 0 2 0 0 0
Cuando P5 devuelve sus recursos luego de ejecutar, la matriz de recursos disponibles es la siguiente: R1 4
R2 6
R3 17
R4 9
Luego de ejecutar P3 la matriz de asignación es la siguiente: R1
R2
R3
R4
-15-
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas P1 P2 P3 P4 P5
0 1 0 0 0
0 1 0 0 0
0 3 0 0 0
Guía nº 2 Sincronización
0 2 0 0 0
Cuando P3 devuelve sus recursos luego de ejecutar, la matriz de recursos disponibles es la siguiente: R1 4
R2 8
R3 18
R4 9
Luego de ejecutar P2 la matriz de asignación es la siguiente:
P1 P2 P3 P4 P5
R1 0 0 0 0 0
R2 0 0 0 0 0
R3 0 0 0 0 0
R4 0 0 0 0 0
Cuando P2 devuelve sus recursos luego de ejecutar, la matriz de recursos disponibles es la siguiente: R1 5
R2 9
R3 21
R4 11
La matriz final de recursos disponibles es igual al vector de recursos, si el ejercicio está bien hecho. Hemos demostrado que este estado es seguro para el sistema y que todos los procesos finalizan su ejecución en esta secuencia.
22.Escribir un algoritmo para sincronizar el paso de vehículos sobre un puente con una sola dirección de circulación. Los vehículos arriban al puente pueden ir en ambas direcciones, pero sólo pueden pasar de una dirección por vez. No hay restricción acerca de la cantidad de vehículos que pueden estar sobre el puente al mismo tiempo. ¿Hay starvation?; si la hay, ¿cómo hacer pare evitarla? ¿Puede haber Deadlock? Explicar porqué. a=1,b=0 P1
P2 while (1) { P(b) { if(hay_autos()) /*puede no haber ningun auto esperando*/ { entrar_en_puente () usar_puente () salir_puente () } } V(a) }
while (1) { P(a) { if(hay_autos()) /*puede no haber ningun auto esperando*/ { entrar_en_puente () usar_puente () salir_puente () } } V(b) }
Puede haber starvation si existiera la posibilidad de que haya infinitos autos de un lado y nunca terminen de pasar. Y los que están esperando del lado contrario nunca pueden empezar a pasar. En este caso eso no puede ocurrir porque el sistema pregunta una vez por lado alternadamente si hay
-16-
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
Guía nº 2 Sincronización
autos, si no es así pasa al otro lado y si la respuesta es afirmativa, deja pasar el auto correspondiente. 23.Se tienen 3 procesos: P1, P2 y P3: El código del proceso Pi (i=1, 2, 3) es: Pi( ) /*Proceso Pi con i=1,2,3 */ { while (TRUE) printf(“Soy el proceso i \n”); } Se desea mostrar en la salida lo siguiente: Soy el proceso 1 Soy el proceso 2 Soy el proceso 3 Soy el proceso 1 Soy el proceso 2 …………………………… a) Sincronizar mediante semáforos. Definir los semáforos e inicializarlos correctamente. Usar el mínimo número de semáforos. A=1,B=0,C=0 P1 P(A) ---V(B)
P2 P(B) ----V(C)
P3 P(C) ----V(A)
b) Reescriba los tres procesos con los semáforos incorporados.
P1( ) { while (TRUE) P(A) printf(“Soy el proceso i \n”); V(B) }
c)
P2( ) { while (TRUE) P(B) printf(“Soy el proceso i \n”); V(C) }
P3( ) { while (TRUE) P(C) printf(“Soy el proceso i \n”); V(A) }
Sincronizar mediante mensajes. Se pide el mínimo código. ¿Cómo parte?
24.Dados 4 procesos que cumplen las siguientes funciones:
P
X S1
Y S2
S2
S3
V3
V2
V
Z S1
W S3
V1
V3
V1 Los valores iniciales de los semáforos son S1=2 y S2=S3=1. Los procesos siguen un orden del tipo YXZW.
Se pide, determinar la traza de ejecución y si los procesos terminan o no. S1
S2
S3
X
Y
-17-
Z
W
Q
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas 2
1 0
Guía nº 2 Sincronización
1 P(S2) P(S3) ------V(S2)
0 1 1
P(S1) P(S2) ------V(S3)
0 1 0
P(S1) -----V(S1) V(S1)
1 2 0
P(S3) -----V(S3)
1 -1
P(S2)
1
Y->Qs2
P(S1) P(S2)
-2
X->Qs2
0
P(S1) -----V(S1) V(S1)
1 2 0
P(S3) -----V(S3)
1 Terminan Z,W. Bloqueados Y,X.
25.Dados los siguientes procesos con su respectivos códigos y los valores iniciales de los semáforos A =0, B= 1, C = 1, D=0. X P(C)
Y P(D)
P(D) .......
P(A) ........
V(D)
V(B)
Z P(C)
....... V(A)
W P(A) P(B) ....... V(C)
Indique los procesos que terminaron (y en que orden) y los que no. Secuencia: Y- Z - X -W. A 0
B 1
C 1
D 0 -1
X
Y
W
P(D)
0
Q Y->Qd
P(C) ----V(A)
1 -1
Z
P(C)
X->Qc
0
P(A) P(B) ----V(C)
0 0 Terminan Z, W. Bloqueados Y, X.
-18-
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
Guía nº 2 Sincronización
26.Cambie los semáforos del ejercicio anterior para que el sistema sea SEGURO y no quede ningún proceso bloqueado. 27.Los siguientes procesos se ejecutan en paralelo. Utilizando semáforos, especifique cuales terminaron y cuales no. Inicialización de los semáforos: P1 D(I) U(I) D(P) U(P) D(K)
A B C G 0 0 0 1 1
I, B, A, C, P = 0
P2 D(M) U(A) D(I) U(I) D(K) U(M)
I 0
K M P 1 1 0
P3 U(B) D(C) D(G) U(G)
P1
M, K, G = 1 P4 D(A) D(A) U(I) D(K) U(K) D(P) U(P) P3
P2
P5 U(C) D(P) D(M) D(G) U(M) D(K) U(G) P4
P5
P6 D(K) U(A) D(I) U(I) D(M) U(K) U(P) P6
U(C) D(P)
-1 1
P5->Qp
U(B) D(C) D(G) U(G)
0 0 1 0
D(M) U(A) D(I)
1 -1
P2->Qi
0
D(K) U(A) D(I)
2 -2 1 0
D(A) D(A) U(I) D(K)
-1 -1 0
P2Qk P6Qk
U(I) D(K)
-2 1
U(I) D(M)
-1 0 1 -2
D(I) U(I) D(P)
P6->Qi
P6->Qm
P1->Qp
Sólo P3 termina.
28.Realice la sincronización de 4 procesos A ---> |____10______| --->BDBD(una vez cada uno, en ese orden) ----->|colalimitada------> C -Genera mensajes
-Retira mensajes
-Retira mensajes
-Deposita mensajes
-Procesa el mens
-Consume el mens.
-Deposita mens.
-19-
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
Guía nº 2 Sincronización
vacio=10, lleno=0 a=1,b=0, lleno1=0 A while (1) { m=generar() P(vacio) P(mutex) depositar(m) V(mutex) V(lleno) }
B while (1) { P(a) P(lleno) P(mutex) m=retirar() V(mutex) V(vacio) procesar(m) P(mutex1) depositar(m) P(lleno1) V(mutex1) v(b) }
C while (1) { P(b) P(lleno) P(mutex) m=retirar() V(mutex) V(vacio) procesar(m) P(mutex1) depositar(m) P(lleno1) V(mutex1) v(a) }
D while (1) { P(lleno1) P(mutex1) m=retirar() V(mutex1) consumir (m) }
29.Realice la sincronización de 4 procesos A ----> |______ilimitada____| ----->B--->|___5___|------> C y D (en forma alternada estrictamente) -Genera mensajes - Retira mensajes -Retira mensajes -Deposita mensajes - Procesa el mens -Consume el mens. - Deposita mens. lleno=0=lleno1, vacio=5 a=0,b=1 A B while (1) while (1) { { m=generar() P(lleno) P(mutex) P(mutex) depositar(m) m=retirar() V(mutex) V(mutex) V(lleno) procesar(m) } P(vacio) P(mutex1) depositar(m) V(mutex1) V(lleno1) }
C while (1) { P(b) P(lleno1) P(mutex1) m=retirar() V(mutex1) V(vacio) consumir(m) V(a) }
D while (1) { P(a) P(lleno1) P(mutex1) m=retirar() V(mutex1) V(vacio) consumir (m) V(b) }
30.Tengo un proceso productor que deposita los mensajes en un Buffer de 30 posiciones. Luego los retira y los procesa otro proceso intermediario, que va depositando los mensajes procesados en un Buffer de 5 posiciones otros dos procesos C1 y C2 los retiran e Imprimen altenadamente , C1,C2, C1,C2, C1,C2 etc. Realizar los algoritmos para los 4 procesos.
vacio=30,lleno=0,vacio1=5,lleno1=0,a=1,b=0
A while(1) { m=producir()
B while(1) { P(lleno)
C while(1) { P(a)
-20-
D while(1) { P(b)
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas P(vacio) P(mutex) depositar(m) V(mutex) V(lleno)
P(mutex) m=retirar() V(mutex) V(vacio) k=procesar(m) P(vacio1) P(mutex1) depositar(k) V(mutex1) V(lleno1)
}
Guía nº 2 Sincronización
P(lleno1) P(mutex1) k=retirar_k() V(mutex1) V(vacio1) consumir(k) V(b)
P(lleno1) P(mutex1) k=retirar_k() V(mutex1) V(vacio1) consumir(k) V(a)
}
}
}
31.Dado el siguiente grafo de asignación de recursos seleccione la opción correcta, justificando su elección. r1
r2 P2
P1
r3
r4 P4
P3
P5
r5
a) El grafo tiene un ciclo y por tanto se puede asegurar que no existe interbloqueo (Deadlock). b) El grafo tiene un ciclo y por tanto se puede asegurar que existe interbloqueo. c) Existe una secuencia en la terminación de procesos que no produce interbloqueo. d) Ninguna es correcta. JUSTIFIQUE RESPUESTA: C Si Termina P5, P4, P3, P2, P1 tengo una secuencia de ejecución donde no hay deadlock, (Hay otras más) Podemos armar las matrices de asignación y necesidad de la siguiente manera: M Asignación R1 R2 0 P1 1 1 P2 0 0 P3 1 0 P4 0 1 P5 0
R3 0 0 1 0 0
R4 0 1 0 0 0
R5 0 0 0 1 1
M Necesidad R1 R2 0 P1 0 0 P2 1 0 P3 0 1 P4 0 0 P5 0
El vector de recursos disponibles es: R1 0
R2 0
R3 0
R4 0
R5 0
Y el vector de recursos es: R1 2
R2 2
R3 1
R4 1
R5 2
-21-
R3 1 0 0 0 0
R4 0 0 0 0 0
R5 0 0 1 0 0
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
Guía nº 2 Sincronización
Debemos encontrar una secuencia en la que se terminen de ejecutar todos los procesos para que no haya deadlock. A simple vista nos parece que la secuencia P5, P4, P3, P2, P1 es un estado seguro. Vamos a comprobarlo. Luego de ejecutar P5 la matriz de asignación es la siguiente:
P1 P2 P3 P4 P5
R1 1 0 1 0 0
R2 0 1 0 0 0
R3 0 0 1 0 0
R4 0 1 0 0 0
R5 0 0 0 1 0
Cuando P5 devuelve sus recursos luego de ejecutar, la matriz de recursos disponibles es la siguiente: R1 0
R2 1
R3 0
R4 0
R5 1
Luego de ejecutar P4 la matriz de asignación es la siguiente:
P1 P2 P3 P4 P5
R1 1 0 1 0 0
R2 0 1 0 0 0
R3 0 0 1 0 0
R4 0 1 0 0 0
R5 0 0 0 0 0
Cuando P4 devuelve sus recursos luego de ejecutar, la matriz de recursos disponibles es la siguiente: R1 0
R2 1
R3 0
R4 0
R5 2
Luego de ejecutar P3 la matriz de asignación es la siguiente:
P1 P2 P3 P4 P5
R1 1 0 0 0 0
R2 0 1 0 0 0
R3 0 0 0 0 0
R4 0 1 0 0 0
R5 0 0 0 0 0
Cuando P3 devuelve sus recursos luego de ejecutar, la matriz de recursos disponibles es la siguiente: R1 1
R2 1
R3 1
R4 0
R5 2
Luego de ejecutar P2 la matriz de asignación es la siguiente:
P1 P2 P3 P4 P5
R1 1 0 0 0 0
R2 0 0 0 0 0
R3 0 0 0 0 0
R4 0 0 0 0 0
R5 0 0 0 0 0
-22-
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
Guía nº 2 Sincronización
Cuando P3 devuelve sus recursos luego de ejecutar, la matriz de recursos disponibles es la siguiente: R1 1
R2 2
R3 1
R4 1
R5 2
Luego de ejecutar P1 la matriz de asignación es la siguiente:
P1 P2 P3 P4 P5
R1 0 0 0 0 0
R2 0 0 0 0 0
R3 0 0 0 0 0
R4 0 0 0 0 0
R5 0 0 0 0 0
Cuando P1 devuelve sus recursos luego de ejecutar, la matriz de recursos disponibles es la siguiente: R1 2
R2 2
R3 1
R4 1
R5 2
La matriz final de recursos disponibles es igual al vector de recursos, si el ejercicio está bien hecho. Hemos demostrado que este estado es seguro para el sistema y que todos los procesos finalizan su ejecución en esta secuencia. 32.Final 03/03/2007 (ej 1) Considere que estos 4 procesos se están ejecutando concurrentemente, y que en el. Sistema existen 4 semáforos inicializados en 1. Dada la siguiente secuencia de ejecución se pide determinar los posibles estados del sistema, justificando su respuesta en cada caso. Si existiera la posibilidad de que se produzca deadlock indique entre que procesos y con que recursos. P1 P(S) P(T) P(S) ……. V(T) V(S)
P2 P(X) P(U) P(X) … V(U) V(X)
P3 P(U) P(S) … V(S) V(U)
P4 P(T) P(X) … V(X) V(T)
Hay diferentes secuencias de ejecución que producen resultados distintos, basta con explicar alguna. a) Si ejecuta el P1 ,P2,P3;P4 en forma completa hasta bloquearse S 1 0
T 1
U 1
X 1
P1
P2
P3
P4
P(S) P(T) P(S)
0 -1 0 0 -1
P(X) P(U) P(X)
-1
P(U)
-1
P(T)
-23-
Q
Estado
P1->Qs
BLOQ
P2->Qx P3->Qu P4->Qt
BLOQ BLOQ BLOQ
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
Guía nº 2 Sincronización
El Proceso P1 y P2 padecen inanición ya que no hay suficientes recursos y no hay espera circular no se cumplen las condiciones del Deadlock En este caso. b) Otra forma de ejecución es que cada uno ejecute una instrucción y pase a otro proceso. S 1 0
T 1
U 1
X 1
P1
P2
P3
P4
Q
Estado
P1->Qt P2->Qu P3->Qs P4->Qx
BLOQ BLOQ BLOQ BLOQ
P(S) 0
P(X)
0
P(U)
0 -1
P(T) P(T) -1
P(U)
-1
P(S) -1
P(X)
Si se produce esta secuencia y de esta forma è hay deadlock 33.Final 18/02/2006 (ej c2) Indicando la traza de ejecución, muestre en forma CLARA de que manera se ejecutarán los siguientes procesos, considerando que lo hacen concurrentemente en un sistema multiprogramado. Detalle que procesos finalizaron y cuáles no y por que razón. Para que se considere aprobado el punto deberá justificar su conclusión con un grafo de asignación de recursos, caso contrario el ejercicio se evaluará como incorrecto en su TOTALIDAD. Adicionalmente, considere que el sistema operativo no libera los recursos que tienen asignados los procesos cuando finalizan. Inicialización de los semáforos: P1 D(I) U(I) D(P) U(P) D(K)
Instante
P2 D(M) U(A) D(I) U(I) D(K) U(M)
READY QUEUE
I, B, A, C, P = 0 P3 U(B) D(C) D(G) U(G)
M, K, G = 1 P4 D(A) D(A) U(I) D(K) U(K) D(P) U(P)
RUN-
P5 U(C) D(B) D(M) D(G) U(M) D(K) U(G)
COLA DE SEM.
SEMAFOROS
NING
I
B
A
C
P
M
K
G
0
0
0
0
1
1
1
Inicial
P1,P2,P3,P4,P5,P6
______
0
t1
P2,P3,P4,P5,P6
P1(DI)
-1
T2
P3,P4,P5,P6
P2(DM)
T3
P3,P4,P5,P6
P2(UA)
T4
P3,P4,P5,P6
P2(DI)
T5
P4,P5,P6
P3(UB)
____ I={P1}
0 1
_____ P1 = Blocked
A={}
-2
I={P1,P2} 1
P2 = Blocked
B={} -1
C={P3}
P4,P5,P6
P3(DC)
T7
P5,P6
P4(DA)
0
A={}
P4(DA)
-1
A={P4}
P5,P6
Estado
M={}
T6
T8
P6 D(K) U(A) D(I) U(I) D(M) U ( K) U(P)
-24-
P3 = Blocked
P4 = Blocked
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas T9
P6
P5(UC)
t10
P6, P3
P5(DB)
t11
P6, P3
P5(DM)
t12
P3
P6(DK)
t13
P3
P6(UA)
Guía nº 2 Sincronización
0
C={}
0
P3 = Ready
B={} -1
M={P5} 0
P5 = Blocked
K ={}
0 -3
A ={}
P4 = Ready
I={P1,P2,P6}
P5 = Blocked
t14
P3,P4
P6(DI)
t15
P4
P3(DG)
0
G={}
t16
P4
P3(UG)
1
G={}
P3 = TERMINA
t17
VACIA
P4(UI)
I={P2,P6}
P1 = Ready
t18
P1
P4(DK)
K ={P4}
P4 = Blocked
t19
VACIA
P1(UI)
I={P6}
P2 = Ready
T20
P2
P1(DP)
P={P1}
P1 = Blocked
T21
VACIA
P2(UI)
I={}
P6 = Ready
T22
P6
P2(DK)
K ={P4,P2}
P2 = Blocked
T23
VACIA
P6(UI)
T24
VACIA
P6(DM)
-2 -1 -1 -1 0 -2 1
I={} -2
M={P6}
P6 = Blocked
PROCESO P3
TERMINA EN EL INSTANTE 16
PROCESO P1
ESTA BLOQUEADO ESPERANDO QUE SE LIBRE EL RECURSO P
PROCESO P5
ESTA BLOQUEADO ESPERANDO QUE SE LIBRE EL RECURSO M
PROCESO P3
ESTA BLOQUEADO ESPERANDO QUE SE LIBRE EL RECURSO K
LOS PROCESOS P2 Y P6
ESTAN EN DEADLOCK
OBSERVACIÓN: Los procesos P1, P4 Y P5 ESTAN BLOQUEADOS aunque la liberación de recursos ( P, B y A) depende del orden de ejecución externa o de los procesos involucrados en el conflicto, técnicamente no están involucrados en el DEADLOCK como sí lo están M y K
34.Final 17/02/2007 (ej 1) En un Depósito hay un montacargas para distribuir la mercadería en los dos sectores del 1er piso. El empleado de depósito carga un paquete y lo coloca en el montacargas y los empleados de los sectores A y B los retiran. Siempre deben retirar 3 paquetes el empleado del sector A y luego 1 paquetes el empleado del sector B , 3 del A y 1 del B y así sucesivamente. El ascensor puede cargar hasta 20 paquetes e inicialmente está vacío. 1.1 Realizar la sincronización con semáforos (sin pseudo código) de los tres procesos. D, A y B D
|________20______|
AAABAAAB
vacio=20 lleno=0 a=3 b=0 mutex D Do while (t) { traer_paquete() P(vacio) P(mutex) Cargar_paq_montacargas() V(mutex) V(lleno) }
A Do while(t) { P(a) P(lleno) Retirar_paq_montacargas () V(mutex) V(vacio) Llevar_paquete_al_sector()
-25-
B Do while (t) { P(b) P(b) P(b) P(lleno) V(mutex) Retirar_paquete_montacargas() V(mutex)
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas }
Guía nº 2 Sincronización
V(vacio) V(a) V(a) V(a) Llevar_paquete_al _sector() }
1.2 Hacer una prueba de escritorio donde el orden de ejecución .sea D D D D D D D D A B A para mostrar que la sincronización funciona. vacio
lleno
mutex
a
b
20
0
1
3
0
19
A
D
B
Colas
P(vacio) 0
P(mutex)
1
V(mutex)
1
V(lleno)
18
P(vacio) 0
P(mutex)
1
V(mutex)
2
V(lleno)
17
P(vacio) 0
P(mutex)
1
V(mutex)
3
V(lleno)
16
P(vacio) 0
P(mutex)
1
V(mutex)
4
V(lleno)
15
P(vacio) 0
P(mutex)
1
V(mutex)
5
V(lleno) 2
P(a)
4
P(lleno) 0
P(mutex)
1
V(mutex)
16
V(vacio) 1
V(b)
0
P(b)
-1
P(b)
1
B
Qb (Bloqueado)
B
Qb ( Ready)
P(a)
3
P(lleno) 0
P(mutex)
1
V(mutex)
17
V(vacio) 0
V(b)
35.Los organizadores del próximo mundial de fútbol 5 se encuentran desarrollando una aplicación que simule los penales que se producirán en los partidos que se llevarán a cabo durante 1 campeonato. Pero están teniendo inconvenientes, ya que han definido 3 tipos de procesos que se ejecutan en forma concurrente y no loran sincronizar los mismos. Para ser un poco más ordenados, se han
-26-
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
Guía nº 2 Sincronización
definido una serie de reglas que se deberán cumplir, y a su vez definieron un pseudo código que es una primera aproximación para poder resolver la simulación. A continuación se detallan las reglas que se tienen que cumplir para que puedan lograr una correcta simulación: • Existen 5 jugadores y un arquero • Los jugadores no pueden patear si el árbitro no lo indicó • El arquero no debe atajar si el árbitro no da la orden • Sólo se deben usar semáforos, indicando el tipo y los valores iniciales • Se debe sincronizar el orden en que patean los jugadores • El árbitro no debe dar el pitido hasta que los 2 jugadores no estén posicionados en sus respectivos lugares. • Existe una variable global GOL que indica si el último penal pateado fue gol o no • Una vez que se valide el penal, se pasará el turno al próximo patearodr • Se tiene una función “Siguiente ()” que cuando es invocada por los procesos retorna el identificador del próximo pateador y la función “Actual()” que retorna el identificador del jugador actual. Ésta es la solución implementada con semáforos mutex, dadas las reglas del ejercicio se utiliza un vector de semáforos (turno) para sincronizar el turno de cada jugador, y que éstos no se salteen, el resto de los semáforos solo son para la sincronización de la acción de cada proceso durante el penal. SEMAFOROS: jugEnPos=arqEnPos=Tiro=Atajada=ValidacionJ=ValidacionA=0 Turno[5] = {1}
Arbitro While (1) { wait(arqEnPos); wait(jugEnPos); darOrden(); signal (orden); wait(atajada) ; validar_tiro(); signal(ValidacionJ); signal(ValidacionJ); }
Jugador While(1) { wait(turno[Actual()]); posicionarse(); signal(jugEnPos); wait(orden); patear(); signal(Tiro); wait(ValidacionJ) ; if(GOL=TRUE) festejar(); else lamentarse(); signal(turno[Siguiente()]) }
Arquero While(1) { ubicarse(); signal(arqEnPos); wait(Tiro); atajar(); signal(atajada); wait(ValidacionA) ; if(GOL=TRUE) lamentarse(); else festejar(); }
36.Un pequeño centro de sky cuenta con una aerosilla con capacidad para una sola persona. Si se tiene los seudo códigos de los procesos aerosilla u esquiador, se pide que sincronice convenientemente usando semáforos para que no produzca Deadlock ni Starvation. Semáforos mutex: base=1;silla=0;cima=0 Void esquiador ()
Void Aerosilla()
{ while (1) { llegar_a_la_aerosilla(); wait(base) ; subir_a_la_aerosilla(); signal(silla); wait(cima); bajar_de_la_aerosilla(); signal(silla);
{ while(1) { wait(silla); subir_la_montaña(); signal(cima); wait(silla); bajar_la_montaña(); signal (base); }
-27-
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas bajar_esquiado(); } } Esquiador Llegar_a_la_aerosilla() W(base) Subir_a_la_aerosilla() S(silla) W(cima) Bajar_de_la_aerosilla S(silla) Bajar_esquiando()
Guía nº 2 Sincronización
}
Aerosilla W(silla)
Subir_a_la_montaña() S(cima) W(silla) Bajar_la_montaña() S(base)
Silla 0 0 0 0 1 0 0 0 1 0
Cima 0 0 0 0 0 0 1 0 0 0
Base 1 1 0 0 0 0 0 0 0 1
37.Cuatro alumnos están jugando en clase un juego de cartas que implica coordinación (no saltearse los turnos) y exclusión mutua (mientras uno toma una carta o la cambia con el compañero el resto debe esperar a que finalice para no quitarse la carta de la mano). Se plantea tomar como base esta experiencia para implementar una arquitectura de comunicación entre procesos que permita realizar una práctica de inteligencia artificial en la que cada alumno codificará su estrategia dentro de las siguientes funciones aisladas. Proceso_jugador() { while(1) { pensar_la_jugada(); wait(esperar[IDENTIFICACION_DE_JUGADOR]); jugar(); signal(esperar[SIGUIENTE(IDENTIFICACION_DE_JUGADOR)]); } } Todos los procesos serán hijos de un procesos principal denominado partida, y por lo tanto heredarán a través de la función fork() y exec() correspondiente una serie de semáforos inicializados de la siguiente manera: #define NUMERO_DE_JUGADORES 4 #define NUMERO_DE_CARTAS 40 #define SIGUIENTE(IDENTIFICACION_DE_JUGADOR) 1)/NUMERO_DE_JUGADORES)
((IDENTIFICACION_DE_JUGADOR
+
Se pide: a) Intercalar en el código propuesto para cada proceso_jugador() las funciones wait y signal necesarias sobre los semáforos esperar [IDENTIFICACION_DE_JUGADOR] y esperar[SIGUIENTE(IDENTIFICACION_DE_JUGADOR)] para asegurar el correcto funcionamiento del mismo, es decir, que cada jugador deba esperar su turno antes de poder ejecutar jugar (). b) ¿Cómo debe estar inicializado el array de semáforos para que funcione, es decir, empiece el primer jugador y ceda el turno al siguiente y así sucesivamente, quedando bloqueado cada cual hasta que le toque el turno? Rta: Esperar[1,0,0,0] c) En el caso que jugar() no se ejecute de forma atómica, ya que tendrá que modificar al menos dos entradas de la tabla carta, ¿habría que incorporar algo para garantizar la exclusión mutua en la ejecución de jugar()?. De ser necesario, escribir el código. De no serlo, explique porqué. Rta: No es necesario porque wait y signal se ejecutan de forma atómica, por lo tanto se garantiza
-28-
UTN - FRBA
Sistemas Operativos
Lic. Graciela De Luca – Ing. Nicanor Casas
Guía nº 2 Sincronización
la exclusión mutua de la ejecución jugar. Para que se ejecute esa sentencia cada proceso debe esperar a q se habilite el respectivo semáforo del cual está haciendo el wait. P0
P1
P2
P3
Pensar() Wait(esperar[0]) Jugar() Signal(esperar[1]) Pensar() Wait(esperar[0])
Pensar() Wait(esperar[1])
Pensar() Wait(esperar[2])
Pensar() Wait(esperar[3])
Jugar() Signal(esperar[2]) Pensar() Wait(esperar[1])
Jugar() Signal(esperar[3]) Pensar() Wait(esperar[3])
-29-
Jugar() Signal(esperar[3]) Pensar() Wait(esperar[3])
0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
Esperar 1 2 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
