9.3 A First-InFirst-Out Binary Semaphore | The .NET Developers Guide to Directory Services Programming

< Day Day Up >

9.3 A First-In/First-Out Binary Semaphore

In Chapter 2, a binary semaphore was introduced to protect a critical region in the swap method of an object. The semaphore allowed a thread to obtain a lock when it entered a method and to release the lock when it left the method, thereby ensuring that only a single thread could be in that method at any one time. This scheme of locking and unlocking was used to illustrate the behavior of a synchronized block in Java; however, this semaphore was unfair in that if more than one thread was waiting for the semaphore the first thread to begin waiting was not necessarily the thread that would obtain the semaphore after another thread released it. This behavior mirrors the behavior of the Java synchronized statement, where the same unfair locking can occur.

The fact that a semaphore is unfair is normally not a problem. In fact, it allows the semaphore to be implemented more simply and to work well with thread priorities, but occasions arise when it would be nice to have a way to make sure that threads obtain the semaphore in the order in which they began waiting for it. Such a semaphore is a first-in/first-out binary semaphore (FIFOBS).

This section implements just such a FIFOBS using the type of monitor introduced in Chapter 3. However, because the rules on notify and notifyAll on an object do not allow the system to choose which thread will be given the semaphore, a notification object will be used for the notify in the state diagram so that a specific thread (the one waiting the longest) can be notified. This change shows how a notification object can be included in the simple monitor to greatly enhance the capabilities of the monitor object.

The rest of this section shows how to use a notification object in a monitor by using the example of the FIFOBS. The first step involves designing the state diagram for the component, as shown in Exhibit 1. The state diagram for this component is very similar to the state diagram for the unfair semaphore from Chapter 2. This is true because the basic operations of the semaphore remain the same. In fact, it would be easy to define a binary semaphore interface and then simply instantiate the type of binary semaphore (fair or unfair) to be used at run time. The only thing that changes is the way in which the translations between the states for the monitor are handled in the program.

Exhibit 1: Binary Semaphore State Diagram

click to expand

Exhibit 2: Program9.1: FIFOBS implementation

 import java.util.Vector; import java.util.Random; public class FIFOBS {   private boolean locked; // State of the semaphore   private Vector waiting; // Vector of notification objects                           // Objects are released in the order                           // in which they are entered into                           // the vector.   /**    * Public constructor. Set the monitor state and create the    * waiting object vector.    */   public FIFOBS () {     locked = false;     waiting = new Vector();   }   /**    *  Get the lock on this semaphore if it is available. If the    *  lock is not available, then put a notification object on    *  the wait list to wait until the semaphore is free.    */   public void getLock(){     Object waitObject = new Object();     synchronized(waitObject) {       synchronized(this) {         if (locked) {           waiting.addElement(waitObject);         }         else{           waitObject = null;// No need to wait, get rid of                    // object         }         locked = true; // Note that this must be set                        // while holding the semaphore                        // object (this) lock.       }       if (waitObject ! = null) {         try {           waitObject.wait();         } catch (InterruptedException e) {         }       }     }   }   /**    *  Release the lock on the semaphore.  If any thread is    *  waiting, notify the thread that has been waiting the longest;    *  do not release the lock. This allows the lock to transfer    *  to the notified thread. Because the lock is never true, it    *  cannot be acquired by any other thread. If no threads are    *  waiting, set the semaphore to unlocked.    */   public synchronized void releaseLock() {     if (waiting.size() > 0) {       Object wakeObject = waiting.firstElement();       waiting.removeElementAt(0);       synchronized(wakeObject) {        wakeObject.notify();       }     }     else {       locked = false;     }   } /**  * Main test program.  */ public static void main(String args[]) {     FIFOBS fifobs = new FIFOBS();     Thread a[] = new Thread[10];     for (int i = 0; i < 10; ++i) {       (new Thread(new testP(fifobs, i))).start();     }   } } /**  *  This class simply creates the thread that allows us to test  *  the semaphore.  */ class testP implements Runnable {   FIFOBS fifobs;   int id;   Random random;   public testP(FIFOBS fifobs, int id) {     this.fifobs = fifobs;     this.id = id;     random = new Random(id);   }   public void run() {     try {       Thread.sleep(random.nextInt(500));       System.out.println("Process"+ id + "Waiting");       fifobs.getLock();       System.out.println("Process" + id + "In Critical           Section");       Thread.sleep(500);       System.out.println("Process" + id + "Free");       fifobs.releaseLock();     } catch(InterruptedException e) {     }   } }

The code for the FIFOBS is given in Exhibit 2 (Program9.1). Because a specific thread is to be notified when the lock is free, the threads do not all wait on the monitor object, and all waiting threads are not notified to check the monitor when the state changes. Instead, each thread waits on a specific object, and the FIFOBS implements a queue of these objects. When the lock is freed, the FIFOBS takes the first object off of the queue and notifies that specific object. Because only one thread is waiting on that object, and that thread is the one that has been waiting the longest, that thread will be the one that is notified and will begin running. Thus, the FIFOBS is a fair semaphore.

In this program, the simpler test that the object is in the correct state as a precondition has been replaced by a more complex implementation that allows the object to wait and notify on a specific notification object. The reason for this complexity has to do with the format of the notification object. Because the notification object requires that the lock on the "this" object (in this case, the monitor object) be dropped before waiting on the notification object, accommodations must be made to make sure that all access to critical data (operations that must occur in a program critical region) only occur in the synchronized block on the "this" (monitor) object. Operations that occur while the notification object lock is held cannot be considered to be inside of the critical region, as the lock on the "this" object is what protects the critical region. Therefore, the presence of a notification object causes the critical section in the monitor to be broken between the checking of the precondition and the code and post-condition parts of the method.

The reason this was not a problem in the monitor as defined in Chapter 3 was that the lock on the monitor was obtained before the state of the monitor was checked, and no changes were made unless the monitor was in the correct state, allowing the lock to then be held through the rest of the method. If the monitor was not in the correct state, the lock was dropped, but the precondition was never part of the critical section of the program. With the notification object, the state can be checked and the thread allowed to enter the monitor with the lock on the "this" object not held. Attempting to obtain the lock with a later "synchronized(this)" block is also not sufficient, because a race condition can occur before the lock is obtained again.

To prevent this race condition, the FIFOBS in Exhibit 2 (Program9.1) handles the critical data in a more ad hoc fashion. First, if the lock is not set, the thread sets it inside of what is basically the precondition, while the lock on the "this" object is held. If the lock is already held by another thread, the current thread will do a wait on a notification object. When the running thread attempts to release the lock, it first checks to see if any threads are waiting on the lock. If so, it notifies the waiting thread and does not set the lock to false, in effect transferring the lock to the new thread and not allowing any other thread an opportunity to obtain the lock. If no threads are waiting, it would set the lock to false, in effect releasing the lock so that it can be obtained by any thread.

Exhibit 2 (Program9.1) shows how a notification object can be merged with a simple monitor; however, it lacks the simplicity and consistency of the monitors in Chapter 3, where all methods consisted of a precondition guard, the program code, the post-condition processing, and a return value. For simple situations, this ad hoc method of adding the notification object to a monitor is not difficult, but it would be nice to generalize a methodology for adding a notification object to a monitor. One example of doing this is found in Exhibit 3 (Program9.2). In this program, a new state is created from which the getLock method can be called. This new state is dependent on the number of threads waiting for this object. If the lock is taken or any thread is currently waiting, the thread will be forced to wait on the notification object's queue. The only other consideration necessary is to show that no harmful race condition exists between the time the "this" object's lock is dropped and it is reacquired in the getLock method. This is left for an exercise.

Exhibit 3: Program9.2: Alternative FIFOBS Implementation with Preand Post-Conditions

 import java.util.Vector; import java.util.Random; public class FIFOBS {   private boolean locked;   private Vector waiting;   /**    *  Public constructor. Initialize the locked variable and    *  create waiting vector.    */   public FIFOBS () {     locked = false;     waiting = new Vector();   }   /**    *  Get the lock on this semaphore if it is free. Note that    *  here the method still has pre- and post-conditions, but    *  extra code for locking has to be considered to make this    *  work.    */   public void getLock(){     // Pre-condition for the wait object.     Object waitObject = new Object();     synchronized(waitObject) {       synchronized(this) {         waiting.addElement(waitObject);         if (! (locked || waiting.size() > 1))           waitObject = null;       }       if (waitObject ! = null) {         try {           waitObject.wait();         } catch (InterruptedException e) {         }       }     }     // Code section. Note the absence of a race condition here,     // as a thread only comes through when no one is waiting     // or the lock is free.     synchronized (this) {       locked = true;       waiting.removeElementAt(0);     // Post-condition. Note that the notifyAll here on the     // monitor is useless as no threads are ever waiting on the     // monitor itself. Also note that the synchronized block     // from the code section should include the post-condition     // processing.     }   }   /**    *  Release any locks held. If any threads are waiting,    *  notify the one waiting the longest that this lock is    * now free. Note that the lock variable can be changed    * in this method now.    */   public synchronized void releaseLock() {     // Pre-condition is locked as "true," but this thread holds     // the lock, so it must be true.     // Code section     locked = false;     // Post-condition. Note you can only notify on notify object     // if someone is waiting.     if (waiting.size() > 0) {       Object wakeObject = waiting.firstElement();       synchronized(wakeObject) {         wakeObject.notify();       }     }   }   /**    * Main test program.    */   public static void main(String args[]) {     FIFOBS fifobs = new FIFOBS();     Thread a[] = new Thread[10];     for (int i = 0; i < 10; ++i) {       (new Thread(new testP(fifobs, i))).start();     }   } } /**  * This class simply creates the thread that allows us to test  * the semaphore.  */ class testP implements Runnable {   FIFOBS fifobs;   int id;   Random random;   public testP(FIFOBS fifobs, int id) {     this.fifobs = fifobs;     this.id = id;     random = new Random(id);   }   public void run() {     try {       Thread.sleep(random.nextInt(500));       System.out.println("Process" + id + "Waiting");       fifobs.getLock();       System.out.println("Process" + id + "In Critical           Section");       Thread.sleep(500);       System.out.println("Process" + id + "Free");       fifobs.releaseLock();     } catch(InterruptedException e) {     }   } }

As shown in this section, notification objects can be combined with monitor objects to create fair components. They can also be used to optimize a component by getting rid of wasteful calls to the notifyAll method, as shown in Section 9.4.

< Day Day Up >