Scheduler design

[Jon Taylor]

Hi,

More design notes. This is a more-detailed writeup of my thoughts on
how to write a cleanly-designed virtual scheduler. In the context of
PerlOS, this means that everything dealing with scheduling priority,
from hard realtime critical section locks to soft lowest-priority
threading and everything in between, can be handled in one abstraction
system by using the concepts of abstract resource production and
consumption to specify constraints on the use of a consumable basis
of computing resources.

The basic scheduler is a simple FIFO which queues up code sections and
dequeues them into a set of managed runqueues. Subscheduling and
scheduling control is managed by queueing a scheduling FIFO code
section into the master scheduling FIFO and therefore taking a virtual
slice over an abstract underlying resource specification space. Top-
level scheduling maps over a "hard" underlying resource basis which is
measured directly instead of abstractly mapped and presumed be outside
the scope of this system.

Code sections specify scheduling policy based on consumption of
resources with scalar or typed weights, which are queued onto a FIFO
as they are acquired and popped off as they are finished being
consumed or go out of scope. Resource usage flow determines
scheduling policy based on an underlying scheduling motif. Resource
consumption motifs may be statically specified, pre-profiled before
execution or dynamically monitored and evaluated at runtime. Examples
of consumable resource types include: Hard time intervals as measured
by a TOD clock or equivalent, Units of exception handling related
consumable resources (execution time, IO buffer usage, cache
saturation, etc), soft scheduling intervals as specified by time
interval subdivisional policy, wait conditions such as event reception
or blocking function/method calls, or even generic resource types.
Code sections are specified by type, both implicitly as well as
explicitly: Standard linear/procedural code sections and subsections,
objects in abstraction, typed data structures, opaquely typed
executable resources (precompiled binaries, scripts in other
languages, etc), and any other type of resource consumption unit in
general.

The scheduler is the core of any OS, and without a good one
performance in the face of consistently high resource loads, transient
load spikes or special conditions will degrade in a markedly nonlinear
fashion. The keys to making this whole system tune up and perform
are 1) Good profile coverage of hard resource constraint spaces, 2)
Efficient dynamic JIT recompilation from perl source, and 3) Proper
segmentation of the underlying code base into schedulable sections
with associated profiling weights and types. Needless to say,
profiling tools to extract performance and scoping metadata as part of
the overall build and packaging process of any perl systems code will
be needed, as well as other types of tools such as code-from-template
generators, code repackaging and refactoring analysis tools, etc.

Jon