何时均衡 在linux内核中，有一些场景会触发任务均衡的分布在系统的各个cpu上，可以分为以下几个场景： 任务放置：task placement，fork创建的任务、sched_exec的任务或者阻塞被唤醒的任务，这些任务加入就绪队列时，可以确定放置任务到那个cpu上。 主动均衡：active upmigration，一个低算力的cpu无法运行某个重载任务时（misfit task），可以主动将misfit task向上迁移到算力更高的cpu上。 周期均衡：tick load balance，周期性的触发均衡。 new idle均衡：new idle load balance，调度器在选择下一个任务时，发现cfs 就绪队列中没有可运行任务，只能指向idle任务，进入idle状态会触发负载均衡。 nohz idle均衡：某个cpu任务太重，而其他cpu都进入idle，这时候任务重cpu会唤醒idle的cpu进行均衡负载。 laod balance （1）找出最繁忙的调度组 （2）在最繁忙调度组范围CPU找出最繁忙的CPU （3）从最繁忙的CPU就绪队列中出队任务 （4）将出队的任务挂到当前的cpu上。 负载均衡总结 图来自窝蜗科技 PELT的缺陷： （1）算法迟钝，负载的变化需要一定的时间，在一些嵌入式场景如手机，在浏览网页等情况下，需要迅速识别重活来提高CPU频率或者迁移任务，保证手机流程型。 （2）对于睡眠或阻塞的进程，PELT还会继续计算其衰减负载，这些继续贡献的负载对于下一次唤醒没有实际用处，会推迟降低cpu频率的速度，导致功耗升高。 参考文献 1.蜗窝科技：http://www.wowotech.net/ 2.奔跑吧linux内核卷1基础架构

概述 从上一章节大概应该能够理解负载和利用率的区别了，当一个进程正在运行或者即使没有在cpu上运行，而在就绪队列中等待运行，那么他依旧消耗cpu的负载。这是合理的，因为cpu的就绪队列有10个任务等待着运行与5个任务等待运行，明显是10个任务的负载重。而利用率只是关注正在运行的任务而不包含在就绪队列的任务，在某个时间段内可能某个任务的cpu利用率很高，但是占用完之后一直睡眠，那么其队系统的负载贡献还是较小。 从CPU的层次划分，从大到小分为： NUMA: 多个SOC组成，通过UPI可以共享多块物理内存，常用于服务器。 SOC: system-on-a-chip，集成了多个系统组件或功能的芯片，对应DIE。 MC:multi-core，多核处理器，一个SOC集成多个核心，每个核心用于自己的缓存或寄存器资源，可以并行处理多个程序。 SMT:Simultaneous Multi-Threading，超线程，单个核心处理器同时执行多个线程，在单个核心处理器引入多个逻辑执行单元和资源共享极致，实现更好的指令集并发性。 现在的嵌入式处理器通常包含SOC+MC技术，也就是在一个SOC上集成了多核处理器，目前遇到的SMT和NUMA的还比较少，因此本章节先讨论一个SOC上集成MC的情况。 因为多核的出现，我们需要引入负载均衡，我们需要解决将SOC运行的任务均衡的分配到各个核上处理，但是并不能简单的平均分配任务到各个CPU上，从上图的架构来看，一个SOC上存在大小核的情况2个小核+2个大核，那自然大核的算力要高于小核的算力，同时我们还需要考虑CPU的频率，同样的架构核心高频的算力自然要高于低频的算力。除了配合各CPU的算力来均衡负载外，还需要考虑任务迁移的开销，上图CPU0上的任务迁移到CPU1上的开销会少于迁移到CPU2上，因为CPU0和CPU1共享L2 cache，如果迁移到L2上的话，cache就会失效，性能或许会减弱。基于上述这些因素，linux构建了相关的数据结构来处理这些问题，称为调度域和调度组。 系统为了便于负载均衡，构建调度域（sched domain，简记sd）和调度组(sched group，简记sg)。按照架构层级可以依次划分为不同的SOC、相同SOC不同的核心、相同的核心不同的超线程。我们把相同层级称为调度域，越往下层的调度域共用的缓存越多，因此在任务做迁移时，优先选择从底层的调度域中进行。先不考虑SMT，上图的调度域可以分为两级从下往上MC domain（multi core domain），DIE domain。 DIE domain：处于顶层，覆盖系统所有的CPU（CPU0~CPU3）。 MC domain：处于底层，也称为base domain，分为小核MC domain（cpu0~cpu1）和大核MC domain（CPU2~CPU3），小核MC domain是一个cluster，大核MC domain是一个cluster。 负载均衡调度的最小单元是调度组，每个调度域进行分组。对于MC域，基本可以按照一个cpu是一组，所以小核MC domain可以分为两组（一个CPU对应一组），大核MC domain也是分为两组。对于DIE域，每个分组要覆盖到其child domain，DIE 域有两个子domain，分别是小核MC domain，大核MC domain，因此DIE domain分为两个组对于小核group和大核group。 数据结构 Linux内核使用struct sched_domain_topology_level，简称SDTL来描述CPU的层次关系。 struct sched_domain_topology_level mask：函数指针，指定cpumask位图 sd_flags：函数指针，指定标志位 flags:进一步描述和设置调度域 numa_level:NUMA层级，确定该层级为NUMA的那一层 data:调度域数据结构，存储关于调度域的统计信息 name:调度域名称 以下是内核默认定义了一个层次结构，DIE是默认打开，MC和SMT是可选的。 static struct sched_domain_topology_level default_topology[] = { #ifdef CONFIG_SCHED_SMT { cpu_smt_mask, cpu_smt_flags, SD_INIT_NAME(SMT) }, #endif #ifdef CONFIG_SCHED_MC { cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) }, #endif { cpu_cpu_mask, SD_INIT_NAME(DIE) }, { NULL, }, }; static struct sched_domain_topology_level *sched_domain_topology = default_topology; struct sd_data,该结构体中成员都使用percpu来修饰，用于指示该指针是一个per-CPU变量，告诉编译器将变量的内存分配为每个CPU分别保留的独立内存块，如struct sched *__percpu *sd是指向struct sched_domain类型的per-CPU变量，也就是其指向的是一个数组（有cpu个数元素），数组的每个元素是指向一个struct sched_domain类型的指针，每个指针与一个特定的CPU相关联，分配数组是使用alloc_percpu来实现，该函数会分配一个具有相同大小的块，并为每个cpu都分配一个指针。 sd = alloc_percpu(struct sched_domain *)，则sd分配了per-CPU变量的内存空间，这意味着每个CPU都有自己独立的struct sched_domain指针变量，当给其每个CPU的指针变量赋值后，后续可以通过sd[cpu]来cpu上的struct sched_domain变量。 sd[]: 描述CPU的调度域，实际是一个指针数组，每个数组元素指针指向cpu所属的调度域，下同。 sds[]:存储调度域共享数据，用于描述多个CPU共享的调度域。 sg[]:每个cpu都有一个指向调度组的指针，用于描述CPU所属的调度组 sgc[]:调度组的容量信息，用于描述调度组的资源容量。 在系统中，为了避免多核之间的互斥访问影响性能，调度域sched_domain数据结构采用Per-CPU的变量来构建，每个CPU都维护一个调度域数据结构。 struct sched_domain_shared，为了降低锁竞争，sd是per-cpu的，但是有一些信息需要在per-cpu上的sd之间共享，不能在每个sd上构建，这些共享的信息就存储在sds上。 nr_busy_cpus:该sd中忙的cpu个数。 has_idle_cores:该sd中是否有idle cpu。 struct sched_group_capacity capacity: min/max_capacity: next_update: imbalance: cpumask[] struct sched_domain parent和child:调度域会形成层次结构，parent和child建立了不同层级的父子关系。对于base domain而言，其child=NULL，对于顶层domain而言，parent=NULL。 groups:一个调度域中有若干调度组，这些调到组形成一个环形的链表，groups成员就是链表头。 flags:调度域的标志，SD_BALANCE_NEWIDLE是否支持newidle balance，SD_SHARE_PKG_RESOURCES是否共享cache等资源。 span[]:调度域中cpu 核形成的cpu mask，即调度域覆盖的cpu核范围，当前调度域可使用那几个cpu核。 struct sched_group next: 调度域中的所有group都会形成一个链表，next指向下一个group。 ref:该调度组被应用的次数。 group_weight:调度组中有多少个cpu。 sgc:调度组的算力信息。 cpumask:调度组包括那些cpu。 include/linux/cpumask.h struct cpumask { DECLARE_BITMAP(bits, NR_CPUS); //unsigned long bits[1]； } //NR_CPUS为核心数，以8核，64位系统计算为例。 #define DECLARE_BITMAP(name,bits) \\ unsigned long name[BITS_TO_LONGS(bits)] #define BITS_TO_LONGS(nr) __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(long)) #define __KERNEL_DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d)) #define BITS_PER_TYPE(type) (sizeof(type) * BITS_PER_BYTE) #define BITS_PER_BYTE 8 (((n) + (d) - 1) / (d)) = (((8) + (64) - 1) / (64)) = 1 struct s_data { struct sched_domain * __percpu *sd; struct root_domain *rd; }; CPU拓扑结构 Linux内核中，通过读取dts文件，建立Topology。 cpus { #address-cells = <0x02>; #size-cells = <0x00>; cpu@0 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x00>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x39a>; clocks = <0x04 0x01>; operating-points-v2 = <0x05>; #cooling-cells = <0x02>; dynamic-power-coefficient = <0x11e>; cpu-supply = <0x06>; phandle = <0x09>; }; cpu@100 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x100>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x39a>; clocks = <0x04 0x01>; operating-points-v2 = <0x05>; #cooling-cells = <0x02>; phandle = <0x0a>; }; cpu@200 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x200>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x39a>; clocks = <0x04 0x01>; operating-points-v2 = <0x05>; #cooling-cells = <0x02>; phandle = <0x0b>; }; cpu@300 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x300>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x39a>; clocks = <0x04 0x01>; operating-points-v2 = <0x05>; #cooling-cells = <0x02>; phandle = <0x0c>; }; cpu@400 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x400>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x400>; clocks = <0x04 0x03>; operating-points-v2 = <0x07>; #cooling-cells = <0x02>; dynamic-power-coefficient = <0x162>; cpu-supply = <0x08>; phandle = <0x0d>; }; cpu@500 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x500>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x400>; clocks = <0x04 0x03>; operating-points-v2 = <0x07>; #cooling-cells = <0x02>; phandle = <0x0e>; }; cpu@600 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x600>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x400>; clocks = <0x04 0x03>; operating-points-v2 = <0x07>; #cooling-cells = <0x02>; phandle = <0x0f>; }; cpu@700 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x700>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x400>; clocks = <0x04 0x03>; operating-points-v2 = <0x07>; #cooling-cells = <0x02>; phandle = <0x10>; }; cpu-map { cluster0 { core0 { cpu = <0x09>; }; core1 { cpu = <0x0a>; }; core2 { cpu = <0x0b>; }; core3 { cpu = <0x0c>; }; }; cluster1 { core0 { cpu = <0x0d>; }; core1 { cpu = <0x0e>; }; core2 { cpu = <0x0f>; }; core3 { cpu = <0x10>; }; }; }; } 上面的dts描述，soc中有8个核心，分为两个cluster，cpu0~cpu3，cpu4~cpu7，因此调度域可以这样划分。 DIE: cpu 0~7 MC: cpu 0~3一组，cpu4~7一组。 可以通过 /sys/devices/system/cpu/cpuX/topology节点来获取topology相关信息。 root@TinaLinux:/sys/devices/system/cpu/cpu0/topology# cat * 01 //core_cpus 0 //core_cpus_list 0 //core_id 0f //core_siblings 0-3 //core_siblings_list 01 //die_cpus 0 //die_cpus_list -1 //die_id 0f //package_cpus 0-3 //package_cpus_list 0 //physical_package_id 01 //thread_siblings 0 //thread_siblings_list root@TinaLinux:/sys/devices/system/cpu/cpu6/topology# cat * 40 //core_cpus 6 //core_cpus_list 2 //core_id f0 //core_siblings 4-7 //core_siblings_list 40 //die_cpus 6 //die_cpus_list -1 //die_id f0 //package_cpus 4-7 //package_cpus_list 1 //physical_package_id 40 //thread_siblings 7 //thread_siblings_list 在后续章节中，我们都以当前的拓扑结构举例来说明。 创建sd和sg CPU MASK #define cpu_possible_mask ((const struct cpumask *)&__cpu_possible_mask) //系统中有多少个CPU核可以运行 #define cpu_online_mask ((const struct cpumask *)&__cpu_online_mask) //系统中有多少个CPU核正在运行 #define cpu_present_mask ((const struct cpumask *)&__cpu_present_mask) //系统中有多少个正处于运行状态的CPU核。 #define cpu_active_mask ((const struct cpumask *)&__cpu_active_mask) //系统中有多少个活跃的CPU核 #define cpu_dying_mask ((const struct cpumask *)&__cpu_dying_mask) //系统中有多少个将死的cpu核 如果没有CONFIG_HOTPULG_CPU，那么present=possible，active = online。 int sched_init_domains(const struct cpumask *cpu_map) { int err; zalloc_cpumask_var(&sched_domains_tmpmask, GFP_KERNEL); zalloc_cpumask_var(&sched_domains_tmpmask2, GFP_KERNEL); zalloc_cpumask_var(&fallback_doms, GFP_KERNEL); arch_update_cpu_topology(); asym_cpu_capacity_scan(); ndoms_cur = 1; doms_cur = alloc_sched_domains(ndoms_cur); //创建cpumask_var_t类型，存储用于当前调度域的可用的cpu。 if (!doms_cur) doms_cur = &fallback_doms; cpumask_and(doms_cur[0], cpu_map, housekeeping_cpumask(HK_FLAG_DOMAIN)); //cpu_map为cpu_active_mask，在active中排除掉不能用于调度域的cpu，isolcpus对某些//cpu进行的隔离，不参与调度域中，doms_cur最终保存的排除之后可用调度域的cpu。 err = build_sched_domains(doms_cur[0], NULL); //调度域建立。 return err; } 为DIE和MC分配每CPU的sd/sdc/sg/sgc空间 static int build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr) { enum s_alloc alloc_state = sa_none; struct sched_domain *sd; struct s_data d; ...... //分配DIE,MC SDTL拓扑相关数据结构，初始化一个struct s_data； alloc_state = __visit_domain_allocation_hell(&d, cpu_map); ...... } build_shed_domains函数中首先调用__visit_domain_allocation_hell为每个cpu分配各个调度域层级（DIE/MC）分配sd/sdc/sg/sgc。 struct sched_domain_topology_level { sched_domain_mask_f mask; sched_domain_flags_f sd_flags; int flags; int numa_level; struct sd_data data; #ifdef CONFIG_SCHED_DEBUG char *name; #endif }; //定义了一个static struct sched_domain_topology_level default_topology[]全局变量。 static struct sched_domain_topology_level default_topology[] = { #ifdef CONFIG_SCHED_SMT { cpu_smt_mask, cpu_smt_flags, SD_INIT_NAME(SMT) }, #endif #ifdef CONFIG_SCHED_MC { cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) }, #endif { cpu_cpu_mask, SD_INIT_NAME(DIE) }, { NULL, }, }; 内核定义了一个全局变量static struct sched_domain_topology_level default_topology[]，该变量根据宏配置调度域的层次，DIE调度域是默认开启的，往下是MC调度域，再到SMT调度域，由于ARM架构SMT调度目前见得还比较少，所以再不考虑，build_shed_domains得核心就是各层级得SDTL。 static enum s_alloc __visit_domain_allocation_hell(struct s_data *d, const struct cpumask *cpu_map) { memset(d, 0, sizeof(*d)); //为全局struct sched_domain_topology_level default_topology[]的DIE和MC分配对应的 //per-CPU sd/sds/sg/sgc if (__sdt_alloc(cpu_map)) return sa_sd_storage; //为每个CPU分配了一个调度域，作用是用户存储最底层（MC）的sd，也就是每个CPU 的 //d->sd指向MC的sd，这只是临时分配，用于在建立sg的时候辅助使用，后续会销毁。 d->sd = alloc_percpu(struct sched_domain *); if (!d->sd) return sa_sd_storage; //分配一个rootdomain并进行初始化，主要用于rt的？ d->rd = alloc_rootdomain(); if (!d->rd) return sa_sd; return sa_rootdomain; } __visist_domain_allocation_hell调用__sdt_alloc，分配SDTL中的struct sd_data data并进行初始化。 struct sd_data { struct sched_domain *__percpu *sd; struct sched_domain_shared *__percpu *sds; struct sched_group *__percpu *sg; struct sched_group_capacity *__percpu *sgc; }; sd_data的成员都是__percpu类型，需要先调用alloc_percpu分配相同大小的cpu个数区域，这些区域存储的是指针，指向每个cpu对应的sd/sds/sg/sgc，以struct sched_domain *__percpu *sd为例，sdd->sd = alloc_percpu(struct sched_domain *)分配一块指针数组，数组元素的个数为cpu核个数，sd指向这个指针数组，数组中的指针用于后续每个CPU指向分配的sd空间。 static int __sdt_alloc(const struct cpumask *cpu_map) { struct sched_domain_topology_level *tl; int j; //遍历SDTL，这里有MC和DIE。 for_each_sd_topology(tl) { struct sd_data *sdd = &tl->data; //分配当前层级调度域sd Per-CPU变量（指针数组，数组元素为cpu个数指针，下同） sdd->sd = alloc_percpu(struct sched_domain *); if (!sdd->sd) return -ENOMEM; //分配当前层级sdc Per-CPU变量 sdd->sds = alloc_percpu(struct sched_domain_shared *); if (!sdd->sds) return -ENOMEM; //分配当前层级sg Per-CPU变量 sdd->sg = alloc_percpu(struct sched_group *); if (!sdd->sg) return -ENOMEM; //分配当前层级sgc Per-CPU变量 sdd->sgc = alloc_percpu(struct sched_group_capacity *); if (!sdd->sgc) return -ENOMEM; //上面已经完成当前层级Per-CPU变量，下面就遍历每个cpu分配sd/sds/sg/sgc，Per-CPU //遍历将一一对应指向。 for_each_cpu(j, cpu_map) { struct sched_domain *sd; struct sched_domain_shared *sds; struct sched_group *sg; struct sched_group_capacity *sgc; sd = kzalloc_node(sizeof(struct sched_domain) + cpumask_size(), GFP_KERNEL, cpu_to_node(j)); if (!sd) return -ENOMEM; *per_cpu_ptr(sdd->sd, j) = sd; //如对应cpu0来说，sdd-sd[0] = sd,sdd-sd[0]是一个指针，指向当前分配的sd空间。 sds = kzalloc_node(sizeof(struct sched_domain_shared), GFP_KERNEL, cpu_to_node(j)); if (!sds) return -ENOMEM; *per_cpu_ptr(sdd->sds, j) = sds; sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(), GFP_KERNEL, cpu_to_node(j)); if (!sg) return -ENOMEM; sg->next = sg; *per_cpu_ptr(sdd->sg, j) = sg; sgc = kzalloc_node(sizeof(struct sched_group_capacity) + cpumask_size(), GFP_KERNEL, cpu_to_node(j)); if (!sgc) return -ENOMEM; *per_cpu_ptr(sdd->sgc, j) = sgc; } } return 0; } 执行完__sdt_alloc，层次结构就如下所示，如对应DIE层次，sdd-sd[0~7]分别指向各自cpu分配的sd区域。 初始化调度域sd static int build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr) { enum s_alloc alloc_state = sa_none; struct sched_domain *sd; struct s_data d; struct rq *rq = NULL; int i, ret = -ENOMEM; bool has_asym = false; ........ //遍历每个CPU，从下往上初始化SDTL的sd，先初始化MC再初始化DIE。 // DIE的sd 其child指向MC的sd，MC的sd 其parent指向DIE的sd。 for_each_cpu(i, cpu_map) { struct sched_domain_topology_level *tl; sd = NULL; for_each_sd_topology(tl) { if (WARN_ON(!topology_span_sane(tl, cpu_map, i))) goto error; //初始化调度域 sd = build_sched_domain(tl, cpu_map, attr, sd, i); has_asym |= sd->flags & SD_ASYM_CPUCAPACITY; if (tl == sched_domain_topology) *per_cpu_ptr(d.sd, i) = sd; //将最低层级的sd保存到s_data.sd的per_cpu变量中，最底层为MC level的sd //为下一步建立sg做准备。 if (tl->flags & SDTL_OVERLAP) sd->flags |= SD_OVERLAP; if (cpumask_equal(cpu_map, sched_domain_span(sd))) break; //sched_domain_span(sd)用于获取给定调度域sd的范围cpu，也就是说当前调度域 //中覆盖的cpu是那几个。 //调度域都有一个范围，表示该调度域可以管理的CPU范围，这个范围通常有一 //个cpumask表示，其中每个位都对应一个cpu，调度域的范围定义了该调度域影//响的cpu集合。 } } ........ } for_each_cpu遍历每一个cpu，接着for_each_sd_topology(tl)对每个cpu从最底层依次往上构建调度域，先构建MC再DIE。build_sched_domain中会调用sd_init对调度域进行初始化，主要是struct sched_domain结构体成员赋值，同时建立起MC与DIE层级sd的父子联系，如下对于DIE层级，每cpu的sd.child指向MC层级的sd，而MC层级sd.parent指向DIE层级的sd。在初始化调度域是会设置其span，span为调度域作用的cpu范围，实际是根据span的作用范围来对当前调度域层级进行分组。如MC层级，按照4.2.1.2的拓扑结构，有两个MC调度域名，CPU0~CPU3是一组，所以CPU0~CPU3的sd->span是相同的，CPU4~CPU7是一组，所以CPU4~CPU7的sd->span相同的。sd->span非常重要，在后续章节中也会使用该信息来建立sg之间的联系。 初始化调度组sg static int build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr) { enum s_alloc alloc_state = sa_none; struct sched_domain *sd; struct s_data d; struct rq *rq = NULL; int i, ret = -ENOMEM; bool has_asym = false; ........ /* Build the groups for the domains */ for_each_cpu(i, cpu_map) { //d.sd是最底层得调度域，这里是MC，即每cpu的sd for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) { sd->span_weight = cpumask_weight(sched_domain_span(sd)); if (sd->flags & SD_OVERLAP) { if (build_overlap_sched_groups(sd, i)) goto error; } else { if (build_sched_groups(sd, i)) goto error; } } } ........ } for_each_cpu遍历每个cpu，for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent)遍历当前cpu的调度域，从MC调度域往上开始，调用build_sched_groups构建当前调度域的调度组。 static int build_sched_groups(struct sched_domain *sd, int cpu) { struct sched_group *first = NULL, *last = NULL; struct sd_data *sdd = sd->private; const struct cpumask *span = sched_domain_span(sd); //获取当前调度域的cpu作用范围，对于DIE层级，span是cpu0~cpu7而对于MC层级 //span是core_siblings，即cpu0~cpu3或cpu4~cpu7。 struct cpumask *covered; int i; lockdep_assert_held(&sched_domains_mutex); covered = sched_domains_tmpmask; cpumask_clear(covered); //从当前cpu开始遍历整个sd span。 for_each_cpu_wrap(i, span, cpu) { struct sched_group *sg; if (cpumask_test_cpu(i, covered)) //已经在coverd msk中的cpu，继续执行，与下面的cpumask_or配合，避免重复指向。 continue; //获取cpu i的调度组sg sg = get_group(i, sdd); cpumask_or(covered, covered, sched_group_span(sg)); //coverd = coverd | sched_group_span(sg) if (!first) first = sg;//每个cpu进来的第一个sg if (last) last->next = sg;//每个sg的下一个sg last = sg; } last->next = first; //最后一个sg再指向第一个sg，就形成环形链表了。 sd->groups = first; //sd->groups指向第一个sg，对于MC是自己的sg return 0; } 在MC调度域层级，根据调度域sd->span定义的cpu范围内的sg形成环形链表，下面就是两个环形链表，对应的就是MC调度域层级的两个调度域实体。 在DIE区域，sg取的是子调度域所在的第一个cpu，即cpu0所在的sg和cpu4所在的sg。 static struct sched_group *get_group(int cpu, struct sd_data *sdd) { struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu); struct sched_domain *child = sd->child; struct sched_group *sg; bool already_visited; if (child) cpu = cpumask_first(sched_domain_span(child)); //如果调度域存在子调度域，则cpu获取子调度域的第一个cpu，只有DIE层级才有子调度//域，所以这里是cpu0或cpu4 sg = *per_cpu_ptr(sdd->sg, cpu); //获取当前层级cpu上的sg sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);//获取当前层级cpu上的sgc，将sg->sgc指向sgc /* Increase refcounts for claim_allocations: */ already_visited = atomic_inc_return(&sg->ref) > 1; /* sgc visits should follow a similar trend as sg */ WARN_ON(already_visited != (atomic_inc_return(&sg->sgc->ref) > 1)); /* If we have already visited that group, it\'s already initialized. */ if (already_visited) return sg; //如果是DIE层级 if (child) { cpumask_copy(sched_group_span(sg), sched_domain_span(child)); //将子调度域的cpu范围赋值到调度组sg的cpu范围，子sd->span = 父sg->cpumask cpumask_copy(group_balance_mask(sg), sched_group_span(sg)); //将调度组sg的cpu范围赋值到sg的平衡掩码balance mask } else { cpumask_set_cpu(cpu, sched_group_span(sg)); //将cpu添加到调度组sg的cpu范围中 cpumask_set_cpu(cpu, group_balance_mask(sg)); //将cpu添加到调度组sg平衡掩码中 } sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sched_group_span(sg)); //计算调度组能力。 sg->sgc->min_capacity = SCHED_CAPACITY_SCALE; sg->sgc->max_capacity = SCHED_CAPACITY_SCALE; return sg; } MC层级基本是一个cpu对应一个调度组sg，而对于DIE层级一个cluster对应一个调度组，调度组表示一般选择每个cluster的第一个cpu，该sg代表的不是一个cpu，而是整个cluster上的cpu，所以cpu上的sg->cpumask为子调度域的sd->span。 构建调度组能力sgc static int build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr) { ...... /* Calculate CPU capacity for physical packages and nodes */ //遍历每个CPU，从大到小开始遍历，然后依次遍历MC到DIE，初始化sg的cpu_capacity for (i = nr_cpumask_bits-1; i >= 0; i--) { if (!cpumask_test_cpu(i, cpu_map)) continue; //还是从底层MC开始往上遍历，初始化sgc for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) { claim_allocations(i, sd); init_sched_groups_capacity(i, sd); } } ...... } 遍历每个cpu，然后从MC层级往上到DIE层级，初始化每cpu各层级的sgc。 static void init_sched_groups_capacity(int cpu, struct sched_domain *sd) { struct sched_group *sg = sd->groups; WARN_ON(!sg); //循环，对sg环形链表中所有的sg->group_weight进行初始化。 do { int cpu, max_cpu = -1; sg->group_weight = cpumask_weight(sched_group_span(sg)); if (!(sd->flags & SD_ASYM_PACKING)) goto next; for_each_cpu(cpu, sched_group_span(sg)) { if (max_cpu < 0) max_cpu = cpu; else if (sched_asym_prefer(cpu, max_cpu)) max_cpu = cpu; } sg->asym_prefer_cpu = max_cpu; next: sg = sg->next; } while (sg != sd->groups); if (cpu != group_balance_cpu(sg)) return; update_group_capacity(sd, cpu); //更新group 的capacity。 } 将每cpu的MC层级sd、rootdomain与cpu rq绑定 static int build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr) { ...... //遍历每个cpu，获取最底层的调度域MC，将其与d.rd以及cpu rq绑定起来 for_each_cpu(i, cpu_map) { rq = cpu_rq(i); sd = *per_cpu_ptr(d.sd, i); /* Use READ_ONCE()/WRITE_ONCE() to avoid load/store tearing: */ if (rq->cpu_capacity_orig > READ_ONCE(d.rd->max_cpu_capacity)) WRITE_ONCE(d.rd->max_cpu_capacity, rq->cpu_capacity_orig); cpu_attach_domain(sd, d.rd, i); } ...... } for_each_cpu遍历所有cpu，sd = *per_cpu_ptr(d.sd, i)获取的是MC层级的调度域，最后调用cpu_attach_domain进行绑定。 static void cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu) { ...... sched_domain_debug(sd, cpu); rq_attach_root(rq, rd); // 将新的root domain与cpu rq绑定，rd->rd = rd。 tmp = rq->sd; rcu_assign_pointer(rq->sd, sd); //将新的sd与rd->sd 绑定 dirty_sched_domain_sysctl(cpu); destroy_sched_domains(tmp); update_top_cache_domain(cpu); } 将每个cpu的MC层级的调度域sd赋值给当前cpu调度队列的rq->sd，将root domain 赋值为当前cpu调度队列的rq->rd。 总结： 根据CPU架构的层次，从下到上，分为MC层级->DIE层级，每个层级使用struct sched_domain_topology_levels（SDTL）数据结构描述。 考虑多核的锁竞争访问，每层级SDTL为每个cpu定义了sd/sds/sg/sgc数据结构。 在同一层级（如MC层级）由SOC架构（DTS描述）来确定那些是兄弟关系(core_siblings)，兄弟关系在调度域sd中使用sd->span来描述，在调度组中sg中使用sg->cpumask来描述，属于兄弟关系的cpu核属于一个调度域。DIE层级的sg->cpumask = MC层级sd->span。 对于MC层级来说每个cpu就是一个调度组sg，兄弟关系的sg归属为一个调度域，该调度域的sg形成一个环形链表，但不同cpu指向的环形链表首元素是不同的，首元素指向的都是自己cpu所在的sg，如cpu0的链表顺序是(0,1,2,3)，cpu1的链表顺序是(1,2,3,0)。 对于DIE层级来说每个cluster是一个调度组，每个调度组有多个cpu，调度组覆盖的cpu范围子调度域的cpu覆盖范围，也可以认为是每个cluster的cpu范围。同时调度组选取的是子调度域cpu范围的第一顺序cpu作为调度组，也可以认为是每个cluster的第一个cpu。 对于DIE层其每cpu的调度域sd.child指向下一级MC层每cpu调度域sd，而MC层其每cpu调度域sd.parent指向上一级DIE层每cpu调度域sd。 负载均衡时会优先从最底层级进行均衡，从下往上意味着可选择的cpu会越来越多，但是均衡的代价也会越来越大。

各任务负载、各cpu的算力（频率+架构）、任务迁移开销（调度域，调度组）。 root@Linux:/# cat /proc/loadavg 3.49 3.43 3.54 4/131 3065 cat /proc/loadavg可以获取CPU全局平均负载，前面的三个值分别表示为1分钟、5分钟、15分钟系统平均负载，第四个字段正在运行的进程数量/总进程数量，第五个字段最后一个运行的进程ID。 公式①：CPU负载=就绪队列总权重 早期系统计算系统负载是所有CPU上就绪队列的总权重，但是使用权重来计算是比较局限的，因为负载考虑的是对CPU资源占用情况，而权重高的进程可能并不一定会一直运行，或许运行一会就一直睡眠，因此使用就绪队列的总权重并不合理。 在权重的基础上进行演化，从全局考虑整体就绪队列到追踪每一个调度实体对CPU资源的占用，从而调度器有更精细的控制。在一段时间内，将每个任务可运行时间考虑进去（可运行表示处于就绪队列中，但并不是在执行），这样就能够代表任务对CPU的资源占用情况。 公式②：load = weight * t /T 采样一段时间T，任务处于运行状态时间为t,该任务对CPU的负载可运行时间与采样时间的比值再与权重相乘。 公式②看起来是比较合理，但是仍然存在问题，考虑一些场景，假设相同优先级A任务和B任务在某天同一时刻启动，A任务运行了半天就一直睡眠，而B任务一启动就睡眠半天，然后一直运行。按照公式②的计算A和B的负载是一样的，显然不合理，在最近的这段时间内任务B的负载要高于A，因此基于公式再进行了演化，加入历史运行情况的参数。 公式③：load = weight * (t0*y^0+ t1*y^1 + t2*y^2+...+tn*y^n)/T 负载计算将历史运行因素考虑进去，但是历史因素的因素有一个衰减（decay）过程，也就是说离当前最近的影响最大，离当前时间越远影响程度越小，所以衰减因子y^32=0.5。为了便于系统计算对公式在进行了量化，采样周期为1ms，所以公式为 公式④L = L0 + L1*y^1 + L2*y^2 + L3* y^3 +.... Ln*y^n。 下面是描述调度实体或就绪队列的负载信息。 struct sched_avg { u64 last_update_time; u64 load_sum; u64 runnable_sum; u32 util_sum; u32 period_contrib; unsigned long load_avg; unsigned long runnable_avg; unsigned long util_avg; struct util_est util_est; } ____cacheline_aligned; last_update_time: 上次更新负载信息的时间点，可用于计算差值。 load_sum：调度实体来说是任务累计历史衰减总时间,包括running+runnable+blocked，对于调度队列来说是其所有任务累计工作总负载，前者统计的仅仅是时间，后者是工作负载即时间乘权重。 runnable_sum: 调度实体来说是running+runnable累计历史衰减总时间， util_sum:调度实体来说正在运行状态下的累计衰减总时间，调度队列来说其所有正在运行任务的总时间。 period_contrib: 存放着上一次时间采样时，不能凑成一个周期的剩余时间。 _avg/util_avg:根据_sum计算得到的负载均值。 util_est:辅助计算阻塞之前load avg信息。 上面是struct cfs_rq/struct sched_entity 与struct sched_avg之间的关系，也就是说在计算负载时有调度实体的负载和就绪队列的负载。 /* * sched_entity: * * task: * se_weight() = se->load.weight * se_runnable() = !!on_rq * * group: [ see update_cfs_group() ] * se_weight() = tg->weight * grq->load_avg / tg->load_avg * se_runnable() = grq->h_nr_running * * runnable_sum = se_runnable() * runnable = grq->runnable_sum * runnable_avg = runnable_sum * * load_sum := runnable * load_avg = se_weight(se) * load_sum * * cfq_rq: * * runnable_sum = \\Sum se->avg.runnable_sum * runnable_avg = \\Sum se->avg.runnable_avg * * load_sum = \\Sum se_weight(se) * se->avg.load_sum * load_avg = \\Sum se->avg.load_avg */ PELT基本原理 公式④L = L0 + L1*y^1 + L2*y^2 + L3* y^3 +.... Ln*y^n。 在计算负载时，计算时刻并不能这么精确，这次计算的时间距离上一次计算负载的时间跨越了多个周期，如上图所示，last_update_time时刻表示上一次计算负载，而这次计算的负载为now时刻。时间可以分为3段d1、d2、d3，之所以这样划分当前计算时刻与上一次计算负载的时刻并不一定落在周期点。假设last_update_time时刻的计算出来的负载为，根据划分的3段，因此系统的负载计算为：Llast，先不考虑权重，那么当前时刻负载为： 从这个公式来看，负载的计算可以分为3段。 val*y^p计算 先来看(d1+ Llast) * y^p 中代码的实现，由于y^p 的值是浮点，为了避免浮点运算可以转化为y^p = y^p * 2^32 >> 32，相当于先乘以2^32 再右移32（右移就是除），而y^p * 2^32 再系统中提前计算好了存放再数组runable_avg_yN_inv中，如下： static const u32 runnable_avg_yN_inv[] __maybe_unused = { 0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6, 0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85, 0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581, 0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9, 0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80, 0x85aac367, 0x82cd8698, }; //计算val * y^n，y^32 = 0.5。 static u64 decay_load(u64 val, u64 n) { unsigned int local_n; //经过LOAD_AVG_PERIOD * 63周期后，就衰减为0了 if (unlikely(n > LOAD_AVG_PERIOD * 63)) return 0; /* after bounds checking we can collapse to 32-bit */ local_n = n; //如果衰减周期大于32，则计算方式有调整如下，反之直接查表， //val * y^p =val * (y^32)^(p/32) * y^(p%32) * 2^32 >>32, p=p/32 + p%32, //而y^32=1/2,所以val * (y^32)^(p/32) =val >> (p/32), //y^(p%32) * 2^32 就先计算p%32，然后从runnable_avg_yN_inv表中查询。 if (unlikely(local_n >= LOAD_AVG_PERIOD)) { val >>= local_n / LOAD_AVG_PERIOD; //val * (y^32)^(p/32) =val >> (p/32) local_n %= LOAD_AVG_PERIOD; //p%32,便于从runnable_avg_yN_inv查询 } val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32); //val * runnable_avg_yN_inv[local_n] >> 32 return val; } 1024*(y^1 + y^2 +......+ y^p-1)计算 由等比求和公式 y^p + y^p+1 + y^P+2 +......+ y^p+n=(y^p-y^p+n+1)/(1-y), 得 y^1 + y^2 + y^3 +......+ y^p-1 =( y^1-y^p) / (1-y) =( 1-y^p) / (1-y) - (1-y)/(1-y)=( 1-y^p) / (1-y)-1 因为0<y<1，所以当趋于0（体验下什么叫做0.99^n和1.11^n），所以上面的公式再次简化为如下： 代码实现 Lnow =d3 + 1024*(y^1 + y^2 + y^3 +......+ y^p-1) + (d1+ Llast) * y^p = Llast * y^p（step1）+ [d1 * y^p + LOAD_AVG_MAX - *LOAD_AVG_MAX - 1024 + d3]（step2） accumulate_sum是计算负载的核心函数，计算的负载结果并不是会增加而有可能是减少，负载的变化都在这个函数中实现，当调度实体没有在就绪队列时，随着时间的增加其对CPU的负载会逐渐减弱，而如果调度实体在就绪队列时，对CPU的负载就会逐渐增加。 static __always_inline u32 accumulate_sum(u64 delta, struct sched_avg *sa, unsigned long load, unsigned long runnable, int running) { u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */ u64 periods; // sa->period_contrib是上次更新负载不足1024us周期的时间，delta是上次更新负载到现在要计算负载经过的时间，要计算有多少个周期需要加上period_contrib，见4.1.1的图。 delta += sa->period_contrib; periods = delta / 1024; /* A period is 1024us (~1ms) */ /* * Step 1: decay old *_sum if we crossed period boundaries. */ if (periods) { //step1: 分别计算 Llast * y^p，历史负载的衰减 sa->load_sum = decay_load(sa->load_sum, periods); sa->runnable_sum = decay_load(sa->runnable_sum, periods); sa->util_sum = decay_load((u64)(sa->util_sum), periods); /* * Step 2 */ delta %= 1024; //当load=0时，说明当前的调度实体不处于running或runnable，因此不需要计算新增负载负载贡献，而只计算负载衰减，过了一段时间周期，一直没得到运行，累计的负载衰减step1的操作就是衰减。 //step2: 计算[d1 * y^p + LOAD_AVG_MAX - *LOAD_AVG_MAX - 1024 +d3]，period即P。 //当load !=0，说明调度实体处于running或runnable，就需要计算增加的负载贡献。 if (load) { //d1= 1024 - sa->period_contrib, d3=delta % 1024。 contrib = __accumulate_pelt_segments(periods, 1024 - sa->period_contrib, delta); } } //更新不足一个周期贡献值 sa->period_contrib = delta; if (load) sa->load_sum += load * contrib; if (runnable) sa->runnable_sum += runnable * contrib << SCHED_CAPACITY_SHIFT; if (running) sa->util_sum += contrib << SCHED_CAPACITY_SHIFT; return periods; } static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3) { u32 c1, c2, c3 = d3; /* y^0 == 1 */ c1 = decay_load((u64)d1, periods); //计算d1 * y^p c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024; //计算LOAD_AVG_MAX - *LOAD_AVG_MAX - 1024 return c1 + c2 + c3; } 负载更新 负载使用的是struct sched结构体来进行描述，负载的描述对象分为调度实体se负载（包含group se和task se）和调度实体所在的就绪队列cfs_rq负载。cfs_rq的负载可以先简单的理解为是其队列中所有调度实体se的贡献，当然不能简单是相加关系，需要考虑权重、cpu算力等因素，顶层的cfs_rq负载实际就等于CPU的负载。 追踪调度实体se的负载是基础，当调度实体se的负载变化时进而也会影响到其所在cfs_rq队列的负载变化，cfs_rq.load = f(se.load)，负载更新的核心函数使用update_load_avg来实现，因此本小结主要就是围绕该函数进行解读。 负载的更新实际是基于某个时间刻进行计算，对于一个调度实体来说其有不同的运行状态，每个状态对CPU的负载计算是不相同的。 - 当一个任务处于running（正在运行）或runnable（就绪队列中）时，那么对系统的负载计算是贡献的，因此负载需要在原来的基础上（上一个时刻的负载衰减值）加上当前新增的贡献负载，也就是说任务处于就绪队列或者正在运行对于CPU来说就是有负荷的。 - 当一个任务没有正运行或没有处于就绪队列中如处于睡眠态，那么也要考虑其任务的历史负载，睡眠的任务必然是此前运行过因为得不到某个资源而从就绪队列中移除，而该任务此前的任务负载也需要考虑进去，只不过会随着时间的增加，任务的负载会不断的衰减，最终趋于0（要是中间没有再次运行）。 如下图负载更新可以分为四部分，触发负载更新，更新task和所属cfs_rq平均负载，负载、运行负载、利用率计算，group se负载传播，本章节会按这四个部分依次展开。 触发负载更新 en/dequeue_task_fair：任务被唤醒/睡眠、CPU/Cgroup迁移、任务调度参数变化等会导致任务出入队变化就会触发负载更新。 set_next_entity：进程切换设置下一个要运行的任务。 put_prev_entity：进程切换将被抢占的任务重新放入队列。 entity_tick：周期性的tick触发。 __sched_group_set_shares：修改task group的调度参数。 de/attach_entity_cfs_rq:唤醒新创建任务、非CFS调度类切换CFS调度类等，cfs_rq在cgroup的迁移等等。 上面列出了一部分场景会触发负载更新，如任务的出入队列、设置下一个要运行的任务、被抢占的任务重新入队、周期性调度更新等，下面以几个场景来进行说明。 （1）任务入队enqueue_task_fair->enqueue_entity。 static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) { ...... for_each_sched_entity(se) { ... if (se->on_rq) break; enqueue_entity(cfs_rq, se, flags); ... } //se入队所属cfs_rq，并向上遍历直到对应的组调度实体被加入到cfs_rq为止（se要调度，//其父实体也必须入队），enqueue_entity中会更新一次负载，见下，此次的负载更新主要//负责从下到上对应的父调度实体加入到就绪队列为止，再往上就调用下面的code来进行//更新了，如下图示例只更新到cfs_rq2层级权重。 for_each_sched_entity(se) { update_load_avg(cfs_rq, se, UPDATE_TG); se_update_runnable(se); //更新se所属cfs_rq上的任务数量，负载跟该值也有关系。 update_cfs_group(se); } //这里就是补全了再往上层级剩余部分se和cfs_rq负载信息，如下如更新cfs_rq1+cfs_rq0 //权重 .... } static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { ...... update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH); //更新load avg多传递了一个DO_ATTACH的flag，当一个任务从一个队列迁移到一个新队 //列，那么PELT的层级结构发生了变化，这时候需要负载的传播过程。 se_update_runnable(se); update_cfs_group(se); account_entity_enqueue(cfs_rq, se); .... } 当调度实体se入队时，自然调度实体se的负载是要更新的，又因为se所属的cfs_rq是其下所有se的负载和，所以当其他se变化时，那么cfs_rq的负载也需要做对应的更新，所以可以在update_load_avg函数中可以看到会先更新se再更新se所属的cfs_rq。而在一个cpu的调度队列中，由于组调度的引入，会有多个层级的情况，因此当最底层的se变化时，对应的cfs_rq变化继而在影响上一层级gse变化，再影响ges所属cfs_rq的变化直到最顶层。简而言之，最底层的se和cfs_rq负载变化会导致上一层的se（gse）和cfs_rq负载也随之变化，直至顶层的cfs_rq。 （2）任务出队dequeue_task_fair->dequeue_entity。 这是入队的逆过程， static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags) { ...... for_each_sched_entity(se) { ... dequeue_entity(cfs_rq, se, flags); ... } for_each_sched_entity(se) { update_load_avg(cfs_rq, se, UPDATE_TG); se_update_runnable(se); update_cfs_group(se); } .... } static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { ...... update_load_avg(cfs_rq, se, UPDATE_TG); //更新调度实体及所属cfs_rq的负载 se_update_runnable(se); //如果是group se，任务已经出队（如进入阻塞状态），那么其runnable_weight需要更新。 //因为对于group se，只有在计算runnable_sum才会考虑任务数量，但是任务已经出队了 //就不再是runnable状态了，是block或者dead状态了。 //这里并没有更新，那么任务阻塞出队cfs rq的负载没有变化，只不 account_entity_enqueue(cfs_rq, se); //将调度实体的load weight从cfs rq中加上。 update_cfs_group(se); .... } 从上述队列出队来看，并没有将load_avg负载减去，而是变化了runnable相关的负载计算，所以即使任务出队进入阻塞状态，其负载依旧在load_avg中，只不过随着时间的增长而衰减。 task与cfs_rq平均负载 这一小节我们主要来分析一下update_load_avg函数主要的作用，直接上代码吧。 static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { u64 now = cfs_rq_clock_pelt(cfs_rq) //获取当前的时刻，减去了空闲时间，也就是该调度实体时间运行的时刻。 int decayed; /* * Track task load average for carrying it to new CPU after migrated, and * track group sched_entity load average for task_h_load calc in migration */ //先计算调度实体的调度负载。 if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD)) __update_load_avg_se(now, cfs_rq, se); //计算调度实体所属cfs_rq的负载。 decayed = update_cfs_rq_load_avg(now, cfs_rq); //group se负载传播：如果调度实体是group se，其下任务有新增或移除等变化，则需要重//新更新group se所在层次的负载，group se下的cfs rq，负载变化要传播到上一层级（group se所在层级）。 decayed |= propagate_entity_load_avg(se); //se->avg.last_update_time为0且DO_ATTACH，表示任务从其他队列迁移过来新入队的。 if (!se->avg.last_update_time && (flags & DO_ATTACH)) { /* * DO_ATTACH means we\'re here from enqueue_entity(). * !last_update_time means we\'ve passed through * migrate_task_rq_fair() indicating we migrated. * * IOW we\'re enqueueing a task on a new CPU. */ //刚加入队列，计算se的负载主要是根据当前所属cfs_rq以及cpu算力等信息进行计//算，接着再将se的负载信息load、runnable、tutil传播到所属cfs_rq的负载。最后会//调用add_tg_cfs_propagate启动负载传播，只有调用了这个函数上面的//propagate_entity_load_avg才会具体执行传播动作。 attach_entity_load_avg(cfs_rq, se); //更新group的平均负载。 update_tg_load_avg(cfs_rq); } else if (decayed) { //负载有变化 cfs_rq_util_change(cfs_rq, 0); //触发是否需要调频 if (flags & UPDATE_TG) update_tg_load_avg(cfs_rq); } } 负载、运行负载、利用率计算 负载计算可以分为两类，调度实体（task se、group se）和调度实体所属的cfs_rq；调度实体的计算是调用函数__update_load_avg_se实现，cfs_rq的计算是调用__update_load_avg_cfs_rq来实现，但是最终都会调用___update_load_sum来计算，只是传入的参数不一样。但两类都使用struct sched_avg结构体来进行描述，主要的核心就是需要先计算出{load|runnable|utils}_sum|avg，计算方法总结如下，后续的代码实际也是围绕这个计算公式来执行。 {load|runnable|utils}_sum’：上一时刻计算的负载。 contrib：上一个时刻到当前时刻负载贡献。 SCHED_CAPACITY_SHIFT:归一化处理，一般是2^10=1024。 divider：LOAD_AVG_MAX - (1024 - avg->period_contrib)，最大负载。 无论load,runnable,running为任何值，只要更新负载上一时刻计算的{load|runnable|utils}_sum’都会衰减。 当load=0时，runable和running也都为0，因为load的取值为se->on_rq，该值为1就已经包含了runnable+running；若该值为0，那么就不是runnable或running，那自然runnable和running为0。 当load≠0，runnable≠0或running≠0，其对应的{load|runnable|utils}_sum会有新增负载贡献。 处于blocked状态的调度实体，不会带来新增负载贡献（load=runnable=running=0），但是会对历史负载进行衰减（step1计算的就是历史负载衰减）。 root@TinaLinux:/# cat /proc/1214/task/1214/sched wifi_daemon (1214, #threads: 2) ------------------------------------------------------------------- se.exec_start : 19745.413299 se.vruntime : 2705.836320 se.sum_exec_runtime : 0.599750 se.nr_migrations : 0 nr_switches : 1 nr_voluntary_switches : 1 nr_involuntary_switches : 0 se.load.weight : 1048576 se.avg.load_sum : 47234 se.avg.runnable_sum : 17325956 se.avg.util_sum : 17325956 se.avg.load_avg : 1024 se.avg.runnable_avg : 361 se.avg.util_avg : 361 se.avg.last_update_time : 19745214464 se.avg.util_est.ewma : 361 se.avg.util_est.enqueued : 361 policy : 0 prio : 120 clock-delta : 83 __update_load_avg_se 参数说明： - load：为se->on_rq，表示当前任务是否处于可运行态，包括runnable + running，对于调度实体来说load要么为0，要么为1。 - runnable：为se_runnable(se)，调度实体是task se则为se->on_rq，如果是group se，则为se->runnable_weight。对于group se来说只要其下有一个se是runnable或running，则group se为runnable或running。runnable_weigh等于处于runnable或running的任务数量。 - running：为cfs_rq->curr se，也就是说当前是否有任务正在运行。 对于task se来说load,runnable,running非0即1；对于group se来说，load,running非0即1，runnable为group se其下运行的任务数量。以下是传入的参数示例： task se： load=runnable=1,running=1 group se： load = 1, runnable = se->runnable_weight, running =1 从上面看出，对于task se与group se的计算，区别主要是runnabe_sum的计算方式不同，group se新增负载贡献需要乘以runnable_weight(group se其下的任务数量)。 {load|runnable|utils}_sum计算的负载只是时间没有权重，但是load_avg需要考虑权重，是权重*时间。 int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se) { //计算{load|runnable|utils}_sum，这里传入三个参数load，runnable，running。 //load：为se->on_rq，se->on_rq=1表示running+runnable //runnable：为se_runnable(se)，这里要考虑当前的调度实体是group se还是task se，如果是task se那就等于se->on_rq，但是如果是group se则为se->runnable_weight，该值实际等于该任务组中running+runnable的任务数量，对于组调度实体来说组内即使有一个任务处于running或runnable那么group se就是running或runnable。 //running：代表当前正在运行的任务。 if (___update_load_sum(now, &se->avg, !!se->on_rq, se_runnable(se), cfs_rq->curr == se)) { //计算{load|runnable|utils}_avg，其中对于load_sum需要乘以权重se_weight(se)。 ___update_load_avg(&se->avg, se_weight(se)); cfs_se_util_change(&se->avg); trace_pelt_se_tp(se); return 1; } return 0; } update_cfs_rq_load_avg load：为scale_load_down(cfs_rq->load.weight)，可以先简单理解为cfs_rq上所有任务的权重和。 runnable：为h_nr_running，表示当前在就绪队列中的任务数量，包含正在运行的任务。 running：为cfs_rq->curr != NULL，cfs_rq队列有任务运行。 下面示例对比task se与cfs_rq。 Task se: load=runnable=1,running=1 group se：load = cfs_rq->load.weight,runnable = cfs_rq->h_nr_running, running =1 从上面公式可以看出，task se和cfs-rq的差别 ① task （group）se的load_sum不考虑权重只考虑时间，而cfs_rq需要考虑整个队列的权重。 ② task se是一个任务，所以 runnable_sum新增负载贡献乘1，而task group 、cfs_rq 计算的runnable_sum需要乘以任务数量。 ③ load_avg对于cfs_rq是不需要乘以权重的，而task se需要相乘权重。 int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq) { //计算cfs_rq的{load|runnable|utils}_sum， //load = cfs_rq->load.weight为当前cfs_rq队列上的权重和，对于64为系统做了缩放。 //runnable = cfs_rq->h_nr_running，当前队列上的任务数量。 //running = cfs_rq->curr != NULL if (___update_load_sum(now, &cfs_rq->avg, scale_load_down(cfs_rq->load.weight), cfs_rq->h_nr_running, cfs_rq->curr != NULL)) { ___update_load_avg(&cfs_rq->avg, 1); trace_pelt_cfs_tp(cfs_rq); return 1; } return 0; } 实际上cfs_rq的负载初值，就是其下task （group）的和，得到初值后，如果没有任务出入队列的情况下，就按照上面的公式进行更新负载，如果说有任务出入队列那么就需要重新更新初值，这个过程叫负载传播。 static void enqueue_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) { cfs_rq->avg.load_avg += se->avg.load_avg; cfs_rq->avg.load_sum += se_weight(se) * se->avg.load_sum; } cfs_rq->avg.util_avg += se->avg.util_avg; cfs_rq->avg.util_sum += se->avg.util_sum; cfs_rq->avg.runnable_avg += se->avg.runnable_avg; cfs_rq->avg.runnable_sum += se->avg.runnable_sum; ___update_load_sum __update_load_avg_se和__update_load_avg_cfs_rq最终都要调用___update_load_sum来计算调度实体负载。 int ___update_load_sum(u64 now, struct sched_avg *sa, unsigned long load, unsigned long runnable, int running) { u64 delta; //delta为当前时刻与上一次计算负载的时间差 delta = now - sa->last_update_time; /* * This should only happen when time goes backwards, which it * unfortunately does during sched clock init when we swap over to TSC. */ if ((s64)delta < 0) { sa->last_update_time = now; return 0; } /* * Use 1024ns as the unit of measurement since it\'s a reasonable * approximation of 1us and fast to compute. */ delta >>= 10; if (!delta) return 0; sa->last_update_time += delta << 10; /* * running is a subset of runnable (weight) so running can\'t be set if * runnable is clear. But there are some corner cases where the current * se has been already dequeued but cfs_rq->curr still points to it. * This means that weight will be 0 but not running for a sched_entity * but also for a cfs_rq if the latter becomes idle. As an example, * this happens during idle_balance() which calls * update_blocked_averages(). * * Also see the comment in accumulate_sum(). */ if (!load) runnable = running = 0; //如果load=0，即cfs_rq->0为0，那么任务不会处于running、runnable，因此也不需要计 //算runnable、running的新增负载贡献。正在运行的任务即使出队了，但是cfs_rq=1。 /* * Now we know we crossed measurement unit boundaries. The *_avg * accrues by two steps: * * Step 1: accumulate *_sum since last_update_time. If we haven\'t * crossed period boundaries, finish. */ //计算*_sum负载。 if (!accumulate_sum(delta, sa, load, runnable, running)) return 0; return 1; } delta为计算当前与上一次更新负载权重的差值，用于后续计算调度负载信息。该函数中会判断load是否等于0，如果为0，说明当前调度实体没有处于running或runnable状态，没有在就绪队列中就不需要计算新增调度负载贡献（注意是贡献，表增量），同时调度实体应该要进行调度负载衰减（没得运行，那么自然对CPU的消耗要降低），因此会调用decay_load对load_sum、runnable_sum、util_sum进行衰减；反之如果load不为0，那么说明调度实体处于running或runnable，那么就需要计算调度负载贡献，最后调度负载等于衰减的负载+新增贡献负载。 负载传播 当一个新创建或从其他cpu迁移的task se加入到一个新的cfs_rq队列时，会导致整个层级的cfs_rq负载发生变化。任务的休眠导致出队的不算？ 会调用attach_entity_load_avg/detach_entity_load_avg来更新cfs_rq load_avg。本章节我们以task se从一个cpu迁移到另外一个cpu的cfs_rq为例说明，update_load_avg->attach_entity_load_avg。 static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) { /* * cfs_rq->avg.period_contrib can be used for both cfs_rq and se. * See ___update_load_avg() for details. */ u32 divider = get_pelt_divider(&cfs_rq->avg); // /* * When we attach the @se to the @cfs_rq, we must align the decay * window because without that, really weird and wonderful things can * happen. * * XXX illustrate */ //当前调度实体的参数从所属cfs_rq中更新 se->avg.last_update_time = cfs_rq->avg.last_update_time; se->avg.period_contrib = cfs_rq->avg.period_contrib; /* * Hell(o) Nasty stuff.. we need to recompute _sum based on the new * period_contrib. This isn\'t strictly correct, but since we\'re * entirely outside of the PELT hierarchy, nobody cares if we truncate * _sum a little. */ //重新计算utils_sum、runnable_sum、load_sum。 se->avg.util_sum = se->avg.util_avg * divider; se->avg.runnable_sum = se->avg.runnable_avg * divider; se->avg.load_sum = se->avg.load_avg * divider; if (se_weight(se) < se->avg.load_sum) se->avg.load_sum = div_u64(se->avg.load_sum, se_weight(se)); else se->avg.load_sum = 1; //将负载信息{load|runnable|util}_更新累加到cfs_rq中。 enqueue_load_avg(cfs_rq, se); cfs_rq->avg.util_avg += se->avg.util_avg; cfs_rq->avg.util_sum += se->avg.util_sum; cfs_rq->avg.runnable_avg += se->avg.runnable_avg; cfs_rq->avg.runnable_sum += se->avg.runnable_sum; //启动负载传播，使能了这个标志，对于gse类型的调度实体才能调用 //propagate_entity_load_avg进行负载传播。 add_tg_cfs_propagate(cfs_rq, se->avg.load_sum); //触发调频 cfs_rq_util_change(cfs_rq, 0); trace_pelt_cfs_tp(cfs_rq); } 对于组任务调度实体，还需要调用propagate_entity_load_avg函数更新当前层级的负载信息。 static inline int propagate_entity_load_avg(struct sched_entity *se) { struct cfs_rq *cfs_rq, *gcfs_rq; //如果时task直接返回，只有gse才需要传播和更新负载。 if (entity_is_task(se)) return 0; //获取gse其下的cfs_rq gcfs_rq = group_cfs_rq(se); //如果没有启动传播，直接返回，有变化才需要更新，没有就直接返回。 if (!gcfs_rq->propagate) return 0; gcfs_rq->propagate = 0; //获取gse所属的cfs_rq cfs_rq = cfs_rq_of(se); //将gcfs_rq上的runnable_sum传递到其所属的cfs_rq上，后续会不断的往上循环更新。 add_tg_cfs_propagate(cfs_rq, gcfs_rq->prop_runnable_sum); //更新gse的utis_avg/sum，所属cfs的utis_avg/sum update_tg_cfs_util(cfs_rq, se, gcfs_rq); //更新gse的runnable_avg/sum，所属cfs的runnable_avg/sum update_tg_cfs_runnable(cfs_rq, se, gcfs_rq); //更新gse的laod_avg/sum，所属cfs的load_avg/sum update_tg_cfs_load(cfs_rq, se, gcfs_rq); trace_pelt_cfs_tp(cfs_rq); trace_pelt_se_tp(se); return 1; } 在更新{utils|runnable|load}_sum|avg的时候，更新gse和所属的cfs_rq，这里的更新与__update_load_avg_se和__update_load_avg_cfs_rq的调用计算是不是重复了？毕竟调用关系是update_load_avg中先调用__update_load_avg_se和__update_load_avg_cfs_rq分别计算se和cfs_rq，然后再调用propagate_entity_load_avg进行更新。答案显然不是，这里的更新可以认为是设置初始值，因为并不是每次都会调用且必须是group se类型才会调用propagate_entity_load_avg计算。__update_load_avg_se和__update_load_avg_cfs_rq是在其初始值的基础上进行更新负载。

时间计算 vruntime与runtime static void update_curr(struct cfs_rq *cfs_rq) { struct sched_entity *curr = cfs_rq->curr; u64 now = rq_clock_task(rq_of(cfs_rq)); u64 delta_exec; if (unlikely(!curr)) return; //实际运行时间 = 当前时刻 减去上次执行时刻 delta_exec = now - curr->exec_start; if (unlikely((s64)delta_exec <= 0)) return; //重新更新开始执行时刻 curr->exec_start = now; schedstat_set(curr->statistics.exec_max, max(delta_exec, curr->statistics.exec_max)); //累计进程实际运行的时间 curr->sum_exec_runtime += delta_exec; schedstat_add(cfs_rq->exec_clock, delta_exec); //累计计算进程的虚拟时间，公式vruntime = delta_exec*（nice_0_weight/weight） curr->vruntime += calc_delta_fair(delta_exec, curr); //更新min_vruntime update_min_vruntime(cfs_rq); if (entity_is_task(curr)) { struct task_struct *curtask = task_of(curr); trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime); cgroup_account_cputime(curtask, delta_exec); account_group_exec_runtime(curtask, delta_exec); } account_cfs_rq_runtime(cfs_rq, delta_exec); } schduer_tick最终会update_curr来个更新当前进程的相关时间信息，包括进程实际运行的时间runtime，虚拟时间vruntime一级min_vruntime。 ideal_runtime 在Linux系统中，为了保证每个进程在一段时间内至少能够运行的机会，系统使用sched_period来表示系统周期，也就是将时间划分成n个sched_period，通常值时6ms，用户可以进行修改。而在这个period周期内，根据各进程的权重来进行瓜分。 Idea_runtime表示每个进程在这个period周期内，可以调度的执行的最长时间，但并不是累计值，比如在period=15ms，进程A的ideal_runtime=6ms，当进程A运行了4ms由于等待某个资源让出了调度，后续获得资源继续运行并不是说进程A只能再运行2ms了，而是运行不超过6ms就行，也就是说ideal_runtime限制的是每次运行不超过的时间，并不算累计值。 在计算ideal_runtime的时候，需要考虑当前进程是否处于任务组内，处于任务组内的进程ideal_runtime相当于是在组内进行按权重划分。在引入任务组后，进程的组织方式可以按照层次来划分，调度实体分为任务调度实体和组调度实体，当然都是使用struct sched_entity来描述。按照层次来划分后，无论调度实体处理哪一个层次，其调度实体ideal_runtime的时间在其平行层次的树中按比例来计算获取，可以简计为 A.ideal_runtime = A.weight / cfs_rqX.load，其中cfs_rqX.load为调度实体所处层级所有进程权重之和。 tse.ideal_runtime = tse.weight / cfs_rq.load = tse.weight / (tse.weight + gse.weight)。 tse3.ideal_runtime= gse2.ideal_runtime * tse3.weight / cfs_rq2.load gse2.ideal_runtime = gse.ideal_runtime * gse2.weight / cfs_rq1.load gse.ideal_runtime = period * gse.weight / cfs_rq0.load tse3.ideal_runtime = period * gse.weight / cfs_rq0.load * gse2.weight / cfs_rq1.load * tse3.weight / cfs_rq2.load 由上公式，period表示当前的运行周期的总时间，根据以上公式，因为都是相乘（ABC与CBA一样），所以计算调度实体的ideal_runtime可以从下往上进计算。 对于tse3处于最底层级L2，所以其权重先计算period * tse3.weight / cfs_rq2.load得到C，然后计算Cgse2.weight / cfs_rq1.load得到B，最后再计算Bgse.weight / cfs_rq0.load得到最终tse3的ideal_runtime。 对于tse处于最高层级L0，也可以从下往上计算，只不过上面没有了，因此就只遍历一次得到结果ideal_runtime = gse.weight / cfs_rq0.load。 在软件上的实现也就变得简单很多了，调度实体se中有一个成员parent指向其父实体，如果parent为空表示没有父实体，也就处于最高层级，不存在任务组内，因此在代码中只要根据se从下往上遍历即可。 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) { unsigned int nr_running = cfs_rq->nr_running; u64 slice; if (sched_feat(ALT_PERIOD)) nr_running = rq_of(cfs_rq)->cfs.h_nr_running; 当前层级tse与gse个数之和 slice = __sched_period(nr_running + !se->on_rq); 一个周期的运行时间period for_each_sched_entity(se) { struct load_weight *load; struct load_weight lw; cfs_rq = cfs_rq_of(se); load = &cfs_rq->load; if (unlikely(!se->on_rq)) { lw = cfs_rq->load; update_load_add(&lw, se->load.weight); load = &lw; } //slice=slice * (se->load.weight / se->cfs_rq->load.weight) //根据权重比例逐级往上计算分配到的物理时间。如果不是属于组任务，则只有一级。 slice = __calc_delta(slice, se->load.weight, load); } if (sched_feat(BASE_SLICE)) slice = max(slice, (u64)sysctl_sched_min_granularity); return slice; } 在设置抢占调度标志章节系统会调用scheduler_tick周期性的检测任务是否超过运行时间，如果超过了就会设置抢占标志位，让出调度权。 static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) { unsigned long ideal_runtime, delta_exec; struct sched_entity *se; s64 delta; bool skip_preempt = false; ideal_runtime = sched_slice(cfs_rq, curr); 计算当前进程一个周期内可以运行的时间。 delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime; 实际运行时间。 如果运行时间超过了一个周期内可调度的时间，则设置可抢占标志。 if (delta_exec > ideal_runtime) { resched_curr(rq_of(cfs_rq)); clear_buddies(cfs_rq, curr); return; } ...... } 任务创建 任务出入列 入就绪队列 出就绪队列 static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags) { struct cfs_rq *cfs_rq; struct sched_entity *se = &p->se; int task_sleep = flags & DEQUEUE_SLEEP; int idle_h_nr_running = task_has_idle_policy(p); bool was_sched_idle = sched_idle_rq(rq); util_est_dequeue(&rq->cfs, p); //迭代遍历每个调度实体，其中se是当前迭代的调度实体 for_each_sched_entity(se) { cfs_rq = cfs_rq_of(se); //获取se所属的CFS实时队列cfs_rq dequeue_entity(cfs_rq, se, flags); //从CFS队列中取出当前的调度实体。 cfs_rq->h_nr_running--; //减少实时队列正在运行的任务数量 cfs_rq->idle_h_nr_running -= idle_h_nr_running; //减少空闲空闲状态下的任务数量 if (cfs_rq_is_idle(cfs_rq)) //如果实时队列变为空闲状态 idle_h_nr_running = 1; /* end evaluation on encountering a throttled cfs_rq */ if (cfs_rq_throttled(cfs_rq)) //如果实时队列被限制，则直接结束处理。 goto dequeue_throttle; //如果实时队列的负载权重大于0，则说明实时队列还有其他调度实体，将调度实体 //更新为其父调度实体，并设置接下来任务选择偏向于从当前实时队列中选择任务。 /* Don't dequeue parent if it has other entities besides us */ if (cfs_rq->load.weight) { /* Avoid re-evaluating load for this entity: */ se = parent_entity(se); //获取父调度实体 /* * Bias pick_next to pick a task from this cfs_rq, as * p is sleeping when it is within its sched_slice. */ if (task_sleep && se && !throttled_hierarchy(cfs_rq)) set_next_buddy(se); //设置下一个调度实体 break; } flags |= DEQUEUE_SLEEP; } trace_android_rvh_dequeue_task_fair(rq, p, flags); for_each_sched_entity(se) { cfs_rq = cfs_rq_of(se); //更新CFS实时队列的负载平均值 update_load_avg(cfs_rq, se, UPDATE_TG); se_update_runnable(se);//更新调度实体的可运行状态 update_cfs_group(se);//更新CFS调度组的信息 cfs_rq->h_nr_running--; cfs_rq->idle_h_nr_running -= idle_h_nr_running; if (cfs_rq_is_idle(cfs_rq)) idle_h_nr_running = 1; /* end evaluation on encountering a throttled cfs_rq */ if (cfs_rq_throttled(cfs_rq)) goto dequeue_throttle; } /* At this point se is NULL and we are at root level*/ sub_nr_running(rq, 1); /* balance early to pull high priority tasks */ if (unlikely(!was_sched_idle && sched_idle_rq(rq))) rq->next_balance = jiffies; dequeue_throttle: util_est_update(&rq->cfs, p, task_sleep); hrtick_update(rq); } 任务选择 开启CFS组调度且被抢占的任务是CFS类 struct task_struct * pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) { //prev表示当前rq上正在运行的，被抢占的task。 struct cfs_rq *cfs_rq = &rq->cfs; struct sched_entity *se = NULL; struct task_struct *p = NULL; int new_tasks; bool repick = false; again: if (!sched_fair_runnable(rq)) goto idle; #ifdef CONFIG_FAIR_GROUP_SCHED //组调度处理 if (!prev || prev->sched_class != &fair_sched_class) goto simple; //如果被抢占task不属于cfs，则跳转到simple处理。 /* * Because of the set_next_buddy() in dequeue_task_fair() it is rather * likely that a next task is from the same cgroup as the current. * * Therefore attempt to avoid putting and setting the entire cgroup * hierarchy, only change the part that actually changes. */ do { struct sched_entity *curr = cfs_rq->curr; /* * Since we got here without doing put_prev_entity() we also * have to consider cfs_rq->curr. If it is still a runnable * entity, update_curr() will update its vruntime, otherwise * forget we've ever seen it. */ //如果当前cfs_rq队列中存在正在运行的调度实体，则需要更新时间，并检查当前 //cfs_rq上的时间片是否使用完（开启带宽控制），如果使用完，那么cfs_rq上所有的//任务都不能再调度，跳转simple处理。 if (curr) { if (curr->on_rq) update_curr(cfs_rq); //更新时间 else curr = NULL; //检查当前cfs_rq队列runtime是否还有剩余（cfs_rq->runtime_remaining>0） //3.4.4.1描述，如果没有剩余，那么cfs_rq下所有的任务将不再允许调度。 if (unlikely(check_cfs_rq_runtime(cfs_rq))) { cfs_rq = &rq->cfs; if (!cfs_rq->nr_running) goto idle; goto simple; } } //挑选下一个调度实体，选择红黑树最左边的 se = pick_next_entity(cfs_rq, curr); cfs_rq = group_cfs_rq(se); //当前的调度实体是一个任务组,se->my_q !=NULL } while (cfs_rq); //如果是一个任务组，则继续从该任务组从挑选合适的任务 p = task_of(se); //获取当前调度实体对应的task_struct。 trace_android_rvh_replace_next_task_fair(rq, &p, &se, &repick, false, prev); /* * Since we haven't yet done put_prev_entity and if the selected task * is a different task than we started out with, try and touch the * least amount of cfs_rqs. */ if (prev != p) { //被抢占的任务与当前挑选要允许的任务不同。 struct sched_entity *pse = &prev->se; //获取被抢占任务的调度实体。 //循环遍历，直到将要运行的调度实体与被抢占的调度实体或父实体在同一级 while (!(cfs_rq = is_same_group(se, pse))) { int se_depth = se->depth; //获取将要运行的调度实体所在层次 int pse_depth = pse->depth;//获取将被抢占任务调度实体所在层次 if (se_depth <= pse_depth) { //要运行的调度实体层次比被抢占的要浅（在上一级） put_prev_entity(cfs_rq_of(pse), pse); //将其调度实体调整重新入队（运行的时候是不在就绪队列上的，不能调度了，//因此需要加入到就绪队列） pse = parent_entity(pse); //找到其父调度实体，继续循环跟当前要运行的调度实体在同一级 } if (se_depth >= pse_depth) { //要运行的调度实体层次比被抢占的要深（在下一级） set_next_entity(cfs_rq_of(se), se); //设置将要执行的调度实体，主要动作是将当前将要调度的实体出队，要调度的实//体不应该在保存在就绪队列上，而是存储在cfs->curr上。 se = parent_entity(se); //指向其父调度实体 } } //到此时，已经找到将要调度的实体与被抢占的调度实体同一级的父调度实体 //为什么要找将要调度实体与被抢占的实体的父/祖所在同一层级的了，是因为 //调度是从上往下的，其任务组中的任务实体要能够被调度，那必须要让其父 //拿到调度权。 put_prev_entity(cfs_rq, pse); //将被抢占的调度实体（可能是父）重新入队 set_next_entity(cfs_rq, se);//设置当前的调度实体为下一个将要运行调度实体。 } goto done; 未开启CFS组调度或被抢占的任务不是CFS调度类 simple: #endif if (prev) put_prev_task(rq, prev); //将被抢占的进程重新放回就绪队列中，运行的进程是放在cfs_rq->curr上，不在就绪队列上。 trace_android_rvh_replace_next_task_fair(rq, &p, &se, &repick, true, prev); if (repick) goto done; do { //从cfs_rq中重新挑选下一个调度实体 se = pick_next_entity(cfs_rq, NULL); //将挑选的调度实体设置未将要运行的进程并移除就绪队列 set_next_entity(cfs_rq, se); //判断当前的调度实体是任务组调度实体，如果是则在任务组cfs_rq查找调度实体。 cfs_rq = group_cfs_rq(se); } while (cfs_rq); p = task_of(se); done: __maybe_unused; #ifdef CONFIG_SMP /* * Move the next running task to the front of * the list, so our cfs_tasks list becomes MRU * one. */ list_move(&p->se.group_node, &rq->cfs_tasks); #endif if (hrtick_enabled_fair(rq)) hrtick_start_fair(rq, p); update_misfit_status(p, rq); return p; 没有要运行的任务 idle: if (!rf) return NULL; new_tasks = newidle_balance(rq, rf); /* * Because newidle_balance() releases (and re-acquires) rq->lock, it is * possible for any higher priority task to appear. In that case we * must re-start the pick_next_entity() loop. */ if (new_tasks < 0) return RETRY_TASK; if (new_tasks > 0) goto again; /* * rq is about to be idle, check if we need to update the * lost_idle_time of clock_pelt */ update_idle_rq_clock_pelt(rq); return NULL; } 小结 任务的选择分为三种情况：开了组调度且被抢占的任务是CFS类，未开组调度或被抢占的任务不是CFS类，没有任务可运行。 挑选了下一个要运行的任务调用set_next_entity来设置并且把被抢占的任务调用put_prev_entity重新入队。set_next_entity和put_prev_entity两个函数可以看出是一对，当设置要运行的运行时，任务将会从就绪队列出队，用cfs_rq->curr来指向当前正在运行的任务，但是这里需要注意的时出队调用的时__dequeue_entity直接从红黑树中移除，而不是调用dequeue_entity，再去更新时间、计算负载贡献等等，这里尤其要注意的是se->on_rq这个变量，在dequeue_entity该变量se->on_rq=0，表示任务出队，而set_next_entity直接调用__dequeue_entity该值se->on_rq不会变，而是se->on_rq=1，当前正在运行的任务即使从红黑树中被移除的，但是se->on_rq依旧是1，所以该任务并不是完全意义的出队列，因此se->on_rq=1意味着任务是runnable+running（runnable表示任务处于就绪队列中，running表示任务正在运行），这对于后续负载计算的时候影响较大。put_per_entity要做的时候就是将被抢占的任务再次入队与set_next_entity所做事情相对应。 任务切换 参考： https://heapdump.cn/article/2730937

Linux系统都是支持多用户登录，如果一个Linux系统两个用户存在不同的数量的进程，假设A用户有10个进程，B用户有20个进程，如果系统对这30个进程进行平分CPU，实际上是不公平的，因此引入了组调度的概念，即A用户对CPU的占用应该跟B用对CPU的占用各自为50%，A/B用户下的进程再根据得到占用进行划分。系统中有cfs组调度和rt组调度，本小节主要以cfs调度为主。 如上图，组A的进程分别分配到了CPU0和CPU1上运行，在CPU0和CPU1上的进程各自组合成一个调度实体G1，两个组在各自的CPU上互不影响。以CPU0为例，G1和P1在一颗红黑树中进行调度，G1获得的“调度资源”，将需要“平分”给其组员（组进程）。 基本原理 使用struct task_group来描述任务组，下面是struct task_group的数据结构，后续的组用tg简称。 kernel/sched/sched.h struct task_group { struct cgroup_subsys_state css; struct sched_entity **se; //动态数组，对应每个cpu上调度实体 struct cfs_rq **cfs_rq;//动态数组，对应每个cpu上调度实体下的进程集合 unsigned long shares; //当前进程组权重 atomic_long_t load_avg; struct sched_rt_entity **rt_se; struct rt_rq **rt_rq; struct rt_bandwidth rt_bandwidth; struct list_head list; 全局所有任务组加入到全局链表task_groups上。 struct task_group *parent; 指向当前调度组的父任务组 struct list_head siblings; 将当前tg挂载到父tg的children链表上。 struct list_head children; 挂着当前tg组所有孩子的tg。 struct cfs_bandwidth cfs_bandwidth; 用于带宽控制 } 所有的任务组会以树结构来组织，在Linux系统中定义了一个全局的根节点struct task_group root_task_group;同时定义一个全局链表LIST_HEAD(task_groups)将所有任务组串在一个链表上。 如上图，G1~G4形成一颗树，根为root_task_group，并且G1~G4串联在链表上task_groups上。 上图是task_group与调度相关数据结构之间的关系。task_group有自己的调度实体struct sched_entity，与task_struct中的调度实体区别是，这里是一个指针数组，指针数组的大小为当前cpu核的个数，因为一组中有多个进程，但是这些进程可以分配到不同的cpu核上，因此每个数组se表示一个cpu核上的调度实体，也就是说当分配一个组时，就会为每个CPU都会维护一个se。同理task_group中cfs_rq红黑树用于记录组任务中在每个cpu下的进程。 上图是一个任务组的示例，任务组tg下进程分配到CPU0和CPU1上运行。全局root_task_group，其se和parent都会NULL，cfs分别指向CPU0和CPU1的cfs队列。因为任务组tg下的进程分布在两个cpu上，因此CPU0和CPU1各自对应一个任务组调度实体group se，tg中的se[0]和se[1]分别指向cpu0和cpu1上组调度实体，组调度实体group和进程调度实体task se处于第一级的平行关系，也就是调度公平。Group se中my_q和tg中cfs指向了任务组进程的队列，该队列处于调度的第二级。所以当组调度实体再与平行关系的进程获得调度机会后，将平均（再按照CFS算法）分给其组内进程进行调度。 创建组调度 权重 gse->load.weigh = tg->weight * grq->load.weight / Sum grq->load.weight tg->weight：任务组默认权重值，等于tg->shares，默认是1024。 grq->load.weight：单cpu下任务组中所有进程的权重之和。 Sum grq->load.weight：任务组中所有进程任务之后，包含分配在各cpu上的。 示例：cpu0 gse->load.weight = 1024 * (1024 + 2048) / (1024 + 2048 + 3072) = 3145728/6144 = 512 上面是理想化的公式模型，但是实际情况Sum grq->load.weight因为需要涉及访问各个CPU上的grq，会导致锁竞争的代价，因此根据上面公式做了近似计算最终得到如下： gse->load.weight = tg-weight * grq->load.weight / (tg->load_avg - grq->avg.load_avg + max (grq->load.weight,grq->avg.load_avg)) 具体演化结果可以参考kernel/sched/fair.c中calc_group_shares函数的注释，这里就不详细阐述了，calc_group_shares通过上面的公式近似计算各个gse分得的权重。 static long calc_group_shares(struct cfs_rq *cfs_rq) { long tg_weight, tg_shares, load, shares; struct task_group *tg = cfs_rq->tg; tg_shares = READ_ONCE(tg->shares); load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg); tg_weight = atomic_long_read(&tg->load_avg); /* Ensure tg_weight >= load */ tg_weight -= cfs_rq->tg_load_avg_contrib; tg_weight += load; shares = (tg_shares * load); if (tg_weight) shares /= tg_weight; return clamp_t(long, shares, MIN_SHARES, tg_shares); } 从公式可以看出，gse的权重与任务组进程个数以及cpu.shares有关系。cpu.shares则是用户节点/sys/fs/cgroup/cpu.shares可控制。 带宽管理 考虑这样的一个场景，假设一个用户只支付了0.5个CPU的费用，那么正常情况下就只能给其0.5个CPU的时间。因此为了限制用户进程对CPU资源占用情况，引入带宽控制，带宽控制是基于分组调度来实现，对一个任务组的运行带宽做限制，也就是在一个周期内，允许一个任务组最多执行多长时间，当任务组运行完了自己的时间，将会被限制不允许运行，即使没有任何任务运行，也需要等到下一个周期。 带宽限制以任务组为单位进行限制，为方便描述原理，上图是只有一个任务组，任务组中的进程被分配到CPU0和CPU1上运行。在task_group数据结构中，cfs_bandwidth成员用于全局描述当前任务组带宽限制，表示在一个period周期内，任务组可使用的时间为quota，这里的时间是任务组中进程的和，当quota使用完后，在整个周期内将会被限制运行，称为throttle操作。 在任务组tg（便于简化假设用户组中只有一个任务组，暂且也称用户组）中有cpu数量的就绪队列，对应上图的cfs_rq0和cfs_rq1，这两个就绪队列所属于任务组。就绪队列中runtime_remaining为当前队列中所有进程可运行的时间，进程运行时就会消耗runtime_remaining，当runtime_remaining被消耗小于0时，可以向全局时间池tg->cfs_b->runtime（表示任务组剩余可使用的时间）中申请，每次申请的值为sysctl_sched_cfs_bandwidth_slice（可节点配置，默认是5ms），当tg->cfs_b->runtime将被耗尽时，不能满足cfs_rqx->runtime_remaining时，cfs_rqx就绪队列将会被移除（对应的gse在上一级中被移除）。 （1）cfs_bandwidth - period: 定时器周期时间 - quota:在周期内任务组可使用的时间 - runtime:剩余时间，quota+runtime = period - period_timer:周期性定时器，定时到达后重置剩余限额runtime为quota。 - slack_timer: - throttled_cfs_rq:所有被throttle的cfs_rq挂入到次链表，用于后期unthrottle cfs_rq操作。 （2）cfs_rq中关于带宽管理描述 - runtime_enabled：该就绪队列是否开启带宽限制。 - runtime_remaining: cfs_rq会从全局时间池申请时间片，当剩余时间片小于0，需要重新申请。 - throttled:判定cfs_rq是否被throttled。 - throttled_list: 被throttled_list的cfs_rq会被挂入到cfs_bandwidth->throttled_cfs_rq链表。 任务组剩余时间 在task_group中，在每个CPU上都有一个cfs_rq红黑树，cfs_rq结构体中有一个runtime_remining用于描述当前组能够运行的时间合计，任务组中的每个任务运行都会消耗掉runtime_remining，当runtime_remaining被消耗完时会从全局时间池申请，如果全局池中的时间也用完了，那么就需要让出调度，cfs_rq就会被throttle。 runtime_remaining的更新在update_curr函数中进行。如上图所示cfs_rq->runtime_remaining-=delta_exec，每个进程将会对runtime_remainning进行消耗，当runtime_remaining不足时，调用assign_cfs_rq_runtime进行申请。 static int __assign_cfs_rq_runtime(struct cfs_bandwidth *cfs_b, struct cfs_rq *cfs_rq, u64 target_runtime) { u64 min_amount, amount = 0; lockdep_assert_held(&cfs_b->lock); /* note: this is a positive sum as runtime_remaining <= 0 */ min_amount = target_runtime - cfs_rq->runtime_remaining; //计算每次向全局时间池要申请的时间片大小，target_runtim由sched_cfs_bandwidth_slice()计算得来，默认是5ms，可以通过sched_cfs_bandwidth_slice_us节点进行修改。 if (cfs_b->quota == RUNTIME_INF) //不限制带宽，remainig可以一直申请到时间片。 amount = min_amount; else { start_cfs_bandwidth(cfs_b); //如果没有启动cfs_b->period_timer就启动 //如果全局时间池时间还有剩余，则分配给当前就绪队列。 if (cfs_b->runtime > 0) { amount = min(cfs_b->runtime, min_amount); cfs_b->runtime -= amount; //时间被瓜分出去 cfs_b->idle = 0; } } //更新当前队列的剩余时间 cfs_rq->runtime_remaining += amount; //如果没有从全局池申请到时间片，则返回0，那么当前进程将会被throttle，让出调度。 return cfs_rq->runtime_remaining > 0; } 任务组一个全局时间池，剩余全局池的时间存储在cfs_b->runtime中，其所属的就绪队列cfs_rq会从全局池中申请可使用的时间，每次申请时间大小为sched_cfs_bandwidth_slice_us（可通过节点来进行修改默认是5ms）。 cfs_rq->runtime_remaining和cfs_b->runtime的区别是？runtime为任务组的全局剩余时间，一个任务组可能包含多个cfs_rq（包含各CPU，以及子任务组等），所以runtime大于runtime_remaining。cfs_rq->runtime_remaining小于等于0时就绪队列cfs_rq的调度实体将会被移除，下次调度将不再被选择到。 限制任务组运行 static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) { /* dock delta_exec before expiring quota (as it could span periods) */ cfs_rq->runtime_remaining -= delta_exec; if (likely(cfs_rq->runtime_remaining > 0)) return; if (cfs_rq->throttled) return; /* * if we're unable to extend our runtime we resched so that the active * hierarchy can be throttled */ if (!assign_cfs_rq_runtime(cfs_rq) && likely(cfs_rq->curr)) resched_curr(rq_of(cfs_rq)); } 当assign_cfs_rq_runtime从全局时间池中申请不到时间，就会调用resched_curr触发调度。在以下场景下，会检测是否进行限流，如果限制则调用throttle_cfs_rq将当前调度实体（组调度实体）移除就绪队列。 static bool throttle_cfs_rq(struct cfs_rq *cfs_rq) { struct rq *rq = rq_of(cfs_rq); struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg); struct sched_entity *se; long task_delta, idle_task_delta, dequeue = 1; raw_spin_lock(&cfs_b->lock); //计算当前cfs_rq剩余可用的时间。 if (__assign_cfs_rq_runtime(cfs_b, cfs_rq, 1)) { dequeue = 0; } else { //如果剩余可用时间为0，则将当前cfs_rq添加到throttled_cfs_rq。 list_add_tail_rcu(&cfs_rq->throttled_list, &cfs_b->throttled_cfs_rq); } raw_spin_unlock(&cfs_b->lock); //还有剩余可使用时间，直接返回 if (!dequeue) return false; /* Throttle no longer required. */ //获取当前cfs_rq对应的调度实体 se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))]; /* freeze hierarchy runnable averages while throttled */ rcu_read_lock(); //遍历cfs_rq子任务组，并累加cfs_rq->throttle_count++ walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq); rcu_read_unlock(); task_delta = cfs_rq->h_nr_running; idle_task_delta = cfs_rq->idle_h_nr_running; for_each_sched_entity(se) { struct cfs_rq *qcfs_rq = cfs_rq_of(se); /* throttled entity or throttle-on-deactivate */ if (!se->on_rq) goto done; //将当前调度实体出队，移除就绪队列 dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP); if (cfs_rq_is_idle(group_cfs_rq(se))) idle_task_delta = cfs_rq->h_nr_running; qcfs_rq->h_nr_running -= task_delta; qcfs_rq->idle_h_nr_running -= idle_task_delta; //如果当前调度实体的就绪队列只有一个，那么父调度实体也要被出队。 //如果调度实体就绪队列不只是一个，那么直接退出，也就只循环一次。 if (qcfs_rq->load.weight) { /* Avoid re-evaluating load for this entity: */ se = parent_entity(se); break; } } //设置被限流的标志 cfs_rq->throttled = 1; return true; } 判断一个cfs_rq是否被限流的标志，就是看cfs_rq-reamaining是否还能申请到时间。 period_time和slack_timer定时器 struct cfs_bandwith结构体中，有两个定时器：period_timer和slack_timer。period_timer计时到达时表示一个period到期（对应cfs_bandwith中的period周期），就会重新更新quota以及解除之前限制的任务。slack_timer则要解决的是全局时间池时间的浪费问题，假设一个cfs_rq从全局池申请了5ms时间片，而cfs_rq中只有一个进程，该进程运行1ms就睡眠一直睡眠了，而整个cfs_rq对应的gse会被dequeue，那么剩余的4ms需要归部分还给全局时间池，当全局池时间累计大于5ms，那么就启动slack_timer将此前ttrottle cfs_rq取消限流。 void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) { raw_spin_lock_init(&cfs_b->lock); cfs_b->runtime = 0; cfs_b->quota = RUNTIME_INF; //默认=-1，无限制 cfs_b->period = ns_to_ktime(default_cfs_period()); //初始化period，默认100ms cfs_b->burst = 0; INIT_LIST_HEAD(&cfs_b->throttled_cfs_rq); //初始化链表，被限制的cfs将挂到该链表上 hrtimer_init(&cfs_b->period_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS_PINNED); cfs_b->period_timer.function = sched_cfs_period_timer; //初始化period_timer定时器 hrtimer_init(&cfs_b->slack_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL); cfs_b->slack_timer.function = sched_cfs_slack_timer; //初始化slack_timer定时器 cfs_b->slack_started = false; } init_cfs_bandwidth函数将初始化两个定时器，period_timer在进程入队/更新runtime时间的时候进行启动，启动period_timer后就每个period时间后重新将quota更新给任务组的runtime并将已经节流的cfs_rq重新加入队列。slack_timer是在调度实体出队的时候触发，当调度实体被移除就绪队列时，就检测cfs_rq上剩余可运行时间，如果剩余时间不足1ms就不用归还给全局时间池，否则归还cfs_rq->runtime_remaining - min_cfs_rq_runtime（默认1ms）的时间给全局时间池，归还给全局时间池后需要判断是否可以启动定时器将此前被节流的cfs_rq调度实体重新加入到就绪队列中，判断的条件是全局池中剩余的时间要大于cfs_b->runtime > sched_cfs_bandwidth_slice()（默认要大于5ms），因为cfs_rq每次申请的时间片是sched_cfs_bandwidth_slice()。 static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq) { struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg); s64 slack_runtime = cfs_rq->runtime_remaining - min_cfs_rq_runtime; //计算归还给系统的时间，预留一点时间给就绪队列 //如果没有剩余时间，直接返回。 if (slack_runtime <= 0) return; raw_spin_lock(&cfs_b->lock); if (cfs_b->quota != RUNTIME_INF) { cfs_b->runtime += slack_runtime; //全局池的时间要大于cfs_rq每次申请的时间片并且有就绪队列被节流 if (cfs_b->runtime > sched_cfs_bandwidth_slice() && !list_empty(&cfs_b->throttled_cfs_rq)) start_cfs_slack_bandwidth(cfs_b); } raw_spin_unlock(&cfs_b->lock); //重新更新当前就绪队列的时间片 cfs_rq->runtime_remaining -= slack_runtime; } 小结 （1）cfs_b->runtime: 任务组的进程在一个period周期能可运行的时间为runtime，该值在每个周期到来时会被更新为quota值。 （2）cfs_rq->runtime_remaining:任务组所属的就绪队列cfs_rq，就绪队列中的进程运行后将会消耗runtime_remaining，调度周期会调用update_curr函数更新当前进程执行时间了多少时间即对应runtime_remaining就会被减少，当runtime_remaining不足时就会向全局cfs_b->runtime申请，如果申请不到当前的cfs_rq就绪队列上所以进程就会被节流无法再运行。 （3）节流：就绪队列无法申请到运行时间就会被节流并设置可被抢占（resched_curr），在进程切换的时候会检查被节流的调度实体，并将当前调度实体从就绪队列中移除。 （4）解除节流：下一个周期到来或者另外一个就绪队列让出了时间（slack_timer），节流的队列将会被重新加入到就绪队列得以运行。 将两个进程放到任务组，调整quota_us观察cpu占用率情况。 mkdir -p cgroup/cpu/ mount -t cgroup -ocpu cpu /cgroup/cpu/ cd /cgroup/cpu/ mkdir A cd A echo 1293 > cgroup.procs echo 1294 > cgroup.procs cat cpu.cfs_period_us echo 10000 > cpu.cfs_quota_us 将两个进程绑定到一个核上运行，调整nice观察cpu占用率。 # 将1309和1221都绑定到0核上 taskset -cp 0 1309 taskset -cp 0 1221 renice -1 1221 #动态调整1221进程的优先级 将两个进程放到任务组，并运行多个进程，调整cpu.shares，观察整体任务组分配到的cpu占用率，把相同业务的进程放到一个组，然后调整优先级。 mkdir -p cgroup/cpu/ mount -t cgroup -ocpu cpu /cgroup/cpu/ cd /cgroup/cpu/ mkdir A cd A echo 1293 > cgroup.procs echo 1294 > cgroup.procs echo 1277 > cpu.shares

上一章节中描述了Linux系统中支持多种调度，不同的调度有不同的优先级范围。对于普通进程使用的CFS调度（Completely Fair Scheduler，CFS）。完全公平调度主要核心思想就是保证在一段时间内，每个进程能够运行的时间趋于相等。 为了尽可能的保证一段时间内，每个进程能够运行的时间相等，那么系统就需要计算出每个进程每次能够运行的时间runtime，计算出每个进程的runtime后，系统总是让之前累计运行时间最少的进程先运行，累计运行时间长的进程后运行，这样让进程运行公平。 理想公平调度模型 假设单核CPU上有3个进程，这3个进程都处于就绪队列中，调度器每次调度运行会挑选一个runtime值最小的来运行。 如上图，TASK1先运行了4ms（runtime=4ms）让出调度，调度器查询就绪队列中发现TASK2和TASK3的runtime=0（没运行过），那么此次调度按顺序选择TASK2进行调度运行，TASK2运行了2ms就结束了其runtime=2ms。调度器在就绪队列中继续选择，发现此时TASK3的runtime值最小=0，那么挑选TASK3运行，TASK3运行了5ms让出调度其runtime=5ms。调度器继续从就绪队列中选择进程，发现TASK2 runtime=2ms为最小，因此选择TASK2运行，TASK2运行了4ms，因此runtime累计为=6ms。因此在T1时间内TASK1、TASK2、TASK3分别运行了4ms，5ms，6ms，随着时间的推进，调度器总是选择运行时间最小的先运行，那么各进程获得的运行时间趋于相等。 调度器选择运行时间最小的进程先运行，那是不是进程得到调度后想运行多久就运行多久？答案并不是的，而是有一定的限制。在CFS调度中，规定了一个调度周期period，每个进程能够运行的最长时间等于period/进程数量（当然还没有考虑优先级权重）。规定这样的一个调度周期用来限制每个进程最长的运行时间，避免某个进程一直运行，这样保证一段时间内，每个进程都能够得到至少运行一次。理想情况下如果period为20ms，那么有4个进程，那么平均每个进程的运行时间为5ms。在Linux系统中period并不是固定一个值，因为period固定后，当进程数量越来越多后，每个进程分配的时间就会变少，那么调度器的切换时间就会变得频繁，频繁的切换调度器也就意味着需要频繁的切换上下文，这样对于系统的开销是得不偿失的。因此Linux系统的做法是默认情况下保持一个默认值（默认值6ms），当系统就绪进程个数超过一定数量后，计算处理的运行时间小于6ms后，那么Linux系统会进行动态调整。 kernel/sched/fair.c static u64 __sched_period(unsigned long nr_running) { if (unlikely(nr_running > sched_nr_latency)) return nr_running * sysctl_sched_min_granularity; else return sysctl_sched_latency; } nr_running是系统中就绪进程数量，当超过sched_nr_latency，就无法保证调度延迟，period就转为调度最小粒度。如果没有超过，调度周期就等于调度延迟sysctl_sched_latency（6ms）。 因此根据sched_period可知，总时间固定的情况下，每个进程要运行的理想时间也是确定的。 优先级与虚拟时间 优先级 CFS想要实现的是每个进程能够平均分配时间片，但是现实并非如此，因为任务总是有优先级的，有权重之分，一些任务比较重要，所以它理论上能够运行更多时间（就好比每个人的能力不一样，产生的绩效不一样，所以公司在分配年终奖的时候会倾向于产出更多绩效的优秀员工）。基于上述的场景，引入了权重的概念，权重代表这优先级，也就是不同进程的优先级对应不同的权重，CFS调度器使用nice值来表示优先级，取值范围[-20,19]数值越小，优先级越大，每个nice值都与权重值一一对应。 kernel/sched/core.c const int sched_prio_to_weight[40] = { /* -20 */ 88761, 71755, 56483, 46273, 36291, /* -15 */ 29154, 23254, 18705, 14949, 11916, /* -10 */ 9548, 7620, 6100, 4904, 3906, /* -5 */ 3121, 2501, 1991, 1586, 1277, /* 0 */ 1024, 820, 655, 526, 423, /* 5 */ 335, 272, 215, 172, 137, /* 10 */ 110, 87, 70, 56, 45, /* 15 */ 36, 29, 23, 18, 15, }; 引入权重后，分给进程的运行时间就由一下公式计算得来： 进程运行时间=总的CPU时间*（进程权重/就绪队列所有进程权重之和） 如上假设就绪队列中有A和B两个进程，A进程的nice值是0，B的nice值-1。那么A和B各自运行的时间占比为：A=1024/（1024+1277）=44.5%。B=1277/（1024+1277）=55.5%。相当于B比A多运行了10%的时间，也就是说当nice值降低一个挡位，将多获得10%的cpu时间。 虚拟时间 理想情况下，不区分优先级和权重，那么每个进程能够平分运行时间，但是引入权重后，本身在每个进程得到运行的时长就是不一样的，优先级高的进程会得到更长的运行时间。当每个进程本身的能够得到的运行时间就不一样的情况下，按照3.2.1公平调度原则，累计运行时间少的先运行看起来就太适用了。 为了解决这个问题，引入了虚拟时间。虚拟时间用于在加入权重后，衡量每个进程在一段时间内运行是公平的，即各自能够运行的虚拟时间是相等的。 假设A、B、C的进程权重分别是1，2，3。那么A运行Nms、B运行2Nms，C运行3Nms才是公平的。虚拟时间和实际的转化公式如下： vruntime = delta_exec*（nice_0_weight/weight） delta_exec表示实际运行时间，nice_0_weight表示nice值为0的进程权重值，weight表示进程的权重值。为什么是nice_0_weight/weight了，是因为nice_0_weight对应的权重实际运行时间和虚拟运行时间相当。 当引入优先级权重中，就不用runtime值最小来判定优先运行，而是选择vruntime来判断，选择vruntime值最小的优先运行。虚拟时间等于实际运行时间乘以一定比重，这个比重根据优先级来判断。调度保证每个进程在一定时间内运行的虚拟时间相等。 就绪队列中的每个进程对应的vruntime将会被挂到红黑树中，当前CPU进行调度时，将会从左往右开始优先选择，也就是选择vruntime最小的进程先运行。之所以选择红黑树是因为查找速度是O(1)。 min_runtime 考虑这样的一个场景，就绪队列中有A,B,C进程已经各自运行了一段时间了，此时有一个新的进程加入到就绪队列，D加入的时候，runtime应该是多少？如果D从0开始计算，那么D将会一直运行指导追赶上A/B/C三个进程，因为调度的原则就是选择最小的vruntime来运行，如果A/B/C已经运行了几天了，那么当D加入的时候就要先运行几天追赶上A/B/C，这样显然是不合理的。 针对以上的场景，引入了min_runtime。min_runtime记录调度队列中，虚拟时间最小的值。因此当新进程加入的时候，其虚拟时间需要+min_runtime值，这样就能够解决上述场景的问题。

调度类别 进程调度依赖于调度策略（schedule policy），linux内核把相同的调度策略抽象成调度类（schedule class）。不同类型的进程采用不同的调度策略，目前Linux内核中默认采用5种调度类，分别是stop、deadline、realtime、CFS和idle。 Stop：最高优先级的进程，只在多核场景下启用，用于热插拔等场景下停止CPU。 Dealine：用于有严格时间要求的实时进程，优先级为-1。 Realtime：用于普通的实时进程，优先级为0~99。 CFS：完全公平调度，非实时类进程，优先级100~139。 Idle：最低优先级进程，当所有进程都没运行之后运行idle，仅供内核使用。 实际上STOP、IDLE不算是真正意义上的调度类，因为其需要在比较特殊的场景下由内核去执行，因此重点的调度主要分为三个DL,RT,CFS。 Linux用户空间程序可以使用如sched_setscheduler来设定用进程的调度策略，SCHED_NORMAL、SCHED_BATCH、SCHED_IDLE使用CFS。SCHED_FIFO和SCHED_RR用于Realtime。SCHED_DEADLINE用于DL调度。 SCHED_FIFO和SCHED_RR使用Realtime。SCHED_FIFO和SCHED_RR的区别是，SCHED_RR按时间片循环运行，如优先级相同的进程，轮流运行固定长度时间片，而SCHED_FIFO先到先得，会一直运行直到自愿放弃或被更高优先级抢占为止。 Linux系统中，按照优先级顺序从高到低顺序遍历各个调度器，如果某个调度器成功取出了任务，则选择任务进行调度。 kernel/sched/core.c for_each_class(class) { p = class->pick_next_task(rq); if (p) return p; } chrt -p 1234 # 可以查看 pid=1234 的进程的 调度策略 chrt -p -f 10 1234 # 修改调度策略为 SCHED_FIFO, 并且优先级为10 调度时机 调度队列 在linux系统中，定义了一个全局的struct rq类型的数组runqueues，每个CPU对应一个数组成员，定义如下： kernel/sched/core.c static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues); kernel/sched/sched.h #define cpu_rq(cpu) (&per_cpu(runqueues, (cpu))) 根据CPU编号获取rq #define this_rq() this_cpu_ptr(&runqueues) 获取当前进程的rq #define task_rq(p) cpu_rq(task_cpu(p)) 获取进程p所在的rq #define cpu_curr(cpu) (cpu_rq(cpu)->curr) 根据CPU编号获取正在运行的进程 上 图列出了struct rq与struct task_struct之间的关系。每个CPU都对应一个struct rq实体。rq中分别对应3个调度队列（暂不考虑stop、idle类，从数据结构也可以看出stop、idle属于特殊调度类）。 cfs_rq对应的是CFS调度，CFS就绪进程通过红黑树来组织，调度优先选择vruntime最小的进行。 rt_rq对应的是RT调度，RT就绪进程通过链表来组织，每个优先级对应一条链表，相同优先级的进程挂载到同一条链表上；每个链表对应一个bitmap，系统通过查询bitmap的位0或1来判断当前链表中是否有进程就绪。系统调度是一次从高优先级开始遍历查询对应的bitmap，进而选择对应进程运行。 dl_rq对应的是DL调度，后续再阐述。 触发调度 调度顾名思义就是选择一个进程运行，包括系统启动运行的第一个进程，以及运行过程中从当前运行进行切换到另外一个进程。在Linux系统中触发调度的可以分为两类：主动让出调度与抢占式调度（与FreeRTOS的区别，就是抢占式调度这里，FreeRTOS是systick来进行调度，有时间片的概念，而Linux不在有时间片的概念）。 主动调度是CPU主动放弃CPU，包括主动Sleep，读写IO，Mutex等。 抢占调度在Linux系统中并不是立即得到调度权，而是在需要抢占调度时设置一个标志（TIF_NEED_RESCHED），Linux系统在合适时机检测到这个标志会进行调度，因此抢占调度可以分为三个阶段设置抢占调度标志、检测抢占调度标志、选择任务调度。 无论是主动调度还是抢占调度，最终调用的都是函数schedule。 设置抢占调度标志 设置抢占调度的标志一般有以下场景： - Tick调度：Linux系统中有周期性的时钟，会周期性的检测当前的进程是否运行idle_runtime超期。 - 任务创建：新创建任务的时候，会将任务加入到就绪队列中，会根据优先级判定是否需要抢占。 - 任务唤醒：任务在获取到等待的资源从睡眠中唤醒，判定是否需要抢占。 - 任务切换：调整调度类、优先级等。 - 带宽控制：分配给当前运行的任务带宽用尽。 以上只是列出了部分设置抢占调度标志的代码流程，并未全部列出，并且代码流程做了简化。 检测抢占标志 选择任务调度

fork创建了一个新的进程，也就是fork执行后就会返回两次，分别是父进程返回和子进程返回。 exec可以加载新的程序运行（原程序是A，可以在A中运行后加载可执行程序B，B是A的子进程）。而如果没有exec，A程序执行fork后，仅只是将fork之后的代码复制了一份。exec最早是为了实现shell而涉及的，目的是能够A程序启动B程序后，可以改变进程的环境变量实现如 ps > 1.txt这种处理。 父进程可以调用wait来等待子进程退出，子进程结束后会销毁其使用的资源，但是会保留task_struct+栈空间（一般累计4K或8K大小），这块空间子进程不能销毁，只能等父进程使用wait来进行销毁。如果父进程没有wait来销毁这块内存，子进程就会变成僵尸进程。如果父进程没有调用wait而先于子进程结束，那么init进程会收留这个子进程，调用wait进行销毁掉。 进程终止一是自愿终止包括显式调用exit()系统调用或者从某个程序主函数返回；另外一个式被动收到终止信号或者异常终止。进程主动终止：在main函数中返回，链接程序会自动添加exit系统调用或主动调用exit函数两种方式。进程被动终止：进程收到一个自己不能处理的信号、进程在内核态执行时产生异常、进程收到SIGKILL等终止信号。 进程创建 Linux系统中，创建进程用户空间一般有3个函数，fork、vfork、clone，3个函数最终调用的是kernel_clone（旧一点的内核版本调用_do_fork）。 fork：子进程是父进程的翻版，完成复制了一份栈、数据段、堆、文件等等。在操作系统中使用写时复制的技术，当fork一个进程后，父子进程是共享一份系统资源的，当父进程或子进程有任一进程有写操作时，就会触发缺页异常复制一份属于自己的一份资源，从此父子进程的这类资源无任何关系。 vfork：fork和vfork函数类似，vfork的父进程会一直阻塞，直到子进程调用exit或者execve为止。vfork比fork实现多了两个标志位，分别是CLONE_VFORK和CLONE_VM。CLONE_VFORK会让父进程被挂起，直到子进程释放虚拟内存资源，CLONE_VM表示父子进程执行在相同的进程地址空间中。vfork与fork的区别是，父子进程是共享内存空间的，也就是说子进程修改了内存，父进程也会受影响。同时父进程需要等待子进程运行结束才能运行。vfork最初的设计是系统没有MMU而设计的，没法实现COW机制。 clone：Clone通常用于创建用线程，在linux系统中没有专门的线程，而是把线程当成普通进程来看待，在内核中还是以task_struct数据结构来描述线程，并没有使用特殊的数据结构或者调度算法来描述线程。Clone函数功能强调，可以传递众多参数，可以有选择性的继承父进程的资源（共享使用），如可以和vfork一样，与父进程共享一个进程地址空间，从而创建线程，也可以不和父进程共享进程地址空间，甚至可以创建兄弟关系进程。 写时复制 子进程在被创建后，父子进程是共享所有资源的，当父进程或子进程任一进程先触发写操作，触发写保护缺页异常，然后复制一份页面内容。Linux使用写时复制技术使得创建新进程的开销变得很小，免去了复制父进程整个进程地址空间中的内容避免巨大开销，只需要复制父进程页表的一点开销。

进程标识 进程是程序加载到内存的执行过程。进程与程序相比用于操作系统的资源如内存空间、文件、signal等。对于进程的标识我们使用process id来标识（PID）。 线程是进程中活跃状态的实体，也是操作系统实际调度的基本单元。进程中的所有线程是共享一些资源的。在linux中，实际上不区分进程和线程，进程和线程都是task_struct结构体来描述。在linux中使用thread ID（TID）来标识进程中的线程，thread id在所属进程中是唯一的，在linux系统中也是全局唯一的。对于单线程的进程来说，process ID和thread ID是一样的；而对于多线程来说，每个线程有自己的thread ID，但是所有线程共享一个PID。 进程组是一组进程的集合，创建进程组主要是将一些拥有共同特性的进程组合起来便于管理，如可以发一个信号给一个进程组，则这个组内的进程都会收到该信号。任何一个进程都不是独立存在的，一定是属于某个进程组，当fork的时候进程就归属到创建这所属的进程组。进程组用process group ID（PGID）来标识，进程组内的所有进程都有相同的GPID，等于该组组长的PID。可以通过setpgid、getpgid、setpgrp和getpgrp等接口函数访问PGID。 会话是一个用户登录后会创建一个会话，这个会话用sesssion ID（SID）来进行标识。登录的第一个进程较会话领头进程，通常是shell/bash。领头进程PID=SID。用户登录系统后，不断提交任务给操作系统，最后退出登录，就会销毁该session。可以通过getsid，setid来操作SID。 命名空间是用来隔离内核资源的，当一个进程运行在linux系统上的时候，它就拥有了很多系统资源如PID，网络设备，文件系统等。Linux内核通过namespace可以让一些进程只能看到与自己相关的一部分资源，而另外一些进程也只能看到与他们自己相关的资源，让互不联系的进程感觉不到对方的存在。目前linux现有的namespace有如下7种： namespace 隔离内容 Cgroup Cgoup root directory IPC System V IPC，POSIX消息队列 Network 网络设备、栈、端口等 Mount 挂载点 PID 进程ID User 用户和组ID UTS 主机名和NIS域名 与namespace相关的函数只有三个clone,setns,unshare。分别是创建一个进程放到对应namespace，将当前进程加入到已知namespace，退出指定类型namespace并加如到创建的namespace。 PID命名空间对进程PID重新标号，即不同的namespace下进程可以有同一个PID，如下容器1的a和容器2的a。他们分别对应在内核空间是PID namespace 1和PID namespace2。内核种为所有的PID namespace维护了一个树状结构，最顶层的是系统初始化创建的，被称为root namespace，由他创建的新的PID namespace成为它的chid namespace。父节点是可以看到字节点种的进程的，可以通过信号对子节点的进程产生影响，但是子节点无法看到父节点的进程。PID namespace对容器应用特别重要，可以实现容器内进程的暂停/恢复等功能，还可以支持容器在跨主机的迁移前后保持内部进程的PID不发生变化。 进程描述 Linux系统要对进程进行操作，需要抽象出所拥有的资源，我们称为进程控制块（Process Control Block，PCB），也称为进程描述符号，Linux中使用struct task_struct结构体来进行描述。task_struct数据结构包含的内容可以归类为几类： 进程属性相关。 进程间的关系。 进程调度相关信息。 内存管理相关信息。 文件管理相关信息。 信号相关信息。 资源限制相关信息。 上图中列出了task_struct数据结构中包含的一些内容。在linux中，进程和线程都是使用task_struct来进行描述。 进程状态 就绪态：进程获得了可以运行的所有资源和准备条件 运行态：CPU正在运行该进程。（linux中就绪态和运行态都是TASK_RUNNING） 浅度睡眠：进程需要某些资源不满足而进入等待，当条件满足时转为就绪队列。 深度睡眠：与浅度睡眠不同的时，进程睡眠等待不受干扰，不响应信号，如SIGKILL信号无法终止。 暂停：进程运行停止 僵死：进程已经消亡，但是task_struct数据结构还没有释放，父进程通过wait来获取子进程消亡原因。僵死进程已经放弃了几乎所有的内存空间，不会再执行代码，也不能被调度。之所以产生僵死进程时因为其父进程没有调用wait函数来等待子进程结束（父进程没来收尸，就变僵尸了），如果父进程异常退出了，那么init进程会自动接手这个子进程，也就是说父进程还活着，但是并没有调用wait来清除子进程。 进程间的关系 linux内核启动时，会创建一个init_task进程，这是系统中所有进程的祖先，称为进程0或idle进程，当系统没有进程调度时，调度器就会运行idle进程。在smp中，每个cpu都有一个进程0。在执行kernel_init函数后，会启动进程1（用户第一个进程），进程1是所有用户进程的祖先，可以通过pstree来查看进程关系。 上图中，procd等同于init，有用openwrt的1号进程使用的是procd，当然也可以改成init。 Linux系统中task_struct数据结构使用4个成员来描述进程间的关系，如下： real_parent: 指向创建当前进程的进程描述描述符，如果创建的进程不存在，则指向init进程。 parent:指向进程当前的父进程，通常和real_parent一致。 children:指向其子进程，所有的子进程被链接到这个链表上。 sibling:指向兄弟进程，所有的兄弟进程链接成一个链表。 获取当前进程 系统运行时，调度操作的数据结构就是task_struct，因此在系统调度时要运行进程，必现要找到对应进程的task_struct结构体。Linux内核提供了current宏来方便快速找到当前要运行或正在运行的task_struct数据结构。 current的实现和具体的架构有关，通常有两类实现方式。在ARM32系统中，存放了一个thread_info的数据结构在内核栈里面，current宏通过arm32的SP寄存器来获取当前内核栈的地址，对齐后即可获取到thread_info数据结构的指针，最后通过thread_info->task成员获取task_struct数据结构。 在linux 5.0内核中，新增了一个配置选项CONFIG_THREAD_INFO_IN_TASK，将thread_info存放在task_struct数据结构中。在ARM64处理上，利用SP_EL0寄存器粗放囊当前进程的task_struct数据结构的地址。