[openbeos] Re: GSoC ticket #1069 (thread scheduler) application
- From: "André Braga" <meianoite@xxxxxxxxx>
- To: openbeos@xxxxxxxxxxxxx
- Date: Mon, 9 Apr 2007 06:03:07 -0300
On 4/8/07, Gustavo grieco <gustavo.grieco@xxxxxxxxx> wrote:
Im studing CC and i find this subject very interesting. Now we are
working with NachOS, could you tell me more about the O(1) scheduler ?
What do you think about a genetic algorithm for "auto tunning" the scheduler ?
(http://kerneltrap.org/node/4493)
Hi, Gustavo.
The current documentation on the scheduler design and prototype
implementation is in Portuguese. If I have the opportunity to work on
the GSoC, I'll definitely produce documentation in English, but for
the time being it's not a high priority task. Sorry.
Conceptually, an O(1) scheduler is not that difficult to understand.
You mostly have to find a data structure that's suitable for the task
of context switching; IOW, selecting a thread to schedule, allow it to
run, unschedule it, and selecting the next thread. The catch is when
you impose suitability rules to decide wether it is desirable, or even
allowable, for a given thread to be let run on a given moment. If you
reference your threads using a simple linked list, finding such
suitable (let's say suitability means being the highest priority
thread in a ready state) thread among all others naturally takes up to
'n' comparisons, 'n' being the number of threads. If you use a max
heap, you just take the root node. But then you'll have to maintain
the heap property, and that might mean a lot of housekeeping.
The Mach kernel was designed in such a way that *almost* solved the
O(1) problem: by having 32 global run queues and assigning threads to
those RQs based on their priorities. CPU affinity was also tackled by
having per-CPU local run queues. The problem with algorithmic
complexity on time is that every time you must do a "find the
maximum/minimum"-like search, it's guaranteed that you have at least
an O(n) complexity factor on your algorithm. When a you read on your
CS books something that states a given ordering algorithm has
O(n.logn) time complexity, it's in essence saying that every element
('n') must be compared k times to at least a multiple of log(n) (i.e.,
h.log(n)) elements, where k and h are constants. Quicksort, in a
nutshell, is a bunch of insertions on a binary tree, and thus share
the same properties of this operation, even if they seemingly serve
completely different purposes.
Sorry if it sounds like I'm just stating the blatantly obvious, but
since we're both students, I assumed you'd be more comfortable with
what we're both very familiar with, namely order of complexity theory.
Regarding genetic algorithms to auto-tune the scheduler, I must
confess that I *had* thought about that, but I ultimately believe (and
now I'm going to piss off a LOT of computer science luminaries) that
genetic algorithms are a red herring. They're great tools to do
exactly what is described on that link you posted, namely tuning
parameters to excel in a given workload, but they don't address the
fact that the base algorithm itself might not be the most suitable
one, nor do they solve the fact that workloads tend to change all the
time on general purpose operating systems, and IMHO caching "decent"
parameters to make up for this basic defficiency of using GAs in this
kind of environment is not really satisfactory. I enjoyed the critique
presented by the comments entitled "It isn't as cool as it looks",
"Broken concept" and "You take for granted that a" [sic].
If you really want to know my opinion regarding how would an "one size
fits all" solution look like, please check this post:
//www.freelists.org/archives/openbeos/03-2007/msg00214.html
Pursuing the perfect algorithm for all given workloads on an
uniprocessor system is a quixotesque task, IMVHO. There are better
windmills to fight out there. Besides, Haiku has a clear goal of
desktop responsiveness, so that's the kind of tuning we're interested
in.
That said, I would definitely like to experiment with *offline*
optimization of tunables using GAs once I'm set with an algorithm of
my liking; I even hinted at that on my GSoC application form. But I
can't really subscribe to bolting a GA runtime mutation engine onto
the Haiku kernel. IMO the overhead is just not worth it.
Cheers,
A.
Other related posts:
