Advanced Synchronization in Java Threads, Part 2
Pages: 1, 2, 3, 4
To use this class, replace all instances of
ReentrantLock with
DeadlockDetectingLock. This slows down your
program, but when a deadlock is detected, a
DeadlockDetectedException
is immediately thrown. Because of the performance implications of
this class, we do not recommend using it in a production environment:
use it only to diagnose occurrences of deadlock. The advantage of
using this class is that it detects the deadlock immediately when it
occurs instead of waiting for a symptom of the deadlock to occur and
diagnosing the problem then.
The DeadlockDetectingLock class maintains two lists—a
deadlockLocksRegistry and a
hardwaitingThreads list. Both of these lists are
stored in thread-unsafe lists because external synchronization will
be used to access them. In this case, the external synchronization is
the class lock; all accesses to these lists come from synchronized
static methods. A single deadlockLocksRegistry
list holds all deadlock-detecting locks that have been created. One
hardwaitingThreads list exists for each
deadlock-detecting lock. This list is not static; it holds all the
thread objects that are performing a hard wait on the particular
lock.
The deadlock locks are added and removed from the registry by using
the registerLock() and unregisterLock() methods. Threads are added and removed from
the hard waiting list using the markAsHardwait() and freeIfHardwait()
methods respectively. Since these methods are static—while the
list is not—the list must be passed as one of the parameters to
these methods. In terms of implementation, they are simple; the
objects are added and removed from a list container.
The getAllLocksOwned() and getAllThreadsHardwaiting() methods are used to get the two types of waiting subtrees we mentioned earlier. Using these subtrees, we can
build the complete wait tree that needs to be traversed. The
getAllThreadsHardwaiting() method simply returns
the list of hard waiting threads already maintained by the
deadlock-detecting lock. The list of owned locks is slightly more
difficult. The getAllLocksOwned() method has to
traverse all registered deadlock-detecting locks, looking for locks
that are owned by the target thread. In terms of synchronization,
both of these methods are called from a method that owns the class
lock; as a result, there is no need for these private methods to be
synchronized.
The canThreadWaitOnLock() method is used to traverse the wait tree,
looking to see if a particular lock is already in the tree. This is
the primary method that is used to detect potential deadlocks. When a
thread is about to perform a hard wait on a lock, it calls this
method. A deadlock is detected if the lock is already in the wait
tree. Note that the implementation is recursive. The method examines
all of the locks owned to see if the lock is in the first level of
the tree. It also traverses each owned lock to get the hard waiting
threads; each hard waiting thread is further examined recursively.
This method uses the class lock for synchronization.
With the ability to detect deadlocks, we can now override the
lock() method of the
ReentrantLock class. This new implementation is
actually not that simple. The ReentrantLock class
is incredibly optimized—meaning it uses minimal
synchronization. In that regard, our new lock()
method is also minimally synchronized.
The first part of the lock() method is for nested locks. If the lock is
already owned by this thread, there is no reason to check for
deadlocks. Instead, we can just call the original lock() method. There is no race condition for this case: only
the owner thread can succeed in the test for nested locks and call
the original lock() method. And since there is no
chance that the owner of the lock will change if the owner is the
currently executing thread, there is no need to worry about the
potential race condition between the isHeldByCurrentThread() and super.lock() method calls.
The second part of the lock() method is used to
obtain new locks. It first checks for deadlocks by calling the
canThreadWaitOnLock() method. If a deadlock is
detected, a runtime exception is thrown. Otherwise, the thread is
placed on the hard wait list for the lock, and the original
lock() method is called. Obviously, a race
condition exists here since the lock() method is
not synchronized. To solve this, the thread is placed on the hard
wait list before the deadlock check is done. By simply reversing the
tasks, it is no longer possible for a deadlock to go undetected. In
fact, a deadlock may be actually detected before it happens due to
the race condition.
There is no reason to override the lock methods that accept a timeout
since these are soft locks. The interruptible lock request is
disabled by routing it to the uninterruptible version of the
lock() method.
Unfortunately, we are not done yet. Condition variables can also free
and reacquire the lock and do so in a fashion that makes our
deadlock-detecting class much more complex. The reacquisition of the
lock is a hard wait since the await() method
can't return until the lock is acquired. This means
that the await() method needs to release the
lock, wait for the notification from the signal()
method to arrive, check for a potential deadlock, perform a hard wait
for the lock, and eventually reacquire the lock.
If you've already examined the code,
you'll notice that the implementation of the
await() method is simpler than we just discussed.
It doesn't even check for the deadlock. Instead, it
simply performs a hard wait prior to waiting for the signal. By
performing a hard wait before releasing the lock, we keep the thread
and lock connected. This means that if a later lock attempt is made,
a loop can still be detected, albeit by a different route.
Furthermore, since it is not possible to cause a deadlock simply by
using condition variables, there is no need to check for deadlock on
the condition variable side. The condition variable just needs to
allow the deadlock to be detected from the lock()
method side. The condition variable also must place the thread on the
hard wait list prior to releasing the lock due to a race condition
with the lock() method—it is possible to
miss detection of the deadlock if the lock is released first.
At this point, we are sure many readers have huge diagrams on their desk—or maybe on the floor—with thread and lock scenarios drawn in pencil. Deadlock detection is a very complex subject. We have tried to present it as simply as possible, but we are sure many readers will not be convinced that this class actually works without a few hours of playing out different scenarios. To help with this, the latest online copy of this class contains many simple test case scenarios (which can easily be extended).
To help further, here are answers to some possible questions. If you are not concerned with these questions, feel free to skip or skim the next section as desired. As a warning, some of these questions are very obscure, so obscure that some questions may not even be understood without a few hours of paper and pencil work. The goal is to work out the scenarios to understand the questions, which can hopefully be answered here.
We have stated that a deadlock condition is detected when a loop in the wait tree is detected. Is it really a loop? The answer is yes. This means that we have to be careful in our search or we can recursively search forever. Let's examine how the loop is formed from another point of view. Any waiting thread node can have only one parent lock node. That's because a thread can't perform a hard wait on more than one lock at a time. Any owned lock node can have only one parent thread node. That's because a lock can't be owned by more than one thread at a time. In this direction, only nodes connected to the top node can form the loop. As long as none of the owned lock nodes are connected to the top thread node, we don't have a loop. It is slightly more complicated than this, but we will address it with the next question.
Why are we using only the thread tree? What about the lock tree? These questions introduce a couple of definitions, so let's back up a few steps. To begin, we are trying to determine whether a thread can perform a hard wait on a particular lock. We then build a wait tree using this thread object as the top node; that's what we mean by the thread tree. However, the lock isn't independent. It is also possible to build a wait tree using the lock object as the top node, which we define as the lock tree. There may be other locks in the lock tree that could be in the thread tree, possibly forming a deadlock condition.
Fortunately, we don't have to traverse the lock tree because the thread tree is guaranteed to contain a root node as the top node. The top node of the thread tree is the currently running thread. It is not possible for this thread to be currently waiting on a lock since it wouldn't be executing the lock request. The top node of the lock tree is only the root node if the lock is not owned. For a loop to form, either the lock tree or the thread tree must be a subtree of the other. Since we know that the thread tree definitely contains the root node, only the lock node can be the subtree. To test for a subtree, we just need to test the top node.
Isn't marking the hard wait prior to checking for the deadlock condition a problem? Can it cause spurious deadlock exceptions? The answer is no. The deadlock condition will definitely occur since the thread will eventually perform the hard wait. It is just being detected slightly before it actually happens. On the other hand, our class may throw more than one deadlock exception once the deadlock has been detected. It must be noted that the purpose of this class is not to recover from the deadlock. In fact, once a deadlock exception is thrown, the class does not clean up after it. A retry attempt throws the same exception.
Can marking the hard wait first interfere with the deadlock check? By marking first, we are making a connection between the thread and the lock. In theory, this connection should be detected as a deadlock condition by the deadlock check. To determine if we're interfering with the deadlock check, we have to examine where the connection is made. We are connecting the lock node to the top thread node—the connection is actually above the top thread node. Since the search starts from the top thread node, it isn't able to detect the deadlock unless the lock node can be reached first. This connection is seen from the lock tree but is not a problem because that tree is not traversed. Traversals by other threads will be detected early as a deadlock condition since the hard wait will eventually be performed.
Can marking the hard wait first cause an error condition in other threads? Will it cause a loop in the trees? We need to avoid a loop in the wait trees for two reasons. First, and obviously, is because it is an indication of a deadlock condition. The second reason is because we will be searching through the wait trees. Recursively searching through a tree that has a loop causes an infinite search (if the lock being sought is not within the loop).
The answer to this question is no, it can't cause an error condition. First, there is no way to enter the loop from a thread node that is not within the loop. All thread nodes within the loop are performing a hard wait on locks within the loop. And all lock nodes within the loop are owned by thread nodes within the loop. Second, it is not possible to start from a thread node that is within the loop. With the exception of the top thread node, all the thread nodes are performing a hard wait. To be able to perform the deadlock check, a thread cannot be in a wait state and therefore can't be in the wait tree. If a loop is formed, only the thread represented by the top thread node can detect the deadlock.
This answer assumes that a deadlock-detected exception has never been thrown; this class is not designed to work once such an exception is thrown. For that functionality, consider using the alternate deadlock-detecting class that is available online.
How can the simple solution of switching the
"thread owns the lock" to the
"thread hard waiting for lock" work
for condition variables? Admittedly, we did a bit of hand
waving in the explanation. A better way to envision it is to treat
the operations as being separate entities—as if the
condition variable is releasing and
reacquiring the lock. Since the reacquisition is mandatory (i.e., it
will eventually occur), we mark the thread for reacquisition before
we release the lock. We can argue that switching the ownership state
to a hard wait state removes the connection from the thread tree,
making detection impossible. This is just an artifact of examining
the wait tree from the condition variable's
perspective. When the lock() method is called at
a later time, we will be using a different thread object as the top
node, forming a different wait tree. From that perspective, we can
use either the ownership state or hard wait state for the detection
of the deadlock.
Why don't we have to check for potential
deadlocks on the condition variable side? It is not
necessary. Marking for the wait operation prior to unlocking works in
a pseudo atomic manner, meaning that it is not possible for another
thread to miss the detection of the deadlock when using the
lock() method. Since it is not possible to create
a new deadlock just by using condition variables, we
don't need to check on this end. Another explanation
is that there is no need to check because we already know the answer:
the thread is capable of performing a hard wait because it has
previously owned the lock and has not had a chance to request
additional locks.
Isn't marking for the hard wait prior to
performing theawait()operation a problem? Can it cause spurious deadlock exceptions? Can
it cause an error condition in other threads? Two of these
questions are very similar to the questions for the lock() method side. The extra question here addresses the issue
of interfering with the deadlock check. That question
doesn't apply on the lock()
method side because we do not perform a deadlock check on the
condition variable side.
However, the answers to the other questions are not exactly the same as before. In this case, the thread is performing a hard wait on the lock before the thread releases ownership of the lock. We are creating a temporary loop—a loop that is created even though the deadlock condition does not exist. This is not a case of detecting the deadlock early—if the loop were detected, the deadlock detected would be incorrect.
These three questions can be answered together. As with the error
question on the lock() method side, it is not
possible to enter the loop from a thread node outside of the loop.
Second, the one thread node that is within this small loop is not
performing a deadlock check. And finally, any deadlock check does not
traverse the lock tree. This means that an error condition
can't occur in another thread and that detecting a
false deadlock condition also can't occur in another
thread. Of course, eventually it would be possible to get to the lock
node externally, but by then, the loop would have been broken. It is
not possible for another thread to own the lock unless the condition
variable thread releases it first.
To review, we are traversing the thread tree to check whether the lock tree is a subtree. Instead of recursively traversing from the thread tree, isn't it easier to traverse upward from the lock tree? Our answer is maybe. We simply list the pluses and minuses and let the reader decide. Two good points can be made for traversing from the lock tree. First, the search is not recursive. Each node of the lock tree has only one parent, so going upward can be done iteratively. Second, moving upward from lock node to parent thread node does not need any iterations—the owner thread object is already referenced by the lock object. On the other hand, moving downward from the thread node to the lock node requires iteration through the registered locks list.
Unfortunately, there are two bad points to traversing upward from the lock tree. First, moving upward from the thread node to the lock node on which it is performing the hard wait is incredibly time-consuming. We need to iterate through the registered locks list to find the hard wait lists, which we must, in turn, iterate through to find the lock node. In comparison, moving downward from the lock node to the thread node is done by iterating through one hard wait list. And it gets worse. We need to iterate through all of the hard wait lists. By comparison, we need to iterate only through the hard wait lists in the wait tree in our existing implementation. This one point alone may outweigh the good points.
The second bad point stems from the techniques that we use to solve the race conditions in the lock class. The class allows loops to occur—even temporarily creating them when a deadlock condition does not exist. Searching from a lock node that is within a loop—whether recursively downward or iteratively upward—does not terminate if the top thread node is not within the loop. Fortunately, this problem can be easily solved. We just need to terminate the search if the top lock node is found. Also note that finding the top lock node is not an indication of a deadlock condition since some temporary loops are formed even without a deadlock condition.
To review, we are traversing the thread tree instead of the lock tree because the top thread node is definitely the root node. The top lock node may not be the root node. However, what if the top lock node is also the root node? Isn't this a shortcut in the search for a deadlock? Yes. It is not possible for the lock tree to be a subtree of the thread tree if the top lock node is a root node. This means we can remove some calls to the deadlock check by first checking to see if the lock is already owned. This is an important improvement since the deadlock check is very time-consuming.
However, a race condition exists when a lock has no owner. If the lock is unowned, there is no guarantee that the lock will remain unowned during the deadlock check. This race condition is not a problem since it is not possible for any lock in the wait tree to be unowned at any time during the deadlock check; the deadlock check may be skipped whether or not the lock remains unowned.
This shortcut is mostly for locks that are infrequently used. For frequently used locks, this shortcut is highly dependent on the thread finding the lock to be free, which is based on the timing of the application.
The modification with some deadlock checking removed is available online in our alternate deadlock-detecting lock.
