swappable work queue

Question

There's a name for this, but I don't know what it is so it's hard to google.

What I'm looking for is something in the java concurrency utilities, which is a pair of queues, an "pending" queue used by a producer, and a "processing" queue used by a consumer, where the consumer can swap the queues atomically. If used in this way (1 producer thread, 1 consumer thread), the individual queues don't need to be threadsafe, just the references to them.

I know I've seen this somewhere before, and I can probably cobble together something like this on my own, but if it exists already I'd rather use that.

edit: I guess the primitive I'm looking for is a pair of atomic references that can be atomically swapped. (& I can add the queues myself.)

---

edit 2: @Alex Miller answered the nagging question of what it was that I was thinking of but couldn't remember. However that doesn't solve my problem since it's a thread barrier and I want the producer to not have to block.

@sfossin's point about swapping references to queues is a good one; what I wanted was that the instant the consumer starts retrieving and processing items from the queue, all those queue items have to be complete and the producer can't add any items afterwards; the producer now has to add items to the other queue. So the paired/swapped set of atomic references won't work.

(It's sort of like if there are 2 school buses, one of which is always waiting for passengers and the other is always delivering them elsewhere. Once the driver pulls away, that's it, you have to get on the other bus. Having references lets producers access the bus even though it's already left, which is not allowed.)

I think what I will do instead is to use a single ConcurrentLinkedQueue and have a sentinel value that the consumer adds to the queue. This allows there to be multiple producers, not just 1. In order for the consumer to process batches of items on the queue, the consumer waits for there to be at least 1 item on the queue, then inserts the sentinel at the end of the queue, and removes items until the sentinel is removed. Then the consumer does whatever it has to do between batches. That's the behavior I wanted.

It doesn't necessarily need to be a guaranteed non-blocking approach (locking or synchronized methods are options), but if there's an easy way to architect it so that it is, that's preferred in my application.

Answer 1

There isn't a data structure with the dual queues like you describe, but the concurrent utils have a lot a different queues to choose from to make one.

The problem you describe is very common though, I kind of expected to find one as well. Maybe in Java 1.7.

Answer 2

Exchanger?

Answer 3

A reader/writer locked queue, is probably a better idea. Since, if you would otherwise have to copy to a local queue atomically.

Since you'd have a sync issue, if you swapped the references, while one was reading/deleting or writing.

RWLock would allow multiple consumers/producers.

Is there any reason, why you'd like to stay away from RWLocks?

As with any locking, the lock should be held for the minimum time possible to prevent starvation.

or use something like this for the exchanging of data. With each thread holding it's own queue.

 class LockedQueue
 {
    private final List<Data>  q = new ArrayList<Data>();
    private final Lock lock = new ReentrantLock();

    public void get( List<Data> consumerQ ) {
        if( lock.tryLock() ) { try { consumerQ .addAll( q ); q.clear(); } finally { lock.unlock(); }}
    }
    public Data put( List<Data> producerQ ) {
        if( lock.tryLock() ) { try { return q.addAll( producerQ  ); producerQ .clear(); } finally { lock.unlock(); }}
    }
    public void clear() {
        lock.lock(); try { q.clear(); } finally { lock.unlock(); }
    }
 }

with the consumer calling get(), when empty or at the end of each loop and the consumer calling put, after adding so many items or time or ...