Re: Circular Convolution scheduler

[bill davidsen]

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.


-- 
bill davidsen <davidsen@xxxxxxx>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.
-
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/