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);
pthread.exit(0); 
}

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