jtrag is is a small java library on top of jtwfg. It adds a "task resource assignment graph" API to the "task wait for graph" API of jtwfg.
The typical use case for someone is having some kind of own "execution engine" implementation (local, distributed, grid…) with some kind of tasks and resources in it, with optional dependencies between the tasks and resources. Someone wants to be able to easily detect deadlocks in his/her engine.
jtrag together with jtwfg implements a graph model with a deadlock detection algorithm.
To use the jtrag/jtwfg deadlock detection, you transform your "execution engine" domain model objects into jtrag/jtwfg graph model objects and call then the jtwfg deadlock detector.
A graph consists of tasks and resources. Resources are assigned to tasks and tasks can be dependent on resources. As soon as a circular relationship exists, the involved tasks and resources are deadlocked.
In this first example you see two tasks and two resources with a circular relationship.
Since they are waiting synchronously for each other forever, they are deadlocked.
jtrag/jtwfg can analyze such graphs and find the deadlock(s).
The situation in the second example is a bit more interesting.
Here, we have a circle consisting of "Task 1", "Resource 1", "Task 2", "Resource 2", "Task 3" and "Resource 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 resource. Same for "Resource 4" and "Task 5", also deadlocked.
"Task 6" is fine.
jtrag/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 and resources (outside of a deadlock circle) are also deadlocked
Beside of the mentioned classic "custom execution engine" deadlock use case, jtrag/jtwfg can also be used to find any kind of circular dependencies in problem areas like configuration, dependency injection, …
For more details about deadlock detection algorithms see e.g. Daniel Moser’s semester project.
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) jtrag/jtwfg model objects using a jtrag graph builder object:
GraphBuilder builder = new GraphBuilder();
builder.addTask2ResourceDependency("task 1", "resource 1");
builder.addResource2TaskAssignment("resource 1", "task 2");
builder.addTask2ResourceDependency("task 2", "resource 2");
builder.addResource2TaskAssignment("resource 2", "task 1");
builder.addTask("task 3");
builder.addTask("task 4");
builder.addResource("resource 3");
builder.addResource("resource 4");
Graph graph = builder.build();As soon as you have a jtwfg graph instance, you can use the jtwfg deadlock detector to find deadlocks:
DeadlockDetector deadlockDetector = new DeadlockDetector();
DeadlockAnalysisResult 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 jtrag/jtwfg model" as you update your domain model objects and check for deadlocks on the fly
Probably you want to keep the jtrag/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.
For simplicity and comfort, the jtrag/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.
-
At the moment jtrag/jtwfg support only simple, synchronous dependencies in graphs.
-
jtrag doesn’t fully encapsulate jtwfg. Therefore you need to program using the jtrag and the jtwfg API and understand both of them.
-
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/resources and run into performance/memory issues.
To use the jtrag library you need
-
Java 8 or later
There is a transitive dependency to the jtwfg library
Add the following dependency in your gradle build file:
repositories {
mavenCentral()
}
dependencies {
compile 'ch.petikoch.libs:jtrag:x.y.z' // replace x.y.z with the real version
// or "latest", for the braves:
//compile 'ch.petikoch.libs:jtrag:+'
}Add jtrag as dependency to your pom.xml:
<dependency>
<groupId>ch.petikoch.libs</groupId>
<artifactId>jtrag</artifactId>
<version>x.y.z</version> <!-- replace x.y.z with the real version -->
<!-- or latest release (not snapshot), for the braves
<version>RELEASE</version>
-->
</dependency>To run a build of the jtrag project on your machine, clone the git repo to your local machine and start the gradle based build using gradle’s gradlewrapper from the shell/command line:
> ./gradlew buildAfter I created first jtwfg, I had a use case involving tasks and resources.
Of course, this can be solved also with jtwfg: Every "task resource assignment graph" can be transformed into a "task wait for graph". Just use tasks for resources.
But the API isn’t very intuitive then. So I added the jtrag API on top of jtwfg, which does the "transformation" for you.
Best regards,
