Add VCL scheduler documentation

Change-Id: Ifb2332b6d3c8bf472c684d3a79c861cc9035d246

1 files changed, 156 insertions, 0 deletions

diff --git a/vcl/README.scheduler b/vcl/README.scheduler
new file mode 100644
index 000000000000..1f2d617734a0
--- /dev/null
+++ b/vcl/README.scheduler
@@ -0,0 +1,156 @@
+= Introduction =
+
+The VCL scheduler handles LOs primary event queue. It is simple by design,
+currently just a single-linked list, processed in list-order by priority
+using round-robin for reoccuring tasks.
+
+The scheduler has the following behaviour:
+
+B.1. Tasks are scheduled just priority based
+B.2. Implicitly cooperative AKA non-preemptive
+B.3. It's not "fair" in any way (a consequence of B.2)
+B.4. Tasks are handled round-robin (per priority)
+B.5. Higher priorities have lower values
+B.6. A small set of priorities instead of an flexible value AKA int
+
+There are some consequences due to this design.
+
+C.1. Higher priorority tasks starve lower priority tasks
+     As long as a higher task is available, lower tasks are never run!
+     See Anti-pattern.
+
+C.2. Tasks should be split into sensible blocks
+     If this can't really be done, process pending tasks by calling
+     Application::Reschedule(). Or use a thread.
+
+C.3. This is not an OS scheduler
+     There is no real way to "fix" B.2. and B.3.
+     If you need to do an preemptive task, use a thread!
+     Otherwise mke your task suspendable and check SalInstance::AnyInput
+     or call Application::Reschedule regularly.
+
+
+= Driving the scheduler AKA the system timer =
+
+  1. There is just one system timer, which drives LO event loop
+  2. The timer has to run in the main window thread
+  3. The scheduler is run with the Solar mutex acquired
+  4. The system timer is a single-shot timer
+  5. The scheduler system event / message has a low system priority.
+     All system events should have a higher priority.
+
+Everytime a task is started, the scheduler timer is adjusted. When the timer
+fires, it posts an event to the system message queue. If the next most
+importent task is an Idle (AKA instant, 0ms timeout), the event is pushed to
+the back of the queue, so we don't starve system messages, otherwise to the
+front. This is especially importent to get a correct SalInstance::AnyInput
+handling, as this is used to suspend long background Idle tasks.
+
+Everytime the scheduler is invoked it searches for the next task to process,
+restarts the timer with the timeout for the next event and then invokes the
+task. After invoking the task and if the task is still active, it is pushed
+to the end of the queue and the timeout is eventually adjusted.
+
+
+= Locking =
+
+The locking is quite primitve: all interaction with internal Scheduler
+structures are locked. This includes the ImplSchedulerContext and the
+Task::mpSchedulerData, which is actually a part of the scheduler.
+Before invoking the task, we have to release the lock, so others can
+Start new Tasks.
+
+
+= Lifecycle / thread-safety of Scheduler-based objects =
+
+A scheduler object it thread-safe in the way, that it can be associated to
+any thread and any thread is free to call any functions on it. The owner must
+guarantee that the Invoke() function can be called, while the Scheduler object
+exists / is not disposed.
+
+
+= Anti-pattern: Dependencies via (fine grained) priorities =
+
+"Idle 1" should run before "Idle 2", therefore give "Idle 1" a higher priority
+then "Idle 2". This just works correct for low frequency idles, but otherwise
+always breaks!
+
+If you have some longer work - even if it can be split by into schedulable,
+smaller blocks - you normally don't want to schedule it with a non-default
+priority, as it starves all lower priority tasks. Even if a block was processed
+in "Idle 1", it is scheduled with the same (higher) priority again. Changing
+the "Idle" to a "Timer" also won't work, as this breaks the dependency.
+
+What is needed is task based dependency handling, so if "Task 1" is done, it
+has to start "Task 2" and if "Task 1" is started again, it has to stop
+"Task 2". This currently has to be done by the implementor, but this feature
+can be added to the scheduler reasonably.
+
+
+= Implementation details =
+
+== MacOS implementation details ==
+
+Generally the Scheduler is handled as expected. There is a workaround for a
+problem for pushing tasks to an empty queue, as [NSApp postEvent: ...
+atStart: NO] doesn't append the event, if the message queue is empty.
+
+Probably that's the reason, why some code comments spoke of lost events and
+there was some distinct additional event processing implemented.
+
+== Windows implementation details ==
+
+Posted or sent event messages often trigger processing of WndProc in
+PeekMessage, GetMessage or DispatchMessage, independently from the message to
+fetch, remove or dispatch ("During this call, the system delivers pending,
+nonqueued messages..."). Additionally messages have an inherited priority
+based on the function used to generate them. Even if WM_TIMER should have been
+the lowest prio, a posted WM_TIMER is processed with the prio of a posted
+message.
+
+Therefore the current solution always starts a (threaded) timer even for the
+instant Idles and syncs to this timer message in the main dispatch loop.
+Using SwitchToThread(), this seem to work reasonably well.
+
+== KDE implementation details ==
+
+This inplementation also works as intended. But there is a different Yield
+handling, because Qts QAbstractEventDispatcher::processEvents will allways
+process all pending events.
+
+
+= TODOs and ideas =
+
+== Task dependencies AKA children ==
+
+Every task can have a list of children / a child.
+
+ * When a task is stopped, the children are started.
+ * When a task is started, the children are stopped.
+
+This should be easy to implement.
+
+== Per priority time-sorted queues ==
+
+This would result in O(1) scheduler. It was used in the Linux kernel for some
+time (search Ingo Molinars O(1) scheduler). This can be a scheduling
+optimization, which would prevent walking longer event list. But probably the
+management overhead would be too large, as we have many one-shot events.
+
+To find the next task the scheduler just walks the (constant) list of priority
+queues and schedules the first ready event of any queue.
+
+The downside of this approach: Insert / Start / Reschedule(for "auto" tasks)
+now need O(log(n)) to find the position in the queue of the priority.
+
+== Always process all (higher priority) pending events ==
+
+Currently Application::Reschedule() processes a single event or "all" events,
+with "all" defined as "100 events" in most backends. This already is ignored
+by the KDE4 backend, as Qt defines its QAbstractEventDispatcher::processEvents
+processing all pending events (there are ways to skip event classes, but no
+easy way to process just a single event).
+
+Since the Scheduler is always handled by the system message queue, there is
+really no more reasoning to stop after 100 events to prevent LO Scheduler
+starvation.