[PATCH] O1int 0307021808 for interactivity

[PATCH] O1int 0307021808 for interactivity

[Con Kolivas]

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

This latest patch I'm formally announcing has the base O1int changes so far 
but includes new semantics for freshly started applications so they can 
become interactive very rapidly even during heavy load. This addresses the 
"slow to start new apps" evident in O1int so far.

Please test this one and note given just how rapidly things can become 
interactive it may have regressions in other settings.

This performs better in all settings than any previous one I've posted in my 
testing, but hardware differs substantially!

The latest should always be found:
http://kernel.kolivas.org/2.5

Con

[-- Attachment #2: patch-O1int-0307021808 --]
[-- Type: text/x-diff, Size: 3728 bytes --]

--- linux-2.5.73/include/linux/sched.h	2003-06-30 10:06:40.000000000 +1000
+++ linux-2.5.73-test/include/linux/sched.h	2003-07-01 11:56:08.000000000 +1000
@@ -336,6 +336,7 @@ struct task_struct {
 	prio_array_t *array;
 
 	unsigned long sleep_avg;
+	unsigned long avg_start;
 	unsigned long last_run;
 
 	unsigned long policy;
--- linux-2.5.73/kernel/sched.c	2003-06-30 10:06:40.000000000 +1000
+++ linux-2.5.73-test/kernel/sched.c	2003-07-02 17:57:04.000000000 +1000
@@ -72,6 +72,7 @@
 #define EXIT_WEIGHT		3
 #define PRIO_BONUS_RATIO	25
 #define INTERACTIVE_DELTA	2
+#define MIN_SLEEP_AVG		(HZ)
 #define MAX_SLEEP_AVG		(10*HZ)
 #define STARVATION_LIMIT	(10*HZ)
 #define NODE_THRESHOLD		125
@@ -297,6 +298,21 @@ static inline void enqueue_task(struct t
 	p->array = array;
 }
 
+static inline void normalise_sleep(task_t *p)
+{
+	int old_avg_time, new_avg_time;
+	new_avg_time = MIN_SLEEP_AVG;
+	old_avg_time = jiffies - p->avg_start;
+	if (old_avg_time < new_avg_time) return;
+
+	if (p->sleep_avg > MAX_SLEEP_AVG)
+		p->sleep_avg = MAX_SLEEP_AVG;
+	if (old_avg_time > MAX_SLEEP_AVG)
+		old_avg_time = MAX_SLEEP_AVG;
+	p->sleep_avg = p->sleep_avg * new_avg_time / old_avg_time;
+	p->avg_start = jiffies - new_avg_time;
+}
+
 /*
  * effective_prio - return the priority that is based on the static
  * priority but is modified by bonuses/penalties.
@@ -314,11 +330,23 @@ static inline void enqueue_task(struct t
 static int effective_prio(task_t *p)
 {
 	int bonus, prio;
+	long sleep_period;
 
 	if (rt_task(p))
 		return p->prio;
 
-	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*p->sleep_avg/MAX_SLEEP_AVG/100 -
+	sleep_period = jiffies - p->avg_start;
+
+	if (!sleep_period)
+		return p->static_prio;
+
+	if (sleep_period > MAX_SLEEP_AVG)
+		sleep_period = MAX_SLEEP_AVG;
+
+	if (p->sleep_avg > sleep_period)
+		sleep_period = p->sleep_avg;
+
+	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*p->sleep_avg/sleep_period/100 -
 			MAX_USER_PRIO*PRIO_BONUS_RATIO/100/2;
 
 	prio = p->static_prio - bonus;
@@ -349,7 +377,7 @@ static inline void activate_task(task_t 
 	long sleep_time = jiffies - p->last_run - 1;
 
 	if (sleep_time > 0) {
-		int sleep_avg;
+		int runtime = jiffies - p->avg_start;
 
 		/*
 		 * This code gives a bonus to interactive tasks.
@@ -359,7 +387,10 @@ static inline void activate_task(task_t 
 		 * spends sleeping, the higher the average gets - and the
 		 * higher the priority boost gets as well.
 		 */
-		sleep_avg = p->sleep_avg + sleep_time;
+		p->sleep_avg += sleep_time;
+		if (runtime < MAX_SLEEP_AVG)
+			p->sleep_avg += (runtime - p->sleep_avg) * (MAX_SLEEP_AVG - runtime)/MAX_SLEEP_AVG;
+
 
 		/*
 		 * 'Overflow' bonus ticks go to the waker as well, so the
@@ -367,12 +398,17 @@ static inline void activate_task(task_t 
 		 * boosting tasks that are related to maximum-interactive
 		 * tasks.
 		 */
-		if (sleep_avg > MAX_SLEEP_AVG)
-			sleep_avg = MAX_SLEEP_AVG;
-		if (p->sleep_avg != sleep_avg) {
-			p->sleep_avg = sleep_avg;
-			p->prio = effective_prio(p);
+		if (p->sleep_avg > MAX_SLEEP_AVG * 12/10)
+			p->sleep_avg = MAX_SLEEP_AVG * 11/10;
+		if (sleep_time > MIN_SLEEP_AVG){
+			p->avg_start = jiffies - MIN_SLEEP_AVG;
+			p->sleep_avg = MIN_SLEEP_AVG / 2;
 		}
+		if (unlikely(p->avg_start > jiffies)){
+			p->avg_start = jiffies;
+			p->sleep_avg = 0;
+		}
+		p->prio = effective_prio(p);
 	}
 	__activate_task(p, rq);
 }
@@ -550,6 +586,8 @@ void wake_up_forked_process(task_t * p)
 	 * from forking tasks that are max-interactive.
 	 */
 	current->sleep_avg = current->sleep_avg * PARENT_PENALTY / 100;
+	p->avg_start = current->avg_start;
+	normalise_sleep(p);
 	p->sleep_avg = p->sleep_avg * CHILD_PENALTY / 100;
 	p->prio = effective_prio(p);
 	set_task_cpu(p, smp_processor_id());

Re: [PATCH] O1int 0307021808 for interactivity

[Daniel Phillips]

On Wednesday 02 July 2003 10:23, Con Kolivas wrote:
> This latest patch I'm formally announcing has the base O1int changes so far
> but includes new semantics for freshly started applications so they can
> become interactive very rapidly even during heavy load. This addresses the
> "slow to start new apps" evident in O1int so far.
>
> Please test this one and note given just how rapidly things can become
> interactive it may have regressions in other settings.

Without this patch, audio skips horribly when I drag a large window.  With it, 
audio is skipless during window dragging, so I like this patch, whatever it 
does (maybe you'd like to do a victory lap and re-explain the theory?).  It's 
not perfect: in Mozilla, scrolling through a long page with the mouse still 
causes skipping.

I'm testing this on a AMD K7 1666 (actual) MHz, 512 MB, VIA VTxxx chipset, 
Software is 2.5.73+Gnome+Metacity+ALSA+Zinf.  Video hardware is S3 ProSavage 
K4M266, running in unaccelerated VGA mode, 1280x1024x16.  Yes, I know audio 
skips less if video is accelerated, IDE runs in dma, etc, but that's not a 
real solution to this soft realtime scheduling problem.

Regards,

Daniel

Re: [PATCH] O1int 0307021808 for interactivity

[Con Kolivas]

On Thu, 3 Jul 2003 21:46, Daniel Phillips wrote:
> On Wednesday 02 July 2003 10:23, Con Kolivas wrote:
> > This latest patch I'm formally announcing has the base O1int changes so
> > far but includes new semantics for freshly started applications so they
> > can become interactive very rapidly even during heavy load. This
> > addresses the "slow to start new apps" evident in O1int so far.
> >
> > Please test this one and note given just how rapidly things can become
> > interactive it may have regressions in other settings.
>
> Without this patch, audio skips horribly when I drag a large window.  With
> it, audio is skipless during window dragging, so I like this patch,
> whatever it does (maybe you'd like to do a victory lap and re-explain the

Lap complete :) Theory? uh erm it's rather involved but basically instead of 
working off the accumulated sleeping ticks gathered in ten seconds it works 
on the accumulated sleeping ticks gathered till it wakes up. It has non 
linear semantics to cope with the fact that you cant accumulate 10 seconds 
worth of ticks (for example) if only 10 seconds has passed (likewise for less 
time). Also idle tasks are no longer considered fully interactive but idle 
and receive no boost or penalty. Finally they all start with some sleep ticks 
inherited by their parent as though they have been running for 1 second at 
least.

> theory?).  It's not perfect: in Mozilla, scrolling through a long page with
> the mouse still causes skipping.

I have (at least) one more trick up my sleeve which might help this, but this 
time I really do want some time to pass and more people test it (in -mm) 
before making another change.

Con

Re: [PATCH] O1int 0307021808 for interactivity

[Daniel Phillips]

On Thursday 03 July 2003 14:21, Con Kolivas wrote:
> Theory? uh erm it's rather involved but basically instead
> of working off the accumulated sleeping ticks gathered in ten seconds it
> works on the accumulated sleeping ticks gathered till it wakes up. It has
> non linear semantics to cope with the fact that you cant accumulate 10
> seconds worth of ticks (for example) if only 10 seconds has passed
> (likewise for less time). Also idle tasks are no longer considered fully
> interactive but idle and receive no boost or penalty. Finally they all
> start with some sleep ticks inherited by their parent as though they have
> been running for 1 second at least.

I'm still pretty much in the dark after that.  It says something about your 
patch, but it doesn't say much about the problem you're solving, i.e., what's 
the Context?  (pun intended)

Regards,

Daniel

Re: [PATCH] O1int 0307021808 for interactivity

[Con Kolivas]

On Fri, 4 Jul 2003 00:27, Daniel Phillips wrote:
> On Thursday 03 July 2003 14:21, Con Kolivas wrote:
> > Theory? uh erm it's rather involved but basically instead
> > of working off the accumulated sleeping ticks gathered in ten seconds it
> > works on the accumulated sleeping ticks gathered till it wakes up. It has
> > non linear semantics to cope with the fact that you cant accumulate 10
> > seconds worth of ticks (for example) if only 10 seconds has passed
> > (likewise for less time). Also idle tasks are no longer considered fully
> > interactive but idle and receive no boost or penalty. Finally they all
> > start with some sleep ticks inherited by their parent as though they have
> > been running for 1 second at least.
>
> I'm still pretty much in the dark after that.  It says something about your
> patch, but it doesn't say much about the problem you're solving, i.e.,
> what's the Context?  (pun intended)

Basically? Who gets to preempt who and for how long. The interactivity 
estimator should decide that the correct task is interactive and get a 
dynamically higher priority and larger timeslice. Is this what you're asking?

Con

Re: [PATCH] O1int 0307021808 for interactivity

[Daniel Phillips]

On Thursday 03 July 2003 16:34, Con Kolivas wrote:
> On Fri, 4 Jul 2003 00:27, Daniel Phillips wrote:
> > I'm still pretty much in the dark after that.  It says something about
> > your patch, but it doesn't say much about the problem you're solving,
> > i.e., what's the Context?  (pun intended)
>
> Basically? Who gets to preempt who and for how long. The interactivity
> estimator should decide that the correct task is interactive and get a
> dynamically higher priority and larger timeslice. Is this what you're
> asking?

I guess what I'm saying is, the problem is far from solved, however your 
concrete results demonstrate you've got an intuitive grasp of how to go at 
it.  I'd like to dig in and find out what the deep issues are.  As I've 
basically ignored scheduling up to now, including all of the details of 
Ingo's work, there's some background to fill in.  Being lazy, I'd prefer to 
read somebody's detailed [rfc] instead of going through the process of 
reverse engineering it myself.  I presume I'm not the only one.

Regards,

Daniel

Re: [PATCH] O1int 0307021808 for interactivity

[Luis Miguel Garcia]

Con,

I have not tested the latest patch from you, but I'm actually running with the one you made public yesterday and it behaves VERY strangely. Sometime, with only XMMS and aMSN (an Instant Messaging app), if I pick an xterm and move it around the screen very fast, xmms stops clearly until I stop doing bad things with the window.

Other times, even when I'm compiling something, I can do that with the windows and XMMS doesn't stop at all.

Very strange, not to?

When I have time, I'll test you patch from today.

Thanks,

-- 
=============================================================
Luis Miguel Garcia Mancebo
Ingenieria Tecnica en Informatica de Gestion
Universidad de Deusto / University of Deusto
Bilbao / Spain
=============================================================

Re: [PATCH] O1int 0307021808 for interactivity

[Con Kolivas]

On Wed, 2 Jul 2003 19:17, Luis Miguel Garcia wrote:
> Con,
>
> I have not tested the latest patch from you, but I'm actually running with
> the one you made public yesterday and it behaves VERY strangely. Sometime,
> with only XMMS and aMSN (an Instant Messaging app), if I pick an xterm and
> move it around the screen very fast, xmms stops clearly until I stop doing
> bad things with the window.

Yes indeed the old one would do that. The time constant was 10 seconds so an 
app would have to be running for up to 50 seconds before it was balanced. 
This new one fixes that by applying a non linear boost with time.

> Other times, even when I'm compiling something, I can do that with the
> windows and XMMS doesn't stop at all.

After a minute of running xmms I'd say.

> Very strange, not to?

Not at all :)

> When I have time, I'll test you patch from today.

Great.

Con

Re: [PATCH] O1int 0307021808 for interactivity

[Luis Miguel Garcia]

On Wed, 2 Jul 2003 19:53:59 +1000
Con Kolivas <kernel@kolivas.org> wrote:

> On Wed, 2 Jul 2003 19:17, Luis Miguel Garcia wrote:
> > Con,
> >
> > I have not tested the latest patch from you, but I'm actually running with
> > the one you made public yesterday and it behaves VERY strangely. Sometime,
> > with only XMMS and aMSN (an Instant Messaging app), if I pick an xterm and
> > move it around the screen very fast, xmms stops clearly until I stop doing
> > bad things with the window.
> 
> Yes indeed the old one would do that. The time constant was 10 seconds so an 
> app would have to be running for up to 50 seconds before it was balanced. 
> This new one fixes that by applying a non linear boost with time.
> 
> > Other times, even when I'm compiling something, I can do that with the
> > windows and XMMS doesn't stop at all.
> 
> After a minute of running xmms I'd say.
> 
> > Very strange, not to?
> 
> Not at all :)

Yes, it seems that this explanation is totally ok. I'm going to test newst patch and say you something

Thanks!

Luis Miguel Garcia

Re: [PATCH] O1int 0307021808 for interactivity

[Luis Miguel Garcia]

Con, must I use granularity with the latest patch? I'm actually compiling with it.

Thanks!


On Wed, 2 Jul 2003 19:53:59 +1000
Con Kolivas <kernel@kolivas.org> wrote:

> On Wed, 2 Jul 2003 19:17, Luis Miguel Garcia wrote:
> > Con,
> >
> > I have not tested the latest patch from you, but I'm actually running with
> > the one you made public yesterday and it behaves VERY strangely. Sometime,
> > with only XMMS and aMSN (an Instant Messaging app), if I pick an xterm and
> > move it around the screen very fast, xmms stops clearly until I stop doing
> > bad things with the window.
> 
> Yes indeed the old one would do that. The time constant was 10 seconds so an 
> app would have to be running for up to 50 seconds before it was balanced. 
> This new one fixes that by applying a non linear boost with time.
> 
> > Other times, even when I'm compiling something, I can do that with the
> > windows and XMMS doesn't stop at all.
> 
> After a minute of running xmms I'd say.
> 
> > Very strange, not to?
> 
> Not at all :)
> 
> > When I have time, I'll test you patch from today.
> 
> Great.
> 
> Con
> 


-- 
=============================================================
Luis Miguel Garcia Mancebo
Ingenieria Tecnica en Informatica de Gestion
Universidad de Deusto / University of Deusto
Bilbao / Spain
=============================================================

Re: [PATCH] O1int 0307021808 for interactivity

[Con Kolivas]

On Wed, 2 Jul 2003 20:12, Luis Miguel Garcia wrote:
> Con, must I use granularity with the latest patch? I'm actually compiling
> with it.

No, it is preferable to see if this patch works without it.

Con