Worst case scenario, you are using your phone or laptop and then it just “freezes” on you for no apparent reason. Nothing works, all you can do is stare at your screen and wonder what is actually going on when your device was literally working okay a few seconds ago. No button or screen swiping works unless you use the power button to hard boot it thereby aborting all processes in its wake.

Or, you have multiple tabs open on your computer but something just is not adding up. One or two of the applications open are taking way too long to respond. What then?

This is one of the many things I have to go through on a daily basis with my phone and quite frankly it’s really annoying having to hard boot your phone and laptop just so it can work properly again.

Believe it or not, but we all have experienced this before without knowing what was really happening or what just happened. This is where deadlock and starvation come in.

In this blog post, we will look at the key definitions we are going to use, then move on to explain what deadlock is. After that, we will look at what causes deadlock and how to we handle it, then finally we will look at how to prevent deadlock from occurring.

After looking at deadlock, we will then move on to look at what starvation is, the major causes and how it can be prevented. And finally, we will look at a summary in that order.

Table of Contents

• Key definitions used
• What is Deadlock?
• Causes of Deadlock
• Mutual Exclusion
• Hold and Wait
• No preemption
• Circular Wait
• How to handle Deadlock
• How to Prevent Deadlock
• Starvation
• Causes of Starvation
• How to Handle Starvation
• Differences between Deadlock and Starvation
• Summary

Key Definitions Used

• Resources: a resource is anything that can only be used by a single process at any instant of time. Can be preemptable or non-preemptable

• CPU: central processing unit which is the main brain of the computer

• OS: Operating system which manages software applications and runs the hardware

• Non-preemption: resources cannot be reassigned to a different process whilst being used by another process
• Preemption: resources can be taken from a process using them and reassigned to a new process.

What is Deadlock?

Let's take this example, you and your friend each have half the puzzle pieces to finally finish that puzzle that has taken you days to figure out. But here is the catch, you and your friend are not in the same country at that particular time and so you cannot finish the puzzle until your friend either returns from their trip or you book the first flight to go and meet them. Chances are, you will want to wait for them to finally come back.

But what if they are not coming back anymore and you have no idea where to find them? What are you going to do?

This occurs when a process or thread needs resources held up by another process or thread in order for it to complete its execution and the same process which the first process is waiting for is also waiting for resources from the first process in order for it to complete its execution. Now both processes will be waiting for each other to release the resources the other is using for it to complete its execution. But this will not happen.

So, what now? What happens to the process that are waiting for each other to release the resources that they are holding? Well, the two processes will remain in the waiting state for the foreseeable future until one process is aborted by the OS which then frees the resources for the other process to use and complete its execution.

Deadlock commonly happens in multiprocessing systems, parallel computing and in distributed system due to the way that they are made. However, this doesn’t not mean that it cannot happen in other types of systems, it just means that it isn’t likely to occur in systems that do not support multiprocessing, parallel or distributed computing.

Something to also note is that deadlock can also occur in databases when two or more actions need request for access of resources being used by another action which is also in turn waiting for resources from the first action to occur. This can be solved by simply putting time constraints on one of the actions and if that set time elapses then the process is aborted and the resources are then allocated to the other action which requested for them.

Causes of Deadlock

Now that we know what deadlock is, we will continue to discuss what situations can lead to it and why it happens in the first place.

In order for deadlock to occur, the following conditions have to be true:

1. Mutual exclusion
2. Hold and wait
3. No preemption
4. Circular wait

Mutual Exclusion

When each resource is either currently allocated to exactly one process or if the resource ifs available. No two processes can have access to the same resources at the exact same time.

Hold and Wait

Occurs when processes holding resources request for more new resources from the OS.

No Preemption

Preemption is when a process is taken out of execution and placed in the secondary storage by the OS in order for it to allow another process to execute and then is switched back into the CPU for it to finish executing.

However, no preemption means that the OS cannot by any means take any resources held by one process and allocate it to another process or even take that process from its flow of execution.

Circular Wait

Each process or thread is waiting to obtain the resources that are being held by another process at the same time of it requesting for the resources. The above is illustrated in the image below: However, just having one or a third of these conditions will not lead to a deadlock occurring as the conditions for deadlock to occur have not been fully met.

How To Handle Deadlock Deadlock can be handled in three ways depending on which one the OS you are using was set up to use.

The following are the three ways in which it can be handled: • usage of a protocol to ensure that the system will never enter a deadlock state • allow for the system to enter deadlock state and then recover from it • ignore the deadlock problem and pretend that deadlocks never occur in the operating system

How To Preventing Deadlock

Deadlocks can be prevented by ensuring that one of the four necessary conditions for deadlock cannot occur. Of the four necessary conditions that can lead to deadlock, eliminating the circular wait is the only practical approach. That is making sure that no one process in execution requests for resources that are held by another process that is also in execution.

This is one of the most effective ways of preventing from occurring, however, there are other ways in which deadlock can be prevented such as using an algorithm known as the Banker’s Algorithm, which does not grant resources because doing so would lead the system into an unsafe state where deadlock is likely to occur – Operating System Concepts 10th ed. We won’t get into the Banker’s Algorithm and how it can used.

For more information of the Banker’s Algorithm, read here read here

NOTE: If deadlock does however occur, your system can attempt to recover from the deadlock by either aborting one of the processes in the circular wait or preempting resources that have been assigned to a deadlocked process.

Deadlock is a pretty interesting topic in OS and if you want to read more about it then check this page out for everything that I may have forgotten to include in here

Starvation

Let’s take this example, you are waiting in line at a hospital and a severely ill patient shows up while you just have a regular checkup, nothing too serious that you require immediate attendance. The severely ill patient is then rushed into the ER for surgery while you remain waiting.

Just as the surgery is done, another seriously ill patient needing immediate attendance shows up and is given more priority over you. This keeps on happening while you remain waiting because your issue is not of high importance at that given time.

Obviously, you would get frustrated at the fact that you have been waiting for such a long time and no one is attending to you simply because your issue is not that important.

This is what happens in operating systems and is known as Starvation or Lived Lock. Starvation or indefinite blocking occurs usually when high priority processes keep on executing while the low priority processes keep on waiting indefinitely for their turn to finally get a chance at the CPU.

What Happens during Starvation?

Unlike in a deadlocked situation, when starvation occurs, the only wait happening is that done by low priority process as resources keep on continuously being used by high priority process all the time.

The resources include things like:

• CPU time
• Memory
• Disk space
• Network bandwidth
• I/O access to network or disk

As more and more high priority processes keep on coming into the computer, so does the risk of starvation increase. The danger of starvation is that a low priority process can remain waiting for a really long which is not really efficient at all.

Causes

One of the major causes of starvation is simplistic scheduling. The use of the priority scheduling algorithm is an example of what might increase the chances of starvation occurring in a system. This algorithm assigns CPU time to processes that have high priority while those with a less priority is made to wait for high priority processes to finish executing so that resources can be freed. But considering how the algorithm is implemented, starvation may not occur.

Prevention

Starvation can be solved by the use of aging which allows low priority processes to finally get that big chance at execution.

Aging is a technique used to gradually increase the priority of processes that have been waiting in the system for a long time. This helps reduce the chances of starvation occurring and allows all the processes with their different priorities to get a chance at execution.

You can read more about aging here

Starvation can also be prevented by using a priority scheduling that is not simplistic in nature and caters for all types of priorities without favouring one over the other.

Differences between Deadlock & Starvation

There are two major differences between deadlock and starvation and these two are listed below:

• There is waiting of resources in a deadlocked situation due to both processes needing the resources held up by the other process while in starvation, low-level priority processes wait for high-level priority processes to finish executing
• in a deadlock situation, all related processes cannot proceed. However, in starvation, only some processes wait for resources but others proceed .

Summary

Deadlock is a serious issue that could lead to some major issues if not treated well. The waiting that it causes an indefinite nothingness to occur which is not good for your laptop. However, four conditions have to be met before deadlock which are mutual exclusion, circular wait, hold and wait and no preemption. These can be handled fairly easily depending on how your operating system was designed.

Next, we looked at what starvation is and we said that this usually occurs with low-level priority processes as they are made for high-level processes to finish execution before they are allocated any resources. This is a case of bad scheduling algorithm and depending on what scheduling algorithm your particular operating system uses; you are either likely to face this or not face it at all.

Thank You! Thank you for reading up to this point. Hopefully this article helped both you and I learn what the Deadlock and Starvation are along with what causes them and how they can be prevented.

Check out my twitter