On Fri, 27 Jul 2007, Chris Snook wrote:
I don't think that achieving a constant error bound is always a good thing.
We all know that fairness has overhead. If I have 3 threads and 2
processors, and I have a choice between fairly giving each thread 1.0 billion
cycles during the next second, or unfairly giving two of them 1.1 billion
cycles and giving the other 0.9 billion cycles, then we can have a useful
discussion about where we want to draw the line on the fairness/performance
tradeoff. On the other hand, if we can give two of them 1.1 billion cycles
and still give the other one 1.0 billion cycles, it's madness to waste those
0.2 billion cycles just to avoid user jealousy. The more complex the memory
topology of a system, the more "free" cycles you'll get by tolerating
short-term unfairness. As a crude heuristic, scaling some fairly low
tolerance by log2(NCPUS) seems appropriate, but eventually we should take the
boot-time computed migration costs into consideration.
I think we are in agreement. To avoid confusion, I think we should be more
precise on what fairness means. Lag (i.e., ideal fair time - actual
service time) is the commonly used metric for fairness. The definition is
that a scheduler is proportionally fair if for any task in any time
interval, the task's lag is bounded by a constant (note it's in terms of
absolute time). The knob here is this constant and can help trade off
performance and fairness. The reason for a constant bound is that we want
consistent fairness properties regardless of the number of tasks. For
example, we don't want the system to be much less fair as the number of
tasks increases. With DWRR, the lag bound is the max weight of currently
running tasks, multiplied by sysctl_base_round_slice. So if all tasks are
of nice 0, i.e., weight 1, and sysctl_base_round_slice equals 30 ms, then
we are guaranteed each task is at most 30ms off of the ideal case. This is
a useful property. Just like what you mentioned about the migration cost,
this property allows the scheduler or user to accurately reason about the
tradeoffs. If we want to trade fairness for performance, we can increase
sysctl_base_round_slice to, say, 100ms; doing so we also know accurately
the worst impact it has on fairness.
Adding system calls, while great for research, is not something which is done
lightly in the published kernel. If we're going to implement a user
interface beyond simply interpreting existing priorities more precisely, it
would be nice if this was part of a framework with a broader vision, such as
a scheduler economy.
Agreed. I've seen papers on scheduler economy but not familiar enough to
comment on it.
Scheduling Algorithm:
The scheduler keeps a set data structures, called Trio groups, to maintain
the weight or reservation of each thread group (including one or more
threads) and the local weight of each member thread. When scheduling a
thread, it consults these data structures and computes (in constant time) a
system-wide weight for the thread that represents an equivalent CPU share.
Consequently, the scheduling algorithm, DWRR, operates solely based on the
system-wide weight (or weight for short, hereafter) of each thread. Having
a flat space of system-wide weights for individual threads avoids
performing seperate scheduling at each level of the group hierarchy and
thus greatly simplies the implementation for group scheduling.
Implementing a flat weight space efficiently is nontrivial. I'm curious to
see how you reworked the original patch without global locking.
I simply removed the locking and changed a little bit in idle_balance().
The lock was trying to avoid a thread from reading or writing the global
highest round value while another thread is writing to it. For writes,
it's simple to ensure without locking only one write takes effect when
multiple writes are concurrent. For the case that there's one write going
on and multiple threads read, without locking, the only problem is that a
reader may read a stale value and thus thinks the current highest round is
X while it's actually X + 1. The end effect is that a thread can be at
most two rounds behind the highest round. This changes DWRR's lag bound to
2 * (max weight of current tasks) * sysctl_base_round_slice, which is
still constant.
I had a feeling this patch was originally designed for the O(1) scheduler,
and this is why. The old scheduler had expired arrays, so adding a
round-expired array wasn't a radical departure from the design. CFS does not
have an expired rbtree, so adding one *is* a radical departure from the
design. I think we can implement DWRR or something very similar without
using this implementation method. Since we've already got a tree of queued
tasks, it might be easiest to basically break off one subtree (usually just
one task, but not necessarily) and migrate it to a less loaded tree whenever
we can reduce the difference between the load on the two trees by at least
half. This would prevent both overcorrection and undercorrection.
Yes, the description was based on O(1) and the intent was exactly not to
be much a departure from its design. I totally agree the same philosophy
should apply to an implementation based on CFS.
The idea of rounds was another implementation detail that bothered me. In
the old scheduler, quantizing CPU time was a necessary evil. Now that we can
account for CPU time with nanosecond resolution, doing things on an as-needed
basis seems more appropriate, and should reduce the need for global
synchronization.
Without the global locking, the global synchronization here is simply
ping-ponging a cache line once of while. This doesn't look expensive to
me, but if it does after benchmarking, adjusting sysctl_base_round_slice
can reduce the ping-pong frequency. There might also be a smart
implementation that can alleviate this problem.
I don't understand why quantizing CPU time is a bad thing. Could you
educate me on this?
I guess it's worth mentioning that although we now have nanosecond-level
accounting, scheduling in the common case still occurs at timer tick
granularity.
In summary, I think the accounting is sound, but the enforcement is
sub-optimal for the new scheduler. A revision of the algorithm more
cognizant of the capabilities and design of the current scheduler would seem
to be in order.
I've referenced many times my desire to account for CPU/memory hierarchy in
these patches. At present, I'm not sure we have sufficient infrastructure in
the kernel to automatically optimize for system topology, but I think
whatever design we pursue should have some concept of this hierarchy, even if
we end up using a depth-1 tree in the short term while we figure out how to
optimize this.
Agreed.
tong
-
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]
