[lkml]   [2007]   [Jul]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [RFC] scheduler: improve SMP fairness in CFS
Tong Li wrote:
> On Mon, 23 Jul 2007, Chris Snook wrote:
>> This patch is massive overkill. Maybe you're not seeing the overhead
>> on your 8-way box, but I bet we'd see it on a 4096-way NUMA box with a
>> partially-RT workload. Do you have any data justifying the need for
>> this patch?
>> Doing anything globally is expensive, and should be avoided at all
>> costs. The scheduler already rebalances when a CPU is idle, so you're
>> really just rebalancing the overload here. On a server workload, we
>> don't necessarily want to do that, since the overload may be multiple
>> threads spawned to service a single request, and could be sharing a
>> lot of data.
>> Instead of an explicit system-wide fairness invariant (which will get
>> very hard to enforce when you throw SCHED_FIFO processes into the mix
>> and the scheduler isn't running on some CPUs), try a simpler
>> invariant. If we guarantee that the load on CPU X does not differ
>> from the load on CPU (X+1)%N by more than some small constant, then we
>> know that the system is fairly balanced. We can achieve global
>> fairness with local balancing, and avoid all this overhead. This has
>> the added advantage of keeping most of the migrations
>> core/socket/node-local on SMT/multicore/NUMA systems.
> Chris,
> These are all good comments. Thanks. I see three concerns and I'll try
> to address each.
> 1. Unjustified effort/cost
> My view is that fairness (or proportional fairness) is a first-order
> metric and necessary in many cases even at the cost of performance.

In the cases where it's critical, we have realtime. In the cases where it's
important, this implementation won't keep latency low enough to make people
happier. If you've got a test case to prove me wrong, I'd like to see it.

> A
> server running multiple client apps certainly doesn't want the clients
> to see that they are getting different amounts of service, assuming the
> clients are of equal importance (priority).

A conventional server receives client requests, does a brief amount of work, and
then gives a response. This patch doesn't help that workload. This patch helps
the case where you've got batch jobs running on a slightly overloaded compute
server, and unfairness means you end up waiting for a couple threads to finish
at the end while CPUs sit idle. I don't think it's that big of a problem, and
if it is, I think we can solve it in a more elegant way than reintroducing
expired queues.

> When the clients have
> different priorities, the server also wants to give them service time
> proportional to their priority/weight. The same is true for desktops,
> where users want to nice tasks and see an effect that's consistent with
> what they expect, i.e., task CPU time should be proportional to their
> nice values. The point is that it's important to enforce fairness
> because it enables users to control the system in a deterministic way
> and it helps each task get good response time. CFS achieves this on
> local CPUs and this patch makes the support stronger for SMPs. It's
> overkill to enforce unnecessary degree of fairness, but it is necessary
> to enforce an error bound, even if large, such that the user can
> reliably know what kind of CPU time (even performance) he'd get after
> making a nice value change.

Doesn't CFS already do this?

> This patch ensures an error bound of (max
> task weight currently in system) * sysctl_base_round_slice compared to
> an idealized fair system.

The thing that bugs me about this is the diminishing returns. It looks like it
will only give a substantial benefit when system load is somewhere between 1.0
and 2.0. On a heavily-loaded system, CFS will do the right thing within a good
margin of error, and on an underloaded system, even a naive scheduler will do
the right thing. If you want to optimize smp fairness in this range, that's
great, but there's probably a lighter-weight way to do it.

> 2. High performance overhead
> Two sources of overhead: (1) the global rw_lock, and (2) task
> migrations. I agree they can be problems on NUMA, but I'd argue they are
> not on SMPs. Any global lock can cause two performance problems: (1)
> serialization, and (2) excessive remote cache accesses and traffic. IMO
> (1) is not a problem since this is a rw_lock and a write_lock occurs
> infrequently only when all tasks in the system finish the current round.
> (2) could be a problem as every read/write lock causes an invalidation.
> It could be improved by using Nick's ticket lock. On the other hand,
> this is a single cache line and it's invalidated only when a CPU
> finishes all tasks in its local active RB tree, where each nice 0 task
> takes sysctl_base_round_slice (e.g., 30ms) to finish, so it looks to me
> the invalidations would be infrequent enough and could be noise in the
> whole system.

Task migrations don't bother me all that much. Since we're migrating the
*overload*, I expect those processes to be fairly cache-cold whenever we get
around to them anyway. It'd be nice to be SMT/multicore/NUMA-smart about the
migrations, but that's an implementation detail.

The global lock is what really bothers me. It's not just that it'll suck in
certain rare cases (though I think it will), but it's really more the top-down
design. If we take a bottom-up approach, first keeping fairness between
neighbors, it'll function identically on the low-end systems, but it'll be a
huge win on the big systems, instead of a potential bottleneck.

> The patch can introduce more task migrations. I don't think it's a
> problem in SMPs. For one, CFS already is doing context switches more
> frequently than before, and thus even if a task doesn't migration, it
> may still miss in the local cache because the previous task kicked out
> its data. In this sense, migration doesn't add more cache misses. Now,
> in NUMA, the penalty of a cache miss can be much higher if we migrate
> off-node. Here, I agree that this can be a problem. For NUMA, I'd expect
> the user to tune sysctl_base_round_slice to a large enough value to
> avoid frequent migrations (or just affinitize tasks). Benchmarking could
> also help us determine a reasonable default sysctl_base_round_slice for

The kernel should be tuned reasonably by default. The days in which NUMA
implied a supercomputer tuned by specialists are over. NUMA is commodity now.
As a simple heuristic, I suggest multiplying your default
sysctl_base_round_slice by (log2(num_nodes)+1). This scales the migration cost
proportionally on most simple topologies. People with gigantic torus-topology
supercomputers who still bring in specialists to tune everything might still
want to raise it.

> 3. Hard to enforce fairness when there are non-SCHED_FAIR tasks
> All we want is to enforce fairness among the SCHED_FAIR tasks.
> Leveraging CFS, this patch makes sure relative CPU time of two
> SCHED_FAIR tasks in an SMP equals their weight ratio. In other words, if
> the entire SCHED_FAIR tasks are given X amount of CPU time, then a
> weight w task is guaranteed with w/X time in any interval of time.

The problem is that there are various reasons why a particular CPU might not get
to execute this codepath for a little while, and then either your round
invariant is broken, or you have a performance-killing barrier. Relaxing your
invariants and your locking would mitigate this.

Concerns aside, I agree that fairness is important, and I'd really like to see a
test case that demonstrates the problem.

-- Chris
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2007-07-24 20:11    [W:0.101 / U:4.968 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site