Re2: Scheduler

2Andre:

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

It means quite nothing. O(140) is not worse then O(8), it's just the same... 
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...

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

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).

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

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.

With respect to Haiku community,
Dmitry Malyshev
                 


-----------------
Все блоги - ТУТ: http://blogs.tut.by/

-------------------------------------------------------------------------
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/
_______________________________________________
Open-beos-kernel-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/open-beos-kernel-devel