Deadlocks and Starvation

• The implementation of a semaphore with a waiting queue may result in a situation where two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes.
• The event in question is the execution of a $signal()$ operation. When such a state is reached, these processes are said to be deadlocked.
• To illustrate this, we consider a system consisting of two processes, $P_0$ and $P_1$, each accessing two semaphores, $S$ and $Q$, set to the value 1:

  
  • Suppose that $P_0$ executes $wait(S)$ and then $P_1$ executes $wait(Q)$.
  • When $P_0$ executes $wait(Q)$, it must wait until $P_1$ executes $signal(0)$.
  • Similarly, when $P_1$ executes $wait(S)$, it must wait until $P_0$ executes $signal(S)$.
  • Since these $signal()$ operations cannot be executed, $P_0$ and $P_1$ are deadlocked.
• Another problem related to deadlocks is indefinite blocking, or starvation, a situation in which processes wait indefinitely within the semaphore.
• Indefinite blocking may occur if we add and remove processes from the list associated with a semaphore in LIFO (last-in, first-out) order.