Virtual Labs

Introduction

Deadlock occurs in computing when two or more processes are unable to continue because each is waiting for the other to release resources. The main concepts involved are mutual exclusion, resource holding, circular wait, and no preemption.
For example, imagine two trains approaching each other on a single track with no possibility to pass. When they meet, neither can move forward, effectively trapping both. This situation illustrates the concept of deadlock in a real-world scenario.

How Does Deadlock occur in the Operating System?

In operating systems, a deadlock occurs when two or more processes hold resources and simultaneously wait for resources held by each other. For instance, consider the following diagram: Process 1 holds Resource 1 and waits for Resource 2, which is held by Process 2. Meanwhile, Process 2 is waiting for Resource 1, creating a circular dependency.

Fig. 1 Deadlock Occurrence

Necessary Conditions for Deadlock in OS

Deadlock can occur if all of the following four conditions are met simultaneously:

Mutual Exclusion: Resources are non-shareable, meaning that only one process can use a resource at any given time.
Hold and Wait: A process is currently holding at least one resource while waiting to acquire additional resources.
No Preemption: Resources cannot be forcibly taken from a process; they must be voluntarily released by the process holding them.
Circular Wait: A set of processes are each waiting for a resource held by another process in a circular chain.

What is Deadlock Detection?

Deadlock detection is the process used by a system to identify if any set of processes is stuck in a state of indefinite waiting, where each process is waiting for resources held by the others, thereby preventing progress. In simpler terms, it involves determining whether any processes are trapped in a circular wait. Several algorithms are used for this purpose, including:

Resource Allocation Graph
Banker’s Algorithm

Banker's Algorithm

The Banker's Algorithm, developed by Edsger Dijkstra, is a resource allocation and deadlock avoidance algorithm used in operating systems to manage resources and ensure the system remains in a safe state. It prevents deadlock by allocating resources in a manner that avoids unsafe states and checks the system's state for safety before granting resource requests.

The following Data structures are used to implement the Banker’s Algorithm:

Processes and Resources:

Processes(n): These are the active entities in the system that require resources to perform tasks.
Resources(m): These are the passive entities that processes need, such as CPU time, memory, or I/O devices. Resources can be classified into different types, and there can be multiple instances of each type.

Claim Matrix:

Each process declares the maximum number of instances of each resource type it may need, known as the claim. This information is used to determine if the system can remain in a safe state after allocating resources to a process.

Maximum (Max):

It is a 2-d array of size ‘n*m’ that defines the maximum demand of each process in a system.
Max[ i, j ] = k means process P_i may request at most ‘k’ instances of resource type R_j.
Example: If a process may need up to 5 units of resource A and 3 units of resource B during its execution, its maximum matrix entry for resources A and B would be 5 and 3, respectively.

Allocation:

It is a 2-d array of size ‘n*m’ that defines the number of resources of each type currently allocated to each process.
Allocation[ i, j ] = k means process P_i is currently allocated ‘k’ instances of resource type R_j
Example: If a process is currently holding 2 units of resource A and 1 unit of resource B, its allocation matrix entry for resources A and B would be 2 and 1, respectively.

Available

It is a 1-d array of size ‘m’ indicating the number of available resources of each type.
Available[ j ] = k means there are ‘k’ instances of resource type R_j
Example: If there are 10 units of resource A and 5 units of resource B in total, and 4 units of A and 2 units of B are currently allocated, then the available resources would be (10-4) = 6 units of A and (5-2) = 3 units of B.

Need:

It is a 2-d array of size ‘n*m’ that indicates the remaining resource need of each process.
Need [ i, j ] = k means process P_i currently needs ‘k’ instances of resource type R_j
Find by using the formula :

Need [ i, j ] = Max [ i, j ] – Allocation [ i, j ]

Example: If a process's maximum requirement is 5 units of resource A and 3 units of resource B, and it currently holds 2 units of A and 1 unit of B, its need for A and B would be (5-2) = 3 and (3-1) = 2, respectively.

Safety Algorithm:
Ensures that the system remains in a safe state by verifying if resource allocation can be done without leading to a deadlock.
- Safe Sequence :
  A safe sequence is a sequence of processes in which the system can allocate resources to each process in turn without causing a deadlock. In other words, if the system can find a sequence of processes such that each process can get the resources it needs (considering the resources currently allocated and the maximum demand of each process), then the system is in a safe state.
- Unsafe Sequence :
  An unsafe sequence is a sequence of processes where, if the system allocates resources to them in that order, it might lead to a deadlock. In other words, there exists at least one process in the sequence that cannot proceed to completion because the resources it needs are not available.
Steps involved in safety algorithm:
1) Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.
Initialize: Work = Available
Finish[i] = false; for i=1, 2, 3, 4….n
2) Find an i such that both
a) Finish[i] = false
b) Need_i <= Work
if no such i exists goto step (4)
3) Work = Work + Allocation[i]
Finish[i] = true
goto step (2)
4) if Finish [i] = true for all i then the system is in a safe state

Resource Request Algorithm:
Handles requests for resources from processes and determines whether granting the request will keep the system in a safe state. Let Request_i be the request array for process P_i. Request_i [j] = k means process P_i wants k instances of resource type R_j.
When a request for resources is made by process P_i, the following actions are taken:
1) If Request_i <= Need_i
Goto step (2) ; otherwise, raise an error condition, since the process has exceeded its maximum claim.
2) If Request_i <= Available
Goto step (3); otherwise, P_i must wait, since the resources are not available.
3) Have the system pretend to have allocated the requested resources to process P_i by modifying the state as follows:
Available = Available – Request_i
Allocation_i = Allocation_i + Request_i
Need_i = Need_i– Request_i

Advantages

Allows more dynamic and flexible allocation of resources compared to prevention and avoidance strategies.
Detects deadlocks as they occur, enabling timely intervention to resolve them.
Maximizes resource utilization by not imposing strict constraints to prevent deadlocks.

Disadvantages

Continuous monitoring and analysis of resource allocation can introduce computational overhead.
Requires sophisticated mechanisms to accurately detect cycles or knots in resource allocation graphs.
Delays in detection or resolution can impact system performance and user experience.

Applications

Operating Systems: essential for managing resources like memory, CPU, and I/O devices.
In database Management Systems (DBMS): Critical for managing transaction concurrency and resource locking.
In distributed Systems: Important for managing resources across multiple nodes in a network.

To Implement Deadlock Detection Algorithm