[coyotos-dev] Scheduler design

[Jonathan S. Shapiro]

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
five levels:

  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
             missile.

  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
             queue.

  Normal     Things that run round-robin. No dynamic priority
             adjustment.

  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
     scheduling capability.

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
patented.

I am sure that significant changes are required for SMP, and especially
for NUMA-MP.

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.


shap