In this article we discuss about the mechanics of non-fair and fair Reentrant lock. We discuss about thread parking and unparking, the data structure used internally and how it changes as we lock and unlock.
First time a thread wants to acquire the lock, it acquires it without any wait as the lock is not owned by any thread yet. Thread acquires and owns it.
Lock below is called the ReentrantLock, which is either open to be acquired or locked and is determined by its state which is either zero or non-zero. It knows the owning thread.
What is Reentrance Mutext?
When a thread acquires a previously unheld lock, the JVM records the owner thread and sets the acquisition count to one. If that same thread acquires the lock again, the count is incremented, and when the owning thread calls unlock, the count is decremented. When the count reaches zero, the lock is released.
Reentrancy means that locks are acquired on a per-thread rather than per-invocation basis. In other words, if a thread is not reentrant, and tries to acquire a lock that it already holds, the request won’t succeed.
A re-entrant lock can follow either fair or non-fair policy, by default it is non-fair. In this article we will discuss both non-fair and fair locks. Below is the class diagram.
If the lock to acquire is currently owned by some other thread then the current thread trying to acquire the lock will be parked, that is, disabled for thread scheduling purposes unless the permit is available. If the permit is available then it is consumed and the call returns immediately, otherwise it remains blocked. The blocker (the lock) which is responsible for this thread parking will be set to the thread.
If the lock is already owned by a thread, any other thread trying to acquire the lock will put on a hold and will be waiting in a queue. The thread would be disabled for thread scheduling purpose. The queue here is a double linked list. The lock will know the owning thread, state (0 or 1), head and tail of the linked list. If the node’ successor node is waiting for the lock then its wait state property (-1) will reflect that.
The thread fails to acquire the lock fails as the lock is already acquired by another thread. The thread is added to a double linked list queue where the header is a dummy node with a mode indicating that it is waiting for a signal and the current thread which failed to acquire the lock becomes the tail node and is the next node to header. Since the current thread fails to get the lock, it is parked as it remains blocked till some other thread unblocks it.
Second thread tries to acquire the lock, it too fails so gets queued. It becomes the new tail and the thread is parked.
If the current thread is the holder of this lock then the hold count is decremented. If the hold count is now zero then the lock is released. If the current thread is not the holder of this lock then llegalMonitorStateException is thrown.
Once the lock is released, the lock finds out the node which is in waiting status, removed the waiting status and wakes up the node’s successor so that the node woken up can acquire the lock.
The thread to unpark is held in successor, which is normally just the next node. But if cancelled or apparently null, traverse backwards from tail to find the actual non-cancelled successor.
If the node woken up is immediate successor to the head node, it tries to acquire the lock and become the new head. The old head and the variables referring to it are nullified so the gc can claim the memory.
If the owning thread releases the lock, the head’s successor node’s thread will be unparked. The successor node is tail in this case, so we will end up with a single node which is itself head and tail both. The unparked thread will take the ownership of the lock.
Further release of the lock will simply nullify the owning thread and the state of the lock will be set to 0.
The ReentrantLock constructor offers a choice of two fairness options: a nonfair lock (the default) or a fair lock. When a thread fails to acquire the lock, it is put on a queue. When the owning thread releases the lock, the first thread waiting in the queue is allowed to try acquiring the lock. In case of a fair lock, threads always acquire lock in the order in which they requested it, whereas a non-fair lock permits barging. In other words, if a thread requesting a lock appears at right time when the lock happens to be available, it can jump ahead of the queue of waiting threads. This is because there can be a significant delay between when a suspended thread is resumed and when it actually runs. During this time a new thread can barge in and acquire the lock. Below example shows a non-fair lock scenario.
- Thread A acquires the lock
- Thread B tries to acquire the lock. It fails as thread A already holds the lock.
- Since the lock is not available, thread B is put on a queue.
- Thread A releases the lock.
- Thread A unparks Thread B so that it can try acquire the lock.
- Thread C tries to acquire the lock.
- Since it is still free and is not yet acquired by thread B, thread C manages to acquire it.
- By the time thread B shows up to acquire the lock, thread C is done with its work and releases the lock.
- Thread B acquires the lock
Thus with a non-fair lock throughput can be better.
At step 6, unlike non-fair lock, fair lock doesn’t allow the thread C to acquire the lock and instead puts it on queue. Thread B which is the first thread in waiting acquires the lock.
An unparked thread will try again to acquire the lock, in case of any run time exception while trying to acquire the lock, the thread’s node in the queue will be canceled. Its associated thread is made null. If the predecessor’s node wait status is of SIGNAL mode, it’s next link should point now to the successor node of the canceled node. If the predecessor node is already canceled we need to skip that and any other cancelled predecessors. If the node canceled is the tail node then it is removed and its new predecessor becomes the tail node.
In below scenario, the canceled node’s predecessor is the head node so its successor node is unparked. If the node’s successor is cancelled or apparently null, traverse backwards from tail to find the actual non-cancelled successor.