[test] hackbench.c interactivity results: vanilla versus SD/RSDL

[test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Ingo Molnar]

* Ingo Molnar <mingo@elte.hu> wrote:

> * Con Kolivas <kernel@kolivas.org> wrote:
> 
> > I'm cautiously optimistic that we're at the thin edge of the bugfix 
> > wedge now.
[...]

> and the numbers he posted:
> 
>  http://marc.info/?l=linux-kernel&m=117448900626028&w=2
> 
> his test conclusion was that under CPU load, RSDL (SD) generally does 
> not hold up to mainline's interactivity.

Today i've done some hackbench.c (which is similar to VolanoMark) 
interactivity testing on SD-latest (v0.37), doing "hackbench 10", 
"hackbench 50" and "hackbench 100" runs, comparing it to 
vanilla+Mike's-task-promotion-patch.

Performance
-----------

performance was largely comparable, within noise: the vanilla scheduler 
was slightly (~5%) better at "hackbench 10", SD and vanilla was within 
noise on "hackbench 50" and "hackbench 100" runs. (I think vanilla's 
better results might be due to the longer timeslices vanilla can give 
out - SD has to operate via short timeslices, by design.)

Shell interactivity
-------------------

The vanilla scheduler kept the shell completely usable during all tests: 
'ls' output was instantaneous and characters could be typed without 
delay.

The SD/RSDL scheduler kept the shell barely usable during the hackbench 
10 test, and it was completely unusable during the hackbench 50 and 100 
tests. A simple 'ls' took 2-3 seconds to complete (up to 6 seconds at 
times) and the shell printed characters in a very laggy way. 'vi' was 
totally unusable, etc. etc.

[ i've also re-tested this with RSDL 0.34, and there interactivity got 
  better although it still didnt match that of the vanilla scheduler's
  interactivity. So this is a definitive SD regression. ]

[ A quick guess: could SD's substandard interactivity in this test be 
  due to the SMP migration logic inconsistencies Mike noticed? This is 
  an SMP system and the hackbench workload is very scheduling intense 
  and tasks are frequently queued from one CPU to another. ]

Conclusion
----------

i consider this a must-fix item as SD badly misbehaves under this 
workload.

Test environment details
------------------------

the test system is a 2GHz Athlon64 dual-core box. All tests were running 
on default nice 0 levels. All tests were done 10 times on a totally idle 
test-system. Mike's patch is the one that improves vanilla scheduler's 
anti-starvation code:

   http://marc.info/?l=linux-kernel&m=117507110922009&w=2

( Mike's patch does not make a measurable performance difference in
  hackbench, nor does it make a visible interactivity difference for 
  this workload, but since i think Mike's patch improves the vanilla 
  scheduler i included it in the test for completeness, so that both 
  variants of interactivity code are at the 'bleeding edge'. )

	Ingo

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Con Kolivas]

On Thursday 29 March 2007 21:22, Ingo Molnar wrote:
> [ A quick guess: could SD's substandard interactivity in this test be
>   due to the SMP migration logic inconsistencies Mike noticed? This is
>   an SMP system and the hackbench workload is very scheduling intense
>   and tasks are frequently queued from one CPU to another. ]

I assume you put it on and endless loop since hackbench 10 runs for .5 second 
on my machine. Doubtful it's an SMP issue. update_if_moved should maintain 
cross cpu scheduling decisions. The same slowdown would happen on UP and is 
almost certainly due to the fact that hackbench 10 induces a load of _160_ on 
the machine.

-- 
-ck

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Mike Galbraith]

On Tue, 2007-04-03 at 12:34 +1000, Con Kolivas wrote:
> On Saturday 31 March 2007 19:28, Xenofon Antidides wrote:
> > For long time now I use windows to work 
> > problems. I cannot play wine games with audio, I
> > cannot sample video, I cannot use skype, I cannot play
> > midi. And even linux only things I try do I cannot
> > share my X, I cannot use more than one vmware. All
> > those is fix for me with SD.
> 
> Any semblance of cpu bandwidth and latency guarantees are easily shot on 
> mainline by a single process going wild (eg open tab in firefox).

I've written a patch which I believe fixes that.

	-Mike

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Con Kolivas]

On Saturday 31 March 2007 19:28, Xenofon Antidides wrote:
> For long time now I use windows to work 
> problems. I cannot play wine games with audio, I
> cannot sample video, I cannot use skype, I cannot play
> midi. And even linux only things I try do I cannot
> share my X, I cannot use more than one vmware. All
> those is fix for me with SD.

Any semblance of cpu bandwidth and latency guarantees are easily shot on 
mainline by a single process going wild (eg open tab in firefox).

> I sorry I answer kernel 
> email and go away now for good.

respected; dropped from cc

-- 
-ck

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Ingo Molnar]

Xenofon,

could you tell us a bit more about the specs of your system? What CPU 
speed for example? (i suspect it's a single-CPU box, right?)

	Ingo

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Ingo Molnar]

* Xenofon Antidides <xantidides@yahoo.gr> wrote:

> [...] I cannot play wine games with audio, I cannot sample video, I 
> cannot use skype, I cannot play midi. And even linux only things I try 
> do I cannot share my X, I cannot use more than one vmware. [...]

strange - i can do such things (and other things) with the vanilla 
scheduler (except vmware which i dont run). It would be nice to debug 
your 'cannot play midi' problem for example - could you try to describe 
it a bit more accurately so that we can try to reproduce it and fix it? 
(in the alternative i can send you tracing patches to capture what the 
scheduler does and how)

also, could you possibly try these workloads you described with Mike's 
latest patch too? Thanks,

	Ingo

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Xenofon Antidides]

--- Mike Galbraith <efault@gmx.de> wrote:

> On Fri, 2007-03-30 at 22:41 -0700, Xenofon Antidides
> wrote:
> 
> > Patch makes X yuck with any load. I stick with SD.
> 
> Shrug.  My milage is different, but hey, it's a work
> in progress.  If SD
> ever gets to the point that it actually delivers
> what it claims, I may
> join you.
> 
> In the meantime, IMHO mainline is MUCH better in the
> general case.  If
> the general case was that which the various sleep
> exploits do, the
> history mechanism in mainline wouldn't have survived
> it's first day.
> 
> 	-Mike

I have no any idea what is wrong to you. Mainline is
skata to me. For long time now I use windows to work
problems. I cannot play wine games with audio, I
cannot sample video, I cannot use skype, I cannot play
midi. And even linux only things I try do I cannot
share my X, I cannot use more than one vmware. All
those is fix for me with SD. I sorry I answer kernel
email and go away now for good.

Xant


 
____________________________________________________________________________________
Now that's room service!  Choose from over 150,000 hotels
in 45,000 destinations on Yahoo! Travel to find your fit.
http://farechase.yahoo.com/promo-generic-14795097

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Mike Galbraith]

On Sat, 2007-03-31 at 08:31 +0200, Mike Galbraith wrote:
> On Fri, 2007-03-30 at 22:41 -0700, Xenofon Antidides wrote:
> 
> > Patch makes X yuck with any load. I stick with SD.

General comment directed at nobody in particular:

If anyone thinks the current scheduler sucks rocks, maybe they should
try to fix it.  If they think SD is the best thing since sliced bread,
maybe they should help Con fix that.  Code talks...

	-Mike

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Mike Galbraith]

On Fri, 2007-03-30 at 22:41 -0700, Xenofon Antidides wrote:

> Patch makes X yuck with any load. I stick with SD.

Shrug.  My milage is different, but hey, it's a work in progress.  If SD
ever gets to the point that it actually delivers what it claims, I may
join you.

In the meantime, IMHO mainline is MUCH better in the general case.  If
the general case was that which the various sleep exploits do, the
history mechanism in mainline wouldn't have survived it's first day.

	-Mike

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Mike Galbraith]

On Sat, 2007-03-31 at 05:42 +0200, Mike Galbraith wrote:

> Yesterday, I piddled around with tracking interactive backlog as a way
> to detect when the load isn't really an interactive load, that's very
> simple and has potential.

Kinda like the patch below (though it can all be done slow path), or
something like my old throttling patches do (for grins I revived one,
and watched it yawn at your exploit)...

top - 07:49:36 up 6 min, 13 users,  load average: 4.42, 3.11, 1.40

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  P COMMAND
 6027 root      20   0  1564  104   24 R   45  0.0   0:09.47 1 fiftypercent
 6028 root      19   0  1564  104   24 R   40  0.0   0:09.43 1 fiftypercent
 6025 root      25   0  2892 1240 1032 R   32  0.1   0:09.04 1 sh
 6024 root      16   0  1564  436  356 S   30  0.0   0:10.45 0 fiftypercent
 6026 root      15   0  1564  104   24 R   27  0.0   0:09.52 0 fiftypercent
 6029 root      16   0  1564  104   24 R   18  0.0   0:09.33 0 fiftypercent

...or both, or maybe something clever instead :)

--- kernel/sched.c.org	2007-03-27 15:47:49.000000000 +0200
+++ kernel/sched.c	2007-03-31 06:56:57.000000000 +0200
@@ -109,6 +109,7 @@ unsigned long long __attribute__((weak))
 #define MAX_SLEEP_AVG		(DEF_TIMESLICE * MAX_BONUS)
 #define STARVATION_LIMIT	(MAX_SLEEP_AVG)
 #define NS_MAX_SLEEP_AVG	(JIFFIES_TO_NS(MAX_SLEEP_AVG))
+#define INTERACTIVE_LIMIT	(DEF_TIMESLICE * 4)
 
 /*
  * If a task is 'interactive' then we reinsert it in the active
@@ -167,6 +168,9 @@ unsigned long long __attribute__((weak))
 	(JIFFIES_TO_NS(MAX_SLEEP_AVG * \
 		(MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1))
 
+#define INTERACTIVE_BACKLOG_EXCEEDED(array) \
+	((array)->interactive_ticks > INTERACTIVE_LIMIT)
+
 #define TASK_PREEMPTS_CURR(p, rq) \
 	((p)->prio < (rq)->curr->prio)
 
@@ -201,6 +205,7 @@ static inline unsigned int task_timeslic
 
 struct prio_array {
 	unsigned int nr_active;
+	int interactive_ticks;
 	DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */
 	struct list_head queue[MAX_PRIO];
 };
@@ -234,6 +239,7 @@ struct rq {
 	 */
 	unsigned long nr_uninterruptible;
 
+	unsigned long switch_timestamp;
 	unsigned long expired_timestamp;
 	/* Cached timestamp set by update_cpu_clock() */
 	unsigned long long most_recent_timestamp;
@@ -691,6 +697,8 @@ static void dequeue_task(struct task_str
 	list_del(&p->run_list);
 	if (list_empty(array->queue + p->prio))
 		__clear_bit(p->prio, array->bitmap);
+	if (TASK_INTERACTIVE(p))
+		array->interactive_ticks -= p->time_slice;
 }
 
 static void enqueue_task(struct task_struct *p, struct prio_array *array)
@@ -700,6 +708,8 @@ static void enqueue_task(struct task_str
 	__set_bit(p->prio, array->bitmap);
 	array->nr_active++;
 	p->array = array;
+	if (TASK_INTERACTIVE(p))
+		array->interactive_ticks += p->time_slice;
 }
 
 /*
@@ -882,7 +892,11 @@ static int recalc_task_prio(struct task_
 	/* Caller must always ensure 'now >= p->timestamp' */
 	unsigned long sleep_time = now - p->timestamp;
 
-	if (batch_task(p))
+	/*
+	 * Migration timestamp adjustment may induce negative time.
+	 * Ignore unquantifiable values as well as SCHED_BATCH tasks.
+	 */ 
+	if (now < p->timestamp || batch_task(p))
 		sleep_time = 0;
 
 	if (likely(sleep_time > 0)) {
@@ -3051,9 +3065,9 @@ static inline int expired_starving(struc
 {
 	if (rq->curr->static_prio > rq->best_expired_prio)
 		return 1;
-	if (!STARVATION_LIMIT || !rq->expired_timestamp)
+	if (!STARVATION_LIMIT)
 		return 0;
-	if (jiffies - rq->expired_timestamp > STARVATION_LIMIT * rq->nr_running)
+	if (jiffies - rq->switch_timestamp > STARVATION_LIMIT * rq->nr_running)
 		return 1;
 	return 0;
 }
@@ -3131,8 +3145,74 @@ void account_steal_time(struct task_stru
 		cpustat->steal = cputime64_add(cpustat->steal, tmp);
 }
 
+/*
+ * Promote and requeue the next lower priority task.  If no task
+ * is available in the active array, switch to the expired array.
+ * @rq: runqueue to search.
+ * @prio: priority at which to begin search.
+ */
+static inline void promote_next_lower(struct rq *rq, int prio)
+{
+	struct prio_array *array = rq->active;
+	struct task_struct *p = NULL;
+	unsigned long long now = rq->most_recent_timestamp;
+	unsigned long *bitmap;
+	unsigned long starving = JIFFIES_TO_NS(rq->nr_running * DEF_TIMESLICE);
+	int idx = prio + 1, found_noninteractive = 0;
+
+repeat:
+	bitmap = array->bitmap;
+	idx = find_next_bit(bitmap, MAX_PRIO, idx);
+	if (idx < MAX_PRIO) {
+		struct list_head *queue = array->queue + idx;
+
+		p = list_entry(queue->next, struct task_struct, run_list);
+		if (!TASK_INTERACTIVE(p))
+			found_noninteractive = 1;
+
+		/* Skip non-starved queues. */
+		if (now < p->last_ran + starving) {
+			idx++;
+			p = NULL;
+			goto repeat;
+		}
+	} else if (!found_noninteractive && array == rq->active) {
+		/* Nobody home, check the expired array. */
+		array = rq->expired;
+		idx = 0;
+		p = NULL;
+		goto repeat;
+	}
+
+	/* Found one, requeue it. */
+	if (p) {
+		dequeue_task(p, p->array);
+		if (array == rq->active)
+			p->prio--;
+		/*
+		 * If we pulled a task from the expired array, correct
+		 * expired array info.  We can't afford a full search
+		 * for best_expired_prio, but do the best we can.
+		 */
+		else {
+			idx = sched_find_first_bit(array->bitmap);
+			if (idx < MAX_PRIO) {
+				if (rq->best_expired_prio > idx)
+					rq->best_expired_prio = idx;
+			} else {
+				/* We emptied the array */
+				rq->best_expired_prio = MAX_PRIO;
+				rq->switch_timestamp = jiffies;
+			}
+		}
+		enqueue_task(p, rq->active);
+	}
+}
+
 static void task_running_tick(struct rq *rq, struct task_struct *p)
 {
+	int task_was_interactive;
+
 	if (p->array != rq->active) {
 		/* Task has expired but was not scheduled yet */
 		set_tsk_need_resched(p);
@@ -3161,21 +3241,41 @@ static void task_running_tick(struct rq 
 		}
 		goto out_unlock;
 	}
+
+	/*
+	 * Tick off interactive task ticks from the active array.
+	 */
+	task_was_interactive = TASK_INTERACTIVE(p);
+	if (task_was_interactive && --rq->active->interactive_ticks < 0)
+		rq->active->interactive_ticks = 0;
+
 	if (!--p->time_slice) {
+		int expire_limit = STARVATION_LIMIT;
+
 		dequeue_task(p, rq->active);
 		set_tsk_need_resched(p);
 		p->prio = effective_prio(p);
 		p->time_slice = task_timeslice(p);
 		p->first_time_slice = 0;
 
-		if (!rq->expired_timestamp)
-			rq->expired_timestamp = jiffies;
 		if (!TASK_INTERACTIVE(p) || expired_starving(rq)) {
 			enqueue_task(p, rq->expired);
 			if (p->static_prio < rq->best_expired_prio)
 				rq->best_expired_prio = p->static_prio;
+			if (!task_was_interactive)
+				rq->expired_timestamp = jiffies;
 		} else
 			enqueue_task(p, rq->active);
+
+		/*
+		 * If we haven't expired a non-interactive task within
+		 * STARVATION_LIMIT ticks, or the current interactive
+		 * load exceeds INTERACTIVE_BACKLOG, start promoting
+		 * lower priority tasks.
+		 */
+		if (time_after(jiffies, rq->expired_timestamp + expire_limit) ||
+				INTERACTIVE_BACKLOG_EXCEEDED(rq->active))
+			promote_next_lower(rq, p->prio);
 	} else {
 		/*
 		 * Prevent a too long timeslice allowing a task to monopolize
@@ -3356,7 +3456,7 @@ need_resched_nonpreemptible:
 		idle_balance(cpu, rq);
 		if (!rq->nr_running) {
 			next = rq->idle;
-			rq->expired_timestamp = 0;
+			rq->switch_timestamp = jiffies;
 			goto switch_tasks;
 		}
 	}
@@ -3370,7 +3470,8 @@ need_resched_nonpreemptible:
 		rq->active = rq->expired;
 		rq->expired = array;
 		array = rq->active;
-		rq->expired_timestamp = 0;
+		array->interactive_ticks = 0;
+		rq->switch_timestamp = jiffies;
 		rq->best_expired_prio = MAX_PRIO;
 	}
 

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Xenofon Antidides]

--- Mike Galbraith <efault@gmx.de> wrote:

> On Fri, 2007-03-30 at 19:36 -0700, Xenofon Antidides
> wrote:
> 
> > Something different on many cpus? Sorry I was
> thinking
> > something other. I try 50% run + 50% sleep on one
> cpu
> > and mainline has big problem. Sorry for bad code I
> > copy bits to make it work. Start program first
> then
> > run bash 100% cpu (while : ; do : ; done). Try
> change
> > program forks from 1 till 3 or more mainline
> kernel
> > and bash gets 0%.

Mainline hangs with program. SD does not have problem
with program and is more responsible then mainline.

> That's mainline with the below (which I'm trying
> various ideas to improve).

Patch makes X yuck with any load. I stick with SD.

Xant


 
____________________________________________________________________________________
Bored stiff? Loosen up... 
Download and play hundreds of games for free on Yahoo! Games.
http://games.yahoo.com/games/front

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Nick Piggin]

Xenofon Antidides wrote:
> ----- Original Message ----
> From: Ingo Molnar <mingo@elte.hu>
> To: Con Kolivas <kernel@kolivas.org>
> Cc: linux list <linux-kernel@vger.kernel.org>; Andrew Morton <akpm@linux-foundation.org>; Mike Galbraith <efault@gmx.de>
> Sent: Thursday, March 29, 2007 9:22:49 PM
> Subject: [test] hackbench.c interactivity results: vanilla versus SD/RSDL
> 
> 
> * Ingo Molnar <mingo@elte.hu> wrote:
> 
> 
>>* Con Kolivas <kernel@kolivas.org> wrote:
>>
>>
>>>I'm cautiously optimistic that we're at the thin edge of the bugfix 
>>>wedge now.
> 
> [...]
> 
> 
>>and the numbers he posted:
>>
>> http://marc.info/?l=linux-kernel&m=117448900626028&w=2
> 
> 
> We been staring at these numbers for while now and we come to the conclusion they wrong.
> 
> The test is f is 3 tasks, two on different and one on same cpu as sh here:
> virgin 2.6.21-rc3-rsdl-smp
> top - 13:52:50 up 7 min, 12 users,  load average: 3.45, 2.89, 1.51
> 
>   PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  P COMMAND
>  6560 root      31   0  2892 1236 1032 R   82  0.1   1:50.24 1 sh
>  6558 root      28   0  1428  276  228 S   42  0.0   1:00.09 1 f
>  6557 root      30   0  1424  280  228 R   35  0.0   1:00.25 0 f
>  6559 root      39   0  1424  276  228 R   33  0.0   0:58.36 0 f
> 
> 6560 sh is asking for 100% cpu on cpu number 1
> 6558 f is asking for 50% cpu on cpu number 1
> 6557 f is asking for 50% cpu on cpu number 0
> 6559 f is asking for 50% cpu on cpu number 0
> 
> So if 6560 and 6558 are asking for cpu from cpu number 1:
> 6560 wants 100% and 6558 wants 50%.
> 6560 should get 2/3 cpu 6558 should get 1/3 cpu

I don't think you can say that. If the 50% task alternated between
long periods of running and sleeping, then the end result should
approach a task that is sleeping for 50% of the time, and on the
CPU 25% of the time. As the periods get shorter, then the schedulers
will favour the 50% task relatively more, but details will depend on
implementation.

You could have an implementation that always gives runs the 50% task
when it becomes runnable, because it is decided that its priority is
higher because it has been sleeping.

The only thing you can really say is that the 50% task should get
between 25% and 50% (inclusive) CPU time.

-- 
SUSE Labs, Novell Inc.

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Mike Galbraith]

On Sat, 2007-03-31 at 05:23 +0200, Mike Galbraith wrote:
> On Fri, 2007-03-30 at 19:36 -0700, Xenofon Antidides wrote:
> 
> > Something different on many cpus? Sorry I was thinking
> > something other. I try 50% run + 50% sleep on one cpu
> > and mainline has big problem. Sorry for bad code I
> > copy bits to make it work. Start program first then
> > run bash 100% cpu (while : ; do : ; done). Try change
> > program forks from 1 till 3 or more mainline kernel
> > and bash gets 0%.
> 
> top - 05:16:41 up 43 min, 13 users,  load average: 9.51, 4.32, 5.67
> 
>   PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  P COMMAND
>  7146 root      15   0  1564  104   24 R   43  0.0   0:20.74 0 fiftypercent
>  7142 root      15   0  1564  104   24 S   37  0.0   0:18.08 0 fiftypercent
>  7140 root      15   0  1564  436  356 R   21  0.0   0:18.94 1 fiftypercent
>  7144 root      15   0  1564  104   24 R   21  0.0   0:18.75 1 fiftypercent
>  7143 root      15   0  1564  104   24 R   20  0.0   0:18.85 1 fiftypercent
>  7145 root      15   0  1564  104   24 R   19  0.0   0:18.30 1 fiftypercent
>  7147 root      15   0  1564  104   24 R   19  0.0   0:18.03 1 fiftypercent
>  7141 root      16   0  1564  104   24 R   10  0.0   0:18.29 0 fiftypercent
>  6245 root      16   0  3368 1876 1376 R    7  0.2   0:49.81 0 bash
> 
> That's mainline with the below (which I'm trying various ideas to improve).

Note: that's not an sh -c started at the same time as the 50% duty cycle
dos, the pertinent data is that bash is getting into the loop.

Yesterday, I piddled around with tracking interactive backlog as a way
to detect when the load isn't really an interactive load, that's very
simple and has potential.

	-Mike

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Mike Galbraith]

On Fri, 2007-03-30 at 19:36 -0700, Xenofon Antidides wrote:

> Something different on many cpus? Sorry I was thinking
> something other. I try 50% run + 50% sleep on one cpu
> and mainline has big problem. Sorry for bad code I
> copy bits to make it work. Start program first then
> run bash 100% cpu (while : ; do : ; done). Try change
> program forks from 1 till 3 or more mainline kernel
> and bash gets 0%.

top - 05:16:41 up 43 min, 13 users,  load average: 9.51, 4.32, 5.67

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  P COMMAND
 7146 root      15   0  1564  104   24 R   43  0.0   0:20.74 0 fiftypercent
 7142 root      15   0  1564  104   24 S   37  0.0   0:18.08 0 fiftypercent
 7140 root      15   0  1564  436  356 R   21  0.0   0:18.94 1 fiftypercent
 7144 root      15   0  1564  104   24 R   21  0.0   0:18.75 1 fiftypercent
 7143 root      15   0  1564  104   24 R   20  0.0   0:18.85 1 fiftypercent
 7145 root      15   0  1564  104   24 R   19  0.0   0:18.30 1 fiftypercent
 7147 root      15   0  1564  104   24 R   19  0.0   0:18.03 1 fiftypercent
 7141 root      16   0  1564  104   24 R   10  0.0   0:18.29 0 fiftypercent
 6245 root      16   0  3368 1876 1376 R    7  0.2   0:49.81 0 bash

That's mainline with the below (which I'm trying various ideas to improve).

--- linux-2.6.21-rc5/kernel/sched.c.org	2007-03-27 15:47:49.000000000 +0200
+++ linux-2.6.21-rc5/kernel/sched.c	2007-03-30 18:21:12.000000000 +0200
@@ -234,6 +234,7 @@ struct rq {
 	 */
 	unsigned long nr_uninterruptible;
 
+	unsigned long switch_timestamp;
 	unsigned long expired_timestamp;
 	/* Cached timestamp set by update_cpu_clock() */
 	unsigned long long most_recent_timestamp;
@@ -882,7 +883,11 @@ static int recalc_task_prio(struct task_
 	/* Caller must always ensure 'now >= p->timestamp' */
 	unsigned long sleep_time = now - p->timestamp;
 
-	if (batch_task(p))
+	/*
+	 * Migration timestamp adjustment may induce negative time.
+	 * Ignore unquantifiable values as well as SCHED_BATCH tasks.
+	 */ 
+	if (now < p->timestamp || batch_task(p))
 		sleep_time = 0;
 
 	if (likely(sleep_time > 0)) {
@@ -3051,9 +3056,9 @@ static inline int expired_starving(struc
 {
 	if (rq->curr->static_prio > rq->best_expired_prio)
 		return 1;
-	if (!STARVATION_LIMIT || !rq->expired_timestamp)
+	if (!STARVATION_LIMIT)
 		return 0;
-	if (jiffies - rq->expired_timestamp > STARVATION_LIMIT * rq->nr_running)
+	if (jiffies - rq->switch_timestamp > STARVATION_LIMIT * rq->nr_running)
 		return 1;
 	return 0;
 }
@@ -3131,6 +3136,67 @@ void account_steal_time(struct task_stru
 		cpustat->steal = cputime64_add(cpustat->steal, tmp);
 }
 
+/*
+ * Promote and requeue the next lower priority task.  If no task
+ * is available in the active array, switch to the expired array.
+ * @rq: runqueue to search.
+ * @prio: priority at which to begin search.
+ */
+static inline void promote_next_lower(struct rq *rq, int prio)
+{
+	struct prio_array *array = rq->active;
+	struct task_struct *p = NULL;
+	unsigned long long now = rq->most_recent_timestamp;
+	unsigned long *bitmap;
+	unsigned long starving = JIFFIES_TO_NS(rq->nr_running * DEF_TIMESLICE);
+	int idx = prio + 1, found_noninteractive = 0;
+
+repeat:
+	bitmap = array->bitmap;
+	idx = find_next_bit(bitmap, MAX_PRIO, idx);
+	if (idx < MAX_PRIO) {
+		struct list_head *queue = array->queue + idx;
+
+		p = list_entry(queue->next, struct task_struct, run_list);
+		if (!TASK_INTERACTIVE(p))
+			found_noninteractive = 1;
+
+		/* Skip non-starved queues. */
+		if (now < p->last_ran + starving) {
+			idx++;
+			p = NULL;
+			goto repeat;
+		}
+	} else if (!found_noninteractive && array == rq->active) {
+		/* Nobody home, check the expired array. */
+		array = rq->expired;
+		idx = 0;
+		p = NULL;
+		goto repeat;
+	}
+
+	/* Found one, requeue it. */
+	if (p) {
+		dequeue_task(p, p->array);
+		if (array == rq->active)
+			p->prio--;
+		/*
+		 * If we pulled a task from the expired array, correct
+		 * expired array info.  We can't afford a full search
+		 * for best_expired_prio, but do the best we can.
+		 */
+		else {
+			idx = sched_find_first_bit(array->bitmap);
+			if (idx < MAX_PRIO) {
+				if (rq->best_expired_prio > idx)
+					rq->best_expired_prio = idx;
+			} else
+				rq->best_expired_prio = MAX_PRIO;
+		}
+		enqueue_task(p, rq->active);
+	}
+}
+
 static void task_running_tick(struct rq *rq, struct task_struct *p)
 {
 	if (p->array != rq->active) {
@@ -3162,20 +3228,30 @@ static void task_running_tick(struct rq 
 		goto out_unlock;
 	}
 	if (!--p->time_slice) {
+		int task_was_interactive = TASK_INTERACTIVE(p);
 		dequeue_task(p, rq->active);
 		set_tsk_need_resched(p);
 		p->prio = effective_prio(p);
 		p->time_slice = task_timeslice(p);
 		p->first_time_slice = 0;
 
-		if (!rq->expired_timestamp)
-			rq->expired_timestamp = jiffies;
 		if (!TASK_INTERACTIVE(p) || expired_starving(rq)) {
 			enqueue_task(p, rq->expired);
 			if (p->static_prio < rq->best_expired_prio)
 				rq->best_expired_prio = p->static_prio;
-		} else
+			if (!task_was_interactive)
+				rq->expired_timestamp = jiffies;
+		} else {
+			int limit = STARVATION_LIMIT;
 			enqueue_task(p, rq->active);
+
+			/*
+			 * Start promoting lower priority tasks if we haven't
+			 * expired a task within STARVATION_LIMIT tics.
+			 */
+			if (time_after(jiffies, rq->expired_timestamp + limit))
+				promote_next_lower(rq, p->prio);
+		}
 	} else {
 		/*
 		 * Prevent a too long timeslice allowing a task to monopolize
@@ -3356,7 +3432,7 @@ need_resched_nonpreemptible:
 		idle_balance(cpu, rq);
 		if (!rq->nr_running) {
 			next = rq->idle;
-			rq->expired_timestamp = 0;
+			rq->switch_timestamp = jiffies;
 			goto switch_tasks;
 		}
 	}
@@ -3370,7 +3446,7 @@ need_resched_nonpreemptible:
 		rq->active = rq->expired;
 		rq->expired = array;
 		array = rq->active;
-		rq->expired_timestamp = 0;
+		rq->switch_timestamp = jiffies;
 		rq->best_expired_prio = MAX_PRIO;
 	}
 

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Xenofon Antidides]

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


--- Mike Galbraith <efault@gmx.de> wrote:

> On Fri, 2007-03-30 at 15:05 +0000, Xenofon Antidides
> wrote:
> > ----- Original Message ----
> > From: Ingo Molnar <mingo@elte.hu>
> > To: Con Kolivas <kernel@kolivas.org>
> > Cc: linux list <linux-kernel@vger.kernel.org>;
> Andrew Morton <akpm@linux-foundation.org>; Mike
> Galbraith <efault@gmx.de>
> > Sent: Thursday, March 29, 2007 9:22:49 PM
> > Subject: [test] hackbench.c interactivity results:
> vanilla versus SD/RSDL
> > 
> > 
> > * Ingo Molnar <mingo@elte.hu> wrote:
> > 
> > > * Con Kolivas <kernel@kolivas.org> wrote:
> > > 
> > > > I'm cautiously optimistic that we're at the
> thin edge of the bugfix 
> > > > wedge now.
> > [...]
> > 
> > > and the numbers he posted:
> > > 
> > > 
>
http://marc.info/?l=linux-kernel&m=117448900626028&w=2
> > 
> > We been staring at these numbers for while now and
> we come to the conclusion they wrong.
> > 
> > The test is f is 3 tasks, two on different and one
> on same cpu as sh here:
> > virgin 2.6.21-rc3-rsdl-smp
> > top - 13:52:50 up 7 min, 12 users,  load average:
> 3.45, 2.89, 1.51
> > 
> >   PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM
>    TIME+  P COMMAND
> >  6560 root      31   0  2892 1236 1032 R   82  0.1
>   1:50.24 1 sh
> >  6558 root      28   0  1428  276  228 S   42  0.0
>   1:00.09 1 f
> >  6557 root      30   0  1424  280  228 R   35  0.0
>   1:00.25 0 f
> >  6559 root      39   0  1424  276  228 R   33  0.0
>   0:58.36 0 f
> 
> This is a 1 second sample, tasks migrate.
> 
> 	-Mike

Something different on many cpus? Sorry I was thinking
something other. I try 50% run + 50% sleep on one cpu
and mainline has big problem. Sorry for bad code I
copy bits to make it work. Start program first then
run bash 100% cpu (while : ; do : ; done). Try change
program forks from 1 till 3 or more mainline kernel
and bash gets 0%.



Xant


 
____________________________________________________________________________________
Get your own web address.  
Have a HUGE year through Yahoo! Small Business.
http://smallbusiness.yahoo.com/domains/?p=BESTDEAL

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 1949799762-fiftyp.c --]
[-- Type: text/x-csrc; name="fiftyp.c", Size: 2772 bytes --]

// gcc -O2 -o fiftyp fiftyp.c -lrt
// code from interbench.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
int forks=1;
int runus,sleepus=7000;
unsigned long loops_per_ms;
void terminal_error(const char *name)
{
	fprintf(stderr, "\n");
	perror(name);
	exit (1);
}

unsigned long long get_nsecs(struct timespec *myts)
{
	if (clock_gettime(CLOCK_REALTIME, myts))
		terminal_error("clock_gettime");
	return (myts->tv_sec * 1000000000 + myts->tv_nsec );
}

void burn_loops(unsigned long loops)
{
	unsigned long i;

	/*
	 * We need some magic here to prevent the compiler from optimising
	 * this loop away. Otherwise trying to emulate a fixed cpu load
	 * with this loop will not work.
	 */
	for (i = 0 ; i < loops ; i++)
	     asm volatile("" : : : "memory");
}

/* Use this many usecs of cpu time */
void burn_usecs(unsigned long usecs)
{
	unsigned long ms_loops;

	ms_loops = loops_per_ms / 1000 * usecs;
	burn_loops(ms_loops);
}

void microsleep(unsigned long long usecs)
{
	struct timespec req, rem;

	rem.tv_sec = rem.tv_nsec = 0;

	req.tv_sec = usecs / 1000000;
	req.tv_nsec = (usecs - (req.tv_sec * 1000000)) * 1000;
continue_sleep:
	if ((nanosleep(&req, &rem)) == -1) {
		if (errno == EINTR) {
			if (rem.tv_sec || rem.tv_nsec) {
				req.tv_sec = rem.tv_sec;
				req.tv_nsec = rem.tv_nsec;
				goto continue_sleep;
			}
			goto out;
		}
		terminal_error("nanosleep");
	}
out:
	return;
}

/*
 * In an unoptimised loop we try to benchmark how many meaningless loops
 * per second we can perform on this hardware to fairly accurately
 * reproduce certain percentage cpu usage
 */
void calibrate_loop(void)
{
	unsigned long long start_time, loops_per_msec, run_time = 0;
	unsigned long loops;
	struct timespec myts;

	loops_per_msec = 1000000;
redo:
	/* Calibrate to within 1% accuracy */
	while (run_time > 1010000 || run_time < 990000) {
		loops = loops_per_msec;
		start_time = get_nsecs(&myts);
		burn_loops(loops);
		run_time = get_nsecs(&myts) - start_time;
		loops_per_msec = (1000000 * loops_per_msec / run_time ? :
			loops_per_msec);
	}

	/* Rechecking after a pause increases reproducibility */
	sleep(1);
	loops = loops_per_msec;
	start_time = get_nsecs(&myts);
	burn_loops(loops);
	run_time = get_nsecs(&myts) - start_time;

	/* Tolerate 5% difference on checking */
	if (run_time > 1050000 || run_time < 950000)
		goto redo;
 loops_per_ms=loops_per_msec;
 sleep(1);
 start_time=get_nsecs(&myts);
 microsleep(sleepus);
 run_time=get_nsecs(&myts)-start_time;
 runus=run_time/1000;
}

int main(void){
 int i;
 calibrate_loop();
 printf("starting %d forks\n",forks);
 for(i=1;i<forks;i++){
  if(!fork())
   break;
 }
 while(1){
  burn_usecs(runus);
  microsleep(sleepus);
 }
 return 0;
}

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Mike Galbraith]

On Fri, 2007-03-30 at 15:05 +0000, Xenofon Antidides wrote:
> ----- Original Message ----
> From: Ingo Molnar <mingo@elte.hu>
> To: Con Kolivas <kernel@kolivas.org>
> Cc: linux list <linux-kernel@vger.kernel.org>; Andrew Morton <akpm@linux-foundation.org>; Mike Galbraith <efault@gmx.de>
> Sent: Thursday, March 29, 2007 9:22:49 PM
> Subject: [test] hackbench.c interactivity results: vanilla versus SD/RSDL
> 
> 
> * Ingo Molnar <mingo@elte.hu> wrote:
> 
> > * Con Kolivas <kernel@kolivas.org> wrote:
> > 
> > > I'm cautiously optimistic that we're at the thin edge of the bugfix 
> > > wedge now.
> [...]
> 
> > and the numbers he posted:
> > 
> >  http://marc.info/?l=linux-kernel&m=117448900626028&w=2
> 
> We been staring at these numbers for while now and we come to the conclusion they wrong.
> 
> The test is f is 3 tasks, two on different and one on same cpu as sh here:
> virgin 2.6.21-rc3-rsdl-smp
> top - 13:52:50 up 7 min, 12 users,  load average: 3.45, 2.89, 1.51
> 
>   PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  P COMMAND
>  6560 root      31   0  2892 1236 1032 R   82  0.1   1:50.24 1 sh
>  6558 root      28   0  1428  276  228 S   42  0.0   1:00.09 1 f
>  6557 root      30   0  1424  280  228 R   35  0.0   1:00.25 0 f
>  6559 root      39   0  1424  276  228 R   33  0.0   0:58.36 0 f

This is a 1 second sample, tasks migrate.

	-Mike

Re: [test] hackbench.c interactivity results: vanilla versus SD/RSDL

[Xenofon Antidides]

----- Original Message ----
From: Ingo Molnar <mingo@elte.hu>
To: Con Kolivas <kernel@kolivas.org>
Cc: linux list <linux-kernel@vger.kernel.org>; Andrew Morton <akpm@linux-foundation.org>; Mike Galbraith <efault@gmx.de>
Sent: Thursday, March 29, 2007 9:22:49 PM
Subject: [test] hackbench.c interactivity results: vanilla versus SD/RSDL


* Ingo Molnar <mingo@elte.hu> wrote:

> * Con Kolivas <kernel@kolivas.org> wrote:
> 
> > I'm cautiously optimistic that we're at the thin edge of the bugfix 
> > wedge now.
[...]

> and the numbers he posted:
> 
>  http://marc.info/?l=linux-kernel&m=117448900626028&w=2

We been staring at these numbers for while now and we come to the conclusion they wrong.

The test is f is 3 tasks, two on different and one on same cpu as sh here:
virgin 2.6.21-rc3-rsdl-smp
top - 13:52:50 up 7 min, 12 users,  load average: 3.45, 2.89, 1.51

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  P COMMAND
 6560 root      31   0  2892 1236 1032 R   82  0.1   1:50.24 1 sh
 6558 root      28   0  1428  276  228 S   42  0.0   1:00.09 1 f
 6557 root      30   0  1424  280  228 R   35  0.0   1:00.25 0 f
 6559 root      39   0  1424  276  228 R   33  0.0   0:58.36 0 f

6560 sh is asking for 100% cpu on cpu number 1
6558 f is asking for 50% cpu on cpu number 1
6557 f is asking for 50% cpu on cpu number 0
6559 f is asking for 50% cpu on cpu number 0

So if 6560 and 6558 are asking for cpu from cpu number 1:
6560 wants 100% and 6558 wants 50%.
6560 should get 2/3 cpu 6558 should get 1/3 cpu

2.6.21-rc3-rsdl-smp gives 65% sh and 35% f

patched 2.6.21-rc3-rsdl-smp gives 60% sh and 40% f

2.6.20.3-smp gives 51% sh and 49% f

We think cpu correctness is 2.6.21-rc3-rsdl-smp
 in that test.

Xant





 
____________________________________________________________________________________
Food fight? Enjoy some healthy debate 
in the Yahoo! Answers Food & Drink Q&A.
http://answers.yahoo.com/dir/?link=list&sid=396545367