Java Multi-Threading APIs (Reentrant locks)

There are many ways to achieve Thread synchronization, and one of the traditional ways is using synchronized keyword. While it provides basic synchronization, but it is not much flexible.
One instance is if there are multiple Threads waiting for a lock, and once the lock is free, any of these threads can take up the lock, leading the other threads to starve.
Re-entrant Lock was introduced to provide better flexibility. E.g. to deal with the starvation problem, it has a concept of fairness, by which once the lock is released, it will go to the thread who has been waiting for the longest.
As the name suggests Re-entrant Lock allows a thread to acquire a lock more than once, and the (hold)count will increase by one every time. lock is deemed released if the count reaches 0.
Unlike to the traditional way, its usage is quite simpler, we need to acquire the lock, then work on the shared resource, and then unlock/release the lock.

Now we will dig inside how the synchronization between Threads works without using the traditional Synchronize and wait/notify methods.

Internal Working of Re-entrant Lock

Since Re-entrant Lock works on mutual exclusive principle i.e. only One thread will be allowed to have a particular lock at one time, we use EXCLUSIVE lock here. There is another type of lock called SHARED Lock which is used where multiple Threads can acquire a same lock, used in Semaphores, etc.

Say Thread T1 wants a Lock. The workflow of lock acquire will be:

Line 1: state variable is used to check if lock is free or not. 0 means its free, else means the lock has been acquired that many times by same Thread
Line 4: Check if lock is free.
CompareAndSetState means it will check if State Variable == 0 , if it is then set it to 1. i.e. If lock is free i.e. State==0, means the Thread can acquire the lock, so set state=1.
Line 5: Save this Thread, which will be required if subsequent requests of lock() comes. By saving the thread we will know if future requests of lock() is from same thread, or if some other thread wants it.
line 7: If State != 0 i.e. lock is not free, then we will try getting the lock by putting this thread in a FIFO Queue, and keeping it Blocked until lock gets free. Parameter=1 in acquire(1) means we want 1 lock on it. Useful as Semaphores might want more locks/permits in a single call. Will discuss Semaphores in another story.

Note that here variables like state are integer values, on which we perform Atomic Operations using UNSAFE. Atomicity is very crucial in a multi threaded environment.

Please note that the snippet shared above is for nonFair lock acquire. Here if the lock is present(state>0), then the lock is given to that thread immediately.
For the fair case we directly call acquire() and omit the top if condition check.
I.e. in case of Fair Lock the lock is only allowed if its the first in the Queue of Threads waiting to get the lock. Acquire method is discussed later in the blog.
Fair vs NonFair is discussed below.

If a Thread was unable to acquire a lock(as it was not free), then it will follow one of the 2 roads to acquire it:
Fair and NonFair.
1. Fair means the Thread who waited the longest will get the lock first. This is by giving the lock only to Thread at the first in the QUEUE.
2. NonFair means it will just give the lock to any one in waiting to get the lock.

These are 2 ways to acquire locks,
In general the algorithm in both the ways are same:
1. If Lock is free, give it.
Line 3,4 and 22,23: Check if state==0 ( means lock is free), then:
Line 5 and 25: Set state=1, and
Line 6 and 26: save this Thread who acquired the lock(for future references).
2. If the thread who wants the lock is same as the one who already has the lock(here we use the Thread we had saved before), then increment state meaning same thread acquired lock multiple times.
Line 11–15 and 31–35 takes care of it.
3. Else return false, meaning the lock is not free.

The Difference in 2 methods in only in line 5 and line 24. In Fair case, we have additional check to grant the Lock only if it has no Queued Predecessors meaning if it has no Thread lying in front of it in the Queue, meaning its the top of the Queue.

Now lets look how is this method used, and how is Thread added to the queue, and what happens once its added there.

Every subsequent request to lock will do this.
It first tries to acquire the lock if its available, or else add it to the Queue.
AddWaiter adds the current thread who wants the lock, at the last of the queue.
acquireQueued tries indefinately(until interrupted offcourse) to see if the head of the Queue can acquire the lock(if lock is free).

AddWaiter adds the current Node(i.e. current Thread who wants lock) at the tail of the Queue.
If Tail is initialized(Line5) then current node has its prev set as tail(Line6) and tail is updated with this Node(7). If the queue is not initialized, enq is called.

If Tail is not initialized, initializes tail(Line4–6), and then does the same Operation(add Node at tail.next, and change tail to point to this Node).

After adding the Thread to the Queue, it will try indefinitely to see if it can acquire the lock.

Release the Lock:

Releasing the lock is comparatively easy:

Line 2: Checks the locks count acquired yet, and reduce it by number of locks we want to release(=1 always for Re-entrant locks).
Line 3: Ensure the lock is held by the same thread who wants to release it.
Line 6–8: If the lock hold count=0 now, means lock is free, then set that no thread is holding the lock now(set it null).

Parking and unParking and waitStatus:

Lets look at the Acquire Method, which tries indefinitely to get the lock, and block the thread if it cant get the lock(to save the CPU cycles of not trying for this thread to participate in the lock getting competition).

Line 6–12: We find if its the first Node after the head, and if we can get the lock(using tryAcquire). If we can get the lock, then head will now point to our Node(who has not got the lock), and earlier Node is removed from Queue(by p.next=null), so that it has no reference to anything in Queue now.

Line 13–15: Its where the parking and waitstatus thing comes in place. We first check if there is any Node who might get lock before us, then we will park this Node. Waitstatus is mainly present to save us from unnecessary park/unpark operations as those are costly ones.

Important point to note is that at Line14: where we park the thread, it means thread wont execute anything after that, until its unparked. So it will be suspended after its parked. Once its unparked(once the lock is release for instance), it will carry on with its infinite loop and try acquiring lock next time.

The Thread is parked(i.e. blocked) and unparked(put into competition of getting lock).
So say a Thread wants to get a lock, and lock is not free, so in that case it makes sense to park(remove it temp from competition) it. So idea here is that whenever a Thread wants a lock, it tried to get it(based on holdCount). If it is unable to get a lock, then its Parked temporarily.
Caveat here it, what if the lock gets free sooner, then there lies an overhead of unparking it immediately. So to avoid this, we always keep the next likely thread to get the look unparked and mark it with a waitStatus. We put a wait status on its previous Node in the Queue. It means if the previous Node is not yet parked, then lets mark the previous Node with something, and park this Thread. And if say previous one is parked, then we can anyways park this Thread(as it will be server only after the Previous one).
Marking this with something is called SIGNAL.
So algorithm goes like:
If prev one is marked as SIGNAL, then it means prev One is not yet parked, so we can park our current Thread(as prev will get the lock if it gets free before us).
If prev one is not yet marked SIGNAL, then we can mark the Prev one as SIGNAL, and park me by retrying for lock once more(who knows if in next try the prev is cancelled and we might get the lock, saving us from PARK and UNPARK operation).
Same thing happens for every Thread(each is under an infinite Loop), so if Prev is marked SIGNAL, then same may happen with prev also, i.e. prev.prev will get marked SIGNAL and prev will be parked, and so on, until there is only one left who is marked SIGNAL, and all its successors are PARKED.

Line 3–8: We check if Previous one is already SIGNAL, means it will get the lock if lock gets free first, so we return true i.e. park myself.
Line 9–17: We check if prev one is cancelled(waitstatus>1 means Cancel), in that case we keep on going to prev one by one, until we find a Thread which is not cancelled, and follow same thing from it. (infinite Loop in acquireQueued method takes care of calling this again).
Line 18–24: If prev one is neither Cancelled nor marked Signal, We can mark the previous one as Signal, and can retry once more and next time we can park ourselves(line 3–8 in next run will handle this).

Similarly reverse thing happens with the unparking:
We need to unpark the successor Threads when a release happens:

tryRelease is already discussed before(it will check if current Thread has the lock, and if yes it will reduce the holdCount). Additionally, we also need to handle the unparking operation(to bring back blocked threads in competition). Since the unparking should start from the head of the queue, we see waitStatus on Head. If head has waitStatus = 0, meaning head does not has the SIGNAL set, that means there is no other Thread to awake, so no need to bother.
But if that’s not the case, we will unpark its successor. We iterate its successors and find first nonCancelled unparked child. We check if its unparked if waitStatus is either SIGNAL(meaning all its children are parked), or 0(means it will be marked SIGNAL in next run). We need not unpark the Cancelled Threads(as they were never parked at the first place), so we skip over them too(here we iterate backwards from tail).

Line 7–9: Checks if the current Node is SIGNAL, then we remove its SIGNAL.
Line 17–23: We find a closest Node with waitStatus ≤ 0 to unpark it, iterating backwards from tail.
Line 25: We unPark the next successor.

Please note that the waitStatus is just present to enhance the performance, so as to avoid parking/unparking operations on the next thread who would be getting the Lock.

Lock Code:

Unlock Code:

Conclusion:

In a nutshell, Re-entrant Locks provides a paradigm to manage the access to shared common resource without worrying about Synchronized/wait/notify etc. It will see if lock hold count = 0, then it will grant the lock to the Thread asking for it, else it will place this Thread into a Queue. Once the lock is released, the hold count is reduced, and the process continues to serve the lock to the next Thread in the Queue.
To Lock: We see if any lock is free, else we add it to Queue, and mark first successor node from Head as SIGNAL(who will get the lock first), and park all others.
To Unlock: We reset lock count, and unpark the successor of the head node.