lkml.org 
[lkml]   [2004]   [Mar]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
Subject[PATCH]Staircase scheduler - experimental
This is a rewrite of the scheduler policy for 2.6, based on the current
O(1) scheduler.

Aims:

- Making renicing processes actually matter for CPU distribution
(nice 0 gets 20 times what nice +20 gets)
- Interactive by design rather than have complicated interactivity algorithm
bolted onto an existing design
- Good scalability.
- Simple predictable design.
- Maintain appropriate cpu distribution and fairness.
- Low scheduling latency for normal policy tasks.
- Low overhead.

Summary of design:
A descending multilevel single runqueue per cpu with deadline elevation of
priorities.

Details:
This patch takes advantage of the existing infrastructure but has no expired
array. Real time tasks are treated the same as the current fixed priority &
timeslice system. The details are in the management of normal policy tasks.

Normal policy tasks have a dynamic priority that drops by one every
RR_INTERVAL which equals 10ms * num_online_cpus(). Once they drop to zero
they are requeued with 2 intervals at a lower priority and then drop back to
one interval. If they drop to zero they are requeued with 3 intervals lower
priority and so on. Every time a task sleeps it moves back up one priority.
The sub-jiffy case is handled specially to prevent it fooling this system.

Use a fixed font to see clearly:

ie
RR_INTERVALs nice 0 task
20<-------------->40 PRI
11111111111111111111
02111111111111111111
00311111111111111111
and so on
nice +10 task
30<---->40 PRI
1111111111
0211111111
0031111111
and so on
This is how cpu distribution is kept proportional while optimising latency
for interactive tasks.

The patch was made to be added to the sched_domains infrastructure since this
is likely to be merged with mainline so all comparisons are made to a kernel
with sched_domains patched in.

Subjective Performance:

For the end desktop user they will find this performs much like the
mainline 2.6 scheduler over a wide range of loads apart from the fact that
applications start faster with this.

Some applications that misbehave with 2.6 mainline will behave better using
less cpu time. At extreme loads the stock 2.6 scheduler feels better by
being too unfair on cpu bound tasks which this one does not. Nice has more
predictable and larger effects on cpu distribution (nice 0 gets 20 times
what nice +20 gets).

Objective Performance:

Note that there has been no "tuning" put into this scheduler at all; the cpu
balancing on smp and so on is that used in mainline/sched_domains.

The executive summary is that in most cases smp performance is equivalent and
occasionally better, while maintaining interactivity and improving
responsiveness. Detailed summary of benchmarks found at the end of the mail.

Known Problems:
There is one minor interactivity issue I encountered during testing that I
need to examine and adddress when time permits. There are no known bugs
per se.

Future Direction:
I will be departing shortly for extended leave and will be unable to do any
further coding till the end of May. This release, therefore, is to make the
project known and to receive some testing in the interim.

Download:
http://ck.kolivas.org/patches/2.6/2.6.4/experimental/staircase/

Three patches are currently available:
2.6.4-staircase5:
A full patch against 2.6.4 which includes current sched_domains
2.6.4.domains2-staircase5:
A patch against sched_domains which shows more clearly only my changes
2.6.5-rc2-mm2-stair
An incremental patch against 2.6.5-rc2-mm2.

Testing:
Please feel free to test and use this patch extensively. I will be able
to respond to emails only intermittently while away but unable to do any
coding.

Thanks:
Zwane Mwaikambo and William Lee Irwin III for help and ideas.


Con Kolivas
25th March 2004

-----------
Detailed benchmark results:
2.6.4 is 2.6.4 patched with latest sched-domains
2.6.4-s is 2.6.4 with sched-domains patched with staircase deadline sched
Reaim 8x (higher is better)
---------------------------
2.6.4 http://khack.osdl.org/stp/290462/
Peak load Test: Maximum Jobs per Minute 7482.37 (average of 3 runs)
Quick Convergence Test: Maximum Jobs per Minute 7351.78 (average of 3 runs)

2.6.4-s http://khack.osdl.org/stp/290536/
Peak load Test: Maximum Jobs per Minute 9492.30 (average of 3 runs)
Quick Convergence Test: Maximum Jobs per Minute 9037.34 (average of 3 runs)

kernbench 16x (lower is better)
-------------------------------
2.6.4 http://www.osdl.org/projects/kernbench/results/results.2.6.4-domains
Average Half Load Run:
Elapsed Time 112.084
Average Optimum Load Run:
Elapsed Time 79.07
Average Maximum Load Run:
Elapsed Time 80.926

2.6.4-s http://www.osdl.org/projects/kernbench/results/results.2.6.4-s4.2
Average Half Load -j 8 Run:
Elapsed Time 106.59
Average Optimal -j 64 Load Run:
Elapsed Time 78.6866
Average Maximal -j Load Run:
Elapsed Time 83.2134

Hackbench 8x (lower is better)
------------------------------
2.6.4 http://khack.osdl.org/stp/290460/
# Processes | Ave Time(sec)
20 1.85
40 2.7742
60 3.754
80 4.8018
100 5.8758
2.6.4-s http://khack.osdl.org/stp/290542/
# Processes | Ave Time(sec)
20 1.8894
40 2.6808
60 3.51853333333333
80 4.40575
100 5.365

Contest 1x (generally lower is better see http://contest.kolivas.org)
---------------------------------------------------------------------
The osdl automated contest runs have been playing up and the averages posted
here are wrong so I've tried to extract the meaningful runs from the logs
and distill them here:
2.6.4 http://khack.osdl.org/stp/290453/
no_load:
Kernel[runs] Time CPU% Loads LCPU% Ratio
2.6.4 4 103 96.1 0.0 0.0 1.00
cacherun:
2.6.4 4 100 99.0 0.0 0.0 0.97
process_load:
2.6.4 4 166 59.6 140.2 38.0 1.61
ctar_load:
2.6.4 4 148 68.2 17.2 17.6 1.44
xtar_load:
2.6.4 4 131 78.6 9.0 15.2 1.27
io_load:
2.6.4 4 147 70.7 36.2 20.4 1.43
io_other:
2.6.4 4 143 72.0 31.3 17.5 1.39
read_load:
2.6.4 3 140 XX 98.3 XX 1.36
list_load:
2.6.4 3 120 XX 2 XX 1.16
mem_load:
2.6.4 3 153 XX 121 XX 1.49

2.6.4-s http://khack.osdl.org/stp/290538/
no_load:
Kernel[runs] Time CPU% Loads LCPU% Ratio
2.6.4 4 103 96.1 0.0 0.0 1.00
cacherun:
2.6.4 4 100 99.0 0.0 0.0 0.97
process_load:
2.6.4 4 103 97.1 3.8 1.0 1.00
ctar_load:
2.6.4 4 126 80.2 5.2 6.3 1.22
xtar_load:
2.6.4 4 111 91.9 2.0 2.7 1.08
io_load:
2.6.4 4 112 90.2 7.8 4.5 1.09
io_other:
2.6.4 4 117 86.3 8.3 5.1 1.14
read_load:
2.6.4 3 131 XX 76.3 XX 1.27
list_load:
2.6.4 3 113 XX 1 XX 1.10
mem_load:
2.6.4 3 105 XX 44.3 XX 1.02

-------------------------------------------------------
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 14:01    [from the cache]
©2003-2014 Jasper Spaans. Advertise on this site