Peter Williams wrote:
Ingo Molnar wrote:
* Peter Williams <[email protected]> wrote:
- bugfix: use constant offset factor for nice levels instead of
sched_granularity_ns. Thus nice levels work even if someone sets
sched_granularity_ns to 0. NOTE: nice support is still naive, i'll
address the many nice level related suggestions in -v4.
I have a suggestion I'd like to make that addresses both nice and
fairness at the same time. As I understand the basic principle
behind this scheduler it to work out a time by which a task should
make it onto the CPU and then place it into an ordered list (based on
this value) of tasks waiting for the CPU. I think that this is a
great idea [...]
yes, that's exactly the main idea behind CFS, and thanks for the
compliment :)
Under this concept the scheduler never really has to guess: every
scheduler decision derives straight from the relatively simple
one-sentence (!) scheduling concept outlined above. Everything that
tasks 'get' is something they 'earned' before and all the scheduler
does are micro-decisions based on math with the nanosec-granularity
values. Both the rbtree and nanosec accounting are a straight
consequence of this too: they are the tools that allow the
implementation of this concept in the highest-quality way. It's
certainly a very exciting experiment to me and the feedback 'from the
field' is very promising so far.
[...] and my suggestion is with regard to a method for working out
this time that takes into account both fairness and nice.
First suppose we have the following metrics available in addition to
what's already provided.
rq->avg_weight_load /* a running average of the weighted load on the
CPU */ p->avg_cpu_per_cycle /* the average time in nsecs that p
spends on the CPU each scheduling cycle */
yes. rq->nr_running is really just a first-level approximation of
rq->raw_weighted_load. I concentrated on the 'nice 0' case initially.
I appreciate that the notion of basing the expected wait on the
task's average cpu use per scheduling cycle is counter intuitive but
I believe that (if you think about it) you'll see that it actually
makes sense.
hm. So far i tried to not do any statistical approach anywhere: the
p->wait_runtime metric (which drives the task ordering) is in essence
an absolutely precise 'integral' of the 'expected runtimes' that the
task observes and hence is a precise "load-average as observed by the
task"
To me this is statistics :-)
in itself. Every time we base some metric on an average value we
introduce noise into the system.
i definitely agree with your suggestion that CFS should use a
nice-scaled metric for 'load' instead of the current rq->nr_running,
but regarding the basic calculations i'd rather lean towards using
rq->raw_weighted_load. Hm?
This can result in jerkiness (in my experience) but using the smoothed
version is certainly something that can be tried later rather than
sooner. Perhaps just something to bear in mind as a solution to
"jerkiness" if it manifests.
your suggestion concentrates on the following scenario: if a task
happens to schedule in an 'unlucky' way and happens to hit a busy
period while there are many idle periods. Unless i misunderstood your
suggestion, that is the main intention behind it, correct?
You misunderstand (that's one of my other schedulers :-)). This one's
based on the premise that if everything happens as the task expects it
will get the amount of CPU bandwidth (over this short period) that it's
entitled to. In reality, sometimes it will get more and sometimes less
but on average it should get what it deserves. E.g. If you had two tasks
with equal nice and both had demands of 90% of a CPU you'd expect them
each to get about half of the CPU bandwidth. Now suppose that one of
them uses 5ms of CPU each time it got onto the CPU and the other uses
10ms. If these two tasks just round robin with each other the likely
outcome is that the one with the 10ms bursts will get twice as much CPU
as the other but my proposed method should prevent and cause them to get
roughly the same amount of CPU. (I believe this was a scenario that
caused problems with O(1) and required a fix at some stage?)
BTW this has the advantage that the decay rate used in calculating the
task's statistics can be used to control how quickly the scheduler
reacts to changes in the task's behaviour.
I think that, with this model, if the current task hasn't surrendered
the CPU when the next task on the queue's "on CPU" time arrives that the
current task should be pre-empted in favour of that task. I'm not sure
what would be the best way to implement this.
Peter
--
Peter Williams [email protected]
"Learning, n. The kind of ignorance distinguishing the studious."
-- Ambrose Bierce
-
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/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
