ArrayBlockingQueue uses a single lock for insertion and removal but LinkedBlockingQueue uses 2 separate locks

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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 .