Introduction
In 2005, I wrote a toolkit for creating state machines with .NET. In Part II of my state machine articles, I used a simple version of a traffic light as a running example for how to implement a hierarchical state machine. My initial implementation was a bit naive in the way I handled timer events to signal light changes. Fortunately, a post from "leeloo999" was very helpful in pointing me towards a better way. The solution involved using an event queue that provides functionality for queueing timed events. I made a mental note of leeloo999's suggestion, but it wasn't until I was writing a much more complex state machine that his suggestion began to really make sense to me.
The event queue leeloo999 suggested I look at seems very promising. However, I can seldom resist the temptation to "roll my own," so I decided to write my own version; I wanted my class to compliment my DelegateQueue
class. This new class would be called DelegateScheduler
.
Before I could write it, however, I needed a priority queue for storing timed events in sorted order. This led me to explore adapting a skip list for use as a priority queue. Eventually, I wrote my PriorityQueue
class. With this class written, I was set to begin implementing my DelegateScheduler
class.
What is a Delegate Scheduler?
Many times we need an event to occur at specific intervals. Often, a simple timer will do the trick. We create a timer, initialize it to "tick" at a certain rate, and start it.. When timing events occur, we respond by carrying out a task. There are other situations in which our timing requirements are much more sophisticated. For example, we may need more than one timing event to occur, each at different intervals. Also, we may need a timing event to occur a specific number of times instead of indefinitely. You can accomplish these requirements with simple timers, but it takes quite a bit of setup. It would be nice to have a class that handles this for us. Enter the DelegateScheduler
: This class provides functionality for implementing a classic timed event queue. It lets you queue delegates to be invoked at specific intervals of time and a specific number of times.
Implementation
The DelegateScheduler
uses a priority queue for storing delegates in the order in which they will be invoked. When a delegate is added to a DelegateScheduler
, it is accompanied by the arguments that will be passed to it when it is invoked, the number of times to invoke it, and an interval in milliseconds that determines how often it will be invoked. All of this is stored in a Task
object and placed in the DelegateScheduler
's priority queue.
The Task Class
The Task
class is a private class belonging to the DelegateScheduler
class. It represents a scheduled event. Specifically, it represents a delegate, its arguments, and when and how many times the delegate will be invoked. It provides an implementation of the IComparable
interface so that priority queues can determine in what order to store their Task
s. Here is the Task
's CompareTo
implementation:
public int CompareTo(object obj)
{
Task t = obj as Task;
if(t == null)
{
throw new ArgumentException("obj is not the" +
" same type as this instance.");
}
return -nextTimeout.CompareTo(t.nextTimeout);
}
The Task
class uses the .NET Framework's DateTime
class to represent when the next timeout will occur, i.e. when the delegate it represents should be invoked. In fact, the Task
's CompareTo
method delegates the comparison its DateTime
object: nextTimeout
. If you look closely, however, you will see that a negative sign inverts the results of the comparison:
return -nextTimeout.CompareTo(t.nextTimeout);
Consider how the CompareTo
method is suppose to work:
- If this instance is less than obj, a value of less than zero is returned.
- If this instance is equal to obj, zero is returned.
- If this instance is greater than obj, a value of greater than zero is returned.
Priority queues store items in descending order. If item A has a greater value than item B, item A is stored before item B. That is to say, if item A has a greater priority value than item B, A is placed in the queue before B (some priority queues provide functionality to alter this behavior). With Task
objects, we want them placed in priority queues in ascending order; if Task
A's next timeout occurs earlier than Task
B's, A is placed in the queue before B. For this reason, it is necessary to invert the result of the DateTime
comparison.
Polling the Priority Queue
A DelegateScheduler
will periodically poll its priority queue to check the Task
at the head of the queue. If the value of its next timeout has passed, the DelegateScheduler
will dequeue it and tell it to invoke its delegate. If the Task
's count has been set to a finite value, it will decrement its count after invoking its delegate. The DelegateScheduler
checks a Task
's count and will place it back into the priority queue if the count is greater than zero or if the count value represents an infinite count.
After invoking its delegate, a Task
will update its next timeout value. It does so by adding the timeout value that was given to it when it was created to the time in which it invoked its delegate. It's possible that the next timeout has already passed. This can happen if the timeout is set to a value less than the rate at which a DelegateScheduler
polls its priority queue. In which case, a DelegateScheduler
will continue telling a Task
to invoke its delegate until its count reaches zero or the next timeout has not already expired.
Here is the DelegateScheduler
's code for polling its priority queue:
lock(queue.SyncRoot)
{
#region Guard
if(queue.Count == 0)
{
return;
}
#endregion
Task tk = (Task)queue.Peek();
object returnValue;
while(queue.Count > 0 && tk.NextTimeout <= e.SignalTime)
{
queue.Dequeue();
while((tk.Count == Infinite || tk.Count > 0) &&
tk.NextTimeout <= e.SignalTime)
{
try
{
Debug.WriteLine("Invoking delegate.");
Debug.WriteLine("Next timeout: " + tk.NextTimeout.ToString());
returnValue = tk.Invoke(e.SignalTime);
OnInvokeCompleted(
new InvokeCompletedEventArgs(
tk.Method,
tk.GetArgs(),
returnValue,
null));
}
catch(Exception ex)
{
OnInvokeCompleted(
new InvokeCompletedEventArgs(
tk.Method,
tk.GetArgs(),
null,
ex));
}
}
if(tk.Count == -1 || tk.Count > 0)
{
queue.Enqueue(tk);
}
if(queue.Count > 0)
{
tk = (Task)queue.Peek();
}
}
}
After a Task
has invoked its delegate, the DelegateScheduler
raises its InvokeCompleted
event. This event is accompanied by an InvokeCompletedEventArgs
object. This object includes information about the invocation such as the delegate that was invoked, its arguments, and its return value. If an exception was thrown, it will include that as well.
The DelegateScheduler
uses the System.Timers.Timer
for timing events. Each time its timer raises the Elapsed
event, the DelegateScheduler
responds by polling its priority queue. You can set the rate at which the polling takes place by setting the PollingInterval
property. This property gets its value from the timer's Interval
property.
Heavyweight vs. Lightweight
The DelegateScheduler
class is a lightweight version of a classic timed event queue. A heavyweight approach would have each task run in its own thread. When the time comes for a task to run, it signals the task to do its job. This is the approach I initially took. However, I decided that I wanted to lower the overhead of the class, so I have all of the Task
s invoke their delegates on the same thread. This thread is the one in which the System.Timers.Timer
Elapsed
event occurs. Because all of the delegates are invoked on the same thread, consideration must be taken to ensure that each delegate doesn't take too long to do its job. This is especially true if more than one Task
times out at the same time.
The DelegateScheduler
class has a SynchronizingObject
property that represents an ISynchronizeInvoke
object. The DelegateScheduler
uses this object to marshal delegate invocations and events. Specifically, it delegates the property's value to the System.Timers.Timer
's SynchronizingObject
property. This ensures that the timer's Elapsed
event is marshaled to the SyncrhonizingObject
's thread. When using a DelegateScheduler
in a Windows Form
, you initialize the SynchronizingObject
property to the Form
itself. Delegate invocations and events are marshaled to the Form
's thread.
Dependencies
The demo project download for this article includes the entire Sanford.Threading
namespace. This includes my DelegateQueue
class. This namespace is fairly small, and both the DelegateQueue
and the DelegateScheduler
use some of the same classes, so I decided to leave them together. You should know, however, that the Sanford.Threading
namespace depends on one of my other namespaces, Sanford.Collections
. In the latest update, I've included a copy of the release version of the Sanford.Collections
assembly. The projects in the solution that need the assembly are linked to it. I've done this in hopes that the download will compile "out of the box." This has been a source of frustration in the past, and I hope I've finally found a solution that works. If, however, you find that you need any of my assemblies, you can go here.
Conclusion
I hope you've found this article useful and informative, and I hope the code comes in handy if you ever need it. I look forward to your comments and suggestions. Take care.
History
- October 26, 2006 - First version completed.
- March 12, 2007 - Updated article and download.