[coyotos-dev] Scheduler design
Jonathan S. Shapiro
shap at eros-os.org
Tue Nov 8 11:53:57 EST 2005
Unless there is a reason to change it, I intend to bring the EROS
scheduler forward into Coyotos unchanged. This note describes it. If
there is a better real-time scheduling technology that is not patent
encumbered, I would appreciate recommendations.
The current EROS scheduler is a two-level (or perhaps two and a half
level) scheduler. It operates as follows:
The top level scheduler is a fixed, static-priority scheduler having
Urgent Put things here for emergency response, but only
if they are so important that they should violate
existing real-time contracts.
Example: missile self-destruct code for an off-target
RealTime This is the static priority at which all real-time
processes run. A second-level scheduler determines
the preemption delay and the currently active ready
Normal Things that run round-robin. No dynamic priority
Idle What to do when there is nothing to do. Usually
the only processes here are the per-CPU idle processes.
Scheduling class exists purely to ensure that there
is always something to run.
Never Things that should not be dispatched at all.
Each of these scheduling classes has a ready queue that is dispatched in
round-robin fashion. In the case of the RealTime class, the underlying
real time scheduler operates by changing the ready queue pointer
whenever the current real time slice expires. The choice of round-robin
quanta will be alterable on a per-queue basis.
Currently, the real-time scheduler is a variant of the Mercer/Tokuda
capacity reserve scheduler. The variation is that it does not schedule
processes directly. The capacity reserves are used to select a ready
queue. Multiple processes can be ready on that queue, and are dispatched
in round-robin fashion when the relevant scheduler reserve is live.
I am fairly committed to three parts of this:
1. The idea that the outer schedule is static priority, having
approximately the format described. The "Normal" class could
certainly be made part of the real-time scheduler if desired.
2. The idea that the real-time scheduler activates queues rather
than processes. The idea is that multiple collaborating threads
can collectively occupy an activation without needing to create
a separate activation for each.
3. The idea that a scheduling class is a resource named by a
I am not committed to the choice of Mercer-Tokuda. In fact, I prefer the
tree scheduler designed by Jones et al., but I believe that it is
I am sure that significant changes are required for SMP, and especially
I have a strong, motivated, negative opinion about priority inheritance,
but I am not convinced that this opinion is correct.
For the moment, I can get away with deferring the entire choice of
real-time scheduler, but I would appreciate input on this if only to
allow forward time planning.
More information about the coyotos-dev