Thoughts on Priorities and Quanta
Mark K. Gardner
(10 Feb 2000 00:39 UTC)
|
Re: Thoughts on Priorities and Quanta
Marc Feeley
(10 Feb 2000 16:27 UTC)
|
Re: Thoughts on Priorities and Quanta David Rush (11 Feb 2000 14:16 UTC)
|
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" <xxxxxx@asimov.lanl.gov> 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) handler. > > 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 scheduler. > > 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...