Deadlocks

Sources

1. Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, “Operating System Concepts” - 2021-02-09

What Are Resources

• Processes require resources to run.
• There are different types of resources such as program cycles, memory, etc.
• Three stages of a resource utilization:
  1. request
  2. use
  3. release

Semaphores

Operating systems use semaphores to manage how different processes share resources. They are used with the wait().

wait() to be specific, will force the process to wait until the semaphore returns to the initialized value before it is free to use.

Deadlock

Preconditions for a deadlock:

1. Mutual exclusion: a resource can only be used by a single process at a time
2. Hold and wait: a process holding at least one resource is waiting for additional resources held by another process
3. No preemption: only the process holding the resource can release said resource, meaning that it can only be released once the process is done using it
4. Circular wait: there exist a set of processes $\{P_1,P_2,P_3\dots P_n\}$ whereby each process is waiting for the other process to release their resource: $P_1$ is waiting for a resource held by $P_2$, $P_2$ is waiting for a resource held by P$3$ … $P_{n-1}$ is waiting for a resource held by $P_n$, and $P_n$ is waiting for a resource held by $P_1$.

Ensure that the system never enters a deadlock state through deadlock prevention or deadlock avoidance.

If deadlock does occur:

• Recover from it
• Ignore it and pretend it did not occur

Deadlock Prevention

Invalidate one of the preconditions for a deadlock:

• Mutual exclusion: for resources that are shareable, allow them to be shared between several processes to prevent mutual exclusion.
• Hold and wait:
  • Ensure that the process can only request a resource when it is not holding one at the moment, or force it to request all necessary resources and wait for them to be allocated before executing that process.
  • Although this invalidates the hold and wait precondition, it can also result in low resource utilization and starvation.
• No preemption:
  • If a process requests for a resource that cannot be immediately be allocated to it, it should drop all the resource it is holding.
  • The process will only restart after it regains both its old resources and the new resources that it requested.
• Circular wait: arrange all resource types in a way that requires each process to request resources in an increasing order of enumeration.

Deadlock Avoidance

Deadlock avoidance needs the system to have pre-existing knowledge on the process and its resource requirements.

• The best model requires that each process declares the maximum number of needed resources of each type.
• Its algorithm inspects the resource allocation state to prevent a circular-wait condition.
• Resource allocation state is defined by three things:
  • the number of available resources;
  • the number of allocated resources; and
  • the maximum demands of the processes

Resource-Allocation Graph

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

Types of vertices:

1. Process vertices $P_n$
2. Resource vertices $V_n$

Types of edges:

1. Request edges $P_n\to R_n$
2. Assignment edges $R_n\to P_{}n$

TIP

1. If no cycles, then there is no deadlock
2. If there is cycles
3. If only one process requesting a resource type, then it is a deadlock
4. if multiple processes requesting for a resource type, then a possibility of a deadlock

Safe State

• An essential concept in deadlock avoidance wherein the system must determine if responding to a process request leads to a safe state.
  • Deadlocks cannot exist when the system is in a safe state.
  • Deadlock avoidance will guarantee that the system does not enter an unsafe state.
• Deadlocks are not possible when the system is in a safe state.
• The system is in a safe state when a sequence of processes exists wherein each process can have their requests satisfied through currently available resources and resources held by a previous process.
  • If a resource is not immediately available, then it can wait until they are available (i.e., the previous process is done with using it)

Avoidance Algorithms

Use the resource-allocation graph when there is only a single instance of a resource type; otherwise, use the Banker’s algorithm.

Resource-Allocation Scheme

1. A claim edge indicates that the process might request for a resource. It is represented by a dashed line.
2. The claim edge turns into a request edge when the process actually requests for the resource
3. When the resource responds to the request and is allocated to the process, the request edge turns into an assignment edge
4. Once the process is done with the resource, the assignment edge reconverts back to a claim edge

Note: Resources must be claimed in advanced

Resource-Allocation Algorithm

This algorithm ensures that a request is only granted when it does not result in a formation of a cycle (or circular-wait).

Banker’s Algorithm

• There are multiple instances of resources
• Each process must declare the maximum number of needed resources of each type in advanced
• A process may need to wait when requesting a resource
• Once the process has all of its resources, it must return them within a limited period of time

Data structures involved in this algorithm:

1. Available
2. Max
3. Allocation
4. Need

Deadlock Detection

To detect deadlocks, the system must first allow the system to enter a deadlock. It will then be able to detect it through a detection algorithm. Afterwards, a recovery scheme is performed to deal with the deadlock.

For a single instance of each resource type, a wait-for graph is maintained, where nodes represent the processes. An algorithm will be applied periodically to find existing cycles and detect a deadlock. This algorithm will need an order of $n^2$ operations ($n$ is the number of vertices in the graph).

Deadlock Recovery: Process Termination

One approach to recover from a deadlock state is by aborting all deadlocked processes, or by aborting one process at a time until the deadlock cycle is eliminated. Nonetheless, there are a variety of ways to order the abortion of processes depending on the needs of the user.

Deadlock Recovery: Resource Preemption

1. Select a victim to minimize the cost
2. Rollback to a safe state and restart the processes in that state
3. Because the same process may always be the victim, include the number of rollback in cost factor to prevent starvation