Operating System Deadlocks

Deadlocks Definition:
In a multiprogramming system, processes request resources. If those resources are being used by other processes then the process enters a waiting state. However, if other processes are also in a waiting state, we have deadlock.

 

The formal definition of deadlock is as follows:
Definition: A set of processes is in a deadlock state if every process in the set is waiting for an event (release) that can only be caused by some other process in the same set.

 

Example
example-5-1

 

In this chapter, we shall analyze deadlocks with the following assumptions:

  • A process must request a resource before using it. It must release the resource after using it. (request -> use -> release)
  • A process cannot request a number more than the total number of resources available in the system.

 

For the resources of the system, a resource table shall be kept, which shows whether each process is free or if occupied, by which process it is occupied. For every resource, queues  shall be kept, indicating the names of processes waiting for that resource.

 

A deadlock occurs if and only if the following four conditions hold in a system simultaneously:

1. Mutual Exclusion: At least one of the resources is non-sharable (that is; only a limited number of processes can use it at a time and if it is requested by a process while it is being used by another one, the requesting process has to wait until the resource is released.).

 

2. Hold and Wait: There must be at least one process that is holding at least one resource and waiting for other resources that are being hold by other processes.

 

3. No Preemption: No resource can be preempted before the holding process completes its task with that resource.

 

4. Circular Wait: There exists a set of processes: {P1, P2, …, Pn} such that
P1 is waiting for a resource held by P2
P2 is waiting for a resource held by P3

Pn-1 is waiting for a resource held by Pn
Pn is waiting for a resource held by P1

 

Methods for handling deadlocks are:

  1.  Deadlock prevention
  2.  Deadlock avoidance
  3.  Deadlock detection and recovery

 

Try Now – Operating Systems MCQs
Practice Now – Operating System Online Test