Scheduler: Change ClockService implementation to utilize the POSIX CLOCK_MONOTONIC...

[senf.git] / Scheduler / FIFORunner.cc

diff --git a/Scheduler/FIFORunner.cc b/Scheduler/FIFORunner.cc
index 8a1293b..169bcf8 100644 (file)
--- a/Scheduler/FIFORunner.cc
+++ b/Scheduler/FIFORunner.cc
@@ -32,6 +32,28 @@
 #define prefix_
 ///////////////////////////////cc.p////////////////////////////////////////
 
+// At the moment, the FIFORunner is not very efficient with many non-runnable tasks since the
+// complete list of tasks is traversed on each run().
+//
+// To optimize this, we woould need a way to find the relative ordering of two tasks in O(1) (at the
+// moment, this is an O)(N) operation by traversing the list).
+//
+// One idea is, to give each task an 'order' value. Whenever a task is added at the end, it's order
+// value is set to the order value of the last task + 1. Whenever the order value such added exceeds
+// some threshold (e.g. 2^31 -1 or some such), the task list is traversed from beginning to end to
+// assign new consecutive order values. This O(N) operation is so seldom, that it is amortized over
+// a very long time.
+//
+// With this value at hand, we can do several optimizations: One idea would be the following: The
+// runnable set always has two types of tasks: There are tasks, which are heavily active and are
+// signaled constantly and other tasks which lie dormant most of the time. Those dormant tasks will
+// end up at the beginning of the task queue.
+//
+// With the above defined 'ordering' field available, we can manage an iterator pointing to the
+// first and the last runnable task. This will often help a lot since the group of runnable tasks
+// will mostly be localized to the end of the queue. only occasionally one of the dormant tasks will
+// be runnable. This additional traversal time will be amortized over a larger time.
+
 prefix_ void senf::scheduler::FIFORunner::dequeue(TaskInfo * task)
 {
     TaskList::iterator i (TaskList::current(*task));