Deadlock Avoidance is a process that is going to use by operating system to check whether the system is existing in a safe mode or in an unsafe mode. Therefore, now we are going to explain all possible things about deadlock avoidance in OS (Operating System) and deadlock avoidance algorithm in OS with ease. After reading this article, you will definitely educate about what is deadlock avoidance in OS without any hassle.
What is Deadlock Avoidance?
Definition – Deadlock avoidance is the mostly used by several types of operating systems, but it is used mainly for end users. This concept is more comfortable for single user system because they use their system for simply browsing as well as other simple activities.
How Does Deadlock Avoidance Work?
Deadlock avoidance works by letting the operating system know the process requirements of resources to complete their execution, and accordingly, the operating system checks if the requirements can be met without causing a deadlock. The following steps are involved in deadlock avoidance:
The process must tell the operating system the maximum number of resources it may ever need.
The operating system identify the resource allocations and multiple requests are fired by processes to examine if granting a request would potentially result in a deadlock.
The operating system checks if the resulting state of the system after granting the request would cause a deadlock or not.
If the resulting state is safe, the request is granted, and the process can continue execution.
If the resulting state is unsafe, the request is denied, and the process must wait until the required resources become available.
Deadlock avoidance technique(method) helps to avoid deadlock to occur in the system. So, Wait for Graph technique is used for deadlock avoidance.
Wait for Graph Technique
Wait for Graph’s concept is used in the deadlock avoidance, but it can’t bear the large database, it is designed mainly for small databases.
In the Wait for Graph, to create the relationship in the among of resources and transactions. If, any time transaction is needed of resources then it fires the request for those resources, but that same time those resources are already hold by other transactions. Then they are persisted at the one edge on the Wait for Graph. So, If Wait for Graph is converted into cycle form then deadlock is happened into system, otherwise it is not persisted into system.
Safe State
Whenever process fires the requests for available resource, then system must have to decide that if immediate allocations free the system in safe state.
System is in safe state if there exists a sequence <P1, P2, …, Pn> of ALL the processes in the systems such that for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with j < I
Then is –
If, Pi resource does not require immediately available, then Pi have to wait until completely Pj have been finished.
Whenever Pj is getting ending, then Pi can receive required resources, execute, return allocated resources, and terminate.
If Pi terminates, then Pi+1 can get its required resources, and so on.
Primary Facts –
If system is getting in the safe state, then does not happen deadlock
If system is getting in the unsafe state, then may be occur deadlock
If ensure that system will never going to enter an unsafe state, then Avoidance is getting.
Deadlock Avoidance can be solved by two different algorithms, such as –
One instance of a resources type – To use a Resource Allocation Graph
Several instance of a resources type – To use Banker’s Algorithm
Resource Allocation Graph
In the Resource Allocation Graph, to represent of all states of system in the graphically form. Resource Allocation Graph contains the whole information related to all processes those are hold by few resources otherwise getting to wait for some resources.
Example
Vertices have two varieties, Resource and Process. Every vertices is shown by different shape, such as Circle represents a process, and other side rectangle represents a resources.
Resources may be containing the multiple instances, and every instance will be represented by a dot inside the rectangle.
Other Example
Let’s walk through a simple example of deadlock avoidance using a Resource Allocation Graph (RAG) and the four main resource allocation policies: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait.
Consider a system with two processes, P1 and P2, and three resources, R1, R2, and R3. The system keeps track of the resource allocation and request status using an RAG. Here’s the initial state of the system:
Resources:
R1 R2 R3
Processes:
P1 P2
In RAG (Resource Allocation Graph), Initially, there are no edges in the graph, indicating that no resources are allocated or requested.
Let’s go through a sequence of resource requests and allocations, ensuring that the deadlock avoidance policies are followed:
Mutual Exclusion: Resources must be non-shareable.
P1 requests R1.
The request is granted, and an edge is added from P1 to R1 in the RAG.
P2 requests R1.
Since R1 is already allocated to P1, P2’s request is denied, adhering to mutual exclusion.
Hold and Wait: Processes must request all the resources they need at the beginning.
P1 requests R2.
The request is granted, and an edge is added from P1 to R2 in the RAG.
P2 requests R2.
P2’s request is granted because P2 doesn’t hold any resources and is requesting all the resources it needs. P2 requests R3.
The request is granted, and an edge is added from P2 to R3 in the RAG.
No Preemption: Resources cannot be preempted.
P1 requests R3.
P1’s request is denied because it already holds R1 and R2, and it cannot preemptively take R3 from P2.
Circular Wait: Processes can only request resources in increasing order of their values.
P2 requests R1.
The request is denied because R1 has a lower value than the previously allocated resources (R2 and R3).
With these resource allocation policies, we’ve ensured that no deadlock conditions are met:
Mutual Exclusion prevents multiple processes from holding the same resource simultaneously.
Hold and Wait ensures that processes request all the resources they need at once.
No Preemption prevents resources from being taken away from a process.
Circular Wait enforces a specific order of resource allocation requests.
With helping of these policies, we can avoid the conditions necessary for a deadlock to occur in this example. The system can continue to allocate and release resources as needed by the processes without getting stuck in a deadlock situation.
Banker’s Algorithm
Banker’s Algorithm is used to resource allocation and deadlock avoidance that determine to safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.
Banker’s Algorithm is named because it is implemented in the banking sector, and main objective of using this algorithm is to check that loan can be sanctioned or not to clients.
Example
Let’s go through a simple example of the Banker’s Algorithm.
Suppose we have three types of resources (A, B, and C) and five processes (P0, P1, P2, P3, and P4). The available resources are:
Now, let’s use the Banker’s Algorithm to determine whether a resource request from one of the processes can be granted. Suppose process P1 requests (1, 0, 0) additional resources. We need to check if the system remains in a safe state after granting this request.
Available (A, B, C) = (3, 3, 2) – (1, 0, 0) = (2, 3, 2)
Check if the system is in a safe state:
To check for safety, we can use a simple algorithm that simulates resource allocation. The idea is to try and allocate resources to processes while keeping track of the available resources. If all processes can complete, the system is in a safe state. If any process cannot complete, the system is not safe.
Let’s go through the safety check:
Initially, the available resources are (2, 3, 2).
Try to satisfy the resource requests of the processes in a sequence. We start with P0, as it’s the first process in the order:
P0’s request (0, 1, 0) can be satisfied. Now available resources are (2, 4, 2).
Continue with P3:
P3’s request (0, 1, 1) can be satisfied. Now available resources are (2, 5, 3).
Continue with P4:
P4’s request (0, 0, 2) can be satisfied. Now available resources are (2, 5, 5). Now, P2 is the only remaining process, and it can complete using the available resources (2, 5, 5).
Since all processes can complete, the system is in a safe state, and the request from P1 can be granted.
If the request is granted, update the allocation and available matrices accordingly:
The Banker’s Algorithm ensures that resource requests are granted only if they leave the system in a safe state, thus preventing deadlock.
FAQs (Frequently Asked Questions)
What is meant by deadlock avoidance in distributed system?
Deadlock Avoidance is a method that is used by the operating system to avoid the deadlock problem.
What is deadlock avoidance in OS with example?
Deadlock Avoidance is a process that is going to use by operating system to check whether the system is existing in a safe mode or in an unsafe mode.
What is difference between deadlock prevention and avoidance?
The deadlock prevention makes ensure that at least one of necessary conditions to cause a deadlock will never happen; but deadlock avoidance make ensures that system will not enter an unsafe state.
Which is deadlock avoidance algorithm in OS?
The Banker’s algorithm is a resource allocation and deadlock avoidance algorithm that is introduced by Edsger Dijkstra. It helps to prevent the single thread from entering the similar lock more than once.
Bottom Lines
Now, I make ensure that you have been fully understood about deadlock avoidance in OS (Operating System) and deadlock avoidance algorithm in OS with ease. If this article is helpful for you, then please share it along with your friends, family members or relatives over social media platforms like as Facebook, Instagram, Linked In, Twitter, and more.
