Lock-free and size-restricted queue in Java

Question

I'm trying to extend an implementation of a lock-free queue in Java according to this posting.

For my implemenation I am restricted in using only atomic variables/references. The addition is that my queue should have a maximum size. And therefore a putObject() should block when the queue is full and a getObject() if the queue is empty.

At the moment I don't know how to solve this without using locks.

When using an AtomicInteger for example, the modifying operations would be atomic. But there is still the problem that I must handle a check-and-modify-situation in putObject() and getObject() right? So the situation still exists that an enqueuing thread will be interrupted after checking the current queue size.

My question at the moment is if this problem is solvable at all with my current restrictions?

Greets

Answer 1

If you have a viable, correctly working lock-free queue, adding a maximum size can be as easy as just adding an AtomicInteger, and doing checks, inc, dec at the right time.

When adding an element, you basically pre-reserve the place in the queue. Something like:

while (true) {
    int curr = count.get();
    if (curr < MAX) {
        if (count.compareAndSet(curr, curr + 1)) {
            break;
        }
    }
    else {
        return FULL;
    }
}

Then you add the new element and link it in. When getting, you can just access the head as usual and check if there is anything at all to return from the queue. If yes, you return it and then decrease the counter. If not, you just return EMPTY. Notice that I'm not using the counter to check if the queue is really empty, since the counter could be 1, while there is nothing linked into the queue yet, because of the pre-reserve approach. So I just trust your queue has a way to tell you "I have something in me" or not (it must, or get() would never work).

Answer 2

It is a very common problem which is usually solved by using a Ring Buffer. This is what network adapters use as does the Disruptor library. I suggest you have a look at Disruptor and a good example of what you can do with ring buffers.