[OSC] Day4: Deadlocks

Deadlock

---

Deadlocks and conditions for deadlocks

How do they occur?

Process A and B request the resources in opposite orders and end up in deadlock

• Deadlock can occur on the same machine or between multiple machines(e.g. resources are requested over the network) and any number of resources
• Deadlocks are not just related to operating systems but also occur in databases

A resource (e.g. a device, a data record, file, semaphore) can be acquired, used, and released

• A resource can be preemptable, i.e. it can be forcefully taken away from the process without permanent adverse effect(e.g. memory -> disk)
• A resource can be non-preemptable, i.e. it cannot b taken away from a process without permanent adverse effect(e.g. CD, printer)
  If a non-preemptable resource is requested but not available, the process is made to wait
  Deadlocks only occur for non-preemtable resources since preemtable resources can be temporarily taken away to recover from the deadlock

definition

“A set of processes is deadlocked if each process in the set is waiting for an event that only the other process in the set can cause”

• each deadlocked process is waiting for a resource held by an other deadlocked process(which cannot run and hence cannot release the resources)
• This can happen between any number of processes and for any number of resources

Minimum conditions

Four conditions must hold for deadlocks to occur:

• Mutual exclusion: a resource can be assigned to at most one process at a time
• Hold and wait condition: a resource can be held whilst requesting new resources
• No preemption: resources cannot be forcefully taken away from a process
• Circular wait: there is a circular chain of two or more processes, waiting for a resource held by the other processes

No deadlocks can occur if one of the conditions is not satisfied.

---

Algorithm to detect deadlocks

Approaches to dealing with deadlocks

1. Just ignore them: Ostrich algorithm
2. Detection and recovery
3. Avoid deadlocks from happening by detecting them early
4. Avoid deadlocks from happening by breaking Coffman’s conditions

Detecting deadlocks

A graph based approach

Deadlocks can be modelled using directed graphs:

• resources are represented by squares and processes are represented by circles
• A directed arc from a square(resource) to a circle(process) means that the resource was requested and granted, i.e. is allocated to the process
• A directed arc from a circle(process) to a squared(resource) indicates that the process has requested the resouces and is waiting to obtain it

A cycle in the graph means that a deadlock occurs for the respective resources and processes

Example

If all of them run sequential, no deadlock will occur, but no multi-programming will take place
But if not

This is the directed graph it is a circle, so there will be deadlocks
If the OS were able to detect deadlocks, it could have changed the order in which the processes are executed, e.g.:
`A requests R, C requests T, A requests S
Basic graph algorithms can be used to search the graph and detect cycles
This is the second approach –Detection and recovery

A matrix based algorithm(Detection and recovery)

A matrix based algorithm is used when multiple “copies” of the same resource exist(The graph only applied to one copy of resource!!!!!)

• Let P1 to Pn denote n processes
• Let there by m resources classes:
  Let Ei denote the “existing” resources of type i
  Let Ai denote the number of available resources of type i
  The total number of allocated and available resources (Ai ) of type i is equal to Ei

The algorithm uses two vectors for the existing and available resources (E and A), and two matrices to describe the current and requested resources per process (C and R)

This might seems complicated! But we see one example

Assume C is the current allocation situation, R is the request situation.
E is the total resources situation
From C, we can know there only remains 2 Tape drives and 1 plotter, so we can came up with A=(2 1 0 0 )
So can we run process1 or process2 then? Obviously, there request can not be satisified.
Thus, we only can run process 3 first!
Then process 3 can be released and the available matrix A would be (2 1 0 0) + (0 1 2 0) = (2,2,2,0)
This time, process 2 can obtain resources and release it, there will be no deadlocks!

recovery from deadlocks(three methods)

Preemption: the resource is forcefully removed from one of the processes (this is likely to have an ill effect)
Rollback mechanisms: build in check points that allow the process to be restarted

• The check points contain the memory image and resource states
• Multiple checkpoints should be maintained
• The process that owns the “deadlocked” resources is rolled back

Kill a strategically chosen processes to release its resources

• The process should own the required type of resources
• The process should be easy to restart

---

Deadlock avoidance

Example

Assume two processes, A and B, and two resources, a plotter and a printer:
Process A needs the printer between I1 and I3, and the plotter between I2 and I4
Process B needs the plotter between I5 and I7, and the printer between I6 and I8
we can draw a picture:

The shaded regions are inaccessible (the resources would be assigned by two processes simultaneously)
The box defined by I1, I2, I5, I6 is not deadlocked, but will deadlock eventually (i.e. unsafe)

Safe state and unsafe state

A safe state is one where there is a feasible order for the processes to finish without deadlock, even if all of them were to acquire all their resources immediately
Consider the following example for a single resource, assuming that 10 entities exist for the given resource (current allocation, and MAXIMUM allocation):

We can see every process can run, it is safe state for a!
Now let’s see a unsafe example:

(d) at least need 5 free resources but we only have 4, so it is unssafe.

But unsafe doesn’t means deadlock
A state might not be in deadlocked, but still be unsafe
The “bankers algorithm” (Dijkstra) can be used to avoid deadlocks

Bankers algorithm

For a single resource:

  - Find customer closest to max resource allocation
  - Check whether remaining resources can satisfy
      the maximum request
  - Return the resources from this process to
      the set of available resources
  - Find next process closest to its max
      resource allocation
  - ...
  The state is safe iff all processes can finish,
  even when they request all their resources
  at the same time

For multiple resources:
The bankers algorithm for multiple resources is a generalisation of the bankers algorithm for a single resource
Two matrices are maintained, one for the allocated resources C, one for the remaining resources that are required R
Three vectors are maintained; the existing resources, the possessed resources, the available resources

There are there vectors on the right
E is the total(exist) resources
P is the assigned(possessed) resources
A is the available resources
Thus, E = P+A
So the banker’s algorithm for multiple resources is :

Find a row in R which all corresponding resource requirements are less or equal to A
(selection order has no influence)
-If no row satisfied this, the state is unsafe
-Else "run the process" and add its resource to A
Repeat the above until all processes have finished
-The state is safe if all processes complete successfully

So as the image shows above, there are two questions:
Q: Can process B be granted a printer?
A: Yes. we can first run D, then A =(1 0 2 0) + (1 1 0 1) = (2 1 2 1)
then we can run A or E(assume we run A first) A = (2 1 2 1)+(3 0 1 1) = (5 1 3 2)
then we can run E, A = (5 1 3 2)+(0 0 0 0)=(5 1 3 2)
then we can run B…
we can run C finally.
So, a feasible order exists(D, A, E, B, C)
Q: Can process B and E both be granted a printer?
A:TBC?

Deadlock Prevention

The maximum number of requested resources for a certain process are not always known in advance, i.e., deadlock avoidance can be difficult in practices
An alternative approach to prevent deadlocks is to undermine at least one of the four Coffman conditions：

• No preemption: forcibly remove a process’s resources
• Prevent the circular waits:
  Allow at most one resource per process at any one time (this is not always practical)
  Allocate resources a number and force resource requests to be made in numerical order

---

Q: A system has four processes and five allocatable resources. The current allocation and maximum needs are as follows:
What is the smallest value of x for which this is a safe state?
A:The needs matrix is as follows:
0 1 0 0 2
0 2 1 0 0
1 0 3 0 0
0 0 1 1 1
If x is 0, we have a deadlock immediately. If x is 1, process D can run to completion. When it is finished, the available vector is 1 1 2 2 1. Unfortunately we are now deadlocked. If x is 2, after D runs, the available vector is 1 1 3 2 1 and C can run. After it finishes and returns its resources the avail- able vector is 2 2 3 3 1, which will allow B to run and complete, and then A to run and complete. Therefore, the smallest value of x that avoids a deadlock is 2.