Friday, December 31, 2010

Optimizing concurrency with Freescale’s Deadlock Preventer

The overall concurrency of a program, given it already uses an optimal number of threads, will depend on how much lock contention is occurring.

To avoid both deadlocks and lock contention, synchronization primitives should be the most granular possible given a fixed number of primitives.

For example, in the following snippet:

public synchronized void setProperty(Object newValue) {
    value = newValue;
    notifyPropertyChange();
}

private void notifyPropertyChange() {
    synchronized(listeners) {
        for (IListener listener : listeners)
            listener.changed();
    }
}

The setProperty() method is synchronized in order to protect the “value” data from concurrent data access.  Inadvertently, the synchronized block will cause all the code path executed by the listener.changed() invocation to needlessly have the synchronized(this) lock as a precedent.

This will not only cause the code to have a sub-optimal concurrent execution, but also introduce a lock order dependency between ‘this’, ‘listeners’, and whatever lock is acquired by the listener’s changed() implementation, possibly eventually causing a deadlock (in the Deadlock' Preventer’s terminology, the ‘listeners’ lock is then a ‘follower’ of the ‘this’ lock, and the ‘this’ lock a precedent of the ‘listeners’ lock).

The code could be re-written as follows:

public void setProperty(Object newValue) {
    synchronized(this) {
        value = newValue;
    }
    notifyPropertyChange();
}

By simply reducing the granularity of the ‘this’ lock acquisition, we improve possible concurrent execution, eliminate the lock dependency, and avoid lock ordering acquisition problems between ‘this’ and ‘listeners’, and ‘this’ and all listener’s changed() implementations, without any negative effect whatsoever.

We could also re-write the notifyPropertyChange() implementation as follows:

private void notifyPropertyChange() {
    IListener[] tmp;
    synchronized(listeners) {
        tmp = listeners.clone();
    }
    for (IListener listener : tmp)
        listener.changed();
}

At the cost of the clone() statement (something probably insignificant compared to the code executed in the listeners), the lock dependency is completely removed between ‘this’, ‘listeners’, and all lock acquisitions in the listener’s changed() implementations.

In a java program, the locks with the most number of followers are not only the most likely to cause deadlocks, but also the locks that are likely to reduce overall system concurrency.

It is unfortunately very easy to induce unnecessary dependencies between synchronization primitives, and hard to discover which locks have effectively a large number of followers.

Without a tool such as the Deadlock Preventer, which helps identifying which locks have the most followers, developers would be reduced to half hazardly trying to improve lock granularity without knowing where to start.

This is very similar to performance optimization without using a profiler:  without knowing what takes the most time, developer’s time is easily wasted, and so is concurrency optimization.

Help with the Deadlock Preventer

With the latest release of the Deadlock Preventer, it is now possible to use the Deadlock Preventer view to download lock statistics for a java program.

image

By right-clicking on the process name in the “Conflicts” tab, and selecting the “Statistics…” menu, the following dialog appears:

image

The table lists all locks in the program, the number of followers and precedents, and their acquisition locations.  More information can be obtained for each lock by selecting its row and doing copy, which puts the following information in the clipboard (for the first lock in the table above):

lock: java.lang.Object (id=2), precedents(1) followers(1)
  zzz.Main.test(Main.java:14)
  zzz.Main.main(Main.java:6)
  precedents:
    java.lang.Object (id=1), thread id(1 (main))
     zzz.Main.test(Main.java:13)
     zzz.Main.main(Main.java:6)
  followers:
    java.lang.Object (id=1), thread id(13 (Thread-2))
     zzz.Main$1.run(Main.java:22)
     java.lang.Thread.run(Thread.java:619)

The text contains detailed information about each precedents and followers, along with the stack trace in which their relationship to the lock were recorded.

The information for all locks can also be exported to a single text file by using the “Export…” button.

One very useful way to use the statistics generated by the Deadlock Preventer is to sort all the locks by their follower count.

To give an example of what large programs lock statistics look like, the following table shows what the Eclipse IDE synchronization primitives statistics just after opening the workbench window:

image

Listing the top followers’ count locks out of a total of 21 830 locks.

2 comments:

jtonic said...

Very useful tool.
Eclipse Jobs is a very powerful API, but IMHO an eclipse developer could easily feel overwhelmed by many subsequent (and probably improper order) lock acquisitions.
Tracking down a concurrent issue and to fixing it is a very tedious and time consuming task, and the developer is not at all very confident with his solution.
Definitely the Deadlock Preventer will go in my Eclipse development toolbox, besides other useful tools such as Mylyn.

Serge Beauchamp said...

Thanks for your comment :)