No Busy Waiting

When we use semaphores (or any other synchronization construct) to solve a concurrency problem (such as mutual exclusion or any of the other ones we shall see), we usually want a solution that has no busy waiting.

Let us clarify what is meant by "no busy waiting". Suppose we want a process to wait until a condition B holds. No busy waiting means that the process has to wait on a semaphore (or whatever synchronization construct we happen to be using). It cannot wait by executing a while loop in which it repeatedly checks B, as in:

while not B do skip

or as in the following (if B and S need to be checked in a critical section):

P(mutex);
if not B
  then { V(mutex); go to L }
  else { V(mutex) };

"No busy waiting" also means that whenever the process wakes up from waiting, the condition it was waiting for should hold. That is, it must not wake up, find the condition false, and again wait on the same semaphore. This condition is really just the previous condition in a more general setting; for example, it rules out the following kind of wait:

P(mutex);
if not B
  then { "irrelevant code;
         V(mutex);
         "more irrelevant code";
         go to L
  }
  else { "still irrelevant code;
         V(mutex)
  };

Here is a solution without busy waiting:

P(mutex);
if not B
  then { V(mutex);
         P(waitforB);
  };

And you would ensure that waitforB is signalled if code gets executed that makes B true. That is, whenever there is a possibility of B becoming true, execute:

P(mutex);
if B
  then { V(waitforB);
         V(mutex);
  };