David Rush <xxxxxx@bellsouth.net> writes:
> that you are meaning that you have some subset of the tasks in
> the system that need completion by a certain time,

Yes. Deadline driven scheduling of RT tasks gives the highest priority
to the task which has the earliest completion time.

> and that their priority should be dynamically raised each quanta
> that they are runnable but not actually running. Also that the
> priority of a deadlined task is never allowed to rise higher than
> that of a task with an earlier deadline.

Conceptually, hard RT systems do not have quanta. However, as long as
the partial ordering of tasks does not deviate from what it would be
if priorities were assigned according to earliest completion time, you
can do whatever you want to the actual priorities.

> Now in a hypothetical system with deadlines, I've got to assume that
> you have tasks with and without deadlines (Non-deadline tasks being
> dedicated to various housekeeping functions: logging, monitoring,
> etc). Non-deadlined tasks would be scheduled by normal priority, but
> deadlined tasks get the per-quantum magic.

Looking at it from the RT perspective (to which I have been thoroughly
indoctrinated ;-), non-RT tasks are tasks with deadlines at infinity.
Thus, a RT task will always preempt a non-RT task when scheduled
according to a deadline driven policy.

> Now if you try and map the scheduling of deadlined tasks into the
> priority scheme of non-deadlined tasks, you lose information in the
> scheduler, specifically the actual deadline (which serves as both a
> maximum priority limit and as strong heuristic of the needed
> priority).

Yes. The loss of information is what prevents the implementation of
deadline driven scheduling on a fixed priority scheduler in a straight
forward and efficient way.

Note though, that it is possible to implement deadline driven
scheduling in a fixed priority system by employing a scheduler task
which has the second highest priority in the system. The scheduler
task selects the (user) task with the earliest deadline and elevates
its priority to be the highest priority in the system, where upon it
preempts the scheduler thread and runs. If the average unit of work is
sufficiently large in relation to the (admittedly high) overhead of
the scheduler-as-task scheme, the system works pretty well for soft
RT. This scheme was implemented on top of Solaris by Hao-hua Chu at
the University of Illinois at Urbana-Champaign. For more details, see
<http://cairo.cs.uiuc.edu/papers/thesis.hao.ps>.

> Another case where this kind of thing arises is in the
> implementation of priority inheritance mutexes. In this case each
> mutex has an associated priority, to which any acquiring thread gets
> promoted (if a thread already has higher priority than the mutex it
> retains its priority). So a thread's effective priority is the
> maximum of its 'native' priority and the priorities of any mutexes
> it owns. Again, with a simple integer mapping you can make the right
> thing happen, but it becomes very difficult to get the right
> priority restored to a thread upon mutex release, especially without
> stopping the the scheduler entirely.

I'm not sure I followed you. First of all, if the mutex isn't assigned
the highest priority of any task that acquires it, the potential for
priority inversion (a low priority task executes while a higher
priority task is blocked) is still there. Second of all, a correct
implementation of priority inheritence raises the temporary priority
of the task holding the mutex each time a higher priority task
attempts to acquire the mutex. As soon as it releases the mutex, the
task's priority returns to the priority it had before it acquired the
mutex. Since a task can hold several mutexes, this requires a stack of
(increasing) priorities, with the priority at the bottom of the stack
being the task's original priority. I see nothing in the integer
implementation that would prevent the use of integer priorities. In
fact, priority inheritence is routinely done in fixed priority RT
systems.

> Which was Marc's main complaint about the THREAD-PRIORITY>?
> primitive. But the fundamental problem is that whenever you have a
> change in the priority levels of the tasks in a system the scheduler
> has to stop and get its head screwed back on straight. When all you
> have is a single integer affecting the task priority this doesn't
> seem to be much of a problem, but it is still the same problem.

But the creation of a task also causes a change in the priority
ordering of the tasks in the system. Changing the priority of an
existing task is conceptually no different than removing the task at
its current priority and creating it at its new priority (with out
loosing its state, of course). Thus the "stop" mechanism is already in
place.

I believe Marc's objection to parameterizing the scheduler with
THREAD-PRIORITY>? (or allowing modular schedulers) is that it is very
difficult to design the rest of the thread/mutex/condition variable
system abstractly enough to allow things to work without heavy
penalties in performance. (Depending on your definitions of
"difficult" and "performance", the design may be impossible.)
Furthermore, the properties of the system depend critically upon the
parameterizing comparison function hence it makes the use of
independently developed libraries which use threads problematic. Their
semantics will change depending on the comparision function you install.

> As you can tell, I am actually in favor of THREAD-PRIORITY>?
> (although I'm not implementing a scheduler around it at the moment).
> It nicely captures the essence of the variations in scheduling
> schemes. But regardless of that my experience in implementing
> priority-inheritance mutexes suggests that having the
> (without-scheduling <thunk>) form is going to be necessary for
> mapping complex priority schemes onto the integers anyway.

As you can tell from my original posting "Thoughts on Priorities and
Quanta" in the archive and from my comments here, I too would like to
see RT threads in Scheme. However, I feel that Marc has generally done
a good job of wording SRFI-18 such that it does not preclude the
development of a RT-thread SRFI in the future. The only limitation
that I still see is that the concept of integral priorities prevents
an efficient implementation of a deadline-driven scheduler.

Marc: What about weakening the definition of priority to allow other
comparable values such as real numbers or (more specifically) time
objects? With this, I am sure a RT-SRFI could be written without
having to undo parts of SRFI-18.

Mark

--
Mark K. Gardner
RADIANT Team
Network Engineering, CIC-5
Los Alamos National Laboratory
P.O. Box 1663, M.S. D451
Los Alamos, NM 87545
Email: xxxxxx@lanl.gov
Phone: 1-505-665-4953
--