This page is part of the web mail archives of SRFI 18 from before July 7th, 2015. The new archives for SRFI 18 contain all messages, not just those from before July 7th, 2015.
> 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