[PATCH] O(1) Entitlement Based Scheduler v1.1

[PATCH] O(1) Entitlement Based Scheduler v1.1

[John Lee]

Hi,

This patch is an update of the original Entitlement Based Scheduler 
announed a few weeks ago. The patch can be downloaded from

http://sourceforge.net/projects/ebs-linux/

and applies to Linux 2.6.4.

The two main changes in this version are:
1) Interactivity has been greatly improved, courtesy of "ramp-up" 
dampening being applied to newly forked tasks. 
2) Background tasks are now "almost background" tasks in that they are 
given periodic (but slow) promotion.

As before, when using this patch X should be reniced to -15.

Below is a contest benchmark for this patch, performed on a dual 
P3-800MHz:

no_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio CPU+LCPU%
2.6.4              3    86      168.6   0       25.6    1.00    194.2
2.6.4-EBS          3    82      176.8   0       15.9    1.00    192.7
cacherun:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio CPU+LCPU%
2.6.4              3    85      170.6   0       27.1    0.99    197.7
2.6.4-EBS          3    80      181.2   0       15.0    0.98    196.2
process_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio CPU+LCPU%
2.6.4              3    103     140.8   34      54.4    1.20    195.2
2.6.4-EBS          3    103     139.8   35      53.4    1.26    193.2
ctar_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio CPU+LCPU%
2.6.4              3    100     153.0   0       1.0     1.16    154.0
2.6.4-EBS          3    98      157.1   0       0.0     1.20    157.1
xtar_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio CPU+LCPU%
2.6.4              3    95      160.0   0       6.3     1.10    166.3
2.6.4-EBS          3    92      163.0   0       5.4     1.12    168.4
io_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio CPU+LCPU%
2.6.4              3    312     51.0    23      12.1    3.63    63.1
2.6.4-EBS          3    200     77.0    14      11.4    2.44    88.4
read_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio CPU+LCPU%
2.6.4              3    116     135.3   6       7.8     1.35    143.1
2.6.4-EBS          3    111     139.6   6       8.1     1.35    147.7
2list_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio CPU+LCPU%
2.6.4              3    122     123.8   0       10.7    1.42    134.5
2.6.4-EBS          3    123     121.1   0       8.1     1.50    129.2
mem_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio CPU+LCPU%
2.6.4              3    102     158.8   31      2.9     1.19    161.7
2.6.4-EBS          3    103     159.2   31      2.9     1.26    162.1
dbench_load:
Kernel        [runs]    Time    CPU%    Loads   LCPU%   Ratio CPU+LCPU%
2.6.4              3    203     76.4    2       45.6    2.36    122.0
2.6.4-EBS          3    150     104.0   1       22.0    1.83    126.0

Comments, bug reports and testing are welcome.

Thanks,

John

Re: [PATCH] O(1) Entitlement Based Scheduler v1.1

[John Lee]

On 25 Mar 2004, Andi Kleen wrote:

> John Lee <johnl@aurema.com> writes:
> 
> > Hi,
> > 
> > This patch is an update of the original Entitlement Based Scheduler 
> > announed a few weeks ago. The patch can be downloaded from
> > 
> > http://sourceforge.net/projects/ebs-linux/
> > 
> > and applies to Linux 2.6.4.
> 
> [...]
> 
> I tested this patch for some days on my workstation now and it works
> fine for me. The interactivity problems I had previously with background
> load seem to be gone too.

Hi Andi,

I'm glad to hear that the interactivity now works well for you, and that 
it seems to be behaving itself over a period of days.

Thanks for testing,

John

Re: [PATCH] O(1) Entitlement Based Scheduler v1.1

[Andi Kleen]

On Fri, 26 Mar 2004 11:02:36 +1100 (EST)
John Lee <johnl@aurema.com> wrote:

> I'm glad to hear that the interactivity now works well for you, and that 
> it seems to be behaving itself over a period of days.

There seem to be still small issues, but I wasn't able to pinpoint them
to a scenario (I'm not even 100% sure they are related to the CPU scheduler, could
be IO elevator or VM too). Just thought I would mention them. Occassionally 
(very seldom, saw it two times yesterday) I have visible stalls (2-3s) of my xterms. 
It doesn't seem to be  related to direct visible background load (but i wasn't 
able yet to get a top up during such a stall) I don't remember these stalls from 
the non Entitlement kernel. They only happen very rarely so it could be 
something unrelated too. I know the report is probably too vague to be useful.

-Andi

Re: [PATCH] O(1) Entitlement Based Scheduler v1.1

[Andi Kleen]

John Lee <johnl@aurema.com> writes:
>
> On the contrary, any reports of strange/bad behaviour are useful. It 
> probably is related to the scheduler, as no one seems to have reported 
> this problem with stock 2.6.4.

Actually I saw it on 2.6.5rc2 with your scheduler patch merged
(and my x86-64 patchkit, but that is unlikely to affect scheduling
decisions). 

-Andi

Re: [PATCH] O(1) Entitlement Based Scheduler v1.1

[John Lee]

On Fri, 26 Mar 2004, Andi Kleen wrote:

> On Fri, 26 Mar 2004 11:02:36 +1100 (EST)
> John Lee <johnl@aurema.com> wrote:
> 
> > I'm glad to hear that the interactivity now works well for you, and that 
> > it seems to be behaving itself over a period of days.
> 
> There seem to be still small issues, but I wasn't able to pinpoint them
> to a scenario (I'm not even 100% sure they are related to the CPU 
> scheduler, could be IO elevator or VM too). Just thought I would mention 
> them. Occassionally (very seldom, saw it two times yesterday) I have 
> visible stalls (2-3s) of my xterms. 
> It doesn't seem to be  related to direct visible background load (but i 
> wasn't able yet to get a top up during such a stall) I don't remember 
> these stalls from the non Entitlement kernel. They only happen very 
> rarely so it could be something unrelated too. I know the report is 
> probably too vague to be useful.

On the contrary, any reports of strange/bad behaviour are useful. It 
probably is related to the scheduler, as no one seems to have reported 
this problem with stock 2.6.4.

I'll look out for these stalls, and try to find the cause/fix.

John