Abstract Queued Synchronizer Class
It provides a framework for implementing blocking locks and related synchronizers like semaphores, CountDownLatch etc. The basic algorithm for acquire is try acquire, if successful return else enqueue thread if it is not already queued and block the current thread. Similarly basic algorithm for release is try release, if successful, unblock the first thread in the queue else simply return. The threads will wait in a first-in-first-out (FIFO) wait queues. The abstract methods tryAcquire() and tryRelease() will be implemented by subclasses based on their need.
Acquire in exclusive mode
In the above diagram ‘shouldParkAfterFailedAcquire?’ verifies whether the predecessor’s wait status is SIGNAL. If yes, it knows for sure that the predecessor thread will SIGNAL on its release so it will immediately block else it may retry to acquire the lock in case it is the first node in queue.
If a thread fails to acquire the lock, it will be put in a queue. If the queue doesn’t exist yet, it will initialize it using a dummy header and then link itself to it. The ‘next’ of the head and ‘prev’ of the node will be linked. The new node also becomes the tail. The wait status of the header node will be set to SIGNAL so that as the owner thread releases the lock, it can signal the head node’s successor to acquire the lock. One more time the thread will try to acquire the lock to make sure it cannot acquire before it actually parks.
Thus the thread which failed to acquire the lock can be safely parked as long as its predecessor node’s waiting status is set to SIGNAL so it can retry to acquire the lock once the predecessor is released.
If the predecessor was cancelled, it will skip over all the canceled predecessors to reset its next and prev pointers to a waiting thread.
The sub classes will implement ‘try Release’ based on their requirement. Once released, the header node’s successor node needs to be signaled so that it can re-try to acquire. If there is no head, it means there are are no threads in queue so there is no one to be signaled. If the head exists, it makes sure wait status is not zero. If it is zero, it means the successor node need not be signaled.
Unpark successor node’s thread
Thread to unpark is held in successor, which is normally just the next node.
Case 1: If head’s waiting status < 0, clear the waiting status. If the successor node (P1) is not in canceled state, unpark the successor node’s thread so that it can retry to acquire.
Once the unparked thread to acquire, its node becomes the new head. The old head will be delinked. If it fails to acquire, it will be re-parked. The head node’s wait status which was set to 0 will be reset to SIGNAL.
This is similar to exclusive release. It also ensures that a release propagates.
Acquire in shared mode
This is similar to exclusive acquire. It also propagates the release to other waiting threads in queue which are waiting to acquire the shared lock. Once a lock is released, it unparks its successor node which in turn propagates release to its next node.
There may be a runtime exception while trying to acquire in which case the node in context will be canceled. If a node is canceled we must make sure that its successor node is properly linked to a valid predecessor node so the links may have to be adjusted. If its predecessor nodes are already in a canceled state, those nodes will be skipped to arrive to a proper predecessor node which has wait status <= 0.
If the node to be canceled is tail node itself, it will simply be removed. Its predecessor node will become the new tail. The ‘next’ link of the new tail will point to null.
If the wait status is < 0, it means the successor needs signal, try to set predecessor’s next-link so it will get one. If the predecessor is the head node itself then it will wake up its successor node.