William Lee Irwin III wrote:
William Lee Irwin III wrote:
Lag should be considered in lieu of load because lag
On Sun, May 27, 2007 at 11:29:51AM +1000, Peter Williams wrote:
What's the definition of lag here?
Lag is the deviation of a task's allocated CPU time from the CPU time
it would be granted by the ideal fair scheduling algorithm (generalized
processor sharing; take the limit of RR with per-task timeslices
proportional to load weight as the scale factor approaches zero).
Over what time period does this operate?
Negative lag reflects receipt of excess CPU time. A close-to-canonical
"fairness metric" is the maximum of the absolute values of the lags of
all the tasks on the system. The "signed minimax pseudonorm" is the
largest lag without taking absolute values; it's a term I devised ad
hoc to describe the proposed algorithm.
So what you're saying is that you think dynamic priority (or its
equivalent) should be used for load balancing instead of static priority?
William Lee Irwin III wrote:
is what the
scheduler is trying to minimize;
On Sun, May 27, 2007 at 11:29:51AM +1000, Peter Williams wrote:
This isn't always the case. Some may prefer fairness to minimal lag.
Others may prefer particular tasks to receive preferential treatment.
This comment does not apply. Generalized processor sharing expresses
preferential treatment via weighting. Various other forms of
preferential treatment require more elaborate idealized models.
This was said before I realized that your "lag" is just a measure of
fairness.
load is not directly relevant, but
appears to have some sort of relationship. Also, instead of pinned,
unpinned should be considered.
On Sun, May 27, 2007 at 11:29:51AM +1000, Peter Williams wrote:
If you have total and pinned you can get unpinned. It's probably
cheaper to maintain data for pinned than unpinned as there's less of it
on normal systems.
Regardless of the underlying accounting,
I was just replying to your criticism of my suggestion to keep pinned
task statistics and use them.
I've presented a coherent
algorithm. It may be that there's no demonstrable problem to solve.
On the other hand, if there really is a question as to how to load
balance in the presence of tasks pinned to cpus, I just answered it.
Unless I missed something there's nothing in your suggestion that does
anything more about handling pinned tasks than is already done by the
load balancer.
William Lee Irwin III wrote:
Using the signed minimax pseudonorm (i.e. the highest
signed lag, where positive is higher than all negative regardless of
magnitude) on unpinned lags yields a rather natural load balancing
algorithm consisting of migrating from highest to lowest signed lag,
with progressively longer periods for periodic balancing across
progressively higher levels of hierarchy in sched_domains etc. as usual.
Basically skip over pinned tasks as far as lag goes.
The trick with all that comes when tasks are pinned within a set of
cpus (especially crossing sched_domains) instead of to a single cpu.
On Sun, May 27, 2007 at 11:29:51AM +1000, Peter Williams wrote:
Yes, this makes the cost of maintaining the required data higher which
makes keeping pinned data more attractive than unpinned.
BTW keeping data for sets of CPU affinities could cause problems as the
number of possible sets is quite large (being 2 to the power of the
number of CPUs). So you need an algorithm based on pinned data for
single CPUs that knows the pinning isn't necessarily exclusive rather
than one based on sets of CPUs. As I understand it (which may be
wrong), the mechanism you describe below takes that approach.
Yes, the mechanism I described takes that approach.
William Lee Irwin III wrote:
The smpnice affair is better phrased in terms of task weighting. It's
simple to honor nice in such an arrangement. First unravel the
grouping hierarchy, then weight by nice. This looks like
[...]
In such a manner nice numbers obey the principle of least surprise.
On Sun, May 27, 2007 at 11:29:51AM +1000, Peter Williams wrote:
Is it just me or did you stray from the topic of handling cpu affinity
during load balancing to hierarchical load balancing? I couldn't see
anything in the above explanation that would improve the handling of cpu
affinity.
There was a second issue raised to which I responded. I didn't stray
per se. I addressed a second topic in the post.
OK.
To reiterate, I don't think that my suggestion is really necessary. I
think that the current load balancing (stand fast a small bug that's
being investigated) will come up with a good distribution of tasks to
CPUs within the constraints imposed by any CPU affinity settings.
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]
