Ограниченный PriorityBlockingQueue

Насколько я знаю, я бы создал подкласс и перезаписал метод put, чтобы обеспечить это. Если это произойдет, создайте исключение или сделайте то, что кажется подходящим.

Что-то вроде:

public class LimitedPBQ extends PriorityBlockingQueue {

    private int maxItems;
    public LimitedPBQ(int maxItems){
        this.maxItems = maxItems;
    }

    @Override
    public boolean offer(Object e) {
        boolean success = super.offer(e);
        if(!success){
            return false;
        } else if (this.size()>maxItems){
            // Need to drop last item in queue
            // The array is not guaranteed to be in order, 
            // so you should sort it to be sure, even though Sun's Java 6 
            // version will return it in order
            this.remove(this.toArray()[this.size()-1]);
        }
        return true;
    }
}

Edit: и добавляет, и помещает предложение вызова, поэтому переопределения должно быть достаточно

Edit 2: теперь должен удалить последний элемент, если он превышает maxItems. Однако может быть более элегантный способ сделать это.

Если порядок выполнения Runnables, которые вы хотите выполнить, не строгий (как есть: может случиться, что некоторые задачи с более низким приоритетом будут выполнены, несмотря на существование задач с более высоким приоритетом), то я бы предложил следующее, что сводится к периодическому уменьшению размера PriorityQueue:

if (queue.size() > MIN_RETAIN * 2){
    ArrayList<T> toRetain = new ArrayList<T>(MIN_RETAIN);
    queue.drainTo(toRetain, MIN_RETAIN);
    queue.clear();
    for (T t : toRetain){
      queue.offer(t);
    }
}

Это, очевидно, не сработает, если порядок должен быть строгим, так как осушение приведет к моменту, когда задача с низким приоритетом будет извлечена из очереди с использованием параллельного доступа.

Преимущества в том, что это потокобезопасно и, вероятно, получится так же быстро, как и при использовании конструкции приоритетной очереди.

Посмотрите на ForwardingQueue из Google Collections API. Для семантики блокировки можно использовать Semaphore.