Re: Scheduler

On 10/18/07, Dima Malyshev <[email protected]> wrote:
> Hello, everybody!

Hi!

> What is the current progress in scheduler design? Is there any description
> of the final version of the algotithm Andre designed?

In... flux. I stumped upon a pretty irritating roadblock, namely that
the stride idea works great when the number of threads remain stable
for a long time (so it's a great, great strategy for a userland
scheduler built in on a simulation engine, for example), but on a
desktop OS, surprise, that's not a guarantee one can afford to have.

So... It hurts a little to admit, but I'm adopting a more CFS-like
approach, in that I'm using a more timeline-like data structure. I'm
still using exactly the same variables I was, just had to add one more
for comparison/goal checking purposes. I'm glad I rewrote everything
as templates, as it made things much easier to change/re-plug.

But of course, it was a change, and I'm still doing batteries of tests
to see what's really behind the curtains this time. Good news is that
now I don't need any heuristics to find the ideal stride anymore, this
thing sorts out itself. :)

They say the third time is a charm, right? :)

> The requested time complexity is O(1). But we have a limited N, so the
> asymptotic estimation can't provide us with good results. Formally, any
> algorithm including O(N*N) can be shown as O(1) because N is limited to
> 2^12.

Correct... But our N is limited *and* guaranteed to be low. The
original O(1) scheduler on Linux was O(140). Mine is around O(log
256), i.e., pretty close to O(8). And that's the really worst case,
"mega-boosting" and real-time threads included.

> I suggest including O(log(N)) algorithms in the candidate list, because they
> may be quite simple and provide a better speed in the mean. I have at least
> one in my mind...

Ok, have I fulfilled your request now? :)

> Also, as far as I know, improved scheduling techniques work with priority
> queues. And here we obtain Q - priority queues number. Are we to include Q
> into the algorithms complexity even if Q is also limited to 120?

Priority queues are not necessary here, as we are using per-priority
queues. See the difference? They're already "sorted out" by priority.

Actually, I just have to discuss my new approach with Axel a little
bit, and then I'm probably going to write another blog entry
documenting it.

> With respect to Haiku community,
> Dmitry Malyshev

Thanks for your input, Dmitry!



Knocking on wood (third time, third time, third time, be a charm!),
A.

-------------------------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc.
Still grepping through log files to find problems?  Stop.
Now Search log events and configuration files using AJAX and a browser.
Download your FREE copy of Splunk now >> http://get.splunk.com/