In my previous post, I mentioned that I had actually 4 implementations proposal and I commented two of them, which were within the drafted requirements but had an issue with fairness: in both cases, one could bypass the thread pool queue altogether.
Let’s turn our attention to the other two, which are interesting because they share a common issue while having radically different approach.
C#, very short one
|public class Sequencer|
|private readonly object _lock = new object();|
|private Task _task = Task.FromResult(0);|
|public void Dispatch(Action action)|
|_task = _task.ContinueWith(_ => action());|
Clearly, the .Net version benefits from the TPL features. That being said, they are actually very close as they share the same algorithm: ordering is secured by creating a private queue, and non concurrency is ensured by making sure at most one task is enqueued or executing in the .net threadpool.
Contract is fulfilled, albeit with a steep price in terms of performance, or more precisely latency. As a task is actually dispatched only after the previous one have been executed, there is a minimum delay between two tasks. So, once again there is a fairness issue. It is obvious that non sequenced tasks would be executed faster than sequenced ones.
What should be the proper algorithm
For order guarantee: you MUST capture the order when the tasks is submitted. IMO the best approach is to queue the task into a sequencer’s queue (hence private). Then you submit to the threadpool a task that will ensure sequenced execution. That task , when executed, will need to:
- Pop the next task to be executed
- Push it in the execution queue
- If no execution is in progress start the execution, otherwise end here
- Execution: while there is task in the execution queue, pop them and execute them
That’s it. I am not saying this is the most efficient implementation you can achieve (far from it), but those are the steps that must be executed to achieve the contract.
- Capture the order on submission
- Ensure non concurrence
- Ensure tasks are executed roughly as fast as they are poped from the pool
- Allow tasks to be delayed only to prevent concurrent execution and executed as soon as it is possible
Guys, you have submitted excellent work so far, now I ask you to take those comments into account and submit improved version.