Sleep and Wakeup using Semaphores

As we have seen, sleep and wakeup is a solution to the problem of race conditions which does not require busy waiting. One must be careful in implementing a sleep and wakeup policy, since race conditions can arise in certain circumstances. Consider the following implementation of sleep and wakeup.

  
   var occupied;        // 1 if critical section is occupied, 0 if not. 
   var blocked;         // counts the number of blocked processes

   Enter_Region:        // process enters its critical section
   {
     IF (occupied){                     // if critical section occupied
       THEN blocked = blocked + 1;      // increment blocked counter   
       sleep();                         // go to "sleep", or block 
       }
     ELSE occupied = 1;                 // if can enter critical section, 
                                        // increment counter   

   }
       ...
       ...                              // critical section
       ...
                 
   Exit_Region:          // process exits its critical section  
   {
      occupied = 0;
      IF (blocked){ 
        THEN wakeup(process);           // if another process is sleeping,
                                        // wake the process up.
        blocked = blocked - 1;          // decrement blocked counter
        }
   }                       

In the example above, a process wanting to enter its critical section must first check to see if any other processes are currently in the critical section. If so, the process calls the Sleep() system call, which causes it to block. Upon leaving its critical section, a process must check to see if any other processes have been put to sleep, waiting to enter their critical section. If a process is waiting, the process now exiting its critical section must wakeup the sleeping process.

Now consider what would happen if two processes, A and B, where using this method for mutual exclusion. Process A enters its critical section, and before it leaves the critical section, process B is scheduled. Now process B attempts to enter its critical section. It sees that process A is already there, so it increments the "blocked" variable in preparation to go to sleep. Just before it can call the Sleep primitive, process A is scheduled again. Process A exits its critical section. Upon exiting, it sees that the "blocked" variable is now 1, so it calls Wakeup on process B. But process B is not yet asleep. The Wakeup is lost, so when process B is scheduled again, it will call Sleep, and block forever.

Semaphores allow a Sleep and Wakeup mutual exclusion policy to be implemented without the risk of loosing a Wakeup. Basically, a semaphore is a new type of variable. Semaphores can have a value of 0 (meaning no Wakeups are saved), or a positive integer value, indicating the number of sleeping processes. Two different operations can be performed on a semaphore, DOWN and UP , coresponding to Sleep and Wakeup.

Let us look at an example of semaphores. In figure A, there are three semaphores: S1 has a value of zero and process P1 is blocked on S1; S2 has a value of three, meaning three more processes may execute a down operation on S2 without being put to sleep; S3 has a value of zero, and has two sleeping processes, P4 and P5, blocked on it.

Now let us look at what happens when a process executes an UP on S1. In figure B, process P1 is activated by an UP operation. It executes a DOWN on S1 and enters its critical section. The state of the semaphores after these actions has now changed.

Here is an example of how semaphores are used to enforce mutual exclusion:

  semaphore mutex;      // variable's value is restricted to 0 or 1.


    DOWN(mutex);          // execute a DOWN on mutex before entering
      ...                 // critical section
      ...


    UP(mutex);            // execute an UP on mutex when leaving
                          // critical section

The value of a semaphore need not always be 0 or 1. Semaphores can have a value greater than one. The original value of the semaphore dictates the total number of processes that can enter a specific region at a time. For instance, a semaphore with an original value of 4 would allow four processes to enter the section of code they protect. We will see in later examples how this is useful.

               
IPC Home    Subway    Solution    Sleep &  Monitors
  Page       Map       Types      Wake Up