Deadlock Avoidance in Operating System

In this tutorial, we will be covering deadlock avoidance in the Operating system.

The deadlock Avoidance method is used by the operating system in order to check whether the system is in a safe state or in an unsafe state and in order to avoid the deadlocks, the process must need to tell the operating system about the maximum number of resources a process can request in order to complete its execution.

How does Deadlock Avoidance work?

In this method, the request for any resource will be granted only if the resulting state of the system doesn't cause any deadlock in the system. This method checks every step performed by the operating system. Any process continues its execution until the system is in a safe state. Once the system enters into an unsafe state, the operating system has to take a step back.

With the help of a deadlock-avoidance algorithm, you can dynamically assess the resource-allocation state so that there can never be a circular-wait situation.

According to the simplest and useful approach, any process should declare the maximum number of resources of each type it will need. The algorithms of deadlock avoidance mainly examine the resource allocations so that there can never be an occurrence of circular wait conditions.

Deadlock avoidance can mainly be done with the help of Banker's Algorithm.

Let us first understand the concept of Safe and Unsafe states

Safe State and Unsafe State

A state is safe if the system can allocate resources to each process( up to its maximum requirement) in some order and still avoid a deadlock. Formally, a system is in a safe state only, if there exists a safe sequence. So a safe state is not a deadlocked state and conversely a deadlocked state is an unsafe state.

In an Unsafe state, the operating system cannot prevent processes from requesting resources in such a way that any deadlock occurs. It is not necessary that all unsafe states are deadlocks; an unsafe state may lead to a deadlock.

The above Figure shows the Safe, unsafe, and deadlocked state spaces

Deadlock Avoidance Example

Let us consider a system having 12 magnetic tapes and three processes P1, P2, P3. Process P1 requires 10 magnetic tapes, process P2 may need as many as 4 tapes, process P3 may need up to 9 tapes. Suppose at a time to, process P1 is holding 5 tapes, process P2 is holding 2 tapes and process P3 is holding 2 tapes. (There are 3 free magnetic tapes)

Processes Maximum Needs Current Needs
P1 10 5
P2 4 2
P3 9 2

So at time t0, the system is in a safe state.The sequence is <P2,P1,P3> satisfies the safety condition.Process P2 can immediately be allocated all its tape drives and then return them. After the return the system will have 5 available tapes, then process P1 can get all its tapes and return them ( the system will then have 10 tapes); finally, process P3 can get all its tapes and return them (The system will then have 12 available tapes).

A system can go from a safe state to an unsafe state. Suppose at time t1, process P3 requests and is allocated one more tape. The system is no longer in a safe state. At this point, only process P2 can be allocated all its tapes. When it returns them the system will then have only 4 available tapes.Since P1 is allocated five tapes but has a maximum of ten so it may request 5 more tapes. If it does so, it will have to wait because they are unavailable. Similarly, process P3 may request its additional 6 tapes and have to wait which then results in a deadlock.

The mistake was granting the request from P3 for one more tape. If we made P3 wait until either of the other processes had finished and released its resources, then we could have avoided the deadlock

Note: In a case, if the system is unable to fulfill the request of all processes then the state of the system is called unsafe.

The main key of the deadlock avoidance method is whenever the request is made for resources then the request must only be approved only in the case if the resulting state is a safe state.

In the next tutorial, we will cover the concept of Banker's algorithm for deadlock avoidance.