El deadlock o interbloqueo

El interbloqueo

Situación en la que se encuentran un conjunto de procesos,

(al menos dos), tal que cada proceso del conjunto espera la
ocurrencia de un evento que sólo puede ser provocado por
otro proceso del mismo conjunto.

Dr. Roberto Gómez C. Diapo. No. 1

 El deadlock o interbloqueo

Los recursos

Tipos de recursos:

1. Recurso apropiable

Se puede tomar del proceso que lo posee

sin provocar efectos dañinos

2. Recurso no apropiable

No se puede tomar de su poseedor activo sin

provocar un error.

Secuencia de eventos necesarios para utilizar un recurso:

1. Solicitar el recurso

2. Utilizar el recurso

3. Liberar el recurso

Dr. Roberto Gómez C. Diapo. No. 2

 El deadlock o interbloqueo

Condiciones interbloqueo

1. Condición de exclusión mutua

2. Condición de posesión y espera

3. Condición de no apropiación

4. Condición de espera circular

Dr. Roberto Gómez C. Diapo. No. 3

 El deadlock o interbloqueo

Modelando interbloqueos:
i el modelo de Holt

A S D

T U

R B C

(a) (b) (c)

Gráficas de asignación de recursos. (a) Posesión de un

recurso. (b) Solicitud de un recurso. (c) Bloqueo.

Dr. Roberto Gómez C. Diapo. No. 4

 El deadlock o interbloqueo

A B C 1 A Solicitud R
Solicitud de R Solicitud de S Solicitud de T 2 B Solicitud S
Solicitud de S Solicitud de T Solicitud de R 3 C Solicitud T
Liberación de R Liberación de S Liberación de T 4 A Solicitud S
Liberación de S Liberación de T Liberación de R 5 B Solicitud T
6 C Solicitud R
bloqueo

A B C A B C A B C

R S T R S T R S T

(1) (2) (3)

A B C A B C A B C

R S T R S T R S T

(4) (5) (6)

Dr. Roberto Gómez C. Diapo. No. 5

 El deadlock o interbloqueo

1. A Solicitud R
2 C Solicitud T
2.
3. A Solicitud S
4. C Solicitud R
5. A libera R
6. A libera S
no existe
it
bloqueo

A B C A B C A B C

R S T R S T R S T

(1) (2) (3)

A B C A B C A B C

R S T R S T R S T

(4) (5) (6)

Dr. Roberto Gómez C. Diapo. No. 6

 El deadlock o interbloqueo

Areas de investigación del Interbloqueo

Prevención del interbloqueo

Condicionar un sistema para quitar cualquier
posibilidad de ocurrencia de interbloqueo
interbloqueo.

Evitar el interbloqueo
No precondiciona al usuario a quitar todas las
posibilidades
ibilid d dde iinterbloqueo.
bl

Detectar el interbloqueo
Determinar si un interbloqueo se dio o no.

Recuperarse del interbloqueo

Limpiar un sistema de interbloqueos, una vez
que fueron detectados.

Dr. Roberto Gómez C. Diapo. No. 7

 El deadlock o interbloqueo

Prevención del Interbloqueo

Havender (Hv68)

+ Negación de la condición de no apropiación

Cada proceso debe de hacer todas sus requisiciones de
recursos y no puede continuar hasta que todo le haya
sido otorgado.

+ Negación de la condición de posesión y espera

Si a uun pproceso
S oceso que retiene
et e e recursos
ecu sos asignados
as g ados se lee negó
egó
un recurso, éste debe de liberar todos los que tenía. Si
es necesario los puede pedir después.

g
+ Negación de la espera
p circular
Imponer un orden lineal de los tipos de recursos en todos
los procesos. Por ejemplo, si un proceso tiene asignados
recursos de un determinado tipo, éste sólo puede pedir
recursos de tipos posteriores en el ordenamiento.

Dr. Roberto Gómez C. Diapo. No. 8

 El deadlock o interbloqueo

Ejemplo Ordenamiento Lineal Recursos

R9
R10 .......

R8

R7

R6

R5

R4

R3

R2

R1

Dr. Roberto Gómez C. Diapo. No. 9

 El deadlock o interbloqueo

R
Resumen metodos
t d prevención
ió iinterbloqueo
t bl

Exclusión Mutua
Realizar un spooling general

Posesión y espera
Solicitar todos los recursos al principio

p p
No apropiación
Retirar los recursos

Espera circular
Ordenar los recursos en forma numérica

Dr. Roberto Gómez C. Diapo. No. 10

 El deadlock o interbloqueo

Evitando el interbloqueo
q el algoritmo
g del banquero
q

Si las condiciones necesarias para que se produzca un interbloqueo no

se pueden eliminar
=> tener cuidado con la asignación de recursos

P
Propuesto
t por Dijkstra.
Dijk t

Banquero:
Involucra un banquero que realiza prestamos y recibe pagos
de una determinada fuente de capital.
capital
Para autorizar un préstamo es necesario que el cliente sea
soluble y que no deje en banca rota al banco.

Objetivo algoritmo:
Dejar al sistema en un estado seguro después de asignar
recursos

Edo. Seguro:
g la situación total de los recursos es tal qque los usuarios
podrán terminar su trabajo

Edo. Inseguro: estado que me puede llevar a un interbloqueo

Dr. Roberto Gómez C. Diapo. No. 11

 El deadlock o interbloqueo

Ejemplo Estado Seguro e Inseguro

Ejemplo de estado seguro:

Estado I

Préstamo Actual Necesidad Máxima

Usuario 1 1 4
Usuario 2 4 6
Usuario 3 5 8
Disponibles 2

Ejemplo de estado inseguro

Estado II

Préstamo Actual Necesidad Máxima

Usuario 1 8 10
Usuario 2 2 5
Usuario 3 1 3
Disponibles 1

Dr. Roberto Gómez C. Diapo. No. 12

 El deadlock o interbloqueo

Paso de transición de edo

edo. seguro a inseguro

E d III
Estado

Préstamo Actual Necesidad Máxima

Usuario 1 1 4
Usuario 2 4 6
Usuario 3 5 8
Disponibles 2

E d IV
Estado

Préstamo Actual Necesidad Máxima

Usuario 1 1 4
Usuario 2 4 6
Usuario 3 6 8
Disponibles 1

Dr. Roberto Gómez C. Diapo. No. 13

 El deadlock o interbloqueo

El algoritmo del banquero

• Varios ejemplares de recursos del mismo tipo

• Algoritmo puede extenderse a recursos de diferentes
tipos
ti
• Consideremos la asignación de una cantidad t de
recursos ( p.e. unidades de cinta ) entre un número u
de usuarios:
– cada usuario especifica el número de cintas que
necesitará durante la ejecución de su trabajo en el
sistema
– el sistema aceptará la petición de un usuario si la
necesidad máxima de ese usuario no es mayor que la
cantidad de recursos disponibles
– un usuario puede obtener o liberar unidades de cinta
una a una
– un usuario puede esperar para obtener una cinta
adicional, sin embargo la espera es finita
– el usuario debe garantizar al sistema que las unidades
de cinta serán utilizadas y liberadas en un tiempo
finito
• El algoritmo permite la asignación de unidades de
cinta a los usuarios solamente cuando la asignación
permita/conduzca a estados seguros y no a estados
inseguros

Dr. Roberto Gómez C. Diapo. No. 14

 El deadlock o interbloqueo

Estructuras datos algoritmo

banquero

• Necesario representar el estado del sistema, para

determinar si se provocará un estado seguro o
inseguro
• M h estructuras
Muchas t t datos
d t deben
d b actualizarse
t li para
implementar el algoritmo del banquero
• Variables necesarias:
– t: número máximo de recursos
– n: número de procesos
– prestamo(i): cuantos recursos tiene asignado Pi
– max(i):número máximo de recursos solicitados por
Pi
– necesidad(i): el resto de los recursos que Pi puede
solicitar
– peticion(i): Pi requiere tantos procesos como
peticion(i) almacene
– dispo: número de recursos disponibles
n
dispo = t − ∑ prestamo(i)
i =n

Dr. Roberto Gómez C. Diapo. No. 15

 El deadlock o interbloqueo

El algoritmo del Banquero

1. Si ( peticion(i) ≤ necesidad(i) )
i all paso 2
ir
sino
error --> proceso excedió su necesidad máxima
2. Si ( peticion(i) ≤ dispo )
ir al paso 3
sino
Pi debe esperar ya que no hay recursos disponibles
3. El sistema asigna los recursos pedidos al proceso Pi
modificando el estado del sistema de la siguiente
forma:
dispo = dispo
di di - petición(i);
i ió (i)
prestamo(i) = prestamo(i) + petición(i);
necesidad(i) = necesidad(i) - petición(i);

Si el estado después de la asignación es seguro:

=> la transacción es completada y Pi obtiene sus recursos.
Si el estado es inseguro:
=> entonces Pi debe esperar por petición(i) y el antiguo estado
de asignación de recursos es reestablecido.

Dr. Roberto Gómez C. Diapo. No. 16

 El deadlock o interbloqueo

Algoritmo Detección de Estado del Sistema

Un algoritmo para verificar si el sistema de detección se

encuentra en estado seguro o inseguro es el siguiente:

1. Declaración e inicialización de variables:

trabajo
j = dispo;
p
terminado[1...n] inicializado en falso;
2. Encontrar i de forma que:

( ) terminado [[i]] = falso;;

(a)
(b) necesidad( i) ≤ trabajo

si i no existe ==> ir a 4
sii no ==> ir
i a3
3. trabajo = trabajo + prestamo(i);
terminado[i] = verdadero;
ir a 2;
4. si terminado[i] = verdadero (para toda i)
==> sistema está en un estado seguro
sino
el sistema esta en un estado inseguro

Dr. Roberto Gómez C. Diapo. No. 17

 El deadlock o interbloqueo

Ejemplo algoritmo

Considere el siguiente escenario:

Se cuenta con 4 recursos disponibles, y el resto

esta distribuido de la siguiente forma:

P
Proceso RA N M
Nec Max. Necesidad
N id d
prestamo(i) necesidad(i)
P1 1 4 3
P2 2 6 4
P3 5 8 3

Ahora bien el proceso P2 solicita 2 recursos,

ppor lo qque la tabla anterior se actualiza:

Proceso RA Nec Max. Necesidad

prestamo(i) necesidad(i)
P1 1 4 3
P2 4 6 2
P3 5 8 3

di
dispo = 4 -2
2=2

Dr. Roberto Gómez C. Diapo. No. 18

 El deadlock o interbloqueo

Ahora hay que verificar que no se crea un edo. inseguro

Paso 1)
trabajo = dispo = 2

P1 P2 P3
préstamo(i) 1 4 5
necesidad(i) 3 2 3
terminado(i) F F F

Paso 2)
i tal que (terminado[i] = falso) y (necesidad[i] ≤ trabajo)
==> i = 2

Paso 3)
trabajo = trabajo + prestamo[2] = 2 + 4 = 6
terminado[2] = V

la tabla queda de la siguiente forma:

P1 P2 P3
préstamo(i) 1 4 5
necesidad(i) 3 2 3
terminado(i) F V F

Dr. Roberto Gómez C. Diapo. No. 19

 El deadlock o interbloqueo

Paso 2)
i tal que (terminado[i] = falso) y (necesidad[i] ≤ trabajo)
==> i = 1
Paso 3)
trabajo = trabajo + prestamo[1] = 6 + 1 = 7
t
terminado[1]
i d [1] = V
la tabla queda de la siguiente forma:
P1 P2 P3
préstamo(i) 1 4 5
necesidad(i) 3 2 3
terminado(i) V V F

Paso 2))
i tal que (terminado[i] = falso) y (necesidad[i] ≤ trabajo)
==> i = 3
Paso 3)
trabajo = trabajo + prestamo[3] = 7 + 5 = 12
terminado[3] = V
la tabla queda de la siguiente forma:
P1 P2 P3
préstamo(i)
ét (i) 1 4 5
necesidad(i) 3 2 3
terminado(i) V V V

Paso 3) No hay => Paso 4: terminado[i]=V para toda i

Dr. Roberto Gómez C. Diapo. No. 20

 El deadlock o interbloqueo

La detección del interbloqueo

- Sistema no intenta evitar los bloqueos, sino que dejan que

aparezcan

- Deja que aparezcan y después lleva a cabo una acción para

recuperarse

- Existen dos tipos:

1 Detección
1. ió interbloqueo
i bl con un recursos de
d cada
d
tipo

2. Detección interbloqueo de varios recursos de cada

tipo

Dr. Roberto Gómez C. Diapo. No. 21

 El deadlock o interbloqueo

Detección interbloqueo
(un recurso de cada tipo)

En el caso de que solo exista un recurso de cada tipo, para

detectar un interbloqueo basta con detectar un ciclo en el grafo
d asignaciones
de i i
R A B

C S D T E

F U V

W G
D T E
(a) Gráfica de recursos

U V
(b) Ciclo extraido de (a)

Dr. Roberto Gómez C. Diapo. No. 22

 El deadlock o interbloqueo

Detección Interbloqueo
(varios recursos de cada tipo)

Es necesario utilizar dos matrices: asignación y disponible

Recursos en existencia
(E1,E2,E3,..., Em)

Matriz de asignación actual

C11 C12 C13 . . . C1m

Renglón n es la asignación C21 C22 C23 . . . C2m
actual para el proceso n. . . . .
: : : : . . .
. . . .
Cn1 Cn2 Cn3 . . . Cnm

Recursos disponibles
(A1,A
A2,A
A3,..., Am)

Matriz de solicitudes

R11 R12 R13 . . . R1m

1
R21 R22 R23 . . . R2m
. . . .
.: :. :. : .
. . . .
El renglón 2 es lo que
Rn1 Rn2 Rn3 . . . Rnm
necesita el proceso 2

Dr. Roberto Gómez C. Diapo. No. 23

 El deadlock o interbloqueo

Algoritmo de asignación

Cada recurso debe estar asignado o disponible, por lo que:

m
∑ Cij + Aj = Ej
i =1

Algoritmo se basa en la comparación de vectores:

A ≤ B cada elemento vector A es menor o igual que
el elemento correspondiente de B, es decir:
A ≤ B ⇔ Ai ≤ Bi ∀ ( 0 ≤ i ≤ m)

El algoritmo de detección de bloqueos es el siguiente:

1 Se busca un proceso no marcado Pi, para que el i-ésimo

1. i ésimo
renglón de R sea menor o igual que A
2. Si se encuentra tal proceso, se suma el i-ésimo renglón
de C a A, se marca el proceso y se regresa al paso 1.
3 Si no existe
3. i tall proceso, ell algoritmo
l i termina
i

Al concluir el algoritmo, los procesos no marcados, de existir

alguno,
l están
á bloqueados.
bl d

Dr. Roberto Gómez C. Diapo. No. 24

 El deadlock o interbloqueo

Ejemplo de aplicación

Recursos en existencia Recursos disponibles

mpresoras
Imppresoras

D ROM
Unidades
D ROM
Unnidades

dee cinta

Plloters
de cinta

Plooters

CD
Im
CD

U
E = ( 4 2 3 1) A= (2 1 0 0)

Matriz de asignación actual Matriz de solicitudes

0 0 1 0 2 0 0 1

C= 2 0 0 1 R= 1 0 1 0

0 1 2 0 2 1 0 0

Dr. Roberto Gómez C. Diapo. No. 25

 El deadlock o interbloqueo

Recuperación de un interbloqueo

Una vez que se detectó un interbloqueo:

se necesita una forma de recuperarse y lograr que

el sistema continúe nuevamente

Existen
i varias
i técnicas,
é i (ninguna
( i de
d ellas
ll interesante):
i )

1. Recuperación mediante la apropiación

2. Recuperación mediante rollback

3. Recuperación mediante la eliminación de procesos

Dr. Roberto Gómez C. Diapo. No. 26

 El deadlock o interbloqueo

Apropiación

• Selección de la víctima
– cuales recursos de cuales procesos se deben
expropiar
– orden de expropiación para minimizar el costo
– factores costo: número de recursos que un
proceso tiene asignados, y el tiempo que un
proceso bloqueado ha consumido
• Retroceso (rollback)
– que debe hacerse con el proceso víctima
– no puede continuar con su ejecución normal
– se debe regresar el proceso a un estado seguro y
reiniciarlo en ese estado
• Inanición (hambruna)
– como asegurarse de que no habrá inanición
– como garantizar
ti que no siempre
i se expropiaran
i
los recursos del mismo proceso
– un proceso debe ser elegido como víctima un
número finito, ((chico)) de veces
– solución común: incluir número retrocesos como
factor de costo
Dr. Roberto Gómez C. Diapo. No. 27
 El deadlock o interbloqueo

Eliminación

• Dos opciones:
p
– abortar todos los procesos bloqueados
– abortar un proceso a la vez hasta eliminar el ciclo
de bloqueo mutuo
• Terminación forzada de un proceso podría
no ser fácil (proceso estaba actualizando un
archivo; imprimiendo)
• Factores en la selección de los procesos
– Prioridad del proceso
– Tiempo que ha trabajado el proceso y tiempo que
le resta antes de llevar a cabo su tarea designada
– cuantos recursos ha usado el proceso y de que
tipo (los recursos se pueden expropiar fácilmente)
– cuantos
t recursos adicionales
di i l necesita it ell proceso
para terminar su tarea
– cuantos procesos habrá que abortar
– los procesos son interactivos o por lotes

Dr. Roberto Gómez C. Diapo. No. 28

 El deadlock o interbloqueo

Combinando métodos
• Investigadores argumentan que ninguna técnica
estrategia por si sola es apropiada para el manejo del
deadlock
• Una posibilidad es combinar ciertas técnicas y permitir
el uso de la estrategia para cada clase de recursos
• Considerar sistema que maneja cuatro de los siguientes
recursos:
– recursos internos: recursos usados por el sistema como un
bloque de control de proceso
– memoria central: memoria usada por trabajo de un usuario
– recursos de trabajo: dispositivos asignables (como
unidades de cinta) y archivos
– espac
espacio
o intercambiable:
te ca b ab e: espacio
espac o pa
paraa cada trabajo
t abajo de
usuario en el almacenamiento auxiliar
• Solución mixta:
– recursos internos: ordenamiento de recursos
– memoriai principal:
i i l expropiación
i ió
– recursos trabajos: evitar, ya que información se puede
obtener de las tarjetas de control de trabajos
– espacio intercambiable: preasignación

Dr. Roberto Gómez C. Diapo. No. 29