Process Deadlock in OSs

Abstract

Within a multiprogramming environment in modern computing systems, several processes may fight and compete over resources required to complete their tasks. If the resources required are not available for a specific process, the process will enter the waiting state. In some cases such waiting state never changes because the required resources are held by other waiting processes. Such phenomenon is called a deadlock that can happen within any operating system. Despite the fact that applications can identify programs that may cause the deadlock situation; operating system typically do not provide the mechanism that can facilitate the deadlock-prevention and it remains as part of the effort of the applications developers to ensure during their application design, that their application is free of deadlock (Silberschatz and Galvin, 2009).

Silberschatz and Galvin (2009) explained that a computing system consists of a finite number of resources that can be used by competing processes (such as CPU cycles, I/O devices, files and memory). Such resources might have several instance, for example, if a system have two processors, then the resource type CPU has two instances. When the request occurs by the process, for an instance of a resource type; the required resource type satisfies the request. A process must first do the request before using it to ensure availability of such resource. Also, a process may request as many resources as it needs to carry out its tasks. However, the number of resources requested may not exceed the total number of resources available in the system. That said, resources are shared among processes; and as such a set of process is in a deadlock state when every process in the set is waiting for resource that is hold by another process in the same set. Such resources can be physical resources (such as printers, CPU cycles, memory space, and I/O devices) or logical resources (such as files, monitors, and semaphores).

The occurrence of the Deadlock

Silberschatz and Galvin (2009) explained that the deadlock state happens when a process is in execution state that never ends because it is waiting for a resource that is held by other process, the system resources are tied up; and as such preventing other jobs from starting. A deadlock situation will occur if one of the four of the following conditions are raised, and hold simultaneously during the process execution:

 

  • Mutual execution – where at least one process holding a resource in a non-sharable mode; and as such only one process can use the resource at a time.
  • Hold and wait – where a process is holding at least one resource and requesting additional resources that are currently being held by other processes.
  • No pre-emption – where a resource can be released only voluntarily by the process holding it, after that the process has completed its task.
  • Circular wait – where a set of process are in a waiting state (P0…Pn); and as such process (P0) is waiting for a resource held by process (P1) and a process (P1) is waiting for a resource held by process (Pn) and process (Pn) is waiting for a resource held by process (P0).

Gupta (2009) suggested that for the system to recover from the deadlock state, a process termination is required to be implemented with the system. With applying such technique, all the processes that are involved in the deadlock cycle must be aborted, and it can be done by implement one of the following techniques in the system:

 

  • Abort all the processes involved in the deadlock cycle. However, such technique is too expensive to implement since many processes that would be aborted might be in the finishing state, and the re-computation for such processes has to restart again from scratch.
  • Abort only a single process involved in the deadlock cycle and the system will check for deadlock. If the deadlock still standing, abort another process and the system will continue the aborting procedure by a single process at a time until the system is recovered from the deadlock state.

Lee and Mooney (2005) explained that the system is in deadlock state if the system has a set of processes where each of them is blocked, and waiting for resources that never being available. On the other hand the deadlock avoidance is a way of dealing with deadlock state where resources utilizations are dynamically controlled to avoid reaching the deadlock state.

 Preventing the Deadlock

 For deadlock state to occur with any computing system the four necessary conditions mentioned above must hold simultaneously; and as such by ensuring that one of these conditions cannot hold, the occurrence of a deadlock can be avoided. The following examine the solution for the four necessary conditions for deadlock:

 

  • Mutual Exclusion – where a process is holding for non-sharable resources. Such scenario can’t be prevented because some resources are intrinsically non-sharable (i.e. a printer cannot be simultaneously shared by several processes).
  • Hold and wait – to ensure such condition never occurs in the system; a protocol must be implemented that guarantee that whenever a process requests a resource, it does not hold any other resources.
  • No pre-emption – to ensure that this condition does not hold; a protocol should be implemented to ensure that if a process is holding some resources and requests another resource that cannot be immediately allocated to such process; then all resources that such process is currently holding must be implicitly released.
  • Circular wait – one way to ensure that this scenario never holds, a protocol must be implemented to impose a total ordering of all resource types, and to require that each process requests resources in an increasing order of enumeration.

Lee and Mooney (2005) explained that to avoid the deadlock, avoidance algorithm is used where it’s required and as such the applied algorithm required for each process to declare the maximum requirements of each resource available within the system that will ever needs. However, deadlock avoidance is more expensive than the deadlock detection and it has the following drawbacks:

 

  • An avoidance algorithm must be executed prior granting resources for every request.
  • Deadlock avoidance tends to restrict resources utilization which may lead to a system’s performance degradation.
  • The maximum resources required by any process might not be known in advance.

Conclusion

Silberschatz and Galvin (2009) explained that a deadlock state occurs when two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes. A deadlock can occur only if four necessary conditions hold simultaneously in the system: Mutual Exclusion, Hold and Wait, No Pre-emption, and Circular Wait; and as such to prevent deadlocks, implementation should be in place to ensure that at least one of the necessary conditions never holds. There are three basic principal methods that can be used to resolve the deadlock state:

 

  • Implementing a protocol that can prevent or avoid deadlock; and as such ensuring that the system will never encounter a deadlock state.
  • Allow the system to enter a deadlock state, and the system must detect it, and then recover it.
  • The system can ignore the problem and pretend that deadlocks never occur in the system.

Holidayand Abbadi (n.d.) explained that a method for avoiding deadlock, rather than preventing it, requires that the operating system have prior information about how each process will utilize system resources.  If a system has no implementation of a protocol that can ensure that deadlocks will never occur, then a detection-and-recovery scheme may be employed; and as such a deadlock detection algorithm must be invoked to determine whether a deadlock has occurred.

Finally, with implementing such schema; if a deadlock is detected, the system must recover either by terminating some of the processes involved in the deadlock or by releasing some resources used by the processes involved in the deadlock (Holidayand Abbadi, n.d.).

References

Holiday, J. & Abbadi, A. (n.d.) Distributed Deadlock Detection [Online]. Available from: http://www.cse.scu.edu/~jholliday/dd_9_16.htm (Accessed: 21 August 2010).

Gupta, H. (2009) How to Recover from Deadlock [Online]. Available from: http://www.associatedcontent.com/article/1310956/how_to_recover_from_deadlock.html?cat=4 (Accessed: 21 August 2010).

Lee, J. & Mooney V. (2005) ‘Hardware/software partitioning of operating systems: focus on deadlock detection and avoidance’, Computer and Digital Techniques, IEE Proceedings, pp. 167-182, IEEE Journal [Online]. Available from: http://ieeexplore.ieee.org.ezproxy.liv.ac.uk/stamp/stamp.jsp?tp=&arnumber=1454198 (Accessed: 21 August 2010).

Silberschatz, A. & Galvin, P. (2009) Operating System Concepts. 8th ed. NJ: John Wiley & Sons, Inc.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: