Cap09 Deadlocks

SISTEMAS OPERATIVOS DEPARTAMENTO DE CIENCIAS DE LA COMPUTACION UNIVERSIDAD NACIONAL DEL COMAHUE

CAPITULO 9

Deadlocks

TEMARIO











Planteo del problema Modelización Caracterización Métodos para el manejo de deadlocks Prevención Evitación Detección y recuperación Métodos combinados

Sistemas Operativos 2008

Capítulo 9

3

PLANTEO DEL PROBLEMA

Un conjunto de procesos “deadlocked” se caracteriza porque cada uno de los procesos tiene asignado un cierto recurso y se encuentra esperando por otro recurso, el cual a su vez está asignado a otro proceso del conjunto. Como consecuencia, ningún proceso del conjunto puede avanzar en su cómputo.

Sistemas Operativos 2008

Capítulo 9

4

PLANTEO DEL PROBLEMA Un primer ejemplo:  El sistema tiene 2 unidades de cinta.  Dos procesos P1 y P2 tienen cada uno asignada una de las unidades, pero necesitan la otra unidad para poder continuar su cómputo.  Ambos procesos se encuentran en estado esperando.

Sistemas Operativos 2008

Capítulo 9

5

PLANTEO DEL PROBLEMA Otro ejemplo: Dos semáforos A y B, inicializados en 1:

P0 wait (A); wait (B);

P1 wait (B) wait (A)

Si cada proceso ejecuta instrucciones alternadamente, P0 se bloqueará en el wait(B) y P1 se bloqueará en el wait(A).

Sistemas Operativos 2008

Capítulo 9

6

EJEMPLO DEL CRUCE DE UN PUENTE

 El puente tiene una sola mano de circulación.  Cada sección del puente puede verse como si fuera un recurso.  Si ocurre un deadlock, se puede solucionar si un auto retrocede (libera recursos y vuelve atrás).  Puede darse la situación que varios autos tengan que retroceder.  Es posible que ocurra starvation. Sistemas Operativos 2008

Capítulo 9

7

MODELIZACION  Un sistema tiene procesos P1, P2, . ., Pn, y tipos de recursos R1, R2, . . ., Rm (ciclos de CPU, espacio de memoria, etc.).  Cada tipo de recurso Ri tiene Wi elementos.  La interacción entre procesos y recursos es: • Un proceso requiere un recurso; • El proceso usa el recurso; • El proceso libera el recurso.

Sistemas Operativos 2008

Capítulo 9

8

CARACTERIZACION Un deadlock puede ocurrir si se dan las siguientes 4 condiciones simultáneamente:

   

Exclusión Mutua Retención y espera (hold and wait) No desalojo (no preemption) Espera circular

Sistemas Operativos 2008

Capítulo 9

9

CARACTERIZACION Exclusión Mutua: sólo un proceso a la vez puede usar un recurso. Los recursos no son compartibles.

Retención y espera: un proceso que tiene asignado al menos un recurso está en espera por recursos adicionales que están asignados a otros procesos.

Sistemas Operativos 2008

Capítulo 9

10

CARACTERIZACION No desalojo: un recurso puede ser liberado solo en forma voluntaria por el proceso que lo tiene asignado. El recurso no se le puede “quitar” al proceso que lo posee.

Espera circular: dado un conjunto de procesos {P0,P1,…,Pn}, ocurre que P0 espera por un recurso que posee P1, P1 espera por un recurso que posee P2, …, Pn–1 espera por un recurso que posee Pn, y Pn espera por un recurso que posee P0.

Sistemas Operativos 2008

Capítulo 9

11

GRAFO DE ASIGNACION DE RECURSOS Modelo gráfico para representar la relación entre procesos y recursos de un sistema en un determinado instante. Se compone de:  P = {P1, P2, …, Pn}, es el conjunto de todos los procesos en el sistema.  R = {R1, R2, …, Rm}, es el conjunto de todos los tipos de recursos del sistema.  Línea de requerimiento: línea P1 → Rj  Línea de asignación: línea Rj → Pi

Sistemas Operativos 2008

Capítulo 9

12

GRAFO DE ASIGNACION DE RECURSOS

Sistemas Operativos 2008

Capítulo 9

13

CONSIDERACIONES BASICAS  Si un grafo no contiene ciclos, entonces no hay deadlock.

 Si un grafo contiene un ciclo, entonces: • Si existe un solo elemento por cada tipo de recurso, hay deadlock. • Si hay varios elementos por cada tipo de recurso, hay posibilidad de deadlock.

Sistemas Operativos 2008

Capítulo 9

14

GRAFO DE ASIGNACION DE RECURSOS

Este grafo presenta un deadlock.

Sistemas Operativos 2008

Capítulo 9

15

GRAFO DE ASIGNACION DE RECURSOS

En este grafo hay un ciclo pero no hay deadlock.

Sistemas Operativos 2008

Capítulo 9

16

METODOS PARA EL MANEJO DE DEADLOCKS Existen 3 políticas:  Impedir que el sistema nunca caiga en un estado de deadlock (Prevención y Evitación).  Permitir que el sistema caiga en deadlock, y recuperarlo (detección con recuperación).  Ignorar el problema, pretendiendo que los deadlocks nunca ocurrirán en el sistema (política del avestruz).

Sistemas Operativos 2008

Capítulo 9

17

PREVENCION Se trata de asegurar que no se cumpla alguna (cualquiera) de las 4 condiciones de ocurrencia del deadlock: exclusión mutua, retención y espera, no desalojo y espera circular.

Sistemas Operativos 2008

Capítulo 9

18

PREVENCION Exclusión Mutua Para que no se cumpla, los recursos deben ser compartibles. No se puede aplicar en recursos que no sean compartibles como, por ejemplo, impresoras.

Sistemas Operativos 2008

Capítulo 9

19

PREVENCION Retención y espera Para que no se cumpla, si un proceso requiere algún recurso, no debe tener asignado ningún otro. Se puede forzar el no cumplimiento mediante:  Obligar a los procesos a solicitar todos los recursos antes que comiencen su ejecución;  Los procesos solo pueden requerir recursos si no tienen ninguno. Produce una baja utilización de recursos y hay posibilidad de starvation.

Sistemas Operativos 2008

Capítulo 9

20

PREVENCION No desalojo Para que no se cumpla, habrá que “quitarle” forzosamente recursos a un proceso. Se puede forzar el no cumplimiento mediante el siguiente mecanismo:  Si un proceso, que ya tiene asignados algunos recursos, solicita nuevos recursos que no están disponibles, entonces se liberan todos los recursos que tiene asignados.  Los recursos “quitados” al proceso se agregan a la lista de recursos que el proceso necesita.  El proceso podrá reiniciar su tarea solo cuando obtenga todos sus recursos (los que tenía y los nuevos que pidió).

Sistemas Operativos 2008

Capítulo 9

21

PREVENCION Espera circular

Se impone un esquema de ordenamiento para todos los tipos de recursos de modo que cada proceso requiera los recursos en un orden determinado.

Sistemas Operativos 2008

Capítulo 9

22

EVITACION Se basa en un análisis detallado que realiza el sistema ante cada requerimiento de recursos por parte de los procesos.

Para su implementación se requiere que el sistema tenga disponible algunos datos adicionales a priori de los procesos y de los recursos.

Sistemas Operativos 2008

Capítulo 9

23

EVITACION  El modelo más simple y más usado requiere que cada proceso declare el máximo número de elementos de cada tipo de recurso que puede necesitar.  Un algoritmo examina dinámicamente el estado de asignación de recursos del sistema para asegurar que no suceda la condición de espera circular.

Sistemas Operativos 2008

Capítulo 9

24

EVITACION  Cuando un proceso requiere un recurso que está disponible, el sistema debe decidir si la asignación del mismo deja al sistema en un estado seguro.  Un sistema está en un estado seguro si existe una secuencia segura para todos los requerimientos de todos los procesos (es decir, no se producirá una espera circular).

Sistemas Operativos 2008

Capítulo 9

25

EVITACION  Si el sistema está en un estado seguro, entonces no hay deadlock.  Si el sistema está en un estado inseguro, entonces existe la posibilidad de deadlock.

EVITACIÓN ES ASEGURAR QUE EL SISTEMA NUNCA ENTRE EN UN ESTADO INSEGURO. Sistemas Operativos 2008

Capítulo 9

26

DETECCION CON RECUPERACION  El sistema puede entrar en un deadlock.  Bajo determinadas condiciones se ejecuta un algoritmo de detección de deadlock.  Si se encuentra un deadlock, se debe aplicar un esquema de recuperación.

Sistemas Operativos 2008

Capítulo 9

27

ALGORITMO DE DETECCION Cuándo y con qué frecuencia invocarlo, depende de:  La frecuencia probable de ocurrencia de deadlock en el sistema;  Cantidad de procesos que será necesario volver atrás (rollback), considerando que al menos habrá uno por cada ciclo disjunto. Si es invocado arbitrariamente, puede suceder que el sistema tenga una gran cantidad de ciclos y no resulte simple determinar cuál de los muchos procesos en deadlock lo “causó”.

Sistemas Operativos 2008

Capítulo 9

28

RECUPERACION Hay dos estrategias para recuperar el sistema de un deadlock:  Abortar procesos • todos los procesos • de un proceso a la vez

 Desasignar recursos

Sistemas Operativos 2008

Capítulo 9

29

ABORTAR PROCESOS Todos los procesos Se procede a abortar la totalidad de los procesos involucrados en el deadlock. Es el método más simple pero puede resultar muy costoso en cómputo por lo realizado hasta allí por los procesos.

Sistemas Operativos 2008

Capítulo 9

30

ABORTAR PROCESOS De un proceso a la vez Se procede a abortar de a un proceso a la vez hasta verificar que se eliminó la situación de deadlock.  Implica más overhead que el método anterior, pero puede ser mejor en resultado pues muchos procesos quedarán en el sistema.  Después de abortar cada proceso se debe correr el algoritmo de detección.

Sistemas Operativos 2008

Capítulo 9

31

ABORTAR PROCESOS De un proceso a la vez Implica decidir qué orden seguir:     

Prioridad. Tiempo computado y/o tiempo que le resta. Recursos usados. Recursos necesarios para terminar. Proceso interactivo o batch

Sistemas Operativos 2008

Capítulo 9

32

DESASIGNAR RECURSOS 2 pasos: 1) Seleccionar un proceso víctima. Se aplican los mismos criterios que para abortar procesos.

2) Rollback para volver a un estado seguro anterior y reiniciar el proceso desde ese estado.

Existe posibilidad de starvation: el mismo proceso puede ser siempre elegido como víctima.

Sistemas Operativos 2008

Capítulo 9

33

MANEJO DE DEADLOCKS CON METODOS COMBINADOS Los sistemas reales en general combinan los tres métodos básicos y usan el óptimo para cada uno de los recursos del sistema.

Una técnica consiste en dividir los recursos en clases y usar la técnica más apropiada con cada clase.

Sistemas Operativos 2008

Capítulo 9

34

UN CASO GRAFICO DE DEADLOCK

Sistemas Operativos 2008

Capítulo 9

35