0

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.

Community
  • 1
  • 1
veritas
  • 2,444
  • 1
  • 21
  • 30
  • 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?" – Solomon Slow Jul 02 '14 at 22:10
  • with two locks u can have a better throughput like in case of LinkedBlockingQueue .. producers need not to contend with consumers – veritas Jul 02 '14 at 22:12
  • @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. – Solomon Slow Jul 02 '14 at 22:12
  • 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. – Solomon Slow Jul 02 '14 at 22:14
  • @jameslarge am not actually asking for the whole algorithm, but merely a good reason why it don't use the same strategy as LBQ – veritas Jul 02 '14 at 22:14
  • @jameslarge what can go wrong, i cannot see the problem, Its tightly coupled but can be taken care very easily with just AtomicInteger count – veritas Jul 02 '14 at 22:16
  • @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... – awksp Jul 02 '14 at 22:21
  • @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 – veritas Jul 02 '14 at 22:24
  • @veritas 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. – awksp Jul 02 '14 at 22:25

2 Answers2

3

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.

spudone
  • 1,267
  • 7
  • 10
  • 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 – veritas Jul 02 '14 at 22:32
  • 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 http://pastebin.com/ZD1uFy7S. The race condition you explained will not happen in the above code pasted. – veritas Jul 03 '14 at 02:59
  • 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. – spudone Jul 03 '14 at 16:26
  • @jthalborn if you're going to discount the scenario you should explain why. – spudone Jul 03 '14 at 16:30
  • @spudone 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 – veritas Jul 03 '14 at 17:23
  • @veritas 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). – spudone Jul 03 '14 at 17:40
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.

veritas
  • 2,444
  • 1
  • 21
  • 30
  • 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. – BeeOnRope Aug 23 '14 at 02:15
  • Many implementations along this line avoid the count variable entirely, but this poses another safety issue. – BeeOnRope Aug 23 '14 at 02:15