Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.
Consider an example when two trains are coming toward each other on same track and there is only one track, none of the trains can move once they are in front of each other. Similar situation occurs in operating systems when there are two or more processes hold some resources and wait for resources held by other(s). For example, in the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is acquired by process 2, and process 2 is waiting for resource 1.
How to avoid Deadlocks
Deadlocks can be avoided by avoiding at least one of the four conditions, because all this four conditions are required simultaneously to cause deadlock.
- Mutual Exclusion
Resources shared such as read-only files do not lead to deadlocks but resources, such as printers and tape drives, requires exclusive access by a single process.
- Hold and Wait
In this condition processes must be prevented from holding one or more resources while simultaneously waiting for one or more others.
- No Preemption
Preemption of process resource allocations can avoid the condition of deadlocks, where ever possible.
- Circular Wait
Circular wait can be avoided if we number all resources, and require that processes request resources only in strictly increasing(or decreasing) order.
Handling Deadlock
The above points focus on preventing deadlocks. But what to do once a deadlock has occurred. Following three strategies can be used to remove deadlock after its occurrence.
- Preemption
We can take a resource from one process and give it to other. This will resolve the deadlock situation, but sometimes it does causes problems.
- Rollback
In situations where deadlock is a real possibility, the system can periodically make a record of the state of each process and when deadlock occurs, roll everything back to the last checkpoint, and restart, but allocating resources differently so that deadlock does not occur.
- Kill one or more processes
This is the simplest way, but it works.
Critical Section is the part of a
program which tries to access shared resources. That resource may be any
resource in a computer like a memory location, Data structure, CPU or any IO
device.
The critical section cannot be executed
by more than one process at the same time; operating system faces the
difficulties in allowing and disallowing the processes from entering the
critical section.
The critical section problem is used to
design a set of protocols which can ensure that the Race condition among the
processes will never arise.
In order to synchronize the cooperative
processes, our main task is to solve the critical section problem. We need to
provide a solution in such a way that the following conditions can be
satisfied.
Primary
Mutual Exclusion
Our solution must provide mutual
exclusion. By Mutual Exclusion, we mean that if one process is executing inside
critical section then the other process must not enter in the critical section.
Progress
Progress means that if one process
doesn't need to execute into critical section then it should not stop other
processes to get into the critical section.
Secondary
Bounded Waiting
We should be able to predict the
waiting time for every process to get into the critical section. The process
must not be endlessly waiting for getting into the critical section.
Architectural Neutrality
Our mechanism must be
architectural natural. It means that if our solution is working fine on one
architecture then it should also run on the other ones as well.