Deadlock in Operating System

Introduction

Deadlock is a critical problem in programs and operating systems. It happens when two or more processes or threads cannot continue because they are waiting for each other to release a resource. In this article, we will explore the concept of deadlock, its causes, prevention strategies, and various resolution algorithms with code examples.

What is Deadlock?

This is best understood through a simple analogy - imagine two people trying to pass each other in a narrow corridor. If both people are rude and refuse to step in, they will be in a state of "lockdown" because they cannot move forward without cooperation.

In computer science, deadlocks occur when a process or class cannot continue because it is waiting for shared resources. This can cause the system to be unresponsive or sluggish.

Causes of Deadlock

Lockouts can occur for a variety of reasons, but are often associated with the following four conditions, known as the "Four Prerequisites for Lockouts":

1. Mutual Exclusion: At least one resource must be stored in a non-shared format. This means that only one process or thread can be accessed at a time.

2. Hold and Wait: You must save at least one resource while waiting to receive additional resources.

3. No Preemption: Resources cannot be obtained by force. It can only be released voluntarily.

4. Circular Wait: Each process must be a circular chain of processes waiting for resources to be held by the next process in the chain.

To avoid conflicts, you must ensure that at least one of these conditions is not met.

Deadlock Prevention

Deadlock Prevention aims to eliminate one or more of the four prerequisites for a lock. Here are some strategies:

1. Resource Allocation Graph: Maintain a graph showing resource allocation and operational demand. If the graph does not have a loop, then it does not have a loop. If there is a cycle, identify it and use the resources.

2. Resource Allocation Table: Use the table to track the status of each resource, whether it is available, allocated, or requested by the process. This information helps in resource allocation decisions.

3. Resource Allocation Policy: Implement a resource allocation policy that prevents constraints. For example, the Banker algorithm ensures that resource allocation is not blocked.

Deadlock Resolution Algorithms

A deadlock resolution algorithm is used to escape the deadlock when the prevention strategy fails. Here are the most commonly used nesting algorithms:

1. Kill one or more processes

In this strategy, one or more processes are terminated to break the deadlock. The process to be carried out is selected based on certain criteria (for example, priority or resource use).

Cheat code to kill the process to resolve the lock
def kill_process(process):
    process.terminate()

2.Resource Preemption

Resource redundancy refers to taking resources from one or more processes to solve problems. An option can be either standard (resources taken by force) or non-standard (resources taken by voluntary release).

Pseudo code to prevent the source from resolving the key
def preempt_resource(resource, action):
    process.release_resource(resource)
    resource.allocate_to(function)

Example type

Example 1: Dining Philosophers Problem

The Philosophers' Dinner problem is a classic example of a blocked scenario in a concurrent program. It includes a group of philosophers sitting at a round table and eating with chopsticks. Philosophers need two chopsticks to eat, but there are not enough chopsticks for everyone, leading to a gridlock situation.

class philosopher:
    def __init __ ( self , name , left_shepherd , right_shepherd ):
        self.name = name
        self.left_chopstick = left_chopstick
        self.right_chopstick = right_chopstick

    def eat ( self ):
        self.left_chopstick.acquire()
        self.right_chopstick.acquire()
        # Eat
        self.left_chopstick.release()
        self.right_chopstick.release()

philosopher = [Philosopher("P1", print1, print2), ...]

Example 2: Banker Algorithm

The banker's algorithm is a key prevention strategy that distributes funds in a way that ensures safe execution of transactions. If resource allocation cannot be made reliably, the system rejects the request, preventing blocking.

def request_resource(process, resource, request):
    if request <= resource.available:
        if request <= resource.max - resource.allocated[process]:
            resource.available -= request
            resource.allocated[process] += request
            return "Resource granted."
        else:
            return "Resource request exceeds maximum claim."
    else:
        return "Resource not available. Process must wait.