linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [RFC][PATCH] SCHED_ISO for interactivity
@ 2003-07-11 10:53 Con Kolivas
       [not found] ` <1068.::ffff:217.208.49.177.1057927722.squirrel@lanil.mine.nu>
  2003-07-12 15:49 ` William Lee Irwin III
  0 siblings, 2 replies; 24+ messages in thread
From: Con Kolivas @ 2003-07-11 10:53 UTC (permalink / raw)
  To: linux kernel mailing list; +Cc: Daniel Phillips

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

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

After the recent discussions about the limitations on real time tasks and 
normal users...

Wli coined the term "isochronous" (greek for same time) for a real time task 
that was limited in it's timeslice but still guaranteed to run. I've decided 
to abuse this term and use it to name this new policy in this patch. This is 
neither real time, nor guaranteed.

What this patch does is introduce a new scheduler policy, SCHED_ISO. SI tasks 
get the maximum interactive bonus so they always get a dynamic priority of 5 
better than their static priority, but are penalised by having a smaller 
timeslice. Most interactive tasks don't use up their full timeslice anyway.

Since most users and applications are not going to be altering scheduler 
policies, this patch uses the current semantics in patches up to the O4int 
patch I have posted previously (and in 2.5.75-mm1) to dynamically allocate 
tasks as SI. This happens when their sleep avg hits MAX_SLEEP_AVG which is 
extremely unlikely to happen for the wrong task. Unfortunately it also means 
it takes at least 10 seconds. There are semantics in place to stop it 
happening to idle tasks, tasks forking, and new children.

Anyway it's pretty rough around the edges since I slapped it together more to 
prove it works, but appears to work as planned. The O*int patches appear to 
be hitting a ceiling to their ability and this can help them further but I 
need some feedback about it's usefulness, and appropriateness. 

Without further feedback about the O*int patches I can't do much to develop 
them further.

akpm: obviously this one is not to be included in -mm 

Enough talk. The patch is attached below and available at:
http://kernel.kolivas.org/2.5
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)

iD8DBQE/DpcyF6dfvkL3i1gRAjp9AJ9S30i7ZQjpM7ETsxchKuLnDaL8GgCfb9OU
xl8PGFqY5BXEWPs83OaUCLY=
=cUdC
-----END PGP SIGNATURE-----

[-- Attachment #2: patch-SI-0307111938 --]
[-- Type: text/x-diff, Size: 5578 bytes --]

--- linux-2.5.74-mm3/include/linux/sched.h	2003-07-10 10:23:14.000000000 +1000
+++ linux-2.5.74-test/include/linux/sched.h	2003-07-11 19:35:37.000000000 +1000
@@ -125,6 +125,7 @@ extern unsigned long nr_iowait(void);
 #define SCHED_NORMAL		0
 #define SCHED_FIFO		1
 #define SCHED_RR		2
+#define SCHED_ISO		3
 
 struct sched_param {
 	int sched_priority;
--- linux-2.5.74-mm3/kernel/exit.c	2003-07-10 10:23:14.000000000 +1000
+++ linux-2.5.74-test/kernel/exit.c	2003-07-11 19:35:37.000000000 +1000
@@ -223,7 +223,7 @@ void reparent_to_init(void)
 	/* Set the exit signal to SIGCHLD so we signal init on exit */
 	current->exit_signal = SIGCHLD;
 
-	if ((current->policy == SCHED_NORMAL) && (task_nice(current) < 0))
+	if ((current->policy == SCHED_NORMAL || current->policy == SCHED_ISO) && (task_nice(current) < 0))
 		set_user_nice(current, 0);
 	/* cpus_allowed? */
 	/* rt_priority? */
--- linux-2.5.74-mm3/kernel/sched.c	2003-07-11 19:43:34.000000000 +1000
+++ linux-2.5.74-test/kernel/sched.c	2003-07-11 19:38:09.000000000 +1000
@@ -76,7 +76,6 @@
 #define MIN_SLEEP_AVG		(HZ)
 #define MAX_SLEEP_AVG		(10*HZ)
 #define STARVATION_LIMIT	(10*HZ)
-#define SLEEP_BUFFER		(HZ/20)
 #define NODE_THRESHOLD		125
 #define MAX_BONUS		((MAX_USER_PRIO - MAX_RT_PRIO) * PRIO_BONUS_RATIO / 100)
 
@@ -118,6 +117,8 @@
 #define TASK_INTERACTIVE(p) \
 	((p)->prio <= (p)->static_prio - DELTA(p))
 
+#define iso_task(p)		((p)->policy == SCHED_ISO)
+
 /*
  * BASE_TIMESLICE scales user-nice values [ -20 ... 19 ]
  * to time slice values.
@@ -134,7 +135,10 @@
 
 static inline unsigned int task_timeslice(task_t *p)
 {
-	return BASE_TIMESLICE(p);
+	if (iso_task(p))
+		return (BASE_TIMESLICE(p) / 5 ? : 1);
+	else
+		return BASE_TIMESLICE(p);
 }
 
 /*
@@ -319,6 +323,10 @@ static inline void normalise_sleep(task_
 
 	p->sleep_avg = p->sleep_avg * MIN_SLEEP_AVG / old_avg_time;
 	p->avg_start = jiffies - MIN_SLEEP_AVG;
+
+	if (iso_task(p))
+		p->policy = SCHED_NORMAL;
+
 }
 
 /*
@@ -343,26 +351,32 @@ static int effective_prio(task_t *p)
 	if (rt_task(p))
 		return p->prio;
 
-	sleep_period = jiffies - p->avg_start;
+	if (!iso_task(p)){
+		sleep_period = jiffies - p->avg_start;
 
-	if (unlikely(!sleep_period))
-		return p->static_prio;
+		if (unlikely(!sleep_period))
+			return p->static_prio;
 
-	if (sleep_period > MAX_SLEEP_AVG)
-		sleep_period = MAX_SLEEP_AVG;
+		if (sleep_period > MAX_SLEEP_AVG)
+			sleep_period = MAX_SLEEP_AVG;
 
-	if (p->sleep_avg > sleep_period)
-		sleep_period = p->sleep_avg;
+		if (p->sleep_avg > sleep_period)
+			sleep_period = p->sleep_avg;
 
-	/*
-	 * The bonus is determined according to the accumulated
-	 * sleep avg over the duration the task has been running
-	 * until it reaches MAX_SLEEP_AVG. -ck
-	 */
-	bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*p->sleep_avg/sleep_period/100 -
-			MAX_USER_PRIO*PRIO_BONUS_RATIO/100/2;
+		/*
+		 * The bonus is determined according to the accumulated
+		 * sleep avg over the duration the task has been running
+		 * until it reaches MAX_SLEEP_AVG. -ck
+		 */
+		bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*p->sleep_avg/sleep_period/100 -
+				MAX_USER_PRIO*PRIO_BONUS_RATIO/100/2;
+
+	} else
+		bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO/100 -
+				MAX_USER_PRIO*PRIO_BONUS_RATIO/100/2;
 
 	prio = p->static_prio - bonus;
+
 	if (prio < MAX_RT_PRIO)
 		prio = MAX_RT_PRIO;
 	if (prio > MAX_PRIO-1)
@@ -401,6 +415,8 @@ static inline void activate_task(task_t 
 			p->avg_start = jiffies - MIN_SLEEP_AVG;
 			p->sleep_avg = MIN_SLEEP_AVG * (MAX_BONUS - INTERACTIVE_DELTA - 1) /
 				MAX_BONUS;
+			if (iso_task(p))
+				p->policy = SCHED_NORMAL;
 		} else {
 			/*
 			 * This code gives a bonus to interactive tasks.
@@ -422,13 +438,11 @@ static inline void activate_task(task_t 
 					(MAX_SLEEP_AVG + MIN_SLEEP_AVG - runtime) *
 					(MAX_BONUS - INTERACTIVE_DELTA) / MAX_BONUS / MAX_SLEEP_AVG;
 
-			/*
-			 * Keep a small buffer of SLEEP_BUFFER sleep_avg to
-			 * prevent fully interactive tasks from becoming
-			 * lower priority with small bursts of cpu usage.
-			 */
-			if (p->sleep_avg > (MAX_SLEEP_AVG + SLEEP_BUFFER))
-				p->sleep_avg = MAX_SLEEP_AVG + SLEEP_BUFFER;
+			if (p->sleep_avg > MAX_SLEEP_AVG){
+				if (p->policy == SCHED_NORMAL)
+					p->policy = SCHED_ISO;
+				p->sleep_avg = MAX_SLEEP_AVG;
+			}
 		}
 
 		if (unlikely(p->avg_start > jiffies)){
@@ -1813,7 +1827,7 @@ static int setscheduler(pid_t pid, int p
 	else {
 		retval = -EINVAL;
 		if (policy != SCHED_FIFO && policy != SCHED_RR &&
-				policy != SCHED_NORMAL)
+				policy != SCHED_NORMAL && policy != SCHED_ISO)
 			goto out_unlock;
 	}
 
@@ -1824,7 +1838,7 @@ static int setscheduler(pid_t pid, int p
 	retval = -EINVAL;
 	if (lp.sched_priority < 0 || lp.sched_priority > MAX_USER_RT_PRIO-1)
 		goto out_unlock;
-	if ((policy == SCHED_NORMAL) != (lp.sched_priority == 0))
+	if ((policy == SCHED_NORMAL || policy == SCHED_ISO) != (lp.sched_priority == 0))
 		goto out_unlock;
 
 	retval = -EPERM;
@@ -1846,7 +1860,7 @@ static int setscheduler(pid_t pid, int p
 	p->policy = policy;
 	p->rt_priority = lp.sched_priority;
 	oldprio = p->prio;
-	if (policy != SCHED_NORMAL)
+	if (policy == SCHED_FIFO || policy == SCHED_RR)
 		p->prio = MAX_USER_RT_PRIO-1 - p->rt_priority;
 	else
 		p->prio = p->static_prio;
@@ -2147,6 +2161,9 @@ asmlinkage long sys_sched_get_priority_m
 	case SCHED_NORMAL:
 		ret = 0;
 		break;
+	case SCHED_ISO:
+		ret = 0;
+		break;
 	}
 	return ret;
 }
@@ -2169,6 +2186,8 @@ asmlinkage long sys_sched_get_priority_m
 		break;
 	case SCHED_NORMAL:
 		ret = 0;
+	case SCHED_ISO:
+		ret = 0;
 	}
 	return ret;
 }

^ permalink raw reply	[flat|nested] 24+ messages in thread
* Re: [RFC][PATCH] SCHED_ISO for interactivity
@ 2003-07-13 10:41 Guillaume Chazarain
  2003-07-13 11:54 ` Christian Axelsson
  0 siblings, 1 reply; 24+ messages in thread
From: Guillaume Chazarain @ 2003-07-13 10:41 UTC (permalink / raw)
  To: linux-kernel

Hi Con,

I am currently testing SCHED_ISO, but I have noticed a regression:
I do a make -j5 in linux-2.5.75/ everything is OK since gcc prio is 25.
X and fvwm prio are 15, but when I move a window it's very jerky.

And btw, as I am interested in scheduler improvements, do you have a testcase
where the stock scheduler does the bad thing? Preferably without KDE nor
Mozilla (I don't have them installed, and I'll have access to a decent
connection in september).

BTW2, you all seem to test interactivity with xmms. Just for those like me
that didn't noticed, I have just found that it skips much less with alsa's
OSS emulation than with alsa-xmms.


Thanks,
Guillaume










^ permalink raw reply	[flat|nested] 24+ messages in thread
[parent not found: <JEPOQNA0LFV95MFCPMSKONGFSNX.3f113751@monpc>]
* Re: [RFC][PATCH] SCHED_ISO for interactivity
@ 2003-07-13 14:54 Guillaume Chazarain
  2003-07-14  0:07 ` Con Kolivas
  2003-07-14  4:05 ` Con Kolivas
  0 siblings, 2 replies; 24+ messages in thread
From: Guillaume Chazarain @ 2003-07-13 14:54 UTC (permalink / raw)
  To: Con Kolivas; +Cc: linux-kernel, phillips, smiler

13/07/03 14:53:12, Con Kolivas <kernel@kolivas.org> wrote:

>On Sun, 13 Jul 2003 20:41, Guillaume Chazarain wrote:
>> Hi Con,
>>
>> I am currently testing SCHED_ISO, but I have noticed a regression:
>> I do a make -j5 in linux-2.5.75/ everything is OK since gcc prio is 25.
>> X and fvwm prio are 15, but when I move a window it's very jerky.
>
>Interesting. I don't know how much smaller the timeslice can be before 
>different hardware will be affected. Can you report what cpu and video card 
>you're using? Unfortunately I don't have a range of hardware to test it on 
>and I chose the aggressive 1/5th timeslice size. Can you try with ISO_PENALTY 
>set to 2 instead?

Pentium3 450, 320 Mo RAM, Voodoo Banshee

Good, with ISO_PENALTY == 2, I can smoothly move big windows (with ISO_PENALTY == 5
it was smooth only with very small windows), but it lets me move them smoothly
during less time than stock :(

>> And btw, as I am interested in scheduler improvements, do you have a
>> testcase where the stock scheduler does the bad thing? Preferably without
>> KDE nor Mozilla (I don't have them installed, and I'll have access to a
>> decent connection in september).
>
>Transparency and antialiased fonts are good triggers. Launcing Xterm with 
>transparency has been known to cause skips. Also the obvious make -j 4 kernel 
>compiles, and 
>while true ; do a=2 ; done
>as a fast onset full cpu hog

Well, I had a hard time at making xmms skip with a transparent gnome-terminal.
I could easily make xmms skip with this, but it's quite artificial.

#include <sys/types.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>

/* Should be near MAX_SLEEP_AVG. */
#define DELAY 20

/* With how many processes, will xmms resist? */
#define NPROC 4

int main(void)
{
    int i;
    pid_t the_pid, my_pid;

    the_pid = getpid();

    /* Make some friends. */
    for (i = 1; i < NPROC; i++)
        if (fork())
            break;

    my_pid = getpid();

    for (;;) {
        /* Wait, gain interactivity. */
        for (i = DELAY; i >= 0; i--) {
            if (the_pid == my_pid)
                printf("%d\n", i);
            sleep(1);
        }

        /* Attack! */
        if (my_pid == the_pid)
            puts("attack");
        for (i = 0; i < 100000000; i++);
    }

    return 0;
}

>The logical conclusion of this idea where there is a dynamic policy assigned 
>to interactive tasks is a dynamic policy assigned to non interactive tasks 
>that get treated in the opposite way. I'll code something for that soon, now 
>that I've had more feedback on the first part.

Interesting, let's see :)
But as the interactive bonus can already be negative I wonder what use
will have another variable.


Guillaume






^ permalink raw reply	[flat|nested] 24+ messages in thread
* Re: [RFC][PATCH] SCHED_ISO for interactivity
@ 2003-07-14 15:40 Guillaume Chazarain
  2003-07-14 21:45 ` Con Kolivas
  0 siblings, 1 reply; 24+ messages in thread
From: Guillaume Chazarain @ 2003-07-14 15:40 UTC (permalink / raw)
  To: Con Kolivas; +Cc: linux-kernel, phillips, smiler

14/07/03 02:07:34, Con Kolivas <kernel@kolivas.org> wrote:
>On Mon, 14 Jul 2003 00:54, Guillaume Chazarain wrote:
>> Good, with ISO_PENALTY == 2, I can smoothly move big windows (with
>> ISO_PENALTY == 5 it was smooth only with very small windows), but it lets
>> me move them smoothly during less time than stock :(
>
>Less time than stock? I don't understand you. You can only move them smoothly 
>for a small time or they move faster or... ?

With the previous SCHED_ISO, moving big windows was smooth for a short time,
but then it became jerky.  Unlike with stock where it was smooth all the time.

>Indeed it is artificial, and probably never a real world condition unless it 
>was specifically an attack, but it would never bring the system to a halt, 
>just some minor audio hiccups while it adjusted. 

This is also true for stock.

>> >The logical conclusion of this idea where there is a dynamic policy
>> > assigned to interactive tasks is a dynamic policy assigned to non
>> > interactive tasks that get treated in the opposite way. I'll code
>> > something for that soon, now that I've had more feedback on the first
>> > part.
>>
>> Interesting, let's see :)
>> But as the interactive bonus can already be negative I wonder what use
>> will have another variable.
>
>As it is, the penalty will be no different to what it currently gets to (in 
>the same way sched_iso get the same bonus they normally would). The 
>difference is once they are moved to the different policy it is much harder 
>for them to change from that state, always getting the maximum penalty, and 
>being expired each time they run out of timeslice instead of getting a chance 
>to be put onto the active array. Neither of these new states is very 
>different to what normal policy tasks get except for the fact they dont 
>change interactive state without a lot more effort.

OK, the latest SCHED_ISO fixed my problem, but now I am afraid of the scheduler
trying to be too intelligent, because if it makes the wrong choice the bad result
will be much more noticeable.
I like the simplicity of stock, the interactivity bonus is given in a simple and
understandable way, and if it's not given to the process you want, you can always
renice it or make it RT.

I have to admit that
p->sleep_avg = MIN_SLEEP_AVG * (MAX_BONUS - INTERACTIVE_DELTA - 1) / MAX_BONUS;
and
if ((runtime - MIN_SLEEP_AVG < MAX_SLEEP_AVG) && (runtime * JUST_INTERACTIVE > p->sleep_avg))
	p->sleep_avg += (runtime * JUST_INTERACTIVE - p->sleep_avg) *
	                (MAX_SLEEP_AVG + MIN_SLEEP_AVG - runtime) / MAX_SLEEP_AVG;

are quite obscure to me.

Also, I don't understand your MAX_BONUS definition:
((MAX_USER_PRIO - MAX_RT_PRIO) * PRIO_BONUS_RATIO / 100) it evaluates to -15

I would use ((MAX_PRIO - MAX_RT_PRIO) * PRIO_BONUS_RATIO / 100 / 2) since it gives 5.


Guillaume







^ permalink raw reply	[flat|nested] 24+ messages in thread
end of thread, other threads:[~2003-07-14 21:30 UTC | newest]

Thread overview: 24+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2003-07-11 10:53 [RFC][PATCH] SCHED_ISO for interactivity Con Kolivas
     [not found] ` <1068.::ffff:217.208.49.177.1057927722.squirrel@lanil.mine.nu>
2003-07-11 14:30   ` Con Kolivas
2003-07-11 23:37     ` Christian Axelsson
2003-07-12  0:13       ` Con Kolivas
2003-07-12 15:39         ` Con Kolivas
2003-07-12 16:27           ` Michael Buesch
2003-07-12 16:28           ` Christian Axelsson
2003-07-13  2:26             ` Con Kolivas
2003-07-13  3:40               ` Christian Axelsson
2003-07-13 20:07               ` Daniel Phillips
2003-07-12 15:49 ` William Lee Irwin III
2003-07-12 15:53   ` Con Kolivas
2003-07-13 20:03   ` Daniel Phillips
2003-07-14  0:13     ` Con Kolivas
2003-07-14  2:40       ` Daniel Phillips
2003-07-13 10:41 Guillaume Chazarain
2003-07-13 11:54 ` Christian Axelsson
2003-07-13 14:06   ` Con Kolivas
     [not found] <JEPOQNA0LFV95MFCPMSKONGFSNX.3f113751@monpc>
2003-07-13 12:53 ` Con Kolivas
2003-07-13 14:54 Guillaume Chazarain
2003-07-14  0:07 ` Con Kolivas
2003-07-14  4:05 ` Con Kolivas
2003-07-14 15:40 Guillaume Chazarain
2003-07-14 21:45 ` Con Kolivas

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).