Deadlocks

Deadlocks

1. deadlock problems

   • A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set

2. system model

   • *Resource types R1, R2, . . ., Rm : CPU cycles, memory space, I/O devices
   • Each process utilizes a resource : request, use , release
   • Each resource type Ri has Wi instances

3. Deadlock Characterization

   • 1-Mutual exclusion 2- Hold and wait 3- No preemption 4- Circular wait
     • If you can prevent at least one of the necessary deadlock conditions then you

4. Resource-Allocation Graph

   • Deadlock can be described more precisely in term of a directed graph called a system resource-allocation graph consist of :
     • set of Vertices V
       • P = {P1, P2, …, Pn} consisting of all the processes inthe system
       • R = {R1, R2, …, Rm}, the set consisting of all resource types in the system
     • set of edges E
       • request edge – directed edge P1 → Rj
       • assignment edge – directed edge Rj → Pi

5. basic facts :

   • 1- If graph contains no cycles ⇒ no deadlock
     • 2- If graph contains a cycle : a- if only one instance per resource type, then deadlock , b- if several instances per resource type, possibility of deadlock

6. Methods for Handling Deadlocks

   • We can deal with the deadlock problem in one of three ways:-
     • Use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlock state
     • Allow the system to enter a deadlock state, detect it, and recover
     • Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX

7. Deadlock Prevention

   • Mutual Exclusion
   • Hold and Wait
   • No Preemption
   • Circular Wait

8. Deadlock Avoidance

9. safe state

   • When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state

10. basic facts :

    • 1- If a system is in safe state ⇒ no deadlocks
    • 2- If a system is in unsafe state ⇒ possibility of deadlock
    • 3- Avoidance ⇒ ensure that a system will never enter an unsafe state.

11. Avoidance algorithms

    • Single instance of a resource type : Use a resource-allocation graph
    • Multiple instances of a resource type : Use the banker’s algorithm