What is Deadloack in Operating System?

June 10, 2018 Author: munishmishra04_3od47tgp
Print Friendly, PDF & Email

A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause. Deadlocks are a set of blocked processes each holding a resource and waiting to acquire a resource held by another process.




Because all the processes are waiting, none of them will ever cause any of the events that could wake up any of the other members of the set, and all the processes continue to wait forever. For this model, we assume that processes have only a single thread and that there are no interrupts possible to wake up a blocked process. The no-interrupts condition is needed to prevent an otherwise deadlocked process from being awakened by, say, an alarm, and then causing events that release other processes in the set.
In most cases, the event that each process is waiting for is the release of some resource currently possessed by another member of the set. In other words, each member of the set of deadlocked processes is waiting for a resource that is owned by a deadlocked process. None of the processes can run, none of them can release any resources, and none of them can be awakened. The number of processes and the number and kind of resources possessed and requested are unimportant. This result holds for any kind of resource, including both hardware and software.
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.

Deadlock View

Figure: Deadlock

The Deadlock Problem

A condition that arises when two or more processes are waiting indefinitely for an event that can only be caused by one of the waiting processes

  • The events that the processes are waiting for will never happen
  • Other processes in the system that need the resources that are currently locked will never get access to them.

Operating systems do not typically provide deadlock-prevention facilities.

  • It is up to the programmer to design deadlock-free programs

Deadlock will become an even greater problem with the trend toward more processor cores and more threads

How to Prevent Deadlocks

Deadlock prevention algorithms ensure that at least one of the necessary conditions (Mutual exclusion, hold and wait, no preemption and circular wait) does not hold true. However most prevention algorithms have poor resource utilization, and hence result in reduced throughputs.

Mutual Exclusion

Not always possible to prevent deadlock by preventing mutual exclusion (making all resources shareable) as certain resources are cannot be shared safely.

Hold and Wait

We will see two approaches, but both have their disadvantages.

A resource can get all required resources before it start execution. This will avoid deadlock, but will result in reduced throughputs as resources are held by processes even when they are not needed. They could have been used by other processes during this time.

Second approach is to request for a resource only when it is not holing any other resource. This may result in a starvation as all required resources might not be available freely always.

No preemption

We will see two approaches here. If a process request for a resource which is held by another waiting resource, then the resource may be preempted from the other waiting resource. In the second approach, if a process request for a resource which are not readily available, all other resources that it holds are preempted.




The challenge here is that the resources can be preempted only if we can save the current state can be saved and processes could be restarted later from the saved state.

Circular wait

To avoid circular wait, resources may be ordered and we can ensure that each process can request resources only in an increasing order of these numbers. The algorithm may itself increase complexity and may also lead to poor resource utilization.

Handling Deadlock

The above points focus on preventing deadlocks. But what to do once a deadlock has occured. 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 cause 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.



References

[1] “Operating System | Process Management | Deadlock Introduction”, available online at: https://www.geeksforgeeks.org/operating-system-process-management-deadlock-introduction/

[2] “What is a Deadlock?” available online at: https://www.studytonight.com/operating-system/deadlocks

[3] “Deadlock Prevention, Avoidance, Detection and Recovery in Operating Systems”, available online at: https://javajee.com/deadlock-prevention-avoidance-detection-and-recovery-in-operating-systems

[4] James Moscola, “CS420: Operating Systems Deadlocks & Deadlock Prevention”, available online at: https://ycpcs.github.io/cs420-fall2017/lectures/lecture13+14+15_deadlock.pdf

No Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert