The Scheduler Will Fitzgerald (11 Apr 2000 18:12 UTC)
Re: The Scheduler Marc Feeley (13 Apr 2000 14:16 UTC)
RE: The Scheduler Will Fitzgerald (13 Apr 2000 15:27 UTC)
Re: The Scheduler Marc Feeley (13 Apr 2000 16:56 UTC)
RE: The Scheduler Will Fitzgerald (13 Apr 2000 17:29 UTC)
Re: The Scheduler David Rush (14 Apr 2000 10:34 UTC)
RE: The Scheduler Will Fitzgerald (14 Apr 2000 13:42 UTC)
Re: The Scheduler Marc Feeley (14 Apr 2000 13:47 UTC)
Re: The Scheduler David Rush (14 Apr 2000 15:14 UTC)
Re: The Scheduler Mark K. Gardner (14 Apr 2000 16:09 UTC)
Re: The Scheduler David Rush (14 Apr 2000 16:31 UTC)
Re: The Scheduler Marc Feeley (15 Apr 2000 02:26 UTC)

Re: The Scheduler David Rush 14 Apr 2000 10:33 UTC

Caveat lector:

I've just realized that SRFI-18 uses Unix style priorities where lower
values get more CPU resource. I've (out of habit) used the opposite
language, where higher priorities get more CPU resource.

"Will Fitzgerald" <xxxxxx@neodesic.com> writes:
> Marc, thanks for the complete remarks. They were very helpful.

Agreed.

> One alternative I suggested is something like the following:
> (1) The type of the value of the priority field of a thread is left
> undefined.
> (2) The 'user' defines a THREAD-PRIORITY>? ordering procedure.
> (3) To change the priority, you need to use THREAD-PRIORITY-SET!
>
> (1) and (2) could default to values as in the proposal.
>
> But you say (2) can't be done, for the reasons you describe.

I didn't read it as *can't*, it sounded more like 'is a pain, and
dangerous, too'. But there are some good reasons for finding a less
painful and dangerous way to do the same things, of which

> Pity. (But
> I guess we can create an integer priority from anything I can dream up,
> including the mythical deadline).

is a good reason. Actually, we are discussing the heart of the first
bulleted open issue in the SRFI document. How shall dynamic priority
changes be addressed in the SRFI and in the scheduler?

Specifically, while I don't know precisely what you mean by scheduling
to deadlines either, I'll take a guess (based on my limited RT
experience) that you are meaning that you have some subset of the
tasks in the system that need completion by a certain 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.

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

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.

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.

Which leads me to wonder if some form like

	(without-scheduling <thunk>)

which encapsulates Marc's:

     (let ((eh (current-exception-handler)))
       (with-exception-handler
         (lambda (exc)
           (thread-reorder-and-enable-scheduler! t)
           (eh exc))
         (lambda ()
           <thunk>
           (thread-reorder-and-enable-scheduler! t))))

might be a useful adjunct to the SRFI. This is of course in addition
to Will Fitzgerald's suggestions concerning THREAD-PRIORITY>?. I think
that with these you'l have a system that can be adapted to RT systems
fairly easily, while ameliorating the difficulties in Marc's
post. Admittedly, all the difficulties don't go away; you still must
be careful in writing a custom THREAD-PRIORITY>?, but you have to be
really careful about anything relating to priorities in an RT
system. There is nothing in Marc's objections which doesn't apply in
the C world *and* which doesn't also apply to an attempt to map
everything onto integer priorities. The only exception is not being
able to make a procedure call, which  seems a harsh restriction, and
one that you wouldn't encounter in a C based solution.

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.

david rush
--
C makes it easy to shoot yourself in the foot, C++ makes it harder,
but when you do, it blows away your whole leg -- Bjarne Stroustrup