Update
I received two more proposals I will comment soon.
Original
I closed the last episode with a little exercise for my readers: suggest me how to complete my requirements, namely by ensuring guaranteed ordering for the sequencer.
Alas, only two were skilled or brave enough to face the challenge and try an answer, and I thank them for that.
The two proposal were similar, but freeman did provide a gist, so let’s discuss it
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Show hidden characters
| using System; | |
| using System.Collections.Generic; | |
| using System.Threading; | |
| namespace Sequencer | |
| { | |
| using System.Collections.Concurrent; | |
| public class Sequencer | |
| { | |
| private readonly ConcurrentQueue<Action> _pendingTasks = new ConcurrentQueue<Action>(); | |
| private readonly object _running = new Object(); | |
| public void Dispatch(Action action) | |
| { | |
| // Queue the task | |
| _pendingTasks.Enqueue(action); | |
| // Schedule a processing run (may be a noop) | |
| ThreadPool.QueueUserWorkItem( x=> Run()); | |
| } | |
| // run when the pool has available cpu time for us. | |
| private void Run() | |
| { | |
| if (Monitor.TryEnter(_running)) | |
| { | |
| try | |
| { | |
| Action taskToRun; | |
| while (_pendingTasks.TryDequeue(out taskToRun)) | |
| { | |
| taskToRun(); | |
| } | |
| } | |
| finally | |
| { | |
| Monitor.Exit(_running); | |
| } | |
| } | |
| } | |
| } | |
| } |
Definitely, this will capture and secure the order of execution. And I like the smart use of TryEnter, allowing to get rid of the boolean used to store the state
But, and this is a big but, this solution violates another (implicit) requirement. I have to apologize for this one, as I failed to state it earlier.
But you know customers: they understand what they need when the development is over :-).
That requirement is fairness: fairness between Sequencer instances as well as fairness between Sequencers and other tasks. Fairness is to be understood as the guarantee that all submitted tasks will eventually executed,that they have equivalent access to execution units (i.e. cores), and with similar delays.
It means that no system can gain exclusive access to execution unit(s) ans that tasks are executed roughly in the order they are submitted.
This being defined, this solution is not fair. Can you tell me why?
Note: here is a gist for the first proposal
Many Cores
If a sequencer keeps dispatching actions, the Run method will never end. It is not fair because the sequencer will monopolize a ThreadPool thread. It is also a bad practice to execute long running tasks in the ThreadPool.
LikeLike
I tried to propose a fair implementation of the Sequencer on my github: https://github.com/tpierrain/SequencerAiiiight/blob/master/SequencerAiiiight/Sequencer.cs
There are still lots of improvements to make about this implementation (i.e. introducing a lock-free algorithm, using another underlying thread pool, etc), but this should answer Olivier’s concerns.
LikeLike
I slightly improved my first proposal : https://gist.github.com/ocoanet/e20aadf323663f56229f. I suppose it will have to be rewritten if more requirements are added. It would be a good idea to have a common test base, to validate our solutions and to benchmark them. Maybe we can put that in a github repo?
LikeLike
Before Cyrille buy a new laptop (the previous one seems to suffer toi much from his multithreading experimentation;-) and creates the open source project we talked about, I suggest that we continue what I already added on my github, with a first test, and our two Sequencer implementation. https://github.com/tpierrain/SequencerAiiiight/
LikeLike
BTW, I just changed my SequencerAiiiight repo into a new “Michonne” one on github. https://github.com/tpierrain/Michonne
As a consequence, my previous link is broken and the sequencer is now available here; https://github.com/tpierrain/Michonne/blob/master/Michonne/Sequencer.cs
LikeLike