Re: Circular Convolution scheduler

[Richard B. Johnson]

On Tue, 21 Oct 2003, bill davidsen wrote:

> In article <20031016015105.27987.qmail@xxxxxxxxx>,
> Clayton Weaver <cgweav@xxxxxxxxx> wrote:
> |
> | > Ok, but what is "circular convolution scheduling"?
> |
> | It was a vague idea that I had for integrating our current,
> | more-or-less distributed system of priority scaling heuristics into a
> | single state model and applying them all at once to a scheduling
> | decision with a single matrix multiply. The motivation would be to
> | engineer out unexpected interactions between different parts of the
> | heuristic analyses that produce unpredicted (and potentially unwanted)
> | behavior in the scheduler.
> |
> | Ad hoc code is fast, but it depends on implementers being able to model
> | the implied state machine in their imagination, with the implementation
> | of it distributed across various code points in the scheduler. This
> | makes isolated simulation and verification (proof that the scheduler
> | does what we intend it to do) difficult, and we might get farther
> | faster by having an implementation of these scheduling-relevant runtime
> | heuristic analyses that allows us to reliably model scheduler state in
> | the abstract.
> |
> | I'm not saying that can't be done with the present system, it's just a
> | lot harder to be sure that your model really reflects what is happening
> | at runtime when you start with ad hoc code and try to model it than if
> | you start with a model of a set of state transitions that does what you
> | want and then implement/optimize the model.
> |
> | As other people have pointed out, runtime scheduler performance is the
> | trump card, and abstract verifiability that a scheduler (with heuristic
> | priority scaling) meets a specified set of state transition constraints
> | is not much help if you can't implement the model with code that
> | performs at least as well as a scheduler with ad-hoc heuristics pasted
> | in "wherever it looked convenient".
> |
> | (But you are not likely to need to revert stuff very often with a
> | heuristic-enhanced scheduler implemented from a verified formal model,
> | because you aren't guessing what a code change is going to do to the
> | state machine. You already know.)
>
> As I noted elsewhere, this depends on the past being a predictor of the
> future. I don't think we will see a major improvement in behaviour until
> disk, CPU, and VM management are all integrated. Given that the
> implementors don't agree on any one part of this I find that unlikely.
> At least the scheduler folks are all civil and acknowledge the good
> points of all work, resulting in progress even thought they are taking
> different approaches. With that model perhaps integration of all
> resource managers would be possible.
>
> On the other hand... the pissing contest with suspend makes good soap
> opera, but does not seem to have resulted in even one widely functional
> implementation. The phrase "does not play well with others" comes to
> mind.
>

Isn't scheduling something that's supposed to
be deterministic? I think your "nice marketing
name that sounds very technical" scheduler would
put policy in absolutely the wrong place.

We need less heuristics in the kernel, not more.
Already, we don't know anything about the time
necessary to guarantee much of anything. This
impacts data-base programs that are trying to
find safe intervals, guaranteed to be restartable.

Also, the "circular convolution theorem", from
which I would guess the name was scrounged, does
not relate in any imaginable way to kernel scheduling.
The name is a misnomer when used in this context.
That theorem states simply that what can be done
with a DFT can be undone using the same mechanism.


Cheers,
Dick Johnson
Penguin : Linux version 2.4.22 on an i686 machine (797.90 BogoMips).
            Note 96.31% of all statistics are fiction.


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/