This article is a continuation to our previous article extrinsic locks in java.
Reentrant lock is similar to synchronized block/implicit monitor but it provides extended capabilities. It provides methods for monitoring the state of the lock ,for instance number of threads waiting for the resource(getQueueLength()), to check whether a specific thread is waiting for the lock(hasQueuedThread(Thread thread)).
Reentrant lock is an implementation of java.util.concurrent.locks.Lock interface and it is implemented as an exclusive lock. Reentrant lock internally uses AbstractQueuedSynchronizer (AQS). AQS has CLH(Craig, Landin, and Hagersten) lock queue as a blocking synchronizer. AQS has a volatile instance variable named “state” which is of type integer. If the value of the “state” variable is 0 then the lock object is unacquired else it is acquired.Updation to the “State” should always done via CAS(Compare and Set) in order to maintain it as an atomic operation. Reentrant lock accepts an boolean argument for fairness in its constructor. If the fairness argument is flagged true, then the long waiting thread in the wait queue will acquire the lock.
Whenever a thread invokes on the lock() method of the Reentrant Object (NonFair) anyone of the below mentioned operations will occur.
a.Value of the “State” is checked and if the value is 0 then it will immediately increment it by one.
b. Value of the State variable is greater than 0, then it will check whether the thread holds the lock and the current thread are same. If both the threads are same(in case of Reentrancy), then the hold count of the state variable is incremented by one.
In order to acquire the lock, after updating the “State” variable threads will invoke the setExclusiveOwnerThread() method by passing the current thread as the argument.
Note:
a. Reentracy of thread should not exceed 2147483647(Integer.MAX_VALUE) as it will result in integer overflow. In order to avoid this overflow we can make use of Custom class which implements AbstractQueuedLongSynchronizer and state instance variable is of type “long”.
b. If the fairness attribute is set to true in the Reentrant lock, then the initialTryLock() implementation will have an additional check to ensure that no other Threads are waiting in the AQS lock queue.
If the initialTryLock() fails, then the thread will be moved to CLH lock queue which is present in the AQS.
AQS has two instance variables head and tail reference to the CLH lock queue, head pointer will be always a stub and it is a lazy initialized and tail will always point to the new thread that is enqueued in the wait queue/lock queue.
CLH lock queue stores the data in form of Nodes. Each Node have the below instance variables.
a. Previous and Next Pointer to point the previous and next nodes in the queue respectively.
b. Status to signal the status (Cancelled/Waiting).
c. Waiter. - Reference to the current waiting thread.
Node class is an abstract class and it has two concrete class namely ExclusiveNode and SharedNode. Since Reentrant lock is an exclusive lock, it makes use of the ExclusiveNode.
Let’s look into a use case in which the lock queue/wait queue is empty and initialTryLock() method returned false. Then the below mentioned operations will take place.
a. An Instance of the ExclusiveNode() will be created and the waiter instance of the exclusive node will refer to the Current Thread.
b. Since Head of the wait queue is lazily initialized, an empty instance of ExclusiveNode will be initialized and it will be assigned to head.Tail will also refer to the newly created Exclusive Node. During this process both the head and tail points to the same Exclusive Node.
c. Prev pointer of the newly created current Thread’s Exclusive node will be pointing to null and this signifies that the newly created node is yet to be part of the wait queue and hence the prev pointer will now point to current tail reference (Node is getting enqueued) and the new node will be assigned as tail. End of this process makes sure the prev pointer of the Current Thread’s Node is referring to the head note.
d. If the previous pointer of the current node points to the head then the current node will be considered as the first node and tryAcquire() method will be invoked until the lock is acquired.
If the node is not the first node (i.e) there are many predecessor threads are waiting in the queue, then the WAITING signal of the node will be set and the whole process from (a to d) will be performed (Except initializing head node as it will be required only ones) and if fails again then the thread will be parked(dormant).
Note: There is one possible case, if the predecessor of the current node got cancelled due to thread.interrupt and those node will be cleaned from the queue.
When a thread invokes the unlock() method of the Reentrant lock then the “State” instance variable is decremented by one and it will check whether the value of state is now “0” and if it is then it will set the Owner of the Lock to null by invoking setExclusiveOwnerThread(null) and null as the argument and it signals the next node. Next Node is always head.next node , the status signal of that node will be cleared from WAITING and LockSupport.unpark () method will be invoked to ensure the next waiter to be consider in the thread scheduling process even if it is parked. Thus the wait queue will ensure the fairness of the threads waiting in the queue.
Note:
a) tryLock() method does not upload the fairness of the wait queue, as it will acquire the thread if the value of the state variable is “0" and it won’t consider the threads waiting in the wait queue.
b) AbstractQueuedSynchronizer is a core to not only core to lock implementation but also to other Concurrency classes namely Semaphore and CountDownLatch.In our next article we can focus on the internal working of the CountDownLatch.