Ensayos

ABRAZO MORTAL DEADLOCK INTERBLOQUEO

1

DEFINICION DE DEADLOCK
Un conjunto de procesos está en estado de "DEADLOCK" cuando cada proceso del conjunto está esperando por un evento que solo puede ser causado por otro proceso que está dentro de ese conjunto.

2

PROBLEMA
Dos objetos (Procesos) desean hacer uso de un único recurso no compartible o un número finito de ellos, y cada uno deellos posee la porción que el otro necesita.
Ejemplo clásico: Dos procesos P(1) y P(2), cada uno de ellos tiene asignadas 2 unidades de cinta y cada uno de ellos necesita dos más, pero en el sistema existen sólo 4 unidades en total. Obviamente estamos en presencia de un deadlock, ya que P(1) espera recursos de P(2) y P(2) espera recursos de P(1).
3

CONDICIONES NECESARIAS PARA EL "DEADLOCK"Exclusión Mutua: debe haber recursos no compartidos de uso exclusivo. Espera y Retenido (Hold & Wait): un proceso retiene un recurso y espera por otro Sin Desalojo: no es posible quitarle el recurso retenido a un proceso. Lo libera voluntariamente. Espera circular: hay un ciclo de espera entre procesos
4

El modelo del sistema
• Tipos de recursos: R1, R2, R3,..... • Cada tipo de recurso poseeWi instancias • Cada proceso utiliza un recurso de esta forma: Pedirlo : (REQUEST) si no puede ser satisfecho esperar. Será incluido en una cola en espera de ese recurso (Tablas). Usarlo : (USE) el proceso puede operar el recurso. Liberarlo : (RELEASE) el proceso libera el recurso que fue pedido y asignado
5

GRAFO DE ASIGNACIÓN DE RECURSOS (elementos)
• Procesos • Tipo de Recurso con 4instancias • Pi pide instancia of Rj
Pi

• Pi retiene una instancia de Rj

Pi

6

GRAFO DE ASIGNACION DE RECURSOS
• Sea G = (V,E), donde V es el conjunto de vértices y E es el conjunto de flechas (arcos orientados). • A su vez V está compuesto por 2 tipos: P = {p(1),p(2),...,p(n)} Procesos • R = {r(1),r(2),......,r(m)} Recursos • conjunto de conjunto de

7

GRAFO DE ASIGNACION DERECURSOS
• Los elementos de E son: • (p(i),r(j)) ======> p(i) está esperando una instancia del recurso r(j). • (r(j),p(i)) ======> r(j) (una instancia de) está asignada al proceso p(i).

8

Un ejemplo de un grafo de asignación de recursos

9

Grafo de asignación de recursos con un Deadlock

10

GRAFO DE ASIGNACIÓN DE RECURSOS
• En caso de tipos de recursos con más de una instancia, laexistencia de un ciclo cerrado es condición necesaria, pero no suficiente. • CONCLUSION: Cuando no existe un ciclo no hay deadlock. Ahora si existe un ciclo puede o no haber deadlock. Ciclo: p(1) --> r(1)--> p(3)--> r(2)--> p(1). Si p(4) o p(2) liberan sus recursos se rompe el ciclo.
11

MANEJO DE DEADLOCK
Existen dos maneras de manejar los Deadlocks: • No permitir que ocurran ( PrevenciónEvitarlo ). • Permitirlo y luego recuperar (es caro y dificultoso).

12

PREVENCIÓN
• EXCLUSIÓN MUTUA No hay recursos exclusivos, permiso de acceso en concurrencia (todos leen), pero ... • ESPERA Y RETENIDO (Hold & Wait) Asignación Total al inicio(dos problemas, asignación sin uso, e inanición) Si tiene asignado un recurso para pedir otro debe liberar éste. • SIN DESALOJO Permitirlo. Pérdida derecursos cuando se quiere acceder a uno no disponible.
13

PREVENCION
• ESPERA CIRCULAR Numeración de recursos Para asegurar que esta condición no se cumpla consideremos lo siguiente: A cada "tipo de recurso" le asignamos un número Natural único R = {r(1),r(2),....,r(n)} F: R --> N F(impresora)=1 , F(disco)=5 , F(cinta)=7
14

PREVENCIÓN
Un proceso puede pedir un r(j) sii F(r(j)) >F(r(i)) ∀i de los recursos que ya posee. Si no cumple esta condición, debe liberar todos los r(i) que cumplen F(r(i)) ≥ F(r(j)). Es decir el proceso siempre debe solicitar los recursos en un órden creciente. Dadas estas condiciones se puede demostrar que no tendremos nunca una espera circular, es decir el sistema está libre de Deadlock
15

Estado Seguro
• Un estado "seguro" (SAFE) es cuando se...