Beginner’s guide to Deadlock and its Handling Mechanisms

Let’s say two people are arguing and neither is willing to compromise or budge on their position. This can lead to a situation where both sides are stuck and no result is achieved. Well, this is a deadlock. It is one of the most important concepts to know about when you are designing the architecture of an application or an Operating System.

Deadlock is a situation where two threads are each waiting for the other to release a lock, and neither ever does.

But why should I know about a deadlock?

There are many reasons why one should know about deadlocks, but here are some solid ones:

1. To avoid it in your own code! Deadlock can lead to your program getting stuck and being unable to make any further progress.
2. To diagnose it if it does happen in your program. If you suspect that your program is deadlocked, knowing about deadlock can help you resolve it.
3. To understand how deadlock works in general. This can be helpful for understanding how concurrent programs can fail, and how to prevent or fix such failures.

Before we move on, here are certain prerequisites that I would like you to know about…

Process - A process is defined to be an instance of a program in execution. What this means is that a process is an active entity that is running through the instructions that are specified in the program. Whenever you run the software program that you have written and compiled into an executable file, you create a new process.

Resource - A resource can be defined as any physical (or) virtual component in a computer that is available in limited quantities. Resource categories may include memory, printers, CPUs, open files, tape drives, CD-ROMS, etc.

In normal operation a process must request a resource before using it, and release it when it is done, in the following sequence:

Request — If the request cannot be immediately granted, then the process must wait until the resource(s) it needs become available. For example the system calls open( ), malloc( ), new( ), and request( ).

Use — The process uses the resource, e.g. prints to the printer or reads from the file.

Release — The process releases the resource so that it becomes available for other processes to request/use. For example, close( ), free( ), delete( ), and release( ).

Okay, too many of the tedious prerequisites let’s jump to an example now…

Consider there are five ‘binary’ philosophers and since they are ‘binary’ philosophers their job is to either eat or think. While eating, they are not thinking, and while thinking, they are not eating. The philosophers sit at a circular table with a bowl of spaghetti. There are also 5 chopsticks on the table. A chopstick is placed in between each philosopher, thus each philosopher has one chopstick to his left and one chopstick to his right. In order to eat the spaghetti, a philosopher must use 2 chopsticks which are on his immediate left and right.

Let’s take a scenario in which every philosopher holds a left chopstick and waits for a right chopstick (or vice versa). In this case, philosopher P0 waits for the chopstick grabbed by philosopher P1 who is waiting for the chopstick of philosopher P2 and so forth, making a circular chain resulting in no philosopher being able to eat the spaghetti.

Well, this was the classic Dining Philosophers Problem which is facing a deadlock.

Deadlock: A situation in an operating system where 2 or more processes are unable to proceed because each of them is waiting for one of the other processes to release the required resource(s).

An everyday depiction of a deadlock.

In our example, the philosophers can be considered as the process and the chopstick as the resource waiting for other processes to release their resources.

Two processes waiting for resources acquired by each other hence undergoing a deadlock.

In an Operating System, a deadlock occurs when the following 4 conditions occur; notice that all of them are necessary, and none is sufficient:

1. Mutual Exclusion — It means that a resource cannot be shared by 2 or more processes.
2. Hold and wait — A process is holding at least one resource and waiting for more resources.
3. No preemption — A resource cannot be taken from a process unless the process releases the resource.
4. Circular wait — A set of processes waiting for each other in circular form.

Well, that was all about deadlocks. Let us now take a look at some of the Deadlock Handling Mechanisms.

In general, there are four approaches to handling deadlocks:

1. Deadlock prevention

2. Deadlock Avoidance

3. Deadlock Detection & Recovery

4. Deadlock Ignorance

1. Deadlock prevention

By using this approach, the system will prevent any deadlock situation. As we saw, the above list presented before enumerates conditions that are all necessary for a deadlock to occur; therefore, it suffices that at least one of those conditions does not hold. Let us see how -

• Removing the mutual exclusion condition means that no thread may have exclusive access to a resource. This isn’t very practical if we want concurrency.
• A thread has to be able to have a resource for a certain amount of time, or the processing outcome may be inconsistent. So removing the no preemption condition may also be difficult.
• Removing the ‘hold and wait’ condition can be implemented practically if a process declares all the resources initially. However, this sounds very practical but can’t be done in the computer system because a process can’t determine necessary resources initially.
• Removing Circular wait. Numbering all resources and requiring that processes only request them in strictly increasing (or decreasing) order are two ways to avoid circular waits. One big challenge in this scheme is determining the relative ordering of the different resources.

Note : It is only feasible to eliminate the circular wait condition.

2. Deadlock Avoidance

In the deadlock avoidance technique, we try to avoid deadlock to happen in our system.

Even though a resource is available, we might force processes to wait for it, because doing so might trigger a deadlock later. This typically calls for processes to announce in advance any potential resource requests.

Safe state: a state is safe if there is some way to let all the processes run without creating a deadlock. A state is safe if there is a safe sequence.

Safe sequence: It describes the order in which processes will finish and release their resources, and once all previous processes have finished, process Pi can get whatever resource(s) it needs and finish too.

THE BANKER’S ALGORITHM

The Banker’s algorithm is a resource allocation and deadlock avoidance algorithm that test for safety by simulating the allocation for the predetermined maximum possible amounts of all resources, then makes a safe state check to test for possible activities before deciding whether the allocation should be done or not.

Every time a process asks for resources, the operating system executes the Banker’s algorithm. If the algorithm determines that accepting the request would put the system in an unsafe state (one where deadlock could occur), it delays the resource request to avoid deadlock.

The Banker’s algorithm requires knowledge of three things in order to function:

1. The maximum amount of each resource that each process might use

2. The quantity of each resource that each process currently has in stock

3. The quantity of each resource that is available within the system

Knowing the maximum number of resources beforehand is not possible. Hence deadlock avoidance using Banker’s Algorithm is not practically possible.

3. Deadlock detection & recovery

In this method, the CPU assumes that a deadlock will eventually occur in the system and that it will then employ a recovery technique to get rid of the deadlock. The CPU checks for the deadlock on a regular basis. A system’s deadlock can be found using the Resource Allocation Graphs.

Resource Allocation Graphs- It depicts a system’s state graphically. It contains all the details regarding the resource requests and allocations made to each process. The vertices of the RAG represent the process or the resource, and the edges represent the allocation or request of any resource. Given this graph, we can run any cycle detection algorithm. If a cycle is found, we have a deadlock. This is only true if there is one instance of each resource. With multiple instances of resources, there might not be a deadlock even if a cycle is detected.

The CPU may forcibly take a resource allotted to one process and give it to another for recovery of deadlock, but the second process must have a high priority or be a system process.

4. Deadlock Ignorance

In most systems, the probability of a deadlock occurring is very low. So why use so many different detection and recovery strategies, or why use a technique to prevent deadlock? The Operating System makes the erroneous assumption that a deadlock will never occur. Since these deadlock prevention procedures are expensive, it simply ignores the deadlock. This is the most widely used deadlock handling mechanism.

Performance and correctness must be traded off. The three approaches mentioned above are valid, however, the system performance is poor since the CPU must periodically check for deadlock. But if we ignore the deadlock then there might be cases where deadlock can happen but that is rare of the rarest case. If a deadlock develops in our system, we may simply restart it to resolve it. However, you will also lose any data that is not being preserved.

To conclude,

You must consider whether you desire accuracy or effectiveness. When a system enters a deadlock, it should be ignored if performance is what you’re after. Otherwise, you can use a deadlock prevention approach. It all depends on the demands of the circumstances. If your system handles some extremely crucial data that you just cannot lose in the event of a deadlock, then you should absolutely opt for deadlock prevention.

Well, that’s it for this blog! Hope to see you at my next one!