[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
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.


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. 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). 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.
This patch ensures an error bound of (max task weight currently in system)
* sysctl_base_round_slice compared to an idealized fair system.

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.

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 NUMA.

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.

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 19:11    [W:0.163 / U:2.756 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site