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.

Answer 1

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.

Answer 2

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.