[haiku-development] Re: Scheduler algorithm improvements

  • From: Mikhail Panasyuk <otoko@xxxxxxxxx>
  • To: haiku-development@xxxxxxxxxxxxx
  • Date: Fri, 13 Nov 2009 16:46:37 +0300

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

Just wanted to share my progress with others.

After some tinkering here is more fair approach to scheduling. Free from 
annoying "feature" of BeOS/Haiku schedulers I've mentioned earlier.

Real-world-like test case, note 'Each' field:

Settings: work time 10000000 microseconds, 1000 working threads.

  Task                  Time    Share (%)
-------------------------------------------
  Scheduler             5530     0.055391
  Others             9978000    99.944609

  Amount: Numbers       Priority       Quantums    Share (%)   Each* (%)
--------------------------------------------------------------------------
       2: 0 - 1         1                     1     0.030066    0.015033
      15: 2 - 16        5                     4     0.120265    0.008018
     479: 17 - 495      10                  610    18.340349    0.038289
       6: 496 - 501     12                   15     0.450992    0.075165
     478: 502 - 979     15                 2489    74.834636    0.156558
      20: 980 - 999     20                  207     6.223692    0.311185


Compare to original Haiku:

  Task                  Time    Share (%)
-------------------------------------------
  Scheduler             3554     0.035595
  Others             9981000    99.964405

  Amount: Numbers       Priority       Quantums    Share (%)   Each* (%)
--------------------------------------------------------------------------
       2: 0 - 1         1                     0     0.000000    0.000000
      15: 2 - 16        5                     0     0.000000    0.000000
     479: 17 - 495      10                    0     0.000000    0.000000
       6: 496 - 501     12                    5     0.150286    0.025048
     478: 502 - 979     15                  121     3.636910    0.007609
      20: 980 - 999     20                 3201    96.212804    4.810640


My algorithm accesses run queue much more often than Haiku simple scheduler so 
I had to optimize everything I could to reduce execution time. With little 
additional memory used current implementation performs well enough even in 
toughest conditions. Less than 0.1% CPU time share for worst cases with maximum 
allowed 4096 threads. For the most part it's ~0.05% which is very close to 
BeOS/Haiku schedulers.

But because I have all those optimizations there are rare cases (mostly 
non-real-world) when Haiku & BeOS schedulers are hundred times worse performers:


Using Haiku2 scheduler add-on.

  Task                  Time    Share (%)
-------------------------------------------
  Scheduler           244326     2.446851
  Others             9741000    97.553149

  Amount: Numbers       Priority       Quantums    Share (%)   Each* (%)
--------------------------------------------------------------------------
       2: 0 - 1         1                   123     3.788112    1.894056
    4093: 2 - 4094      99                 3124    96.211888    0.023506
    
    
Using BeOS5 scheduler add-on.

  Task                  Time    Share (%)
-------------------------------------------
  Scheduler           304736     3.051713
  Others             9681000    96.948287

  Amount: Numbers       Priority       Quantums    Share (%)   Each* (%)
--------------------------------------------------------------------------
       2: 0 - 1         1                     0     0.000000    0.000000
    4093: 2 - 4094      99                 3227   100.000000    0.024432
    
    
Using BeOSrt6 scheduler add-on.

  Task                  Time    Share (%)
-------------------------------------------
  Scheduler             4969     0.049760
  Others             9981000    99.950240

  Amount: Numbers       Priority       Quantums    Share (%)   Each* (%)
--------------------------------------------------------------------------
       2: 0 - 1         1                     2     0.060114    0.030057
    4093: 2 - 4094      99                 3325    99.939886    0.024417



After some additional testing and code cleanup will release for everyone to try.


Mikhail.

Other related posts: