Inf-3240 Presentacion sobre Interbloqueos.ppt

Presentacion sobre Interbloqueos

1. Sistemas operativos: una visión aplicada
Capítulo 6
Interbloqueos

2. Sistemas operativos: una visión aplicada 2 © J. Carretero, F. García, P. de Miguel, F. Pérez
Contenido
•Introducción
•Tipos de recursos
•Modelo del sistema
•Definición y caracterización del interbloqueo
•Tratamiento del interbloqueo
•Detección y recuperación del interbloqueo
•Prevención del interbloqueo
•Predicción del interbloqueo
•Tratamiento del interbloqueo en los sistemas operativos

3. Sistemas operativos: una visión aplicada 3 © J. Carretero, F. García, P. de Miguel, F. Pérez
Introducción
•Procesos compiten por recursos y se comunican entre sí
•S.O. proporciona mecanismos de comunicación y sicronización
•No basta: Conflicto entre necesidades de procesos puede causar
bloqueo indefinido
–Interbloqueo (deadlock)
•Problema conocido y estudiado pero poca repercusión práctica
•Aparece en otras disciplinas informáticas (p.e. Bases de datos)
•Múltiples ejemplos de la vida cotidiana
–Carretera de 2 sentidos con puente donde sólo cabe 1 coche
–2 personas llamándose por teléfono mutuamente

4. Sistemas operativos: una visión aplicada 4 © J. Carretero, F. García, P. de Miguel, F. Pérez
Caracterización
•Interbloqueo se caracteriza por la existencia de:
–Cjto. de entidades activas que usan un cjto. de recursos
•Entidades activas
–Procesos y threads
•Recursos
–Físicos:
•UCPs, memoria, dispositivos. etc.
–Lógicos:
•archivos, semáforos, mutex, cerrojos, mensajes, señales, etc.

5. Sistemas operativos: una visión aplicada 5 © J. Carretero, F. García, P. de Miguel, F. Pérez
Tipos de recursos
•Reutilizables o consumibles
–¿Sigue existiendo después de usarse?
•Uso dedicado o compartido
–¿Pueden usarlo varios procesos simultáneamente?
•Con uno o múltiples ejemplares
–¿Existen múltiples ejemplares del mismo recurso?
•Expropiables o no expropiables
–¿Es factible expropiar el recurso cuando se está usando?

6. Sistemas operativos: una visión aplicada 6 © J. Carretero, F. García, P. de Miguel, F. Pérez
Recursos reutilizables
•Todos los recursos físicos
•Algunos lógicos (archivos,
cerrojos, mutex, ...)
Primer ejemplo de interbloqueo
Proceso P1 Proceso P2
Solicita(C)Solicita(I)
Solicita(I)Solicita(C)
Uso de rec.Uso de rec.
Libera(I) Libera(C)
Libera(C) Libera(I)
Ejecución sin interbloqueo
P
1: solicita(C)
P
1: solicita(I)
P
2
: solicita(I)  bloqueo
P
1: libera(I)
P
2: solicita(C)  bloqueo
P
1
: libera(C)
P
2: libera(C)
P
2
: libera(I)
Ejecución con interbloqueo
P
1
: solicita(C)
P
2: solicita(I)
P
2: solicita(C)  bloqueo
P
1
: solicita(I)  interbloqueo

7. Sistemas operativos: una visión aplicada 7 © J. Carretero, F. García, P. de Miguel, F. Pérez
Recursos consumibles
•Proceso genera recurso y otro lo consume
•Recursos asociados a comunicación y sincronización
–mensajes, señales, semáforos, ...
•Ejemplo: Interbloqueo inevitable (“estructural”)
Proceso P
1
Proceso P
2
Proceso P
3
Enviar(P
3
) Recibir(P
1
) Recibir(P
2
)
Recibir(P
3
) Enviar(P
3
) Enviar(P
1
)
Enviar(P
2
) Recibir(P
1
)

8. Sistemas operativos: una visión aplicada 8 © J. Carretero, F. García, P. de Miguel, F. Pérez
Recursos reutilizables y consumibles
•En general, procesos usan ambos tipos de recursos
–No hay solución general eficiente
•Exposición se centra en recursos reutilizables
•Ejemplo mixto:
Proceso P
1
Proceso P
2
Solicita(C)Solicita(C)
Enviar(P
2
) Recibir(P
1
)
Libera(C) Libera(C)
Si P
2 obtiene C  interbloqueo

9. Sistemas operativos: una visión aplicada 9 © J. Carretero, F. García, P. de Miguel, F. Pérez
Uso dedicado o compartido
•Recursos compartidos no afectan a interbloqueos
•Puede haber recursos con ambos tipos de uso
–En solicitud debe indicarse el modo de uso deseado
•Si compartido: concedido si no se está usando en m. exclusivo
•Si exclusivo: concedido si no se está usando
–Por ejemplo, cerrojos sobre archivos
–No tratados en la exposición

10. Sistemas operativos: una visión aplicada 10 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Con uno o múltiples ejemplares
•Modelo general: N unidades de cada recurso
–Solicitud de varias unidades de un recurso
–Ejemplos: sistema con varias impresoras, la memoria, ...
Ejemplo: Memoria disponible: 450KB
Proceso P
1
Proceso P
2
Solicita(100K) Solicita(200K)
Solicita(100K) Solicita(100K)
Solicita(100K)
Si P
1
satisface 2 primeras y P
2
satisface 1ª  interbloqueo

11. Sistemas operativos: una visión aplicada 11 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Expropiables o no expropiables
•Algunas soluciones basadas en expropiación:
–Salvar estado de recurso y asignarlo a otro proceso
–No siempre posible eficientemente: p.ej. plotter
•Ejemplos de recursos expropiables:
–Procesador:
•Cambio de proceso = Expropiación
•Estado de procesador copiado a BCP
–Memoria virtual:
•Reemplazo = Expropiación
•Contenido de página copiado a swap
–Ejemplo de interbloqueo potencial:
•P1 listo (espera UCP) y tiene asignada cinta
•P2 en ejecución (tiene UCP) solicita cinta
•¿Cómo lo resuelve el S.O.?

12. Sistemas operativos: una visión aplicada 12 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Modelo del sistema
•Conjunto de procesos o threads
•Conjunto de recursos de uso exclusivo (N unidades/recurso)
•Relaciones entre procesos y recursos:
–Asignación: nº unidades asignadas a cada proceso
–Pendientes: nº unid. pedidas pero no asignadas por proceso
•Primitivas genéricas:
–Solicitud (R
1
[U
1
],...,R
n
[U
n
])
•U
1
unidades del recurso 1, U
2
del recurso 2, etc.
•Si todos disponibles, se concederá
•Si no, se bloquea proceso sin reservar ningún recurso
–Liberación (R
1
[U
1
],...,R
n
[U
n
])
•Puede causar desbloqueo de otros procesos
•Carácter dinámico del sistema:
–procesos y recursos aparecen y desaparecen

13. Sistemas operativos: una visión aplicada 13 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Representación mediante grafo de asignación
•Nodos {N}: Procesos {P} + Recursos {R}
–Asociado a cada R
i valor que indica nº de unidades existentes
•Aristas {A}:
–Asignación (R
i
P
j
): P
j tiene asignada 1 unidad de R
i
•Unidades asignadas de R
i
 Unidades existentes
–Solicitud (P
i
R
j
): P
i tiene pedida y no concedida 1 unid. de R
j
•Solicitud de recursos de P
i: ¿Todos disponibles?
–Sí: Por cada R
j tantas aristas R
j
P
i
como unidades solicitadas
–No: Por cada R
j tantas P
i
R
j
como unidades solicitadas
•Cuando disponibles se cambian a R
j
P
i

•Liberación de recursos de P
i:
–Eliminar aristas R
j
P
i
correspondientes

14. Sistemas operativos: una visión aplicada 14 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Ejemplo 1 de representación con grafo
•Ejecución de 3 procesos con 3 recursos R
1
(2), R
2
(3) y R
3
(2)
1.P
1: solicita(R
1[2])  solicita 2 unidades
2.P
2
: solicita(R
2
[1])
3.P
2: solicita(R
1[1])  se bloquea
4.P
3: solicita(R
2[1])
5.P
3
: solicita(R
2
[1])
6.P
1: solicita(R
2[1], R
3[2])  se bloquea
•Grafo resultante:
N={P
1
,P
2
,P
3
,R
1
(2),R
2
(3),R
3
(2)}
A={R
1
P
1
,R
1
P
1
,R
2
P
2
,P
2
R
1
,R
2
P
3
,
R
2
P
3
,P
1
R
2
,P
1
R
3
,P
1
R
3
}

15. Sistemas operativos: una visión aplicada 15 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Representación gráfica del ejemplo
P 1 P 3
1
2
3
4
P 2
R 1 R 2 R 3
5
6

16. Sistemas operativos: una visión aplicada 16 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Ejemplo 2 de representación con grafo (1unid/rec)
1.P
1
: solicita(R
1
)
2.P
2
: solicita(R
2
)
3.P
2
: solicita(R
1
)  bl.
4.P
3
: solicita(R
2
)  bl.
5.P
4
: solicita(R
3
)
6.P
1
: solicita(R
2
)
R2
1
23
6
P1 P3
4
P4P2
R1 R3
5
N={P
1
,P
2
,P
3
,P
4
,R
1
(1),R
2
(1),R
3
(1)}
A={R
1
P
1
,R
2
P
2
,P
2
R
1
,P
3
R
2
,R
3
P
4
,P
1
R
2
}

17. Sistemas operativos: una visión aplicada 17 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Representación matricial
•Rec. existentes E (dim p): E
i cuántas unid de R
i hay en el sistema
•Asignación A (dim pxr): A[i,j] unid de R
j
asignadas a P
i
•Solicitud S (dim pxr):S[i,j] unid de R
j
pedidas y no concedidas a P
i
•Rec. disponibles D (dim p): D
i cuántas unid de R
i hay disponibles
–Deducible de E y A, su uso facilita descripción de algoritmos
•Solicitud de recursos de P
i: ¿Todos disponibles?
–Sí: Por cada R
j, A[i,j]= A[i,j]+ U
j
(unidades solicitadas de R
j)
–No: Por cada R
j
, S[i,j]= S[i,j]+ U
j
•Cuando disponibles se resta U
j
de S[i,j] y se suma a A[i,j]
•Liberación de recursos de P
i:
–Por cada R
j, A[i,j]= A[i,j]- U
j
(unidades solicitadas de R
j)

18. Sistemas operativos: una visión aplicada 18 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Ejemplo 1 de representación matricial
•Ejecución de 3 procesos con 3 recursos R
1
(2), R
2
(3) y R
3
(2)
1.P
1
: solicita(R
1
[2])  solicita 2 unidades
2.P
2
: solicita(R
2
[1])
3.P
2
: solicita(R
1
[1])  se bloquea
4.P
3: solicita(R
2[1])
5.P
3
: solicita(R
2
[1])
6.P
1: solicita(R
2[1], R
3[2])  se bloquea
•Matriz resultante:
2 0 0 0 1 2
A= 0 1 0 S= 1 0 0E=[2 3 2] D=[0 0 2]
0 2 0 0 0 0

19. Sistemas operativos: una visión aplicada 19 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Ejemplo 2 de representación matricial (1unid/rec)
•Ejecución de 3 procesos con 3 recursos R
1
(2), R
2
(3) y R
3
(2)
1.P
1
: solicita(R
1
)
2.P
2
: solicita(R
2
)
3.P
2
: solicita(R
1
)  se bloquea
4.P
3
: solicita(R
2
)  se bloquea
5.P
4
: solicita(R
3
)
6.P
1
: solicita(R
2
)
•Matriz resultante:
1 0 0 0 1 0
A= 0 1 0 S=1 0 0 E=[1 1 1] D=[0 0 0]
0 0 0 0 1 0
0 0 1 0 0 0

20. Sistemas operativos: una visión aplicada 20 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Definición de interbloqueo
•Cjto. de procesos tal que cada uno está esperando un recurso que
sólo puede liberar (generar, si consumibles) otro proceso del cjto
–No es requisito bloqueo: puede haber espera activa
•Condiciones para interbloqueo (Coffman):
–Exclusión mutua. Recursos de uso exclusivo.
–Retención y espera. Mientras proc. espera por recursos
pedidos, mantiene los ya asignados.
–Sin expropiación. No se expropian recursos asignados.
–Espera circular. Existe lista circular de procesos tal que
cada proceso espera por recurso que tiene siguiente proceso.
•Son necesarias pero no suficientes:
–Ejemp. 1 y 2 las cumplen pero sólo en el 2º hay interbloqueo

21. Sistemas operativos: una visión aplicada 21 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Condición necesaria y suficiente
•Idea base: Visión “optimista” del estado actual
–Proceso no bloqueado debería devolver recursos en el futuro
–Recursos liberados desbloquearían otros procesos
–Esos procesos liberarían recursos desbloqueando a otros, etc.
•Reducción del sistema por proceso P
–Si se pueden satisfacer necesidades de P con rec. disponibles
–Nuevo estado hipotético donde P ha liberado todos sus rec.
•Condición necesaria y suficiente:
 secuencia de reducciones desde estado actual que incluya a
todos los procesos
–Si no: procesos no incluidos están en interbloqueo
•Sistemas con restricciones son más sencillos:
–Si 1 unid/rec  Cond. de Coffman necesarias y suficientes

22. Sistemas operativos: una visión aplicada 22 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Tratamiento del interbloqueo
•Detección y recuperación. Dejar que se produzca, detectarlo y
recuperarse del mismo.
–Coste de algoritmo + pérdida del trabajo realizado
•Prevención. Asegura que no ocurre fijando reglas para pedir rec.
–Infrautilización de rec.: se deben pedir antes de necesitarlos
•Predicción. Asegura que no ocurre basándose en conocimiento
de necesidades futuras de los procesos
–Dificultad de conocer futuro
–Coste de algoritmo + Infrautilización de recursos
•Ignorar el problema: Utilizada por la mayoría de los SS.OO.
–Dada la baja probabilidad de que ocurra y el coste que
conlleva evitarlo (infrautilización y/o coste de algoritmos).

23. Sistemas operativos: una visión aplicada 23 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Detección del interbloqueo
•Aplicación del concepto de reducción
–Esta presentación se limita a alg. para rep. matricial
•Para sistemas con restricciones, algoritmos más sencillos:
–Si 1 unid/rec  Cond. de Coffman necesarias y suficientes
•Espera circular  ciclo en grafo
•Sólo necesario comprobar que no ciclo en grafo O(pr))
R2
1
23
6
P1 P3
4
P4P2
R1 R3
5
Ejemplo 2 tiene interbloqueo

24. Sistemas operativos: una visión aplicada 24 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Algoritmo de detección
•Reducción por P
i:
–Si S[i]D (recs. disponibles satisfacen necesidades)
• D= D+A[i](devolver los recursos asignados)
•Algoritmo de complejidad O(p
2
r):
S=;
Repetir {
Buscar P
i
no incluido en S tal que S[i] D;
Si Encontrado {
Reducir por P
i
: D = D + A[i]
Añadir P
i
a S;
}
} Mientras (Encontrado)
Si (S==P) No hay interbloqueo
Si no: Procesos en P-S están en interbloqueo

25. Sistemas operativos: una visión aplicada 25 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Ejemplo de aplicación del algoritmo (1/3)
•Matriz inicial:
2 0 0 0 1 2
A= 0 1 0 S= 1 0 0E=[2 3 2] D=[0 0
2]
0 2 0 0 0 0
P 1 P 3P 2
R 1 R 2 R 3
Primera iteración:
–Estado inicial: S=
–Red. por P
3
(S[3]D)
D=D+A[3]=[022]
–S={P
3
}

26. Sistemas operativos: una visión aplicada 26 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Ejemplo de aplicación del algoritmo (2/3)
•Segunda iteración (D=[022]):
–Red. por P
1
: S[1]D([012][022])
D=D+A[1]=[022]+[200]=[222]
–S={P
3,
P
1
}
P 1 P 3P 2
R 1 R 2 R 3

27. Sistemas operativos: una visión aplicada 27 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Ejemplo de aplicación del algoritmo (3/3)
•Tercera iteración (D=[222]):
–Red. por P
2
: S[2]D([100][222])
D=D+A[2]=[222]+[010]=[232]
–S={P
3,
P
1,
P
2
}
P 1 P 3P 2
R 1 R 2 R 3

28. Sistemas operativos: una visión aplicada 28 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Activación del algoritmo de detección
•¿Con qué frecuencia se ejecuta?
–Algoritmo tiene coste pero, cuanto antes de detecte, mejor
•Supervisión continua:
–Por cada petición que no puede satisfacerse
–Puede tener coste demasiado alto
•Supervisión periódica:
–Guiada por tiempo y/o por detección de síntomas
•P.ej. Uso de UCP < umbral con alto grado de multiprogram.

29. Sistemas operativos: una visión aplicada 29 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Recuperación del interbloqueo
•Una vez detectado, hay que eliminarlo
–Seleccionar sucesivamente procesos implicados y quitarles
sus recursos hasta eliminar interbloqueo
•Alternativas:
–“Retroceder en el tiempo” ejecución de proceso
•Requiere S.O. con mecanismo de puntos de recuperación
–Abortar proceso perdiendo todo su trabajo realizado
•Criterio de selección de procesos basado en:
–prioridad, nº de recursos asignados al proc., t. de ejecución,...

30. Sistemas operativos: una visión aplicada 30 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Prevención del interbloqueo
•Estrategias basadas en que no se cumpla una cond. necesaria
•“Exclusión mutua” y “sin expropiación” no se pueden relajar
–Dependen de carácter intrínseco del recurso
•Las otras dos condiciones son más prometedoras

31. Sistemas operativos: una visión aplicada 31 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Prevención basada en evitar “retención y espera”
•Sólo pueden solicitarse recursos
si no se tiene ninguno asignado
–Infrautilización
t
1
: solicita(A,B,C)
(t
1
,t
2
): sólo utiliza A
(t
2
,t
3
): utiliza A y B
t
3
: Libera(A)
(t
3
,t
4
): sólo utiliza B
(t
4
,t
5
): utiliza B y C
t
5
: Libera(B)
(t
5
,t
6
): sólo utiliza C
t
6
: Libera(C)
t
7
: solicita(D)
(t
7
,t
8
): sólo utiliza D
t
8
: Libera(D)
A
tiem po
B C D
t
1
REC URSOS
t
5
t
4
t
3
t
8
t
7
t
6
t
2

32. Sistemas operativos: una visión aplicada 32 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Prevención basada en evitar “espera circular”
•Método de las peticiones ordenadas:
–Se establece un orden total de los recursos del sistema
–Restricción: Proceso sólo puede pedir recursos en orden
–Conlleva infrautilización
•En ejemplo anterior:
–Si A<B<C<D  Proceso pide justo cuando necesita
–Si A>B>C>D  Proceso pide todo en t
1
•Se deben ordenar recursos según orden más frecuente de uso

33. Sistemas operativos: una visión aplicada 33 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Predicción del interbloqueo
•Existencia de “punto de no retorno”
•Si P
1
y P
2
obtienen su primer recurso habrá interbloqueo
•Se evita conociendo a priori plan de peticiones de cada proceso
•No concede 1 de esas peticiones aunque recursos disponibles
•El sistema debe estar siempre en un “estado seguro”
Proceso P1 Proceso P2
Solicita(C)Solicita(I)
Solicita(I)Solicita(C)
Uso de rec.Uso de rec.
Libera(I) Libera(C)
Libera(C) Libera(I)

34. Sistemas operativos: una visión aplicada 34 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Concepto de estado seguro
•“Aunque todos los procesos solicitasen en este momento sus
necesidades máximas, existe un orden secuencial de ejecución
tal que cada proceso pueda obtenerlas”
•Similar al análisis “futuro” de algoritmo de detección
–Pero usando necesidades máx en vez de peticiones actuales
•E. seguro: No interbl. usando como solicitudes necesidades máx.
•Conocimiento a priori no da información sobre uso real
Proceso P1 Proceso P2
Solicita(C)Solicita(I)
Libera(C) Solicita(C)
Solicita(I)Libera(C)
Libera(I) Libera(I)
Estado inseguro  condición
necesaria pero no suficiente
Ejemplo: no hay interbloqueo y
sí estado inseguro

35. Sistemas operativos: una visión aplicada 35 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Algoritmo de predicción
•Esta presentación se limita a alg. para rep. matricial
–Algoritmo del banquero de Dijkstra (1965)
•Requiere nueva estr. de datos: Matriz de necesidad N (dim pxr):
–N[i,j] cuántas unid adicionales de R
j
puede necesitar P
i
–Es la diferencia entre necesidades máx. y unidades asignadas
–Refleja tanto solicitudes no concedidas como futuras
•Matriz S queda recogida en N y no la usa el algoritmo
–Inicialmente contiene necesidades máx. de cada proceso
•Solicitud de recursos de Pi: ¿Todos disponibles?
–Sí: Por cada Rj, A[i,j]= A[i,j]+ Uj y N[i,j]= N[i,j]- Uj
–No: Sólo se actualiza S (que no se usa en algoritmo)
•Cuando disponibles, A[i,j]= A[i,j]+ Uj y N[i,j]= N[i,j]- Uj
•Liberación de recursos de Pi:
–Por cada Rj, A[i,j]= A[i,j]- Uj y N[i,j]= N[i,j]+ Uj

36. Sistemas operativos: una visión aplicada 36 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Algoritmo del banquero
•Determina si estado es seguro O(p
2
r)
S=;
Repetir {
Buscar P
i
no incluido en S tal que
N[i]D;
Si Encontrado {
Reducir por P
i
: D = D + A[i]
Añadir P
i
a S;
}
} Mientras (Encontrado)
Si (S==P) El estado es seguro
Si no: El estado no es seguro

37. Sistemas operativos: una visión aplicada 37 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Estrategia de predicción
•Cuando proceso realiza petición de rec. que están disponibles:
–Se calcula nuevo estado provisional transformando A y N
–Se aplica algoritmo del banquero sobre nuevo estado
–Si es seguro, se asignan recursos y nuevo estado se hace
permanente
–Si no, se bloquea al proceso sin asignarle los recursos y se
restaura el estado previo

38. Sistemas operativos: una visión aplicada 38 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Ejemplo de algoritmo del banquero (1/3)
•Estado actual del sistema (es seguro):
1 1 0 3 0 2
A= 0 1 2 N= 2 2 0 D=[2 1 2]
1 0 0 1 1 2
•Secuencia de peticiones:
–P
3 solicita 1 unidad de R
3
–P
2 solicita 1 unidad de R
1

39. Sistemas operativos: una visión aplicada 39 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Ejemplo de algoritmo del banquero (2/3)
•P
3
solicita 1 unidad de R
3
: Nuevo estado provisional
1 1 0 3 0 2
A= 0 1 2 N= 2 2 0D=[2 1 1]
1 0 1 1 1 1
•¿Estado seguro?
1. S=
2. P
3
: ya que N[3]D D=D+A[3]=[312]  S={P
3
}
3. P
1
: ya que N[1]D  D=D+A[1]=[422] S={P
3
,P
1
}
4. P
2
: ya que N[2]DD=D+A[2]=[434] S={P
3
,P
1,
P
2
}
Se acepta petición: estado provisional  estado del sistema

40. Sistemas operativos: una visión aplicada 40 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Ejemplo de algoritmo del banquero (3/3)
•P
2 solicita 1 unidad de R
1: Nuevo estado provisional
1 1 0 3 0 2
A= 1 1 2 N= 1 2 0 D=[1 1 1]
1 0 1 1 1 1
•¿Estado seguro?
1. S=
2. P
3
: ya que N[3]D D=D+A[3]=[212]  S={P
3
}
3. No hay Pi tal que N[i]D  Estado inseguro
No se acepta petición:
Se bloquea al proceso y se restaura estado del sistema

41. Sistemas operativos: una visión aplicada 41 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Limitaciones de estrategias de predicción
•Conocimiento a priori de necesidades máximas
–Difícil de obtener
–Basado en peor caso posible
•Necesidades máximas no expresan uso real de recursos
•Infrautilización de recursos
–Niegan uso de recurso aunque esté libre

42. Sistemas operativos: una visión aplicada 42 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Tratamiento del interbloqueo en los SS.OO.
•Mayoría lo ignora o no da una solución general
•Distinción entre dos tipos de recursos:
–Recursos internos (propios del S.O.)
•Usados por un proceso en modo sistema
•Uso restringido a ejecución de una llamada
•Ej. semáforo interno para acceder a t. de procesos o buffer
•Interbloqueo puede causar colapso del sistema
–Recursos de usuario
•Usados por un proceso en modo usuario
•Uso durante tiempo impredecible
•Ej. dispositivo dedicado o semáforo de aplicación
•Interbloqueo afecta a procesos y recursos involucrados

43. Sistemas operativos: una visión aplicada 43 © J. Carretero, F. García, P. de Miguel, F.
Pérez
Tratamiento del interbloqueo en los SS.OO.
•Tratamiento de recursos internos
–Código del S.O. es algo que apenas se modifica
•Se puede estudiar a priori uso de recursos
–Interbloqueo  error de programación de S.O.
–Uso de estrategias de prevención es adecuado
•Dado que tiempo de uso es breve y acotado
•Tratamiento de recursos de usuario
–Código de procesos que usan recursos es impredecible
–No hay tratamiento general para todos los recursos
–Prevención  Infrautilización
–Predicción  Dificultad de conocer información a priori
–Detección y recuperación  Demasiada sobrecarga
•Puede usarse para un único recurso
•P.ej. En 4.4BSD se usa para cerrojos sobre archivos