13
Condiciones para el interbloqueo
Enunciadas por Coffman
Exclusión mutua: un recurso está asignado a un proceso o está disponible
Retención y espera: Se pueden solicitar más recursos sin abandonar los ya obtenidos
No expulsión: Los procesos tienen que dejar los recursos explícitamente
Círculo de espera: Se produce un círculo de 2 o más procesos
14
Grafos para modelar interbloqueos
Los grafos sirven para averiguar si una determinada secuencia produce interbloqueo
R
P
R asignado a P
R
P
P bloqueado esperando R
R1
R2
D
P
Interbloqueo
15
Ejemplo
3 procesos
Planificación por turno rotatorio ===== >
El S.O puede suspender un proceso = >
A
Pedir R
Pedir S
Dejar R
Dejar S
C
Pedir T
Pedir R
Dejar T
Dejar R
B
Pedir S
Pedir T
Dejar S
Dejar T
1. A pide R
2. B pide S
3. C pide T
4. A pide S
5. B pide T
6. C pide R
R
A
S
B
T
C
2
1
3
4
5
6
1. A pide R
2. C pide T
3. A pide S
4. C pide R
5. A deja R
6. A deja S
16
Formas de tratar el interbloqueo
El algoritmo del avestruz
Esconder la cabeza y desentenderse
Unix
Detección y eliminación de interbloqueos
Controlar peticiones y liberaciones de recursos
Actualizar el grafo de recursos y comprobar que no haya bucles
Comprobar periódicamente si hay procesos que han estado bloqueados durante mucho tiempo
Prevención de interbloqueos
Predicción de interbloqueos
17
Prevención de interbloqueos
Imponer restricciones a los procesos de forma que un interbloqueo no sea posible
No habrá interbloqueo si no se cumple alguna de las 4 condiciones necesarias para el interbloqueo:
Exclusión mutua
No se puede eliminar, se puede llegar a condiciones de carrera
Retención y espera
Solicitar todos los recursos al principio
No permite utilización óptima
No se sabe a priori
Antes de solicitar un recurso, los procesos están obligados a dejar temporalmente los que tienen retenidos
No expulsión
No aconsejable
Círculos de espera
18
Círculos de espera
Retener un recurso en cada momento
No es adecuado
Dar a los recursos una numeración general.
Los recursos se solicitan en orden de numeración
El grafo no puede tener bucles cerrados
Puede ser difícil dar a los recursos una numeración adecuada
A – 1
B – 2
C – 3
D – 4
E – 5
B y luego D
pero no D y luego B
19
Predicción de interbloqueos
Evitar los interbloqueos cuando se asignen los recursos
Trayectorias de recursos
Algoritmo del banquero para un recurso
Algoritmo del banquero para múltiples recursos
20
Trayectorias de recursos
Para 2 recursos y 2 procesos
I1
I2
I3
I4
I5
I6
I7
I8
Impresora
Trazador
Impresora
Trazador
A
B
p
q
r
s
t
Ejecución de A
Ejecución de B
21
Algoritmo del banqueropara un recurso
Estado del sistema con respecto a la asignación de recursos: lista de procesos, recursos usados y máximo
No todos los procesos van a utilizar el máximo
Estado seguro: si hay una secuencia que lleve a todos los procesos a obtener sus máximos
p1
p2
p3
p4
0
0
0
0
6
5
4
7
Disponible=10
p1
p2
p3
p4
1
1
2
4
6
5
4
7
Disponible=2
p1
p2
p3
p4
1
2
2
4
6
5
4
7
Disponible=1
max
max
max
usado
usado
usado
22
Algoritmo del banquero para múltiples recursos
Ra: recursos asignados en ese momento
Rn: recursos que se necesitan todavía
E: recursos existentes
P: recursos asignados a algún proceso
D: recursos disponibles
A
B
C
D
E
Ra
3
0
1
1
0
0
1
1
1
0
0
0
0
0
1
1
1
1
0
0
R1
R2
R3
R4
A
B
C
D
E
Rn
1
1
3
0
2
0
1
1
0
1
1
0
2
0
0
0
0
0
1
1
R1
R2
R3
R4
E=(6 3 4 2)
P=(5 3 2 2)
D=(1 0 2 0)
P+D=E
23
Algoritmo de comprobación de estado seguro
Buscar fila F cuyas necesidades de recursos sean menores que D. 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 a D
Repetir los dos pasos anteriores hasta terminar todos los procesos. Si se puede terminar => estado seguro
24
Ejemplo
Estado seguro
D D=(2 1 2 1)
A D=(5 1 3 2) o E
E D=(5 1 3 2) o C
C D=(6 2 4 2)
B D=(6 3 4 2)
A
B
C
D
E
Ra
3
0
1
1
0
0
1
1
1
0
0
0
0
0
1
1
1
1
0
0
R1
R2
R3
R4
A
B
C
D
E
Rn
1
1
3
0
2
0
1
1
0
1
1
0
2
0
0
0
0
0
1
1
R1
R2
R3
R4
E=(6 3 4 2)
P=(5 3 2 2)
D=(1 0 2 0)
P+D=E
25
Ejemplo
B pide un R3 => ¿estado seguro?
A
B
C
D
E
Ra
3
0
1
1
0
0
1
1
1
0
0
0
0
0
1
1
1
1
1
0
R1
R2
R3
R4
A
B
C
D
E
Rn
1
1
3
0
2
0
1
1
0
1
1
0
2
0
0
0
0
0
0
1
R1
R2
R3
R4
E=(6 3 4 2)
P=(5 3 3 2)
D=(1 0 1 0)
P+D=E
26
Ejemplo
E pide un R3 => ¿estado seguro?
A
B
C
D
E
Ra
3
0
1
1
0
0
1
1
1
0
1
0
0
0
1
1
1
1
1
0
R1
R2
R3
R4
A
B
C
D
E
Rn
1
1
3
0
2
0
1
1
0
1
0
0
2
0
0
0
0
0
0
1
R1
R2
R3
R4
E=(6 3 4 2)
P=(5 3 4 2)
D=(1 0 0 0)
P+D=E
27
Problemas
Poca aplicación práctica:
Los procesos raramente saben la cantidad máxima de recursos que van a utilizar
El nº de procesos no es fijo
Pueden desaparecer recursos con los que se contaba
 Página anterior | Volver al principio del trabajo | Página siguiente  |