> There are a couple of items concerning priorities and quanta that I
> would like to see discussed. First, an admission of bias: I have been
> thoroughly indoctrinated in the real-time community. Thus the comments
> below deal with modifying the SRFI so that it does not prohibit the
> construction of real-time systems programmed in Scheme.

Thanks for your comments.

As I'm sure you know, real-time systems typically tradeoff efficiency
(i.e. speed/throughput) for guarantee of deadlines (i.e. maximum
latency).  As it stands, SRFI-18 can be implemented with simple and
efficient data structures (essentially double-ended-queues for mutex
and condition variables, and a small table of double-ended-queues
indexed by priority to represent the set of runnable threads).  The
more stringent real-time semantics you propose (i.e. 256 priorities,
and prioritized wakeups for mutexes and condition variables) would
require a much more complex and heavy implementation (basically
priority-queues everywhere, represented by heaps or leftist trees,
with O(log N) complexity for insert and delete operations).

>From my recent experiments with a Scheme implementation of leftist
trees, I would say that the overhead is probably between a factor of 5
and 10 for small N (N=10 in my experiments).  Since most of the thread
operations (such as starting or terminating a thread, thread
suspension or wakeup on a mutex, preemption of a thread, extraction of
the next runnable thread) are dominated by queue manipulations, we can
expect a considerable slowdown of these operations.  This can be bad
news for some applications that don't need real-time guarantees.

I think the right approach is to make sure SRFI-18 doesn't disallow a
more stringent real-time implementation, so that a future "real-time
thread" SRFI can extend SRFI-18's semantics and API.  For this reason
I am inclined to use an even weaker form of fairness:

  If threads A and B are blocked (on a mutex or condition variable)
  and A blocked before B, then:
    1) if A's priority is not less than B's priority, A will wakeup before B
    2) otherwise, A will wakeup before or after B

Also, I'll add a procedure to get the maximum priority:

   The call (thread-max-priority) returns a non-negative exact integer that
   indicates the maximum thread priority.

and yes, I mean for priorities to increase with higher integer values.

Concerning your specific comments:

> 1) Limiting the number of priority levels to 8 is a severe problem for
> real-time systems. Mapping otherwise distinct priorities, which have
> been established by fixed priority design guidelines, onto a limited
> set causes a potential reduction in the number of tasks which can meet
> their deadlines. The problem has been well studied and the consensus
> is that 256 priorities are sufficient to virtually eliminate the
> effect. Thus nearly all real-time operating systems have 256 priority
> levels.
>
> Is there any reason for limiting the number of priorities to 8? If
> there is, I suggest that we make 8 the minimum number of priority
> levels and add a function to obtain the maximum number of priority
> levels.

QNX, a well known real-time OS, has only 32 priorities, so 256 seems
way too much, even for a real-time system.  Note that the Java JDK
(not a real-time system) has 10 priorities.

> 3) In general, (hard) real-time tasks do not time share. Thus there
> needs to be another value added to the quantum domain specifying that
> the thread is not to be preempted, i.e., it is to run until it blocks,
> yields the processor, or terminates. As a by-product of defining this
> special value, it is no longer necessary to precisely know how quanta
> map onto real time. (Without the special value, a hard real-time task
> would need to specify a quantum that is guaranteed to be greater than
> its longest execution time before blocking, yielding, etc.)

How about specifying the quantum units to be microseconds, and you
just give a very large value.

> 5) thread-priority-set! should cause an immediate reschedule if the
> priority decreases. This seems logical but it is especially important
> for real-time systems as otherwise predictability will be lost.
>
> 6) Should thread-quantum-set! cause a reschedule if the amount of time
> executed so far exceeds the new quantum? (This is not a real-time
> issue if there is a quantum that signifies no time sharing.) For
> symmetry with the preceding comment, I suggest that this be the case
> but I don't really care as it too can be implemented in user code *if*
> there is a way to access the number of quanta used since beginning to
> run.

Immediate rescheduling is hard and expensive in a multiprocessor
context when the thread being modified is running on another
processor.  I'm not sure what is the right thing to do here...
should the current thread wait for the rescheduling to occur,
which might mean waiting for a large quantum?

> 7) I would suggest that thread-terminate! should always allow the
> current thread to finish the critical section if indeed it is in one.

I'm not sure what you mean by "the critical section".  Critical
sections are implemented, by the user, with calls to mutex-lock! and
mutex-unlock!, but this is not the only use of these primitives.  So
it is not the case that a thread is "in a critical section" if it owns
a lock (for example the end-mutex of a thread is owned by that thread
until it terminates).  It is also possible for a mutex to be unlocked
by a thread other than it's owner.

> 8) Perhaps an exception should be thrown when a thread is terminated
> (as opposed to when its thunk returns) so that the thread's resources
> can be properly deallocated.

It would be nice... but since there is no way to catch exceptions
(currently) how would you specify this!!!  I guess I could add
something like "an exception is raised in the target thread" (but
when??? and does the current thread wait until the exception is
raised), and some future "exception" SRFI can say exactly which form
this exception takes...

> 9) For good flexibility in scheduling, I like the QNX approach. Allow
> FIFO, round-robin and "adaptive priority" which may include aging.

This can be specified by a future "real-time threads" SRFI.

> 10) For predictability, I favor having thread quanta be in some
> sufficiently small unit of time like microseconds.

Agreed.  Should there be a maximum quantum?

> 11) I also like the idea that a program is the initial thread of
> execution and hence the parent of all other threads.

I like this too, mainly because it is more modular.  I'd like to hear
from other implementors on this issue because it requires a
substantial change in the Scheme runtime system.

Marc