Deadlock

In case of multiprogramming environment multiple processes may compete for a finite number of resources. When a process requests for resources and if the resources are unavailable at that time then process enters into the waiting state. In some cases, this waiting state of a process never ends because the resources for which it has requested are held by other waiting processes this condition is called as deadlock.

Deadlock Characterization

Dead lock occurs when these following four conditions hold simultaneously:

1. Mutual Exclusion: At least one resource should be held in a non-shareable mode at a time only one process can use the resource. In case if another process request for the same resources it must be delayed up until the resource has been released.
2. Hold and Wait: A process holding at-least one resource and waiting to get further resources what are currently being used by other processes.
3. No-Preemption: A resource can be released only voluntary by the process that holding it after that the process has completed the task so, the resources cannot be preemptive.
4.  Circular Wait: let say a set of processes {p1,p2,….., pn} which are in  their waiting state such that process p1 is waiting for a resource that is already held by p2 and p2 is waiting for a resource that is held by p3…pn is waiting for a resource that is held by pn-1

And pn-1 is waiting for resource that is held by p1.

Resource Allocation Graph

Deadlocks can be defined more specifically in terms of a directed graph called a system resource-allocation graph.
■ A set of edges E  and a set of vertices V.
■ V is split into two types:
– P = {P1, P2, …, Pn}, the set containing of all the processes in the system
– R = {R1, R2, …, Rm}, the set containing of all resource types in the system
■ request edge – directed edge Pi ® Rj
■ assignment edge – directed edge Rj ® Pi

Resource Allocation Graph (RAG) with Deadlock

If the graph holds no cycles, then no process in the system is deadlocked. If the graph does hold a cycle, then a deadlock might exist. Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which is already held by process P3. Process P3 is waiting for both process P1 or process P2 to release resource R2. Additionally, process P1 is waiting for process P2 to release resource R1

Basic Facts:

• If graph does not contain any cycle no deadlock will occur.
• If graph holds a cycle but if only single instance perresource type then deadlock occurs and if a number of instances perresource type, then there may be possibility ofdeadlock or not.

Read Segmenttation