Re: Thoughts on Priorities and Quanta David Rush 11 Feb 2000 14:13 UTC

Marc Feeley <xxxxxx@IRO.UMontreal.CA> writes:
> 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.

Absolutely. This may take a bit of finess in the wording, or possibly
an alternative approach (see below).

> 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

I prefer this.

> > 1) Limiting the number of priority levels to 8 is a severe problem for
> > real-time systems. ... the consensus
> > is that 256 priorities are sufficient to virtually eliminate the
> > effect. Thus nearly all real-time operating systems have 256 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.

pSOS, an *extremely* common RTOS has (IIRC) 256. eCOS, the
Cygnus/RedHat RTOS has 64 priority levels, although the documentation
seems to indicate that this could be configured to be more.

> "Mark K. Gardner" <> writes:
> > 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.

Actually, I found this to be exceptionally difficult to cope with
under pSOS, at least when setting the priority of the currently
executing thread. I was attempting to implement priority inheritance
mutexes (before pSOS supported them) without running inside the kernel
or using a system-wide lock. The system-wide lock turned out to be
necessary because I had two tasks to perform, each of which could
cause a reschedule, before I could be truly said to have left the
critical section. If, after dropping my priority, I could have
finished my quantum, this would have been much easier. (Please don't
make me remember more details of this task, it was a year ago and its
largely leaked out of my brain)

So I would largely argue against rescheduling, except if a thread with
higher priority than when the current thread started becomes
runnable. OTOH, I am not a RT wizard, either, so this may be
unacceptable in that domain...

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

Snipped Marc Feeley ...

> > 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!!!

Actually, this is something that I was wondering about when I read the
SRFI doc. Are all the primitive pieces in place in order to completely
specify a thread SRFI? Was this why Marc proposed SRFI-12? It seems to
me that the only piece that is missing from Scheme to enable a threads
implementation is some way to arrange for the current continuation to
be passed to an end-of-quantum (actually a generalized interrupt)

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

Actually, I would very much like to see some sort of `pluggable'
scheduler interface. That plus the ability to handle interrupts
would provide a firm foundation for writing all sorts of portable
threading systems.

> > 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?

No. Well, yes. It should be a configurable parameter of the

> > 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.

Doesn't this either clutter up the thread table with threads that are
'babysitting' their children or make at least one thread have the
additional work of detecting when the program ends? OTOH, I am
probably thinking more in OS terms than I am in single program terms.

david rush
Not only does my left hand not know what the right is doing, but my
left brain doesn't know what the right brain is up to either...