In this blog, we are gonna discuss DEADLOCKS
Firstly, these Deadlock topics have come across in Data Base Management Systems
Before going with a deep discussion with Deadlocks first we have to know
what is a ## DeadLock?
Here is the answer:
Basically, a Deadlock is a situation that occurs in OS when any process enters a waiting state because another waiting process is holding the demanded resource. Deadlock is a common problem in multi-processing where several processes share a specific type of mutually exclusive resource known as a soft lock or software.
Now we will see how we can prevent Deadlocks
PREVENTION OF DEADLOCKS
Let us discuss it as an example for better clarity
Suppose they are 2 buses on the same road. Let us assume that one bus is in one direction. And there is another bus in another direction which is exactly opposite to the first bus. They are no way for two buses to move on until and unless one bus takes back or there is a chance of collision in which damage on both sides is unpredictable.
Imagine the same situation in the case of the operating system when they are two or more statements executing at the same time there may be the chance of more errors and even in the worst cases, failures can also happen.
The same is the situation with the deadlock if we become able to violate any condition among the four and do not let them occur together then there can be prevented from the deadlock problem.
So those four conditions are
1. Mutual Exclusion 2. Hold and wait 3. No preemption 4. Circular Wait
Now let’s elaborate or explain these 4 conditions one by one
1. Mutual Exclusion:
Generally, this condition must hold for non-sharable resources. For example, a laptop cannot be simultaneously shared by two or more people. In contrast, Sharable resources do not require mutually exclusive access and thus cannot be involved in a deadlock. A good example of a sharable resource is Read-only files because if several processes attempt to open a read-only file at the same time, then they can be granted simultaneous access to the file. A process need not to wait for the sharable resource. Generally, deadlocks cannot be prevented by denying the mutual exclusion condition because there are some resources that are intrinsically non-sharable.
2. Hold and Wait:
Hold and wait condition occurs when a process holds a resource and is waiting for another resource to complete its execution. Thus if we did not want the occurrence of this condition then we must guarantee that when a process requests a resource, it does not hold any other resource.
There is some set of conditions or systematic procedures that can be used in order to ensure that the Hold and Wait condition never occurs:
- According to the first conditions; Each process must request and gets all its resources before the beginning of its execution.
- The second condition allows a process to request resources only when it does not occupy any resource.
They are also disadvantages while using these Conditions
1.The usage of resources is very low.
2.There is a possibility of Starvation.
3.No Preemption:
Before going to No Preemption we will first we have to know what Is Preemption?
Preemption is used in OS in which we are going to interrupt a task intentionally or wontedly temporarily so that we are gonna resume the task at a later time.
Now we will see what is No Preemption
We already know what is Preemption. To be No Preemption it has to satisfy the following condition does not hold the following protocols can be used :
- According to the First Protocol: “If a process that is already holding some resources requests another resource and if the requested resources cannot be allocated to it, then it must release all the resources currently allocated to it.”
- According to the Second Protocol: “When a process requests some resources, if they are available, then allocate them. If in case the requested resource is not available then we will check whether it is being used or is allocated to some other process waiting for other resources. If that resource is not being used, then the operating system preempts it from the waiting process and allocates it to the requesting process. And if that resource is being used, then the requesting process must wait”.
We are gonna see the last one in Deadlock Prevention
4. Circular Wait:
The fourth necessary condition is a Circular wait
In order to ensure violate this condition we can do the following:
Assign a priority number to each resource. There will be a condition that any process cannot request a lesser priority resource. This method ensures that not a single process can request a resource that is being utilized by any other process and due to which no cycle will be formed.
Finally, we can tell that out of these 4 conditions only Circular wait can be practicably possible.
This is about Deadlock Prevention
Now, we will discuss in detail Deadlock detection and Avoidance
Deadlock Detection:
If a system does not use a deadlock prevention technique or the deadlock avoidance technique, there is a probability that a deadlock will occur. In order to avoid deadlocks, the operating system examines the system for any deadlocks on a regular basis. The OS will recover from the deadlock using recovery mechanisms after it has been discovered.
Deadlock Detection has mainly two types:
1. If a resource has a single instance
2. If a resource has multiple instances
If a resource has a single instance:
In single-instanced resource types, if a cycle is being formed in the system, there will definitely be a deadlock.
If a resource has multiple instances
In multiple instanced resource type graphs, detecting a cycle is not just enough. We have to apply the safety algorithm on the system by converting the resource allocation graph into the allocation matrix and request matrix.
This is a brief description of Deadlock Detection
Now we will see what is Deadlock Avoidance
Deadlock Avoidance:
Before going into a discussion about Deadlock Avoidance we must know what is Deadlock Avoidance.
Generally, Deadlock avoidance is the request for any resource that will be granted if the resulting state of the system doesn’t cause deadlock in the system. The state of the system will continuously be checked for safe and unsafe states.
In Deadlock Avoidance, we are using Banker’s Algorithm
What is Banker’s Algorithm?
Bankers Algorithm is a resource allocation and deadlock avoidance algorithm which test all the request made by processes for resources, it checks for the safe state, if after granting a request system remains in the safe state it allows the request and if there is no safe state it doesn’t allow the request made by the process.
Inputs to Banker’s Algorithm:-
- Max need of resources by each process.
- Currently, allocated resources by each process.
- Max free available resources in the system.
The request will run and follow the above conditions.