Re: Re2: Scheduler

Hi,

On 10/19/07, Dima Malyshev <[email protected]> wrote:
> 2Andre:
[snip]
> It means quite nothing. O(140) is not worse then O(8), it's just the same...

I don't quite agree with that, but I see what you mean.

> The only one way I see is to make benchmarks, lots of benchmarks. The
> question is: how to get the mean time, e.g. how to test algorithms in the
> whole set of situations and how to weight the results...

For the time being I'm using synthetic benchmarks in userland. I may
then use stuff like rtdsc on processors I'm sure won't suffer some
"SpeedStep effect", i.e., have dynamic clock management.

> It's not clear for me. As far as I understood, one of your proposals was to
> work with queues at first, managing 4 values:
> (PQ, offset, priority, # of threads)
> So choosing the right queue takes O(f(Q)) operations. I just wanted to
> notice that we can't ignore Q either than N (assuming they are limited).

That's perfectly correct. The one thing you didn't notice is that the
technique I'm using makes Q (the number of queues) the variable of
interest, not N (which would be the number of threads). Our expected
number of queues is no larger than 8, the maximum number of "regular"
queues (i.e., the number of priorities defined by the API) is 120, but
in practice 100, since the 20 remaining priorities are real-time and
are dealt with separately. Considering my intention to implement
boosting based on which semaphores are visited (which for the time
being Axel has vetoed), the actual number of queues in the system
shouldn't be more than twice that, so max(Q) = 200, now. Which is
closer to 256 than to 128. Hence my suggestion that the complexity is
therefore bound by O(log(256)) == O(8), since the operation in
question is a binary search on a balanced (red-black) tree.

But that was the original, stride-based algorithm. The new one should
be even more lightweight still. :)

> Alright. Though there is no point for me to develop a Sheduler from scratch
> (as you are so close to the finish), I want to look deeply in the algorithm
> you designed (after your discussion with Axel). If you make a detailed
> description of the algorithm I'll be able to make some optimization
> proposals with a clear mind that can help.

BTW, I'm also laying a framework for "pluggable schedulers" of sorts,
by making clear distinctions between policy and mechanism, so you
might want to check it out before writing actual code. For now, work
on your algorithmic ideas, not the implementation.


Once again, thanks!
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/