Different Execution Patterns with WF (or, Going beyond Sequential and State Machine)
How do I do this?
A lot of times people get stuck with the impression that there are only two workflow models available: sequential and state machine. True, out of the box these are the two that are built in, but only because there are is a set of common problems that map nicely into their execution semantics. As a result of these two being "in the box," I often see people doing a lot of very unnatural things in order to fit their problem into a certain model.
The drawing above illustrates the flow of one such pattern. In this case, the customer wanted parallel execution with two branches ((1,3) and (2,5)). But, they had an additional factor that played in here, 4 could execute, but it could only execute when both 1 and 2 had completed. 4 didn't need to wait for 3 and 5 to finish, 3 and 5 could take a long period of time, so 4 could at least start once 1 and 2 were completed. Before we dive into a more simple solution, let's look at some of the ways they tried to solve the problem, in an attempt to use "what's in the box."
The "While-polling" approach
The basic idea behind this approach is that we will use a parallel activity, and in the third branch we will place a while loop that loops on the condition of "if activity x is done" with a brief delay activity in there so that we are not busy polling. What's the downside to this approach:
- The model is unnatural, and gets more awkward given the complexity of the process (what do we do if activity 7 has a dependency on 4 and 5)
- The polling and waiting is just not an efficient way to solve the problem
- This Is a lot to ask a developer to do in order to translate the representation she has in her head (first diagram, with the model we are forcing into).
The SynchScope approach
WF V1 does have the idea of synchronizing some execution by using the SynchronizationScope activity. The basic idea behind the SynchronizationScope is that one can specify a set of handles that the activity must be able to acquire before allowing it's contained activities to execute. This let's us serialize access and execution. We could use this to mimic some of the behavior that the polling is doing above. We will use sigma(x, y, z) to indicate the synchronization scope and it's handles (just because I don't get to use nearly as many Greek letters as I used to).
This should work, provided the synchronization scopes can obtain the handles in the "correct" or "intended" order. Again, the downside here is that this gets to be pretty complex, how do we model 4 having a dependency on 3 and 2? Well, our first synchronization scope now needs to extend to cover the whole left branch, and then it should work. For the simple case like the process map I drew at the beginning, this will probably work, but as the dependency map gets deeper, we are going to run into more problems trying to make this work.
Creating a New Execution Pattern
WF is intended to be a general purpose process engine, not just a sequential or state machine process engine. We can write our own process execution patterns by writing our own custom composite activity. Let's first describe what this needs to do:
Allow activities to be scheduled based on all of their dependent activities having executed.
- We will start by writing a custom activity that has a property for expressing dependencies. A more robust implementation would use attached properties to push those down to any contained activity
Analyze the list of dependencies to determine which activities we can start executing (perhaps in parallel)
When any activity completes, check where we are at and if any dependencies are now satisfied. If they are, schedule those for execution.
So, how do we go about doing this?
Create a simple activity with a "Preconditions" property
In the future, this will be any activity using an attached property, but I want to start small and focus on the execution logic. This one is a simple Activity with a "Preconditions" array of strings where the strings will be the names of the activities which must execute first:
public partial class SampleWithPreconProperty: Activity
{
public SampleWithPreconProperty()
{
InitializeComponent();
}
private string[] preconditions = new string[0];
public string[] Preconditions
{
get { return preconditions; }
set { preconditions = value; }
}
Create the PreConditionExecutor Activity
Let's first look at the declaration and the members:
[Designer(typeof(SequentialActivityDesigner),typeof(IDesigner))]
public partial class PreConditionExecutor : CompositeActivity
{
// this is a dictionary of the executed activities to be indexed via
// activity name
private Dictionary<string, bool> executedActivities = new Dictionary<string, bool>();
// this is a dictionary of activities marked to execute (so we don't
// try to schedule the same activity twice)
private Dictionary<string, bool> markedToExecuteActivities = new Dictionary<string, bool>();
// dependency maps
// currently dictionary<string, list<string>> that can be read as
// activity x has dependencies in list a, b, c
// A more sophisticated implementation will use a graph object to track
// execution paths and be able to check for completeness, loops, all
// that fun graph theory stuff I haven't thought about in a while
private Dictionary<string, List<string>> dependencyMap = new Dictionary<string, List<string>>();
We have three dictionaries, one to track which have completed, one for which ones are scheduled for execution, and one to map the dependencies. As noted in the comments, a directed graph would be a better representation of this so that we could do some more sophisticated analysis on it.
Now, let's look at the Execute method, the one that does all the work.
protected override ActivityExecutionStatus Execute(ActivityExecutionContext executionContext)
{
if (0 == Activities.Count)
{
return ActivityExecutionStatus.Closed;
}
// loop through the activities and mark those that have no preconditions
// as ok to execute and put those in the queue
// also generate the graph which will determine future activity execution.
foreach (Activity a in this.Activities)
{
// start with our basic activity
SampleWithPreconProperty preconActivity = a as SampleWithPreconProperty;
if (null == preconActivity)
{
throw new Exception("Not right now, we're not that fancy");
}
// construct the execution dictionary
executedActivities.Add(a.Name, false);
markedToExecuteActivities.Add(a.Name, false);
List<string> actDependencies = new List<string>();
if (null != preconActivity.Preconditions)
{
foreach (string s in preconActivity.Preconditions)
{
actDependencies.Add(s);
}
}
dependencyMap.Add(a.Name, actDependencies);
}
// now we have constructed our execution map and our dependency map
// let's do something with those, like find those activities with
// no dependencies and schedule those for execution.
foreach (Activity a in this.Activities)
{
if (0 == dependencyMap[a.Name].Count)
{
Activity executeThis = this.Activities[a.Name];
executeThis.Closed += currentlyExecutingActivity_Closed;
markedToExecuteActivities[a.Name] = true;
executionContext.ExecuteActivity(this.Activities[a.Name]);
Console.WriteLine("Scheduled: {0}", a.Name);
}
}
return ActivityExecutionStatus.Executing;
}
Basically, we first construct the execution tracking dictionaries, initializing those to false. We then create the dictionary of dependencies. We then loop through the activities and see if there are any that have no dependencies (there has to be one, this would be a good point to raise an exception if there isn't. We record in the dictionary that this one has been marked to execute and then we schedule it for execution (after hooking the Closed event so that we can do some more work later). So what happens when we close?
void currentlyExecutingActivity_Closed(object sender, ActivityExecutionStatusChangedEventArgs e)
{
e.Activity.Closed -= this.currentlyExecutingActivity_Closed;
if (this.ExecutionStatus == ActivityExecutionStatus.Canceling)
{
ActivityExecutionContext context = sender as ActivityExecutionContext;
context.CloseActivity();
}
else if (this.ExecutionStatus == ActivityExecutionStatus.Executing)
{
// set the Executed Dictionary
executedActivities[e.Activity.Name] = true;
if (executedActivities.ContainsValue(false) /* keep going */)
{
// find all the activities that contain the precondition
// and remove them, and then cycle through any that have 0
// preconditions (and have not already executed or are marked
// to execute
// who contains this precondition?
foreach (Activity a in this.Activities)
{
// filter out those activities executed or executing
if (!(executedActivities[a.Name] || markedToExecuteActivities[a.Name]))
{
if (dependencyMap[a.Name].Contains(e.Activity.Name))
{
// we found it, remove it
dependencyMap[a.Name].Remove(e.Activity.Name);
// if we now have no dependencies, let's schedule it
if (0 == dependencyMap[a.Name].Count)
{
a.Closed += currentlyExecutingActivity_Closed;
ActivityExecutionContext context = sender as ActivityExecutionContext;
markedToExecuteActivities[a.Name] = true;
context.ExecuteActivity(a);
Console.WriteLine("Scheduled: {0}", a.Name);
}
}
}
}
}
else //close activity
{
ActivityExecutionContext context = sender as ActivityExecutionContext;
context.CloseActivity();
}
}
}
There are a few lines of code here, but it's pretty simple what's going on.
- We remove the event handler
- If we're still executing, mark the list of activities appropriately
- Loop through and see if any of them have dependencies on the activity which just now completed being done
- If they do, remove that entry from the dependency list and check if we can run it (if the count == 0). If we can, schedule it, otherwise keep looping.
- If all the activities have completed (there is no false in the Executed list) then we will close out this activity.
To actually use this activity, we place it in the workflow, place a number of the child activity types within it (again, with the attached property, you could put nearly any activity in there) and specify the activities that it depends on. Since I haven't put a designer on it, I just use the SequenceDesigner. Here's what it looks like (this is like the graph I drew above but kicks off with the "one" activity executing first:
Where can we go from here
- Validation, remember all that fun graph theory stuff checking for cycles and completeness and no gaps. Yeah, we should probably wire some of that stuff up here to make sure we can actually execute this thing
- Analysis of this might be interesting, especially as the process gets more complex (identifying complex dependencies, places for optimization, capacity stuff)
- A designer to actually do all of this automatically. Right now, it is left as an exercise to the developer to express the dependencies by way of the properties. It would be nice to have a designer that would figure that out for you, and also validate so you don't try to do the impossible.
- Make this much more dynamic and pull in the preconditions and generate the context for the activities on the fly. This would be cool if you had a standard "approval" activity that you wanted to have a more configurable execution pattern. You could build the graph through the designer and then use that to drive the execution
I'm going to hold off on posting the code, as I've got a few of these and I'd like to come up with some way to put them out there that would make it easy to get to them and use them. You should be able to pretty easily construct your own activity based on the code presented here.
Comments
Anonymous
May 28, 2007
Siguiendo con el rescate de algunos de los posts publicados en nuestro blog , en este post voy a hacerAnonymous
June 14, 2007
Here's a comment from my initial post introducing the pageflow sample from wleong: NavigatorWorkflowAnonymous
June 26, 2007
The comment has been removedAnonymous
June 26, 2007
Temps near 100 F and 100% humidity make for some pretty uncomfortable days Windows Workflow SometimesAnonymous
July 06, 2007
Should you be looping through the Activities collection? foreach (Activity a in this.Activities) Shouldn't you use the EnabledActivities collection just in case there is a cancellation handler or fault handlers activity for the composite activity?Anonymous
July 18, 2007
Good catch mstiefel. I always forget about EnabledActivities when I put these things together.Anonymous
December 11, 2007
Temps near 100 F and 100% humidity make for some pretty uncomfortable days Windows Workflow Sometimes