Messages in this thread | | | Date | Thu, 16 Oct 2003 19:03:45 +1000 | From | Nick Piggin <> | Subject | Re: Circular Convolution scheduler |
| |
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@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |