$ ps -ef | grep migration
root          12       2  0       00:00:01 [migration/0]

CONFIG_CGROUPS                     # 1. 是否支持 cgroup，下面进一步区分 cpu/memory/hugetlb/...
  |-CONFIG_MEMCG                   #   1.1 是否支持 memory cgroup
  |-CONFIG_BLK_CGROUP              #   1.2 是否支持 blkio cgroup
  |-CONFIG_CGROUP_SCHED            #   1.3 是否支持 cpu cgroup
  |   |-CONFIG_RT_GROUP_SCHED      #     1.3.1 是否支持 realtime scheduler cpu cgroup
  |   |-CONFIG_FAIR_GROUP_SCHED    #     1.3.2 是否支持 cfs for task cgroup
  |       |-CONFIG_CFS_BANDWIDTH   #       1.3.2.1 是否支持 cfs cpu bandwidth
  |
  |-CONFIG_CGROUP_PIDS             #   1.4 是否支持 pid cgroup
  |-CONFIG_CPUSETS                 #   1.5 是否支持 cpuset cgroup
  |-CONFIG_CGROUP_DEVICE           #   1.6 是否支持 device cgroup
  |-CONFIG_CGROUP_CPUACCT          #   1.7 是否支持 cpu,acc cgroup
  |-...                            #   1.8 是否支持 ... cgroup

// init/Kconfig

menuconfig CGROUPS
    bool "Control Group support"
    help
      This option adds support for grouping sets of processes together, for
      use with process control subsystems such as Cpusets, CFS, memory controls or device isolation.
      See
        - Documentation/scheduler/sched-design-CFS.rst    (CFS)
        - Documentation/admin-guide/cgroup-v1/ (features for grouping, isolation and resource control)

if CGROUPS
    config MEMCG
        bool "Memory controller"
        select PAGE_COUNTER
        help
          Provides control over the memory footprint of tasks in a cgroup.
    config BLK_CGROUP
        bool "IO controller"
        depends on BLOCK
        help
          Generic block IO controller cgroup interface. This is the common
          cgroup interface which should be used by various IO controlling policies.

          Currently, CFQ IO scheduler uses it to recognize task groups and
          control disk bandwidth allocation (proportional time slice allocation)
          to such task groups. It is also used by bio throttling logic in
          block layer to implement upper limit in IO rates on a device.

          This option only enables generic Block IO controller infrastructure.
          One needs to also enable actual IO controlling logic/policy. For
          enabling proportional weight division of disk bandwidth in CFQ, set
          CONFIG_BFQ_GROUP_IOSCHED=y; for enabling throttling policy, set
          CONFIG_BLK_DEV_THROTTLING=y.

          See Documentation/admin-guide/cgroup-v1/blkio-controller.rst for more information.

    menuconfig CGROUP_SCHED
        bool "CPU controller"
        help
          This feature lets CPU scheduler recognize task groups and control CPU
          bandwidth allocation to such task groups. It uses cgroups to group tasks.
    if CGROUP_SCHED
        config FAIR_GROUP_SCHED
            bool "Group scheduling for SCHED_OTHER"
            depends on CGROUP_SCHED
            default CGROUP_SCHED

            config CFS_BANDWIDTH
                bool "CPU bandwidth provisioning for FAIR_GROUP_SCHED"
                depends on FAIR_GROUP_SCHED
                help
                  This option allows users to define CPU bandwidth rates (limits) for
                  tasks running within the fair group scheduler.  Groups with no limit
                  set are considered to be unconstrained and will run with no restriction.
                  See Documentation/scheduler/sched-bwc.rst for more information.
        config RT_GROUP_SCHED
            bool "Group scheduling for SCHED_RR/FIFO"
            depends on CGROUP_SCHED
            help
              This feature lets you explicitly allocate real CPU bandwidth
              to task groups. If enabled, it will also make it impossible to
              schedule realtime tasks for non-root users until you allocate realtime bandwidth for them.
              See Documentation/scheduler/sched-rt-group.rst for more information.
    endif #CGROUP_SCHED

    config CGROUP_PIDS
        bool "PIDs controller"
    config CPUSETS
        bool "Cpuset controller"
        help
          This option will let you create and manage CPUSETs which
          allow dynamically partitioning a system into sets of CPUs and
          Memory Nodes and assigning tasks to run only within those sets.
          This is primarily useful on large SMP or NUMA systems.
    config CGROUP_DEVICE
        bool "Device controller"
        help
          Provides a cgroup controller implementing whitelists for
          devices which a process in the cgroup can mknod or open.
    config CGROUP_CPUACCT
        bool "Simple CPU accounting controller"
        help
          Provides a simple controller for monitoring the total CPU consumed by the tasks in a cgroup.
endif # CGROUPS

$ chrt --help
Show or change the real-time scheduling attributes of a process.
...

$ chrt -p 219027
pid 219027's current scheduling policy: SCHED_OTHER
pid 219027's current scheduling priority: 0

# 1. 挂载 cgroup 文件系统
$ mount -t tmpfs cgroup_root /sys/fs/cgroup
$ mkdir /sys/fs/cgroup/cpu                       # 创建 cpu 目录，用于控制 cpu 资源份额
$ mount -t cgroup -ocpu none /sys/fs/cgroup/cpu
$ cd /sys/fs/cgroup/cpu

# 2. 创建进程组对应的 cgroup 目录
$ mkdir multimedia     # create "multimedia" group of tasks
$ mkdir browser        # create "browser" group of tasks

# 3. 设置进程组的 CPU 份额： multimedia 可以比 browser 多用一倍
$ echo 2048 > multimedia/cpu.shares
$ echo 1024 > browser/cpu.shares

# 4. 启动浏览器进程 firefox 并放到 "browser" 进程组
$ firefox &
$ echo <firefox_pid> > browser/tasks

# 启动多媒体进程 gmplayer 并放到 "multimedia" 进程组
$ gmplayer &
$ echo <movie_player_pid> > multimedia/tasks

cpu.cfs_period_us=100ms
cpu.cfs_quota_us=-1
cpu.cfs_burst_us=0  # 5.15+

$ cat /sys/fs/cgroup/cpu/kubepods/pod<pod_id>/cpu.stat
nr_periods 1312889
nr_throttled 100714
throttled_time 22081774986248

// include/linux/sched.h

struct task_struct {
    struct thread_info        thread_info;
    volatile long            state; /* -1 unrunnable, 0 runnable, >0 stopped: */

    void                  *stack;
    refcount_t             usage;
    unsigned int           flags; /* Per task flags (PF_*), defined further below: */
    unsigned int           ptrace;

    int                on_cpu;
    struct __call_single_node    wake_entry;
    unsigned int            cpu; /* Current CPU: */
    unsigned int            wakee_flips;
    unsigned long           wakee_flip_decay_ts;
    struct task_struct     *last_wakee;

    int                recent_used_cpu;
    int                wake_cpu;
    int                on_rq;

    int                prio;
    int                static_prio;
    int                normal_prio;

    const struct sched_class    *sched_class;
    struct sched_entity          se;             // schedule entity, including vruntime
#ifdef CONFIG_CGROUP_SCHED
    struct task_group           *sched_task_group;
#endif
    ...
};

// https://github.com/torvalds/linux/blob/v5.10/kernel/sched/sched.h#L383

/* Task group related information */
struct task_group {
    struct cgroup_subsys_state css;

#ifdef CONFIG_FAIR_GROUP_SCHED
    struct sched_entity  **se; /* schedulable entities of this group on each CPU */
    struct cfs_rq        **cfs_rq; /* runqueue "owned" by this group on each CPU */
    unsigned long          shares;

    atomic_long_t        load_avg ____cacheline_aligned;
#endif

#ifdef CONFIG_RT_GROUP_SCHED
    struct sched_rt_entity    **rt_se;
    struct rt_rq        **rt_rq;

    struct rt_bandwidth    rt_bandwidth;
#endif

    struct rcu_head        rcu;
    struct list_head    list;

    struct task_group    *parent;
    struct list_head    siblings;
    struct list_head    children;

#ifdef CONFIG_SCHED_AUTOGROUP
    struct autogroup    *autogroup;
#endif

    struct cfs_bandwidth    cfs_bandwidth;

#ifdef CONFIG_UCLAMP_TASK_GROUP
    /* The two decimal precision [%] value requested from user-space */
    unsigned int        uclamp_pct[UCLAMP_CNT];
    /* Clamp values requested for a task group */
    struct uclamp_se    uclamp_req[UCLAMP_CNT];
    /* Effective clamp values used for a task group */
    struct uclamp_se    uclamp[UCLAMP_CNT];
#endif

};

// https://github.com/torvalds/linux/blob/v5.10/include/linux/sched.h#L451

struct sched_entity {
    struct load_weight      load; // For load-balancing
    struct rb_node          run_node;
    struct list_head        group_node;
    unsigned int            on_rq;

    u64                exec_start;
    u64                sum_exec_runtime;
    u64                vruntime;              // unit: ns
    u64                prev_sum_exec_runtime;

    u64                nr_migrations;

    struct sched_statistics        statistics;

#ifdef CONFIG_FAIR_GROUP_SCHED
    int                   depth;
    struct sched_entity  *parent;
    struct cfs_rq        *cfs_rq; // rq on which this entity is (to be) queued
    struct cfs_rq        *my_q;   // rq "owned" by this entity/group
    unsigned long         runnable_weight; /* cached value of my_q->h_nr_running */
#endif

    // Per entity load average tracking.
    // Put into separate cache line so it does not collide with read-mostly values above.
    struct sched_avg        avg;
};

// https://github.com/torvalds/linux/blob/v5.10/kernel/sched/sched.h#L518

/* CFS-related fields in a runqueue (rq) */
struct cfs_rq {
    struct load_weight    load;
    unsigned int        nr_running;
    unsigned int        h_nr_running;      /* SCHED_{NORMAL,BATCH,IDLE} */
    unsigned int        idle_h_nr_running; /* SCHED_IDLE */

    u64            exec_clock;
    u64            min_vruntime;
    u64            min_vruntime_copy;

    struct rb_root_cached    tasks_timeline; // rbtree

    /*
     * 'curr' points to currently running entity on this cfs_rq.
     * It is set to NULL otherwise (i.e when none are currently running).
     */
    struct sched_entity    *curr;
    struct sched_entity    *next;
    struct sched_entity    *last;
    struct sched_entity    *skip;

    /*
     * CFS load tracking
     */
    struct sched_avg    avg;
#ifndef CONFIG_64BIT
    u64            load_last_update_time_copy;
#endif
    struct {
        raw_spinlock_t    lock ____cacheline_aligned;
        int        nr;
        unsigned long    load_avg;
        unsigned long    util_avg;
        unsigned long    runnable_avg;
    } removed;

#ifdef CONFIG_FAIR_GROUP_SCHED
    unsigned long        tg_load_avg_contrib;
    long            propagate;
    long            prop_runnable_sum;

    /*
     *   h_load = weight * f(tg)
     *
     * Where f(tg) is the recursive weight fraction assigned to
     * this group.
     */
    unsigned long        h_load;
    u64            last_h_load_update;
    struct sched_entity    *h_load_next;
#endif /* CONFIG_FAIR_GROUP_SCHED */

#ifdef CONFIG_FAIR_GROUP_SCHED
    //  the main per-CPU runqueue structure, which cfs_rq would attached to
    struct rq        *rq;    /* CPU runqueue to which this cfs_rq is attached */

    /*
     * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
     * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
     * (like users, containers etc.)
     *
     * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a CPU.
     * This list is used during load balance.
     */
    int            on_list;
    struct list_head    leaf_cfs_rq_list;
    struct task_group    *tg;    /* group that "owns" this runqueue */

#ifdef CONFIG_CFS_BANDWIDTH
    int            runtime_enabled;
    s64            runtime_remaining;

    u64            throttled_clock;
    u64            throttled_clock_task;
    u64            throttled_clock_task_time;
    int            throttled;
    int            throttle_count;
    struct list_head    throttled_list;
#endif /* CONFIG_CFS_BANDWIDTH */
#endif /* CONFIG_FAIR_GROUP_SCHED */
};

// include/linux/rbtree.h

// Leftmost-cached rbtrees.
struct rb_root_cached {
    struct rb_root  rb_root;
    struct rb_node *rb_leftmost;
};

// kernel/sched/sched.h

struct sched_class {
    int uclamp_enabled;

    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
    void (*yield_task)   (struct rq *rq);
    bool (*yield_to_task)(struct rq *rq, struct task_struct *p);

    void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);

    struct task_struct *(*pick_next_task)(struct rq *rq);

    void (*put_prev_task)(struct rq *rq, struct task_struct *p);
    void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);

    int (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);
    int  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
    void (*migrate_task_rq)(struct task_struct *p, int new_cpu);

    void (*task_woken)(struct rq *this_rq, struct task_struct *task);

    void (*set_cpus_allowed)(struct task_struct *p, const struct cpumask *newmask);

    void (*rq_online)(struct rq *rq);
    void (*rq_offline)(struct rq *rq);

    void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
    void (*task_fork)(struct task_struct *p);
    void (*task_dead)(struct task_struct *p);

    /*
     * The switched_from() call is allowed to drop rq->lock, therefore we
     * cannot assume the switched_from/switched_to pair is serliazed by
     * rq->lock. They are however serialized by p->pi_lock.
     */
    void (*switched_from)(struct rq *this_rq, struct task_struct *task);
    void (*switched_to)  (struct rq *this_rq, struct task_struct *task);
    void (*prio_changed) (struct rq *this_rq, struct task_struct *task, int oldprio);

    unsigned int (*get_rr_interval)(struct rq *rq, struct task_struct *task);

    void (*update_curr)(struct rq *rq);

#define TASK_SET_GROUP        0
#define TASK_MOVE_GROUP        1

#ifdef CONFIG_FAIR_GROUP_SCHED
    void (*task_change_group)(struct task_struct *p, int type);
#endif
} __aligned(STRUCT_ALIGNMENT); /* STRUCT_ALIGN(), vmlinux.lds.h */

// kernel/sched/fair.c

/*
 * All the scheduling class methods:
 */
const struct sched_class fair_sched_class
    __section("__fair_sched_class") = {
    .enqueue_task        = enqueue_task_fair,
    .dequeue_task        = dequeue_task_fair,
    .yield_task        = yield_task_fair,
    .yield_to_task        = yield_to_task_fair,

    .check_preempt_curr    = check_preempt_wakeup,

    .pick_next_task        = __pick_next_task_fair,
    .put_prev_task        = put_prev_task_fair,
    .set_next_task          = set_next_task_fair,

#ifdef CONFIG_SMP
    .balance        = balance_fair,
    .select_task_rq        = select_task_rq_fair,
    .migrate_task_rq    = migrate_task_rq_fair,

    .rq_online        = rq_online_fair,
    .rq_offline        = rq_offline_fair,

    .task_dead        = task_dead_fair,
    .set_cpus_allowed    = set_cpus_allowed_common,
#endif

    .task_tick        = task_tick_fair,
    .task_fork        = task_fork_fair,

    .prio_changed        = prio_changed_fair,
    .switched_from        = switched_from_fair,
    .switched_to        = switched_to_fair,

    .get_rr_interval    = get_rr_interval_fair,

    .update_curr        = update_curr_fair,

#ifdef CONFIG_FAIR_GROUP_SCHED
    .task_change_group    = task_change_group_fair,
#endif

#ifdef CONFIG_UCLAMP_TASK
    .uclamp_enabled        = 1,
#endif
};

$ cat /proc/sys/kernel/sched_cfs_bandwidth_slice_us
5000

$ sysctl -a | grep cfs_
kernel.sched_cfs_bandwidth_slice_us = 5000

sched: Introduce primitives to account for CFS bandwidth tracking
In this patch we introduce the notion of CFS bandwidth, partitioned into
globally unassigned bandwidth, and locally claimed bandwidth.

 - The global bandwidth is per task_group, it represents a pool of unclaimed
   bandwidth that cfs_rqs can allocate from.
 - The local bandwidth is tracked per-cfs_rq, this represents allotments from
   the global pool bandwidth assigned to a specific cpu.

Bandwidth is managed via cgroupfs, adding two new interfaces to the cpu subsystem:
 - cpu.cfs_period_us : the bandwidth period in usecs
 - cpu.cfs_quota_us : the cpu bandwidth (in usecs) that this tg will be allowed
   to consume over period above.

static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)
{
    int i;
    struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
    static DEFINE_MUTEX(mutex);

    if (tg == &root_task_group)
        return -EINVAL;

    /*
     * Ensure we have at some amount of bandwidth every period.  This is
     * to prevent reaching a state of large arrears when throttled via
     * entity_tick() resulting in prolonged exit starvation.
     */
    if (quota < min_cfs_quota_period || period < min_cfs_quota_period)
        return -EINVAL;

    /*
     * Likewise, bound things on the otherside by preventing insane quota
     * periods.  This also allows us to normalize in computing quota
     * feasibility.
     */
    if (period > max_cfs_quota_period)
        return -EINVAL;

    mutex_lock(&mutex);
    raw_spin_lock_irq(&cfs_b->lock);
    cfs_b->period = ns_to_ktime(period);
    cfs_b->quota = quota;
    raw_spin_unlock_irq(&cfs_b->lock);

    for_each_possible_cpu(i) {
        struct cfs_rq *cfs_rq = tg->cfs_rq[i];
        struct rq *rq = rq_of(cfs_rq);

        raw_spin_lock_irq(&rq->lock);
        cfs_rq->runtime_enabled = quota != RUNTIME_INF;
        cfs_rq->runtime_remaining = 0;
        raw_spin_unlock_irq(&rq->lock);
    }
    mutex_unlock(&mutex);

    return 0;
}

package main

import (
	"crypto/sha512"
	"flag"
	"log"
	"syscall"
	"time"
)

func main() {
	sleep := flag.Duration("sleep", time.Second, "sleep between iterations")
	interations := flag.Int("iterations", 100, "number of iterations")
	flag.Parse()

	time.Sleep(time.Second)

	b := time.Now()
	for i := 0; i < *interations; i++ {
		s := time.Now()
		burn(time.Millisecond * 5)
		e := time.Now().Sub(s)

		log.Printf("[%d] burn took %dms, real time so far: %dms, cpu time so far: %dms", i, ms(e), ms(time.Since(b)), ms(usage()))
		time.Sleep(*sleep)
	}
}

func ms(duration time.Duration) int {
	return int(duration.Nanoseconds() / 1000 / 1000)
}

func burn(duration time.Duration) {
	s := time.Now()

	for {
		sum := sha512.New()
		sum.Write([]byte("banana"))
		sum.Sum([]byte{})

		if time.Since(s) > duration {
			break
		}
	}
}

func usage() time.Duration {
	r := syscall.Rusage{}
	syscall.Getrusage(syscall.RUSAGE_SELF, &r)
	return time.Duration(r.Stime.Nano() + r.Utime.Nano())
}

$ dk run --rm -it -v $(pwd):$(pwd) -w $(pwd) golang:1.19.4 go run cfs.go -iterations 20 -sleep 10ms
2023/02/05 09:50:35 [0] burn took 5ms, real time so far: 5ms, cpu time so far: 7ms
2023/02/05 09:50:35 [1] burn took 5ms, real time so far: 20ms, cpu time so far: 12ms
2023/02/05 09:50:35 [2] burn took 5ms, real time so far: 37ms, cpu time so far: 17ms
...
2023/02/05 09:50:35 [18] burn took 5ms, real time so far: 338ms, cpu time so far: 102ms
2023/02/05 09:50:35 [19] burn took 5ms, real time so far: 355ms, cpu time so far: 108ms

$ dk run --rm -it --cpu-quota 25000 --cpu-period 100000 -v $(pwd):$(pwd) -w $(pwd) golang:1.19.4 go run cfs.go -iterations 20 -sleep 10ms
2023/02/05 09:48:38 [0] burn took 5ms, real time so far: 5ms, cpu time so far: 6ms
2023/02/05 09:48:38 [1] burn took 11ms, real time so far: 35ms, cpu time so far: 19ms
2023/02/05 09:48:38 [2] burn took 5ms, real time so far: 51ms, cpu time so far: 24ms
2023/02/05 09:48:38 [3] burn took 20ms, real time so far: 83ms, cpu time so far: 28ms
2023/02/05 09:48:38 [4] burn took 5ms, real time so far: 100ms, cpu time so far: 33ms
2023/02/05 09:48:38 [5] burn took 5ms, real time so far: 115ms, cpu time so far: 38ms
2023/02/05 09:48:38 [6] burn took 5ms, real time so far: 131ms, cpu time so far: 43ms
2023/02/05 09:48:38 [7] burn took 5ms, real time so far: 147ms, cpu time so far: 49ms
2023/02/05 09:48:38 [8] burn took 24ms, real time so far: 182ms, cpu time so far: 51ms
2023/02/05 09:48:38 [9] burn took 5ms, real time so far: 197ms, cpu time so far: 56ms
...