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 15:13 UTC

Marc Feeley <xxxxxx@IRO.UMontreal.CA> writes:
> > Caveat lector:
  yadda yadda...
> The latest revision of SRFI-18 says:
>   Each thread has a "priority", which is an exact integer (where higher
>   numerical values mean higher priority) ...
> is this not clear?

It is clear. I was skimming, and other verbage led me to think it
worked the other way. No, I don't remember which bit, I'll check again
and let you know if it was more than just a brain fart.

> > 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.
>
> Yes, but this is much easier to implement if the scheduler has a
> builtin semantics for priority.

called (for lack of a better term) THREAD-PRIORITY>? :) Ultimately
it's going to boil down to a call to > in your code, right? Which in
an arbitrary Scheme might not even be atomic (due to unboxing,
etc. although this is something of a strawman). In some ways you have
*more* control over the semantics of THREAD-PRIORITY>? because you can
specify its constraints in the SRFI specification.

> > Which leads me to wonder if some form like
> > 	(without-scheduling <thunk>)
  ...
> This is not sufficient, because the actual exception handler you need
> depends on context.  In my example I was assuming that the exception
> handler exits the with-exception-handler, but this is not guaranteed
> since exception handlers can return (which is a good thing in
> general).

Fair enough. I blindly took your implementation as exemplary, not as
definitive. Nevertheless, it is very useful to be able to turn the
scheduler off, particularly for an RT system. Now hard-core RT people
won't be afraid to hack your implementation to bits to get the
behavior they want, so in a certain sense it doesn't matter. But I
gave you an example where the ability to turn the scheduler
off temporarily simplifies implementing priority-management
algorithms without hacking the scheduler code directly. The ability
seems likely to be advantageous in any priority-management algorithm,
I just haven't implemented that many.

> In my opinion, disabling scheduling with (without-scheduling <thunk>)
> or any other mechanism is not an option because the runtime system may
> depend critically on the thread system

Of course. But we're not talking about unbounded time in the
WITHOUT-SCHEDULING block. Now if someone *does* such a foolish thing
they get what they deserve, but it *is* useful to have some way that
users can interact with the *scheduler's* critical section (reordering
the priority tree) without having the rug yanked out from under
them. When I built the priority-inheritance mutexes on top of pSOS, we
(I had four people doing line-by-line reviews and simulations of my
code) ended up needing a system-wide lock just to make sure that we
didn't get the priorities wrong during mutex release. After consulting
with a pSOS expert, he suggested that we bring the code inside the
kernel so that we would be effectively running with the scheduler
blocked.

The need to temporarily stop the scheduler occurs. Doing so can have
significant consequences, but it would be a good thing to export that
ability to userland.

> Fundamentally, thread-priority>? needs to be a lower-level procedure
> that lives by different rules.  It should not be at the Scheme
> level.

Something makes me think that we are talking at cross-purposes
here. All that matters is that the rules for THREAD-PRIORITY>? be
documented. If the constraints for writing THREAD-PRIORITY>? can't be
satisfied in Scheme, then there's something wrong with Scheme that
should be addressed. I really don't get your objection here, people
do this sort of thing in C all the time.

> > 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.
>
> I'm not sure how much interesting work you'll be able to do without
> procedure call!

I can certainly tail-recursively look at global data structures and
other things to find out who *really* has the highest
priority. Can we make a distinction between primitive language
operations and procedures? Is it reasonable to expect + to be
implemented atomically? If so, then I can probably do some basic
arithmetic and comparisons. If not, you might well not be able to
implement your thread system at all. Remember, we're not talking about
serious amounts of work here; we're talking about figuring out if one
process should run preferentially to another one.

And finally, pushing THREAD-PRIORITY>? out to userland enables you to
punt on the open issue of priority aging in SRFI-18. All you need do
is document the constraints under which THREAD-PRIORITY>? must be
implemented.

david rush
--
As I've gained more experience with Perl it strikes me that it resembles
Lisp in many ways, albeit Lisp as channeled by an awk script on acid.
	-- Tim Moore (on comp.lang.lisp)