Blocking FIFO Queue with Ability to Skip Elements?

Question

Short Version: How can I best implement a blocking FIFO queue in Java with the ability to temporarily skip or jump over items in the queue if they don't meet certain criteria at the time that they are popped from the queue?

Long Version:

I have been using an ArrayBlockingQueue for many years in an application and it has worked fine for my purposes. I have only ever needed to call put() and take() so far. It has worked fine.

Now there is a requirement that an element meet certain criteria when it is retrieved via take(). If it does not meet the criteria it should go back on the queue but in the same position it was previously.

Imagine a line at customs at an international airport. For some reason the passengers were only given the customs declaration form as they got on the line. The passengers are all scribbling furiously to finish their form before their turn comes up. There is a security guard at the front of the line. When the customs officer is ready for the next passenger the security guard checks if the first passenger on the line has filled out the customs declaration. If so, he sends the pasenger to the customs officer. If not, he checks the second passenger, then the third, etc, until he finds someone who's finished. He sends that person to the customs officer. The same happens each time the customs officer is free, always starting the first passenger on the line.

In researching the only thing I came up with was to use a double ended queue (deque) and take elements off the front until I find an element that meets the criteria. Then put the elements back onto the front in the reverse order that I took them off.

Does anyone have a recommendation?

Answer 1

2 possible suggestions depending on whether or not you're able to listen for status changes on the items:

• If the items can notify you when they are ready, then just number them as they arrive and move them into a PriorityQueue as soon as they are ready. Then just pull the first item from the PriorityQueue, blocking if it is empty.

• If you have to check each item to determine if its status has changed, then you have no choice but to visit every item in turn, starting at the oldest, until you find one that is ready. In this case you really don't need a Queue as the underlying datastructure; a LinkedList is actually a better fit.

The second case is not just slower, it's also worse for dealing with a full queue of items that are not ready; either you pause for some amount of time (while blocking) at the end of the list before restarting, or your blocking behaviour is equivalent to a busy-wait as it repeatedly cycles through the items.

(If I were stuck implementing the second, I'd be inclined to try to dynamically tune the wait-before-restart time, based on the total amount of accumulated time waiting to be ready and the expected probability of at least one being completed the next time I start walking the list.)

Answer 2

Have your structure create a second Queue. Acquire an write lock on the whole structure when you pop. Ignore the main queue for a moment and check the secondary queue first. If it's empty, go to the main queue. Pop an element off the main queue. If it's ready, take it and release the lock. If it's not, put it in the secondary queue, and grab another. Repeat until you're ready.

If the secondary queue wasn't empty when you first tried to grab it, cycle through the secondary queue to see if any of them are ready.

The pros of this is that you always get someone that's ready now. Unless of course you exhaust your main queue, but then there is no one who is ready so, not much you can do there.

The cons of this is that if you have some super slow people, the secondary queue might be a problem. You can solve this by providing an estimate of the remaining time or something. Also, it's always possible that bad actors could lie or otherwise tie you up. But if you have no way to preempt bad actors you're going to have trouble multithreading anyway.

Here's a non-thread-safe version of the algorithm - it's just off the top of my head, so take it with a grain of salt.

class SnappyQueue<E> {
    Queue<E> main = ... // people waiting in line
    Queue<E> slugs = ... // people at the front but still writing
    void push(E e) { main.addLast(e); }
    E pop() {
        E first = slugs.peek();
        if(first != null) {
            for(E cur = slugs.pop(); cur != first; cur = slugs.pop()) {
                if(cur.isReady()) return cur; // we're done, one of the slugs is ready
                slugs.push(cur); // this slug isn't ready, put it back
            }
        }
        while(true) {
            E cur = main.pop();
            if(cur == null) return null; // nothing left
            if(cur.isReady()) return cur; // we found someone ready
            slugs.push(cur); // not ready, push them into the slug line
        }
    }
}