- All Implemented Interfaces:
- java.lang.Iterable<E>, java.util.Collection<E>, java.util.concurrent.BlockingQueue<E>, java.util.Queue<E>
public class BalancedBlockingQueue<E>
Exponentially Balanced BlockingQueue.
Elements are fed off the queue as in a tiered priority system. Each element is assigned a
priority level, which determines what tier that element resides on. Elements are taken off
the highest priority level first, then the next highest, and so on. However, because blind priority
overrides can lead to starvation of lower-priority items, this also has an overflow valve. After
of one priority are fed, one element of the next level is fed.
For example, suppose you use a levelBound of 2 with 3 distinct priority levels. The order of feeding occurs
1. 2 elements of priority 3 are fed off the queue
2. 1 element of priority 2 is fed off the queue
3. 2 elements of P3 are fed
4. 1 element of P2 is fed
5. 2 elements of P3 are fed
6. 1 element of P1
Thus, if the
N, and there are
M priority levels, then the number of
elements that must be fed off the queue before an item of priority
In this sense, this queue is exponentially fair
The above analysis assumes infinitely full levels, so that there are always items available at each priority level.
Obviously, in the real world, this is not guaranteed to be true. If a given level has no items, then it will
feed an item of the next priority level lower. However, once successfully done, it will reset its level; as long
as that level is empty, it will feed lower priority tasks, but as soon as an item becomes available on that level,
that level will behave as if it just started the expontial count over again (e.g the next priority level will have
to wait until a full level bound number of elements are fed off the level, or the level to become empty again).
This class is thread-safe, and implements all the optional operations of Iterator and Collection.