Saturday, January 7, 2017

What is deadlock in computing?


In a multi-programming environment, Processes want resources to do their corresponding process. When a process requests a resource and if it is not available at that instant, then the process enters to a waiting state. Sometimes this process can’t get out from the waiting state because the process has been hold by another process. This situation is called a deadlock. 

Let’s discuss this situation in detail.



A System has finite number of resources to distribute among finite number of competing processes. CPU cycles, I/O devices (scanners, printers) and files are examples for resources. Each resource may have one or more instances (If a system has three printers, then the resource type printer has three instances). As an example, when we consider printing a document as a process, then we want printer as a resource. 
 

A process may use a resource instance/s in this order


1.Request – The process requests a resource. If resource instance/s is available, then allocate that requested resource instance/s to requesting resource. Otherwise requesting process has to wait until requested resource is available.
2.Use – Requested resource instance/s has been allocated and process can operate in the resource.
3.Release – The process releases the resource instance/s.

Examples for system calls that used to request and release a resource.


Request system calls - request(), open(), allocate()
Release system calls - release(), close(), free()

(System call - System calls provide an interface between the process and the operating system which allow user-level processes to request some services from the operating system.)

A process must request a resource instance/s before using it and also must release the resource instance/s after using it. A process may request as many instances from a resource if it is required. The number of resource instances requested may not exceed the total number of resource instances available in the system.

 The operating system has records about each resources whether it is free or not. If a process request resource instance/s, operating system check whether that resource instance/s is free or not. If it is free then resource instance/s is allocated. Otherwise that process is added to a queue of processes waiting for this resource. A set of processes is in a deadlock state when every process in the set is waiting for an event that can caused only by another process in the set. 


Deadlock involving the same resource type.


Consider a system with two printers. Two processes hold one of these printers. Meanwhile each process request another printer. Each process is waiting until the event “printer is released”. Which can be caused only by one of the other waiting process. Now each processes in deadlock state.

Deadlock involving the different resource type


Consider a system with one printer and one scanner. There are two processes and one process (p1) is holding a printer and other process (p2) is holding a scanner. If p1 requests a scanner and p2 requests a printer, then system is in deadlock state and both processes are ceased. 



My next article will describe about necessary conditions for deadlocks.

If you like this post, spread by sharing it on social media. Thank you ! 





2 comments:

How to send Slack notification using a Python script?

 In this article,  I am focussing on sending Slack notifications periodically based on the records in the database. Suppose we have to monit...