next up previous
Next: Semaphores Up: Process Coordination Previous: Disabling Context Switching

Busy Waiting

Another possible technique for mutual exclusion is to use busy waiting. We can introduce a Boolean variable called mutex that is set to true when an activity is in a critical section, to false otherwise. A process executes the following code before it enters a critical section:

while  mutex do 
    do nothing
mutex <- true;
and the following code when it exits the region:
mutex <- false

Unfortunately, this code is wrong. If two processes start executing the while loop at the same time, they might both get past the loop and enter their regions. The problem is that the checking and setting of the Boolean are done in two statements. A process that has tested the Boolean variable may be rescheduled before it sets the variable.

Let us assume that the `test and set' can be done in one instruction, so that the code looks like:

while  (TestAndSet(mutex)) do 
    do nothing
where TestAndSet looks like:
atomic function TestAndSet (var Lock: Boolean): Boolean;
    TestAndSet <- Lock;
    Lock <- true
end TestAndSet;
The solution is not good since the CPU may spend a lot of time executing the while loop which does no useful work. In particular, if the `waiting' process is a high priority process waiting for a lower priority process to set the Boolean variable to false, the CPU will spend all its time executing the loop. However several computers offer such an instruction as the low-level alternative to disabling interrupts in a multiprocessor system.

Prasun Dewan
Tue Feb 24 14:38:40 EST 2004