[coyotos-dev] Scheduling, Intervals, and Time of Day

[Jonathan S. Shapiro]

Sam, Pierre, Valerio:

The discussion about sleep/sleepTill has become a problem. We are trying
to meet deadlines, we aren't ready to deal with this, and it is chewing
up a lot of time *because* we aren't ready to deal with this -- we're
being forced to speculate in order to answer you, and that isn't helping
anybody.

I'm going to try to state here what my actual assumptions and beliefs
are. I'll answer questions about this, but my real goal is to set this
aside for a bit longer. Eventually I want to ask you guys for help on
this, since it is important to you.

The specification of the kernel sleep key is a copy from EROS, and it is
completely wrong -- we haven't cleaned up the miscellaneous capability
specifications yet.


The baseline requirement for Coyotos is that the hardware must supply
some regular (or regularizable) interval timer. We don't specify the
rate of that timer, as we expect that it will be highly implementation
dependent.

  This means that sleep.sleep will ultimately be specified in ticks,
  not milliseconds, because the kernel has no way to compute
  milliseconds.

The baseline requirement for Coyotos does NOT include a time of day
counter.

  This means that the sleep.sleepTill operation will be removed.

Coyotos does not and cannot require time of day. The system has to run
in environments where no time of day information is available **at
all**. We need to specify how time of day works on systems that support
it, but where it should live in the spec is problematic.


The rough intention at the moment is as follows:

** Ticks:

The kernel makes use of a hardware-defined, implementation-dependent
tick counter for preemption. The specification does not say what the
rate of this tick counter is. It is required that the tick counter have
an "interrupt at count X" mechanism (or interrupt at zero if it is a
down-counter).

To save on kernel entries and interrupts, the kernel will irregularly
publish the value of this tick counter into a kernel-supported "time
page". At the moment my guess is that it will be updated whenever an
interrupt occurs, but this is not yet certain. In addition, it can be
updated explicitly via some (not yet specified) capability call. The
idea here is that the scheduler can directly influence how accurate the
time page is by scheduling interrupts at the required intervals.

** Scheduling:

Schedules are built by user-mode software and handed to the kernel
specified in ticks. Calibration of ticks is a matter for user-mode
software. The user mode software may know the answer a priori (as a
consequence of a fixed design) or it may calibrate against an external
source or it may calibrate against a hardware ToD clock that is not
known to the kernel.

The scheduling agent builds a scheduling table in terms of ticks. The
kernel implements preemption by arranging for interrupts when the
appropriate number of ticks has passed. This is the *only* handling of
ticks that the kernel performs.

At startup time, the kernel initially configures into a round-robin
scheduler with an unspecified (implementation-defined) slice (tick
count). The only purpose of this is to provide enough time-slicing to
let initialization occur -- eventually the scheduler is expected to
override this bootstrap policy.

** Time of Day:

Kernel has **zero** knowledge of time of day. This is a driver matter.
On platforms that supply a Time of Day clock, it is expected that the
time of day driver will initially obtain time of day from the hardware,
and then update it based on the kernel tick page (which is generally
more accurate than the hardware). This is consistent with most PC
implementations.

Deciding how/whether to report UTC, TAI, Mickey Mouse Standard Time, and
policy for regularizing relativistic distortion are all a matter for
user code.

** Sleep:

Because it is not specified in portable units, it is not expected that
most processes will use the kernel Sleep capability directly.
Unfortunately there is a nasty storage management problem here that we
need to resolve before we can specify that interface.


** Issues:

1. On multiprocessors, not all processors agree about the tick rate.

2. Implementing "sleep" and "sleepTill" in user mode requires per-client
state. This is bad, because one would really like this service to be
very low overhead. This was why this moved into the kernel in EROS.

One possibility is for the scheduler to advise the kernel about the
MS/tick conversion rate, and let the kernel implement sleep.sleep() in
milliseconds. Not clear what to do here.

3. The issue that we really need to resolve first is the kernel
scheduling policy.

-- 
Jonathan S. Shapiro, Ph.D.
Managing Director
The EROS Group, LLC
+1 443 927 1719 x5100