3/7/2010

Concurrent execution of a dependency graph of threads

During the development phase of my diploma thesis I faced the probl^em of having a bunch of potentially concurrent operations where some dependencies had to be obeyed to finally evaluate to a valid XQuery. Basically this boils down to having a dependency graph and starting threads as they become ready (where the initial point of execution are jobs that don't have dependencies). Two minutes of (not so thorough) Google™ research made me wonder how I could be the only one on the planet to face this problem and soon I felt the itch to implement a suitable library...

The result is a small job scheduling library that takes a number of jobs, lets you define dependencies amongst them and executes them in concurrent threads where possible. The general concept is to start threads that don't have unresolved dependencies and check readiness every time a dependency finishes execution. That way you get dependency management for concurrent job execution without polling. The tricky part was to get it working without deadlocks.

Some interesting facts about the library:

• Easy to drop in: no dependencies
• Full control over thread management - culminates in fully serialized dependency execution if you don't create threads at all
• Supposed to be deadlock free by avoiding locking of more than one resource at once (Thanks applied CS 1)
• Licensed under the EPL :-)
• Source code available (check out the project page)