Deadlocks

Deadlocks (Bloqueo Mutuo)

Deadlocks








El problema del bloqueo mutuo Modelando deadlocks Métodos para manejar deadlocks Prevención de deadlocks Evitando deadlocks Detección de deadlocks Recuperación de un deadlock

Elo321 Deadlocks

2

Objetivos





Descripción del problema que le impide a un conjunto de procesos completar sus misiones. Presentar varios métodos para prevenir o evitar deadlocks en sistemas computacionales.

Elo321 Deadlocks

3

El Problema del Bloqueo Mutuo (1)
Un conjunto de procesos se encuentra en




deadlock, cuando cada proceso del conjunto mantiene un recurso y espera por otro mantenido por un proceso del mismo conjunto. Ejemplo usando discos (recurso de hardware)



Un sistema tiene 2 discos. P1 y P2 mantienen un disco cada uno y esperan por otro.


Ejemplo usando semáforos (recurso de software)
semáforos A y B, inicializados en 1 P0 wait (A); wait (B);

Elo321 Deadlocks

P1 wait(B) wait(A)

4

El Problema del Bloqueo Mutuo (2)


Definición:


Un conjunto de procesos {P1 P2, … Pn} se encuentra en deadlock, ssi ∀ i ∈ {1, ..n}: ∃ j ∈ {1, ..n}, j ≠ i: Pi espera por un evento de Pj .

Elo321 Deadlocks

5

El Ejemplo del Puente Colgante












Tráfico sólo en una dirección Cada sección del puente puede ser vista como un recurso Si ocurre un deadlock, éste puede ser resuelto si un usuario retrocede Puede ser que varios usuarios deban retroceder si ocurre un deadlock Puede haber inanición

Elo321 Deadlocks

6

Modelando Deadlocks


Tipo de recursos R1, R2, . . ., Rm

Ciclos de CPU, espacio en memoria, dispositivos de I/O





Cada recurso de tipo Ri tiene Wi instancias Cada proceso utiliza un recurso de la siguiente manera:




requerimiento uso liberar recurso

Elo321 Deadlocks

7

Caracterización de Deadlocks


Deadlocks pueden ocurrir ssi, se cumplan cuatro condiciones en forma simultanea:











Exclusión Mutua: sólo un proceso a la vez puede usar un recurso. Mantener y esperar (hold and wait): un proceso manteniendo al menos un recurso espera por la obtención de otro recurso. No apropiación (no preemption): un recurso es liberado sólo en forma voluntaria por el proceso que lo mantiene. Espera circular (circular wait): existe un conjunto de procesos {P0, P1, …, Pn-1} que esperan por un recurso, de tal manera de que P0 espera por un recurso mantenido por P1, P1 espera por P2, P2 … Pn-1 y Pn-1 espera por un recurso mantenido por P0.

Elo321 Deadlocks

wfg

8

Grafos de Asignación de Recursos (1)


Sea V el conjunto de vértices (o nodos) y E un conjunto de arcos.


V está particionado en dos tipos:









P = {P1, P2, …, Pn}, el conjunto de todos los procesos en el sistema R = {R1, R2, …, Rm}, el conjunto de todos los tipos de recursos en el sistema

Arco de requerimiento – arco dirigido P1 → Rj Arco de asignación – arco dirigido Rj → Pi

Elo321 Deadlocks

9

Grafos de Asignación de Recursos (2) Proceso

recurso con 4 instancias

Pi Rj Pi Rj Elo321 Deadlocks

Pi requiere una instancia de Rj

Pi mantiene una instancia de Rj

10

Ejemplo de un Grafo de Asignación de Recursos (1) R1

P1

R2

P2

R3 Elo321 Deadlocks




no hay deadlock

P3

R4 11

Ejemplo de un Grafo de Asignación de Recursos (2) R1

P1

R2

P2

R3 Elo321 Deadlocks




hay deadlock

P3

R4 12

Ejemplo de un Grafo de Asignación de Recursos (3) R1

P1

R2

P2

R3 Elo321 Deadlocks




un grafo con círculo pero sin deadlock

P3

R4 13

Conclusiones Básicas





Si un grafo no contiene círculos ⇒ no hay deadlock Si un grafo contiene círculos ⇒





si se tiene sólo una instancia por recurso, entonces hay deadlock si hay varias instancias por recurso entonces puede existir un deadlock

ELO321 Deadlocks

14

Métodos para Manejar deadlocks








Asegurar que el sistema jamás entrará en un deadlock Permitir que el sistema entre en un deadlock y luego recuperarse de esa situación Ignorar el problema, pretendiendo que un deadlock nunca ocurrirá; usado por la mayoría de los sistemas tales como Windows y Unix (conocido como el método del avestruz)

Elo321 Deadlocks

15

Previniendo Deadlocks (1)


Restringir la forma en que los procesos hacen sus requerimientos:





Exclusión Mutual – no se requiere en recursos compartidos; debe mantenerse para recursos que no se puede compartir Mantener y esperar – debe garantizar que si un proceso hace un requerimiento de un recurso, no mantenga ningún otro recurso.





requiere que un proceso solicite sus recursos antes de comenzar, o permitir que un proceso haga requerimientos de recursos sólo si no mantiene ningún recurso Utilización baja de recursos, puede haber muerte por inanición

Elo321 Deadlocks

16

Previniendo Deadlocks (2)


No Apropiación –











Si un proceso que mantiene algún recurso, requiere de otro recurso que no puede ser asignado inmediatamente, entonces todos los recursos que mantiene son liberados Los recursos liberados vuelven a ser parte de los recursos por los que el proceso está esperando El proceso continuará su ejecución, sólo después de que pueda adquirir los recursos anteriores así como los recursos nuevos

Espera Circular – imponer un ordenamiento total de todos los tipos de recursos, lo que también requiere que las solicitudes sean hechas siguiendo una numeración estrictamente ascendente

Elo321 Deadlocks

17

Evitando Deadlocks


Requiere que el sistema mantenga información a priori de los recursos a solicitar por los procesos








El modelo más simple a implementar es que el proceso declare el máximo de recursos a utilizar de cada tipo El algoritmo para evitar deadlocks, examina en forma dinámica el grafo de asignación de recursos para asegurar que no pueda ocurrir una espera circular El estado de asignación de recursos está definido por el número de recursos disponibles, asignados y el máximo demandado por los procesos.

Elo321 Deadlocks

18

Estado Seguro





Si un proceso hace un requerimiento de un recurso disponible, el sistema deberá decidir si la asignación inmediata del recurso deja al sistema en estado seguro o no El sistema está en un estado seguro si existe una secuencia de todos los procesos en el sistema de tal manera de que para cada Pi , los recursos que Pi pueda solicitar pueden ser asignados con los recursos disponibles más aquellos recursos mantenidos por todos los procesos Pj , con j < i, esto es:








Si los recursos solicitados por Pi no pueden ser asignados inmediatamente, entonces Pi deberá esperar hasta que todos los Pj hayan terminado. Si Pj ha finalizado, Pi puede obtener los recursos que requiera, ejecutar, devolver los recursos y luego terminar. Si Pi termina Pi +1 puede obtener los recursos que requiera, y así sucesivamente.

Elo321 Deadlocks

wfg

19

Conceptos Básicos








Si un sistema se encuentra en un estado seguro ⇒ no hay deadlock. Si un sistema se encuentra en un estado inseguro ⇒ hay posibilidad de deadlock. Evitar deadlocks ⇒ asegurar que un sistema nunca entrará en un estado inseguro.

Elo321 Deadlocks

20

Estado Seguro, Estado Inseguro y Estado de Deadlock deadlock

inseguro

seguro

Elo321 Deadlocks

21

Algoritmo para Evitar deadlocks





En caso de una sola instancia por recurso, usar grafo de asignación de recursos Para el caso de múltiples instancias por tipo de recurso, usar el algoritmo del banquero

Elo321 Deadlocks

22

Esquema del Grafo de Asignación de Recursos









Arco de solicitud Pi → Rj indicando que Pi puede requerir el recurso Rj,, que se representa por una línea punteada. Arco de solicitud se convierte en un arco de requerimiento. Arco de requerimiento se transforma en arco de asignación cuando el recurso se le asigna al proceso. El recurso debe solicitarse a priori en el sistema.

Elo321 Deadlocks

23

Grafo de Asignación de Recursos R1

P1

P2

R2

Elo321 Deadlocks

24

Estado Inseguro en Grafo de Asignación de Recursos R1

P1

P2

R2

Elo321 Deadlocks

25

Algoritmo del Grafo de Asignación de Recursos





Suponer que el proceso Pi requiere de un recurso Rj El requerimiento sólo puede ser atendido si el cambio de un arco de requerimiento a un arco de solicitud no deriva en la formación de un círculo en el grafo de asignación de recursos.

Elo321 Deadlocks

26

Algoritmo del Banquero









Instancias múltiples. Cada proceso debe solicitar a priori el máximo de recursos que usará. Cuando un proceso requiere un recurso puede ocurrir que deba esperar. Cuando un proceso obtiene todos sus recursos, deberá liberarlos en un tiempo finito.

Elo321 Deadlocks

27

Estructura de Datos del Algoritmo del Banquero


Sea n el número de procesos y m el número de tipos de recursos











Available: Vector de largo m. si available [j] = k, hay k instancias del recurso Rj disponible. Max: n x m matrix. Si Max [i,j] = k, entonces el proceso Pi puede requerir a lo más k instancias del tipo Rj. Allocation: n x m matrix. Si Allocation[i,j] = k entonces Pi mantiene actualmente k instancias de Rj. Need: n x m matrix. Si Need[i,j] = k, entonces Pi puede necesitar k instancias adicionales de Rj para completar su tarea. Need [i,j] = Max[i,j] – Allocation [i,j].

Elo321 Deadlocks

28

Algoritmo para Verificar Estado Seguro 1. 2. 3. 4.

Work = Available, ∀ i ∈ {1, ..n} Finish[i] = false. Find an i: (Finish[i] == false && Need[i] <= Work) else goto 4 Work += Allocation[i], Finish[i] = true, goto 2 If ∀i ∈ {1, ..n} Finish[i] == true, el sistema se encuentra en un estado seguro.

Elo321 Deadlocks

29

Algoritmo de Requerimiento de Recursos por Proceso Pi


Request = vector de requerimiento del proceso Pi. si Requesti [j] = k entonces Pi requiere k instancias del recurso de tipo Rj. 1. Si Requesti ≤ Needi goto paso 2, de lo contrario generar una excepción dado que el proceso solicita más recursos que su máximo anunciado. 2. Si Requesti ≤ Available, goto paso 3, de lo contrario Pi debe esperar, dado que los recursos no están disponibles. 3. Pretender asignar recursos requeridos por Pi , modificando el estado según: Available = Available – Request; Allocationi = Allocationi + Requesti; Needi = Needi – Requesti;





Si es seguro ⇒ el recurso es asignado a Pi. Si es inseguro ⇒ Pi debe esperar, y el estado anterior debe ser restaurado

Elo321 Deadlocks

30

Ejemplo del Algoritmo del Banquero (1)





5 procesos P0 - P4; 3 tipos de recursos: A (10 instancias), B (5 instancias), y C (7 instancias). Estado en T0: Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 4 3 3 P4 0 0 2

Elo321 Deadlocks

31

Ejemplo del Algoritmo del Banquero (1)


El contenido de la matriz Need debe ser Max – Allocation.

P0 P1 P2 P3 P4


Need ABC 743 122 600 011 431

El sistema se encuentra en un estado seguro dado que existe la secuencia < P1, P3, P4, P2, P0> que satisface el algoritmo.

Elo321 Deadlocks

32

Ejemplo: P1 Requiere (1,0,2)







Revisar que Request ≤ Available (esto es, (1,0,2) ≤ (3,3,2) ⇒ verdadero. Need Available Allocation ABC ABC ABC 010 743 230 P0 P1 302 020 P2 301 600 P3 211 011 P4 002 431 Ejecutando el algoritmo de verificación de estado seguro muestra que la secuencia < P1, P3, P4, P0, P2> satisface los requerimientos. ¿Puede asignarse el requerimiento (3,3,0) de P4? ¿Puede asignarse el requerimiento (0,2,0) de P0?

Elo321 Deadlocks

33

Detección de Deadlock








Permitir que el sistema entre en un estado de deadlock Aplicar un algoritmo de detección de deadlock Aplicar un mecanismo de recuperación

Elo321 Deadlocks

34

Una Instancia por Tipo de Recurso


Mantener un grafo espera-por (wait-for graph)









Nodos son procesos Pi → Pj si Pi espera por Pj

Periódicamente invocar un algoritmo para búsquedas de ciclos en el grafo. Si hay un ciclo, existe un deadlock. El costo de un algoritmo para búsqueda de ciclos en grafos es del orden de O(n2), con n el número de vértices del grafo.

Elo321 Deadlocks

35

Grafo de Asignación de Recursos y el Grafo de Espera-Por Respectivo R1

R5 P4

P4

R1 P1

P3

P2 R2

R3

P3

P2 R4

Grafo de Asignación de Recursos Elo321 Deadlocks

P1

R3 Grafo Espera-Por Correspondiente 36

Múltiples Instancias por Tipo de Recurso








Available: Un vector de largo m, indicando el número de tipos de recursos disponibles. Allocation: Una matriz n x m que define el número de recursos de cada tipo actualmente asignados a cada proceso. Request: Una matriz n x m indicando el requerimiento actual de cada proceso. Si Request [ij] = k, entonces el proceso Pi está requiriendo k instancias adicionales del recurso de tipo Rj.

Elo321 Deadlocks

37

Algoritmo de Detección de Deadlock (1) 1. Sea Work y Finish vectores de largo m y n, respectivamente; Inicializar: (a) Work = Available (b) Para i = 1,2, …, n, si Allocationi ≠ 0, entonces Finish[i] = false; sino Finish[i] = true.

2. Encontrar un índice i tal que: (a) Finish[i] == false (b) Requesti ≤ Work Si no existe tal i, ir a paso 4. Elo321 Deadlocks

38

Algoritmo de Detección de Deadlock (2) 3. Work = Work + Allocationi Finish[i] = true ir a paso 2. 4. Si Finish[i] == false, para algún i, 1 ≤ i ≤ n, entonces el sistema se encuentra en deadlock. Más precisamente, si Finish[i] == false, entonces Pi está en deadlock. • El algoritmo requiere de un orden de O(m x n2) operaciones para determinar si un sistema se encuentra en deadlock.

Elo321 Deadlocks

39

Ejemplo del Algoritmo de Detección de Deadlock (1)






5 proceso P0 - P4; 3 tipos de recursos A (7 instancias), B (2 instancias), y C (6 instancias). Estado en T0: Allocation Request Available ABC ABC ABC P0 0 1 0 000 000 P1 2 0 0 202 P2 3 0 3 000 P3 2 1 1 100 P4 0 0 2 002 Secuencia resulta en Finish[i] = true para cualquier i.

Elo321 Deadlocks

40

Ejemplo del Algoritmo de Detección de Deadlock (2)





P2 requiere una instancia adicional del recurso de tipo C. Request ABC P0 0 0 0 P1 2 0 1 P2 0 0 1 P3 1 0 0 P4 0 0 2 Estado del Sistema?





Puede solicitar recursos mantenidos por P0, pero es insuficiente para suplir requerimientos de otros procesos. Existe un Deadlock de los procesos P1, P2, P3, y P4.

Elo321 Deadlocks

41

Uso del Algoritmo de Detección de Deadlock


Cuando y con qué frecuencia se debe invocar depende de:



¿Cuál es la frecuencia de ocurrencia de un deadlock? ¿A cuántos procesos se les deberá aplicar un rollback?





Uno por cada círculo disjunto

Si la detección de deadlock se invoca en forma arbitraria, pueden existir muchos círculos en el grafo de recursos, lo que impedirá detectar cuál de todos los proceso ocasionó el deadlock.

Elo321 Deadlocks

42

Recuperación de un Deadlock: Término de un Proceso


Eliminar todos los procesos involucrados en el deadlock




Eliminar un proceso tras otro hasta salir del estado de deadlock




¿En qué orden se debe escoger para eliminación?









Prioridad del proceso Cuanto tiempo se ha ejecutado el proceso y cuanto le falta para terminar Recursos que el proceso ha usado Recursos que el proceso requiere para terminar Cuantos procesos deberán ser eliminados. ¿Se trata de un proceso interactivo o de tipo batch?

Elo321 Deadlocks

43

Recuperación de un Deadlock: Apropiación de un Recurso








Seleccionar una victima – minimizar el costo.

Rollback – retornar a un estado seguro, y reiniciar el proceso a partir de este estado. Inanición – el mismo proceso puede ser seleccionado como víctima; incluir el número de rollback en el cálculo del costo.

Elo321 Deadlocks

44