Introduction to OS deadlock

OS stands for Operating System and in simple terms it acts as interface between hardware and users. In this article the focus is not to describe and talk about operating system but about deadlock, and we will see what is deadlock, how it occurs, how it is represented and how it is handled. So let us begin!

Deadlock refers to ability to not able to do anything in general terms, i.e., no process can happen or take place, all resources are occupied or user is simply not able to do anything. For example — If you want to type something from your keyboard, you are not able to or you want to hover/click your mouse and not able to and so on.

There should be a question arising in your mind? What to do when a deadlock occurs? Should I restart my computer? Should I wait? Don’t worry I will be discussing everything regarding that in “how it is handled part”. For now, let us look at its technical definition:

If 2 or more processes are waiting on happening of some event, which never happens, then we say these processes are involved in deadlock and that state is called deadlock.

Still confused? Let me clarify through a real-life example. Consider a hypothetical Bollywood movie situation, suppose you are hero and you have a girlfriend. Now you have told you girlfriend that you will take her to cinema to watch movie when she will return from her office. As evening approached, you were there outside her home waiting for her to come from office but she was kidnapped by villain and she instead is waiting for you to come to her and rescue her. Note the point that she is waiting for you, you are waiting for her but nobody is doing anything and that actually is what you say deadlock.

Extra bit: Deadlock and starvation are 2 different things. Here we are not talking about what starvation is but still let me clarify in simple terms that starvation leads to some definite/temporary wait while deadlock leads to indefinite/permanent wait. In above case, if girlfriend is stuck in traffic and she is little late in reaching home (let us say due to traffic), that will be considered starvation.

Now there are 4 necessary conditions for deadlock to occur, those are

1. Mutual Exclusion

2. No preemption

3. Hold and Wait

4. Circular Wait

Let me explain to you in simple terms what does above 4 things mean and I will give suitable examples as and when necessary

Mutual Exclusion — It simply says that 2 or more processes cannot use same resource, or same code, or any shared component of the OS. In technical terms “prevention of two processes to use critical section at same time and hence preventing race condition”.

Well, I don’t want to confuse you with technical words like critical section and race condition, so I will explain it using simple terms and through an example. I have not told you the notation on how to understand the deadlock diagrammatically but I will try to make you understand about the above diagram in simple terms. Suppose a process P1 has access to resource R1 and process P2 has access to resource R2, now P1 cannot access the resource R2 until and unless it is freed by P2 and P2 cannot access the resource R1 until and unless it is feed by P1.

Here the arrow pointing away from resource represents that resource is allocated to the process to which arrow is pointing to and arrow pointing towards resource represents that process is requesting for a resource.

No Pre-Emption: Coming to what is preemption simply means in English, pre means “before” and emption means “to leave”. So combined it means that a process will not leave the resource acquired by it until it ends or halts or terminates or until there is no further need of the resource to complete its execution.

Let us again take an example and understand. Our hero and heroine are still waiting for each other and if they are following the principle of no preemption then hero will keep waiting and not leave his place until she arrives and she too will keep waiting for him to arrive and rescue her and would not leave her place even if she had the opportunity (weird isn’t it, assume it is old school love).

Also, see that if anyone of them (either boyfriend or girlfriend) leave their place then there will eventually get to know what mishappening has occurred and there is no permanent/indefinite wait and hence no deadlock, so this is the reason why it is one of the necessary conditions for deadlock to occur.

Hold and Wait and Circular Wait: Actually, these conditions can be derived from mutual exclusion and no preemption itself. Hold and wait simply means that the processes will hold the resources allocated to them and wait for the not available resources to get free and so that they can complete their execution.

Circular wait can simply be understood from same diagram as well. The process P1 is waiting for R2 and P2 for R1 and they are waiting in a circular manner to get the required resources. Circular wait for 3 processes and resources is also shown below:

How is deadlock represented?

Till now we have seen quite a few diagrams and I am sure you should have got some basic idea but let me introduce you to the general convention and the details of representation.

Extra bit: It is important to note that there are some resources who can have multiple instances (till now we have seen only single instance resources). It simply means that they can give one instance to one process and one instance to other process and so can take part in execution of different processes simultaneously, but it never means that they are breaking the principle of mutual exclusion because one instance cannot be used by 2 processes at one time.

Above is the flowchart telling you various conventions about how we represent, let me explain the same in simpler terms

Vertex: There are 2 kinds of vertex — resource vertex and process vertex. Process vertex is simply represented by a circle

Resource vertex have different representations (both rectangular) based upon if the resource has single instance or multiple instances. Basically, number of dots are equal to number of instances it has to offer.

Edge: Edges are also of 2 categories based on the pointing direction.

If it is pointing from resource towards the process then it means that resource is assigned to the process.

If it is pointing from process towards resource then it means that process is requesting for resource.

Having said all this, let us come to the very first question which I asked you when I said that in deadlock you cannot do anything from keyboard, from mouse from anything so what should you do? Should you wait? Should you restart/power off?

Well, here is the answer you just wait for some time because it may be due to starvation and deadlock, but eventually if it is taking too long then it is deadlock and you should restart/power off (quite obvious that you cannot afford to wait for indefinite time).

The above answer is based on one of the most popular mechanisms of deadlock handling called deadlock ignorance or Ostrich’s method. This method simply says that your OS will ignore the deadlock and will do nothing to improve state of your computer (as Ostrich doesn’t care about her eggs). So, eventually only choice you have is to restart/power off. In fact, this is most popular method and used in common OS like Windows and MAC.

Extra bit: You will be wondering how an OS can simply ignore the deadlock and do nothing about it. Well, it is simply because deadlock is a very very rare phenomenon and computer do not want to waste its memory and resources on developing algorithms to recover from deadlock.

The other method by which a deadlock may be tackled is:

1. Deadlock prevention

2. Deadlock avoidance

3. Deadlock detection and recovery

Deadlock prevention keeps check that at least one out of those 4 conditions we studied earlier doesn’t occur so that deadlock can be prevented.

Deadlock avoidance uses Banker’s Algorithm to check for safe and unsafe sequences of allotting processes to resources so that no deadlock occurs

As I told you the above are not so common methods, so I will not discuss them in detail.

That is pretty much about what is deadlock and how it occurs, what are its conditions, how it is represented, how it is handled by OS.

I will also keep you wondering and leave you with few other questions so that you can ponder over them

1. For a system containing only single instance resources, only circular wait is sufficient for deadlock?

2. Why is deadlock a rare phenomenon?

3. Printer is which kind of resource, single instance or multi-instance

Well, I hope you have enjoyed reading it and will always remember what actually deadlock is without remembering the boring technical definitions.

Thanks!