Deadlocks in operating systems

Deadlocks in operating systems

Deadlock Introduction

In a multiprogramming environment, several processes may compete for limited resources. When a process request resources and if resources are not available, then the process is going to be in the state of “wait state”. If the waiting state is not gonna change again since the resources are held by other waiting processes. 

It  situation is called as “Deadlock”.

Resources types:

• CPU cycles
• memory
• I/O devices

Each process utilise the resources as follows:

• Request
• Use
• Release

Deadlock Characterisation

• Mutual exclusion : only one process at a time can use a resource
• Hold and wait : A process holding at least one resource is waiting to acquire additional resources are held by other processes
• No preemption : A process can be released only voluntarily by the process it holding it, after that process has completed it task
• Circular wait : there exists a set of processes which are waiting for the resources circularly.

Methods for handling deadlocks

1.Ensure that the systems is never going to enter deadlock state

• Deadlock prevention
• Deadlock avoidance

2.Allow the system to have a deadlock state and recover

Ignore the problem and pretend that the deadlock never happens in the system.(used by the most operating systems)

Deadlock prevention

prevent the conditions which occur the have deadlocks

• Mutual exclusion : not required for shareable resource(readonly); must hold for non-shareable resources
• Hold and wait : must guarantee that whenever a process request a resource then it foes not hold another process
• No preemption : process will be restarted only when it can regain its old resources.
• Circular wait : impose a total ordering of all resources types. and required that each process requests resources in an increasing order of enumeration.

Deadlock avoidance 

the deadlock avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition.

Avoidance algorithms

• single instance of a resource type : use a resource-allocation graph

• multiple instance of a resource  type : use the banker’s algorithm