Introduction to Deadlocks

What is Deadlock?

• A system is said be in deadlock state, when it’s process are waiting for a particular “event” to occur that never occurs.
• The “event” is nothing other than a process in the system releases a resource which is on hold by that process forever.
• The resources are allocated based on following sequence hence called Resource Allocation Sequence.
  • Request:  A process request for a resource.
  • Use: A process is using the resource.
  • Release: A process releasing the resource.

Deadlock Conditions

• Mutual Exclusion (Mutex)

  • Resource can be allocated for a single process (i.e., non-shareable resource) and probability of occurrence of deadlock is increased.
  • For example: Process P1 exclusively holding the resource R1 for long time (not forever) without allowing other process P2 to use.
  • Real world example: In a single road (R1), one car (P1) is occupying the whole road not allowing the opposite car (P2) to pass through.

• Hold and Wait

  • If a process holding on some resource and wait on other resource, then the probability of this process go in a deadlock is increased.
  • For example: P1 is holding on R1 and R2 together and wait for R3 which is held by other process P3 for a long time (not forever) , then P1 is said to become in deadlock.
  • Real world example: Restaurant server (P1) is holding the prepared foods for table1 (R1) and table2 (R2) to be served, until table3 food (R3) is prepared by the chef (P3).

• No-Preemption

  • The process won’t release the resources until it completes its whole process on all resources, which can take a long time. The probability of other process go in a deadlock can be increased (who waits on some of the resource held by the first process).
  • For example: Process P1 occupying resources R1, R2, R3 and P1 completes the process on R1, but still process on R2 and R3 are pending. P1 won’t release R1 until it completes its process on R2 and R3.
  • Real world example: Kitchen chef  (P1) don’t want to release the prepared food for table1 (R1), until he finishes preparing food for table2 (R2) and table3 (R3).

• Circular-Wait

  • When processes are waiting for each other to complete in a circular fashion, then processes are said to be in circular wait. (there is no probability, deadlock is occurring for the process).
  • For example: When there are 3 process, each process wait for each other in a circle to complete (P1-> P2-> P3 ->P1), then they are in circular wait deadlock state.
  • Real world example: Circular linked-list process are competing each for a resource and nobody gets that resource.

Conclusion

• Whenever a Circular-Wait condition occurs, the deadlock is bound to take place, and it will increase other 3 conditions of deadlock in the system. (i.e.Mutex, Hold & Wait and No-Preemption).
• If conditions such as Mutex (or) Hold & Wait (or) No-Preemption take places, one cannot say a deadlock is bound to occur because they are the probable conditions of deadlocks, hence it’s called as Indirect cause of deadlock.
• On other hand, if Circular-Wait condition occurs, there is a deadlock in the system for sure, hence it’s called a Direct cause of deadlock.

Other useful definitions

Starvation

• When a low priority process does not get access to the resources it needs, because there is a high priority process accessing the resources.
• The entire system of processes hasn’t come to halt in this case; only few processes are starved.
• If entire processes in the system are starving, then system is said to be in deadlock.
• Deadlock is an extreme case of starvation with the criterion of extremeness being the total count of process unable to access the resource in the system.

Race Condition

• A race occurs when two or more threads try to access the same shared data and at least one of the accesses is a write operation.
• A race condition occurs when two or more threads can access shared data and they try to change it at the same time.
• Problems often occur when one thread does a “check-then-act” (e.g. “check” if the value is X, then “act” to do something that depends on the value being X) and another thread does something to the value of X in between the “check” and the “act”.
• Real world example: You are planning to go to a movie at 5 pm. You inquire about the availability of the tickets at 4 pm. The representative says that they are available. You relax and reach the ticket window 5 minutes before the show. I’m sure you can guess what happens: it’s a full house. The problem here was in the duration between the check and the action. You inquired at 4 and acted at 5. In the meantime, someone else grabbed the tickets. That’s a race condition – specifically a “check-then-act” scenario of race conditions.

Critical Section

• Parts of the program where the shared resource is accessed are protected. This protected section is the critical section or critical region.
• It cannot be executed by more than one process at a time.