Skip to content

RFC Coscheduling for Linux

Jan H. Schönherr lkml 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 RFC Latest60 patches 49 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/60sched: Store task_group->se[] pointers as part of cfs_rqkernel/sched/core.c kernel/sched/debug.c kernel/sched/fair.c +1 more+21 -290 replies
2/60sched: Introduce set_entity_cfs() to place a SE into a certain CFS runqueuekernel/sched/fair.c kernel/sched/sched.h+13 -250 replies
3/60sched: Setup sched_domain_shared for all sched_domainsinclude/linux/sched/topology.h kernel/sched/sched.h kernel/sched/topology.c+10 -140 replies
4/60sched: Replace sd_numa_mask() hack with something saneinclude/linux/sched/topology.h kernel/sched/topology.c+30 -210 replies
5/60sched: Allow to retrieve the sched_domain_topologyinclude/linux/sched/topology.h kernel/sched/topology.c+6 -00 replies
6/60sched: Add a lock-free variant of resched_cpu()kernel/sched/core.c kernel/sched/sched.h+25 -20 replies
7/60sched: Reduce dependencies of init_tg_cfs_entry()kernel/sched/core.c kernel/sched/fair.c kernel/sched/sched.h+9 -110 replies
8/60sched: Move init_entity_runnable_average() into init_tg_cfs_entry()kernel/sched/fair.c+1 -10 replies
9/60sched: Do not require a CFS in init_tg_cfs_entry()kernel/sched/fair.c+15 -130 replies
10/60sched: Use parent_entity() in more placeskernel/sched/fair.c+2 -20 replies
11/60locking/lockdep: Increase number of supported lockdep subclassesinclude/linux/lockdep.h+1 -10 replies
12/60locking/lockdep: Make cookie generator accessibleinclude/linux/lockdep.h kernel/locking/lockdep.c+17 -60 replies
13/60sched: Remove useless checks for root task-groupkernel/sched/fair.c+1 -50 replies
14/60sched: Refactor sync_throttle() to accept a CFS runqueue as argumentkernel/sched/fair.c+6 -70 replies
15/60sched: Introduce parent_cfs_rq() and use itkernel/sched/fair.c+12 -60 replies
16/60sched: Preparatory code movementkernel/sched/sched.h+13 -130 replies
17/60sched: Introduce and use generic task group CFS traversal functionskernel/sched/fair.c kernel/sched/sched.h+59 -360 replies
18/60sched: Fix return value of SCHED_WARN_ON()kernel/sched/sched.h+1 -10 replies
19/60sched: Add entity variants of enqueue_task_fair() and dequeue_task_fair()kernel/sched/fair.c kernel/sched/sched.h+51 -340 replies
20/60sched: Let {en,de}queue_entity_fair() work with a varying amount of taskskernel/sched/fair.c kernel/sched/sched.h+14 -100 replies
21/60sched: Add entity variants of put_prev_task_fair() and set_curr_task_fair()kernel/sched/fair.c kernel/sched/sched.h+23 -130 replies
22/60cosched: Add config option for coscheduling supportinit/Kconfig kernel/sched/Makefile kernel/sched/cosched.c+21 -00 replies
23/60cosched: Add core data structures for coschedulingkernel/sched/sched.h+151 -00 replies
24/60cosched: Do minimal pre-SMP coscheduler initializationkernel/sched/core.c kernel/sched/cosched.c kernel/sched/sched.h+93 -00 replies
25/60cosched: Prepare scheduling domain topology for coschedulingkernel/sched/core.c kernel/sched/cosched.c kernel/sched/sched.h+262 -00 replies
26/60cosched: Construct runqueue hierarchykernel/sched/core.c kernel/sched/cosched.c kernel/sched/sched.h+79 -00 replies
27/60cosched: Add some small helper functions for later usekernel/sched/sched.h+34 -00 replies
28/60cosched: Add is_sd_se() to distinguish SD-SEs from TG-SEskernel/sched/fair.c kernel/sched/sched.h+19 -70 replies
29/60cosched: Adjust code reflecting on the total number of CFS tasks on a CPUkernel/sched/core.c kernel/sched/fair.c kernel/sched/sched.h+28 -90 replies
30/60cosched: Disallow share modification on task groups for nowkernel/sched/fair.c+10 -00 replies
31/60cosched: Don't disable idle tick for nowkernel/time/tick-sched.c+14 -00 replies
32/60cosched: Specialize parent_cfs_rq() for hierarchical runqueueskernel/sched/fair.c+13 -00 replies
33/60cosched: Allow resched_curr() to be called for hierarchical runqueueskernel/sched/core.c+5 -00 replies
34/60cosched: Add rq_of() variants for different use caseskernel/sched/fair.c+35 -00 replies
35/60cosched: Adjust rq_lock() functions to work with hierarchical runqueueskernel/sched/sched.h+26 -30 replies
36/60cosched: Use hrq_of() for rq_clock() and rq_clock_task()kernel/sched/core.c kernel/sched/fair.c+19 -120 replies
37/60cosched: Use hrq_of() for (indirect calls to) ___update_load_sum()kernel/sched/fair.c+4 -40 replies
38/60cosched: Skip updates on non-CPU runqueues in cfs_rq_util_change()kernel/sched/fair.c+10 -10 replies
39/60cosched: Adjust task group management for hierarchical runqueueskernel/sched/cosched.c kernel/sched/fair.c kernel/sched/sched.h+124 -80 replies
40/60cosched: Keep track of task group hierarchy within each SD-RQkernel/sched/core.c kernel/sched/cosched.c kernel/sched/sched.h+25 -00 replies
41/60cosched: Introduce locking for leader activitieskernel/sched/cosched.c kernel/sched/sched.h+105 -00 replies
42/60cosched: Introduce locking for (mostly) enqueuing and dequeuingkernel/sched/cosched.c kernel/sched/sched.h+67 -00 replies
43/60cosched: Add for_each_sched_entity() variant for owned entitieskernel/sched/fair.c+70 -00 replies
44/60cosched: Perform various rq_of() adjustments in scheduler codekernel/sched/fair.c+6 -60 replies
45/60cosched: Continue to account all load on per-CPU runqueueskernel/sched/fair.c+6 -50 replies
46/60cosched: Warn on throttling attempts of non-CPU runqueueskernel/sched/fair.c+19 -20 replies
47/60cosched: Adjust SE traversal and locking for common leader activitieskernel/sched/fair.c+23 -50 replies
48/60cosched: Adjust SE traversal and locking for yielding and buddieskernel/sched/fair.c+42 -90 replies
49/60cosched: Adjust locking for enqueuing and dequeueingkernel/sched/fair.c+33 -00 replies
50/60cosched: Propagate load changes across hierarchy levelskernel/sched/fair.c+55 -00 replies
51/60cosched: Hacky work-around to avoid observing zero weight SD-SEkernel/sched/fair.c+15 -00 replies
52/60cosched: Support SD-SEs in enqueuing and dequeuingkernel/sched/fair.c+102 -50 replies
53/60cosched: Prevent balancing related functions from crossing hierarchy levelskernel/sched/fair.c+3 -10 replies
54/60cosched: Support idling in a coscheduled setkernel/sched/core.c kernel/sched/fair.c kernel/sched/idle.c +1 more+104 -120 replies
55/60cosched: Adjust task selection for coschedulingkernel/sched/fair.c+137 -130 replies
56/60cosched: Adjust wakeup preemption rules for coschedulingkernel/sched/fair.c+83 -20 replies
57/60cosched: Add sysfs interface to configure coscheduling on cgroupskernel/sched/core.c kernel/sched/cosched.c kernel/sched/sched.h+101 -00 replies
58/60cosched: Switch runqueues between regular scheduling and coschedulingkernel/sched/cosched.c kernel/sched/fair.c kernel/sched/sched.h+151 -30 replies
59/60cosched: Handle non-atomicity during switches to and from coschedulingkernel/sched/fair.c+68 -00 replies
60/60cosched: Add command line argument to enable coschedulingkernel/sched/cosched.c+31 -11 reply

Reviews trailers per patch

None of the 60 patches has a Reviewed-by or Acked-by.

PatchNishanth Aravamudan
SeriesPartly-reported-by
1/60
2/60
3/60
4/60
5/60
6/60
7/60
8/60
9/60
10/60
11/60
12/60
13/60
14/60
15/60
16/60
17/60
18/60
19/60
20/60
21/60
22/60
23/60
24/60
25/60
26/60
27/60
28/60
29/60
30/60
31/60
32/60
33/60
34/60
35/60
36/60
37/60
38/60
39/60
40/60
41/60
42/60
43/60
44/60
45/60
46/60
47/60
48/60
49/60
50/60
51/60
52/60
53/60
54/60
55/60
56/60
57/60
58/60
59/60
60/60

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v1 thread

Cover letter [RFC 00/60] Coscheduling for Linux

This patch series extends CFS with support for coscheduling. The implementation is versatile enough to cover many different coscheduling use-cases, while at the same time being non-intrusive, so that behavior of legacy workloads does not change.

Peter Zijlstra once called coscheduling a "scalability nightmare waiting to happen". Well, with this patch series, coscheduling certainly happened. However, I disagree on the scalability nightmare. :)

In the remainder of this email, you will find:

A) Quickstart guide for the impatient.
B) Why would I want this?
C) How does it work?
D) What can I *not* do with this?
E) What's the overhead?
F) High-level overview of the patches in this series.

Regards
Jan

A) Quickstart guide for the impatient.
--------------------------------------

Here is a quickstart guide to set up coscheduling at core-level for selected tasks on an SMT-capable system:

1. Apply the patch series to v4.19-rc2.
2. Compile with "CONFIG_COSCHEDULING=y".
3. Boot into the newly built kernel with an additional kernel command line argument "cosched_max_level=1" to enable coscheduling up to core-level.
4. Create one or more cgroups and set their "cpu.scheduled" to "1".
5. Put tasks into the created cgroups and set their affinity explicitly.
6. Enjoy tasks of the same group and on the same core executing simultaneously, whenever they are executed.

You are not restricted to coscheduling at core-level. Just select higher numbers in steps 3 and 4. See also further below for more information, esp. when you want to try higher numbers on larger systems.

Setting affinity explicitly for tasks within coscheduled cgroups is currently necessary, as the load balancing portion is still missing in this series.

B) Why would I want this?
-------------------------

Coscheduling can be useful for many different use cases. Here is an incomplete (very condensed) list:

1. Execute parallel applications that rely on active waiting or synchronous execution concurrently with other applications.

The prime example in this class are probably virtual machines. Here, coscheduling is an alternative to paravirtualized spinlocks, pause loop exiting, and other techniques with its own set of advantages and disadvantages over the other approaches.

2. Execute parallel applications with architecture-specific optimizations concurrently with other applications.

For example, a coscheduled application has a (usually) shared cache for itself, while it is executing. This keeps various cache-optimization techniques effective in face of other load, making coscheduling an alternative to other cache partitioning techniques.

3. Reduce resource contention between independent applications.

This is probably one of the most researched use-cases in recent years:
if we can derive subsets of tasks, where tasks in a subset don't interfere much with each other when executed in parallel, then coscheduling can be used to realize this more efficient schedule. And "resource" is a really loose term here: from execution units in an SMT system, over cache pressure, over memory bandwidth, to a processor's power budget and resulting frequency selection.

4. Support the management of (multiple) (parallel) applications.

Coscheduling does not only enable simultaneous execution, it also gives a form of concurrency control, which can be used for various effects. The currently most relevant example in this category is, that coscheduling can be used to close certain side-channels or at least contribute to making their exploitation harder by isolating applications in time.

In the L1TF context, it prevents other applications from loading additional data into the L1 cache, while one application tries to leak data.

C) How does it work?
--------------------

This patch series introduces hierarchical runqueues, that represent larger and larger fractions of the system. By default, there is one runqueue per scheduling domain. These additional levels of runqueues are activated by the "cosched_max_level=" kernel command line argument. The bottom level is 0.

One CPU per hierarchical runqueue is considered the leader, who is primarily responsible for the scheduling decision at this level. Once the leader has selected a task group to execute, it notifies all leaders of the runqueues below it to select tasks/task groups within the selected task group.

For each task-group, the user can select at which level it should be scheduled. If you set "cpu.scheduled" to "1", coscheduling will typically happen at core-level on systems with SMT. That is, if one SMT sibling executes a task from this task group, the other sibling will do so, too. If no task is available, the SMT sibling will be idle. With "cpu.scheduled" set to "2" this is extended to the next level, which is typically a whole socket on many systems. And so on. If you feel, that this does not provide enough flexibility, you can specify "cosched_split_domains" on the kernel command line to create more fine-grained scheduling domains for your system.

You currently have to explicitly set affinities of tasks within coscheduled task groups, as load balancing is not implemented for them at this point.

D) What can I *not* do with this?
---------------------------------

Besides the missing load-balancing within coscheduled task-groups, this implementation has the following properties, which might be considered short-comings.

This particular implementation focuses on SCHED_OTHER tasks managed by CFS and allows coscheduling them. Interrupts as well as tasks in higher scheduling classes are currently out-of-scope: they are assumed to be negligible interruptions as far as coscheduling is concerned and they do *not* cause a preemption of a whole group. This implementation could be extended to cover higher scheduling classes. Interrupts, however, are an orthogonal issue.

The collective context switch from one coscheduled set of tasks to another -- while fast -- is not atomic. If a use-case needs the absolute guarantee that all tasks of the previous set have stopped executing before any task of the next set starts executing, an additional hand-shake/barrier needs to be added.

Together with load-balancing, this implementation gains the ability to restrict execution of tasks within a task-group to be below a single hierarchical runqueue of a certain level. From there, it is a short step to dynamically adjust this level in relation to the number of runnable tasks. This will enable wide coscheduling with a minimum of fragmentation under dynamic load.

E) What's the overhead?
-----------------------

Each (active) hierarchy level has roughly the same effect as one additional level of nested cgroups. In addition -- at this stage -- there may be some additional lock contention if you coschedule larger fractions of the system with a dynamic task set.

F) High-level overview of the patches in this series.
-----------------------------------------------------

1 to 21: Preparation patches that keep the following coscheduling patches
manageable. Of general interest, even without coscheduling, may be the following:

1: Store task_group->se[] pointers as part of cfs_rq
2: Introduce set_entity_cfs() to place a SE into a certain CFS runqueue 4: Replace sd_numa_mask() hack with something sane
15: Introduce parent_cfs_rq() and use it
17: Introduce and use generic task group CFS traversal functions

As well as some simpler clean-ups in patches 8, 10, 13, and 18.

22 to 60: The actual coscheduling functionality. Highlights are:

23: Data structures used for coscheduling.
24-26: Creation of root-task-group runqueue hierarchy. 39-40: Runqueue hierarchies for normal task groups. 41-42: Locking strategies under coscheduling. 47-49: Adjust core CFS code.
52: Adjust core CFS code.
54-56: Adjust core CFS code.
57-59: Enabling/disabling of coscheduling via cpu.scheduled

Jan H. Schönherr (60):
sched: Store task_group->se[] pointers as part of cfs_rq
sched: Introduce set_entity_cfs() to place a SE into a certain CFS
runqueue
sched: Setup sched_domain_shared for all sched_domains
sched: Replace sd_numa_mask() hack with something sane
sched: Allow to retrieve the sched_domain_topology
sched: Add a lock-free variant of resched_cpu()
sched: Reduce dependencies of init_tg_cfs_entry()
sched: Move init_entity_runnable_average() into init_tg_cfs_entry()
sched: Do not require a CFS in init_tg_cfs_entry()
sched: Use parent_entity() in more places
locking/lockdep: Increase number of supported lockdep subclasses locking/lockdep: Make cookie generator accessible
sched: Remove useless checks for root task-group
sched: Refactor sync_throttle() to accept a CFS runqueue as argument
sched: Introduce parent_cfs_rq() and use it
sched: Preparatory code movement
sched: Introduce and use generic task group CFS traversal functions
sched: Fix return value of SCHED_WARN_ON()
sched: Add entity variants of enqueue_task_fair() and
dequeue_task_fair()
sched: Let {en,de}queue_entity_fair() work with a varying amount of
tasks
sched: Add entity variants of put_prev_task_fair() and
set_curr_task_fair()
cosched: Add config option for coscheduling support
cosched: Add core data structures for coscheduling
cosched: Do minimal pre-SMP coscheduler initialization
cosched: Prepare scheduling domain topology for coscheduling
cosched: Construct runqueue hierarchy
cosched: Add some small helper functions for later use
cosched: Add is_sd_se() to distinguish SD-SEs from TG-SEs
cosched: Adjust code reflecting on the total number of CFS tasks on a
CPU
cosched: Disallow share modification on task groups for now
cosched: Don't disable idle tick for now
cosched: Specialize parent_cfs_rq() for hierarchical runqueues
cosched: Allow resched_curr() to be called for hierarchical runqueues
cosched: Add rq_of() variants for different use cases
cosched: Adjust rq_lock() functions to work with hierarchical
runqueues
cosched: Use hrq_of() for rq_clock() and rq_clock_task()
cosched: Use hrq_of() for (indirect calls to) ___update_load_sum()
cosched: Skip updates on non-CPU runqueues in cfs_rq_util_change()
cosched: Adjust task group management for hierarchical runqueues
cosched: Keep track of task group hierarchy within each SD-RQ
cosched: Introduce locking for leader activities
cosched: Introduce locking for (mostly) enqueuing and dequeuing
cosched: Add for_each_sched_entity() variant for owned entities
cosched: Perform various rq_of() adjustments in scheduler code
cosched: Continue to account all load on per-CPU runqueues
cosched: Warn on throttling attempts of non-CPU runqueues
cosched: Adjust SE traversal and locking for common leader activities
cosched: Adjust SE traversal and locking for yielding and buddies
cosched: Adjust locking for enqueuing and dequeueing
cosched: Propagate load changes across hierarchy levels
cosched: Hacky work-around to avoid observing zero weight SD-SE
cosched: Support SD-SEs in enqueuing and dequeuing
cosched: Prevent balancing related functions from crossing hierarchy
levels
cosched: Support idling in a coscheduled set
cosched: Adjust task selection for coscheduling
cosched: Adjust wakeup preemption rules for coscheduling
cosched: Add sysfs interface to configure coscheduling on cgroups
cosched: Switch runqueues between regular scheduling and coscheduling
cosched: Handle non-atomicity during switches to and from coscheduling
cosched: Add command line argument to enable coscheduling

 include/linux/lockdep.h        |    4 +-
 include/linux/sched/topology.h |   18 +-
 init/Kconfig                   |   11 +
 kernel/locking/lockdep.c       |   21 +-
 kernel/sched/Makefile          |    1 +
 kernel/sched/core.c            |  109 +++-
 kernel/sched/cosched.c         |  882 +++++++++++++++++++++++++++++
 kernel/sched/debug.c           |    2 +-
 kernel/sched/fair.c            | 1196 ++++++++++++++++++++++++++++++++--------
 kernel/sched/idle.c            |    7 +-
 kernel/sched/sched.h           |  461 +++++++++++++++-
 kernel/sched/topology.c        |   57 +-
 kernel/time/tick-sched.c       |   14 +
 13 files changed, 2474 insertions(+), 309 deletions(-)
 create mode 100644 kernel/sched/cosched.c
Signature · 1 line
2.9.3.1.gcba166c.dirty