Learn about deadlock in general.
Video Explanation
What is Deadlock?
Deadlock is a state in which a task starts waiting for something that will not happen. As a result, it stops progressing.
Operating systems use multi-processing and multi-tasking for process completion, task completion, and to speed up work. When the two processes run concurrently and block each other’s paths, this condition is called deadlock.
In other words, deadlock is a condition when a process cannot be completed because it doesn’t get the resources it requires.
The conditions to declare a deadlock state are as follows:
- Only one process can use the resource at a time, resulting in exclusive control of the resources.
- Both processes hold the resources and wait for another process to leave hold of their resource.
- Until the process completes its execution, it doesn’t give up on resources.
- Each process in the chain holds a resource requested by another.
Understand deadlock with an example:
Let’s understand deadlock with a simple example.
Example
Suppose two processes (process A and process B) are running simultaneously.
process A {
update variable x
update variable y
}
process B {
update variable y
update variable x
}Since both processes are executing, process A will acquire a lock on variable x, and process B will acquire a lock on variable y.
Since process B holds the lock on resource y, process A can’t proceed further to acquire a lock on variable y. The same thing happens with process A as well. So, the processes will be in a deadlock state. Neither can move further, and they’ll wait indefinitely for each other to release the resources.
Implementing Deadlock: Considering two different resources.
Java
Python
C++
Go
C#
import java.io.*;
class ProcessA extends Thread {
public void run() {
synchronized (Deadlock.x) {
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized (Deadlock.y) {
System.out.println("Process A completed");
}
}
}
}
class ProcessB extends Thread {
public void run() {
synchronized (Deadlock.y) {
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized (Deadlock.x) {
System.out.println("Process B completed");
}
}
}
}
class Deadlock {
public static final Object x = new Object();
public static final Object y = new Object();
public static void main(String[] args) {
ProcessA processA = new ProcessA();
ProcessB processB = new ProcessB();
processA.start();
processB.start();
}
}import threading
import time
import traceback
class ProcessA(threading.Thread):
def run(self):
with Deadlock.x:
try:
time.sleep(0.1)
except:
traceback.print_exc()
with Deadlock.y:
print("Process A completed")
class ProcessB(threading.Thread):
def run(self):
with Deadlock.y:
try:
time.sleep(0.1)
except:
traceback.print_exc()
with Deadlock.x:
print("Process B completed")
class Deadlock:
x = threading.Lock()
y = threading.Lock()
if __name__ == "__main__":
processA = ProcessA()
processB = ProcessB()
processA.start()
processB.start()#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>
using namespace std;
mutex x;
mutex y;
void ProcessA() {
x.lock();
this_thread::sleep_for(chrono::milliseconds(100));
y.lock();
cout << "Process A completed" << endl;
y.unlock();
x.unlock();
}
void ProcessB() {
y.lock();
this_thread::sleep_for(chrono::milliseconds(100));
x.lock();
cout << "Process B completed" << endl;
x.unlock();
y.unlock();
}
int main() {
thread threadA(ProcessA);
thread threadB(ProcessB);
threadA.join();
threadB.join();
return 0;
}package main
import (
"fmt"
"sync"
"time"
)
var x sync.Mutex
var y sync.Mutex
func ProcessA() {
x.Lock()
time.Sleep(100 * time.Millisecond)
y.Lock()
fmt.Println("Process A completed")
y.Unlock()
x.Unlock()
}
func ProcessB() {
y.Lock()
time.Sleep(100 * time.Millisecond)
x.Lock()
fmt.Println("Process B completed")
x.Unlock()
y.Unlock()
}
func main() {
go ProcessA()
go ProcessB()
time.Sleep(1 * time.Second) // Wait for goroutines to complete
}using System;
using System.Threading;
class ProcessA {
public void Run() {
lock (Deadlock.x) {
Thread.Sleep(100);
lock (Deadlock.y) {
Console.WriteLine("Process A completed");
}
}
}
}
class ProcessB {
public void Run() {
lock (Deadlock.y) {
Thread.Sleep(100);
lock (Deadlock.x) {
Console.WriteLine("Process B completed");
}
}
}
}
class Deadlock {
public static readonly object x = new object();
public static readonly object y = new object();
}
class Program {
static void Main(string[] args) {
ProcessA processA = new ProcessA();
ProcessB processB = new ProcessB();
Thread threadA = new Thread(processA.Run);
Thread threadB = new Thread(processB.Run);
threadA.Start();
threadB.Start();
threadA.Join();
threadB.Join();
}
}In this code, the deadlock occurs because ProcessA acquires lock on x and then tries to acquire lock on y, while ProcessB acquires lock on y and then tries to acquire lock on x. Both threads end up waiting indefinitely for each other to release the locks, resulting in a deadlock situation.
Note that intentionally creating deadlocks is not recommended in real-world scenarios. This example is purely for learning purposes to demonstrate how deadlocks can occur. In practice, it’s important to design systems that prevent, detect, and recover from deadlocks to ensure proper functionality.
How could we correct the above code?
To correct the deadlock in the given scenario, you need to ensure that both ProcessA and ProcessB acquire the locks in the same order. One possible solution is to modify the order in which the locks are acquired in one of the processes. Here’s an updated version of the code that resolves the deadlock:
Java
Python
C++
Go
C#
import java.io.*;
class ProcessA extends Thread {
public void run() {
synchronized (Deadlock.x) {
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized (Deadlock.y) {
System.out.println("Process A completed");
}
}
}
}
class ProcessB extends Thread {
public void run() {
synchronized (Deadlock.x) {
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized (Deadlock.y) {
System.out.println("Process B completed");
}
}
}
}
class Deadlock {
public static final Object x = new Object();
public static final Object y = new Object();
public static void main(String[] args) {
ProcessA processA = new ProcessA();
ProcessB processB = new ProcessB();
processA.start();
processB.start();
}
}import threading
import time
import traceback
class ProcessA(threading.Thread):
def run(self):
with Deadlock.x:
try:
time.sleep(0.1)
except:
traceback.print_exc()
with Deadlock.y:
print("Process A completed")
class ProcessB(threading.Thread):
def run(self):
with Deadlock.x:
try:
time.sleep(0.1)
except:
traceback.print_exc()
with Deadlock.y:
print("Process B completed")
class Deadlock:
x = threading.Lock()
y = threading.Lock()
if __name__ == "__main__":
processA = ProcessA()
processB = ProcessB()
processA.start()
processB.start()#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>
using namespace std;
mutex x;
mutex y;
void ProcessA() {
x.lock();
this_thread::sleep_for(chrono::milliseconds(100));
y.lock();
cout << "Process A completed" << endl;
y.unlock();
x.unlock();
}
void ProcessB() {
x.lock();
this_thread::sleep_for(chrono::milliseconds(100));
y.lock();
cout << "Process B completed" << endl;
y.unlock();
x.unlock();
}
int main() {
thread threadA(ProcessA);
thread threadB(ProcessB);
threadA.join();
threadB.join();
return 0;
}package main
import (
"fmt"
"sync"
"time"
)
var x sync.Mutex
var y sync.Mutex
func ProcessA() {
x.Lock()
time.Sleep(100 * time.Millisecond)
y.Lock()
fmt.Println("Process A completed")
y.Unlock()
x.Unlock()
}
func ProcessB() {
x.Lock()
time.Sleep(100 * time.Millisecond)
y.Lock()
fmt.Println("Process B completed")
y.Unlock()
x.Unlock()
}
func main() {
go ProcessA()
go ProcessB()
time.Sleep(1 * time.Second) // Wait for goroutines to complete
}
using System;
using System.Threading;
class ProcessA {
public void Run() {
lock (Deadlock.x) {
Thread.Sleep(100);
lock (Deadlock.y) {
Console.WriteLine("Process A completed");
}
}
}
}
class ProcessB {
public void Run() {
lock (Deadlock.x) {
Thread.Sleep(100);
lock (Deadlock.y) {
Console.WriteLine("Process B completed");
}
}
}
}
class Deadlock {
public static readonly object x = new object();
public static readonly object y = new object();
}
class Program {
static void Main(string[] args) {
ProcessA processA = new ProcessA();
ProcessB processB = new ProcessB();
Thread threadA = new Thread(processA.Run);
Thread threadB = new Thread(processB.Run);
threadA.Start();
threadB.Start();
threadA.Join();
threadB.Join();
}
}In this updated code, ProcessB now acquires lock on x before trying to acquire lock on y. By ensuring that both processes acquire the locks in the same order (x followed by y), the deadlock situation is avoided.
It’s important to note that this is just one possible solution to resolve the deadlock in the given scenario. In practice, avoiding deadlocks requires careful design of concurrent systems, ensuring proper lock acquisition ordering, using timeouts, or employing other concurrency control mechanisms depending on the specific requirements and constraints of the system.
We hope you have learnt something great, please do share with people. Thank you 😃
Innoskrit
We're building a next-level EdTech Startup.
