[PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Con Kolivas]

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

Hidden at the end of a thread titled "[PATCH] 2.5.72 O(1) interactivity 
bugfix" was a much improved patch for interactivity against 2.5.72 which 
seemed to be swallowed and never appeared on lkml so here it is again.

If a task is interactive it will declare itself in a short period and the 
max_sleep_avg being 10 seconds is too long for a task to be detected as such. 
Unfortunately decreasing the max_sleep_avg will quickly put a task onto the 
expired array if the task uses sustained cpu for a period. This makes X slow 
down after a little usage when the machine is under heavy load. 

This patch uses two settings to determine a task's interactivity, the old 
max_sleep_avg is now more of a sleep_avg "attack" and the new 
best_sleep_decay is the decay. Initially these have been set to 1 and 60 
seconds. Audio skipping is eliminated in my testing at heavy loads, and X 
does not slow down during sustained usage under very heavy load. Unlike my 
previous patch this one does not reset the sleep_avg of new forked processes.

Included as an attachment to prevent mailer mangling.

Testers required. A version for -ck will be created soon.

Con

[-- Attachment #2: patch-sleep_decay --]
[-- Type: text/x-diff, Size: 2127 bytes --]

diff -Naurp linux-2.5.72/kernel/sched.c linux-2.5.72-test/kernel/sched.c
--- linux-2.5.72/kernel/sched.c	2003-06-18 22:47:25.000000000 +1000
+++ linux-2.5.72-test/kernel/sched.c	2003-06-19 22:23:33.000000000 +1000
@@ -72,7 +72,8 @@
 #define EXIT_WEIGHT		3
 #define PRIO_BONUS_RATIO	25
 #define INTERACTIVE_DELTA	2
-#define MAX_SLEEP_AVG		(10*HZ)
+#define MAX_SLEEP_AVG		(HZ)
+#define BEST_SLEEP_DECAY	(60 * HZ)
 #define STARVATION_LIMIT	(10*HZ)
 #define NODE_THRESHOLD		125
 
@@ -318,7 +319,7 @@ static int effective_prio(task_t *p)
 	if (rt_task(p))
 		return p->prio;
 
-	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*p->sleep_avg/MAX_SLEEP_AVG/100 -
+	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*(p->best_sleep_avg/BEST_SLEEP_DECAY)/MAX_SLEEP_AVG/100 -
 			MAX_USER_PRIO*PRIO_BONUS_RATIO/100/2;
 
 	prio = p->static_prio - bonus;
@@ -371,6 +372,8 @@ static inline void activate_task(task_t 
 			sleep_avg = MAX_SLEEP_AVG;
 		if (p->sleep_avg != sleep_avg) {
 			p->sleep_avg = sleep_avg;
+			if ((sleep_avg * BEST_SLEEP_DECAY) > p->best_sleep_avg)
+				p->best_sleep_avg = sleep_avg * BEST_SLEEP_DECAY;
 			p->prio = effective_prio(p);
 		}
 	}
@@ -551,6 +554,7 @@ void wake_up_forked_process(task_t * p)
 	 */
 	current->sleep_avg = current->sleep_avg * PARENT_PENALTY / 100;
 	p->sleep_avg = p->sleep_avg * CHILD_PENALTY / 100;
+	p->best_sleep_avg = p->sleep_avg * BEST_SLEEP_DECAY;
 	p->prio = effective_prio(p);
 	set_task_cpu(p, smp_processor_id());
 
@@ -1200,6 +1204,8 @@ void scheduler_tick(int user_ticks, int 
 	 */
 	if (p->sleep_avg)
 		p->sleep_avg--;
+	if (p->best_sleep_avg)
+		p->best_sleep_avg--;
 	if (unlikely(rt_task(p))) {
 		/*
 		 * RR tasks need a special form of timeslice management.
diff -Naurp linux-2.5.72/include/linux/sched.h linux-2.5.72-test/include/linux/sched.h
--- linux-2.5.72/include/linux/sched.h	2003-06-18 22:47:19.000000000 +1000
+++ linux-2.5.72-test/include/linux/sched.h	2003-06-19 20:56:18.000000000 +1000
@@ -332,6 +332,7 @@ struct task_struct {
 
 	unsigned long sleep_avg;
 	unsigned long last_run;
+	unsigned long best_sleep_avg;
 
 	unsigned long policy;
 	unsigned long cpus_allowed;

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Mike Galbraith]

At 12:05 AM 6/20/2003 +1000, Con Kolivas wrote:

>Testers required. A version for -ck will be created soon.

That idea definitely needs some refinement.

Run test-starve.c, and try to login.  I'm not sure, but I don't think I've 
seen any task change more than one priority from what it started life 
at.  In test-starve's case, that's 16.  It's partner is at 16 as well, so 
it can't preempt (bad).  A dd if=/dev/zero of=/dev/null stays glued to 
21.  Repeated sh -c 'ps l $$'  bounces back and forth between 15 and 
21.  (maybe I should fly to Vegas.. when I try to login with test-starve 
running, I keep hitting 21:)

         -Mike 

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Con Kolivas]

On Fri, 20 Jun 2003 01:47, Mike Galbraith wrote:
> At 12:05 AM 6/20/2003 +1000, Con Kolivas wrote:
> >Testers required. A version for -ck will be created soon.
>
> That idea definitely needs some refinement.
>
> Run test-starve.c, and try to login.  I'm not sure, but I don't think I've
> seen any task change more than one priority from what it started life
> at.  In test-starve's case, that's 16.  It's partner is at 16 as well, so
> it can't preempt (bad).  A dd if=/dev/zero of=/dev/null stays glued to
> 21.  Repeated sh -c 'ps l $$'  bounces back and forth between 15 and
> 21.  (maybe I should fly to Vegas.. when I try to login with test-starve
> running, I keep hitting 21:)

Heh, sounds like you'll get to go there lose all your money come back and 
still be waiting :P

Too fast a woody that stays up too long?
Perhaps 2 seconds up and 10 down would be better than 1 up 60 down. I was just 
trying to make a point with those numbers; they were hardly tuned. Also 
perhaps the child penalty of 50 is now too low and IIRC the 95 used a long 
time ago may give the shell a better chance of firing up.

Con

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Con Kolivas]

On Fri, 20 Jun 2003 01:47, Mike Galbraith wrote:
> At 12:05 AM 6/20/2003 +1000, Con Kolivas wrote:
> >Testers required. A version for -ck will be created soon.
>
> That idea definitely needs some refinement.

Actually no it needs a bugfix even more than a refinement!

The best_sleep_decay should be 60, NOT 60*Hz

Con

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Con Kolivas]

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

On Fri, 20 Jun 2003 02:02, Con Kolivas wrote:
> On Fri, 20 Jun 2003 01:47, Mike Galbraith wrote:
> > At 12:05 AM 6/20/2003 +1000, Con Kolivas wrote:
> > >Testers required. A version for -ck will be created soon.
> >
> > That idea definitely needs some refinement.
>
> Actually no it needs a bugfix even more than a refinement!
>
> The best_sleep_decay should be 60, NOT 60*Hz

Here's a fixed patch.

Con

[-- Attachment #2: patch-sleep_decay-0306200203 --]
[-- Type: text/x-diff, Size: 2121 bytes --]

diff -Naurp linux-2.5.72/kernel/sched.c linux-2.5.72-test/kernel/sched.c
--- linux-2.5.72/kernel/sched.c	2003-06-18 22:47:25.000000000 +1000
+++ linux-2.5.72-test/kernel/sched.c	2003-06-19 22:23:33.000000000 +1000
@@ -72,7 +72,8 @@
 #define EXIT_WEIGHT		3
 #define PRIO_BONUS_RATIO	25
 #define INTERACTIVE_DELTA	2
-#define MAX_SLEEP_AVG		(10*HZ)
+#define MAX_SLEEP_AVG		(HZ)
+#define BEST_SLEEP_DECAY	(60)
 #define STARVATION_LIMIT	(10*HZ)
 #define NODE_THRESHOLD		125
 
@@ -318,7 +319,7 @@ static int effective_prio(task_t *p)
 	if (rt_task(p))
 		return p->prio;
 
-	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*p->sleep_avg/MAX_SLEEP_AVG/100 -
+	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*(p->best_sleep_avg/BEST_SLEEP_DECAY)/MAX_SLEEP_AVG/100 -
 			MAX_USER_PRIO*PRIO_BONUS_RATIO/100/2;

 	prio = p->static_prio - bonus;
@@ -371,6 +372,8 @@ static inline void activate_task(task_t 
 			sleep_avg = MAX_SLEEP_AVG;
 		if (p->sleep_avg != sleep_avg) {
 			p->sleep_avg = sleep_avg;
+			if ((sleep_avg * BEST_SLEEP_DECAY) > p->best_sleep_avg)
+				p->best_sleep_avg = sleep_avg * BEST_SLEEP_DECAY;
 			p->prio = effective_prio(p);
 		}
 	}
@@ -551,6 +554,7 @@ void wake_up_forked_process(task_t * p)
 	 */
 	current->sleep_avg = current->sleep_avg * PARENT_PENALTY / 100;
 	p->sleep_avg = p->sleep_avg * CHILD_PENALTY / 100;
+	p->best_sleep_avg = p->sleep_avg * BEST_SLEEP_DECAY;
 	p->prio = effective_prio(p);
 	set_task_cpu(p, smp_processor_id());
 
@@ -1200,6 +1204,8 @@ void scheduler_tick(int user_ticks, int 
 	 */
 	if (p->sleep_avg)
 		p->sleep_avg--;
+	if (p->best_sleep_avg)
+		p->best_sleep_avg--;
 	if (unlikely(rt_task(p))) {
 		/*
 		 * RR tasks need a special form of timeslice management.
diff -Naurp linux-2.5.72/include/linux/sched.h linux-2.5.72-test/include/linux/sched.h
--- linux-2.5.72/include/linux/sched.h	2003-06-18 22:47:19.000000000 +1000
+++ linux-2.5.72-test/include/linux/sched.h	2003-06-19 20:56:18.000000000 +1000
@@ -332,6 +332,7 @@ struct task_struct {
 
 	unsigned long sleep_avg;
 	unsigned long last_run;
+	unsigned long best_sleep_avg;
 
 	unsigned long policy;
 	unsigned long cpus_allowed;

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Andreas Boman]

On Thu, 2003-06-19 at 12:06, Con Kolivas wrote:
> On Fri, 20 Jun 2003 02:02, Con Kolivas wrote:
> > On Fri, 20 Jun 2003 01:47, Mike Galbraith wrote:
> > > At 12:05 AM 6/20/2003 +1000, Con Kolivas wrote:
> > > >Testers required. A version for -ck will be created soon.
> > >
> > > That idea definitely needs some refinement.
> >
> > Actually no it needs a bugfix even more than a refinement!
> >
> > The best_sleep_decay should be 60, NOT 60*Hz
> 
> Here's a fixed patch.

Ok, that doesnt really seem to change behavior much (from just a little
testing). I can still easily starve xmms by moving a window around over
mozilla or evolution (I suspect for thoose that use nautilus to draw the
desktop that would happen on an 'empty' desktop too..). 

With 2.5.72-mm1, HZ 1000 and MAX_SLEEP_AVG 2 that does *not* happen,
even with a cpu hog running (mpeg2enc) or during make -j20. However with
this kernel, after having moved a window around madly for a while the
mouse pointer is very laggy/jerky for atleast 30 sec after i release the
window (not so with your patch). 

I'm not hitting swap at all, so thats not a factor here.

	Andreas

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Con Kolivas]

On Fri, 20 Jun 2003 02:42, Andreas Boman wrote:
> On Thu, 2003-06-19 at 12:06, Con Kolivas wrote:
> > On Fri, 20 Jun 2003 02:02, Con Kolivas wrote:
> > > On Fri, 20 Jun 2003 01:47, Mike Galbraith wrote:
> > > > At 12:05 AM 6/20/2003 +1000, Con Kolivas wrote:
> > > > >Testers required. A version for -ck will be created soon.
> > > >
> > > > That idea definitely needs some refinement.
> > >
> > > Actually no it needs a bugfix even more than a refinement!
> > >
> > > The best_sleep_decay should be 60, NOT 60*Hz
> >
> > Here's a fixed patch.
>
> Ok, that doesnt really seem to change behavior much (from just a little
> testing). I can still easily starve xmms by moving a window around over
> mozilla or evolution (I suspect for thoose that use nautilus to draw the
> desktop that would happen on an 'empty' desktop too..).
>
> With 2.5.72-mm1, HZ 1000 and MAX_SLEEP_AVG 2 that does *not* happen,
> even with a cpu hog running (mpeg2enc) or during make -j20. However with
> this kernel, after having moved a window around madly for a while the
> mouse pointer is very laggy/jerky for atleast 30 sec after i release the
> window (not so with your patch).
>
> I'm not hitting swap at all, so thats not a factor here.

Ok well next thing to try is max_sleep_avg 2*HZ with my patch, possibly with 
best_sleep_decay 10

Con

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Con Kolivas]

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

On Fri, 20 Jun 2003 07:32, Andreas Boman wrote:
> On Thu, 2003-06-19 at 12:50, Con Kolivas wrote:
> > On Fri, 20 Jun 2003 02:42, Andreas Boman wrote:
> > > On Thu, 2003-06-19 at 12:06, Con Kolivas wrote:
> > > > On Fri, 20 Jun 2003 02:02, Con Kolivas wrote:
> > > > > On Fri, 20 Jun 2003 01:47, Mike Galbraith wrote:
> > > > > > At 12:05 AM 6/20/2003 +1000, Con Kolivas wrote:
> > > > > > >Testers required. A version for -ck will be created soon.
> > > > > >
> > > > > > That idea definitely needs some refinement.
> > > > >
> > > > > Actually no it needs a bugfix even more than a refinement!
> > > > >
> > > > > The best_sleep_decay should be 60, NOT 60*Hz
> > > >
> > > > Here's a fixed patch.
> > >
> > > Ok, that doesnt really seem to change behavior much (from just a little
> > > testing). I can still easily starve xmms by moving a window around over
> > > mozilla or evolution (I suspect for thoose that use nautilus to draw
> > > the desktop that would happen on an 'empty' desktop too..).
> > >
> > > With 2.5.72-mm1, HZ 1000 and MAX_SLEEP_AVG 2 that does *not* happen,
> > > even with a cpu hog running (mpeg2enc) or during make -j20. However
> > > with this kernel, after having moved a window around madly for a while
> > > the mouse pointer is very laggy/jerky for atleast 30 sec after i
> > > release the window (not so with your patch).
> > >
> > > I'm not hitting swap at all, so thats not a factor here.
> >
> > Ok well next thing to try is max_sleep_avg 2*HZ with my patch, possibly
> > with best_sleep_decay 10
>
> Ok, 2.5.72-mm2 + your patch + rml's setscheduler fix,  MAX_SLEEP_AVG
> 2*HZ, BEST_SLEEP_DECAY 10, HZ 1000
>
> This kernel is acting pretty good, I can still starve xmms if I start
> wiggeling a window around right about when a song changes in xmms, but
> it seems to get a timeslice in <20 sec while I'm still wiggeling the
> thing around (this is with make -j20 running as well). Repainting
> windows (evolution -its the slowest app to repaint, and the one its
> easiest to starve xmms with) post-wiggle sometimes takes while, not too
> bad on the whole though.
>
> The mouse pointer isn't all laggy post-window-wiggle like it was with
> -mm1, HZ 1000, MAX_SLEEP_AVG 2*HZ
>
> I have managed to get a few xmms skips when switching desktops (still
> with make -j20 running), but its pretty rare and not at all as
> predictable as it was without your patch (usually takes a few quick
> desktop changes within the first few seconds of playtime).
>
> I may have seen some strangeness while doing concurrent builds and
> similar things (make in linux tree, rpmbuild -ba mozilla.spec for
> example), the bunzip2 of the mozilla tree seemed to take _very_ long,
> and I'm not sure how the fairness is between theese processes now.. (I'm
> wondering if that may be something contest would be able to measure?)

The resolution of results in contest is not up to telling us that I'm afraid. 

> Playing a mpeg movie in mplayer (windowed or fullscreen) while doing the
> concurrent kernel and mozilla builds works just great without any
> noticable framedrops, and no sound skips.
>
> Doing the 'mad window wiggle' with the mplayer window (over evolution)
> will evenually cause some audio skips and/or frame drops, and the mouse
> pointer and framedropping may continue for a few (~15 tops) seconds
> after I stop moving that window around. Just moving the mplayer window
> around 'normally' doesnt cause any bad behavior (still with concurrent
> kernel and mozilla builds running).
>
> Basicly, for normal usage this kernel is acting *very* well here.

Great! Thanks for doing this testing. I've attached a patch with the updated 
figures and cc'ed lkml for others to test.

Con

[-- Attachment #2: patch-sleep_decay-0306201225 --]
[-- Type: text/x-diff, Size: 2125 bytes --]

diff -Naurp linux-2.5.72/kernel/sched.c linux-2.5.72-test/kernel/sched.c
--- linux-2.5.72/kernel/sched.c	2003-06-18 22:47:25.000000000 +1000
+++ linux-2.5.72-test/kernel/sched.c	2003-06-19 22:23:33.000000000 +1000
@@ -72,7 +72,8 @@
 #define EXIT_WEIGHT		3
 #define PRIO_BONUS_RATIO	25
 #define INTERACTIVE_DELTA	2
-#define MAX_SLEEP_AVG		(10*HZ)
+#define MAX_SLEEP_AVG		(2 * HZ)
+#define BEST_SLEEP_DECAY	(10)
 #define STARVATION_LIMIT	(10*HZ)
 #define NODE_THRESHOLD		125
 
@@ -318,7 +319,7 @@ static int effective_prio(task_t *p)
 	if (rt_task(p))
 		return p->prio;
 
-	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*p->sleep_avg/MAX_SLEEP_AVG/100 -
+	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*(p->best_sleep_avg/BEST_SLEEP_DECAY)/MAX_SLEEP_AVG/100 -
 			MAX_USER_PRIO*PRIO_BONUS_RATIO/100/2;

 	prio = p->static_prio - bonus;
@@ -371,6 +372,8 @@ static inline void activate_task(task_t 
 			sleep_avg = MAX_SLEEP_AVG;
 		if (p->sleep_avg != sleep_avg) {
 			p->sleep_avg = sleep_avg;
+			if ((sleep_avg * BEST_SLEEP_DECAY) > p->best_sleep_avg)
+				p->best_sleep_avg = sleep_avg * BEST_SLEEP_DECAY;
 			p->prio = effective_prio(p);
 		}
 	}
@@ -551,6 +554,7 @@ void wake_up_forked_process(task_t * p)
 	 */
 	current->sleep_avg = current->sleep_avg * PARENT_PENALTY / 100;
 	p->sleep_avg = p->sleep_avg * CHILD_PENALTY / 100;
+	p->best_sleep_avg = p->sleep_avg * BEST_SLEEP_DECAY;
 	p->prio = effective_prio(p);
 	set_task_cpu(p, smp_processor_id());
 
@@ -1200,6 +1204,8 @@ void scheduler_tick(int user_ticks, int 
 	 */
 	if (p->sleep_avg)
 		p->sleep_avg--;
+	if (p->best_sleep_avg)
+		p->best_sleep_avg--;
 	if (unlikely(rt_task(p))) {
 		/*
 		 * RR tasks need a special form of timeslice management.
diff -Naurp linux-2.5.72/include/linux/sched.h linux-2.5.72-test/include/linux/sched.h
--- linux-2.5.72/include/linux/sched.h	2003-06-18 22:47:19.000000000 +1000
+++ linux-2.5.72-test/include/linux/sched.h	2003-06-19 20:56:18.000000000 +1000
@@ -332,6 +332,7 @@ struct task_struct {
 
 	unsigned long sleep_avg;
 	unsigned long last_run;
+	unsigned long best_sleep_avg;
 
 	unsigned long policy;
 	unsigned long cpus_allowed;

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Mike Galbraith]

At 12:29 PM 6/20/2003 +1000, Con Kolivas wrote:
>On Fri, 20 Jun 2003 07:32, Andreas Boman wrote:
> >
> > Basicly, for normal usage this kernel is acting *very* well here.
>
>Great! Thanks for doing this testing. I've attached a patch with the updated
>figures and cc'ed lkml for others to test.

Thud is still much more effective at starvation than stock (zero decay 
during run phase), and a parallel kernel build still goes to 
max-interactive virtually instantly.

         -Mike 

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Con Kolivas]

[-- Attachment #1: clearsigned data --]
[-- Type: Text/Plain, Size: 1455 bytes --]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Fri, 20 Jun 2003 12:29, Con Kolivas wrote:
> On Fri, 20 Jun 2003 07:32, Andreas Boman wrote:
> > Basicly, for normal usage this kernel is acting *very* well here.
>
> Great! Thanks for doing this testing. I've attached a patch with the
> updated figures and cc'ed lkml for others to test.

This is the latest state of play with this patch. I have been developing it 
for -ck and ported it to 2.5 if anyone is still interested. Basically it will 
make a task interactive faster than vanilla and will prevent a task losing 
it's interactivity status for longer.

The added changes include a small workaround for integer division, and a new 
feature - non linear boosting.

I have implemented a sigmoid curve shaped boost to the priority boost. This 
makes it harder for tasks to get the largest priority boost or the greatest 
penalty. Basically cpu hungry tasks that remain cpu hungry but fluctuate in 
their sleep time due to lots of other tasks running will get less priority 
boost and fluctuate less in that boost also.

Feel free to test it and comment. Things to look for - the dreaded audio skip 
under load, and X remaining interactive during sustained use under load.

Con
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE+9bCLF6dfvkL3i1gRAgRsAKCS0jN/CEcLyuQxeJelUxLWXtAiTwCfQQuL
58jDY88RrOD0Lmr6ZYu/K50=
=00wP
-----END PGP SIGNATURE-----

[-- Attachment #2: patch-sleep_decay-0306222310 --]
[-- Type: text/x-diff, Size: 2461 bytes --]

diff -Naurp linux-2.5.72/include/linux/sched.h linux-2.5.72-test/include/linux/sched.h
--- linux-2.5.72/include/linux/sched.h	2003-06-18 22:47:19.000000000 +1000
+++ linux-2.5.72-test/include/linux/sched.h	2003-06-19 20:56:18.000000000 +1000
@@ -332,6 +332,7 @@ struct task_struct {
 
 	unsigned long sleep_avg;
 	unsigned long last_run;
+	unsigned long best_sleep_avg;
 
 	unsigned long policy;
 	unsigned long cpus_allowed;
diff -Naurp linux-2.5.72/kernel/sched.c linux-2.5.72-test/kernel/sched.c
--- linux-2.5.72/kernel/sched.c	2003-06-18 22:47:25.000000000 +1000
+++ linux-2.5.72-test/kernel/sched.c	2003-06-22 23:17:39.000000000 +1000
@@ -72,7 +72,8 @@
 #define EXIT_WEIGHT		3
 #define PRIO_BONUS_RATIO	25
 #define INTERACTIVE_DELTA	2
-#define MAX_SLEEP_AVG		(10*HZ)
+#define MAX_SLEEP_AVG		(2 * HZ)
+#define BEST_SLEEP_DECAY	(10)
 #define STARVATION_LIMIT	(10*HZ)
 #define NODE_THRESHOLD		125
 
@@ -313,12 +314,22 @@ static inline void enqueue_task(struct t
  */
 static int effective_prio(task_t *p)
 {
-	int bonus, prio;
+	int bonus, prio, scale = MAX_SLEEP_AVG / 2;
 
 	if (rt_task(p))
 		return p->prio;
 
-	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*p->sleep_avg/MAX_SLEEP_AVG/100 -
+	bonus = p->best_sleep_avg/BEST_SLEEP_DECAY;
+	if (bonus > MAX_SLEEP_AVG) bonus = MAX_SLEEP_AVG;
+
+	bonus -= scale;
+	if (bonus < 0) neg_flag = -1;
+	bonus *= bonus;
+	bonus /= scale;
+	bonus *= neg_flag;
+	bonus += scale;
+
+	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*bonus/MAX_SLEEP_AVG/100 -
 			MAX_USER_PRIO*PRIO_BONUS_RATIO/100/2;
 
 	prio = p->static_prio - bonus;
@@ -371,6 +382,8 @@ static inline void activate_task(task_t 
 			sleep_avg = MAX_SLEEP_AVG;
 		if (p->sleep_avg != sleep_avg) {
 			p->sleep_avg = sleep_avg;
+			if ((sleep_avg * BEST_SLEEP_DECAY) > p->best_sleep_avg)
+				p->best_sleep_avg = sleep_avg * (BEST_SLEEP_DECAY + 1) - 1;
 			p->prio = effective_prio(p);
 		}
 	}
@@ -551,6 +564,7 @@ void wake_up_forked_process(task_t * p)
 	 */
 	current->sleep_avg = current->sleep_avg * PARENT_PENALTY / 100;
 	p->sleep_avg = p->sleep_avg * CHILD_PENALTY / 100;
+	p->best_sleep_avg = p->sleep_avg * (BEST_SLEEP_DECAY + 1) - 1;
 	p->prio = effective_prio(p);
 	set_task_cpu(p, smp_processor_id());
 
@@ -1200,6 +1214,8 @@ void scheduler_tick(int user_ticks, int 
 	 */
 	if (p->sleep_avg)
 		p->sleep_avg--;
+	if (p->best_sleep_avg)
+		p->best_sleep_avg--;
 	if (unlikely(rt_task(p))) {
 		/*
 		 * RR tasks need a special form of timeslice management.

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Con Kolivas]

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

On Sun, 22 Jun 2003 23:35, Con Kolivas wrote:
> On Fri, 20 Jun 2003 12:29, Con Kolivas wrote:
> > On Fri, 20 Jun 2003 07:32, Andreas Boman wrote:
> > > Basicly, for normal usage this kernel is acting *very* well here.
> >
> > Great! Thanks for doing this testing. I've attached a patch with the
> > updated figures and cc'ed lkml for others to test.
>
> This is the latest state of play with this patch. I have been developing it
> for -ck and ported it to 2.5 if anyone is still interested. Basically it
> will make a task interactive faster than vanilla and will prevent a task
> losing it's interactivity status for longer.
>
> The added changes include a small workaround for integer division, and a
> new feature - non linear boosting.
>
> I have implemented a sigmoid curve shaped boost to the priority boost. This
> makes it harder for tasks to get the largest priority boost or the greatest
> penalty. Basically cpu hungry tasks that remain cpu hungry but fluctuate in
> their sleep time due to lots of other tasks running will get less priority
> boost and fluctuate less in that boost also.
>
> Feel free to test it and comment. Things to look for - the dreaded audio
> skip under load, and X remaining interactive during sustained use under
> load.

Woops my bad. Attached the correct one now.

Con

[-- Attachment #2: patch-sleep_decay-0306222343 --]
[-- Type: text/x-diff, Size: 2475 bytes --]

diff -Naurp linux-2.5.72/include/linux/sched.h linux-2.5.72-test/include/linux/sched.h
--- linux-2.5.72/include/linux/sched.h	2003-06-18 22:47:19.000000000 +1000
+++ linux-2.5.72-test/include/linux/sched.h	2003-06-19 20:56:18.000000000 +1000
@@ -332,6 +332,7 @@ struct task_struct {
 
 	unsigned long sleep_avg;
 	unsigned long last_run;
+	unsigned long best_sleep_avg;
 
 	unsigned long policy;
 	unsigned long cpus_allowed;
diff -Naurp linux-2.5.72/kernel/sched.c linux-2.5.72-test/kernel/sched.c
--- linux-2.5.72/kernel/sched.c	2003-06-18 22:47:25.000000000 +1000
+++ linux-2.5.72-test/kernel/sched.c	2003-06-22 23:17:39.000000000 +1000
@@ -72,7 +72,8 @@
 #define EXIT_WEIGHT		3
 #define PRIO_BONUS_RATIO	25
 #define INTERACTIVE_DELTA	2
-#define MAX_SLEEP_AVG		(10*HZ)
+#define MAX_SLEEP_AVG		(2 * HZ)
+#define BEST_SLEEP_DECAY	(10)
 #define STARVATION_LIMIT	(10*HZ)
 #define NODE_THRESHOLD		125
 
@@ -313,12 +314,22 @@ static inline void enqueue_task(struct t
  */
 static int effective_prio(task_t *p)
 {
-	int bonus, prio;
+	int bonus, prio, neg_flag = 1, scale = MAX_SLEEP_AVG / 2;
 
 	if (rt_task(p))
 		return p->prio;
 
-	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*p->sleep_avg/MAX_SLEEP_AVG/100 -
+	bonus = p->best_sleep_avg/BEST_SLEEP_DECAY;
+	if (bonus > MAX_SLEEP_AVG) bonus = MAX_SLEEP_AVG;
+
+	bonus -= scale;
+	if (bonus < 0) neg_flag = -1;
+	bonus *= bonus;
+	bonus /= scale;
+	bonus *= neg_flag;
+	bonus += scale;
+
+	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*bonus/MAX_SLEEP_AVG/100 -
 			MAX_USER_PRIO*PRIO_BONUS_RATIO/100/2;
 
 	prio = p->static_prio - bonus;
@@ -371,6 +382,8 @@ static inline void activate_task(task_t 
 			sleep_avg = MAX_SLEEP_AVG;
 		if (p->sleep_avg != sleep_avg) {
 			p->sleep_avg = sleep_avg;
+			if ((sleep_avg * BEST_SLEEP_DECAY) > p->best_sleep_avg)
+				p->best_sleep_avg = sleep_avg * (BEST_SLEEP_DECAY + 1) - 1;
 			p->prio = effective_prio(p);
 		}
 	}
@@ -551,6 +564,7 @@ void wake_up_forked_process(task_t * p)
 	 */
 	current->sleep_avg = current->sleep_avg * PARENT_PENALTY / 100;
 	p->sleep_avg = p->sleep_avg * CHILD_PENALTY / 100;
+	p->best_sleep_avg = p->sleep_avg * (BEST_SLEEP_DECAY + 1) - 1;
 	p->prio = effective_prio(p);
 	set_task_cpu(p, smp_processor_id());
 
@@ -1200,6 +1214,8 @@ void scheduler_tick(int user_ticks, int 
 	 */
 	if (p->sleep_avg)
 		p->sleep_avg--;
+	if (p->best_sleep_avg)
+		p->best_sleep_avg--;
 	if (unlikely(rt_task(p))) {
 		/*
 		 * RR tasks need a special form of timeslice management.

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Felipe Alfaro Solana]

On Sun, 2003-06-22 at 15:45, Con Kolivas wrote:

> > Feel free to test it and comment. Things to look for - the dreaded audio
> > skip under load, and X remaining interactive during sustained use under
> > load.

I must say this seems to be getting better, but I still prefer Mike's
patches. With the latest sleep decay patch and 2.5.72-mm3, I can still
easily starve XMMS audio for a long time (~5 seconds) on my 700Mhz
Pentium III laptoñ (running RHL9 and KDE 3.1.2) simply by running "while
true; do a=2; done" on a konsole window. Dragging a window fast enough
also starves XMMS for ~5 seconds just until the scheduler adjusts the
priorities.

XMMS is running with an effective priority of 15 (that's what top says).
"while true; do a=2; done" starts with a priority of 15 (which causes
XMMS to stop playing sound), then it is detected as a CPU hog and every
second its priority is increased by one. When its priority reaches 20,
XMMS starts playing again.

When I move windows around fast enough. the X server starts with a
priority of 15, starving XMMS. If I keep moving windows around for a
long time, X's priority starts increasing by one, until it reaches 20.
At this moment, it stops disturbing XMMS audio playback.

I've been playing with scheduler parameters, mainly by reducing
MAX_SLEEP_AVG to (HZ) and STARVATION_LIMIT to (HZ). This seems to help a
lot, although I can still make XMMS skip sound every once a bit.
However, mplayer is a really hard one: I have been unable to make it
skip sound yet.

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Con Kolivas]

On Mon, 23 Jun 2003 01:40, Felipe Alfaro Solana wrote:
> On Sun, 2003-06-22 at 15:45, Con Kolivas wrote:
> > > Feel free to test it and comment. Things to look for - the dreaded
> > > audio skip under load, and X remaining interactive during sustained use
> > > under load.
>
> I must say this seems to be getting better, but I still prefer Mike's
> patches. With the latest sleep decay patch and 2.5.72-mm3, I can still
> easily starve XMMS audio for a long time (~5 seconds) on my 700Mhz
> Pentium III laptoñ (running RHL9 and KDE 3.1.2) simply by running "while
> true; do a=2; done" on a konsole window. Dragging a window fast enough
> also starves XMMS for ~5 seconds just until the scheduler adjusts the
> priorities.
>
> XMMS is running with an effective priority of 15 (that's what top says).
> "while true; do a=2; done" starts with a priority of 15 (which causes
> XMMS to stop playing sound), then it is detected as a CPU hog and every
> second its priority is increased by one. When its priority reaches 20,
> XMMS starts playing again.
>
> When I move windows around fast enough. the X server starts with a
> priority of 15, starving XMMS. If I keep moving windows around for a
> long time, X's priority starts increasing by one, until it reaches 20.
> At this moment, it stops disturbing XMMS audio playback.
>
> I've been playing with scheduler parameters, mainly by reducing
> MAX_SLEEP_AVG to (HZ) and STARVATION_LIMIT to (HZ). This seems to help a
> lot, although I can still make XMMS skip sound every once a bit.
> However, mplayer is a really hard one: I have been unable to make it
> skip sound yet.

Yes Mike's patches are definitely better. My patches are designed for the 
2.4-ck patchset which has other workarounds that augment this patch; however 
these workarounds are harder to stomach for mainstream kernels (read nasty 
hacks). I thought I'd offer the not so nasty sleep_decay patch in 2.5 form 
for perusal and comments since people are more willing to test 2.5 patches.

Con

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Felipe Alfaro Solana]

On Sun, 2003-06-22 at 17:58, Con Kolivas wrote:
> On Mon, 23 Jun 2003 01:40, Felipe Alfaro Solana wrote:
> > On Sun, 2003-06-22 at 15:45, Con Kolivas wrote:
> > > > Feel free to test it and comment. Things to look for - the dreaded
> > > > audio skip under load, and X remaining interactive during sustained use
> > > > under load.
> >
> > I must say this seems to be getting better, but I still prefer Mike's
> > patches. With the latest sleep decay patch and 2.5.72-mm3, I can still
> > easily starve XMMS audio for a long time (~5 seconds) on my 700Mhz
> > Pentium III laptoñ (running RHL9 and KDE 3.1.2) simply by running "while
> > true; do a=2; done" on a konsole window. Dragging a window fast enough
> > also starves XMMS for ~5 seconds just until the scheduler adjusts the
> > priorities.
> >
> > XMMS is running with an effective priority of 15 (that's what top says).
> > "while true; do a=2; done" starts with a priority of 15 (which causes
> > XMMS to stop playing sound), then it is detected as a CPU hog and every
> > second its priority is increased by one. When its priority reaches 20,
> > XMMS starts playing again.
> >
> > When I move windows around fast enough. the X server starts with a
> > priority of 15, starving XMMS. If I keep moving windows around for a
> > long time, X's priority starts increasing by one, until it reaches 20.
> > At this moment, it stops disturbing XMMS audio playback.
> >
> > I've been playing with scheduler parameters, mainly by reducing
> > MAX_SLEEP_AVG to (HZ) and STARVATION_LIMIT to (HZ). This seems to help a
> > lot, although I can still make XMMS skip sound every once a bit.
> > However, mplayer is a really hard one: I have been unable to make it
> > skip sound yet.
> 
> Yes Mike's patches are definitely better. My patches are designed for the 
> 2.4-ck patchset which has other workarounds that augment this patch; however 
> these workarounds are harder to stomach for mainstream kernels (read nasty 
> hacks). I thought I'd offer the not so nasty sleep_decay patch in 2.5 form 
> for perusal and comments since people are more willing to test 2.5 patches.

Well, it's nice to know.
I'm willing to test nearly any 2.5 patch. So, I'll gladly test any other
ideas or patches you (or others) might have.
Thanks!

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Con Kolivas]

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

On Mon, 23 Jun 2003 02:14, Felipe Alfaro Solana wrote:
> On Sun, 2003-06-22 at 17:58, Con Kolivas wrote:
> > On Mon, 23 Jun 2003 01:40, Felipe Alfaro Solana wrote:
> > > On Sun, 2003-06-22 at 15:45, Con Kolivas wrote:
> > > > > Feel free to test it and comment. Things to look for - the dreaded
> > > > > audio skip under load, and X remaining interactive during sustained
> > > > > use under load.
> > >
> > > I must say this seems to be getting better, but I still prefer Mike's
> > > patches. With the latest sleep decay patch and 2.5.72-mm3, I can still
> > > easily starve XMMS audio for a long time (~5 seconds) on my 700Mhz
> > > Pentium III laptoñ (running RHL9 and KDE 3.1.2) simply by running
> > > "while true; do a=2; done" on a konsole window. Dragging a window fast
> > > enough also starves XMMS for ~5 seconds just until the scheduler
> > > adjusts the priorities.
> > >
> > > XMMS is running with an effective priority of 15 (that's what top
> > > says). "while true; do a=2; done" starts with a priority of 15 (which
> > > causes XMMS to stop playing sound), then it is detected as a CPU hog
> > > and every second its priority is increased by one. When its priority
> > > reaches 20, XMMS starts playing again.
> > >
> > > When I move windows around fast enough. the X server starts with a
> > > priority of 15, starving XMMS. If I keep moving windows around for a
> > > long time, X's priority starts increasing by one, until it reaches 20.
> > > At this moment, it stops disturbing XMMS audio playback.
> > >
> > > I've been playing with scheduler parameters, mainly by reducing
> > > MAX_SLEEP_AVG to (HZ) and STARVATION_LIMIT to (HZ). This seems to help
> > > a lot, although I can still make XMMS skip sound every once a bit.
> > > However, mplayer is a really hard one: I have been unable to make it
> > > skip sound yet.
> >
> > Yes Mike's patches are definitely better. My patches are designed for the
> > 2.4-ck patchset which has other workarounds that augment this patch;
> > however these workarounds are harder to stomach for mainstream kernels
> > (read nasty hacks). I thought I'd offer the not so nasty sleep_decay
> > patch in 2.5 form for perusal and comments since people are more willing
> > to test 2.5 patches.
>
> Well, it's nice to know.
> I'm willing to test nearly any 2.5 patch. So, I'll gladly test any other
> ideas or patches you (or others) might have.

ANY?

Ok well I guess I have to give away my secret then. This is the change that 
turns 2.5 into a desktop kernel. Note the very slight change to Ingo's addon 
;-)

Con

[-- Attachment #2: patch-o1int-9396230721 --]
[-- Type: text/x-diff, Size: 3350 bytes --]

diff -Naurp linux-2.5.72/include/linux/sched.h linux-2.5.72-test/include/linux/sched.h
--- linux-2.5.72/include/linux/sched.h	2003-06-18 22:47:19.000000000 +1000
+++ linux-2.5.72-test/include/linux/sched.h	2003-06-19 20:56:18.000000000 +1000
@@ -332,6 +332,7 @@ struct task_struct {
 
 	unsigned long sleep_avg;
 	unsigned long last_run;
+	unsigned long best_sleep_avg;
 
 	unsigned long policy;
 	unsigned long cpus_allowed;
--- linux-2.5.72/kernel/sched.c	2003-06-18 22:47:25.000000000 +1000
+++ linux-2.5.72-test/kernel/sched.c	2003-06-23 07:21:07.000000000 +1000
@@ -72,7 +72,8 @@
 #define EXIT_WEIGHT		3
 #define PRIO_BONUS_RATIO	25
 #define INTERACTIVE_DELTA	2
-#define MAX_SLEEP_AVG		(10*HZ)
+#define MAX_SLEEP_AVG		(2 * HZ)
+#define BEST_SLEEP_DECAY	(10)
 #define STARVATION_LIMIT	(10*HZ)
 #define NODE_THRESHOLD		125
 
@@ -313,12 +314,22 @@ static inline void enqueue_task(struct t
  */
 static int effective_prio(task_t *p)
 {
-	int bonus, prio;
+	int bonus, prio, scale = MAX_SLEEP_AVG / 2;
 
 	if (rt_task(p))
 		return p->prio;
 
-	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*p->sleep_avg/MAX_SLEEP_AVG/100 -
+	bonus = p->best_sleep_avg/BEST_SLEEP_DECAY;
+	if (bonus > MAX_SLEEP_AVG) bonus = MAX_SLEEP_AVG;
+
+	bonus -= scale;
+	if (bonus < 0) neg_flag = -1;
+	bonus *= bonus;
+	bonus /= scale;
+	bonus *= neg_flag;
+	bonus += scale;
+
+	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*bonus/MAX_SLEEP_AVG/100 -
 			MAX_USER_PRIO*PRIO_BONUS_RATIO/100/2;
 
 	prio = p->static_prio - bonus;
@@ -371,6 +382,8 @@ static inline void activate_task(task_t 
 			sleep_avg = MAX_SLEEP_AVG;
 		if (p->sleep_avg != sleep_avg) {
 			p->sleep_avg = sleep_avg;
+			if ((sleep_avg * BEST_SLEEP_DECAY) > p->best_sleep_avg)
+				p->best_sleep_avg = sleep_avg * (BEST_SLEEP_DECAY + 1) - 1;
 			p->prio = effective_prio(p);
 		}
 	}
@@ -551,6 +564,7 @@ void wake_up_forked_process(task_t * p)
 	 */
 	current->sleep_avg = current->sleep_avg * PARENT_PENALTY / 100;
 	p->sleep_avg = p->sleep_avg * CHILD_PENALTY / 100;
+	p->best_sleep_avg = p->sleep_avg * (BEST_SLEEP_DECAY + 1) - 1;
 	p->prio = effective_prio(p);
 	set_task_cpu(p, smp_processor_id());
 
@@ -1200,6 +1214,8 @@ void scheduler_tick(int user_ticks, int 
 	 */
 	if (p->sleep_avg)
 		p->sleep_avg--;
+	if (p->best_sleep_avg)
+		p->best_sleep_avg--;
 	if (unlikely(rt_task(p))) {
 		/*
 		 * RR tasks need a special form of timeslice management.
@@ -1229,6 +1245,27 @@ void scheduler_tick(int user_ticks, int 
 			enqueue_task(p, rq->expired);
 		} else
 			enqueue_task(p, rq->active);
+	} else {
+		/*
+		 * Prevent a too long timeslice allowing a task to monopolize
+		 * the CPU. We do this by splitting up the timeslice into
+		 * smaller pieces.
+		 *
+		 * Note: this does not mean the task's timeslices expire or
+		 * get lost in any way, they just might be preempted by
+		 * another task of equal priority. (one with higher
+		 * priority would have preempted this task already.) We
+		 * requeue this task to the end of the list on this priority
+		 * level, which is in essence a round-robin of tasks with
+		 * equal priority.
+		 */
+		if (!(p->time_slice % MIN_TIMESLICE) &&
+			       		(p->array == rq->active)) {
+			dequeue_task(p, rq->active);
+			set_tsk_need_resched(p);
+			p->prio = effective_prio(p);
+			enqueue_task(p, rq->active);
+		}
 	}
 out_unlock:
 	spin_unlock(&rq->lock);

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Con Kolivas]

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

On Mon, 23 Jun 2003 07:24, Con Kolivas wrote:
> On Mon, 23 Jun 2003 02:14, Felipe Alfaro Solana wrote:
> > On Sun, 2003-06-22 at 17:58, Con Kolivas wrote:
> > > On Mon, 23 Jun 2003 01:40, Felipe Alfaro Solana wrote:
> > > > On Sun, 2003-06-22 at 15:45, Con Kolivas wrote:
> > > > > > Feel free to test it and comment. Things to look for - the
> > > > > > dreaded audio skip under load, and X remaining interactive during
> > > > > > sustained use under load.
> > > >
> > > > I must say this seems to be getting better, but I still prefer Mike's
> > > > patches. With the latest sleep decay patch and 2.5.72-mm3, I can
> > > > still easily starve XMMS audio for a long time (~5 seconds) on my
> > > > 700Mhz Pentium III laptoñ (running RHL9 and KDE 3.1.2) simply by
> > > > running "while true; do a=2; done" on a konsole window. Dragging a
> > > > window fast enough also starves XMMS for ~5 seconds just until the
> > > > scheduler adjusts the priorities.
> > > >
> > > > XMMS is running with an effective priority of 15 (that's what top
> > > > says). "while true; do a=2; done" starts with a priority of 15 (which
> > > > causes XMMS to stop playing sound), then it is detected as a CPU hog
> > > > and every second its priority is increased by one. When its priority
> > > > reaches 20, XMMS starts playing again.
> > > >
> > > > When I move windows around fast enough. the X server starts with a
> > > > priority of 15, starving XMMS. If I keep moving windows around for a
> > > > long time, X's priority starts increasing by one, until it reaches
> > > > 20. At this moment, it stops disturbing XMMS audio playback.
> > > >
> > > > I've been playing with scheduler parameters, mainly by reducing
> > > > MAX_SLEEP_AVG to (HZ) and STARVATION_LIMIT to (HZ). This seems to
> > > > help a lot, although I can still make XMMS skip sound every once a
> > > > bit. However, mplayer is a really hard one: I have been unable to
> > > > make it skip sound yet.
> > >
> > > Yes Mike's patches are definitely better. My patches are designed for
> > > the 2.4-ck patchset which has other workarounds that augment this
> > > patch; however these workarounds are harder to stomach for mainstream
> > > kernels (read nasty hacks). I thought I'd offer the not so nasty
> > > sleep_decay patch in 2.5 form for perusal and comments since people are
> > > more willing to test 2.5 patches.
> >
> > Well, it's nice to know.
> > I'm willing to test nearly any 2.5 patch. So, I'll gladly test any other
> > ideas or patches you (or others) might have.
>
> ANY?
>
> Ok well I guess I have to give away my secret then. This is the change that
> turns 2.5 into a desktop kernel. Note the very slight change to Ingo's
> addon ;-)

Damn did it again.
Here's the real one.

[-- Attachment #2: patch-o1int-9396230736 --]
[-- Type: text/x-diff, Size: 3364 bytes --]

diff -Naurp linux-2.5.72/include/linux/sched.h linux-2.5.72-test/include/linux/sched.h
--- linux-2.5.72/include/linux/sched.h	2003-06-18 22:47:19.000000000 +1000
+++ linux-2.5.72-test/include/linux/sched.h	2003-06-19 20:56:18.000000000 +1000
@@ -332,6 +332,7 @@ struct task_struct {
 
 	unsigned long sleep_avg;
 	unsigned long last_run;
+	unsigned long best_sleep_avg;
 
 	unsigned long policy;
 	unsigned long cpus_allowed;
--- linux-2.5.72/kernel/sched.c	2003-06-18 22:47:25.000000000 +1000
+++ linux-2.5.72-test/kernel/sched.c	2003-06-23 07:21:07.000000000 +1000
@@ -72,7 +72,8 @@
 #define EXIT_WEIGHT		3
 #define PRIO_BONUS_RATIO	25
 #define INTERACTIVE_DELTA	2
-#define MAX_SLEEP_AVG		(10*HZ)
+#define MAX_SLEEP_AVG		(2 * HZ)
+#define BEST_SLEEP_DECAY	(10)
 #define STARVATION_LIMIT	(10*HZ)
 #define NODE_THRESHOLD		125
 
@@ -313,12 +314,22 @@ static inline void enqueue_task(struct t
  */
 static int effective_prio(task_t *p)
 {
-	int bonus, prio;
+	int bonus, prio, neg_flag = 1, scale = MAX_SLEEP_AVG / 2;
 
 	if (rt_task(p))
 		return p->prio;
 
-	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*p->sleep_avg/MAX_SLEEP_AVG/100 -
+	bonus = p->best_sleep_avg/BEST_SLEEP_DECAY;
+	if (bonus > MAX_SLEEP_AVG) bonus = MAX_SLEEP_AVG;
+
+	bonus -= scale;
+	if (bonus < 0) neg_flag = -1;
+	bonus *= bonus;
+	bonus /= scale;
+	bonus *= neg_flag;
+	bonus += scale;
+
+	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*bonus/MAX_SLEEP_AVG/100 -
 			MAX_USER_PRIO*PRIO_BONUS_RATIO/100/2;
 
 	prio = p->static_prio - bonus;
@@ -371,6 +382,8 @@ static inline void activate_task(task_t 
 			sleep_avg = MAX_SLEEP_AVG;
 		if (p->sleep_avg != sleep_avg) {
 			p->sleep_avg = sleep_avg;
+			if ((sleep_avg * BEST_SLEEP_DECAY) > p->best_sleep_avg)
+				p->best_sleep_avg = sleep_avg * (BEST_SLEEP_DECAY + 1) - 1;
 			p->prio = effective_prio(p);
 		}
 	}
@@ -551,6 +564,7 @@ void wake_up_forked_process(task_t * p)
 	 */
 	current->sleep_avg = current->sleep_avg * PARENT_PENALTY / 100;
 	p->sleep_avg = p->sleep_avg * CHILD_PENALTY / 100;
+	p->best_sleep_avg = p->sleep_avg * (BEST_SLEEP_DECAY + 1) - 1;
 	p->prio = effective_prio(p);
 	set_task_cpu(p, smp_processor_id());
 
@@ -1200,6 +1214,8 @@ void scheduler_tick(int user_ticks, int 
 	 */
 	if (p->sleep_avg)
 		p->sleep_avg--;
+	if (p->best_sleep_avg)
+		p->best_sleep_avg--;
 	if (unlikely(rt_task(p))) {
 		/*
 		 * RR tasks need a special form of timeslice management.
@@ -1229,6 +1245,27 @@ void scheduler_tick(int user_ticks, int 
 			enqueue_task(p, rq->expired);
 		} else
 			enqueue_task(p, rq->active);
+	} else {
+		/*
+		 * Prevent a too long timeslice allowing a task to monopolize
+		 * the CPU. We do this by splitting up the timeslice into
+		 * smaller pieces.
+		 *
+		 * Note: this does not mean the task's timeslices expire or
+		 * get lost in any way, they just might be preempted by
+		 * another task of equal priority. (one with higher
+		 * priority would have preempted this task already.) We
+		 * requeue this task to the end of the list on this priority
+		 * level, which is in essence a round-robin of tasks with
+		 * equal priority.
+		 */
+		if (!(p->time_slice % MIN_TIMESLICE) &&
+			       		(p->array == rq->active)) {
+			dequeue_task(p, rq->active);
+			set_tsk_need_resched(p);
+			p->prio = effective_prio(p);
+			enqueue_task(p, rq->active);
+		}
 	}
 out_unlock:
 	spin_unlock(&rq->lock);

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Felipe Alfaro Solana]

On Sun, 2003-06-22 at 23:37, Con Kolivas wrote:
> > > > Yes Mike's patches are definitely better. My patches are designed for
> > > > the 2.4-ck patchset which has other workarounds that augment this
> > > > patch; however these workarounds are harder to stomach for mainstream
> > > > kernels (read nasty hacks). I thought I'd offer the not so nasty
> > > > sleep_decay patch in 2.5 form for perusal and comments since people are
> > > > more willing to test 2.5 patches.
> > >
> > > Well, it's nice to know.
> > > I'm willing to test nearly any 2.5 patch. So, I'll gladly test any other
> > > ideas or patches you (or others) might have.
> >
> > ANY?
> >
> > Ok well I guess I have to give away my secret then. This is the change that
> > turns 2.5 into a desktop kernel. Note the very slight change to Ingo's
> > addon ;-)

OK, I've tested this patch but I still can easily make XMMS starve for
briefs periods of time and can also make X to start behaving jerky. If I
put the system under load (while true; do a=2; done) dragging a window
fast enough for a long time makes the X server priority decreases to a
point where the window moving is not smooth and very jerky. If I stop
dragging the window, after a while, the X server prority is restablished
and I can start all over again.

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Con Kolivas]

On Mon, 23 Jun 2003 21:16, Felipe Alfaro Solana wrote:
> On Sun, 2003-06-22 at 23:37, Con Kolivas wrote:
> > > > > Yes Mike's patches are definitely better. My patches are designed
> > > > > for the 2.4-ck patchset which has other workarounds that augment
> > > > > this patch; however these workarounds are harder to stomach for
> > > > > mainstream kernels (read nasty hacks). I thought I'd offer the not
> > > > > so nasty sleep_decay patch in 2.5 form for perusal and comments
> > > > > since people are more willing to test 2.5 patches.
> > > >
> > > > Well, it's nice to know.
> > > > I'm willing to test nearly any 2.5 patch. So, I'll gladly test any
> > > > other ideas or patches you (or others) might have.
> > >
> > > ANY?
> > >
> > > Ok well I guess I have to give away my secret then. This is the change
> > > that turns 2.5 into a desktop kernel. Note the very slight change to
> > > Ingo's addon ;-)
>
> OK, I've tested this patch but I still can easily make XMMS starve for
> briefs periods of time and can also make X to start behaving jerky. If I
> put the system under load (while true; do a=2; done) dragging a window
> fast enough for a long time makes the X server priority decreases to a
> point where the window moving is not smooth and very jerky. If I stop
> dragging the window, after a while, the X server prority is restablished
> and I can start all over again.

Yeah sure if you do it for long enough. Just change the best_sleep_decay from 
10 seconds to something like 60 if you plan to do that. Are you really going 
to madly drag a window around for 10 seconds? If so, change it to 60. That's 
how it works.

You didn't specify how you made XMMS starve easily... I don't know if I have 
an answer for that, but I need to know the question.

Con

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Mike Galbraith]

At 02:02 AM 6/20/2003 +1000, Con Kolivas wrote:
>On Fri, 20 Jun 2003 01:47, Mike Galbraith wrote:
> > At 12:05 AM 6/20/2003 +1000, Con Kolivas wrote:
> > >Testers required. A version for -ck will be created soon.
> >
> > That idea definitely needs some refinement.
>
>Actually no it needs a bugfix even more than a refinement!
>
>The best_sleep_decay should be 60, NOT 60*Hz

Ok.  Now it acts as you described.

thud is also now THUD though, and a parallel kernel build goes insane 
pretty much instantly.  On the bright side, process_load seems to have lost 
it's ability to crawl up (under X) and starve new processes forever.

         -Mike 

Re: [PATCH] sleep_decay for interactivity 2.5.72 - testers needed

[Andreas Boman]

On Thu, 2003-06-19 at 13:31, Mike Galbraith wrote:
> At 02:02 AM 6/20/2003 +1000, Con Kolivas wrote:
> >On Fri, 20 Jun 2003 01:47, Mike Galbraith wrote:
> > > At 12:05 AM 6/20/2003 +1000, Con Kolivas wrote:
> > > >Testers required. A version for -ck will be created soon.
> > >
> > > That idea definitely needs some refinement.
> >
> >Actually no it needs a bugfix even more than a refinement!
> >
> >The best_sleep_decay should be 60, NOT 60*Hz
> 
> Ok.  Now it acts as you described.
> 
> thud is also now THUD though, and a parallel kernel build goes insane 
> pretty much instantly.  On the bright side, process_load seems to have lost 
> it's ability to crawl up (under X) and starve new processes forever.
> 

Hmm, I'm still able to completely starve xmms by just moving a window
around ontop of evolution or mozilla though (not possible without this
patch).

	Andreas