Interbloque.Pdf

Sistemas operativos: una visión aplicada

Capítulo 6 Interbloqueos

Contenido
• • • • • • • Introducción Modelo general del sistema Definición y 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

Sistemas operativos: una visión aplicada

1

© 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

Sistemas operativos: una visión aplicada

2

© 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 (R1[U1],...,Rn[Un])
• U1 unidades del recurso 1, U2 del recurso 2, etc. • Si todos disponibles, se concederá • Si no, se bloquea proceso sin reservar ningún recurso • Puede causar desbloqueo de otros procesos

– Liberación (R1[U1],...,Rn[Un])

• Carácter dinámico:procesos y recursos aparecen y desaparecen • Representación mediante grafo o matriz
Sistemas operativos: una visión aplicada 3 © J. Carretero, F. García, P. de Miguel, F. Pérez

Ejemplo 1 de representación con grafo
3 proc y 3 rec R1(2),R2(3),R3(2)
1. 2. 3. 4. 5. 6. P1: solicita(R1[2])→ solicita 2 P2: solicita(R2[1]) P2: solicita(R1[1])→ bloq P3: solicita(R2[1]) P3: solicita(R2[1]) P1:solicita(R2[1],R3[2])→ bloq

P1 6 1 3

P2 2 4

P3 5

R1

R2

R3

Sistemas operativos: una visión aplicada

4

© J. Carretero, F. García, P. de Miguel, F. Pérez

Ejemplo 2 de representación con grafo (1unid/rec)
P1 6 1 3 P2 2 P3 4 5 P4

1. 2. 3. 4. 5. 6.

P1: solicita(R1) P2: solicita(R2) P2: solicita(R1) → bl. P3: solicita(R2) → bl. P4: solicita(R3) P1: solicita(R2)..

R1

R2R3

Sistemas operativos: una visión aplicada

5

© J. Carretero, F. García, P. de Miguel, F. Pérez

Ejemplo 3 de representación con grafo
P1 P2 P3

R1
Sistemas operativos: una visión aplicada

R2
6

R3
© J. Carretero, F. García, P. de Miguel, F. Pérez

Definición y tratamiento de interbloqueo
• Conjunto de procesos tal que cada uno está esperando un recurso que sólo puedeliberar otro proceso del conjunto – No es requisito bloqueo: puede haber espera activa • Tratamiento del interbloqueo: – Detección y recuperación. Se detecta y se recupera – Prevención. Asegura que no ocurre fijando reglas
• Coste de algoritmo + pérdida del trabajo realizado • Infrautilización de rec.: se deben pedir antes de necesitarlos • Dificultad de conocer futuro • Coste de algoritmo +Infrautilización de recursos

– Predicción. Asegura que no ocurre basándose en conocimiento de necesidades futuras de los procesos

– 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).
7 © J. Carretero, F. García, P. de Miguel, F. Pérez

Sistemas operativos: unavisión aplicada

Detección del interbloqueo
• Algoritmo que comprueba si se cumplen condiciones de interbl. • 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...