SHORT REVIEW ABOUT DEADLOCK

INTRODUCTION

A process in operating systems uses different resources. For a process to use a particular resource, it has to request for the resource, use the resource and release it after use in that manner. 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.

DEADLOCK

Deadlocks are a set of blocked processes each holding a resource and waiting to acquire a resource held by another process.



METHODS FOR HANDLING DEADLOCKS

Generally speaking there are three ways of handling deadlocks:

1. Deadlock prevention or avoidance - Do not allow the system to get into a deadlocked state.


2. Deadlock detection and recovery - Abort a process or preempt some resources when deadlocks are detected.


3. Ignore the problem all together - If deadlocks only occur once a year or so, it may be better to simply let them happen and reboot as necessary than to incur the constant overhead and system performance penalties associated with deadlock prevention or detection. This is the approach that both Windows and UNIX take.

DEADLOCK PREVENTION

Deadlocks can be prevented by preventing at least one of the four required conditions:

Mutual Exclusion

• Shared resources such as read-only files do not lead to deadlocks.


• Unfortunately some resources, such as printers and tape drives, require exclusive access by a single process.

Hold and Wait

To prevent this condition processes must be prevented from holding one or more resources while simultaneously waiting for one or more others. There are several possibilities for this:

• Require that all processes request all resources at one time. This can be wasteful of system resources if a process needs one resource early in its execution and doesn't need some other resource until much later.


• Require that processes holding resources must release them before requesting new resources, and then re-acquire the released resources along with the new ones in a single new request. This can be a problem if a process has partially completed an operation using a resource and then fails to get it re-allocated after releasing it.


• Either of the methods described above can lead to starvation if a process requires one or more popular resources.

No Preemption

Preemption of process resource allocations can prevent this condition of deadlocks, when it is possible.

• One approach is that if a process is forced to wait when requesting a new resource, then all other resources previously held by this process are implicitly released, ( preempted ), forcing this process to re-acquire the old resources along with the new resources in a single request, similar to the previous discussion.


• Another approach is that when a resource is requested and not available, then the system looks to see what other processes currently have those resources and are themselves blocked waiting for some other resource. If such a process is found, then some of their resources may get preempted and added to the list of resources for which the process is waiting.


• Either of these approaches may be applicable for resources whose states are easily saved and restored, such as registers and memory, but are generally not applicable to other devices such as printers and tape drives.

Circular Wait

• One way to avoid circular wait is to number all resources, and to require that processes request resources only in strictly increasing (or decreasing) order.


• In other words, in order to request resource Rj, a process must first release all Ri such that i >= j.


• One big challenge in this scheme is determining the relative ordering of the different resources.

 

DEADLOCK DETECTION

A deadlock occurrence can be detected by the resource scheduler. A resource scheduler helps OS to keep track of all the resources which are allocated to different processes. So, when a deadlock is detected, it can be resolved using some particular methods.

If deadlocks are not avoided, then another approach is to detect when they have occurred and recover somehow. In addition to the performance hit of constantly checking for deadlocks, a policy /algorithm must be in place for recovering from deadlocks, and there is potential for lost work when processes must be aborted or have their resources preempted.

RECOVERY FROM DEADLOCK

There are three basic approaches to recovery from deadlock:

1. Inform the system operator, and allow him/her to take manual intervention.


2. Terminate one or more processes involved in the deadlock


3. Preempt resources.

ADVANTAGES OF DEADLOCK METHOD

Here, are pros/benefits of using Deadlock method

• This situation works well for processes which perform a single burst of activity


• No preemption needed for Deadlock.


• Convenient method when applied to resources whose state can be saved and restored easily


• Feasible to enforce via compile-time checks


• Needs no run-time computation since the problem is solved in system design

DISADVANTAGES OF DEADLOCK METHOD

Here, are cons/ drawback of using deadlock method

• Delays process initiation


• Processes must know future resource need


• Pre-empts more often than necessary


• Dis-allows incremental resource requests


• Inherent preemption losses.

 

REFERENCES

Coulouris, George (2012). Distributed Systems Concepts and Design. Pearson. p. 716. ISBN 978-0-273-76059-7.

Padua, David (2011). Encyclopedia of Parallel Computing. Springer. p. 524. ISBN 9780387097657. Retrieved 28 January 2012.

Silberschatz, Abraham (2006). Operating System Principles (7th ed.). Wiley-India. p. 237. ISBN 9788126509621. Retrieved 29 January 2012

http://www2.latech.edu/~box/os/ch07.pdf

http://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/7_Deadlocks.html