6.4 Deadlock Detection - Java Threads, Third Edition
|
< Day Day Up > |
|
6.4 Deadlock DetectionThe problem with deadlock is that it causes the program to hang indefinitely. Obviously, if a program hangs, deadlock may be the cause. But is deadlock always the cause? In programs that wait for users, wait for external systems, or have complex interactions, it can be very difficult to tell a deadlock situation from the normal operation of the program. Furthermore, what if the deadlock is localized? A small group of threads in the program may deadlock with each other while other threads continue running, masking the deadlock from the user (or the program itself). While it is very difficult to prevent deadlock, can we at least detect it? To understand how to detect deadlock, we must first understand its cause. Figure 6-1 shows two cases of threads and locks waiting for each other. The first case is of locks waiting for the owner thread to free them. The locks are owned by the thread so they can't be used by any other thread. Any thread that tries to obtain these locks is placed into a wait state. This also means that if the thread deadlocks, it can make many locks unavailable to other threads. Figure 6-1. Lock trees The second case is of threads waiting to obtain a lock. If the lock is owned by another thread, the thread must wait for it to be free. Technically, the lock does not own the thread, but the effect is the same梩he thread can't accomplish any other task until the lock is freed. Furthermore, a lock can have many threads waiting for it to be free. This means that if a lock deadlocks, it can block many waiting threads. We have introduced many new terms here梬e'll explain them before we move on. We define a deadlocked lock as a lock that is owned by a thread that has deadlocked. We define a deadlocked thread as a thread that is waiting for a deadlocked lock. These two definitions are admittedly circular, but that is how deadlocks are caused. A thread owns a lock that has waiting threads that own a lock that has waiting threads that own a lock, and so on. A deadlock occurs if the original thread needs to wait for any of these locks. In effect, a loop has been created. We have locks waiting for threads to free them, and threads waiting for locks to be freed. Neither can happen because indirectly they are waiting for each other. We define a hard wait as a thread trying to acquire a lock by waiting indefinitely. We call it a soft wait if a timeout is assigned to the lock acquisition. The timeout is the exit strategy if a deadlock occurs. Therefore, for deadlock detection situations, we need only be concerned with hard waits. Interrupted waits are interesting in this regard. If the wait can be interrupted, is it a hard wait or a soft wait? The answer is not simple because there is no way to tell if the thread that is implemented to call the interrupt() method at a later time is also involved in the deadlock. For now, we will simply not allow the wait for the lock to be interrupted. We will revisit the issue of the delineation between soft and hard waits later in this chapter. However, in our opinion, interruptible waits should be considered hard waits since using interrupts is not common in most programs. Assuming that we can keep track of all of the locks that are owned by a thread and keep track of all the threads that are performing a hard wait on a lock, is detecting a potential deadlock possible? Yes. Figure 6-2 shows a potential tree that is formed by locks that are owned and formed by hard waiting threads. Given a thread, this figure shows all the locks that are owned by it, all the threads that are hard waiting on those locks in turn, and so on. In effect, each lock in the diagram is already waiting, whether directly or indirectly, for the root thread to eventually allow it to be free. If this thread needs to perform a hard wait on a lock, it can't be one that is in this tree. Doing so creates a loop, which is an indication of a deadlock situation. In summary, we can detect a deadlock by simply traversing this tree. If the lock is already in this tree, a loop is formed, and a deadlock condition occurs. Figure 6-2. Completed thread wait tree Using this algorithm, here is an implementation of a deadlock-detecting lock: package javathreads.examples.ch06;
public class DeadlockDetectedException extends RuntimeException {
public DeadlockDetectedException(String s) {
super(s);
}
}
package javathreads.examples.ch06;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;
public class DeadlockDetectingLock extends ReentrantLock {
private static List deadlockLocksRegistry = new ArrayList( );
private static synchronized void registerLock(DeadlockDetectingLock ddl) {
if (!deadlockLocksRegistry.contains(ddl))
deadlockLocksRegistry.add(ddl);
}
private static synchronized void unregisterLock(DeadlockDetectingLock ddl) {
if (deadlockLocksRegistry.contains(ddl))
deadlockLocksRegistry.remove(ddl);
}
private List hardwaitingThreads = new ArrayList( );
private static synchronized void markAsHardwait(List l, Thread t) {
if (!l.contains(t)) l.add(t);
}
private static synchronized void freeIfHardwait(List l, Thread t) {
if (l.contains(t)) l.remove(t);
}
private static Iterator getAllLocksOwned(Thread t) {
DeadlockDetectingLock current;
ArrayList results = new ArrayList( );
Iterator itr = deadlockLocksRegistry.iterator( );
while (itr.hasNext( )) {
current = (DeadlockDetectingLock) itr.next( );
if (current.getOwner( ) == t) results.add(current);
}
return results.iterator( );
}
private static Iterator getAllThreadsHardwaiting(DeadlockDetectingLock l) {
return l.hardwaitingThreads.iterator( );
}
private static synchronized
boolean canThreadWaitOnLock(Thread t, DeadlockDetectingLock l) {
Iterator locksOwned = getAllLocksOwned(t);
while (locksOwned.hasNext( )) {
DeadlockDetectingLock current =
(DeadlockDetectingLock) locksOwned.next( );
if (current == l) return false;
Iterator waitingThreads = getAllThreadsHardwaiting(current);
while (waitingThreads.hasNext( )) {
Thread otherthread = (Thread) waitingThreads.next( );
if (!canThreadWaitOnLock(otherthread, l)) {
return false;
}
}
}
return true;
}
public DeadlockDetectingLock( ) {
this(false, false);
}
public DeadlockDetectingLock(boolean fair) {
this(fair, false);
}
private boolean debugging;
public DeadlockDetectingLock(boolean fair, boolean debug) {
super(fair);
debugging = debug;
registerLock(this);
}
public void lock( ) {
if (isHeldByCurrentThread( )) {
if (debugging) System.out.println("Already Own Lock");
super.lock( );
freeIfHardwait(hardwaitingThreads, Thread.currentThread( ));
return;
}
markAsHardwait(hardwaitingThreads, Thread.currentThread( ));
if (canThreadWaitOnLock(Thread.currentThread( ), this)) {
if (debugging) System.out.println("Waiting For Lock");
super.lock( );
freeIfHardwait(hardwaitingThreads, Thread.currentThread( ));
if (debugging) System.out.println("Got New Lock");
} else {
throw new DeadlockDetectedException("DEADLOCK");
}
}
public void lockInterruptibly( ) throws InterruptedException {
lock( );
}
public class DeadlockDetectingCondition implements Condition {
Condition embedded;
protected DeadlockDetectingCondition(ReentrantLock lock, Condition e) {
embedded = e;
}
public void await( ) throws InterruptedException {
try {
markAsHardwait(hardwaitingThreads, Thread.currentThread( ));
embedded.await( );
} finally {
freeIfHardwait(hardwaitingThreads, Thread.currentThread( ));
}
}
public void awaitUninterruptibly( ) {
markAsHardwait(hardwaitingThreads, Thread.currentThread( ));
embedded.awaitUninterruptibly( );
freeIfHardwait(hardwaitingThreads, Thread.currentThread( ));
}
public long awaitNanos(long nanosTimeout) throws InterruptedException {
try {
markAsHardwait(hardwaitingThreads, Thread.currentThread( ));
return embedded.awaitNanos(nanosTimeout);
} finally {
freeIfHardwait(hardwaitingThreads, Thread.currentThread( ));
}
}
public boolean await(long time, TimeUnit unit)
throws InterruptedException {
try {
markAsHardwait(hardwaitingThreads, Thread.currentThread( ));
return embedded.await(time, unit);
} finally {
freeIfHardwait(hardwaitingThreads, Thread.currentThread( ));
}
}
public boolean awaitUntil(Date deadline) throws InterruptedException {
try {
markAsHardwait(hardwaitingThreads, Thread.currentThread( ));
return embedded.awaitUntil(deadline);
} finally {
freeIfHardwait(hardwaitingThreads, Thread.currentThread( ));
}
}
public void signal( ) {
embedded.signal( );
}
public void signalAll( ) {
embedded.signalAll( );
}
}
public Condition newCondition( ) {
return new DeadlockDetectingCondition(this);
}
}Before we go into detail on this deadlock-detecting lock, it must be noted that this listing has been cut down for this book. For the latest, fully commented version, including testing tools, please see the online examples, which include (as example 1) a class that can be used to test this implementation. In terms of implementation, this class inherits from the Lock interface, so it may be used anywhere that a Lock object is required. Furthermore, deadlock detection requires the registration of all locks involved in the deadlock. Therefore, to detect a deadlock, replace all the locks with this class, even the locks provided by the synchronized keyword. It may not be possible to detect a loop if any of the locks are unregistered. 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梐 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梬hile the list is not梩he 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梞eaning 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梚t 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梠r maybe on the floor梬ith 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梩he 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梐s 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 the await() 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梐 loop that is created even though the deadlock condition does not exist. This is not a case of detecting the deadlock early梚f 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梩he 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梕ven temporarily creating them when a deadlock condition does not exist. Searching from a lock node that is within a loop梬hether recursively downward or iteratively upward梔oes 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. The deadlock-detecting lock disallows interruptible locking requests. What if we do not agree with this compromise? There are only a few options. Disallowing the interrupt was the easiest compromise that works for the majority of the cases. For those readers who believe an interruptible lock should be considered a soft lock, the change is simple梛ust don't override the lockInterruptibly() method. And for those readers who believe that an interruptible lock should be considered a hard lock while still not compromising interrupt capability, here is a modified version of the method: public void lockInterruptibly( ) throws InterruptedException {
if (isHeldByCurrentThread( )) {
if (debugging) System.out.println("Already Own Lock");
try {
super.lockInterruptibly( );
} finally {
freeIfHardwait(hardwaitingThreads,
Thread.currentThread( ));
}
return;
}
markAsHardwait(hardwaitingThreads, Thread.currentThread( ));
if (canThreadWaitOnLock(Thread.currentThread( ), this)) {
if (debugging) System.out.println("Waiting For Lock");
try {
super.lockInterruptibly( );
} finally {
freeIfHardwait(hardwaitingThreads,
Thread.currentThread( ));
}
if (debugging) System.out.println("Got New Lock");
} else {
throw new DeadlockDetectedException("DEADLOCK");
}
}This change is also provided online in our alternate deadlock-detecting lock class. In terms of implementation, it is practically identical to that of the lock() method. The difference is that we now place all lock requests within a try-finally clause. This allows the method to clean up after the request, regardless of whether it exits normally or by exception. The deadlock-detecting lock regards all lock requests with a timeout as soft locks. What if we do not agree with this premise? This topic is open to debate. While an application that uses timeouts should have an exit strategy when the timeout occurs, what if the exit strategy is to inform the user and then simply retry? In this case, deadlock could occur. Furthermore, at what point is retrying no longer tolerable? When the timeout period is more than an hour? A day? A month? Obviously, these issues are design-specific. Here is an implementation of the tryLock() method that treats the request as a soft wait梑ut only if it is less than a minute: public boolean tryLock(long time, TimeUnit unit)
throws InterruptedException {
// Perform operation as a soft wait
if (unit.toSeconds(time) < 60) {
return super.tryLock(time, unit);
}
if (isHeldByCurrentThread( )) {
if (debugging) System.out.println("Already Own Lock");
try {
return super.tryLock(time, unit);
} finally {
freeIfHardwait(hardwaitingThreads,
Thread.currentThread( ));
}
}
markAsHardwait(hardwaitingThreads, Thread.currentThread( ));
if (canThreadWaitOnLock(Thread.currentThread( ), this)) {
if (debugging) System.out.println("Waiting For Lock");
try {
return super.tryLock(time, unit);
} finally {
freeIfHardwait(hardwaitingThreads,
Thread.currentThread( ));
if (debugging) System.out.println("Got New Lock");
}
} else {
throw new DeadlockDetectedException("DEADLOCK");
}
}This change is also provided in the online examples as an alternative to the deadlock-detecting lock class (including a testing program, which is example 2 in this chapter). Its implementation is practically identical to that of the lock() method. Again, the difference is that we now place all lock requests within a try-finally clause. This allows the method to clean up after the request, regardless if it exits normally or by exception. This example treats the operation as a soft wait for requests that are under a minute. The request is treated as a hard wait otherwise. We leave it up to you to modify the code to suit your needs. One alternate solution could be to use a different time period to separate soft and hard wait lock operations; this time period could also be calculated depending on conditions in the program. Another alternate solution could be for the trylock() method to return false instead of throwing the deadlock-detected exception. While the deadlock-detecting lock is well-designed for detecting the deadlock condition, the design for reporting the condition is pretty weak. Are there better options? This is actually intentional. This class is not designed to be used in a production environment. Searching for deadlocks can be very inefficient梩his class should be used only during development. In fact, most readers will probably not use this class at all. The main purpose of this class is so that we can understand deadlocks梙ow to detect them and, eventually, how to prevent them. For those who insist on using the deadlock-detecting lock in a production environment, there are a few options. The class can be designed to fail fast梞eaning that if a deadlock is detected, the class could throw the exception for every invocation, regardless of whether the request is involved in the deadlock or not. Another option is for the class to report the condition in a manner that allows the program to shut down properly. A third, and not recommended, option is to allow the class to continue functioning. The first and third options are provided as conditional code in the alternate online example. This topic of deadlock detection seems to be incredibly complex. In fact, the discussion on the theory and implementation is more than twice as long as the code itself. Is this topic really that complex? The concept of deadlock detection is complex, but there is another reason why this class is even more complex. The implementation of this class is accomplished by minimal synchronization. This is mainly because the ReentrantLock class is implemented with minimal synchronization, making the class implementation more complex. |
|
|
< Day Day Up > |
|