ArrayBlockingQueue: concurrent put and take

Question

Why ABQ has not been implemented using the way LinkedBlockingQueue. We can use AtomicInteger to keep Track count in ABQ also the same way LBQ does. We can use the Two Locks for ABQ too. I stumble upon the similar question on SO. ArrayBlockingQueue uses a single lock for insertion and removal but LinkedBlockingQueue uses 2 separate locks

But I couldn't understand the answer for that question. I need help in understanding that problem which would arise if we implement ABQ using two locks. If would be very nice if somebody can give example of a race condition where it might fail. This question can be marked as a duplicate, but am really looking for a more descriptive answer. That would be a great help.

I have pasted a code here http://pastebin.com/ZD1uFy7S . can anyone show whether there could be a possible race condition in the code pasted.

Megasporophyll

This question almost certainly is too broad for StackOverflow. You are asking about the design of an algorithm. StackOverflow is supposed to be for specific programming problems: E.g., "I tried this ...example code... and it did X when I expected it to do Y. What gives?" – Tashinatashkent

with two locks u can have a better throughput like in case of LinkedBlockingQueue .. producers need not to contend with consumers – Megasporophyll

@user3580294, not true! LinkedBlockingQueue doesn't use two locks because one is insufficient: One lock can provide sufficient safety, but two can (in that algorithm) provide the same level of safety with a better level of performance. – Tashinatashkent

Two locks can not provide sufficient safety in the Array implementation because the relationship between the head and the tail of the queue is more tightly coupled than in the linked queue. – Tashinatashkent

@jameslarge am not actually asking for the whole algorithm, but merely a good reason why it don't use the same strategy as LBQ – Megasporophyll

@jameslarge what can go wrong, i cannot see the problem, Its tightly coupled but can be taken care very easily with just AtomicInteger count – Megasporophyll

@jameslarge I didn't think that's what I said? I thought I said that if one lock is sufficient adding more shouldn't all of a sudden cause issues (if done correctly, I suppose, which might be by ABQ doesn't use two locks)... Don't think I suggested that two locks were necessary... – Harlin

@user3580294 not generally the two locks here are more fine grain control i.e one for producer and for consumers helps producer not getting blocked by consumer and hence high throughput see the implementation of LBQ – Megasporophyll

@Megasporophyll You're not getting what I'm saying. I didn't mention throughput at all. I'm just saying that if one lock is fine for safety, adding more locks shouldn't make safety impossible for a proper algorithm. – Harlin

Answer 1

I researched a little bit. I came to the conclusion that yes ABQ can be implemented the same way as LBQ. I have pasted a code in paste bin to show that http://pastebin.com/ZD1uFy7S. The main reason for not implementing that way was because code was getting two complex especially because to support iterator and the performance benefits wasn't significant to go for more complex implementation.

Megasporophyll

One problem is that your code adds an atomic increment (which in practice is a CAS-loop) to both the put() and take() paths. For uncontended scenarios this is going to be slower than the simpler single lock approach, and uncontended scenarios are important. For contended scenarios which would be faster would depend on the exact details of your use. – Euthenics

Many implementations along this line avoid the count variable entirely, but this poses another safety issue. – Euthenics

Answer 2

ArrayBlockingQueue, by definition, blocks waiting for space to become available when a put() occurs and its fixed array is full.

The space that becomes available is the element returned from a take(). In other words, elements within the fixed array are getting reused over time. The put() must write its item to a specific location in the array.

The LinkedBlockingQueue, on the other hand, is a linked list. For this discussion, let's say you've created one that's bounded, just to make it more similar to the ArrayBlockingQueue. Attempt the same thing:

put() an element when the LinkedBlockingQueue is full. It will wait for an element to become available.

But in this case, when you perform a take() - it is just going to return the head value and nuke that item. The put() then sees that the LinkedBlockingQueue is below capacity. It links its item to the tail of the list. There's no overwriting of memory like the ArrayBlockingQueue, which must remain contiguous.

Edit: this is sort of a hypothetical exercise since the code isn't written this way. But anyhow, more details here, in particular the insert and extract methods: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/concurrent/ArrayBlockingQueue.java

The potential problem IF 2 locks were used, AND the existing code stayed more or less the same:

ArrayBlockingQueue is full

Thread 1: calls take(), gets lock A, does its thing, decrements count to [capacity-1] -- but isn't done quite yet

Thread 2: calls put(), gets lock B while T1 is still running, increments count to [capacity], releases lock B

Thread 1: signals notFull()

Thread 3: put() starts execution, even though the array really is full, overwrites an element, since ArrayBlockingQueue uses a circular increment.

This situation can't happen in a LinkedBlockingQueue.

Neurasthenia

that what i am trying to say when the queue is full, atomicCount == capacity i.e all producers wait till one of consumer decrements the count. for this i dont' think i need to hold consumer for every put. Also i think may be what u r saying makes sense but something is still missing i can't get it .. may be little code snippet with a possible race condition will help – Megasporophyll

May be i couldn't understand fully, b utrace condition you exhibited could be very simple avoided with while loop checking the condition for queue full. I have pasted a code in paste bin to show what i am asking pastebin.com/ZD1uFy7S. The race condition you explained will not happen in the above code pasted. – Megasporophyll

I haven't stepped through the pastebin code in a real usage yet but the problem I see is the same one: the count increment/decrement (even with AtomicInteger) is a separate call from the notFull / notEmpty.signal(). If put() and take() use different locks, it's possible put() could increment count, then take could decrement it and signal before put signals. Or vice-versa. Not sure how I can explain it more clearly. – Neurasthenia

@jthalborn if you're going to discount the scenario you should explain why. – Neurasthenia

@Neurasthenia no you see there is a while loop while await, so it will always look at the correct count. If this would not be the case even LBQ will fail in the sense not overriding the elements but queue will exceeds its size – Megasporophyll

@Megasporophyll I agree now: since your code is calling lock() and not lockInterruptibly() in signalNotFull / signalNotEmpty, it should be safe. Not sure if there's much benefit to the extra complexity though. I suspect if you perf test both options under a decent load, you might be able to answer your original question (i.e. your take and put methods each use both of the locks). – Neurasthenia