[haiku-development] Re: Scheduler algorithm improvements

  • From: Mikhail Panasyuk <otoko@xxxxxxxxx>
  • To: haiku-development@xxxxxxxxxxxxx
  • Date: Mon, 09 Nov 2009 17:24:33 +0300

Hello. It's me again.


I modified Haiku scheduler and build several custom kernels to test. But when I 
moved from synthetic cases to tests involving real applications I realised 
system behave equally bad with any scheduler.


There is something wrong with the way you, Haiku developers, define priorities 
for some system services and apps. Critical for overall performance and 
responsiveness threads many other threads depend on have too low priorities.

I know that foundation for OS responsiveness in BeOS/Haiku lies in it's 
architecture and carefully selected priorities. UI drawing and mouse/keyboard 
events' handling have higher priorities than normal tasks, time-critical 
media-tasks are real-time and so on.

But in Haiku you can run some CPU-consuming B_NORMAL_PRIORITY (10) tasks and 
get slow UI + problems in MediaPlayer (frame drops, sound glitches, no sound or 
no video...). Something that just shouldn't happen in theory.

Same tasks with priority less than 10 don't cause these problems. Therefore 
there are 10-priority threads involved in handling user input and media-related 
tasks.

I did a research and found bottlenecks:

- kernel_team:
1. scsi scheduler

+ most other kernel_team threads with 10 priority in case there are _lots_ of 
10-priority tasks (see PS. section for details why)

- MediaPlayer:
1. media extractor thread
2. event queue runner
3. playback manager

Give them at least 11 priority if you want to improve audio/video playback. And 
make read buffers bigger. VLC and SoundPlay have no problems with playback even 
when system is heavily loaded with tasks, SoundPlay is the best performing one 
because it's "-loader" thread also has rather high priority (70).

- input_server:
1. input_server

Give it at least 11 if you want fast menus' and buttons' interaction with mouse 
and redraw.

- registrar:
1. _roster_thread_
2. timer_thread
3. message deliverer

Again at least 11 if you don't want UI and media-tasks hang up untill 
CPU-consuming tasks finish.

- Tracker:
1. Tracker

At least 11 if you want fast Desktop redraw and FS-navigation. Slow desktop 
redraw affects MediaPlayer.

- app_server:
1. picasso
2. screen manager

Become significant only when there are _lots_ of 10-priority tasks (again see 
PS. section). Anyway, giving them 11 will not harm.


With right priorities for system services I was able to run hundreds and 
thousands of B_NORMAL_PRIORITY threads without affecting UI responsiveness too 
much and with smooth sound/video playback. Now I can even listen to music in 
MediaPlayer and right-click-navigate FS while running 1000 Haiku3d's background 
with no prob :)


I think someone should draw thread-relation graph for all apps/services bundled 
with Haiku and analyse it. Find cases where high-priority threads depend on 
low-priority ones and optimise them - change priorities / increase or implement 
buffers / make architecture changes...


PS.

There is one important thing about BeOS/Haiku schedulers every developer must 
know.

All threads of same priority get same CPU time-share. For N > M: all threads of 
N priority together get time-share more than all threads of M priority 
together. 

But that doesn't necessary mean each thread on N priority will get more 
time-share each M priority thread gets!

Here is an example, Haiku r33922 kernel without modifications:

sos_tester -n 200 -r 2:1:2:1:* -p 46 50

Settings: work time 10000000 microseconds, 200 working threads.
Real work time 10000008 microseconds, 200 working threads.
Inaccuracy if SMP and more than one CPU enabled: 0.006130%.

  Number  Priority            Value    Share (%)
--------------------------------------------------
       0        46          4835229     0.147079
       1        46          3703110     0.112642
       2        48         65131242     1.981173
       3        48         72654122     2.210005
       4        50         13844670     0.421130
       5        50         12390692     0.376902
       6        50         19725203     0.600005
       7        50         13896422     0.422704
      ..        ..         ........     ........
     190        50         13735592     0.417812
     191        50         14598767     0.444068
     192        50         18272798     0.555825
     193        50         15049781     0.457787
     194        50         18316258     0.557147
     195        50         17669160     0.537463
     196        50         15843177     0.481920
     197        50         15430507     0.469368
     198        50         19961695     0.607198
     199        50         18180107     0.553006


Imagine you have B_NORMAL_PRIORITY kernel thread and another B_LOW_PRIORITY 
one. Now user launches _lots_ of apps, _lots_ of B_NORMAL_PRIORITY threads. All 
theese threads crawl and your kernel thread does too, it recieves even less CPU 
time than other B_LOW_PRIORITY one.

In original BeOS such situations appeared even more often, compare:


sos_emulator -n 200 -r 2:1:2:1:* -p 46 50 -a Haiku2

Settings: work time 10000000 microseconds, 200 working threads.
Using Haiku2 scheduler add-on.

  Task                  Time    Share (%)
-------------------------------------------
  Scheduler            11107     0.111258
  Others             9972000    99.888742

  Number  Priority            Value    Share (%)
--------------------------------------------------
       0        46                2     0.060168
       1        46                1     0.030084
       2        48               70     2.105897
       3        48               66     1.985560
       4        50               14     0.421179
       5        50               16     0.481348
       6        50               20     0.601685
       7        50               16     0.481348
      ..        ..               ..     ........
     190        50               17     0.511432
     191        50               15     0.451264
     192        50               17     0.511432
     193        50               13     0.391095
     194        50               15     0.451264
     195        50               14     0.421179
     196        50               19     0.571600
     197        50               13     0.391095
     198        50               14     0.421179
     199        50               18     0.541516


sos_emulator -n 200 -r 2:1:2:1:* -p 46 50 -a BeOS5 

Settings: work time 10000000 microseconds, 200 working threads.
Using BeOS5 scheduler add-on.

  Task                  Time    Share (%)
-------------------------------------------
  Scheduler            14217     0.142409
  Others             9969000    99.857591

  Number  Priority            Value    Share (%)
--------------------------------------------------
       0        46              113     3.400542
       1        46              112     3.370448
       2        48              309     9.298826
       3        48              308     9.268733
       4        50               13     0.391213
       5        50               13     0.391213
       6        50               13     0.391213
       7        50               13     0.391213
      ..        ..               ..     ........
     190        50               12     0.361119
     191        50               12     0.361119
     192        50               12     0.361119
     193        50               12     0.361119
     194        50               12     0.361119
     195        50               12     0.361119
     196        50               12     0.361119
     197        50               12     0.361119
     198        50               12     0.361119
     199        50               12     0.361119



Either scheduler should be somehow improved, or system should not use 
priorities which user applications may use. Or thread priorities should not be 
too close to each other in raw number. For now just keep in mind this problem 
exists.


Mikhail.

Other related posts: