extensibility to real-time multithreading Marc Feeley 22 Apr 2000 22:06 UTC
A major incompatibility between SRFI-18 as it currently stands and a
real-time multithreading system is that priorities are strictly under
the control of the user (i.e. thread-priority-set!). In a real-time
system, priority inheritance (or a similar dynamic priority mechanism)
is needed to avoid the priority inversion problem.
A brief explanation of the priority inversion problem: assume threads
T1 and T3 have priority 1 and 3 respectively, and that T1 owns a mutex
that T3 wants to lock, if a long-running thread T2 of priority 2
starts before T1 releases the mutex, T1 will be preempted by T2 and T3
will have to wait for a long time before it can lock the mutex... T3's
priority is effectively lowered to that of T1's. The priority
inheritance solution is to raise T1's priority to T3's for as long as
it is the owner of the mutex that T3 wants to lock. More formally,
the "effective priority" of a thread T is the maximum value between
its base priority and the priority of all threads that are blocked on
a mutex owned by T.
I see no easy way of relaxing the fairness constraints to accomodate
priority inheritance, while still giving a useful meaning to
priorities. But because I want SRFI-18 to be extensible to a
real-time SRFI, I see no other choice than to drop the concepts of
priority, quantum, preemption, and thread-yield!. These things will
be specified by a real-time multithreading SRFI (that I may or may not
Below are the changes I propose to the "fairness" section.
In various situations the scheduler must select one thread from a set
of threads (e.g. the next thread to run, the thread to wakeup when a
mutex unlocks or a condition variable is signaled). The constraints
on the selection process determine the scheduler's "fairness". For
example, the selection may depend on the order in which threads
blocked on a mutex, or on some "priority" attached to the threads.
Because we do not wish to preclude extensions to this SRFI (such as
for real-time multithreading) that require specific fairness
constraints, there are no fairness constraints imposed by this SRFI.
It is expected however that implementations of Scheme that support
this SRFI will document the fairness constraints they provide.
The following procedures are also dropped: