[ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Con Kolivas]

A significant bugfix for SMP balancing was just posted for the staircase 
deadline cpu scheduler which improves behaviour dramatically on any SMP 
machine.

Thanks to Willy Tarreau for noticing likely fault point.

Also requested was a version in the Makefile so this version of the patch 
adds -sd045 to the kernel version.

http://ck.kolivas.org/patches/staircase-deadline/2.6.20.7-sd-0.45.patch
http://ck.kolivas.org/patches/staircase-deadline/2.6.21-rc7-sd-0.45.patch

Incrementals from 0.44:
http://ck.kolivas.org/patches/staircase-deadline/2.6.20.7/sd-0.44-0.45.patch
http://ck.kolivas.org/patches/staircase-deadline/2.6.21-rc7/sd-0.44-0.45.patch

Renicing X to -10, while not essential, may be desirable on the desktop. 
Unlike the CFS scheduler which renices X without your intervention to 
nice -19, the SD patches do not alter nice level on their own.

See the patch just posted called 'sched: implement staircase deadline 
scheduler ymf accounting fixes' for details of the fixes.

-- 
-ck

Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Willy Tarreau]

On Sun, Apr 22, 2007 at 02:41:48PM +1000, Con Kolivas wrote:
> A significant bugfix for SMP balancing was just posted for the staircase 
> deadline cpu scheduler which improves behaviour dramatically on any SMP 
> machine.
> 
> Thanks to Willy Tarreau for noticing likely fault point.
> 
> Also requested was a version in the Makefile so this version of the patch 
> adds -sd045 to the kernel version.

Con, I'm sorry, but it is worse with this one :-(

The lag when typing in xterms is even more noticeable and vmstat output
oscillates between 8 and 65, with idle rates around 50%, as you can see
below :

   procs                      memory      swap          io     system      cpu
 r  b  w   swpd   free   buff  cache   si   so    bi    bo   in    cs us sy id
 9  0  0      0 922436   6392  57496    0    0     0     0    2   172 26 33 41
65  0  1      0 922436   6392  57496    0    0     0     0    0   132 23 37 40
66  0  0      0 922436   6392  57496    0    0     0     0    1   159 18 31 51
 9  0  0      0 922436   6392  57496    0    0     0     0    0   166 24 37 40
68  0  0      0 922436   6392  57496    0    0     0     0    5   121 23 32 44
62  0  0      0 922576   6392  57496    0    0     0     0    0   161 17 29 53
 8  0  0      0 922576   6392  57496    0    0     0     0    1   158 23 42 34
65  0  0      0 922576   6392  57496    0    0     0     0    1    92 17 33 50
52  0  2      0 922576   6392  57496    0    0     0     0    0   156 19 28 53
13  0  0      0 922576   6392  57496    0    0     0     0    8   171 25 44 30
65  0  0      0 922576   6392  57496    0    0     0     0   17   172 20 26 54
 8  0  0      0 922576   6392  57496    0    0     0     0    4   188 22 31 47
22  0  0      0 922576   6392  57496    0    0     0     0   10   182 26 38 36
65  0  1      0 922576   6392  57496    0    0     0     0    8   107 18 28 54
 8  0  0      0 922588   6424  57508    0    0    12    36   11   201 26 35 39
66  0  0      0 922588   6424  57508    0    0     0     0   11   115 22 36 43
61  0  0      0 922564   6424  57508    0    0     0     0   32   409 16 28 56
 8  0  0      0 922564   6424  57508    0    0     0     0   19   224 24 42 34
65  0  0      0 922564   6436  57496    0    0     0    12   34   439 19 29 52
 8  0  0      0 922564   6436  57496    0    0     0     0   28   320 18 26 56
20  0  0      0 922564   6436  57508    0    0     0     0    6   195 26 42 32

Renicing X or not does not change anything here.

I suspect that the bug you fixed was hiding another one :-/
If you want me to test another patch, feel free to ask.

Willy

Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Con Kolivas]

On Sunday 22 April 2007 17:00, Willy Tarreau wrote:
> On Sun, Apr 22, 2007 at 02:41:48PM +1000, Con Kolivas wrote:
> > A significant bugfix for SMP balancing was just posted for the staircase
> > deadline cpu scheduler which improves behaviour dramatically on any SMP
> > machine.
> >
> > Thanks to Willy Tarreau for noticing likely fault point.
> >
> > Also requested was a version in the Makefile so this version of the patch
> > adds -sd045 to the kernel version.
>
> Con, I'm sorry, but it is worse with this one :-(

Well that was quick testing, thanks.
>
> The lag when typing in xterms is even more noticeable and vmstat output
> oscillates between 8 and 65, with idle rates around 50%, as you can see
> below :

> Renicing X or not does not change anything here.
>
> I suspect that the bug you fixed was hiding another one :-/
> If you want me to test another patch, feel free to ask.

Thanks. Clearly still a bug in there. I have to keep looking. The other 
changes are still valid so I have to run with them.

> Willy

-- 
-ck

Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Con Kolivas]

On Sunday 22 April 2007 17:27, Con Kolivas wrote:
> On Sunday 22 April 2007 17:00, Willy Tarreau wrote:
> > On Sun, Apr 22, 2007 at 02:41:48PM +1000, Con Kolivas wrote:
> > > A significant bugfix for SMP balancing was just posted for the
> > > staircase deadline cpu scheduler which improves behaviour dramatically
> > > on any SMP machine.
> > >
> > > Thanks to Willy Tarreau for noticing likely fault point.
> > >
> > > Also requested was a version in the Makefile so this version of the
> > > patch adds -sd045 to the kernel version.
> >
> > Con, I'm sorry, but it is worse with this one :-(
>
> Well that was quick testing, thanks.
>
> > The lag when typing in xterms is even more noticeable and vmstat output
> > oscillates between 8 and 65, with idle rates around 50%, as you can see
> > below :
> >
> > Renicing X or not does not change anything here.
> >
> > I suspect that the bug you fixed was hiding another one :-/
> > If you want me to test another patch, feel free to ask.

Just as a debug point could you please try this patch? Thanks.

> Thanks. Clearly still a bug in there. I have to keep looking. The other
> changes are still valid so I have to run with them.
>
> > Willy
---
 kernel/sched.c |    2 ++
 1 file changed, 2 insertions(+)

Index: linux-2.6.21-rc7-sd/kernel/sched.c
===================================================================
--- linux-2.6.21-rc7-sd.orig/kernel/sched.c	2007-04-22 17:30:25.000000000 +1000
+++ linux-2.6.21-rc7-sd/kernel/sched.c	2007-04-22 17:30:49.000000000 +1000
@@ -3276,6 +3276,7 @@ retry:
 	}
 	queue = array->queue + idx;
 	next = list_entry(queue->next, struct task_struct, run_list);
+#if 0
 	if (unlikely(next->time_slice <= 0)) {
 		/*
 		 * Unlucky enough that this task ran out of time_slice
@@ -3287,6 +3288,7 @@ retry:
 		idx = find_next_bit(rq->dyn_bitmap, MAX_PRIO, MAX_RT_PRIO);
 		goto retry;
 	}
+#endif
 	next->rotation = rq->prio_rotation;
 	nstatic = next->static_prio;
 	if (nstatic < array->best_static_prio)

-- 
-ck

Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Willy Tarreau]

On Sun, Apr 22, 2007 at 05:31:58PM +1000, Con Kolivas wrote:
> On Sunday 22 April 2007 17:27, Con Kolivas wrote:
> > On Sunday 22 April 2007 17:00, Willy Tarreau wrote:
> > > On Sun, Apr 22, 2007 at 02:41:48PM +1000, Con Kolivas wrote:
> > > > A significant bugfix for SMP balancing was just posted for the
> > > > staircase deadline cpu scheduler which improves behaviour dramatically
> > > > on any SMP machine.
> > > >
> > > > Thanks to Willy Tarreau for noticing likely fault point.
> > > >
> > > > Also requested was a version in the Makefile so this version of the
> > > > patch adds -sd045 to the kernel version.
> > >
> > > Con, I'm sorry, but it is worse with this one :-(
> >
> > Well that was quick testing, thanks.
> >
> > > The lag when typing in xterms is even more noticeable and vmstat output
> > > oscillates between 8 and 65, with idle rates around 50%, as you can see
> > > below :
> > >
> > > Renicing X or not does not change anything here.
> > >
> > > I suspect that the bug you fixed was hiding another one :-/
> > > If you want me to test another patch, feel free to ask.
> 
> Just as a debug point could you please try this patch? Thanks.

OK, this time, the ocbench took ages to start. They appeared immediately
but very few of them (less than 8 out of 64) really started to work. The
system remained very responsive and smooth during the test. But I guess
I know why : all the load was sent to CPU 0 :

   procs                      memory      swap          io     system      cpu
 r  b  w   swpd   free   buff  cache   si   so    bi    bo   in    cs us sy id
63  0  0      0 923476   6516  57456    0    0     0    28  175  1281 14 26 59
64  0  2      0 922976   6516  57456    0    0     0     0    4   261 19 31 50
64  0  0      0 922924   6516  57492    0    0     0     0    1    85 17 33 50
64  0  0      0 922924   6516  57492    0    0     0     0    0   110 25 25 50
64  0  1      0 922924   6516  57492    0    0     0     0    3    83 24 27 50
64  0  0      0 922924   6516  57492    0    0     0     4   16   267 18 33 50
64  0  0      0 922924   6516  57492    0    0     0     0   15   244 24 27 50
64  0  0      0 922956   6516  57492    0    0     0     0    8   200 20 31 49
59  0  0      0 922956   6516  57492    0    0     0     0    1    98 18 34 49
59  0  0      0 922956   6516  57492    0    0     0     0    0   105 21 30 49
64  0  0      0 922956   6516  57492    0    0     0     0    1    97 19 32 49
62  0  0      0 922972   6516  57492    0    0     0     0    0   114 23 28 49
64  0  0      0 922972   6516  57492    0    0     0     0    1    95 23 28 49
64  0  0      0 922972   6516  57492    0    0     0     0    0   104 22 29 49


CPU0 states:  45.0% user  54.0% system    0.0% nice   0.0% iowait   0.0% idle
CPU1 states:   0.1% user   0.0% system    0.0% nice   0.0% iowait  99.0% idle
Mem:  1034876k av,  112296k used,  922580k free,       0k shrd,    6524k buff
        34232k active,              45428k inactive
Swap:  497972k av,       0k used,  497972k free                   57536k cached

  PID USER     PRI  NI  SIZE  RSS SHARE STAT %CPU %MEM   TIME CPU COMMAND
 1402 willy     31   0  2272  640   548 R     2.9  0.0   0:00   0 ocbench
 1407 willy     31   0  2272  640   548 R     2.9  0.0   0:00   0 ocbench
 1452 willy     31   0  2272  640   548 R     2.9  0.0   0:00   0 ocbench
 1455 willy     31   0  2272  640   548 R     2.9  0.0   0:00   0 ocbench
 1394 willy     29   0  2272  640   548 R     1.9  0.0   0:00   0 ocbench
 1395 willy     29   0  2272  640   548 R     1.9  0.0   0:00   0 ocbench
 1396 willy     31   0  2272  640   548 R     1.9  0.0   0:00   0 ocbench
 1400 willy     31   0  2272  640   548 R     1.9  0.0   0:00   0 ocbench
 1401 willy     29   0  2272  640   548 R     1.9  0.0   0:00   0 ocbench
 1404 willy     31   0  2272  640   548 R     1.9  0.0   0:00   0 ocbench
 1408 willy     31   0  2272  640   548 R     1.9  0.0   0:00   0 ocbench
 1409 willy     31   0  2272  640   548 R     1.9  0.0   0:00   0 ocbench
 1411 willy     31   0  2272  640   548 R     1.9  0.0   0:00   0 ocbench
 1412 willy     31   0  2272  640   548 R     1.9  0.0   0:00   0 ocbench
 1413 willy     31   0  2272  640   548 R     1.9  0.0   0:00   0 ocbench


Willy

Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Con Kolivas]

On Sunday 22 April 2007 18:06, Willy Tarreau wrote:
> On Sun, Apr 22, 2007 at 05:31:58PM +1000, Con Kolivas wrote:
> > On Sunday 22 April 2007 17:27, Con Kolivas wrote:
> > > On Sunday 22 April 2007 17:00, Willy Tarreau wrote:
> > > > On Sun, Apr 22, 2007 at 02:41:48PM +1000, Con Kolivas wrote:
> > > > > A significant bugfix for SMP balancing was just posted for the
> > > > > staircase deadline cpu scheduler which improves behaviour
> > > > > dramatically on any SMP machine.
> > > > >
> > > > > Thanks to Willy Tarreau for noticing likely fault point.
> > > > >
> > > > > Also requested was a version in the Makefile so this version of the
> > > > > patch adds -sd045 to the kernel version.
> > > >
> > > > Con, I'm sorry, but it is worse with this one :-(
> > >
> > > Well that was quick testing, thanks.
> > >
> > > > The lag when typing in xterms is even more noticeable and vmstat
> > > > output oscillates between 8 and 65, with idle rates around 50%, as
> > > > you can see below :
> > > >
> > > > Renicing X or not does not change anything here.
> > > >
> > > > I suspect that the bug you fixed was hiding another one :-/
> > > > If you want me to test another patch, feel free to ask.
> >
> > Just as a debug point could you please try this patch? Thanks.
>
> OK, this time, the ocbench took ages to start. They appeared immediately
> but very few of them (less than 8 out of 64) really started to work. The
> system remained very responsive and smooth during the test. But I guess
> I know why : all the load was sent to CPU 0 :

Shouldn't have affected smp balancing at all, but try this on top of the 
ontop please? Thanks

> Willy

---
 kernel/sched.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Index: linux-2.6.21-rc7-sd/kernel/sched.c
===================================================================
--- linux-2.6.21-rc7-sd.orig/kernel/sched.c	2007-04-22 18:52:29.000000000 +1000
+++ linux-2.6.21-rc7-sd/kernel/sched.c	2007-04-22 18:52:52.000000000 +1000
@@ -703,7 +703,7 @@ static int next_entitled_slot(struct tas
 	 * Go straight to expiration if there are higher priority tasks
 	 * already expired.
 	 */
-	if (p->static_prio > rq->expired->best_static_prio)
+	if (p->static_prio > rq->expired->best_static_prio && p->mm)
 		return MAX_PRIO;
 	if (!rq->prio_level[uprio])
 		rq->prio_level[uprio] = MAX_RT_PRIO;

-- 
-ck

Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Willy Tarreau]

On Sun, Apr 22, 2007 at 06:53:58PM +1000, Con Kolivas wrote:
> On Sunday 22 April 2007 18:06, Willy Tarreau wrote:
> > On Sun, Apr 22, 2007 at 05:31:58PM +1000, Con Kolivas wrote:
> > > On Sunday 22 April 2007 17:27, Con Kolivas wrote:
> > > > On Sunday 22 April 2007 17:00, Willy Tarreau wrote:
> > > > > On Sun, Apr 22, 2007 at 02:41:48PM +1000, Con Kolivas wrote:
> > > > > > A significant bugfix for SMP balancing was just posted for the
> > > > > > staircase deadline cpu scheduler which improves behaviour
> > > > > > dramatically on any SMP machine.
> > > > > >
> > > > > > Thanks to Willy Tarreau for noticing likely fault point.
> > > > > >
> > > > > > Also requested was a version in the Makefile so this version of the
> > > > > > patch adds -sd045 to the kernel version.
> > > > >
> > > > > Con, I'm sorry, but it is worse with this one :-(
> > > >
> > > > Well that was quick testing, thanks.
> > > >
> > > > > The lag when typing in xterms is even more noticeable and vmstat
> > > > > output oscillates between 8 and 65, with idle rates around 50%, as
> > > > > you can see below :
> > > > >
> > > > > Renicing X or not does not change anything here.
> > > > >
> > > > > I suspect that the bug you fixed was hiding another one :-/
> > > > > If you want me to test another patch, feel free to ask.
> > >
> > > Just as a debug point could you please try this patch? Thanks.
> >
> > OK, this time, the ocbench took ages to start. They appeared immediately
> > but very few of them (less than 8 out of 64) really started to work. The
> > system remained very responsive and smooth during the test. But I guess
> > I know why : all the load was sent to CPU 0 :
> 
> Shouldn't have affected smp balancing at all, but try this on top of the 
> ontop please? Thanks

Does not change anything. There clearly is a huge regression somewhere :-/
The second CPU is not used by ocbench, and again, out of 64 tasks, only
a small bunch (between 4 and 8) do something.

Con, you should review the changes between 0.44 and 0.45, I think you
introduced a bug which broke fairness while fixing another one.

Willy

Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Con Kolivas]

On Sunday 22 April 2007 19:14, Willy Tarreau wrote:
> On Sun, Apr 22, 2007 at 06:53:58PM +1000, Con Kolivas wrote:
> > On Sunday 22 April 2007 18:06, Willy Tarreau wrote:
> > > On Sun, Apr 22, 2007 at 05:31:58PM +1000, Con Kolivas wrote:
> > > > On Sunday 22 April 2007 17:27, Con Kolivas wrote:
> > > > > On Sunday 22 April 2007 17:00, Willy Tarreau wrote:
> > > > > > On Sun, Apr 22, 2007 at 02:41:48PM +1000, Con Kolivas wrote:
> > > > > > > A significant bugfix for SMP balancing was just posted for the
> > > > > > > staircase deadline cpu scheduler which improves behaviour
> > > > > > > dramatically on any SMP machine.
> > > > > > >
> > > > > > > Thanks to Willy Tarreau for noticing likely fault point.
> > > > > > >
> > > > > > > Also requested was a version in the Makefile so this version of
> > > > > > > the patch adds -sd045 to the kernel version.
> > > > > >
> > > > > > Con, I'm sorry, but it is worse with this one :-(
> > > > >
> > > > > Well that was quick testing, thanks.
> > > > >
> > > > > > The lag when typing in xterms is even more noticeable and vmstat
> > > > > > output oscillates between 8 and 65, with idle rates around 50%,
> > > > > > as you can see below :
> > > > > >
> > > > > > Renicing X or not does not change anything here.
> > > > > >
> > > > > > I suspect that the bug you fixed was hiding another one :-/
> > > > > > If you want me to test another patch, feel free to ask.
> > > >
> > > > Just as a debug point could you please try this patch? Thanks.
> > >
> > > OK, this time, the ocbench took ages to start. They appeared
> > > immediately but very few of them (less than 8 out of 64) really started
> > > to work. The system remained very responsive and smooth during the
> > > test. But I guess I know why : all the load was sent to CPU 0 :
> >
> > Shouldn't have affected smp balancing at all, but try this on top of the
> > ontop please? Thanks
>
> Does not change anything. There clearly is a huge regression somewhere :-/
> The second CPU is not used by ocbench, and again, out of 64 tasks, only
> a small bunch (between 4 and 8) do something.
>
> Con, you should review the changes between 0.44 and 0.45, I think you
> introduced a bug which broke fairness while fixing another one.

Hmm; well it was "better" without the first debug patch I sent (even though it 
ws worse than 0.44) which is important in itself. I thank you greatly for 
your testing so far. Unfortunately I'm close to a one man code show so I'll 
have to spend time reviewing it further. The changes so far look ok still. 
Something else is lurking.

Thanks!

-- 
-ck

Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Con Kolivas]

On Sunday 22 April 2007 19:14, Willy Tarreau wrote:
> On Sun, Apr 22, 2007 at 06:53:58PM +1000, Con Kolivas wrote:
> > On Sunday 22 April 2007 18:06, Willy Tarreau wrote:
> > > On Sun, Apr 22, 2007 at 05:31:58PM +1000, Con Kolivas wrote:
> > > > On Sunday 22 April 2007 17:27, Con Kolivas wrote:
> > > > > On Sunday 22 April 2007 17:00, Willy Tarreau wrote:
> > > > > > On Sun, Apr 22, 2007 at 02:41:48PM +1000, Con Kolivas wrote:
> > > > > > > A significant bugfix for SMP balancing was just posted for the
> > > > > > > staircase deadline cpu scheduler which improves behaviour
> > > > > > > dramatically on any SMP machine.
> > > > > > >
> > > > > > > Thanks to Willy Tarreau for noticing likely fault point.
> > > > > > >
> > > > > > > Also requested was a version in the Makefile so this version of
> > > > > > > the patch adds -sd045 to the kernel version.
> > > > > >
> > > > > > Con, I'm sorry, but it is worse with this one :-(
> > > > >
> > > > > Well that was quick testing, thanks.
> > > > >
> > > > > > The lag when typing in xterms is even more noticeable and vmstat
> > > > > > output oscillates between 8 and 65, with idle rates around 50%,
> > > > > > as you can see below :
> > > > > >
> > > > > > Renicing X or not does not change anything here.
> > > > > >
> > > > > > I suspect that the bug you fixed was hiding another one :-/
> > > > > > If you want me to test another patch, feel free to ask.
> > > >
> > > > Just as a debug point could you please try this patch? Thanks.
> > >
> > > OK, this time, the ocbench took ages to start. They appeared
> > > immediately but very few of them (less than 8 out of 64) really started
> > > to work. The system remained very responsive and smooth during the
> > > test. But I guess I know why : all the load was sent to CPU 0 :
> >
> > Shouldn't have affected smp balancing at all, but try this on top of the
> > ontop please? Thanks
>
> Does not change anything. There clearly is a huge regression somewhere :-/
> The second CPU is not used by ocbench, and again, out of 64 tasks, only
> a small bunch (between 4 and 8) do something.
>
> Con, you should review the changes between 0.44 and 0.45, I think you
> introduced a bug which broke fairness while fixing another one.

Ok I was able to find time on dual core and could reproduce your problem. 
Testing something now that I think might be responsible.

-- 
-ck

Re: [ck] Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Con Kolivas]

On Sunday 22 April 2007 21:42, Con Kolivas wrote:

Willy I'm still investigating the idle time and fluctuating load as a separate 
issue. Is it possible the multiple ocbench processes are naturally 
synchronising and desynchronising and choosing to sleep and/or run at the 
same time? I can remove the idle time entirely by running ocbench at nice 19 
which means they are all forced to run at basically the same time by the 
scheduler.

Anyway the more important part is... Can you test this patch please? Dump
all the other patches I sent you post 045. Michael, if you could test too
please?

Thanks!

---

It appears load weight still wasn't being set in enough places and changing
where rr_interval was being set a few iterations of SD ago might have revealed
that bug. Ensure load_weight is set whenever p->quota is set and simplify
dramatically the load_weight.

Signed-off-by: Con Kolivas <kernel@kolivas.org>

---
 kernel/sched.c |   35 ++++++++++++++++-------------------
 1 file changed, 16 insertions(+), 19 deletions(-)

Index: linux-2.6.21-rc7-sd/kernel/sched.c
===================================================================
--- linux-2.6.21-rc7-sd.orig/kernel/sched.c	2007-04-22 21:37:25.000000000 +1000
+++ linux-2.6.21-rc7-sd/kernel/sched.c	2007-04-22 22:01:48.000000000 +1000
@@ -102,8 +102,6 @@ unsigned long long __attribute__((weak))
  */
 int rr_interval __read_mostly = 8;
 
-#define DEF_TIMESLICE		(rr_interval * 20)
-
 /*
  * This contains a bitmap for each dynamic priority level with empty slots
  * for the valid priorities each different nice level can have. It allows
@@ -886,16 +884,10 @@ static int task_timeslice(struct task_st
 }
 
 /*
- * Assume: static_prio_timeslice(NICE_TO_PRIO(0)) == DEF_TIMESLICE
- * If static_prio_timeslice() is ever changed to break this assumption then
- * this code will need modification. Scaled as multiples of milliseconds.
- */
-#define TIME_SLICE_NICE_ZERO DEF_TIMESLICE
-#define LOAD_WEIGHT(lp) \
-	(((lp) * SCHED_LOAD_SCALE) / TIME_SLICE_NICE_ZERO)
-#define TASK_LOAD_WEIGHT(p)	LOAD_WEIGHT(task_timeslice(p))
-#define RTPRIO_TO_LOAD_WEIGHT(rp)	\
-	(LOAD_WEIGHT((rr_interval + 20 + (rp))))
+ * The load weight is basically the task_timeslice in ms. Realtime tasks are
+ * special cased to be proportionately larger by their rt_priority.
+ */
+#define RTPRIO_TO_LOAD_WEIGHT(rp)	((rr_interval + 20 + (rp)))
 
 static void set_load_weight(struct task_struct *p)
 {
@@ -912,7 +904,7 @@ static void set_load_weight(struct task_
 #endif
 			p->load_weight = RTPRIO_TO_LOAD_WEIGHT(p->rt_priority);
 	} else
-		p->load_weight = TASK_LOAD_WEIGHT(p);
+		p->load_weight = task_timeslice(p);
 }
 
 static inline void
@@ -995,7 +987,7 @@ static int effective_prio(struct task_st
  * nice -20 = 10 * rr_interval. nice 1-19 = rr_interval / 2.
  * Value returned is in microseconds.
  */
-static unsigned int rr_quota(struct task_struct *p)
+static inline unsigned int rr_quota(struct task_struct *p)
 {
 	int nice = TASK_NICE(p), rr = rr_interval;
 
@@ -1009,6 +1001,13 @@ static unsigned int rr_quota(struct task
 	return MS_TO_US(rr);
 }
 
+/* Every time we set the quota we need to set the load weight */
+static void set_quota(struct task_struct *p)
+{
+	p->quota = rr_quota(p);
+	set_load_weight(p);
+}
+
 /*
  * activate_task - move a task to the runqueue and do priority recalculation
  */
@@ -1036,7 +1035,7 @@ static void activate_task(struct task_st
 				     (now - p->timestamp) >> 20);
 	}
 
-	p->quota = rr_quota(p);
+	set_quota(p);
 	p->prio = effective_prio(p);
 	p->timestamp = now;
 	__activate_task(p, rq);
@@ -3885,8 +3884,7 @@ void set_user_nice(struct task_struct *p
 	p->static_prio = NICE_TO_PRIO(nice);
 	old_prio = p->prio;
 	p->prio = effective_prio(p);
-	p->quota = rr_quota(p);
-	set_load_weight(p);
+	set_quota(p);
 	delta = p->prio - old_prio;
 
 	if (queued) {
@@ -4020,8 +4018,7 @@ static void __setscheduler(struct task_s
 	p->normal_prio = normal_prio(p);
 	/* we are holding p->pi_lock already */
 	p->prio = rt_mutex_getprio(p);
-	p->quota = rr_quota(p);
-	set_load_weight(p);
+	set_quota(p);
 }
 
 /**

-- 
-ck

Re: [ck] Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Willy Tarreau]

On Sun, Apr 22, 2007 at 10:18:32PM +1000, Con Kolivas wrote:
> On Sunday 22 April 2007 21:42, Con Kolivas wrote:
> 
> Willy I'm still investigating the idle time and fluctuating load as a separate 
> issue.

OK.

> Is it possible the multiple ocbench processes are naturally 
> synchronising and desynchronising and choosing to sleep and/or run at the 
> same time?

I don't think so. They're independant processes, and I insist on reducing
their X work in order to ensure they don't get perturbated by external
factor. Their work consist in looping 250 ms and waiting 750 ms, then
displaying a new progress line.

> I can remove the idle time entirely by running ocbench at nice 19 
> which means they are all forced to run at basically the same time by the 
> scheduler.

It may indicate some special handling of nice ?

> Anyway the more important part is... Can you test this patch please? Dump
> all the other patches I sent you post 045. Michael, if you could test too
> please?

OK, I will restart from fresh 0.45 and try again.

Regards,
Willy

Re: [ck] Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Con Kolivas]

On Sunday 22 April 2007 23:07, Willy Tarreau wrote:
> On Sun, Apr 22, 2007 at 10:18:32PM +1000, Con Kolivas wrote:
> > On Sunday 22 April 2007 21:42, Con Kolivas wrote:
> >
> > Willy I'm still investigating the idle time and fluctuating load as a
> > separate issue.
>
> OK.
>
> > Is it possible the multiple ocbench processes are naturally
> > synchronising and desynchronising and choosing to sleep and/or run at the
> > same time?
>
> I don't think so. They're independant processes, and I insist on reducing
> their X work in order to ensure they don't get perturbated by external
> factor. Their work consist in looping 250 ms and waiting 750 ms, then
> displaying a new progress line.

Well if they always wait 750ms and they always do 250ms of work, they will 
never actually get their 250ms in a continuous stream, and may be waiting on 
a runqueue while working. What I mean then is that scheduling could cause 
that synchronising and desynchronising unwittingly by fluctuating the 
absolute time over which they get their 250ms. The sleep always takes 750ms, 
but the actual physical time over which they get their 250ms fluctuates by 
scheduling aliasing. If instead the code said "500ms has passed while I only 
did 250ms work so I should sleep for 250ms less" this aliasing would go away. 
Of course this is impossible since a fully loaded machine would mean each 
process should never sleep. I'm not arguing this is correct behaviour for the 
scheduler to cause this, mind you, nor am I saying it's wrong behaviour. I'm 
just trying to understand better how it happens and what (if anything) should 
be done about it. Overall their progress and cpu distribution appears 
identical, as you said. The difference is that the CFS design intrinsically 
manages this exact scenario by design with its sleep/run timing mechanism.

> > I can remove the idle time entirely by running ocbench at nice 19
> > which means they are all forced to run at basically the same time by the
> > scheduler.
>
> It may indicate some special handling of nice ?

By running them nice 19 the scheduler has effectively just sequentially 
schedules them, and there is no aliasing.

-- 
-ck

Re: [ck] Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Willy Tarreau]

On Sun, Apr 22, 2007 at 10:18:32PM +1000, Con Kolivas wrote:
> On Sunday 22 April 2007 21:42, Con Kolivas wrote:
> 
> Willy I'm still investigating the idle time and fluctuating load as a separate 
> issue. Is it possible the multiple ocbench processes are naturally 
> synchronising and desynchronising and choosing to sleep and/or run at the 
> same time? I can remove the idle time entirely by running ocbench at nice 19 
> which means they are all forced to run at basically the same time by the 
> scheduler.
> 
> Anyway the more important part is... Can you test this patch please? Dump
> all the other patches I sent you post 045. Michael, if you could test too
> please?

OK, it's better now. All tasks equally run. X is still somewhat jerky, even
at nice -19. I'm sure it happens when it's waiting in the other array. We
should definitely manage to get rid of this if we want to ensure low latency.

Just FYI, the idle is often close to zero and the load is often close to 30,
even if still fluctuating :

   procs                      memory      swap          io     system      cpu
 r  b  w   swpd   free   buff  cache   si   so    bi    bo   in    cs us sy id
22  0  0      0 922876   6472  57848    0    0     0     0  164  3275 34 58  8
14  0  0      0 922648   6472  57864    0    0     0     0    8   383 37 63  0
24  0  0      0 922580   6472  57864    0    0     0   128   32   219 34 66  0
13  0  1      0 922524   6472  57864    0    0     0     0    0   393 35 64  0
31  0  0      0 922524   6472  57864    0    0     0     0    3   338 37 63  0
56  0  0      0 922556   6472  57864    0    0     0     0    0   290 35 65  0
57  0  1      0 922556   6472  57864    0    0     0     0    1   288 33 55 11
45  0  0      0 922556   6472  57864    0    0     0     0    1   255 27 52 21
38  0  0      0 922564   6472  57864    0    0     0     0    0   161 24 49 27
 0  0  0      0 922564   6472  57864    0    0     0     0    1   142 23 40 38
 0  0  0      0 922564   6472  57864    0    0     0     0    2   182 29 55 16
22  0  0      0 922564   6472  57864    0    0     0     0    1   253 28 48 24
26  0  0      0 922564   6472  57864    0    0     0     0    1   212 31 60  9
27  0  0      0 922564   6472  57864    0    0     0     0    1   314 31 70  0
44  0  0      0 922564   6472  57864    0    0     0     0    2   282 32 62  6
54  0  1      0 922564   6472  57864    0    0     0     0   26   213 32 67  1
42  0  0      0 922564   6472  57864    0    0     0     0  142   278 34 61  4
35  0  0      0 922564   6472  57864    0    0     0     0   58   226 39 61  0
 6  0  0      0 922564   6472  57864    0    0     0     0   79   228 35 65  0
 5  0  0      0 922564   6472  57864    0    0     0     0   98   225 36 61  3
35  0  1      0 922564   6472  57864    0    0     0     0   71   205 22 41 36

Hoping this helps !
Willy

Re: [ck] Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Con Kolivas]

On Monday 23 April 2007 00:22, Willy Tarreau wrote:
> On Sun, Apr 22, 2007 at 10:18:32PM +1000, Con Kolivas wrote:
> > On Sunday 22 April 2007 21:42, Con Kolivas wrote:
> >
> > Willy I'm still investigating the idle time and fluctuating load as a
> > separate issue. Is it possible the multiple ocbench processes are
> > naturally synchronising and desynchronising and choosing to sleep and/or
> > run at the same time? I can remove the idle time entirely by running
> > ocbench at nice 19 which means they are all forced to run at basically
> > the same time by the scheduler.
> >
> > Anyway the more important part is... Can you test this patch please? Dump
> > all the other patches I sent you post 045. Michael, if you could test too
> > please?
>
> OK, it's better now. All tasks equally run.

Excellent thank you very much (again!)

> X is still somewhat jerky, even 
> at nice -19. I'm sure it happens when it's waiting in the other array. We
> should definitely manage to get rid of this if we want to ensure low
> latency.

Yeah that would be correct. It's clearly possible to keep the whole design 
philosophy and priority system intact with SD and do away with the arrays if 
it becomes a continuous stream instead of two arrays but that requires some 
architectural changes. I've been concentrating on nailing all the remaining 
issues (and they kept cropping up as you've seen *blush*). However... I 
haven't quite figured out how to do that architectural change just yet either 
so let's just iron out all the bugs out of this now.

> Just FYI, the idle is often close to zero and the load is often close to
> 30, even if still fluctuating :

> Hoping this helps !

I can say without a shadow of a doubt it has helped :) I'll respin the patch 
slightly differently and post it and release as v0.46.

> Willy

-- 
-ck

Re: [ck] Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Con Kolivas]

On Monday 23 April 2007 00:35, Con Kolivas wrote:
> On Monday 23 April 2007 00:22, Willy Tarreau wrote:
> > X is still somewhat jerky, even
> > at nice -19. I'm sure it happens when it's waiting in the other array. We
> > should definitely manage to get rid of this if we want to ensure low
> > latency.
>
> Yeah that would be correct. It's clearly possible to keep the whole design
> philosophy and priority system intact with SD and do away with the arrays
> if it becomes a continuous stream instead of two arrays but that requires
> some architectural changes. I've been concentrating on nailing all the
> remaining issues (and they kept cropping up as you've seen *blush*).
> However... I haven't quite figured out how to do that architectural change
> just yet either so let's just iron out all the bugs out of this now.

By the way, Ingo et al, this is yet again an open invitation to suggest ideas, 
or better yet, provide code to do this with now that the core of SD is 
finally looking to be doing everything as expected within its constraints. 
I'm low on cycles and would appreciate the help. I'd prefer to leave 
everything that's queued in -mm as is for the moment before someone wants to 
take this into another wild direction.

Thanks!

-- 
-ck

Re: [ck] Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Michael Gerdau]

[-- Attachment #1: Type: text/plain, Size: 1085 bytes --]

> Anyway the more important part is... Can you test this patch please? Dump
> all the other patches I sent you post 045. Michael, if you could test too
> please?

Have it up running for 40 minutes now and my perljobs show a constant
cpu utilization of 100/50/50 in top most of the time. When the 100% job
goes down to e.g. 70% these 30% are immediately reclaimed by the other
two, i.e. the total sum of all three stays with 2% point of 200%.

From here it seems as if your latest patch did what is was supposed to :-)

Best,
Michael

PS: While these numbercrunching jobs were running I started another
kde session and have my children play supertux for 20 minutes. While
the system occasionally was not as responsive as it is when there
is little load, supertux remained very playable.
-- 
 Technosis GmbH, Geschäftsführer: Michael Gerdau, Tobias Dittmar
 Sitz Hamburg; HRB 89145 Amtsgericht Hamburg
 Vote against SPAM - see http://www.politik-digital.de/spam/
 Michael Gerdau       email: mgd@technosis.de
 GPG-keys available on request or at public keyserver

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [ck] Re: [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Con Kolivas]

On Monday 23 April 2007 00:27, Michael Gerdau wrote:
> > Anyway the more important part is... Can you test this patch please? Dump
> > all the other patches I sent you post 045. Michael, if you could test too
> > please?
>
> Have it up running for 40 minutes now and my perljobs show a constant
> cpu utilization of 100/50/50 in top most of the time. When the 100% job
> goes down to e.g. 70% these 30% are immediately reclaimed by the other
> two, i.e. the total sum of all three stays with 2% point of 200%.
>
> From here it seems as if your latest patch did what is was supposed to :-)

Excellent, thanks for testing. v0.46 with something close to this patch coming 
shortly.

> Best,
> Michael
>
> PS: While these numbercrunching jobs were running I started another
> kde session and have my children play supertux for 20 minutes. While
> the system occasionally was not as responsive as it is when there
> is little load, supertux remained very playable.

-- 
-ck

Re: [ck] [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Michael Gerdau]

[-- Attachment #1: Type: text/plain, Size: 1295 bytes --]

Hi Con,

I now have 2.6.21-rc7-sd-0.45 running on my Intel Core2 T7600 2.33
machine and there is something I don't understand.

For testing I have a Perl script that does some numbercrunching
and runs a couple of hours.

I have two scenarios
a) start the job via loops in a shellscript
b) start the job via a makefile (make -j 2)
that I run in parallel.

I watch the jobs via top and this is what I see:
Job a) quickly gets about 100% (- 0-2) while job b) creates two
perl jobs that both get 50% (- 0-2). I suppose it is expected
behaviour that the single perl job created via a) gets same same
share of the cpu as the two perl jobs created via b) together.

However occasionally cpu drops to 33% for all three perl jobs
while there is no other job visible in top (i.e. the sum drops
from 200% to 100%). After some time this changes back to 100/50/50.

How could this happen and would applying the other patch you
mailed to Willy Tarreau help tracking that down ?

Best wishes,
Michael
-- 
 Technosis GmbH, Geschäftsführer: Michael Gerdau, Tobias Dittmar
 Sitz Hamburg; HRB 89145 Amtsgericht Hamburg
 Vote against SPAM - see http://www.politik-digital.de/spam/
 Michael Gerdau       email: mgd@technosis.de
 GPG-keys available on request or at public keyserver

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [ck] [ANNOUNCE] Staircase Deadline cpu scheduler version 0.45

[Con Kolivas]

On Sunday 22 April 2007 18:02, Michael Gerdau wrote:
> Hi Con,
>
> I now have 2.6.21-rc7-sd-0.45 running on my Intel Core2 T7600 2.33
> machine and there is something I don't understand.
>
> For testing I have a Perl script that does some numbercrunching
> and runs a couple of hours.
>
> I have two scenarios
> a) start the job via loops in a shellscript
> b) start the job via a makefile (make -j 2)
> that I run in parallel.
>
> I watch the jobs via top and this is what I see:
> Job a) quickly gets about 100% (- 0-2) while job b) creates two
> perl jobs that both get 50% (- 0-2). I suppose it is expected
> behaviour that the single perl job created via a) gets same same
> share of the cpu as the two perl jobs created via b) together.
>
> However occasionally cpu drops to 33% for all three perl jobs
> while there is no other job visible in top (i.e. the sum drops
> from 200% to 100%). After some time this changes back to 100/50/50.
>
> How could this happen and would applying the other patch you
> mailed to Willy Tarreau help tracking that down ?

Thanks for report. That patch did not help Willy, and now you have confirmed 
there still is an SMP balancing problem too where it doesn't seem to keep all 
cpus busy. There's still a bug there in the smp balancing code and I'm 
reviewing it madly trying to find it. If anyone else knows this balancing 
code and is willing to help I'd be happy for feedback if they can see an 
obvious error. Likely thing is the runqueue is not being weighted at all 
despite being bust so the other runqueue doesn't try to take any tasks from 
it.

-- 
-ck