AB.CDE Course Website

Deadlock Handling Methods

There are three deadlock handling methods:

  1. Deadlock Prevention
  2. Deadlock Avoidance
  3. Deadlock Detection

Deadlock Prevention

Deadlock prevention works by ensuring that at least 1 of the necessary conditions for deadlock never happens.

Let’s examine each of the necessary conditions and decide whether we can prevent them from happening.

Mutual Exclusion Prevention

We typically cannot prevent deadlocks by denying the mutex condition, because some resources are intrinsically non-sharable.

For example, a mutex lock cannot be simultaneously shared by several processes.

Hold and Wait Prevention

To ensure that hold and wait never happens, we need to guarantee that whenever a process requests for a resource, it does NOT currently hold any other resources.

Possible through such protocols:

  • Protocol 1: Must have all of its resources at once before beginning execution, otherwise, wait empty handed.
  • Protocol 2: Only can request for new resources when it has none.

Example

Consider a process that needs to write from a DVD drive to disk and then print a document from the disk to the printer machine.

With protocol 1: The process must acquire all three resources: DVD drive, disk, and printer before beginning execution, even though the task with the disk and DVD drive has nothing to do with the printer. After it finishes both tasks, it releases both the disk and printer.

With protocol 2: The process requests for DVD drive and disk, and writes to the disk. Then it releases both resources. Afterwards, it submits a new request to gain access to the disk (again) and the printer, prints the document, and releases both resources.

Disadvantages

Starvation:

  • Process with protocol 1 may never start if resources are scarce and there are too many other processes requesting for it.

Low resource utilization:

  • In Protocol 1, resources are allocated at once but it is likely that they aren’t used simultaneously (e.g: the sample process requests a printer but it doesn’t utilize it when writing to disk first)
  • In Protocol B, lots of time is wasted for requesting and releasing many resources in the middle of execution.

No Preemption Prevention (Allow Preemption)

To allow preemption, we need a certain protocols in place to ensure that progress is not lost.

A process is holding some resources and requests another resource that cannot be immediately allocated to it (that is, the process must wait). We can then decide to do either protocols below:

  • Protocol 1: All resources the process is currently holding are preempted – implicitly released.
  • Protocol 2: Check first if the resources requested are held by other waiting processes or not.
    • If held by other waiting process: preempts the waiting process and give the resource to the requesting process
    • If neither held by waiting process nor available: requesting process must wait.

This protocol is often applied to resources whose state can be easily saved and restored later, such as CPU registers and memory space. It cannot generally be applied to such resources as mutex locks and semaphores.

Circular Wait Prevention

To prevent circular wait, one must have a protocol that impose a total ordering of all resource types, and require that each process requests resources according to that order.

Example

We can assign some kind of id to each resource and we need to design some acquiring protocols such as:

  • The highest priority order of currently-held resources should be less than or equal to the current resource being requested, otherwise the process must release the resources that violate this condition.
  • Each process can request resources only in an increasing order of enumeration.

This burdens the programmer to ensure the order by desig to ensure that it doesn’t sacrifice resource utilization unnecessarily.

Deadlock Avoidance

In deadlock avoidance solution, we need to spend some time to perform an algorithm to check BEFORE granting a resource request, even if the request is valid and the requested resources are now available.

This Deadlock Avoidance algorithm is called the Banker’s Algorithm. It’s job is to compute whether or not the current request will lead to a deadlock.

  • If yes, the request for the resources will be rejected,
  • If no, the request will be granted.

This algorithm is run each time a process request the shared resources.

The Banker’s Algorithm

The Banker’s Algorithm is comprised of two parts: The Safety Algorithm and the Resource Allocation Algorithm. The latter utilises the output of the former to determine whether the currently requested resource should be granted or not.

Required Attributes

Before we can run the algorithm, we need to know:

  1. Number of processes (consumers) in the system (denoted as N)
  2. Number of resource types in the system (denoted as M), along with initial instances of each resource type at the start.
  3. The maximum number of resources required by each process (consumers).

The System State

The algorithm maintains these four data structures representing the system STATE:

  1. available: 1 by M vector
  • available[i]: the available instances of resource i
  1. max: N by M matrix
  • max[i][j]: maximum demand of process i for resource j instances
  1. allocation: N by M matrix
  • allocation[i][j]: current allocation of resource j instances for process i
  1. need: N by M matrix
  • need[i][j]: how much more of resource j instances might be needed by process i

Part 1: Resource Allocation Algorithm

You shall read about this algorithm during Lab. As such, the explanation of the algorithm will not be repeated here.

As time progresses, more resource request or resource release can be invoked by any of the processes.

  • Releasing Resources is trivial, we simply update the allocation, available, and need data structures.
  • For each Resource Request received, the output of the algorithm can be either Granted or Rejected depending on whether the system will be in a safe state if the resource is granted

System State Update

Note that these requests are made sequentially in time, so don’t forget to update the system state as you grant each request. When considering subsequent new requests, we perform the resource allocation algorithm with the UPDATED states that’s modified if you have granted the previous request.

If the previous request is rejected however, no change in system state is made and you can leave it as is.

Part 2: The Safety Algorithm

This algorithm receives a copy of available (named as work), need, and allocation data structures to perform a hypothetical situation of whether the system will be in a safe state if the current request is granted.

If we find that all processes can still finish their task (the elements of the finish vector is all True), then the system is in a safe state and we can grant this current request.

  • If you store each value of index i acquired, you can compute the sequence of possible process execution sequence

For example, given the following system state:

and current request R_1 made by P1: [1,0,2], you may find that granting this request leads to a safe state and there exist two possible execution sequence (depending on how you iterate through the finish vector (from index 0 onwards or from index N-1 backwards):

  1. P1, P3, P4, P0, P2, or
  2. P1, P3, P4, P2, P0

Complexity

Deadlock avoidance is time-consuming, since due to the expensive while loop in the safety algorithm. The time complexity of the safety algorithm is \(O(MN^2)\) (which is also the complexity of the Banker’s Algorithm, since the complexity of the Resource Allocation Algorithm is way smaller).

Carefully think: why. Also, ask yourself: what is the space complexity of the Banker’s Algorithm?

Deadlock Detection

In deadlock detection, we allow deadlock to happen first (we don’t deny its possibility), and then detect it later.

It is different from deadlock avoidance. The latter is one step ahead since will not grant requests that may lead to deadlocks in the first place.

Deadlock detection mechanism works by providing two things:

  • An algorithm that examines the state of the system to determine whether a deadlock has occurred
  • An algorithm to recover from deadlock condition

Deadlock Detection Algorithm

This algorithm works similarly Part 2 of the Banker’s Algorithm (the safety algorithm), just that this algorithm is performed on the actual system state (not the hypothetical work, need and allocation!)

Firstly, we need all the state information as in Banker’s algorithm: the available, request(renamed from need), and allocation matrices (no max/need). The only subtle difference is only that the need matrix (in safety algorithm) is replaced by the request matrix.

In a system that adapt deadlock detection as a solution to the deadlock problem, we don’t have to know the max(resource needed by a process), because we will always grant a request whenever whatever’s requested is available, and invoke deadlock detection algorithm from time to time to ensure that the system is a good state and not deadlocked.

The request matrix contains current requests of resources made by all processes at the instance we decide to detect whether or not there’s (already) a deadlock occuring in the system.

  • Row i in the request matrix stands for: Process i requiring some MORE resources that’s what’s been allocated for it.

The deadlock detection algorithm goes as follows:

  • Step 1: Initialize these two vectors:

    • work (length is #resources M) initialized to be == available
    • finish (length is #processes N) initialized to be:
      • False if request[i] != {0} (empty set)
      • True otherwise (means process i doesn’t request for anything else anymore and can be resolved or finished)
    • No update of allocation, need needed. We are checking whether the CURRENT state is safe, not whether a HYPOTHETICAL state is safe.

  • Step 2: find an index i such that both conditions below are fulfilled,

    • Finish[i] == False
    • request[i] <= work (element-wise comparison for these vectors)

  • Step 3:

    • If Step 2 produces such index i, update work and finish[i],
      • work += allocation[i] (vector addition)
      • finish[i] = True
      • Go back to Step 2
    • If Step 2 does not produce such index i, prepare for exit:
      • If finish[i] == False for some i, then the system is already in a deadlock (caused by Process i getting deadlocked by another Process j where finish[j] == False too)
      • Else if finish[i] == True for all i<N, then the system is not in a deadlock.

Complexity

This deadlock detection algorithm requires an order of \(O(MN^2)\) operations to perform.

Frequency of Detection

When should we invoke the detection algorithm? The answer depends on two factors:

  • How often is a deadlock likely to occur?
  • How many processes will be affected by deadlock when it happens?

This remains an open issue.

Deadlock Recovery

To recover from deadlock, we can either:

  1. Abort all deadlocked processes, the resources held are preempted
  2. Abort deadlocked processes one at a time, until deadlock no longer occurs

The second method results in overhead since we need to run the detection algorithm over and over again each time we abort a process. There are a few design choices:

  • Which order shall we abort the processes in?
  • Which “victim” shall we select? We need to determine cost factors such as which processes have executed the longest, etc
  • If we select a “victim”, how much rollback should we do to the process?
  • How do we ensure that starvation does not occur?

Deadlock Recovery remains an open ended issue. Dealing with deadlock is also a difficult problem. Most operating systems do not prevent or resolve deadlock completely and users will deal with it when the need arises.

Search