9.4 Revised Golf Ball Allocator

9.4 Revised Golf Ball Allocator

Fortunately, we can encapsulate the ticketing scheme described in the previous section in a revised implementation of the allocator monitor. Other than using this revised implementation in place of SimpleAllocator, no other changes are required to the program. The new implementation, called FairAllocator, is listed in Program 9.4.

Program 9.4: FairAllocator class.

 public class FairAllocator implements Allocator {   private int available;   private long turn = 0; //next ticket to be dispensed   private long next = 0; //next ticket to be served   public FairAllocator(int n) { available = n; }   synchronized public void get(int n)           throws InterruptedException {     long myturn = turn; ++turn;     while (n>available ||  myturn != next) wait();     ++next; available -= n;     notifyAll();   }   synchronized public void put(int n) {     available += n;     notifyAll();   } }

We have added two instance variables to implement the ticketing scheme: next records the value of the next ticket to be served, and turn records the value of the next ticket to be dispensed. A thread gets a ticket by recording it in the local variable myturn. Remember that each time a thread calls the method get, a new activation record is created. Consequently, a new copy of myturn is also created which is only used by the calling thread. A thread is now blocked until there are sufficient golf balls and its ticket is the next one to be served. To keep the code simple, we have not dealt with resetting the ticket when the maximum ticket value is reached. However, by using 64-bit ticket values, we have ensured that, with a player arrival rate of one per second, the program will run for 300 billion years before ticket overflow becomes a problem!

Figure 9.6 shows a screen dump of the revised golf club applet. The changed behavior can clearly be seen. Although two golf balls are available, players g1 and h1 are waiting because they cannot overtake f4 due to the FIFO ordering enforced by the ticketing scheme.

Figure 9.6: Golf Club applet with fair allocation.