[haiku-development] Scheduler algorithm improvements
- From: Mikhail Panasyuk <otoko@xxxxxxxxx>
- To: haiku-development@xxxxxxxxxxxxx
- Date: Fri, 06 Nov 2009 18:03:35 +0300
Hello, All.
My name is Mikhail Panasyuk. I'm BeOS user and follower since late 1999 (R4.5).
I've been watching OpenBeOS/Haiku progress from the beginning but only recently
(when R1/alpha1 came out) actually began to do something myself to help this
project.
I've toyed with alpha for a month and a half, discovered and reported some
bugs. There are many more ready to report but for now I've dicided to make a
break and dig deeper into the system.
Lately I've been testing and comparing Haiku's scheduler to one of Zeta
(v1.51). To compare schedulers I came up with some sort of testing methodology
and wrote test-program based on it - SOS Tester - [S]imple [O]S [S]cheduler
Tester :) It really IS simple but useful enough.
Things I've discovered with this tool convinced me that NewOS/Haiku scheduler
in it's current state violates scheduling rule declared in Be Book / Be
Newsletter (see volume III issue 45). Which IMHO isn't good because at least
for R1 Haiku should be as BeOS-compartible as possible.
I haven't yet looked into actual Haiku scheduler sources but I had old (from
2003) sources of NewOS scheduler on my computer so I've studied them to find
out where could be the problem.
Actual scheduling algorithm turned out to be so plain simple that I immediately
came up with ideas on how to improve it. I had ideas but there were no tools to
test and refine them. Therefore I had to write one for myself and it's called,
guess what, SOS Emulator.
This piece of software does exactly what SOS Tester does but in a bit different
way. It tests not actual but emulated scheduler. Scheduler is implemented as
add-on and you can easily create new ones and test them too, compare with each
other in equal circumstances.
I've started with NewOS scheduler. After some experiments I've managed to more
or less precisely "emulate" Haiku, BeOS and Zeta (most unprecise and buggy)
scheduler behaviours too and came up with some improved version of BeOS
scheduler which I think is well suited to be the next Haiku scheduler replacing
existing one.
So....
I propose new Haiku scheduler algorithm.
There is an article (in Russian, sorry) which explains why's and how's, written
in Be Newsletter-style or at least I tried to make it so:
http://otoko.narod.ru/files/haiku/haiku_scheduler_part1.html
http://otoko.narod.ru/files/haiku/haiku_scheduler_part2.html
And programs:
http://otoko.narod.ru/files/haiku/sos_tools.zip
Even if you can't read the text you can look at the sources. "BeOSrt2"
scheduler add-on implements algorithm I propose.
Key features:
1) The likeliness for a thread to be scheduled increases with a factor of two
for such unit of priority.
2) This principle is true for both real-time and time-sharing threads. But
time-sharing threads won't be scheduled while there are real-time threads ready
to run.
3) There is concept of tunable (by user) "skip gaps" as an addition to the main
rule (1). If the gap between priorities is big enough scheduler ignores threads
of lower priorities when there are also threads of higher priorities ready to
run.
Skip gap setting is individual for each category - real-time and time-sharing.
With skip gap = 0 for real-time category you get behaviour of BeOS where
real-time thread with highest priority recieves all CPU time until it finishes
or blocks. skip gap = 0 for time-sharing threads is almost meaningless, but
other bigger values can prove themself more or less useful depending on
situation.
How to tune gaps:
Would be great to have separate kernel settings file and preflet like
'VirtualMemory' with two sliders and/or some checkboxes. Ability to change
settings "on the fly" - that would be the best. Default settings should imitate
BeOS behaviour.
Terminology:
Skip gap is a bit confusing term because for user it actually is "continue gap"
and maybe another term should be found to present this concept in preflet.
As an example there is also "BeOSrt3" version of this scheduler with slight
different main rule:
1) The likeliness for a thread to be scheduled increases less rapid than with a
factor of two for such unit of priority.
This allows low priority threads to get some CPU time share even when OS is
heavily loaded with high priority tasks. Therefore GUI may still response and
user may cancel high priority tasks they are out of control.
Actual Zeta scheduler differes from BeOS one in same way - it allows low
priority threads execute even when OS is heavily loaded with high priority
ones. Yes it violates the rule, but...
Anyway, all changes I propose are IMHO very easy to integrate and should be
added to Haiku in the nearest future (pre-R1/R1) not only because it's easy but
because they are needed now, improve (i think) performance and make Haiku more
BeOSish. What do you think?
Thanks!
PS. If you have better idea of what Haiku scheduler algorithm should be like
then you can implement it as SOS Emulator add-on and compare to others. Let the
best one became official :)
PPS. Just looked at Haiku sources, no significant changes since NewOS version.
Other related posts:
