Re: The Scheduler David Rush 14 Apr 2000 16:31 UTC

"Mark K. Gardner" <> writes:
> David Rush <> writes:
> > 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

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

Guilty. I forgot this requirement and opnly remembered it when I was
working out precisely *why* I had a hard time implementing them later.

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

This doesn't seem quite right, but I expect that you know better than
I. It seems like you need a priority stack per task/mutex? But that's
not particularly germane to SRFI-18.

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

Integer priority was *not* the difficulty. The difficulty was avoiding
a race condition on mutex release while trying to restore the original
thread priority. The result of the race was a incorrect restored
priority. If I'm totally confused, please excuse me, this *was* over a
year ago.

The point of my examples was to show the usefulness of
WITHOUT-SCHEDULING in implementing complex priority management

> I believe Marc's objection to parameterizing the scheduler with
> THREAD-PRIORITY>? (or allowing modular schedulers)

Aren't these two very different problems? THREAD-PRIORITY>? would be a
small subset of a modular scheduler. The idea is that the > comparison
is in there anyway, why not expose it? Then we get a number of
benefits to the specification (e.g. no need to say anything more about

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

I have no way to judge. I'm just (at the moment) a whingeing
user. Whichever way Marc goes with this, we'll be ahead of where we
are now.

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

Which I think is the point of having the scheduler parametric on the
priority comparison function. The SRFI can guarantee properties based
on the standard THREAD-PRIORITY>? but you're on yer own if you
implement yer own. Additionally, follow-on SRFIs could just
standardize THREAD-PRIORITY>? to get a new standardized thread system

david rush
I repeat myself when under stress. I repeat myself when under
stress. I repeat myself when under stress. I repeat myself when
under stress. I repeat myself when under stress. I repeat myself
when under stress. I repeat myself when under stress. I repeat