5.6.3 Deadlocks and StarvationThe implementation of a semaphore with a waiting queue may result in asituation where two or more processes are waiting indefinitely for an eventthat can be caused only by one of the waiting processes. The event in questionis the execution of a signal() operation. When such a state is reached, theseprocesses are said to be deadlocked.To illustrate this, consider a system consisting of two processes, P0 and P1 ,each accessing two semaphores, S and Q , set to the value 1:P0 P1wait(S); wait(Q);wait(Q); wait(S);. .. .. .signal(S); signal(Q);signal(Q); signal(S);Suppose that P0 executes wait(S) and then P1 executes wait(Q) . When P0executes wait(Q) , it must wait until P1 executes signal(Q) . Similarly, whenP1 executes wait(S) , it must wait until P0 executes signal(S) . Since thesesignal() operations cannot be executed, P0 and P1 are deadlocked.We say that a set of processes is in a deadlocked state when every processin the set is waiting for an event that can be caused only by another processin the set. The events with which we are mainly concerned here are resourceacquisition and release. Other types of events may result in deadlocks, as weshow in Chapter 7. In that chapter, we describe various mechanisms for dealingwith the deadlock problem.Another problem related to deadlocks is indefinite blocking or starvation,a situation in which processes wait indefinitely within the semaphore. Indefi-nite blocking may occur if we remove processes from the list associated with asemaphore in LIFO (last-in, first-out) order.