Brendan Ang

Search

Search IconIcon to open search

Deadlocks

Last updated Nov 8, 2022 Edit Source

# Deadlocks

A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set An example with improper semaphore usage:

# Modelling Deadlocks

# Cyclic Properties of Deadlocks

[!Having a cycle in the graph is only a necessary condition but not a sufficient condition for a deadlock.]

If each resource only has 1 instance, a cycle implies a deadlock.

# Deadlock Conditions

A deadlock may occur if these conditions hold at the same time:

  1. Mutual exclusion: Only one process at a time can use a resource instance
  2. Hold and wait: A process holding at least one resource is waiting to acquire additional resources held by other processes
  3. No preemption: A resource can be released only voluntarily by the process holding it, after that process has completed its task
  4. Circular wait: There exists a set {P0, P1, …, Pn} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for P2, …, Pn–1 is waiting for Pn, and Pn is waiting for P0

# Deadlock Prevention

As long as we are able to ensure at least one of the following conditions do not hold, we can prevent a deadlock from occurring. Example using : Each process must request for the lower numbered resource first before able to request for the higher numbered resource. This breaks the circular wait as process requests are increasing in their order (no cycle):

# Deadlock Avoidance

Rather than prevent deadlocks as they are about to occur, we can avoid entering into a state where deadlocks are possible. This state is called the unsafe state.

[! Safe state] if there exists a safe completion sequence of all processes without deadlock

A process completion sequence is safe, if for each $P_i$ , the resources that it requests can be satisfied by currently available resources + resources held by all the $Pj , j< i$

Algorithm:

  1. When a process request for resource, determine if allocation leaves the system in a safe state
  2. If safe: grant the request
  3. Else: wait

# Banker’s Algorithm

Checking whether the satisfaction of a request will lead to an unsafe state

Necessary assumptions:

  1. Each process must declare the maximum instances of each resource type that it needs
  2. When a process gets all its resources it must return them in a finite amount of time We need to keep track of some information: Let m be the number of resource types and n be number of processes

# Deadlock Detection

Allow the system to enter deadlock state, invoke detection and recovery algorithms.

# Practice Problems

a. False. If there are only 4 people, the circular wait condition is broken b. True. A single process will not be in a deadlock as there are no other processes which it is sharing resources with. Hold and wait condition can never be satisfied. c. False. Not all cycles indicate a deadlock. Depends on the number of resource instances

Deadlocks 2022-09-18 10.53.26.excalidraw a. Available -> 1. P4 allocation = 5. No process can be satisfied with available 1. Unsafe state b. Safe state. Completion order: P3, P4, P2, P1 x = 0

ProcessAllocationNeedAvailableCompleted
P02 1 10 1 00 1 0P0 Completed
P11 1 02 1 22 2 1P2 Completed
P21 1 12 0 13 3 2P1 Completed
P31 1 14 1 04 4 2P3 Completed