DeadLock ⇒ If two or more processes are waiting on happening of some event, which never happens, then we say these processes are involved in deadlock then that state is DeadLock.

or

• It is a situation where each of the computer process wait for a resource which is being assigned to another process. In this situation none of the process gets executed since the resources it needs, is held by another process waiting for another resources being released.

![Untitled](<https://prod-files-secure.s3.us-west-2.amazonaws.com/79230e93-a4fd-4bfc-97cb-6b8c1af7fd09/59904d3e-01c5-4ef5-8237-602464bb5ff8/Untitled.png>)

• Necessary Condition for DeadLock:
  1. Mutual Exclusion. →
     1. Resources must be shared and used in a Mutual exclusive way(one by one),
     2. which means one resource can’t be used by multiple proceses at the same time.
  2. No Preemption. →
     1. There must not be any release of resources (premption) by a process due to any other process.
  3. Hold and Wait. →
     1. A process must hold the accquired resources while waiting for another resources.
  4. Circular Wait. →
     1. The waiting condition should form a waiting loop b/w the processes.

• Concepts of DeadLock
  • DeadLock Characteristics : Mutual Exclusion, No Premeption, Hold and Wait, Circular Wait.
  • DeadLock Prevention: Avoid any One Condition.
  • DeadLock Avoidance: Banker’s Algorithm.
  • DeadLock Detection: RAG (Resource Allocation Graph).
  • DeadLock Recovery.

Resource Allocation Graph(RAG)

• IT is the most efficient and convenient way to represent the state of the system,i.e , how to the resources are allocated , is there any deadlock.

• It has 2 components:

  • Vertex → Process Vertex, and Resource Vertex.
    • where Process Vertex → Each process is represented by a vertex in circle.
    • Resource Vertex → All the resources are represented as vertex but in rectangle.
    • Single Instance resources → which is only one in count. (ex: CPU)
    • Mutli Instance resources → which is more than one in quantity. (ex: Register)
  • Edge → Assigned Edge, and Request Edge.
    • Assigned Edge → edge from resource to process (means , the resource is assigned to that process).
    • Request Edge → edge from process to resource (means, process is asking for resource).

  How to check DeadLock in a RAG.

  • Single Instance Resources

    • DeadLock occurs

      

    • No DeadLock

      

    • Note:

      • If the waiting is finite → then it is starvation.
      • If the waiting is infinite → then it is deadLock.
      • If RAG has a Circular Wait (means it is cyclic) → then it is Always a DeadLock. and vice-versa in case of Single Instance Resources.

  ---

  • Multi Instance Resources

    • MI(multi Instance) and CW(circular wait) , but no DeadLock

      

      ![Untitled](<https://prod-files-secure.s3.us-west-2.amazonaws.com/79230e93-a4fd-4bfc-97cb-6b8c1af7fd09/d166ad61-7af8-4d5b-989a-c7980365d558/Untitled.jpeg>)
    

    • Note:
      • If Multi-Instance and circular wait its not always true that it gets in deadlock.

• Note:
  • if n processes are there and m resources are there, then:
    • for deadLock free execution:
      • max number of resources req → n-1 .
      • min number of resources req → n+1 .

Various Method to Handle DeadLock

1. DeadLock ignorance (Ostrich Method) Used in Real Life

   • Just Ignore the deadLock
   • Used widely by Windows and Linux, as these OS handles many codes and functions, so to don’t get affected by deadlock handling part then ignore it.
   • Ignoring to maintain performance and speed, as deadlock occurs rarely.
   • Ex: hang , lagg are solved by closing the tab or powering off.

   ---

2. DeadLock prevention

   • Here we try to prevent those 4 necessary conditions of deadlock or atleast any 1 of them to prevent the happening of deadLock.
     • The necessary condition to make false.

       • Mutual exclusion. ⇒ false by making the resources shareable among the processes.

         • but some resource like printer, tape drives mutual exclusion can’t be removed.

       • No premeption. ⇒ false by making prempting processes by using Time Quantum.

         

       • Hold and wait. ⇒ false by giving all the resources to the process before it started exceution, so it doesn’t hold and wait.

       • Ciruclar wait. ⇒ false by giving resources a number and processes can request for resources in increasing order.

         

   ---

3. DeadLock Avoidance (by Banker’s Algorithm)

   • here we check the Safe and Unsafe state.

   ---

4. DeadLock Detection and Recovery