Jan 9, 2015

Lock unlocked : Decode the Lock class, Inside the Lock class

"Lock implementations provide more extensive locking operations than can be obtained using synchronized methods and statements. They allow more flexible structuring, may have quite different properties, and may support multiple associated Condition objects"
- docs.oracle.com

We were good with synchronized keyword, but many were still writing their own Lock class, unless Java came with Lock interface. What was reason why some were writing Lock class, or why we now use Lock class from Java is not an compelling question now, but there is no harm in revisiting the interesting concepts, especially when they are part of our daily programming life. 

Some of the abstracts of Concurrency are not so common but they might be driving forces behind the Lock class - 
Missed Signals: A notify signal is send before the wait, then thread waiting will wait forever. That means along with wait/notify, we need a boolean variable which can be referred. 
Spurious Wakeups: True or not, but a thread might wake up, even if notify or notifyAll is not called. So always a boolean should also be checked, and that too in "while" loop, "if" will check only once. 
Thread Starvation: The thread never gets the lock. This is possible if lock is always granted to high priority thread. When we use synchronized block, we don't care about about starvation, but this is where starvation is perfectly possible. A thread can be blocked indefinitely to enter synchronized block, because others are constantly allowed access over it.  But if we implement our own Lock class, we can check and control that a thread is never starved. 
Nested Monitor Lockout: Like deadlock, but not exactly. Threads take the locks in same order, but problems comes in a situation like - Thread 1 is holding a lock A, and waits for a signal from Thread 2. Thread 2 needs the lock A to send the signal to Thread 1.
Thread 1 locks A and B, then releases B and waits for a signal from Thread 2. Thread 2 needs both A and B to send Thread 1 the signal. So, one thread is waiting for a signal, and another for a lock to be released.
Slipped Condition: Slipped conditions means, that from the time a thread has checked a certain condition until it acts upon it, the condition has been changed by another thread so that it is erroneous for the first thread to act. Its like, Thread checks if already locked, then waits otherwise sets isLocked to true. If code for checking and setting is in two different blocks, then it is possible that two threads come at same time, 1 & 2, they both see isLocked is false, and both try to set isLocked to true in below code - 

For more details, I will suggest you visit - http://tutorials.jenkov.com/. This is the place which has best tutorials. And this post is inspired by the knowledge shared on the site. 

Considering above and other known matters, below is a very simple Lock class - 

On his blog, Jenkov also provides an implementation of Lock class, which takes care of Nested Monitor Lockout, Slipped Conditions, and Missed Signals. 
Below is the explanation provided by jenkov - 
"every thread callinglock() is now queued, and only the first thread in the queue is allowed to lock the FairLock instance, if it is unlocked. All other threads are parked waiting until they reach the top of the queue."
"FairLock creates a new instance of QueueObject and enqueue it for each thread calling lock(). The thread callingunlock() will take the top QueueObject in the queue and call doNotify() on it, to awaken the thread waiting on that object. This way only one waiting thread is awakened at a time, rather than all waiting threads. This part is what governs the fairness of the FairLock."
"Notice how the state of the lock is still tested and set within the same synchronized block to avoid slipped conditions."
"Also notice that the QueueObject is really a semaphore. The doWait() and doNotify() methods store the signal internally in the QueueObject. This is done to avoid missed signals caused by a thread being preempted just before calling queueObject.doWait(), by another thread which calls unlock() and thereby queueObject.doNotify(). ThequeueObject.doWait() call is placed outside the synchronized(this) block to avoid nested monitor lockout, so another thread can actually call unlock() when no thread is executing inside the synchronized(this) block in lock() method"
"Finally, notice how the queueObject.doWait() is called inside a try - catch block. In case an InterruptedException is thrown the thread leaves the lock() method, and we need to dequeue it."

Lets unlock the FairLock code - 
For first thread this will result false, since waitingThreads.get(0) = queueObject, so
since isLocked is false and also waitingThreads.get(0) != queueObject is also false, thus isLockedForThisThread will be false
otherwise if thread is not first queue the isLockedForThisThread will result true, since waitingThreads.get(0) != queueObject
also if thread is second the and FairLock is already locked by first thread, then
isLocked will be true and waitingThreads.get(0) != queueObject will be false, result isLockedForThisThread will be true. 

As you might have noted above was a very fair Lock implemented by Jenkov, and it treats all threads are equal. 

Above we discussed the custom Lock class created by Jenkov. 

But with JDK 5, java contains few Lock implementations, so we don't need to implement our own Lock. 
"ReentrantLock" comes in JDK and as mentioned - 
"A reentrant mutual exclusion Lock with the same basic behavior and semantics as the implicit monitor lock accessed using synchronized methods and statements, but with extended capabilities." (from docs.oracle.com)
The ReentrantLock comes option lock fairness. And below lines give details of that and also more details on fairness - 
"The constructor for this class accepts an optional fairness parameter. When set true, under contention, locks favor granting access to the longest-waiting thread. Otherwise this lock does not guarantee any particular access order. Programs using fair locks accessed by many threads may display lower overall throughput (i.e., are slower; often much slower) than those using the default setting, but have smaller variances in times to obtain locks and guarantee lack of starvation. Note however, that fairness of locks does not guarantee fairness of thread scheduling. Thus, one of many threads using a fair lock may obtain it multiple times in succession while other active threads are not progressing and not currently holding the lock. Also note that the untimed tryLock method does not honor the fairness setting. It will succeed if the lock is available even if other threads are waiting." (from docs.oracle.com)
lock() is the method called by threads to obtain lock. 
If a thread calls lock() will return with either
1. successfully acquiring lock, if no other threads hold lock. 
2. immediately is lock is held by itself holds the lock
3. blocked and thread lies dormant until lock has been acquired
It is recommended to for lock() method with a try-catch-finally, and releasing the lock(unlock()) in finally block.

The ReentrantLock class implementation in Java is far more complicated that what we discussed till now. But we can simply it understand. 
Below is the layout of the class -
Looking above it seems Sync is something behind the scenes a role player, but looking at below code you will know its the major role player. Because ReentrantLock class delegates its every operation to Sync class. 

We go two Sync classes, so delegation will happen to either one of them: NonFairSync or FiarSync. Both classes extend Sync class. Sync class in itself extends AbstractQueuedSynchronizer

Lets look at the inner class Sync code - 
Sync class depends totally on AbstractQueuedSynchronizer's operations: getState(), setState(), getExclusiveOwnerThread(), setExclusiveOwnerThread(), and compareAndSetState().
The operations can be understood by their name, and its clear the Exclusive thread is the thread that holds the lock exclusively (doesn't shares the lock) and State gives hold count (Number of times same lock is held). 
Lets now ignore AbstractQueuedSynchronizer class, and see the painless code of NonfairSync -
acquire(int) is an operation in AbstractQueuedSynchronizer, and below are the details mentioned in oracle docs -
"Acquires in exclusive mode, ignoring interrupts. Implemented by invoking at least once tryAcquire(int), returning on success. Otherwise the thread is queued, possibly repeatedly blocking and unblocking, invoking tryAcquire(int)until success."
Might be you can guess now the code of FairSync, which is similar to NonfairSync
hasQueuedPredecessors() queries whether any threads have been waiting to acquire longer that current thread. 
We are done here with ReentrantLock class, any further understanding or we want to go deep, we will have to delve into AbstractQueuedSynchronizer.
AbstractQueuedSynchronizer is a class extended by Lock classes. Its not just a class but a framework for implementing blocking locks and other synchronizers like semaphore.
The class maintains a FIFO Queues and an atomic int value - state. State field represents state and is manipulated by three methods: getState(), setState(int), and compareAndSetState(int,int).
The class supports lock acquisition in both exclusive and shared mode. Both mode can come into play in the case of ReadWriteLock. Threads waiting in different mode share the same Queue.
The class defines a nested ConditionObject, which is used as Condition by all subclasses (Lock classes). isHeldExclusively is called on ConditionObject and tells if synchronization is held exclusively by current thread, release(int) will release the object and acquire(int) will acquire the object, both methods work along with getState().
The class provides methods to inspect, instrument and monitor the queues and condition objects.
The implementing classes will provide implementation of tryAcquire(int), tryRelease(int), isHeldExclusively(); or tryAcquiredShared(int), tryReleaseShared(int).
The Acquire and Release logic work as below -
Note although it maintains FIFO policy, but FIFO is not guaranteed. A normal non-strict fair implementation of tryAcquire(int) will be like we saw above in ReentrantLock class.

You wait for a lock, once you acquire the lock, you continue, now if some condition is not met, you wait for that condition to signal and release the lock, after receiving the signal you have to again wait for lock to acquire.....so is the life...funny but so it is programmed !!!


1 comment

  1. Your blog is very helpful for readers to boost up their skills. Understanding of Application design is always very important in programming.



© Shift, ShEkUP, Shape, and Surprise | All rights reserved.
Blogger Template Crafted by pipdig