java - Priority concurrent queue which removes lowest priority element when size reaches queue's capacity

Question

I use PriorityBlockingQueue. It is thread safe and allows priority. But I need following functionality:

When new element is added to queue and size of queue is equal capacity then first (lowest priority) element is removed. Is there some queue which fulfill my requirements?

Answer 1

There is no Collection that offers ordering, concurrency and bounded capacity at the same time, so you have to pick two of those features and add a hand-written solution for the third.

However checking the size is trivial and equally thread-safe with the PriorityBlockingQueue:

while (myQueue.size() >= THRESHOLD) {
  Element e = myQueue.poll();
  if (e != null) {
    process(e);
  }
}
myQueue.add(newElement);

Now the well-educated multithreader will immediately spot the non-thread-safe implementation I have chosen (only the counting, the list is always thread-safe), this is however probably ok. The worst thing that could happen is that the queue is pushed over the limit by at maximum as many threads as are asking minus one. So with 4 threads, the queue could be at limit + 3, while with 100 threads it could be at limit + 99.

Now depending on how many threads you use and how critical it is to stay below the limit, there are 3 things you can do:

1. Accept that the limit is sometimes violated.
2. If you have only a few threads, set the limit to the actual limit minus number of threads.
3. Add a synchronization variant to ensure that only one thread is running the above instruction.