> If the THREAD-PRIORITY>? approach were adopted, then the 'fairness
> constraints' section remains the same, the 'priority aging' issue goes
> away (user x, want to implement priority aging? Just change
> THREAD-PRIORITY>? to reflect this), I could implement deadlines, etc.
>
> What do you think? Does this mess up the semantics too much? Make things
> too inefficient?

This has some coupling problems that are difficult to resolve.

For efficiency the scheduler maintains sets of threads (such as the
set of runnable threads, and the set of threads blocked on a given
mutex, and the set of threads blocked with a timeout) in a
data-structure ordered by priority (and insertion time and timeout)
where the highest priority thread can be accessed quickly.  My
implementation uses red-black trees, but leftist trees, plain binary
trees or a "heap" could be used.

When some scheduling information (such as the priority field of a
thread, or it's "deadline") is changed, it is important that the
red-black tree(s) containing the thread be reordered.  So at a minimum
you need another primitive such as (thread-reorder!  <thread>) to
notify the scheduler of a change of priority so it can reorder the
appropriate red-black trees, because it has no knowledge of the user's
implementation of priorities.  The user would use this primitive like
this, where t is a thread:

     (thread-deadline-set! t (foo x)) ; user defined deadline procedure
     (thread-reorder! t)

and define

     (define (thread-priority>? t1 t2)
       (< (thread-deadline t1)   ; note: bogus code... I don't fully
          (thread-deadline t2))) ;       understand what "deadline" means

Note that the scheduler has to be blocked out when the scheduler calls
thread-priority>? during a thread reordering (for example, no
preemption timer interrupts are allowed because it would require
modifying the red-black tree of runnable threads which might be in an
inconsistent state).  Let's assume the preemption timer interrupt is
not a problem because the scheduler disables these interrupts on entry
to the scheduler.  Nevertheless the procedure thread-priority>? has to
be written very specially.  It can't use scheduler related operations,
such as on mutexes.  It probably can't use I/O because mutexes are
used to protect the I/O buffers.  It probably can't allocate memory
(often multiprocessor memory allocators need to protect the memory
pool with a mutex) or do anything that might raise an exception.
Remember also that calling a procedure needs to allocate memory (for
the continuation frame and/or the rest parameter list).  Finally,
what is the value of (current-thread) when thread-priority>? is
called (note that thread reordering occurs at other points than
when the user calls thread-reorder!, for example when a timeout
occurs).  The value of (current-thread) is important to give
meaning to (current-exception-handler), (current-output-port), etc

Moreover, thread reordering has to be done promptly because the
red-black tree search/insertion/deletion operations assume that the
tree is in an ordered state.  But note that the preemption timer may
interrupt the computation just between the calls to
thread-deadline-set! and thread-reorder!.  So these operations must be
performed in a critical section that blocks out the scheduler, along
these lines:

     (thread-disable-scheduler!)
     (thread-deadline-set! t (foo x))
     (thread-reorder-and-enable-scheduler! t)

This bottleneck is going to be a problem in a multiprocessor because
all scheduler related operations, including on mutexes, are going
to have to busy wait for the duration of this critical section before
they can proceed.

Moreover, to be complete the code needs to prevent exceptions (raised
in (foo x)) from exiting the critical-section prematurely.  So you
really have to do something like this:

     (let ((eh (current-exception-handler)))
       (with-exception-handler
         (lambda (exc)
           (thread-reorder-and-enable-scheduler! t)
           (eh exc))
         (lambda ()
           (thread-disable-scheduler!)
           (thread-deadline-set! t (foo x))
           (thread-reorder-and-enable-scheduler! t))))

If this is not done then a missed thread-reorder-and-enable-scheduler!
will completely hang the system.

As you see I'm not very warm to your proposal!

Marc