1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
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 reoccurring 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 priority 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 a preemptive task, use a thread!
Otherwise make 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.
Every time 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
important 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 important to get a correct SalInstance::AnyInput
handling, as this is used to suspend long background Idle tasks.
Every time 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 primitive: 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 implementation also works as intended. But there is a different Yield
handling, because Qts QAbstractEventDispatcher::processEvents will always
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 Molnar's 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.
|
