The Scheduler Will Fitzgerald (11 Apr 2000 18:12 UTC)
Re: The Scheduler Marc Feeley (13 Apr 2000 14:16 UTC)
RE: The Scheduler Will Fitzgerald (13 Apr 2000 15:27 UTC)
Re: The Scheduler Marc Feeley (13 Apr 2000 16:56 UTC)
RE: The Scheduler Will Fitzgerald (13 Apr 2000 17:29 UTC)
Re: The Scheduler David Rush (14 Apr 2000 10:34 UTC)
RE: The Scheduler Will Fitzgerald (14 Apr 2000 13:42 UTC)
Re: The Scheduler Marc Feeley (14 Apr 2000 13:47 UTC)
Re: The Scheduler David Rush (14 Apr 2000 15:14 UTC)
Re: The Scheduler Mark K. Gardner (14 Apr 2000 16:09 UTC)
Re: The Scheduler David Rush (14 Apr 2000 16:31 UTC)
Re: The Scheduler Marc Feeley (15 Apr 2000 02:26 UTC)

Re: The Scheduler Marc Feeley 13 Apr 2000 14:16 UTC

> I'm curious why the scheduler wasn't made a data type, too, and, in
> particular, why the scheduling algorithm isn't changeable.

Well, a thread system could be built with a changeable scheduler but
this would have some consequences that I don't like:

1) The properties of the thread system will depend on the scheduler
   supplied by the user, so a library can't use threads because their
   semantics is not well defined.

2) The scheduler is a global resource, so different modules can't
   install their own scheduler.  So which module is responsible for
   installing the scheduler, and which scheduler do you get when the
   system starts?

3) Decoupling the thread primitives from the scheduler makes it harder
   to implement the scheduler.  For example if you want the "mutex-lock!"
   primitive to essentially do:

      if mutex is unlocked
        then lock it and return  ; note: atomic with test
        else call the scheduler method "block-on-mutex!" with the mutex
             (this method will block the current thread on the mutex)

   then you need to somehow guarantee that the program does not
   service preemption timer interrupts between the test "mutex is
   unlocked" and entry of the method "block-on-mutex!".  The clean
   solution would be to use an extra (lower-level) mutex which is
   locked on entry to "mutex-lock!" and unlocked somewhere inside
   "block-on-mutex!".  But this raises some issues:

     - who is responsible for implementing these lower-level mutexes?
     - are the lower-level mutexes powerful enough to work on multiprocessors?
     - is there a lower-level scheduler that blocks the current thread
       if the lower-level mutex is locked?  how does the lower-level
       scheduler interact with the higher-level scheduler?
     - if two schedulers are needed, then why not view SRFI-18 as
       specifying the lower-level mutexes and scheduler, and
       implement the higher-level scheduler on top of that?

4) I don't really anticipate very big savings (in development time) in
   a changeable scheduler.  You'll end up re-implementing most of the
   thread system because the thread primitives and the scheduler are
   closely coupled.  In any case, it should be relatively
   straightforward to modify the implementation I will supply with the
   SRFI (or the one supplied with your Scheme system if it is
   open-source) to get a specific semantics.

   By the way, I would like to see how you would structure a
   changeable scheduler that supports all the features proposed in

> Further (and relatedly), I'm curious why priority and quantum are
> defined as the only thread-related data that affect the scheduling. If
> the scheduling algorithm were separate, there might be other data it
> would want to consider (e.g., deadlines).

This is an open-ended issue.  I'm proposing a basic (but not minimal)
thread system with features similar to those found in mainstream
thread systems.  In fact the thread system I propose is more powerful
than most mainstream thread systems (for example few thread systems
support per thread quantums and absolute timeouts).  If there is a
need for other "non-mainstream" features, such as deadlines, then a
new SRFI can be proposed.  My hope is that it will be a pure extension
of SRFI-18 (that is why it is important to have a scheduling semantics
that is not too restrictive).