Monthly Archives: February 2012

Why I Think FIFO Is Not Always The Right Task Processing Strategy For CCR Ports

When a message is posted to a CCR port and there exists a receiver on that port that can receive that message then a task is created and queued for processing. This is great, and becomes a fact of life once you become accustomed to the way things are done in the CCR. But why must tasks always be queued? Should they always be queued? If they are not queued then how else would they be scheduled?

In this post we will start with an illustrative example of how FIFO task processing gone wrong. Then we will mention 2 other examples where FILO task processing is more well-suited for certain asynchronous tasks and conclude with ways of going-about performing FILO task processing.

An Illustrative Example

Take the following small console application for example:

class Program
{       

    static void Main(string[] args)
    {
       
using (var taskQueue = new DispatcherQueue
())
        {
           
var hungryGf = HungryGirlfriend
.Create(taskQueue);

            var responsePort = new HungryGirlfriendPort();

            hungryGf.Post(new WhatDoYouWantToEatMessage(responsePort));
            
           
Arbiter
.Activate(taskQueue,
                           
Arbiter
.Interleave(
                           
new TeardownReceiverGroup
(),
                           
new ExclusiveReceiverGroup
                                (
                                   
Arbiter.ReceiveWithIterator<FoodRequest>(true
,
                                                                             responsePort,
                                                                             FoodRequestHandler)
                                ),
                           
new ConcurrentReceiverGroup
()));
                            

            Console.ReadLine();
        }
    }
            
   
protected static IEnumerator<ITask> FoodRequestHandler(FoodRequest
request)
    {            
       
Console.WriteLine("Me: Ok, I’m Going out to get us {0} food"
,request.Cuisine);

        Thread.Sleep(2 * 1000);//Really, it takes me a lot longer than 1 sec. to go get food

        Console.WriteLine("Me: I Got us some {0} food", request.Cuisine);

        yield break;
    }        

}

 
At first glance, this appears to be a simple CCR simulation of asking your girlfriend what she wants for dinner then going out and getting it. When we look into the implementation of the girlfriend CCR service though, we see that things are not as simple when dealing with a woman as indecisive as my girlfriend.

      I kid-you-not when I say that every time I ask my girlfriend what she wants to eat she first claims she doesn’t care, then changes her mind 5 times before deciding what she actually wants to eat. In other words, if we were to implement the HungryGirlfriend CCR service to mimic my girlfriend, it would look something like this:

public class HungryGirlfriend : CcrServiceBase
{

    public static Port<WhatDoYouWantToEatMessage> Create(DispatcherQueue taskQueue)
    {
       
var girlfriend = new HungryGirlfriend
(taskQueue);

        girlfriend.Initialize();
       
return
girlfriend._inputPort;
    }

    protected HungryGirlfriend(DispatcherQueue taskQueue)
        :
base
(taskQueue)
    {

    }

    protected void Initialize()
    {
       
this._inputPort = new Port<WhatDoYouWantToEatMessage
>();
       
Arbiter.Activate(this
.TaskQueue,
           
Arbiter.Receive<WhatDoYouWantToEatMessage>(true
, _inputPort, WhatDoYouWanttoEatHandler));
    }

    Port<WhatDoYouWantToEatMessage> _inputPort = new Port<WhatDoYouWantToEatMessage>();

    Random _rand = new Random();

    int _randMax = Enum.GetNames(typeof(Cuisines)).Count();

    protected void WhatDoYouWanttoEatHandler(WhatDoYouWantToEatMessage msg)
    {
                    
       
Console.WriteLine("Girldfriend: I don’t care what we eat."
);

        for (int i = 0; i < 5; i++)
        {
           
var cuisine = (Cuisines
)_rand.Next(_randMax);
           
Console.WriteLine("Girldfriend: Wait, I changed my mind. I want {0} food"
, cuisine);
            msg.ResponsePort.Post(
new FoodRequest(cuisine));
        }
    }

}

Currently, when I run the example given above, I get the following sample output:

image

What’s wrong with this? Well, in this simulation, even though I know my girlfriend is going to change her mind about what she wants to eat, I run out and get the food she wants as soon as she says she wants it. As soon as I get back, I find out that she really wants something else, so I run out again. You can only imagine how tired and agitated I’d be upon returning the forth time just to find another task on the response port with another change in decision.

More importantly, as you can see from this example, all of the mind-changing responses have been posted by the time I go out the very first time, so why didn’t I just take the last response posted and go get Thai food? Well, because the the tasks were created by a DispatcherQueue that ensures First-In-First-Out (FIFO) processing of messages. In this case, the DispatcherQueue is preventing me from getting the most recent, and in this case the most pertinent, information when I need it. In general, the DispatcherQueue helps me keep the order of tasks straight throughout my program. In this case though, it is forcing me to process old information that I should be ignoring before I can get access to information I really care about.

If, instead of always using a DispatcherQueue I could use a ‘DispatcherStack’ then messages would be processed in a First-In-Last-Out (FILO) order and I would have saved myself a lot of time, money and frustration. Specifically, I would have gotten her last change of mind first, instead of last and I could have ignored the other messages by either completely discarding the messages off of the task stack or checking a timestamp property on the message itself to ensure that only the most up-to-date data was being used.

So What’s Your Point?

I’m NOT writing this blog post because I’m in a fight with my girlfriend (not yet at least, we’ll see after she reads this) nor am I using my .NET blog to vent about her. My goal was to use this simple, everyday example to illustrate a potential use case for FILO task processing.

Now, I realize that this tongue-and-cheek example probably does not fall under any of the intended CCR use cases so I’d like to explain when FILO task processing might be useful in more normal CCR scenarios.

First off, let’s consider a Robotics application. Let’s say that we have some CCR (or DSS) service that takes in sensor data and iteratively spits out successively better and better approximations of some quantity to a port. Maybe this service is implementing some kind of maximum likelihood or expectation-maximization algorithm where the series of approximations is monotonically improving. In this case then, we’d only ever be interested in the most recent approximation and would probably discard all previous estimates. FIFO task processing does not allow us to easily accomplish such a task and this can make a huge difference in the performance of our software.

First of all, if you are lucky enough to have an iterative algorithm that converges exponentially, or at least sufficiently fast, then the quality of the n+1^st estimate may be much, much better than that of the n^th iteration. Secondly, if estimates are created much faster than they can be processed, then several iterations may execute before one can be used. Why waste time processing bad, old estimates when a much better estimate has already been found?

What about in a business application? More and more people are recognizing the CCR and DSS platforms as generally useful for business application. I know my company has and we are now heavily invested in CCR and DSS for all of our real-time systems.

Well, let’s say you are creating a stock trading application where-in one CCR service gets stock prices and posts them to one or more ports for other CCR services to analyze and act on. You can imagine that almost all of the analysis-related CCR services will only be interested in the most recent stock price. However, other analysis services that analyze larger trends will not only be interested in the most recent price, but will be interested in the ten most recent prices but nothing more beyond the latest 10. So then, if while the 10 most recent stock prices are being processed, the price-getting service posts 30 new prices, then the analysis service is only going to want the 10 most recent prices and will ignore the other 20.

The overall point is that the order in which information is received and processed is extremely important. While I agree that most cases require FIFO task processing, I also think that by limiting ourselves to always processing information in the same order it is received we can put ourselves in positions where old (less pertinent or sometimes, simply wrong / useless) information is processed first. This may results in cases where we use outdated information from the past to make decisions for right now, or in the future. The need for FILO task processing in the CCR is about the need for more ways to decouple the receiving of messages from the processing of the messages.

So What Are You Going To Do About It?

Well, there are a couple of ways I could approach this problem. The first would be to create a series of utility CCR and/or DSS services whose only job is to receive messages, reverse their order and send them back out to whoever asks for them. This approach sounds simple but has two short-comings. The obvious one is performance and source complexity. There would always be a middle man between the sender of the message and the message receiver. While this can sometimes be a strong decouple and extensibility mechanism, I fear that is not the point here. Furthermore, posting then re-posting messages may not affect performance too much, but it almost certainly would increase code complexity. 

Secondly, though it sounds simple, creating such a CCR service gets tricky when you really sit down to create it. Creating a CCR service that is general enough to be reused in an arbitrary number of situations without causing memory leaks or surprises is not impossible but is not as simple as you may initially think.

The approach I’d like to take is a more CCR-centric approach. What I’d like to do is to extend the CCR itself by creating a custom Dispatcher that orders task for execution using a stack instead of a Queue. I’ll have to spend some time digging through the CCR docs and maybe a little quality time with Ildasm or reflector to see how realistic this goal really is.

though I’d really like to create a custom DispatcherStack, I am not sure it is going to be possible. Maybe there’s a different approach out there that someone knows about to help me? Maybe there’s s simple way to do it with ports that I don’t see? Basically, I think the need and utility for FILO task processing in the CCR is tremendous, I just don’t know how to achieve it yet. I’ll keep you all up-to-date with any progress I make.