Part 3

Bounded Overtaking Allocation Strategy

The groundsman now starts to get complaints from the better (and more aggressive) players. They are being kept waiting because some novice, who requires a large number of golfballs, is ahead of him in the queue. What is needed is some compromise between giving priority to expert players (requiring fewer golfballs) while preventing novices from waiting forever. One day, when being hit over the head by the golf club of an irate expert, the solution came to him. The policy he adopts is bounded overtaking. A player can be overtaken by not more than k players. In the example below, k = 3.

To Do

3) Provide an implementation for class BoundedOvertakingAllocator which enforces the above strategy:

class BoundedOvertakingAllocator implements Allocator{
    // n golfballs, bound b
    public BoundedOvertakingAllocator(int n, int b) {...}
    synchronized public void get(int n) {...}
    synchronized public void put(int n) {...}
 }

Note: the solution to part 3 is far from obvious. This part carries only 10% of the total marks and should only be attempted if you have the time.

Hand in:

Listings for parts 1-3.