CFS fix place entity spread issue (v2)

CFS fix place entity spread issue (v2)

Huge CFS vruntime spread (18 minutes) has been observed with LTTng while simply running Xorg on a uniprocessor machine. Detailed explanation in my ELC2010 presentation at:

http://www.efficios.com/elc2010

(includes slides, ad-hoc CFS instrumentation patches and wakeup latency test program)

Changelog since v1:

* Keep max(se->vruntime, vruntime). It's needed to ensure that tasks already within the spread window do not get an extra unfair vruntime boost just because they slept.

I've torn the CFS scheduler apart in the past days to figure out what is causing this weird behavior, and the culprit seems to be place_entity(). The problem appears to be the cumulative effect of letting the min_vruntime go backward when putting sleepers back on the runqueue. It lets the vruntime spread grow to "entertaining" values (it is supposed to be in the 5ms range, not 18 minutes!).

In the original code, a max between the sched entity vruntime and the calculated vruntime was supposed to "ensure that the thread time never go backward". But I don't see why we even care about that. The key point is that the min_vruntime of the runqueue should not go backward.

I propose to fix this by calculating the relative offset from min_vruntime + sysctl_sched_latency rather than directly from min_vruntime. I also ensure that the value never goes below min_vruntime.

Under the Xorg workload, moving a few windows around and starting firefox while executing the wakeup-latency.c program (program waking up every 10ms and reporting wakeup latency), this patch brings worse latency from 60ms down to 12ms. Even doing a kernel compilation at the same time, the worse latency stays around 20ms now.

I'm submitting this patch ASAP, since it seems to fix CFS issues that many people have been complaining about. I'm sending it as RFC because testing its effect on more workloads would be welcome.

I can see that place_entity() has stayed more or less the same since 2.6.24 (and maybe even before, as code has just been reorganised between 2.6.23 and 2.6.24), so we can expect this to be a problem people have been experiencing for a while.

---
 kernel/sched_fair.c |   11 +++++++++++
 1 file changed, 11 insertions(+)

Index: linux-2.6-lttng.git/kernel/sched_fair.c
===================================================================
@@ -738,6 +738,14 @@
 		unsigned long thresh = sysctl_sched_latency;
 
 		/*
+		 * Place the woken up task relative to
+		 * min_vruntime + sysctl_sched_latency.
+		 * We must _never_ decrement min_vruntime, because the effect is
+		 * that spread increases progressively under the Xorg workload.
+		 */
+		vruntime += sysctl_sched_latency;
+
+		/*
 		 * Convert the sleeper threshold into virtual time.
 		 * SCHED_IDLE is a special sub-class.  We care about
 		 * fairness only relative to other SCHED_IDLE tasks,

@@ -755,6 +763,9 @@
 			thresh >>= 1;
 
 		vruntime -= thresh;
+
+		/* ensure min_vruntime never go backwards. */
+		vruntime = max_t(u64, vruntime, cfs_rq->min_vruntime);
 	}
 
 	/* ensure we never gain time by being placed backwards. */

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Hmm. I tested this patch with my favourite non-scientific desktop load
test: do web browsing while doing a kernel compile with "make -j16" (after doing a "git clean -dqfx" and "ccache -C" to get rid of old object files and ccache).

This is on a dual-core (with SMT, so 4 threads) Core i5, so "make -j16" overcommits the CPU's quite a bit.

And quite frankly, I think your patch makes things much worse. I don't have numbers, but it felt much choppier and slower to do scrolling in firefox o moving windows around while the load average is 20+.

My testload is in no way objective, nor necessarily any good, but it's the one I happen to use, and while it's subjective, I think the difference was pretty clear and not good.

Linus

Degradation of this particular workload is expected, because the nature of the large CFS spread issue favors Xorg: it gets litterally minutes of available vruntime, while most other threads (e.g. kernel build, audio playing, etc..) suffer from this.

I'll try to play a bit with this (I got plenty of time to kill at the airport today, missed my connecting flight back from San Francisco). Ideally, we might want to try to find a way to ensure that place_entity() is kind to sleepers, but without putting them before min_vruntime. I don't have any SMP machine with Xorg handy, but I'll try to push my UP laptop a bit more heavily with a kernel build.

If we are lucky enough, we might just have to twist a knob or two to make Xorg more responsive.

Thanks,

Mathieu

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

In that case, I think your patch is fundamentally incorrect.

I care a _whole_ lot more about "usable desktop" than I care about some inane "available vruntime". If the current behavior breaks your vruntime rules, then the current behaviour is clearly _correct_.

Linus

So what happened to comprehensive changelogs?

Right, that should not happen, ever, min_vruntime should be monotonic. Your explanation fails to mention how exactly this happens.

Fairness, a task's vruntime going backwards means it can obtain more cputime than a while(1) loop would get, not a good thing.

That is certainly important too.

I'm not sure that's a good idea, that'll end up being a 'fairer' scheduler in the strict sense, but I suspect it will break the wakeup preemption model we have.

That seems nice enough. But really, this changelog doesn't explain the cause at all.

/me goes try and figure out where this min_vruntime goes backwards.

So update_min_vruntime() is the sole place where we change min_vruntime, it is called from update_curr() where we add runtime to the task we're currently servicing, and dequeue_entity() where we remove someone from the tree.

These two sites are the only places where min_vruntime can change because only adding service to the leftmost task, or removal thereof can make the min_vruntime go forward.

So update_min_vruntime():

- takes the smaller vruntime between the current task and the leftmost
tree entry (current is not in the tree, and we can pass beyond the leftmost waiting task due to limited preemption and minimum service windows).

- set min_vruntime to the larger between the existing min_vruntime and
the smallest vruntime.

So colour me confused if I'm not seeing min_vruntime going backwards...

place_entity(), when placing a sleeper on the runqueue, decrements its vruntime (derived from min_vruntime) from -= thresh (derived from load calculation). So if we end up with a task woken up that does not consume enough vruntime to pass the previous min_vruntime value, we effectively decrement min_vruntime.

The other thing I am currently looking into is that, without even considering the question of going lower than min_vruntime, given that a woken up sleeper gets an extra share of vruntime (still because of place_entity), it might always run between -thresh to the previous min_runtime, therefore "stalling" the min_vruntime values at low values while other threads push the maximum vruntime higher, therefore increasing the spread. I'm currently doing some tests trying to cope with this by consuming woken up sleepers vruntime more quickly for a vruntime duration of "thresh".

I am also testing alternatives ways to deal with the min_vruntime going backward problem, by keeping a "floor_vruntime", which ensures that place_entity() can never decrement min_vruntime below the floor value of its previous decrement.

Sorry for the missing changelog info, I was between planes this weekend. Hopefully my sleep-deprived explanation makes sense. ;)

Thanks,

Mathieu

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

On Sun, 2010-04-18 at 09:13 -0400, Mathieu Desnoyers wrote:

OK, so looking purely at the patch:

No we don't, the next time it comes along it will at worst use the exact same min_vruntime, but not a lower one.

But these things will break the wakeup-preemption, you cannot change place_entity() without also considering check_preempt_wakeup()->wakeup_preempt_entity().

It doesn't go backwards!! Show me where min_vruntime actually decreases? Sure can have entities that are left of min_vruntime, but that doesn't mean min_vruntime decreases!

None-what-so-ever ;-)

Now, theory says we should use the 0-lag point for task insertion, and I have a patch that tracks that point, but it adds extra multiplications to all the fast-paths, and I never really managed to make 0-lag insertion work well with wakeup-preemption.

I've never really liked sleeper-fairness stuff from a theoretical pov. but it does provide the 'interactive' stuff lots of things like (otoh it also does cause some over-scheduling for some loads, and as you've seen it rips the spread apart).

I also tried an avg_runtime based wakeup-preemption, where a task that on average runs shorter than the currently running task will preempt (within the wakeup_gran limits), but that also didn't work out -- although it did work for that one latency-tester app from Jens (IIRC) that started that).

---
Subject: sched: avg_vruntime
From: Peter Zijlstra <[email protected]>
Date: Fri, 24 Oct 2008 11:06:17 +0200

Renicing requires scaling the lag. Therefore we need a way to compute the it. Lag is defined as the difference between the service time received from the ideal model and the actual scheduler.

The defining property of a fair scheduler is that the sum of all lags is zero; which can be seen is trivially true for the ideal case, as all lags are zero.

Therefore, the average of all virtual runtimes will be the point of zero lag.

We cannot prove fairness for CFS due to sleeper fairness (without it we can). However since we can observe it does converge to fairness in stable operation, we can say the zero lag point converges to the average.

We can't just take the average of vruntime - as it will use the full range of its u64 and will wrap around. Instead we'll use the average of (vruntime - min_vruntime)

\Sum_{i}^{n} 1/n (v_{i} - v) = 1/n (\Sum_{i}^{n} v_{i}) - vn

By factoring out the 1/n (never storing that) we avoid rounding, which would bring an accumulating error.

LKML-Reference: <[email protected]>

---
 kernel/sched.c       |    4 +++
 kernel/sched_debug.c |    3 ++
 kernel/sched_fair.c  |   60 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 66 insertions(+), 1 deletion(-)

Index: linux-2.6/kernel/sched.c
===================================================================
@@ -349,6 +349,10 @@ struct cfs_rq {
 	struct load_weight load;
 	unsigned long nr_running;
 
+	long nr_queued;
+	long avg_load;
+	s64 avg_vruntime;
+
 	u64 exec_clock;
 	u64 min_vruntime;
 

Index: linux-2.6/kernel/sched_debug.c
===================================================================
@@ -202,6 +202,9 @@ void print_cfs_rq(struct seq_file *m, in
 			SPLIT_NS(spread0));
 	SEQ_printf(m, "  .%-30s: %ld\n", "nr_running", cfs_rq->nr_running);
 	SEQ_printf(m, "  .%-30s: %ld\n", "load", cfs_rq->load.weight);
+	SEQ_printf(m, "  .%-30s: %Ld.%06ld\n", "avg_vruntime",
+			SPLIT_NS(avg_vruntime(cfs_rq)));
+
 
 	SEQ_printf(m, "  .%-30s: %d\n", "nr_spread_over",
 			cfs_rq->nr_spread_over);