From: Roman Zippel <zippel@linux-m68k.org>
To: Ingo Molnar <mingo@elte.hu>
Cc: linux-kernel@vger.kernel.org, peterz@infradead.org,
Mike Galbraith <efault@gmx.de>
Subject: Re: [ANNOUNCE/RFC] Really Simple Really Fair Scheduler
Date: Tue, 4 Sep 2007 13:21:40 +0200 (CEST) [thread overview]
Message-ID: <Pine.LNX.4.64.0709041244080.1817@scrub.home> (raw)
In-Reply-To: <20070904062957.GA25634@elte.hu>
Hi,
On Tue, 4 Sep 2007, Ingo Molnar wrote:
> and what about the mirror image problem?
Sorry, I'm not familiar with that in a scheduler context.
> Your math assumes that tasks
> use up their full timeslices, somewhere starting at (12):
>
> | (12) time_norm_app = sum_{t}^{T}(time_norm_{t} * weight_{t}) /
> | sum_{t}^{T}(weight_{t})
> |
> | This produces only a approximate normalized time, but if all
> | time_norm_{t} are equal (i.e. all tasks got their share), the result
> | is the same, thus the error is only temporary.
>
> >From here on the reasoning and the math is flawed i believe: it assumes
> that tasks use up their timeslices - which is rarely the case.
I'm not sure what you're refering to. The remaining math basically only
deals with the average calculation and if we're still at your simplified
model, then it's largely irrevelant, because the approximation error only
comes into effect with different weights. This means for the common case,
you can assume my code produces a perfect average.
> In practical terms: your code causes unfairness to tasks that sleep when
> they have used up only a fraction of their slice, when they are in a
> fairness-deficit. For example consider a task that just waited alot to
> get on the CPU, and when it finally got there (gathering a fairness
> deficit of say 9 milliseconds), a hundred microseconds later it sleeps.
>
> The problem is that when it wakes up and gets back on the runqueue your
> code "forgets" that the task is in "need of fairness" by 9 milliseconds:
> the task continues as if its previous starvation didnt happen at all.
Please put this into more context, e.g. demonstrate how this problem
doesn't exist in CFS. My code should largely mirror CFS behaviour with the
exception that the bonus maybe isn't as big and this:
if (sysctl_sched_features & SCHED_FEAT_SLEEPER_AVG)
delta_fair = div64_likely32((u64)delta_fair * load,
load + se->load.weight);
> This effect can cause _far more noise_ and even systematic starvation
> than any numeric rounding effects could cause. (This could perhaps
> explain the unfairness Mike reported, and this could perhaps explain the
> noisy hackbench results i'm seeing with your patch - although i'm not
> certain about this, i havent looked into those usecases in detail.)
The problem Mike reported looks more like a bug, I'm puzzled why the
verify code didn't trigger as the whole thing was pretty much out of sync,
so in the next version I'll add a few more checks, but I'm not finished
with the hackbench results yet.
> CFS's current math addresses this problem via the use of the fair-clock
> metric and via ->wait_runtime: that gives us a good idea what happened
> to the system while the task slept. With your model, that information is
> not maintained at all, and is not regainable. At the moment i dont see
> how we could achieve good sleeper behavior with your model, you've
> over-simplified the scheduler metrics and we've lost essential
> information.
Please describe this sleeper behaviour, what kind of sleeper do you have
in mind exactly? If we take for example interactive tasks, these should be
constantly behind other running tasks and thus have an advantage at
getting the cpu, i.e. if a task doesn't use up its time slice its runtime
value won't advance as much as of other tasks which do use their slice.
bye, Roman
prev parent reply other threads:[~2007-09-04 11:21 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-09-02 12:01 Ingo Molnar
2007-09-02 19:12 ` Tong Li
2007-09-02 19:44 ` Ingo Molnar
2007-09-03 18:38 ` Roman Zippel
2007-09-03 18:54 ` Ingo Molnar
2007-09-03 19:13 ` Roman Zippel
2007-09-03 19:20 ` Ingo Molnar
2007-09-03 19:55 ` Roman Zippel
2007-09-03 20:04 ` Ingo Molnar
2007-09-04 2:50 ` Roman Zippel
2007-09-04 6:29 ` Ingo Molnar
2007-09-04 11:21 ` Roman Zippel [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Pine.LNX.4.64.0709041244080.1817@scrub.home \
--to=zippel@linux-m68k.org \
--cc=efault@gmx.de \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@elte.hu \
--cc=peterz@infradead.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®