[coyotos-dev] sleep capability

[Eric Northup]

Jonathan S. Shapiro wrote:
> On Tue, 2007-01-23 at 10:53 -0500, Eric Northup wrote:
>> Jonathan S. Shapiro wrote:
>> [...]
>>> Given (2), the only real solution is a deterministic scheduler. The
>>> problem with this is that real users will not accept a 90%+ reduction in
>>> effective computer speed.
>> Could you explain where this performance reduction comes from?  I agree
>> that forcing computation to be deterministic will slow it down, but I
>> didn't think it needed to be by that magnitude.
> 
> The 90% figure is made up, but here is the intuition.
> 
> You have some multithreaded thing that needs to run under a
> deterministic schedule. You have a multiprocessor. Several of your
> threads are eligible to run at any given time. Because of the
> determinism, the scheduler cannot permit them to use a second CPU, and
> cannot even permit them to use each other's slack time on the main CPU.

I agree that using the 2nd CPU is tricky, but you can schedule the other
threads on a single CPU.  Just change the definition of a time-slice
expiration to be a deterministic function of the computation, such as
number of instructions executed.  IIRC, most recent CPUs' performance
counter registers can be set to count the # of committed user-mode
instructions, and to trigger an interrupt when a counter hits a threshold.

If the kernel saves/restores the performance counters along w/the other
registers, then a user-mode reference monitor object can implement
deterministic multi-threading by multiplexing a single kernel thread
among a set of virtual thread-like objects.  The reference monitor sets
the retired instruction threshold at, say, 10*6 instructions.  When the
counter expires, the reference monitor handles the interrupt and
deterministically selects a new virtual thread and loads it into the
real thread.  It's also OK to switch (again, deterministically) between
virtual threads on any other deterministic event, such as exceptions /
capability invocation.

-Eric