9.6 Bounded Overtaking Golf Ball Allocator

9.6 Bounded Overtaking Golf Ball Allocator

Bounded overtaking is implemented in the allocator of Program 9.5. The program follows the algorithm used in our model. Each thread waits if there are insufficient balls available or if the bound has been reached and the player is not next. Overtaking players are added to the overtakers set and removed as necessary when next is updated; the count of those overtaken is incremented and decremented on addition and removal respectively.

Program 9.5: BoundedOvertakingAllocator class.

 public class BoundedOvertakingAllocator                    implements Allocator{   private int TM;      //must be maximum active threads + bound   private int available;   private int bound;   private int turn = 1;   private int next = 1;   private int overtaken =0;   private BitSet overtakers;   public BoundedOvertakingAllocator(int n, int b)     { available = n; bound = b; TM = 10000+b;       overtakers = new BitSet(TM+1);}   synchronized public void get(int n)            throws InterruptedException{     int myturn = turn; turn = turn%TM + 1;     while (n>available ||           (myturn!=next && overtaken>=bound)) {       wait();     }      if (myturn!=next)  {           overtakers.set(myturn); ++overtaken;      }      else  {           next =  next%TM + 1;           while (overtakers.get(next)) {                overtakers.clear(next);                --overtaken;                next =  next%TM + 1;           }      }     available -= n;     notifyAll();   }   synchronized public void put(int n) {     available += n;     notifyAll();   } }

The operation of the bounded overtaking allocator can be seen in the applet display shown in Figure 9.7. This captures the situation in which player f4 has been overtaken by players g1, h1 and i1. Since the overtaking bound, which has been set to three, has been exceeded, players j1 and k1 are blocked although there are two golf balls available. They will remain blocked until f4 has been served.

Figure 9.7: Golf Club with bounded overtaking allocator (bound = 3).