Explain about Deadlocks.
1 Answer

System Model

  • System consists of resources

  • Resource types R₁, R₂, ..., Rm

  • CPU cycles, memory space, I/O devices

  • Each resource type R₁ has W; instances.

  • Each process utilizes a resource as follows :

    • request

    • use

    • release

Deadlock with Semaphores

  • Data :

    • A semaphore S1 initialized to 1

    • A semaphore s2 initialized to 1

  • Two processes P1 and P2

  • P1 :

    wait (sl)

    wait (s2)

  • P2 :

    wait (s2)

    wait (sl)

Deadlock Characterization

Deadlock can arise if four conditions hold simultaneously.

▪ Mutual exclusion : only one process at a time can use a resource

▪ Hold and wait : a process holding at least one resource is waiting to acquire additional resources held by other processes

▪ No preemption : a resource can be released only voluntarily by the process holding it, after that process has completed its task ...

▪ Circular wait : there exists a set {Po, P₁, Pn} of waiting processes such that Po is waiting for a resource that is held by P₁, P₁ is waiting for a resource that is held by P2, ..., P-1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by Po.

Resource-Allocation Graph

A set of vertices V and a set of edges E.

  • V is partitioned into two types :

    • P= {P₁, P2, ..., P), the set consisting of all the processes in the system
    • R={R₁, R₂, Rm}, the set consisting of all resource types in the system

      • request edge - directed edge $P_i → R_j$

      • assignment edge - directed edge $R_j → P_i$

Resource Allocation Graph Example

▪ One instance of R1

▪ Two instances of R2

▪ One instance of R3

▪ Three instance of R4

▪ T1 holds one instance of R2 and is waiting for an instance of R1

▪ T2 holds one instance of R1, one instance of R2, and is waiting for an instance of R3

▪ T3 is holds one instance of R3

Basic Facts

  • If graph contains no cycles ⇒ no deadlock
  • If graph contains a cycle →
    • If only one instance per resource type, then deadlock
    • If several instances per resource type, possibility of deadlock

Methods for Handling Deadlocks

  • Ensure that the system will never enter a deadlock state :
    • Deadlock prevention
    • Deadlock avoidance
  • Allow the system to enter a deadlock state and then recover
  • Ignore the problem and pretend that deadlocks never occur in the system.

Deadlock Prevention

Invalidate one of the four necessary conditions for deadlock :

  • Mutual Exclusion - not required for sharable resources (e.g., read-only files); must hold for non-sharable resources

  • Hold and Wait - must guarantee that whenever a process requests a resource, it does not hold any other resources

    • Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none allocated to it.
    • Low resource utilization; starvation possible
  • No Preemption :

    • If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released
    • Preempted resources are added to the list of resources for which the process is waiting
    • Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting
  • Circular Wait :

    • Impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration

Circular Wait

  • Invalidating the circular wait condition is most common.

  • Simply assign each resource (i.e., mutex locks) a unique number.

  • Resources must be acquired in order.

  • If :

first_mutex = 1

second_mutex = 5

code for thread two could not be written as follows :

    /* thread one runs in this function 
/ void *do work one (void *param)
 { pthread mutex lock (&first mutex); 
pthread mutex lock (&second mutex); * 
Do some work 
pthread mutex.unlock (&second mutex); 
pthread mutex unlock (&first mutex); 

pthread.exit(0); } 

/* thread two runs in this function

 / void do. work.two(void *param)
 { pthread_mutex lock (&second mutex);
 pthread mutex lock (&first mutex) . 
Do some work ./ 
pthread mutex unlock (&first mutex);
pthread mutex unlock (&second mutex);

Deadlock Avoidance

Requires that the system has some additional a priori information available

  • Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need

  • The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition

  • Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes

Safe State

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

▪ System is in safe state if there exists a sequence <P₁, P2¹ P₁² of ALL the processes in the systems such that for each P₁, the resources that P, can still request can be satisfied by currently available resources + resources held by all the P,, with j </</p>

▪ That is :

  • If P, resource needs are not immediately available, then P, can wait until all P, have finished
  • When P, is finished, P, can obtain needed resources, execute, return allocated resources, and terminate
  • When P, terminates, P₁+1 can obtain its needed resources, and so on

Basic Facts

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

Avoidance Algorithms

  • Single instance of a resource type
    • Use a modified resource-allocation graph
  • Multiple instances of a resource type
    • Use the Banker's Algorithm

Modified Resource-Allocation Graph Scheme

▪ Claim edge P; --> R, indicates that process P, may request resource R₁

▪ Request edge P₁ → R, indicates that process P; requests resource R₁ Claim edge converts to request edge when a process requests a resource

▪ Assignment edge R₁ → P, indicates that resource R; was allocated to process P₁ Request edge converts to an assignment edge when the resource is allocated to the process

▪ When a resource is released by a process, assignment edge reconverts to a claim edge

▪ Resources must be claimed a priori in the system

Resource-Allocation Graph Algorithm


▪ Suppose that process P, requests a resource R

▪ The request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle in the resource allocation graph

Banker's Algorithm

▪ Multiple instances of resources

▪ Each process must a priori claim maximum use

▪ When a process requests a resource it may have to wait

▪ When a process gets all its resources it must return them in a finite amount of time

Data Structures for the Banker's Algorithm

Let n = number of processes, and m = number of resources types.

▪ Available : Vector of length m. If available [j] = k, there are k instances of resource type R, available

▪ Max : n x m matrix. If Max [i,j] = k, then process P, may request at most k instances of resource type R₁

▪ Allocation : n x m matrix. If Allocation[i,j] = k then P, is currently allocated k instances of R₁

▪ Need : n x m matrix. If Need[i,j] = k, then P, may need k more instances of R, to complete its task

Need [i,j] = Max[i,j] - Allocation [i,j]

Safety Algorithm

  1. Let Work and Finish be vectors of length m and n, respectively.

Initialize : Work = Available

Finish [1] = false for i = 0, 1, ..., n-1

  1. Find an i such that both :

(a) Finish [i] = false

(b) Need, < Work

If no such i exists, go to step 4

  1. Work = Work + Allocation,

Finish[i] = true

go to step 2

  1. If Finish [i] == true for all i, then the system is in a safe state

Resource-Request Algorithm for Process $P_i$

Request, = request vector for process $P_i$. If Request, [j] = k then process $P_i$, wants k instances of resource type $R_j$

  1. If Request, ≤ Need, go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim

  2. If Request, < Available, go to step 3. Otherwise P, must wait, since resources are not available

  3. Pretend to allocate requested resources to P, by modifying the state as follows :

Available = Available - Request;

Allocation, Allocation, + Request;

Need, = Need, - Request;

  • If safe ⇒ the resources are allocated to $P_i$
  • If unsafe ⇒ P, must wait, and the old resource-allocation state is restored

Deadlock Detection

  • Allow system to enter deadlock state

  • Detection algorithm

  • Recovery scheme

Please log in to add an answer.