Analyze Hanging Programs Using Java Thread Traces

In this article, we will discuss the following topics:

• How to analyze hanging, deadlocked or frozen programs?
• How to generate stack traces?
• What is deadlock?

What to Do When Your Applications Hang?

If you think your program is hanging, generate a stack trace.  A stack trace of all threads can be useful when trying to diagnose a number of issues such as deadlocks or hangs.

When looking at stack traces, check the following:

• If a thread waits on
• A monitor lock
• A condition variable
• If system threads show up as the current threads
• If the program is deadlocked then some of the system threads will probably show up as the current threads, because there is nothing else for the JVM to do

How to Generate Stack Traces?

With thread stack trace, you can analyze the source of deadlocks.  There are multiple approaches:

• Using jstack command, it can 
• attach to the specified process (or core file) and prints the stack traces of all threads that are attached to the virtual machine (this includes Java threads and VM internal threads).
• For each Java frame, the full class name, method name, 'bci' (byte code index) and line number, if available, are printed.
• Obtain stack traces from a core dump:
• jstack $JAVA_HOME/bin/java core
• Be used to print a mixed stack.  That is, it can print native stack frames in addition to the java stack. 
• • Native frames are the C/C++ frames associated with VM code, and JNI/native code.
  • To print a mixed stack the -m option is used.
• When a deadlock occurs, doing a Ctrl + Break on Windows forces a Java level thread stack trace to print to standard output. On Solaris and Linux, sending a SIGQUIT signal to the Java process id does the same.
• Beginning with Java 6, the bundled JConsole tool added the capability to attach to a hung Java process and analyze the root cause of the deadlock.

What Is Deadlock?

If you're working with a moderately complex multithreaded program, then sooner or later, you'll hit the problem of deadlock^[2,3].  Deadlock is the phenomenon when, typically, two threads each hold an exclusive lock that the other thread needs in order to continue.  In principle, there could actually be more threads and locks involved. Most of the time, a deadlock is caused by acquiring locks in the wrong order.

Deadlock can occur with any locking primitive. It notably occurs with the synchronized keyword, but it's liable to occur with locks, Semaphores, blocking queues etc.

A Deadlock Example

We used jstack to generate Java thread traces as follows:
$ jstack 3554

Our VM is HotSpot Client from JDK 7:

Found one Java-level deadlock:
=============================
"RunLevelControllerThread-1377458723460":
  waiting to lock monitor 0x871756a8 (object 0x93480480, a java.util.logging.LogManager$LoggerContext),
  which is held by "RunLevelControllerThread-1388458723457"
"RunLevelControllerThread-1388458723457":
  waiting to lock monitor 0x87173448 (object 0x93472290, a java.util.logging.LogManager),
  which is held by "RunLevelControllerThread-1377458723460"

Java stack information for the threads listed above:
===================================================
"RunLevelControllerThread-1377458723460":
    at java.util.logging.LogManager$LoggerContext.findLogger(LogManager.java:489)
    - waiting to lock <0x93480480> (a java.util.logging.LogManager$LoggerContext)
    at java.util.logging.LogManager.getLogger(LogManager.java:910)
    at com.sun.enterprise.server.logging.LogManagerService.postConstruct(LogManagerService.java:412)
    - locked < x93472290> (a java.util.logging.LogManager)
    - locked <0x93465158> (a java.lang.Class for java.util.logging.Logger)


"RunLevelControllerThread-1388458723457":
    at java.util.logging.LogManager.drainLoggerRefQueueBounded(LogManager.java:811)
    - waiting to lock <0x93472290> (a java.util.logging.LogManager)
    at java.util.logging.LogManager$LoggerContext.addLocalLogger(LogManager.java:511)
    - locked < x93480480> (a java.util.logging.LogManager$LoggerContext)

In the above example, you can see that two threads:

• RunLevelControllerThread-1377458723460 
• RunLevelControllerThread-1388458723457 

were waiting for locks that were held by each other.  This have created a deadlock.

References

1. jstack - Stack Trace
2. Deadlock
3. How to Avoid Deadlocks (Xml and More)

How to Avoid Deadlocks

Deadlock can be illustrated by the classic dining philosophers problem^[1].

In an operating system, a deadlock^[2] is a situation which occurs when a process enters a waiting state because a resource requested by it is being held by another waiting process, which in turn is waiting for another resource. If a process is unable to change its state indefinitely because the resources requested by it are being used by other waiting process, then the system is said to be in a deadlock.

In Java programming, deadlocks may manifest themselves where multiple threads wait forever due to a cyclic locking dependency.  For example, when thread A holds lock L and tries to acquire lock M, but at the same time thread B holds M and tries to acquire L, both threads will wait forever.  Just as threads can deadlock when they are each waiting for a lock that the other holds and will not release, they can also deadlock when waiting for resources. Comparing to deadlock, starvation and livelock are much less common a problem, but are still problems that every designer of concurrent software is likely to encounter. Java applications do not recover from deadlock, so it is worthwhile to ensure that your design precludes the conditions that could cause it^[6].

In this article, we will discuss some threading best practices to avoid deadlocks.

Necessary Conditions

A deadlock situation can arise only if all of the following conditions hold simultaneously in a system:^[3]

1. Mutual Exclusion: At least, one resource must be non-shareable.  Only one process can use the resource at any given instant of time.
2. Hold and Wait: A process is currently holding at least one resource and requesting additional resources which are being held by other processes.
3. No Preemption: The operation system can de-allocate resources once they have been allocated. They must released by the holding process voluntarily.
4. Circular Wait: A process waiting for a resource which is being held by another process, which in turn is waiting for another process to release a resource.

Unfulfillment of any of these conditions is enough to preclude a deadlock from occurring.

How to Avoid Deadlocks

Never cede control to the client within a synchronized method or block^[4]

Invoking an alien method with a lock held is asking for liveness trouble. The alien method might acquire other locks (risking deadlock) or block for an unexpectedly long time, stalling other threads that need the lock you hold.

In other words, inside a synchronized region, do not invoke a method that is designed to be overridden, or one provided by a client in the form of a function object (i.e., object references used to implement the Strategy pattern).  The class has no knowledge of what the alien method does and has no control over it. If you do call an alien method from within a synchronized region, you open the opportunities of deadlocks by allowing the following conditions to hold:

• Hold and Wait
• Circular Wait

Because you call the alien method from a shynchronized region, it holds a lock. If this alien method is overriden and it engages the services of another thread to do the deed,  Hold and Wait condition will be established.  Given another counterpart of Hold-and-Wait, it can possibly form a Circular Wait condition.

Calling a method with no locks held is called an open call^[6], and classes that rely on open calls are more well-behaved and composable than classes that make calls with locks held.

More generally, try to limit the amount of work that you do from within synchronized regions. When you are designing a mutable class, think about whether it should do its own synchronization. Synchronize your class internally only if there is a good reason to do so, and document your decision clearly.

Ensure that resources are always acquired in some well-defined order^[7]

Deadlocks can be avoided by assigning a partial order to the resources, and establishing the convention that all resources will be requested in order, and released in reverse order, and that no two resources unrelated by order will ever be used by a single unit of work at the same time.  This solution to the dining philosophers problem was originally proposed by Dijkstra.

There are different approaches to enforce a partial order to the resources:

1. If resources are static and known in advanced
   • Just stick to a programming policy (i.e., all programmers apply the policy of acquiring the locks in some well-defined order)
   • Provide a method that combines acquisition and release of the multiple locks in the correct way (see here for an example)
2. If resources are not known in advanced or acquired dynamically
   • We have to explicitly define some way of ordering them. For example,
     • If locking will only exist for the lifetime of the application
       • We can use the identity hash code (System.identityHashCode(r)) of the two objects.
       • In the rare case that two objects have the same hash code, we must use an arbitrary means of ordering the lock acquisitions, and this reintroduces the possibility of deadlock. To prevent inconsistent lock ordering in this case, a third tie breaking lock can be used^[6].

Removing the mutual exclusion condition

Removing the mutual exclusion condition means that no process will have exclusive access to a resource. This proves impossible for resources that cannot be spooled. But even with spooled resources, deadlock could still occur. Algorithms that avoid mutual exclusion are called non-blocking synchronization algorithms.

For example, optimistic concurrency control^[9] uses a pair of consistency markers in the data structure. Processes reading the data structure first read one consistency marker, then read the relevant data into an internal buffer, then read the other marker, and then compare the markers. The data is consistent if the two markers are identical. Markers may be non-identical when the read is interrupted by another process updating the data structure. In such a case, the process discards the data in the internal buffer and tries again.

Finally, immutability is great for multi-threading. Instances of immutable class appear constant. Therefore, no external synchronization is necessary. Examples include String, Long, and BigInteger.

Using timed lock acquisition to acquire multiple locks^[6]

Another technique for detecting and recovering from deadlocks is to use the timed tryLock feature of the explicit Lock classes instead of intrinsic locking.

If a lock acquisition times out, you can release the locks, back off and wait for a while, and try again, possibly clearing the deadlock condition and allowing the program to recover. However, this technique works only when the two locks are acquired together; if multiple locks are acquired due to the nesting of method calls, you cannot just release the outer lock, even if you know you hold it.

Conclusion

We conclude this article by quoting Goetz et al.^[6]:

Like many other concurrency hazards, deadlocks rarely manifest themselves immediately. The fact that a class has a potential deadlock doesn’t mean that it ever will deadlock, just that it can. When deadlocks do manifest themselves, it is often at the worst possible time—under heavy production load.

References

1. Dining philosophers problem
2. Deadlock
3. Advanced Synchronization in Java Threads by Scott Oaks and Henry Wong
4. Effective Java by Joshua Block
5. Threading Best Practices
6. Java Concurrency in Practice by Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes and Doug Lea
7. Deadlock Tutorial
8. The Java Tutorial (Concurrency)
9. Optimistic concurrency control
10. Concurrency: State Models & Java Programs (2nd Edition), by Jeff Magee and Jeff Kramer.
11. Java Concurrent Animated
12. Analyze Hanging Programs Using Java Thread Traces (Xml and More)