While reading source code of ArrayBlockingQueue implementation, I found this rather intriguing snippet of code.
What!? That’s it? Either
false for a lock decides fairness of all blocking queue operations?
Let’s find out what makes a ReentrantLock so special. It’s source code can be found here.
Table of contents
- ReentrantLock & AQS
ReentrantLock & AQS
It turns out ReentrantLock creates 2 helper classes extending
AbstractQueuedSynchronizer, and delegates all locking operations including the fairness.
Also, the class
AQS seems to be used by most locks in Java.
Let us try to understand the code. This code walk through is not sequential nor atomic (per method). In each subsequent step, we will add one feature or address a problem.
Locking means exclusive access. Integer variable called
state is used to maintain this access. Value of 0 means the state is unlocked, while value of 1 or more means state is locked by 1 or more threads. Using integer variable is better because it allows use of single-instruction compare-and-swap operations.
Algorithm for concurrent access
For locking operation, if lock is already being used, the basic algorithm is to enqueue the thread and block. Similarly for unlock operation, release the lock (reset the state) and unblock first queued thread.
Add to the FIFO queue
tryAcquire fails, then add the thread to the queue and block it until
the lock is released and it is at head of the queue (all earlier threads are removed from the queue).
Note that the actual queue used a variation on the standard queue we know. Lets not go into details of it now. If interested, you can read about it here.
You may have noticed
Node.EXCLUSIVE in the code snippet above.
This is easy to understand if we understand its sibling
Shared node is used for read locks where multiple threads can simultaneously have access to the lock.
In most cases we use
Node.EXCLUSIVE, especially in our context of
ReentrantLock where-in we need exclusive access by a single thread.
Now that we understand how queues are used, lets look at what is
Lets revisit the snippet of code.
Suppose the state was just unlocked, and there are few threads waiting in the queue.
But, suddenly a new thread tries to acquire the lock, and it does not check the waiting-thread-queue. It acquires the lock, unfairly ahead of all waiting threads i.e.
Unfair acquire is almost same, except, it again tries to barge in without checking the wait-thread-queue.
Now that the thread owns a lock, unlocking/releasing it is simple. Reset the state and remove thread as lock owner.
When thread is reentrant
When the thread has acquired the lock multiple times (i.e. Reentrant), we reduce the state value by 1 each time the thread calls unlock/release. This is because thread is expected to call unlock same number of times as lock. Thus, in this case, the state cannot be set to 0, and ownership is still retained by the thread.
What about queued threads
If there are threads waiting to acquire the lock, we need to
unpark the thread at head of the queue (thread that has waited the longest).
Note: The actual code unparks node’s successor instead of node itself. This is because, during acquire, immediately after adding node to the queue, it tries again to acquire the lock for the head node. We skipped that part to retain simplicity. You can checkout the acquire and unpark code for more details.
I was putting off going through this code for a long time. It turned out to be a wonderful ride.
We skipped some important parts of the code like
Condition object, doAcquireInterruptibly, Cancelled status and lot more. But hopefully, now that we understand the basics, it will be easier to unpack.
Hats off to the original author of the code, Doug Lea. It is relatively easy to understand (considering its complex functionality) and the documentation for these classes is the most comprehensive and informative I’ve ever encountered.
Hit me up in the comments for any queries or corrections.