You may want to be familiar with Managing Concurrency With Trees[0] before reading this article.
We can easily see from the previous article that RootTask has no depencies, and that after RootTask executes RandomTask, OddJob, RedVendorFileDownload, and GreenVendorFileDownload are all eligible to run. We can express this in code like so in the IExecutable implementation constructors:
public RedVendorFileDownload()
{//Depends on nothing but root task
}
public RedVendorFileUnzip()
{
DependencyTypes.Add(typeof(RedVendorFileDownload));
}
public RedVendorFileImport()
{
DependencyTypes.Add(typeof(RedVendorFileUnzip));
}
… and so forth. There are other good ways to code this, for example creating a mechanims that would simple register the child types as Tree nodes rather than expressing the immediate prerequisite like this. I needed to refresh my mind (reaching back to college) on Tree mechanics, so why not add all of my IExecutable commands to a list and write an algorithm to seat them:
RootTask t = new RootTask();
TaskTree workTree = new TaskTree(t);
workTree.IsRoot = true;
//
OddJob oj = new OddJob();
RandomTask rt = new RandomTask();
RedVendorFileDownload redDown = new RedVendorFileDownload();
RedVendorFileUnzip redZip = new RedVendorFileUnzip();
RedVendorFileImport redImport = new RedVendorFileImport();
RedVendorPhotoDownload redPhoto = new RedVendorPhotoDownload();
GreenVendorFileDownload greenDown = new GreenVendorFileDownload();
GreenVendorFileImport greenImport = new GreenVendorFileImport();
GreenVendorFileUnzip greenUnzip = new GreenVendorFileUnzip();
List<IExecutable> exe = new List<IExecutable>();
exe.Add(redDown);
exe.Add(oj);
exe.Add(redImport);
exe.Add(redZip);
exe.Add(rt);
exe.Add(redPhoto);
exe.Add(greenDown);
exe.Add(greenImport);
exe.Add(greenUnzip);
RandomzeAndPrint(exe);
BuildTree(workTree, exe);
Console.WriteLine("==========Work Tree:==========");
Console.WriteLine(workTree.ToString());
RandomizeAndPrint() merely sorts the array by a random comparator so I could be sure I wasn’t cheating. BuildTree is slightly more interesting:
private static void BuildTree(TaskTree workTree, List<IExecutable> exe)
{
//We do this, which may take multiple iterations,
while (!exe.TrueForAll(new Predicate<IExecutable>(IsHome)))
{
foreach (IExecutable i in exe)
{
if (i.Home) { continue; }
//Tasks without dependencies can belong to the root node
if (i.DependencyInstances.IsNullOrEmpty() && i.DependencyTypes.IsNullOrEmpty())
{
i.Home = true;
Console.WriteLine("Adding {0} as child of {1}", i.FriendlyClassName(), workTree.Value.FriendlyClassName());
workTree.AddChild(new Tree<IExecutable>(i));
}
else
{
workTree.AddToTree(i);
}
}
}
}
The iteration is needed in case we have not yet added the parent of the current IExecutable. We could also do this using recursion and passing a smaller List<IExecutable> on each successive call to BuildTree. This method depends on the TrueForAll implementation of Tree<TNodeType>, which is as follows:
public bool TrueForAll(Predicate<TNodeType> pred)
{
bool allGood = TrueForAll(pred, this);
return allGood;
}
protected bool TrueForAll(Predicate<TNodeType> pred, Tree<TNodeType> tree)
{
bool trueForAll = true;
//Check root of current tree
if (!pred.Invoke(tree.Value))
{
return false;
}
foreach (Tree<TNodeType> subTree in tree.ChildNodes)
{
//Can only be true if everything is true
trueForAll = TrueForAll(pred, subTree);
if (!trueForAll)
{
return false;
}
}
return trueForAll;
}
The ToString() implementation on Tree<TNodeType> is overriden to print out each node value “beneath” it’s parent in an easy to read Console format. In order to make some of the next steps more readable, I’ve created a class TaskTree which extends Tree<IExecutable>.
Running my test program up to this point shows the randomly ordered List<IExecutable> being turned into a Tree<IExecutable> by the BuildTree method.
So, how do we put this together and actually run the IExecutable tasks in the order shown here while taking advantage of multi-core computing? The next article will contain the actual Scheduler algorithm and some performance metrics.