/ COMPUTER-FUNDAMENTAL

DeadLock

DeadLock

DeadLock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.

As an example, in the below diagram, Process 1 is holding Resource 1 and waiting for Resource 2 which is acquired by process 2, and process 2 is waiting for Resource 1.

runtime2

DeadLock can arise if the following four conditions hold simultaneously

  • Mutual Exclusion: Only one Process can use one Resource at a time
  • Hold and Wait : A Process is holding at least one Resource and waiting for Resources
  • No Preemption : A Resource cannot be taken from a process unless the Process releases the Resource
  • Circular Wait : A set of Processes are waiting for each other in circular form

Methods of handling DeadLock

  • DeadLock prevention
  • DeadLock aviodance
  • DeadLock detection and recovery
  • DeadLock ignorance

DeadLock Prevention

This method is not to let the four conditions happen, that is, it denies every four conditions.

  • Mutual Exclusion prevention
    It allows processes to use one Resource simultaneously. This circumstance will arise a synchronization problem.
  • Hold and Wait prevention
    A Process requires all Resources simultaneously and waits for until get permission. It bans any waiting for another Resource.
  • No Preemption prevention
    If no one holds one Resource, it allows the highest priority Process to hold it.
  • Circular Wait prevention
    It allows Processes to require Resources in one way.

    This Method will raise some disadvantages, such as lost of system handling and efficiency.

DeadLock Avoidance

When CPU can distribute every Resources to Processes without DeadLock, the situation is called “Safe State”.
If CPU can find the sequence that does not affect DeadLock, it is called “Safe Sequence”.
However, Unsafe State is the opposite to Safe State, that is, can raise DeadLock.

Avoidance allows CPU to keep allocating Reosurces all the time to stay in “Safe State”.
We use “Banker’s Algorithm” to avoid DeadLock.

DeadLock detection and recovery

Once DeadLock occurs, detect it and recover it.

  • Detection
    CPU detects whether DeadLock occurs or not.
  • Recovery
    CPU uses recovery method to get out of Circular Wait.
    • Seize one or more Processes
      1. Shut all Processes in DeadLock down
        Some normal Processes can be shut down and lost the works.
      2. one check, one pass
        CPU stops Every single Process and detect DeadLock. It is heavy work.
    • Preemption
      CPU preempts the allocated Resource and allocates it to another Process until DeadLock solved.

DeadLock Ignorance

If DeadLock is very rare, then let it happen and reboot the system.