Busy Waiting

How do we implement a mutual exclusion policy? No matter what policy we implement, a process that is about to enter its critical section must first check to see if any other processes are in their critical sections. As we shall see, there are, potentially, an number of ways to enforce mutual exclusion. Ideally, we would like to implement a policy that works in the most efficient way possible.

What about using a lock variable, which must be tested by each process before it enters its critical section? If another process is already in its critical section, the lock is set to 1, and the process currently using the processor is not permitted to enter its critical section. If the value of the lock variable is 0, then the process enters its critical section, and it sets the lock to 1. The problem with this potential solution is that the operation that reads the value of the lock variable, the operation that compares that value to 0, and the operation that sets the lock, are three different atomic actions. With this solution, it is possible that one process might test the lock variable, see that it is open, but before it can set the lock, another process is scheduled, runs, sets the lock and enters its critical section. When the original process returns, it too will enter its critical section, violation the policy of mutual exclusion.

The only problem with the lock variable solution is that the action of testing the variable and the action of setting the variable are executed as seperate instructions. If these operations could be combined into one indivisible step, this could be a workable solution. These steps can be combined, with a little help from hardware, into what is known as a TSL or TEST and SET LOCK instruction. A call to the TSL instruction copies the value of the lock variable and sets it to a nonzero (locked) value, all in one step. While the value of the lock variable is being tested, no other process can enter its critical section, because the lock is set. Let us look at an example of the TSL in use with two operations, enter_region and leave_region:

   enter_region: (executed when a process wants to enter its critical section)

     tsl register, lock    // copy lock to register and set lock to 1
     cmp register, 0       // see if lock variable was set
     jnz enter_region      // if lock was set, loop
     ret                   // enter critical section

   leave_region: (executed when a process wants to leave its critical section)

     mov lock, 0           // store a 0 in lock variable
     ret                   // done

You can see from the example above that if a process is interrupted after executing the TSL, there is no danger that another process might enter its critical section. This is so because the lock variable is set to a non-zero value while the original process is testing it. Another advantage of the TSL instruction is that it works on machines with many processors as well.

Look closely at the code for the "enter_region" example, and you will see that if a process tests a variable which is locked, it will continue to test the variable again and again until it can enter its critical section. In other words, as long as a process is denied access to its critical section, it will stay in a tight loop and wait until it can proceed, all the while wasting processor time. This continuous testing of the lock variable is called busy waiting. Mutual exclusion policies that require busy waiting waste valuable processor time, and in some cases can lead to situations where a process will test the lock variable forever, a very undesirable occurence.

             
IPC Home    Subway     Solution     Sleep 
  Page       Map        Types