A deadlock arises when a set of entities are unable to proceed because each is holding onto resources and waiting for others to release the resources they need.
Example:
Imagine a scenario where only one track is accessible, and two trains are approaching each other. Neither train can change direction once they face each other. In the realm of operating systems, a deadlock arises when multiple processes are unable to progress as each process is waiting for a resource that is currently in use by another process. This situation occurs when a process or thread is in a state of waiting because it has requested a system resource that is being utilized by another process, which in turn is also waiting for a resource held by the initial process.
A deadlock can potentially happen in nearly all programs that rely on locking mechanisms. The only cases where this may not hold true are with products like the Berkeley DB Concurrent Data Store, which sacrifices some concurrency to ensure deadlock-free operations, and situations where all control flows interacting with the relational database are restricted to read-only operations. While there are rare instances of deadlock-free data access patterns, such as when a program updates fixed-length entries in a database, they are highly uncommon.
The deadlock detection mechanism scans the "waits-for" graph to detect and pinpoint any potential deadlocks. Specifically, it scrutinizes each currently locked lock object and navigates through the lock table. Each entry contains a roster of pending locks and released lockers. An enumeration of empty lockers for each object is established to create a partial sequence. The precedence dictates that every holding locker precedes every waiting locker, as the former must relinquish its lock before the latter can progress. In essence, the preliminary sequences are organized in a topological manner after evaluating each entry. Any circular dependencies among lockers highlighted through this topological arrangement signify a deadlock impasse.
Conditions for Deadlock:
There are various circumstances that can lead to a deadlock. Here are some primary deadlock conditions:
Mutual exclusion ensures that only one process can hold a resource at any given time. This means that if Process P1 is using a resource R, Process P2 cannot access the same resource R concurrently. While Process P1 is utilizing resource R, Process P2 is unable to do so simultaneously, but it does have the capability to access it.
"Hold & Wait" describes a scenario in which a process retains certain resources and seeks access to additional resources possessed by other processes. For example, process P1 might be requesting resource R3, which is currently held by process P2, while maintaining ownership of resources R1 and R2.
Preemption is restricted: It is not allowed for one process to force a resource away from another process. For example, if process P1 is utilizing resource R, process P2 is unable to claim it. This constraint eliminates the need for implementing different scheduling techniques. In order for process P2 to access resource R, it must wait until process P1 has finished using it.
Strategies to Prevent Deadlocks
The operating system can employ deadlock avoidance techniques to avert deadlock situations. It will monitor the peak resource requirements of a process from start to finish. Continuously assessing the system's status, the OS will verify resource availability before allocating them to any process.
Throughout the deadlock avoidance procedure, the operating system will steer clear of getting caught in a cyclic wait scenario. In the event that a deadlock occurs at some point down the line, the system will fulfill any resource requests to avert the deadlock.
By following the most straightforward and practical approach, the procedure should specify the maximum quantity of each type of material it might require at any given time. The deadlock avoidance technique reviews the distribution of resources to guarantee the absence of a cyclic waiting condition.
Detection of deadlocks:
The operating system anticipates an upcoming deadlock with this strategy. Consequently, it executes a deadlock detection process at regular intervals and implements a recovery plan upon detecting a deadlock situation.
The primary role of the operating system is to recognize deadlock situations.
There are two methods for finding.
Deadlocks may arise from deadlock detection procedures. Subsequently, it is crucial to evaluate the system's state to determine if a deadlock has occurred and then take steps to resolve it. Monitoring the resource allocation, process statuses, potentially rolling back actions, restarting processes, and resolving identified deadlocks are all managed through specific algorithms. Detecting deadlocks is relatively straightforward as the operating system's resource scheduler keeps track of which resources each process has locked or is actively requesting.
- When Handling a Single Instance of Each Resource: The wait-for-graph technique employed by the OS focuses on identifying circular dependencies, resembling the Resource Allocation Graph (RAG) with some modifications. Often, it integrates elements of both RAG and the Wait-for graph.
- Managing Multiple Instances of Each Resource: In scenarios involving multiple instances of resources, the Safety algorithm is utilized, following a similar approach to the Banker's algorithm. Unlike the Banker's algorithm, there is no need for a maximum resource matrix; instead, only the allocated, available, and current requirement matrices are considered.
Algorithm:
Steps of Algorithm
Step 1
1. Let Work(vector) length = m
2. Finish(vector) length = n
3. Initialize Work= Available.
1. if Allocation = 0 ∀ i ∈[0,N-1], then Finish[i] = true;
otherwise, Finish[i]= false.
Step 2
1. Find the index i with the conditions
1. Finish[i] == false
2. Work >= Request i
If exists no i, go to step 4.
Step 3
1. Work += Allocation i
2. Finish[i] = true
Go to Step 2.
Step 4
1. For some i in [0, N), if Finish[i]==false, the deadlock occurred. Finish [i]==false, the process Pi is deadlocked.
C program for implementation of the Deadlock detection Algorithm
Filename: Deadlock.c
#include <stdio.h>
#define MAX_PROCESSES 10
#define MAX_RESOURCES 10
int allocation[MAX_PROCESSES][MAX_RESOURCES];
int request[MAX_PROCESSES][MAX_RESOURCES];
int available[MAX_RESOURCES];
int resources[MAX_RESOURCES];
int work[MAX_RESOURCES];
int marked[MAX_PROCESSES];
int main() {
int num_processes, num_resources;
printf("Enter the number of processes: ");
scanf("%d", &num_processes);
printf("Enter the number of resources: ");
scanf("%d", &num_resources);
// Input total resources
for (int i = 0; i < num_resources; i++) {
printf("Enter the total amount of Resource R%d: ", i + 1);
scanf("%d", &resources[i]);
}
// Input request matrix
printf("Enter the request matrix:\n");
for (int i = 0; i < num_processes; i++) {
for (int j = 0; j < num_resources; j++) {
scanf("%d", &request[i][j]);
}
}
// User Input allocation matrix
printf("Enter the allocation matrix:\n");
for (int i = 0; i < num_processes; i++) {
for (int j = 0; j < num_resources; j++) {
scanf("%d", &allocation[i][j]);
}
}
// Initialization of the available resources
for (int j = 0; j < num_resources; j++) {
available[j] = resources[j];
for (int i = 0; i < num_processes; i++) {
available[j] -= allocation[i][j];
}
}
// Mark processes with zero allocation
for (int i = 0; i < num_processes; i++) {
int count = 0;
for (int j = 0; j < num_resources; j++) {
if (allocation[i][j] == 0) {
count++;
} else {
break;
}
}
if (count == num_resources) {
marked[i] = 1;
}
}
// Initialize work with available
for (int j = 0; j < num_resources; j++) {
work[j] = available[j];
}
// Mark processes with requests <= work
for (int i = 0; i < num_processes; i++) {
int can_be_processed = 1;
if (marked[i] != 1) {
for (int j = 0; j < num_resources; j++) {
if (request[i][j] > work[j]) {
can_be_processed = 0;
break;
}
}
if (can_be_processed) {
marked[i] = 1;
for (int j = 0; j < num_resources; j++) {
work[j] += allocation[i][j];
}
}
}
}
// Check for unmarked processes (deadlock)
int deadlock = 0;
for (int i = 0; i < num_processes; i++) {
if (marked[i] != 1) {
deadlock = 1;
break;
}
}
if (deadlock) {
printf("Deadlock detected\n");
} else {
printf("No deadlock possible\n");
}
return 0;
}
Output:
Enter the number of processes: 3
Enter the number of resources: 3
Enter the total amount of Resource R1: 4
Enter the total amount of Resource R2: 5
Enter the total amount of Resource R3: 7
Enter the request matrix:
1 2 3
4 5 6
7 8 9
Enter the allocation matrix:
5 6 7 1 2 3 7 8 9
Deadlock detected