I was going through the source code of ArrayBlockingQueue and LinkedBlockingQueue. LinkedBlockingQueue has a putLock and a takeLock for insertion and removal respectively but ArrayBlockingQueue uses only 1 lock. I believe LinkedBlockingQueue was implemented based on the design described in Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. In this paper, they mention that they keep a dummy node so that enqueuers never have to access head and dequeuers never have to access tail which avoids deadlock scenarios. I was wondering why ArrayBlockingQueue doesn't borrow the same idea and use 2 locks instead.
Asked
Active
Viewed 4,865 times
11
-
a more detailed answer related to this same question can be found here [link](https://stackoverflow.com/questions/18490636/condition-give-the-effect-of-having-multiple-wait-sets-per-object) – amarnath harish Aug 15 '18 at 17:07
4 Answers
12
ArrayBlockingQueue has to avoid overwriting entries so that it needs to know where the start and the end is. A LinkedBlockQueue doesn't need to know this as it lets the GC worry about cleaning up Nodes in the queue.
Peter Lawrey
- 525,659
- 79
- 751
- 1,130
-
Thanks for pointing me in the right direction. I went through the code again and found that both ArrayBlockingQueue and LinkedBlockingQueue maintain variable "count". This is AtomicInteger in LinkedBlockingQueue (incremented and decremented accordingly in put and remove) and an int in ArrayBlockingQueue. And I guess it can't be an AtomicInteger in ArrayBlockingQueue because it has to wrap around. – user1168577 Jun 13 '12 at 15:56
-
@Peter it would be really greatfull if you can explain why Two Lock Queue Algorithm would not work. count can very well be AtomicInteger in case of ABQ , and overriding can be very well be avoided by checnking count == max_capacity. – veritas Jul 02 '14 at 20:19
-
1@veritas Can you explain where I mention the Two Lock Queue Algorithm? I wrote this two years ago and I can't find what you are talking about. – Peter Lawrey Jul 02 '14 at 20:24
-
2Two Lock Queue algo is being used by LBQ Implementation. LBQ take and put can work concurrently, but this is not the case with ABQ.So wondering why? This was the original Question Also. But couldn't understand the answer – veritas Jul 02 '14 at 20:49
-
@PeterLawrey i have pasted a small implementation of ABQ using LBQ approach . can you point out the race condition http://pastebin.com/ZD1uFy7S. thanks – veritas Jul 03 '14 at 03:03
12
I was wondering why ArrayBlockingQueue doesn't borrow the same idea and use 2 locks instead.
Because the ArrayBlockingQueue uses a much simpler data structure to hold the queue items.
The ArrayBlockingQueue stores its data in one private final E[] items; array. For multiple threads to deal with this same storage space, either if adding or dequeuing, they have to use the same lock. This is not only because of memory barrier but because of mutex protection since they are modifying the same array.
LinkedBlockingQueue on the other hand is a linked list of queue elements that is completely different and allows for the ability to have a dual lock. It is the internal storage of the elements in the queue that enabled the different lock configurations.
Gray
- 115,027
- 24
- 293
- 354
1
2 locks are used in LBQ to restrict access to head and lock concurrently. The head lock disallows two elements from being removed concurrently and tail lock disallows two elements from being concurrently added to the queue. the two lock together prevent races.
sumit singhal
- 11
- 1
0
I think its possible for ABQ to borrow the same idea as LBQ. Please refer to my code http://pastebin.com/ZD1uFy7S and a similar question i asked on SO ArrayBlockingQueue: concurrent put and take.
The reason why they didn't used it, is mainly because of the complexity in implementation especially iterators and trade off between complexity and performance gain was not that lucrative.
For more reference please have a look at http://jsr166-concurrency.10961.n7.nabble.com/ArrayBlockingQueue-concurrent-put-and-take-tc1306.html .
