Re: Circular Convolution scheduler

[Nick Piggin]

Piet Delaney wrote:

> On Tue, 2003-10-14 at 03:28, Nick Piggin wrote:
>
> > Jamie Lokier wrote:
> >
> >
> > > Nick Piggin wrote:
> > >
> > >
> > > > I don't know anything about it, but I don't see what exactly you'd be
> > > > trying to predict: the kernel's scheduler _dictates_ scheduling behaviour,
> > > > obviously. Also, "best use of system resources" wrt scheduling is a big
> > > > ask considering there isn't one ideal scheduling pattern for all but the
> > > > most trivial loads, even on a single processor computer (fairness, latency,
> > > > priority, thoughput, etc). Its difficult to even say one pattern is better
> > > > than another.
> > > Hmm.  Prediction is potentially useful.
> > >
> > > Instead of an educated ad-hoc pile of heuristics for _dictating_
> > > scheduling behaviour, you can systematically analyse just what is it
> > > you're trying to achieve, and design a behaviour which achieves that
> > > as closely as possible.
> > Maybe, although as I said, I just don't know what exactly you would
> > predict and what the goals would be.
> >
> > And often you'll be left with an ad-hoc pile of heuristics driving
> > (or being driven by) your ad-hoc analysis / prediction thingy. Analysing
> > the end result becomes very difficult. See drivers/block/as-iosched.c :P
> >
> >
> > > This is where good predictors come in: you feed all the possible
> > > scheduling decisions at any point in time into the predictor, and use
> > > the output to decide which decision gave the most desired result -
> > > taking into account the likelihood of future behaviours.  Of course
> > > you have to optimise this calculation.
> > >
> > > This is classical control theory.  In practice it comes up with
> > > something like what we have already :)  But the design path is
> > > different, and if you're very thoroughly analytical about it, maybe
> > > there's a chance of avoiding weird corner behaviours that weren't
> > > intended.
>
> I was wondering about an application in user space that monitors
> various time series within the system. It would periodically 
> perform System Identification by placing the samples
> into a matrix and find the cross correlation coefficients by 
> minimizing the noise of their combination. This matrix would then
> by run in real time, perhaps in the kernel, to crank a Kalman Filter
> to predict the least squares best estimate for the values of the
> system time series. Here is where ad-hoc algorithms then use these
> precicted values to dynamically change the system behavior. I would
> expect the scheduler and pageout code could do better if they knew
> that the odds are high that in 10 seconds a huge demand is going
> to be made on the system memory for example.

I don't expect the scheduler would benefit at all from this sort of future
knowledge or knowledge of each task's patterns.

> Things like effects of lunch and dinner breaks, weekend, holidays, 
> stock market activity, number of servers up, could be combined with
> the servers time series. System Identification and Kalman filters 
> could be run in Long Term, Medium Term, and Sort Term time frames
> to predict in these various time frames; similar to how some commodity
> traders trade in multiple time frames.
>
> You can get very fancy and even add seasonal and non-linear support
> like Dr.Harvey did at the London School of Economics.

I fail to see how this would be simpler or more provably "right" than a
manually designed system.

I would rather not continue in this discussion as I'm not at all
qualified to give further input, and I'm just speculating. I'd love to
see a working implementation though.


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