O6int for interactivity

O*int patches trying to improve the interactivity of the 2.5/6 scheduler for desktops. It appears possible to do this without moving to nanosecond resolution.

This one makes a massive difference... Please test this to death.

Quoted 1 line

This one makes a massive difference... Please test this to death.

Oh, my god... This is nearly perfect! :-)
On 2.6.0-test1-mm1 with o6int.patch, I can't reproduce XMMS initial starvation anymore and X feels smoother under heavy load. Nice... ;-)

O*int patches trying to improve the interactivity of the 2.5/6 scheduler for desktops. It appears possible to do this without moving to nanosecond resolution.

This one makes a massive difference... Please test this to death.

O*int patches trying to improve the interactivity of the 2.5/6 scheduler for desktops. It appears possible to do this without moving to nanosecond resolution.

This one makes a massive difference... Please test this to death.

Changes:
The big change is in the way sleep_avg is incremented. Any amount of sleep will now raise you by at least one priority with each wakeup. This causes massive differences to startup time, extremely rapid conversion to interactive state, and recovery from non-interactive state rapidly as well (prevents X stalling after thrashing around under high loads for many seconds).

The sleep buffer was dropped to just 10ms. This has the effect of causing mild round robinning of very interactive tasks if they run for more than 10ms. The requeuing was changed from (unlikely()) to an ordinary if.. branch as this will be hit much more now.

MAX_BONUS as a #define was made easier to understand

Idle tasks were made slightly less interactive to prevent cpu hogs from becoming interactive on their very first wakeup.

Con

This patch-O6int-0307170012 applies on top of 2.6.0-test1-mm1 and can be found here:
http://kernel.kolivas.org/2.5

and here:

kernel/sched.c +7 -12

@@ -76,9 +76,9 @@
 #define MIN_SLEEP_AVG		(HZ)
 #define MAX_SLEEP_AVG		(10*HZ)
 #define STARVATION_LIMIT	(10*HZ)
-#define SLEEP_BUFFER		(HZ/20)
+#define SLEEP_BUFFER		(HZ/100)
 #define NODE_THRESHOLD		125
-#define MAX_BONUS		((MAX_USER_PRIO - MAX_RT_PRIO) * PRIO_BONUS_RATIO / 100)
+#define MAX_BONUS		(40 * PRIO_BONUS_RATIO / 100)
 
 /*
  * If a task is 'interactive' then we reinsert it in the active

@@ -399,7 +399,7 @@ static inline void activate_task(task_t 
 		 */
 		if (sleep_time > MIN_SLEEP_AVG){
 			p->avg_start = jiffies - MIN_SLEEP_AVG;
-			p->sleep_avg = MIN_SLEEP_AVG * (MAX_BONUS - INTERACTIVE_DELTA - 1) /
+			p->sleep_avg = MIN_SLEEP_AVG * (MAX_BONUS - INTERACTIVE_DELTA - 2) /
 				MAX_BONUS;
 		} else {
 			/*

@@ -413,14 +413,10 @@ static inline void activate_task(task_t 
 			p->sleep_avg += sleep_time;
 
 			/*
-			 * Give a bonus to tasks that wake early on to prevent
-			 * the problem of the denominator in the bonus equation
-			 * from continually getting larger.
+			 * Processes that sleep get pushed to a higher priority
+			 * each time they sleep
 			 */
-			if ((runtime - MIN_SLEEP_AVG) < MAX_SLEEP_AVG)
-				p->sleep_avg += (runtime - p->sleep_avg) *
-					(MAX_SLEEP_AVG + MIN_SLEEP_AVG - runtime) *
-					(MAX_BONUS - INTERACTIVE_DELTA) / MAX_BONUS / MAX_SLEEP_AVG;
+			p->sleep_avg = (p->sleep_avg * MAX_BONUS / runtime + 1) * runtime / MAX_BONUS;
 
 			/*
 			 * Keep a small buffer of SLEEP_BUFFER sleep_avg to

@@ -1311,7 +1307,7 @@ void scheduler_tick(int user_ticks, int 
 			enqueue_task(p, rq->expired);
 		} else
 			enqueue_task(p, rq->active);
-	} else if (unlikely(p->prio < effective_prio(p))){
+	} else if (p->prio < effective_prio(p)){
 		/*
 		 * Tasks that have lowered their priority are put to the end
 		 * of the active array with their remaining timeslice
 
-

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

Hello,

I have been gone from the computer for a couple of hours, and now everything is very chopping. For example I'm transfering some huge data

over nfs to another linux box (on sun, tho) where there is not enough space available. It happens that in the middle of the copying the process 'hangs'. I cannot interrupt it with ctrl-[cz], it takes a couple of seconds (~20). I cannot tell for sure that the problem is with the O6 patch, since I haven't done it on an other kernel, yet.

Quoted 89 lines · Con Kolivas

O*int patches trying to improve the interactivity of the 2.5/6 scheduler for desktops. It appears possible to do this without moving to nanosecond resolution.

This one makes a massive difference... Please test this to death.

Changes:
The big change is in the way sleep_avg is incremented. Any amount of sleep will now raise you by at least one priority with each wakeup. This causes massive differences to startup time, extremely rapid conversion to interactive state, and recovery from non-interactive state rapidly as well (prevents X stalling after thrashing around under high loads for many seconds).

The sleep buffer was dropped to just 10ms. This has the effect of causing mild round robinning of very interactive tasks if they run for more than 10ms. The requeuing was changed from (unlikely()) to an ordinary if.. branch as this will be hit much more now.

MAX_BONUS as a #define was made easier to understand

Idle tasks were made slightly less interactive to prevent cpu hogs from becoming interactive on their very first wakeup.

Con

This patch-O6int-0307170012 applies on top of 2.6.0-test1-mm1 and can be found here:
http://kernel.kolivas.org/2.5

and here:

--- linux-2.6.0-test1-mm1/kernel/sched.c 2003-07-16 20:27:32.000000000
+1000 +++ linux-2.6.0-testck1/kernel/sched.c 2003-07-17
00:13:24.000000000 +1000 @@ -76,9 +76,9 @@
#define MIN_SLEEP_AVG (HZ)
#define MAX_SLEEP_AVG (10*HZ)
#define STARVATION_LIMIT (10*HZ)

kernel/sched.c +1 -2

-#define SLEEP_BUFFER		(HZ/20)
+#define SLEEP_BUFFER		(HZ/100)
 #define NODE_THRESHOLD		125
-#define MAX_BONUS		((MAX_USER_PRIO - MAX_RT_PRIO) * PRIO_BONUS_RATIO /

100) +#define MAX_BONUS (40 * PRIO_BONUS_RATIO / 100)

/*
* If a task is 'interactive' then we reinsert it in the active

kernel/sched.c +4 -8

@@ -399,7 +399,7 @@ static inline void activate_task(task_t
 		 */
 		if (sleep_time > MIN_SLEEP_AVG){
 			p->avg_start = jiffies - MIN_SLEEP_AVG;
-			p->sleep_avg = MIN_SLEEP_AVG * (MAX_BONUS - INTERACTIVE_DELTA - 1) /
+			p->sleep_avg = MIN_SLEEP_AVG * (MAX_BONUS - INTERACTIVE_DELTA - 2) /
 				MAX_BONUS;
 		} else {
 			/*

@@ -413,14 +413,10 @@ static inline void activate_task(task_t
 			p->sleep_avg += sleep_time;
 
 			/*
-			 * Give a bonus to tasks that wake early on to prevent
-			 * the problem of the denominator in the bonus equation
-			 * from continually getting larger.
+			 * Processes that sleep get pushed to a higher priority
+			 * each time they sleep
 			 */
-			if ((runtime - MIN_SLEEP_AVG) < MAX_SLEEP_AVG)
-				p->sleep_avg += (runtime - p->sleep_avg) *
-					(MAX_SLEEP_AVG + MIN_SLEEP_AVG - runtime) *
-					(MAX_BONUS - INTERACTIVE_DELTA) / MAX_BONUS / MAX_SLEEP_AVG;
+			p->sleep_avg = (p->sleep_avg * MAX_BONUS / runtime + 1) * runtime /
 MAX_BONUS;
 
 			/*

kernel/sched.c +1 -2

 			 * Keep a small buffer of SLEEP_BUFFER sleep_avg to

@@ -1311,7 +1307,7 @@ void scheduler_tick(int user_ticks, int
 			enqueue_task(p, rq->expired);
 		} else
 			enqueue_task(p, rq->active);
-	} else if (unlikely(p->prio < effective_prio(p))){
+	} else if (p->prio < effective_prio(p)){
 		/*
 		 * Tasks that have lowered their priority are put to the end
 		 * of the active array with their remaining timeslice
 
-

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

O*int patches trying to improve the interactivity of the 2.5/6 scheduler for desktops. It appears possible to do this without moving to nanosecond resolution.

This one makes a massive difference... Please test this to death.

Changes:
The big change is in the way sleep_avg is incremented. Any amount of sleep will now raise you by at least one priority with each wakeup. This causes massive differences to startup time, extremely rapid conversion to interactive state, and recovery from non-interactive state rapidly as well (prevents X stalling after thrashing around under high loads for many seconds).

The sleep buffer was dropped to just 10ms. This has the effect of causing mild round robinning of very interactive tasks if they run for more than 10ms. The requeuing was changed from (unlikely()) to an ordinary if.. branch as this will be hit much more now.

Quoted 2 lines

O*int patches trying to improve the interactivity of the 2.5/6 scheduler

for

Quoted 9 lines

desktops. It appears possible to do this without moving to nanosecond resolution.

This one makes a massive difference... Please test this to death.

Changes:
The big change is in the way sleep_avg is incremented. Any amount of sleep will now raise you by at least one priority with each wakeup. This causes massive differences to startup time, extremely rapid conversion to

interactive

Quoted 3 lines

state, and recovery from non-interactive state rapidly as well (prevents X stalling after thrashing around under high loads for many seconds).

Quoted 1 line

The sleep buffer was dropped to just 10ms. This has the effect of causing

mild

Quoted 1 line

round robinning of very interactive tasks if they run for more than 10ms.

The

Quoted 2 lines

requeuing was changed from (unlikely()) to an ordinary if.. branch as this will be hit much more now.

Con, I'll make a few notes on the code and a final comment.

Quoted 1 line

-#define MAX_BONUS ((MAX_USER_PRIO - MAX_RT_PRIO) *

100)

Quoted 1 line

+#define MAX_BONUS (40 * PRIO_BONUS_RATIO / 100)

Why did you bolt in the 40 value ? It really comes from (MAX_USER_PRIO - MAX_RT_PRIO)
and you will have another place to change if the number of slots will change. If you want to clarify better, stick a comment.

Review

Quoted 4 lines

(quoted diff) +1 -0

+			p->sleep_avg = (p->sleep_avg * MAX_BONUS / runtime + 1) 

MAX_BONUS;

I don't have the full code so I cannot see what "runtime" is, but if "runtime" is the time the task ran, this is :

p->sleep_avg ~= p->sleep_avg + runtime / MAX_BONUS;

(in any case a non-decreasing function of "runtime" ) Are you sure you want to reward tasks that actually ran more ?

Con, you cannot follow the XMMS thingy otherwise you'll end up bolting in the XMMS sleep->burn pattern and you'll probably break the make-j+RealPlay for example. MultiMedia players are really tricky since they require strict timings and forces you to create a special super-interactive treatment inside the code. Interactivity in my box running moderate high loads is very good for my desktop use. Maybe audio will skip here (didn't try) but I believe that following the fix-XMMS thingy is really bad. I believe we should try to make the desktop to feel interactive with human tollerances and not with strict timings like MM apps. If the audio skips when dragging like crazy a X window using the filled mode on a slow CPU, we shouldn't be much worried about it for example. If audio skip when hitting the refresh button of Mozilla, then yes it should be fixed. And the more you add super interactive patterns, the more the scheduler will be exploitable. I recommend you after doing changes to get this :

http://www.xmailserver.org/linux-patches/irman2.c

and run it with different -n (number of tasks) and -b (CPU burn ms time). At the same time try to build a kernel for example. Then you will realize that interactivity is not the bigger problem that the scheduler has right now.

Quoted 1 line

Review

Quoted 1 line

(quoted diff) +1 -0

+			p->sleep_avg = (p->sleep_avg * MAX_BONUS / runtime + 1)

* runtime /

Quoted 5 lines

MAX_BONUS;

I don't have the full code so I cannot see what "runtime" is, but if "runtime" is the time the task ran, this is :

Quoted 4 lines

p->sleep_avg ~= p->sleep_avg + runtime / MAX_BONUS;

(in any case a non-decreasing function of "runtime" ) Are you sure you want to reward tasks that actually ran more ?

That was the bug. Runtime was supposed to be limited to MAX_SLEEP_AVG. Fix will be posted very soon.

Quoted 17 lines

Con, you cannot follow the XMMS thingy otherwise you'll end up bolting in the XMMS sleep->burn pattern and you'll probably break the make-j+RealPlay for example. MultiMedia players are really tricky since they require strict timings and forces you to create a special super-interactive treatment inside the code. Interactivity in my box running moderate high loads is very good for my desktop use. Maybe audio will skip here (didn't try) but I believe that following the fix-XMMS thingy is really bad. I believe we should try to make the desktop to feel interactive with human tollerances and not with strict timings like MM apps. If the audio skips when dragging like crazy a X window using the filled mode on a slow CPU, we shouldn't be much worried about it for example. If audio skip when hitting the refresh button of Mozilla, then yes it should be fixed. And the more you add super interactive patterns, the more the scheduler will be exploitable. I recommend you after doing changes to get this :

http://www.xmailserver.org/linux-patches/irman2.c

Quoted 4 lines

and run it with different -n (number of tasks) and -b (CPU burn ms time). At the same time try to build a kernel for example. Then you will realize that interactivity is not the bigger problem that the scheduler has right now.

Please don't assume I'm writing an xmms scheduler. I've done a lot more testing than xmms.

Quoted 14 lines · Con Kolivas

Quoted 1 line

Review

Quoted 1 line

(quoted diff) +1 -0

+			p->sleep_avg = (p->sleep_avg * MAX_BONUS / runtime + 1)

* runtime /

Quoted 9 lines

MAX_BONUS;

I don't have the full code so I cannot see what "runtime" is, but if "runtime" is the time the task ran, this is :

p->sleep_avg ~= p->sleep_avg + runtime / MAX_BONUS;

(in any case a non-decreasing function of "runtime" ) Are you sure you want to reward tasks that actually ran more ?

Quoted 2 lines

That was the bug. Runtime was supposed to be limited to MAX_SLEEP_AVG. Fix will be posted very soon.

Con, it is not the limit. You're making sleep_avg a non-decreasing function of "runtime". Basically you are rewarding tasks that did burn more CPU (if runtime is what the name suggests). Are you sure this is what you want ?

Quoted 24 lines

Quoted 23 lines

Con, you cannot follow the XMMS thingy otherwise you'll end up bolting in the XMMS sleep->burn pattern and you'll probably break the make-j+RealPlay for example. MultiMedia players are really tricky since they require strict timings and forces you to create a special super-interactive treatment inside the code. Interactivity in my box running moderate high loads is very good for my desktop use. Maybe audio will skip here (didn't try) but I believe that following the fix-XMMS thingy is really bad. I believe we should try to make the desktop to feel interactive with human tollerances and not with strict timings like MM apps. If the audio skips when dragging like crazy a X window using the filled mode on a slow CPU, we shouldn't be much worried about it for example. If audio skip when hitting the refresh button of Mozilla, then yes it should be fixed. And the more you add super interactive patterns, the more the scheduler will be exploitable. I recommend you after doing changes to get this :

http://www.xmailserver.org/linux-patches/irman2.c

and run it with different -n (number of tasks) and -b (CPU burn ms time). At the same time try to build a kernel for example. Then you will realize that interactivity is not the bigger problem that the scheduler has right now.

Quoted 2 lines

Please don't assume I'm writing an xmms scheduler. I've done a lot more testing than xmms.

Ok, I'm feeling better already ;)

Quoting Davide Libenzi <[email protected]>:

Quoted 26 lines · Con Kolivas

Quoted 3 lines

O*int patches trying to improve the interactivity of the 2.5/6 scheduler

for

Quoted 9 lines

desktops. It appears possible to do this without moving to nanosecond resolution.

This one makes a massive difference... Please test this to death.

Changes:
The big change is in the way sleep_avg is incremented. Any amount of sleep will now raise you by at least one priority with each wakeup. This causes massive differences to startup time, extremely rapid conversion to

interactive

Quoted 4 lines

state, and recovery from non-interactive state rapidly as well (prevents X stalling after thrashing around under high loads for many seconds).

The sleep buffer was dropped to just 10ms. This has the effect of causing

mild

Quoted 13 lines

Quoted 1 line

round robinning of very interactive tasks if they run for more than 10ms.

The

Quoted 2 lines

requeuing was changed from (unlikely()) to an ordinary if.. branch as this will be hit much more now.

Con, I'll make a few notes on the code and a final comment.

Quoted 1 line

-#define MAX_BONUS ((MAX_USER_PRIO - MAX_RT_PRIO) *

PRIO_BONUS_RATIO /

Quoted 8 lines

100)

Quoted 1 line

+#define MAX_BONUS (40 * PRIO_BONUS_RATIO / 100)

Why did you bolt in the 40 value ? It really comes from (MAX_USER_PRIO - MAX_RT_PRIO)
and you will have another place to change if the number of slots will change. If you want to clarify better, stick a comment.

Granted. Will revert. If you don't understand it you shouldn't be fiddling with it I agree.

Quoted 3 lines

Review

Quoted 3 lines

(quoted diff) +1 -0

+			p->sleep_avg = (p->sleep_avg * MAX_BONUS / runtime + 1) 

* runtime /

Quoted 5 lines

MAX_BONUS;

I don't have the full code so I cannot see what "runtime" is, but if "runtime" is the time the task ran, this is :

Quoted 4 lines

p->sleep_avg ~= p->sleep_avg + runtime / MAX_BONUS;

(in any case a non-decreasing function of "runtime" ) Are you sure you want to reward tasks that actually ran more ?

That was the bug. Runtime was supposed to be limited to MAX_SLEEP_AVG. Fix will be posted very soon.

Quoted 64 lines · Con Kolivas

Quoting Davide Libenzi <[email protected]>:

Quoted 29 lines · Con Kolivas

Quoted 1 line

O*int patches trying to improve the interactivity of the 2.5/6 scheduler

for

Quoted 10 lines

desktops. It appears possible to do this without moving to nanosecond resolution.

This one makes a massive difference... Please test this to death.

Changes:
The big change is in the way sleep_avg is incremented. Any amount of sleep will now raise you by at least one priority with each wakeup. This causes massive differences to startup time, extremely rapid conversion to

interactive

Quoted 5 lines

state, and recovery from non-interactive state rapidly as well (prevents X stalling after thrashing around under high loads for many seconds).

The sleep buffer was dropped to just 10ms. This has the effect of causing

mild

Quoted 2 lines

round robinning of very interactive tasks if they run for more than 10ms.

Quoted 8 lines

The

Quoted 2 lines

requeuing was changed from (unlikely()) to an ordinary if.. branch as this will be hit much more now.

Con, I'll make a few notes on the code and a final comment.

Quoted 1 line

-#define MAX_BONUS ((MAX_USER_PRIO - MAX_RT_PRIO) *

PRIO_BONUS_RATIO /

Quoted 8 lines

100)

Quoted 1 line

+#define MAX_BONUS (40 * PRIO_BONUS_RATIO / 100)

Why did you bolt in the 40 value ? It really comes from (MAX_USER_PRIO - MAX_RT_PRIO)
and you will have another place to change if the number of slots will change. If you want to clarify better, stick a comment.

Granted. Will revert. If you don't understand it you shouldn't be fiddling with it I agree.

Quoted 1 line

Review

Quoted 1 line

(quoted diff) +1 -0

+			p->sleep_avg = (p->sleep_avg * MAX_BONUS / runtime + 1)

* runtime /

Quoted 7 lines

MAX_BONUS;

I don't have the full code so I cannot see what "runtime" is, but if "runtime" is the time the task ran, this is :

p->sleep_avg ~= p->sleep_avg + runtime / MAX_BONUS;

Quoted 5 lines

Quoted 2 lines

(in any case a non-decreasing function of "runtime" ) Are you sure you want to reward tasks that actually ran more ?

That was the bug. Runtime was supposed to be limited to MAX_SLEEP_AVG. Fix will be posted very soon.

Should any harm come from running 06int without the phantom patch mentioned?

Quoted 5 lines

Quoted 2 lines · Con Kolivas

Quoting Davide Libenzi <[email protected]>:

Quoted 1 line · Con Kolivas

Should any harm come from running 06int without the phantom patch mentioned?

No harm, but applications that have been running for a while (?hours) will eventually not run quite as smoothly. I promise it is only one 10 minute kernel compile away :)

O*int patches trying to improve the interactivity of the 2.5/6 scheduler for desktops. It appears possible to do this without moving to nanosecond resolution.

This one makes a massive difference... Please test this to death.

Changes:
The big change is in the way sleep_avg is incremented. Any amount of sleep will now raise you by at least one priority with each wakeup. This causes massive differences to startup time, extremely rapid conversion to interactive state, and recovery from non-interactive state rapidly as well (prevents X stalling after thrashing around under high loads for many seconds).

The sleep buffer was dropped to just 10ms. This has the effect of causing mild round robinning of very interactive tasks if they run for more than 10ms. The requeuing was changed from (unlikely()) to an ordinary if.. branch as this will be hit much more now.

MAX_BONUS as a #define was made easier to understand

Idle tasks were made slightly less interactive to prevent cpu hogs from becoming interactive on their very first wakeup.

Con

This patch-O6int-0307170012 applies on top of 2.6.0-test1-mm1 and can be found here:
http://kernel.kolivas.org/2.5

and here:

kernel/sched.c +7 -12

@@ -76,9 +76,9 @@
 #define MIN_SLEEP_AVG		(HZ)
 #define MAX_SLEEP_AVG		(10*HZ)
 #define STARVATION_LIMIT	(10*HZ)
-#define SLEEP_BUFFER		(HZ/20)
+#define SLEEP_BUFFER		(HZ/100)
 #define NODE_THRESHOLD		125
-#define MAX_BONUS		((MAX_USER_PRIO - MAX_RT_PRIO) * PRIO_BONUS_RATIO / 100)
+#define MAX_BONUS		(40 * PRIO_BONUS_RATIO / 100)
 
 /*
 * If a task is 'interactive' then we reinsert it in the active

@@ -399,7 +399,7 @@ static inline void activate_task(task_t 
 		 */
 		if (sleep_time > MIN_SLEEP_AVG){
 			p->avg_start = jiffies - MIN_SLEEP_AVG;
-			p->sleep_avg = MIN_SLEEP_AVG * (MAX_BONUS - INTERACTIVE_DELTA - 1) /
+			p->sleep_avg = MIN_SLEEP_AVG * (MAX_BONUS - INTERACTIVE_DELTA - 2) /
 				MAX_BONUS;
 		} else {
 			/*

@@ -413,14 +413,10 @@ static inline void activate_task(task_t 
 			p->sleep_avg += sleep_time;
 
 			/*
-			 * Give a bonus to tasks that wake early on to prevent
-			 * the problem of the denominator in the bonus equation
-			 * from continually getting larger.
+			 * Processes that sleep get pushed to a higher priority
+			 * each time they sleep
 			 */
-			if ((runtime - MIN_SLEEP_AVG) < MAX_SLEEP_AVG)
-				p->sleep_avg += (runtime - p->sleep_avg) *
-					(MAX_SLEEP_AVG + MIN_SLEEP_AVG - runtime) *
-					(MAX_BONUS - INTERACTIVE_DELTA) / MAX_BONUS / MAX_SLEEP_AVG;
+			p->sleep_avg = (p->sleep_avg * MAX_BONUS / runtime + 1) * runtime / MAX_BONUS;
 
 			/*
 			 * Keep a small buffer of SLEEP_BUFFER sleep_avg to

@@ -1311,7 +1307,7 @@ void scheduler_tick(int user_ticks, int 
 			enqueue_task(p, rq->expired);
 		} else
 			enqueue_task(p, rq->active);
-	} else if (unlikely(p->prio < effective_prio(p))){
+	} else if (p->prio < effective_prio(p)){
 		/*
 		 * Tasks that have lowered their priority are put to the end
 		 * of the active array with their remaining timeslice
 
-

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

O*int patches trying to improve the interactivity of the 2.5/6 scheduler for desktops. It appears possible to do this without moving to nanosecond resolution.

This one makes a massive difference... Please test this to death.

Con Kolivas, Wed, Jul 16, 2003 16:30:25 +0200:

Quoted 1 line

O*int patches trying to improve the interactivity of the 2.5/6 scheduler

for

Quoted 3 lines

desktops. It appears possible to do this without moving to nanosecond resolution.

Quoted 2 lines

This one makes a massive difference... Please test this to death.

tar ztf file.tar.gz and make something somehow do not like each other. Usually it is tar, which became very slow. And listings of directories are slow if system is under load (about 3), too (most annoying).

UP P3-700, preempt. 2.6.0-test1-mm1 + O6-int.

Quoted 8 lines

Quoted 3 lines

O*int patches trying to improve the interactivity of the 2.5/6 scheduler for desktops. It appears possible to do this without moving to nanosecond resolution.

tar ztf file.tar.gz and make something somehow do not like each other. Usually it is tar, which became very slow. And listings of directories are slow if system is under load (about 3), too (most annoying).

Quoted 1 line

UP P3-700, preempt. 2.6.0-test1-mm1 + O6-int.

Thanks for testing. It is distinctly possible that O6.1 addresses this problem. Can you please test that? It applies on top of O6 and only requires a recompile of sched.o.

Quoted 4 lines

Still no good. xine drops frames by kernel's make -j2, xmms skips while bk pull (locally). Updates (after switching desktops in metacity) get delayed for seconds (mozilla window redraws with www.kernel.org on it, for example).

would you mind to give the attached sched-2.6.0-test1-G2 patch a go? (it's ontop of vanilla 2.6.0-test1.) Do you still see audio skipping and/or other bad scheduling artifacts?

(if you prefer -mm2 then please first unapply the second attached patch (Con's interactivity patchset) - they are mutually exclusive.)

http://www.xmailserver.org/linux-patches/irman2.c

and run it with different -n (number of tasks) and -b (CPU burn ms time). At the same time try to build a kernel for example. Then you will realize that interactivity is not the bigger problem that the scheduler has right now.

Quoted 6 lines · Davide Libenzi

http://www.xmailserver.org/linux-patches/irman2.c

and run it with different -n (number of tasks) and -b (CPU burn ms time). At the same time try to build a kernel for example. Then you will realize that interactivity is not the bigger problem that the scheduler has right now.

I added an irman2 load to contest. Con's changes 06+06.1 stomped it flat [1]. irman2 is modified to run for 30s at a time, but with default parameters.

-Mike

[1] imho a little too flat. it also made a worrisome impression on apache bench

------------------------------------------------------------------------

no_load:
Kernel [runs] Time CPU% Loads LCPU% Ratio

2.5.69               1	153	94.8	0.0	0.0	1.00
2.5.70               1	153	94.1	0.0	0.0	1.00
2.6.0-test1          1	153	94.1	0.0	0.0	1.00
2.6.0-test1-mm1      1	152	94.7	0.0	0.0	1.00
cacherun:
Kernel          [runs]	Time	CPU%	Loads	LCPU%	Ratio
2.5.69               1	146	98.6	0.0	0.0	0.95
2.5.70               1	146	98.6	0.0	0.0	0.95
2.6.0-test1          1	146	98.6	0.0	0.0	0.95
2.6.0-test1-mm1      1	146	98.6	0.0	0.0	0.96
process_load:
Kernel          [runs]	Time	CPU%	Loads	LCPU%	Ratio
2.5.69               1	331	43.8	90.0	55.3	2.16
2.5.70               1	199	72.4	27.0	25.5	1.30
2.6.0-test1          1	264	54.5	61.0	44.3	1.73
2.6.0-test1-mm1      1	323	44.9	88.0	54.2	2.12
ctar_load:
Kernel          [runs]	Time	CPU%	Loads	LCPU%	Ratio
2.5.69               1	190	77.9	0.0	0.0	1.24
2.5.70               1	186	80.1	0.0	0.0	1.22
2.6.0-test1          1	213	70.4	0.0	0.0	1.39
2.6.0-test1-mm1      1	207	72.5	0.0	0.0	1.36
xtar_load:
Kernel          [runs]	Time	CPU%	Loads	LCPU%	Ratio
2.5.69               1	196	75.0	0.0	3.1	1.28
2.5.70               1	195	75.9	0.0	3.1	1.27

2.6.0-test1          1	193	76.7	1.0	4.1	1.26
2.6.0-test1-mm1      1	195	75.9	1.0	4.1	1.28
io_load:
Kernel          [runs]	Time	CPU%	Loads	LCPU%	Ratio
2.5.69               1	437	34.6	69.1	15.1	2.86
2.5.70               1	401	37.7	72.3	17.4	2.62
2.6.0-test1          1	243	61.3	48.1	17.3	1.59
2.6.0-test1-mm1      1	336	44.9	64.5	17.3	2.21

Quoted 28 lines · Mike Galbraith

no_load:

Kernel          [runs]  Time    CPU%    Loads   LCPU%   Ratio
2.5.69               1  153     94.8    0.0     0.0     1.00
2.5.70               1  153     94.1    0.0     0.0     1.00
2.6.0-test1          1  153     94.1    0.0     0.0     1.00
2.6.0-test1-mm1      1  152     94.7    0.0     0.0     1.00
cacherun:
Kernel          [runs]  Time    CPU%    Loads   LCPU%   Ratio
2.5.69               1  146     98.6    0.0     0.0     0.95
2.5.70               1  146     98.6    0.0     0.0     0.95
2.6.0-test1          1  146     98.6    0.0     0.0     0.95
2.6.0-test1-mm1      1  146     98.6    0.0     0.0     0.96
process_load:
Kernel          [runs]  Time    CPU%    Loads   LCPU%   Ratio
2.5.69               1  331     43.8    90.0    55.3    2.16
2.5.70               1  199     72.4    27.0    25.5    1.30
2.6.0-test1          1  264     54.5    61.0    44.3    1.73
2.6.0-test1-mm1      1  323     44.9    88.0    54.2    2.12
ctar_load:
Kernel          [runs]  Time    CPU%    Loads   LCPU%   Ratio
2.5.69               1  190     77.9    0.0     0.0     1.24
2.5.70               1  186     80.1    0.0     0.0     1.22
2.6.0-test1          1  213     70.4    0.0     0.0     1.39
2.6.0-test1-mm1      1  207     72.5    0.0     0.0     1.36
xtar_load:
Kernel          [runs]  Time    CPU%    Loads   LCPU%   Ratio
2.5.69               1  196     75.0    0.0     3.1     1.28
2.5.70               1  195     75.9    0.0     3.1     1.27

Quoted 8 lines

2.6.0-test1          1  193     76.7    1.0     4.1     1.26
2.6.0-test1-mm1      1  195     75.9    1.0     4.1     1.28
io_load:
Kernel          [runs]  Time    CPU%    Loads   LCPU%   Ratio
2.5.69               1  437     34.6    69.1    15.1    2.86
2.5.70               1  401     37.7    72.3    17.4    2.62
2.6.0-test1          1  243     61.3    48.1    17.3    1.59
2.6.0-test1-mm1      1  336     44.9    64.5    17.3    2.21

Looks like gcc is getting less priority after a read completes. Keep an eye on this please.

That _might_ (add salt) be priorities of kernel threads dropping too low.

I'm also seeing occasional total stalls under heavy I/O in the order of 10-12 seconds (even the disk stops). I have no idea if that's something in mm or the scheduler changes though, as I've yet to do any isolation and/or tinkering. All I know at this point is that I haven't seen it in stock yet.

Quoted 7 lines · Mike Galbraith

That _might_ (add salt) be priorities of kernel threads dropping too low.

I'm also seeing occasional total stalls under heavy I/O in the order of 10-12 seconds (even the disk stops). I have no idea if that's something in mm or the scheduler changes though, as I've yet to do any isolation and/or tinkering. All I know at this point is that I haven't seen it in stock yet.

I've seen this too while doing a huge nfs transfer from a 2.6 machine to a 2.4 machine (sparc32). Thought it'd be something with the nfs changes which were recently, might be the scheduler, tho. Ah, and it is fully reproducable.

Quoted 9 lines · Wiktor Wodecki

Quoted 7 lines · Mike Galbraith

That _might_ (add salt) be priorities of kernel threads dropping too low.

I'm also seeing occasional total stalls under heavy I/O in the order of 10-12 seconds (even the disk stops). I have no idea if that's something in mm or the scheduler changes though, as I've yet to do any isolation and/or tinkering. All I know at this point is that I haven't seen it in stock yet.

Quoted 4 lines

I've seen this too while doing a huge nfs transfer from a 2.6 machine to a 2.4 machine (sparc32). Thought it'd be something with the nfs changes which were recently, might be the scheduler, tho. Ah, and it is fully reproducable.

Well I didn't want to post this yet because I'm not sure if it's a good workaround yet but it looks like a reasonable compromise, and since you have a testcase it will be interesting to see if it addresses it. It's possible that a task is being requeued every millisecond, and this is a little smarter. It allows cpu hogs to run for 100ms before being round robinned, but shorter for interactive tasks. Can you try this O7 which applies on top of O6.1 please:

available here:
http://kernel.kolivas.org/2.5

and here:

kernel/sched.c +5 -4

@@ -1310,10 +1310,12 @@ void scheduler_tick(int user_ticks, int 
 			enqueue_task(p, rq->expired);
 		} else
 			enqueue_task(p, rq->active);
-	} else if (p->prio < effective_prio(p)){
+	} else if (!((task_timeslice(p) - p->time_slice) %
+		 (MIN_TIMESLICE * (MAX_BONUS + 1 - p->sleep_avg * MAX_BONUS / MAX_SLEEP_AVG)))){
 		/*
-		 * Tasks that have lowered their priority are put to the end
-		 * of the active array with their remaining timeslice
+		 * Running tasks get requeued with their remaining timeslice
+		 * after a period proportional to how cpu intensive they are to
+		 * minimise the duration one interactive task can starve another
 		 */
 		dequeue_task(p, rq->active);
 		set_tsk_need_resched(p);
 
-

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

Quoted 19 lines · Con Kolivas

Quoted 10 lines · Wiktor Wodecki

Quoted 8 lines · Mike Galbraith

That _might_ (add salt) be priorities of kernel threads dropping too low.

I'm also seeing occasional total stalls under heavy I/O in the order of 10-12 seconds (even the disk stops). I have no idea if that's something in mm or the scheduler changes though, as I've yet to do any isolation and/or tinkering. All I know at this point is that I haven't seen it in stock yet.

Quoted 5 lines

I've seen this too while doing a huge nfs transfer from a 2.6 machine to a 2.4 machine (sparc32). Thought it'd be something with the nfs changes which were recently, might be the scheduler, tho. Ah, and it is fully reproducable.

Well I didn't want to post this yet because I'm not sure if it's a good workaround yet but it looks like a reasonable compromise, and since you have a testcase it will be interesting to see if it addresses it. It's possible that a task is being requeued every millisecond, and this is a little smarter. It allows cpu hogs to run for 100ms before being round robinned, but shorter for interactive tasks. Can you try this O7 which applies on top of O6.1 please:

Quoted 3 lines

available here:
http://kernel.kolivas.org/2.5

sorry, the problem still persists. Aborting the cp takes less time, tho (about 10 seconds now, before it was about 30 secs). I'm aborting during a big file, FYI.

Quoted 32 lines · Wiktor Wodecki

Quoted 29 lines · Con Kolivas

Quoted 11 lines · Wiktor Wodecki

Quoted 9 lines · Mike Galbraith

That _might_ (add salt) be priorities of kernel threads dropping too low.

I'm also seeing occasional total stalls under heavy I/O in the order of 10-12 seconds (even the disk stops). I have no idea if that's something in mm or the scheduler changes though, as I've yet to do any isolation and/or tinkering. All I know at this point is that I haven't seen it in stock yet.

Quoted 5 lines

I've seen this too while doing a huge nfs transfer from a 2.6 machine to a 2.4 machine (sparc32). Thought it'd be something with the nfs changes which were recently, might be the scheduler, tho. Ah, and it is fully reproducable.

Well I didn't want to post this yet because I'm not sure if it's a good workaround yet but it looks like a reasonable compromise, and since you have a testcase it will be interesting to see if it addresses it. It's possible that a task is being requeued every millisecond, and this is a little smarter. It allows cpu hogs to run for 100ms before being round robinned, but shorter for interactive tasks. Can you try this O7 which applies on top of O6.1 please:

available here:
http://kernel.kolivas.org/2.5

Quoted 4 lines

sorry, the problem still persists. Aborting the cp takes less time, tho (about 10 seconds now, before it was about 30 secs). I'm aborting during a big file, FYI.

OK if the IO actually stops then it shouldn't be an IO scheduler or request allocation problem, but could you try to capture a sysrq T trace for me during the freeze.

Quoted 4 lines · Mike Galbraith

That _might_ (add salt) be priorities of kernel threads dropping too low.

I'm also seeing occasional total stalls under heavy I/O in the order of 10-12 seconds (even the disk stops). I have no idea if that's

something in

Quoted 2 lines

mm or the scheduler changes though, as I've yet to do any isolation and/or tinkering. All I know at this point is that I haven't seen it in stock

yet.

I've seen this too while doing a huge nfs transfer from a 2.6 machine to a 2.4 machine (sparc32). Thought it'd be something with the nfs changes which were recently, might be the scheduler, tho. Ah, and it is fully reproducable.

Telling to not mess with my kernel threads seems to have fixed it here... no stalls during the whole contest run. New contest numbers attached.

control them. It is right to apply uncontrolled unfairness to userspace tasks though.

Quoted 2 lines · Davide Libenzi

control them. It is right to apply uncontrolled unfairness to userspace tasks though.

s/It is right/It is not right/

Quoted 6 lines · Davide Libenzi

Quoted 2 lines · Davide Libenzi

control them. It is right to apply uncontrolled unfairness to userspace tasks though.

s/It is right/It is not right/

OK.. but is it right to apply *controlled* unfairness to userspace?

Quoted 9 lines · On Fri, 18 Jul 2003 [email protected] wrote:

Quoted 6 lines · Davide Libenzi

Quoted 2 lines · Davide Libenzi

control them. It is right to apply uncontrolled unfairness to userspace tasks though.

s/It is right/It is not right/

OK.. but is it right to apply *controlled* unfairness to userspace?

I'm sorry to say that guys, but I'm afraid it's what we have to do. We did not think about it when this scheduler was dropped inside 2.5 sadly. The interactivity concept is based on the fact that a particular class of tasks characterized by certain sleep->burn patterns are never expired and eventually, only oscillate between two (pretty high) priorities. Without applying a global CPU throttle for interactive tasks, you can create a small set of processes (like irman does) that hit the coded sleep->burn pattern and that make everything is running with priority lower than the lower of the two of the oscillation range, to almost completely starve. Controlled unfairness would mean throttling the CPU time we reserve to interactive tasks so that we always reserve a minimum time to non interactive processes.

Quoted 4 lines

I'm sorry to say that guys, but I'm afraid it's what we have to do. We did not think about it when this scheduler was dropped inside 2.5 sadly. The interactivity concept is based on the fact that a particular class of tasks characterized by certain sleep->burn patterns are never expired and

Quoted 8 lines

eventually, only oscillate between two (pretty high) priorities. Without applying a global CPU throttle for interactive tasks, you can create a small set of processes (like irman does) that hit the coded sleep->burn pattern and that make everything is running with priority lower than the lower of the two of the oscillation range, to almost completely starve. Controlled unfairness would mean throttling the CPU time we reserve to interactive tasks so that we always reserve a minimum time to non interactive processes.

I'd like to find a way to prevent that instead. There's got to be a way.

It's easy to prevent irman type things from starving others permanently (i call this active starvation, or wakeup starvation), and this does something fairly similar to what you're talking about. Just crawl down the queue heads looking for the oldest task periodically instead of always taking the highest queue. You can do that very fast, and it does prevent active starvation.

Quoted 13 lines · Mike Galbraith

Quoted 12 lines

I'm sorry to say that guys, but I'm afraid it's what we have to do. We did not think about it when this scheduler was dropped inside 2.5 sadly. The interactivity concept is based on the fact that a particular class of tasks characterized by certain sleep->burn patterns are never expired and eventually, only oscillate between two (pretty high) priorities. Without applying a global CPU throttle for interactive tasks, you can create a small set of processes (like irman does) that hit the coded sleep->burn pattern and that make everything is running with priority lower than the lower of the two of the oscillation range, to almost completely starve. Controlled unfairness would mean throttling the CPU time we reserve to interactive tasks so that we always reserve a minimum time to non interactive processes.

Quoted 1 line

I'd like to find a way to prevent that instead. There's got to be a way.

Remember that this is computer science, that is, for every problem there "at least" one solution ;)

Quoted 6 lines

It's easy to prevent irman type things from starving others permanently (i call this active starvation, or wakeup starvation), and this does something fairly similar to what you're talking about. Just crawl down the queue heads looking for the oldest task periodically instead of always taking the highest queue. You can do that very fast, and it does prevent active starvation.

Everything that will make the scheduler to say "ok, I gave enough time to interactive tasks, now I'm really going to spin one from the masses" will work. Having a clean solution would not be an option here.

Quoted 3 lines

Everything that will make the scheduler to say "ok, I gave enough time to interactive tasks, now I'm really going to spin one from the masses" will work. Having a clean solution would not be an option here.

... just as soon as I get my decidedly unclean work-around functioning at
least as well as it did for plain old irman. irman2 is _much_ more evil
than irman ever was (wow, good job!). I thought it'd be a half an hour tops. This little bugger shows active starvation, expired starvation, priority inflation, _and_ interactive starvation (i have to keep inventing new terms to describe things i see.. jeez this is a good testcase).

Quoted 10 lines · Mike Galbraith

Quoted 3 lines

Everything that will make the scheduler to say "ok, I gave enough time to interactive tasks, now I'm really going to spin one from the masses" will work. Having a clean solution would not be an option here.

... just as soon as I get my decidedly unclean work-around functioning at
least as well as it did for plain old irman. irman2 is _much_ more evil
than irman ever was (wow, good job!). I thought it'd be a half an hour tops. This little bugger shows active starvation, expired starvation, priority inflation, _and_ interactive starvation (i have to keep inventing new terms to describe things i see.. jeez this is a good testcase).

Yes, the problem is not only the expired tasks starvation. Anything in the active array that reside underneath the lower priority value of the range irman2 tasks oscillate inbetween, will experience a "CPU time eclipse". And you do not even need a smoked glass to look at it :)

Quoted 10 lines · Mike Galbraith

Quoted 3 lines

Everything that will make the scheduler to say "ok, I gave enough time to interactive tasks, now I'm really going to spin one from the masses" will work. Having a clean solution would not be an option here.

... just as soon as I get my decidedly unclean work-around functioning at
least as well as it did for plain old irman. irman2 is _much_ more evil
than irman ever was (wow, good job!). I thought it'd be a half an hour tops. This little bugger shows active starvation, expired starvation, priority inflation, _and_ interactive starvation (i have to keep inventing new terms to describe things i see.. jeez this is a good testcase).

Yes, the problem is not only the expired tasks starvation. Anything in the active array that reside underneath the lower priority value of the range irman2 tasks oscillate inbetween, will experience a "CPU time eclipse". And you do not even need a smoked glass to look at it :)

... Comments on the attached [kiss] approach?

Quoted 1 line · Nick Piggin

Mike Galbraith wrote:

That _might_ (add salt) be priorities of kernel threads dropping too low.

Quoted 3 lines · Mike Galbraith

Quoted 1 line · Nick Piggin

Mike Galbraith wrote:

That _might_ (add salt) be priorities of kernel threads dropping too low.

Is there any good reason for the priorities of kernel threads to vary at all? In the original design they are subject to the same interactivity changes as other processes and I've maintained that but I can't see a good reason for it and plan to change it unless someone tells me otherwise.

Quoted 6 lines · Davide Libenzi

http://www.xmailserver.org/linux-patches/irman2.c

and run it with different -n (number of tasks) and -b (CPU burn ms time). At the same time try to build a kernel for example. Then you will realize that interactivity is not the bigger problem that the scheduler has right now.

I added an irman2 load to contest. Con's changes 06+06.1 stomped it flat [1]. irman2 is modified to run for 30s at a time, but with default parameters.

Quoted 9 lines · Mike Galbraith

Quoted 6 lines · Davide Libenzi

http://www.xmailserver.org/linux-patches/irman2.c

and run it with different -n (number of tasks) and -b (CPU burn ms time). At the same time try to build a kernel for example. Then you will realize that interactivity is not the bigger problem that the scheduler has right now.

Quoted 2 lines

I added an irman2 load to contest. Con's changes 06+06.1 stomped it flat [1]. irman2 is modified to run for 30s at a time, but with default

parameters.

In my case I cannot even estimate the time. It takes 8:33 ususally to do a bzImage, and after 15 minutes I ctrl-c with only two lines printed in the console. If you consider the ratio between the total number of lines that a kernel build spits out, this couls have taken hours. Also, you might

want also to try a low number of processes with a short burn, like the new patch seems to do to better hit mm players. Something like:

irman2 -n 10 -b 40

Guys, I'm saying this not because I do not appreciate the time Con is spending on it. I just hate to see time spent in the wrong priorities. Whatever super privileged sleep->burn pattern you code, it can be exploited w/out a global throttle for the CPU time assigned to interactive and non interactive tasks. This is Unix guys and it is used in multi-user environments, we cannot ship with a flaw like this.

Quoted 2 lines · Mike Galbraith

Telling to not mess with my kernel threads seems to have fixed it here... no stalls during the whole contest run. New contest numbers attached.

It is ok to use unfairness towards kernel threads to avoid starvation. We control them. It is right to apply uncontrolled unfairness to userspace tasks though.