README.adoc

jtwfg Java library

Introduction

jtwfg is a small, standalone java library.

The typical use case for someone is having some kind of own "execution engine" implementation (local, distributed, grid…​) with some kind of tasks in it, with optional dependencies between the tasks. Someone wants to be able to easily detect deadlocks in his/her engine.

Of course, jtwfg also works for any other kind of "find circular dependencies problems", not only deadlocks.

jtwfg implements a task wait for graph model with a deadlock detection algorithm.

To use the jtwfg deadlock detection, you transform your "execution engine" domain model objects into jtwfg graph model objects and call then the jtwfg deadlock detector.

Example 1 for a deadlock in a "task wait for graph"

A graph consists of tasks and synchronous waits-for edges. As soon as a circular dependency exists, the involved tasks are deadlocked.

In this first example you see two tasks, each waiting for the other.

Since they are both waiting synchronously for each other forever, they are deadlocked.

jtwfg can analyze such graphs and find the deadlock(s).

Example 2 for a deadlock in a "task wait for graph"

The situation in the second example is a bit more interesting.

Here, we have a circular dependency consisting of "Task 1", "Task 2" and "Task 3". Since they are all waiting synchronously for each other forever, they are deadlocked. "Task 4" is also deadlocked, although it is not in the circle. It is waiting for a deadlocked task. Same for "Task 6" and "Task 7", also deadlocked.

"Task 5" is fine.

jtwfg can analyze such graphs and tell you

• If there is a deadlock in the graph

• How many deadlock circles exist and which tasks are in them

• What other tasks (outside of a deadlock circle) are also deadlocked

Other use cases

Beside of the mentioned classic "custom execution engine" deadlock use case, jtwfg can also be used to find any kind of circular dependencies in problem areas like configuration, dependency injection, …​

What about a "task resource assignment graph" model?

Check out jtrag.

More about the deadlock detection topic in general

For more details about deadlock detection algorithms see e.g. Daniel Moser’s semester project.

Usage

Usage scenario 1

Step 1

At some point in time you wonder about having a deadlock in your custom engine domain model objects. You transform your domain model objects into the (simple) jtwfg model objects using a jtwfg graph builder object:

GraphBuilder<String> builder = new GraphBuilder<>();
builder.addTaskWaitsFor("task 1", "task 2");
builder.addTaskWaitsFor("task 2", "task 1");
builder.addTask("task 3");
builder.addTask("task 4");
Graph<String> graph = builder.build();

Step 2

As soon as you have a jtwfg graph instance, you can use the jtwfg deadlock detector to find deadlocks:

DeadlockDetector<String> deadlockDetector = new DeadlockDetector<>();
DeadlockAnalysisResult<String>  analyzisResult = deadlockDetector.analyze(graph);
if(analyzisResult.hasDeadlock()){
   // do something in your domain like throwing an exception or killing a task or ...
   //
   // System.out.println(analyzisResult)
}

Usage scenario 2: "Update the jtwfg model" as you update your domain model objects and check for deadlocks on the fly

Probably you want to keep the jtwfg model objects "in sync" with your domain model objects and check for deadlocks on the fly as soon as you update your model objects.Probably you use various threads to update your domain model objects and the jtwfg model objects.

That’s fine.

See executable documentation in src/test/groovy for this and more examples.

Thread-safety of jtwfg

For simplicity and comfort, the jtwfg 'GraphBuilder' and 'DeadlockDetector' classes are threadsafe. See the documentation in the source code for more information about thread-safety.

If you would like to use jtwfg single-threaded and have performance issues, let me know.

Limitations of jtwfg

• At the moment jtwfg supports only simple, synchronous "waits for" dependencies.

• The algorithms are not yet tuned and work more or less in a "brute force" manner. Please create a github issue if you have zillions of tasks and run into performance / memory issues.

Requirements

To use this library you need

• Java 8 or later

Installation

Usage in Gradle, Maven, …​

Gradle based build

Add the following dependency in your gradle build file:

repositories {
   mavenCentral()
}

dependencies {
    compile 'ch.petikoch.libs:jtwfg:x.y.z' // replace x.y.z with the real version

    // or "latest" release, for the braves:
    //compile 'ch.petikoch.libs:jtwfg:+'
}

Maven based build

Add jtwfg as dependency to your pom.xml:

        <dependency>
            <groupId>ch.petikoch.libs</groupId>
            <artifactId>jtwfg</artifactId>
            <version>x.y.z</version> <!-- replace x.y.z with the real version -->
            <!-- or latest release, for the braves
            <version>RELEASE</version>
            -->
        </dependency>

Release notes

See https://github.com/Petikoch/jtwfg/releases.

Support

Please use GitHub issues and pull requests for support.

How to build the project

To run a build of the jtwfg project on your machine, clone the git repo to your local machine and start the gradle based build using the gradle wrapper from the shell/command line:

> ./gradlew build

How to contribute

See DEVELOPMENT.adoc

My motivation to create jtwfg

Motivation 1

Since I didn’t found a "small" and "standalone" library for custom engine deadlock detection on the JVM, I wrote my own. If you know about a solution, thanks for notifying me.

Update January 2015: I found JGraphT and compared it with jtwfg here.

Update April 2015: For deadlock prevention in the java.util.concurrent.locks Domain, I found the CycleDetectingLockFactory class in Google’s excellent Guava library. Read a comparison here.

Motivation 2

I wanted to try the common open source platforms and tools like Github, Bintray, Travis-CI, Coveralls…​ and what’s better than to do this with an own little open source project?

Best regards,