Operating System Part-3

Define the four necessary conditions that characterize deadlock ?

Deadlock can arise if four conditions hold simultaneously.

1. Mutual exclusion: only one thread at a time can use a resource .

2. Hold and wait: a thread holding at least one resource is waiting to acquire additional resources held by other threads.

3. No preemption: a resource can be released only voluntarily by the thread holding it, after that thread has completed its task .

4. Circular wait: there exists a set {T0 , T1 , …, Tn } of waiting threads such that T0 is waiting for a resource that is held by T1 , T1 is waiting for a resource that is held by T2 , …, Tn–1 is waiting for a resource that is held by Tn , and Tn is waiting for a resource that is held by T0 .

• If graph contains no cycles => no deadlock

• If graph contains a cycle=>

  • if only one instance per resource type, then deadlock

  • if several instances per resource type, possibility of deadlock

What are the methods for handling Deadlock?

• Ensure that the system will never enter a deadlock state:

   Deadlock prevention  Deadlock avoidance

• Allow the system to enter a deadlock state and then recover

• Ignore the problem and pretend that deadlocks never occur in the system.

Explain Deadlock Prevention.

Explain Deadlock Avoidance.

Explain Bankers Algorithm.

When a process requests a set of resources, the system must determine whether allocating these resources will leave the system in a safe state. If yes, then the resources may be allocated to the process. If not, then the process must wait till other processes release enough resources.

Explain Deadlock Detection.

Systems haven’t implemented deadlock-prevention or a deadlock avoidance technique, then they may employ DL detection then, recovery technique.

1. Single Instance of Each resource type (wait-for graph method)

   • A deadlock exists in the system if and only if there is a cycle in the wait-for graph. In order to detect the deadlock, the system needs to maintain the wait-for graph and periodically system invokes an algorithm that searches for the cycle in the wait-for graph.

2. Multiple instances for each resource type

   • Banker Algorithm

Explain Recovery From Deadlock.