Segundo Parcial 05/06/2003 (Sistemas Operativos)

Sistemas Operativos
Segundo Parcial del Primer Cuatrimestre del 2003
05/06/2003

Ejercicio 1)

Sea las matrices de Alocación y Necesidad que se muestran a continuación en un sistema que se encuentra en estado seguro. Se pide indicar si un Requerimiento por parte del proceso P5 del tipo < 0 0 0 1 > puede ser satisfecho. Verifiquelo utilizando el algoritmo del Banquero. En caso de no po-der ser satisfecho indique que accion/es se toman.
ALOCACION NECESIDAD DISPONIBLE
R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4
P1 1 1 3 2 0 5 0 0 2 0 0 1
P2 2 3 1 1 1 1 2 1
P3 5 0 0 1 2 2 1 0
P4 1 4 1 0 1 0 0 0
P5 0 5 2 0 0 8 0 5

El nuevo estado es:
ALOCACION NECESIDAD DISPONIBLE
R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4
P1 1 1 3 2 0 5 0 0 2 0 0 0
P2 2 3 1 1 1 1 2 1
P3 5 0 0 1 2 2 1 0
P4 1 4 1 0 1 0 0 0
P5 0 5 2 1 0 8 0 4
Ahora buscamos una secuencia segura: Podemos ejecutar P4 y luego P3. Luego no podemos ejecutar ninguno de los procesos restantes, por lo cual no existe una secuencia segura.
El requerimiento no puede ser satisfecho, aunque el proceso tiene derecho a pedirlo pues NECESIDAD(5) >= REQUERIMIENTO. El proceso es blockeado, hasta que se pueda satisfacer el requerimiento sin entrar a un estado inseguro.

Ejercicio 2)

Ejercicio a)

Dadas las matrices que se indican pruebe si el sistema se encuentra en Deadlock. Utilice el algo-ritmo de Shoshani-Coffman. En caso de estar en deadlock indique los procesos involucrados en el mismo
ALOCACION REQ/ESPERA DISPONIBLE
R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4
P1 1 1 3 2 0 1 0 0 2 0 0 0
P2 2 3 1 1 0 0 1 1
P3 5 0 0 1 1 2 0 0
P4 1 4 1 0 1 0 0 0
P5 0 5 2 1 0 3 0 0

Ejercicio b)

Observe las matrices de los 2 ejercicios anteriores. Indique si observa alguna conclusión. (Ayuda: Preste atención a las matrices ALOC y observe la matriz de Espera respecto de la matriz de Necesidad)
Buscamos una secuencia segura y encontramos: P4, P1, P2, P3, P5. Dado que existe, entonces el sistema esta en un estado seguro, por lo que no hay deadlock.

Ejercicio 3)

Indique cuáles son las condiciones necesarias para la ocurrencia del Deadlock y explíquelas (contestado al costado)
1. Exclusión Mutua: Al menos un recurso debe ser usado en forma exclusiva (no se puede compartir). Si un proceso lo desea, pero ya lo tiene otro, deberá esperar hasta que sea liberado.
2. Espera y Retenido (Hold & Wait): Debe existir un proceso que tiene retenido un recurso y está espe-rando por otro que a su vez está siendo ocupado por otro proceso.
3. Sin Desalojo: Los recursos no pueden ser desalojados, es decir que un recurso es liberado en forma voluntaria por un proceso y luego que haya finalizado su tarea.
4. Espera circular: Debe existir un conjunto de procesos {P(0), P(1),...,P(n)} tal que P(0) espera un re-curso ocupado por P(1), P(1) espera un recurso ocupado por P(2), y P(n) espera un recurso ocupado por P(0). De alguna manera esta última condición implica la de hold & wait.
Para mas informacion ver Capítulo 17 - Abrazo Mortal - Deadlock: Pagina 1-2.

Ejercicio 4)

El BCRA implementó para la cámara compensadora de fondos electrónica un sistema de transmisión diaria de los cheques recibidos en todos los bancos del país. El BCRA decidió enviar la información cifra-da mediante el algoritmo DES. Para dotar de mayor seguridad al sistema la clave DES debe cambiarse to-dos los días antes de iniciar la transmisión de los cheques. Indique una forma segura de lograr esto. Existe un único canal de comunicación y la distancia es tal que la frecuencia de cambios no puede ser satisfecha por medio de mensajeros o correo.
Proponga una solución en la cual sea esto posible, o sea que por cada sesión de comunicación sea posi-ble utilizar una clave DES distinta.
Resuelto en el Segundo Parcial del Primer Cuatrimestre del 2003 - 10/06/2004.

Ejercicio 5)

Supongamos un sistema en el cual existen 300 usuarios, de los cuales solamente los usuarios U1 y U2 pueden acceder como máximo "m" y "n" veces respectivamente al objeto O1.
i) Qué esquema de protección conviene utilizar.
ii) Muestre la implementación de dicho esquema de protección.
PREGUNTAR.

Ejercicio 6)

Sea la siguiente matriz de accesos
OBJETODOMINIO O1 O2 O3 D1 D2 D3 D4
D1 READ 8 – 10 hs
D2 EXEC OWNER 10 – 15 hs CONTROL SWITCH
D3 OWNER READ 0 – 22 hs * CONTROL SWITCH
D4 EXEC R/W * OWNER
a)- Indicar todas las acciones que puede realizar el dominio D3 en virtud de los derechos que po-see.
b)- Puede D3 lograr grabar sobre O2 ? Explique en virtud de qué derechos puede realizarlo.
c)- Quiénes pueden acceder al objeto O3 a las 23:30 hs ? Justifique.
a. D3 puede modificar, agregar y quitar todos los permisos sobre el objeto O1. Puede leer y escribir sobre el objeto O2 ademas de copiar estos derechos a otros dominios atravez del switch que tiene con D4. Tam-bien tiene control total sobre O3 atravez del switch con D4. Y puede sacarle privilegios al dominio D1 atra-vez del control.
b. D3 puede grabar sobre O2 usando el switch que tiene con D4, pues D4 tiene acceso R/W*.
c. Al objeto O3 a las 23:30 pueden acceder D2 y D3 atravez del switch que tienen con D4, y D4 directamen-te.

Ejercicio 7)

Dada la instrucción JOIN codificada como sigue :
1) ACUMUL = COUNT
2) ACUMUL = ACUMUL - 1
3) COUNT = ACUMUL
4) IF COUNT = 0 DESPACHAR Proceso siguiente ELSE Esperar
Se pide demostrar con un ejemplo qué anomalía puede presentarse suponiendo que la codifica-ción anterior es interrumpible entre las instrucciones número 2) y 3).
Supongamos que el join es de 2 procesos, y entonces COUNT = 2. Viene el primer proceso y ejecuta hasta la instrucción 2, y luego viene otro y ejecuta todo el proceso completo, y luego el primer proceso termina la ejecucion. El COUNT termina valiendo 1, pues el primer proceso hizo la resta, pero no llego a guardarla pues antes ejecuto el otro proceso quien sobreescrivio el valor de ACUML. Esto causa que los dos procesos se queden esperando, y nunca comienze el nuevo proceso que inicia en el join cuando se juntan los dos otros procesos.

Ejercicio 8)

Dado el siguiente grafo de precedencia : (ver dibujo)
Escribalo con instrucciones fork y join, y parbegin parend. Escribalo también con semáforos.


S1
C9 = 4
Fork L3
Fork L4
S2
S5
J9:
Join C9
S9

L3:
S3
Fork L8
S7
Goto J9

L8:
S8
Goto J9

L4:
S4
Goto J9

S1
Parbegin
Begin
S2
S5
End
Begin
S3
Parbegin
S7
S8
Parend
End
S4
Parend
S9

X2 = X3 = X4 = X5 = X7 = X8 = X9 = 0.
S1: V(X2); V(X3); V(X4)
S2: P(X2); V(X5)
S3: P(X3); V(X7); V(X8)
S4: P(X4); V(X9)
S5: P(X5); V(X9)
S7: P(X7); V(X9)
S8: P(X8); V(X9)
S9: P(X9); P(X9); P(X9); P(X9)

Ejercicio 9)

Cuáles son las tres condiciones que debe cumplir cualquier solución para resolver el problema de zonas críticas. Justifique.
PREGUNTAR.

Ejercicio 10)

En la fábrica “El Huevo Feliz” se producen huevos de Pascua decorados. Hay una cinta transporta-dora circular en la cual un brazo mecánico coloca los huevos ya armados y un operario decora los hue-vos con chocolate blanco de secado ultrarrápido y los retira de la cinta transportadora.
Diseñe un algoritmo con Monitores que ayude a lograr una provisión continua de la cinta transportado-ra.
La cinta tiene lugar para 50 huevos de Pascua.
El problema es el problema del Productor – Consumidor con un buffer de tamaño 50.
programa Productor_Consumidor;
MAX = 50.
monitor M;
buffer : Array (0..MAX-1);
in, out, n; enteros;
buff_lleno, buff_vacío: condición;
procedure Almacenar (v);
begin
if n = MAX then Wait (buff_vacío);
buffer (in) = v;
in = (in + 1) mod MAX;
n = n + 1;
Signal (buff_lleno)
end;
procedure Retirar (v);
begin
if n = 0 then Wait (buff_lleno);
v = buffer (out);
out = (out + 1) mod MAX;
n = n - 1;
Signal (buff_vacio)
end;
begin (* Cuerpo del monitor *)
in, out, n = 0;
end; (* fin monitor *)
procedure Productor;
begin
v = "dato producido"
Almacenar (v)
end;
procedure Consumidor;
begin
Retirar (v);
Hacer algo con v
end;
begin Programa-Principal
Begin;
cobegin
Productor;
Consumidor
coend
end
Para mas informacion ver Capítulo 19 - Procesos Y Programacion Concurrentes: Pagina 19.