哪种语言做网站,商业网站开发实训报告总结,广告页面模板,ui设计难吗文章说明#xff1a; Linux内核版本#xff1a;5.0 架构#xff1a;ARM64 参考资料及图片来源#xff1a;《奔跑吧Linux内核》 Linux 5.0内核源码注释仓库地址#xff1a; zhangzihengya/LinuxSourceCode_v5.0_study (github.com)
1. 前置知识
1.1 CPU管理位图
内核…文章说明 Linux内核版本5.0 架构ARM64 参考资料及图片来源《奔跑吧Linux内核》 Linux 5.0内核源码注释仓库地址 zhangzihengya/LinuxSourceCode_v5.0_study (github.com)
1. 前置知识
1.1 CPU管理位图
内核对CPU的管理是通过位图bitmap变量来管理的并且定义了possible、present、online和active这4种状态
/* 位图类型变量 */
// 表示系统中有多少个可以运行现在运行或者将来某个时间点运行的 CPU 内核
#define cpu_possible_mask ((const struct cpumask *)__cpu_possible_mask)
// 表示系统中有多少个正处于运行online状态的 CPU 内核
#define cpu_online_mask ((const struct cpumask *)__cpu_online_mask)
// 表示系统中有多少个可处于运行状态的CPU内核它们不一定都处于运行状态有的CPU内核可能被热插拔了
#define cpu_present_mask ((const struct cpumask *)__cpu_present_mask)
// 表示系统中有多少个活跃的 CPU 内核
#define cpu_active_mask ((const struct cpumask *)__cpu_active_mask)#define DECLARE_BITMAP(name,bits) \unsigned long name[BITS_TO_LONGS(bits)]typedef struct cpumask { DECLARE_BITMAP(bits, NR_CPUS); } cpumask_t;name[]位图类型变量使用一个长整数类型数组name[]每位代表一个CPU。对于64位处理器来说一个长整数类型数组成员只能表示64个CPU内核。内核配置中有一个宏CONFIG_NR_CPUS为8那么只需要一个长整数类型数组成员可。struct cpumaskcpumask数据结构本质上是位图内核通常使用cpumask的相关接口函数来管理CPU内核数量。
CPU位图的初始化流程如下图所示 cpu_possible_mask通过查询系统DTS表或者ACPI表获取系统CPU内核数量cpu_present_mask等同于cpu_possible_maskcpu_active_mask是经过使能后的CPU内核数量
1.2 CPU调度域
根据系统的内存和高速缓存的布局CPU域可分为如下几类 Linux内核通过数据结构sched_domain_topology_level来描述CPU的层次关系简称为SDTL
// 用于描述 CPU 的层级关系
struct sched_domain_topology_level {sched_domain_mask_f mask; // 函数指针用于指定某个 SDTL 的 cpumask 位图// sd_flags 函数指针里指定了该调度层级的标志位sched_domain_flags_f sd_flags; // 函数指针用于指定某个 SDTL 的标志位int flags;int numa_level;struct sd_data data;
#ifdef CONFIG_SCHED_DEBUGchar *name;
#endif
};另外内核默认定义了一个数组default_topology[]来概括CPU物理域的层次结构
// CPU 拓扑关系从下往上
static struct sched_domain_topology_level default_topology[] {
#ifdef CONFIG_SCHED_SMT // 超线程// cpu_smt_mask() 函数描述了 SMT 层级的 CPU 位图组成方式{ cpu_smt_mask, cpu_smt_flags, SD_INIT_NAME(SMT) },
#endif
#ifdef CONFIG_SCHED_MC // 多核// cpu_coregroup_mask() 函数描述了 MC 层级的 CPU 位图组成方式{ cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) },
#endif // 处理器// cpu_cpu_mask() 函数描述了 DIE 层级的 CPU 位图组成方式{ cpu_cpu_mask, SD_INIT_NAME(DIE) },{ NULL, },
};从default_topology[]数组可知系统默认支持DIE层级、SMT层级以及MC层级。另外在调度域里划分调度组使用sched_group来描述调度组调度组是负载均衡调度的最小单位在最低层级的调度域中通常一个调度组描述一个CPU。
在一个支持NUMA架构的处理器中假设它支持SMT技术那么整个系统的调度域和调度组的关系如下图所示它在默认调度层级中新增一个NUMA层级的调度域 DIE表示处理器封装它是CPU拓扑结构中的一个层级在多核处理器中通常有多个物理处理器核心组成一个封装
在Linux内核中使用sched_domain数据结构来描述调度层级。在超大系统中系统会频繁访问调度域数据结构为了提升系统的性能和可扩展性调度域sched_domain数据结构采用Per-CPU变量来构建
// 描述调度层级
struct sched_domain {// 父调度域指针顶层调度域必须为 null 终止struct sched_domain *parent;// 子调度域指针底层调度域必须为 null 终止struct sched_domain *child;// groups 指向该调度域的平衡组链表struct sched_group *groups;// 最小平衡间隔毫秒unsigned long min_interval;// 最大平衡间隔毫秒unsigned long max_interval;...
};下面举例来说明CPU调度域的拓扑关系如下图所示假设在一个4核处理器中每个CPU拥有独立L1高速缓存且不支持超线程技术4个物理CPU被分成两个簇Cluster0和Cluster1每个簇包含两个物理CPU簇中的CPU共享L2高速缓存 因为每个CPU内核只有一个运行线程所以4核处理器没有SMT层级。簇由两个CPU组成这两个CPU处于MC层级且是兄弟关系。整个处理器可以看作处于DIE层级因此该处理器只有两个层级即MC和DIE。根据上述原则4核处理器的调度域和调度组的拓扑关系如下图所示 在每个SDTL都为每个CPU分配了对应的调度域和调度组以CPU0为例
对于DIE层级CPU0对应的调度域是domain_die_0该调度域管辖着4个CPU并包含两个调度组分别为group_die_0和group_die_1 调度组group_die_0管辖CPU0和CPU1调度组group_die_1管辖CPU2和CPU3 对于MC层级CPU0对应的调度域是domain_mc_0该调度域中管辖着CPU0和CPU1并包含两个调度组分别为group_mc_0和group_mc_1 调度组group_mc_0管辖CPU0调度组group_mc_1管辖CPU1
除此以外4核处理器的调度域和调度组还有两层关系如下图所示 综上所述为了提升系统的性能和可扩展性sched_domain数据结构采用Per-CPU变量来构建这样可以减少CPU之间的访问竞争。而sched_group数据结构则是调度域内共享的。
2. LLC调度域
在负载均衡算法中我们常常需要快速找到系统中最高层级的并且具有高速缓存共享属性的调度域。通常在—个系统我们把最后一级高速缓存Last Level CacheLLC称为LLC。在调度域标志位中SD_SHARE_PKG_RESOURCE标志位用于描述高速缓存的共享属性。因此在调度域层级中包含LLC的最高一级调度域称为LLC调度域。在Linux内核中实现一组特殊用途的指针用来指向LLC调度域这些指针是Per-CPU变量。查找和设置LLC调度域是在update_top_cache_domain()函数中实现的。在select_idle_cpu()等函数中会使用到LLC 调度域。
// 指向 LLC 调度域
DEFINE_PER_CPU(struct sched_domain *, sd_llc);
// LLC 调度域包含多少个 CPU
DEFINE_PER_CPU(int, sd_llc_size);
// LLC 调度域第一个 CPU 的编号
DEFINE_PER_CPU(int, sd_llc_id);
DEFINE_PER_CPU(struct sched_domain_shared *, sd_llc_shared);
DEFINE_PER_CPU(struct sched_domain *, sd_numa);
DEFINE_PER_CPU(struct sched_domain *, sd_asym_packing);
// 指向第一个包含不同 CPU 架构的调度域主要用于大/小核架构
DEFINE_PER_CPU(struct sched_domain *, sd_asym_cpucapacity);
DEFINE_STATIC_KEY_FALSE(sched_asym_cpucapacity);// 查找和设置 LLC 调度域
static void update_top_cache_domain(int cpu)
{...
}3. 负载均衡
负载均衡机制从注册软中断开始每次系统处理调度节拍时会检查当前是否需要处理负载均衡。负载均衡的流程如图所示 为了使读者有更真切的理解下文将根据流程图围绕源代码进行讲解这个过程
load_balance()
// this_cpu 指当前正在运行的 CPU
// this_rq 表示当前就绪队列
// sd 表示当前正在做负载均衡的调度域
// idle 表示当前 CPU 是否处于 IDLE 状态
// continue_balancing 表示当前调度域是否还需要继续做负载均衡
static int load_balance(int this_cpu, struct rq *this_rq,struct sched_domain *sd, enum cpu_idle_type idle,int *continue_balancing)
{...struct lb_env env {// 当前调度域.sd sd,// 当前的 CPU后面可能要把一些繁忙的进程迁移到该 CPU 上.dst_cpu this_cpu,// 当前 CPU 对应的就绪队列.dst_rq this_rq,// 当前调度域里的第一个调度组的 CPU 位图.dst_grpmask sched_group_span(sd-groups),.idle idle,// 本次最多迁移 32 个进程sched_nr_migrate_break全局变量的默认值为 32.loop_break sched_nr_migrate_break,// load_balance_mask 位图.cpus cpus,.fbq_type all,.tasks LIST_HEAD_INIT(env.tasks),};// 把 sd 调度域管辖的 CPU 位图复制到 load_balance_mask 位图里cpumask_and(cpus, sched_domain_span(sd), cpu_active_mask);schedstat_inc(sd-lb_count[idle]);redo:// should_we_balance() 函数判断当前 CPU 是否需要做负载均衡if (!should_we_balance(env)) {*continue_balancing 0;goto out_balanced;}// 查找该调度域中最繁忙的调度组group find_busiest_group(env);if (!group) {schedstat_inc(sd-lb_nobusyg[idle]);goto out_balanced;}// 在刚才找到的最繁忙的调度组中查找最繁忙的就绪队列busiest find_busiest_queue(env, group);if (!busiest) {schedstat_inc(sd-lb_nobusyq[idle]);goto out_balanced;}...// env.src_cpu 指向最繁忙的调度组中最繁忙的就绪队列中的 CPUenv.src_cpu busiest-cpu;// env.src_rq 指向最繁忙的就绪队列env.src_rq busiest;ld_moved 0;if (busiest-nr_running 1) {...// detach_tasks() 函数遍历最繁忙的就绪队列中所有的进程找出适合被迁移的进程然后让这些// 进程退出就绪队列。cur_ld_moved 变量表示已经迁出了多少个进程cur_ld_moved detach_tasks(env);...if (cur_ld_moved) {// attach_tasks() 函数把刚才从最繁忙就绪队列中迁出的进程都迁入当前 CPU 的就绪队列中attach_tasks(env);ld_moved cur_ld_moved;}...// 由于进程设置了 CPU 亲和性不能迁移进程到 dst_cpu因此还有负载没迁移完成需要换一个新的// dst_cpu 继续做负载迁移if ((env.flags LBF_DST_PINNED) env.imbalance 0) {...goto more_balance;}...}...
}load_balance()-should_we_balance()
// 判断当前 CPU 是否需要做负载均衡
static int should_we_balance(struct lb_env *env)
{// sg 指向调度域中的第一个调度组struct sched_group *sg env-sd-groups;...// 查找当前调度组是否有空闲 CPU如果有空闲 CPU那么使用变量 balance_cpu 记录该 CPUfor_each_cpu_and(cpu, group_balance_mask(sg), env-cpus) {if (!idle_cpu(cpu))continue;balance_cpu cpu;break;}// 查找该调度组有哪些 CPU 适合做负载均衡// 若调度组里有空闲 CPU则优先选择空闲 CPU// 调度组里没有空闲 CPU则选择调度组的第一个 CPUif (balance_cpu -1)balance_cpu group_balance_cpu(sg);// 然后判断适合做负载均衡的 CPU 是否为当前 CPU若为当前 CPU则 should_we_balance()函数返回true表示可以做负载均衡return balance_cpu env-dst_cpu;
}load_balance()-find_busiest_group()
// 查找该调度域中最繁忙的调度组
static struct sched_group *find_busiest_group(struct lb_env *env)
{...// 初始化 sd_lb_stats 结构体init_sd_lb_stats(sds);// 更新该调度域中负载的相关统计信息update_sd_lb_stats(env, sds);...// 如果没有找到最繁忙的调度组或者最繁忙的组中没有正在运行的进程那么跳过该调度域if (!sds.busiest || busiest-sum_nr_running 0)goto out_balanced;// 计算该调度域的平均负载sds.avg_load (SCHED_CAPACITY_SCALE * sds.total_load)/ sds.total_capacity;// 如果最繁忙的调度组的组类型是 group_imbalanced那么跳转到 force_balance 标签处if (busiest-group_type group_imbalanced)goto force_balance;...// 若本地调度组的平均负载比刚才计算出来的最繁忙调度组的平均负载还要大那么不需要做负载均衡if (local-avg_load busiest-avg_load)goto out_balanced;// 若本地调度组的平均负载比整个调度域的平均负载还要大那么不需要做负载均衡if (local-avg_load sds.avg_load)goto out_balanced;// 如果当前 CPU 处于空闲状态最繁忙的调度组里的空闲 CPU 数量大于本地调度组里的空闲 CPU 数量说明不需要做负载均衡if (env-idle CPU_IDLE) {if ((busiest-group_type ! group_overloaded) (local-idle_cpus (busiest-idle_cpus 1)))goto out_balanced;// 如果当前 CPU 不处于空闲状态那么比较本地调度组的平均量化负载和最繁忙调度组的平均量化负载这里使用了 imbalance_pct// 系数它在 sd_init() 函数中初始化默认值为125。若本地调度组的平均量化负载大于最繁忙组的平均量化负载说明该调度组不// 忙不需要做负载均衡。} else {if (100 * busiest-avg_load env-sd-imbalance_pct * local-avg_load)goto out_balanced;}force_balance:env-src_grp_type busiest-group_type;// 根据最繁忙调度组的平均量化负载、调度域的平均量化负载和本地调度组的平均量化负载来计算该调度域需要迁移的负载不均衡值calculate_imbalance(env, sds);// 返回最忙的调度组return env-imbalance ? sds.busiest : NULL;out_balanced:env-imbalance 0;return NULL;
}load_balance()-find_busiest_queue()
for_each_cpu_and()遍历该调度组里所有的CPU通过就绪队列的量化负载runnable_load_avg与CFS额定算力cpu_capacity的乘积来进行比较。使用weighted_cpuload()来获取cfs_rq-avg.runnable_load_avg的值通过capacity_of()来获取cpu_capacity的值。这里要考虑不同处理器架构计算能力的不同对处理器负载的影响。
注意数据结构rq中的cpu_capacity_orig成员指的是CPU的额定算力而cpu_capacity成员指的是CFS就绪队列的额定算力通常CFS额定算力最大能达到CPU额定算力的80。
load_balance()-detach_tasks()
// detach_tasks() 函数遍历最繁忙的就绪队列中所有的进程找出适合被迁移的进程
// 然后让这些进程退出就绪队列。返回值表示已经迁出了多少个进程
static int detach_tasks(struct lb_env *env)
{...// env-imbalance 表示还有多少不均衡的负载需要迁移if (env-imbalance 0)return 0;// while 循环遍历最繁忙的就绪队列中所有的进程while (!list_empty(tasks)) {...// 在can_migrate_task()函数中判断哪些进程可以迁移哪些进程不能迁移。// 不适合迁移的原因// 一是进程允许运行的CPU位图的限制cpus_allowed// 二是当前进程正在运行// 三是热高速缓存cache-hot的问题// 四如果进程负载的一半大于要迁移负载总量env-imbalance则该进程也不适合迁移if (!can_migrate_task(p, env))goto next;load task_h_load(p);if (sched_feat(LB_MIN) load 16 !env-sd-nr_balance_failed)goto next;if ((load / 2) env-imbalance)goto next;// detach_task()函数让进程退出就绪队列然后设置进程的运行CPU为迁移目的地CPU并设置p-on_rq为// TASK_ON_RQ_MIGRARINGdetach_task(p, env);// 把要迁移的进程添加到env-tasks链表中list_add(p-se.group_node, env-tasks);detached;// 递减不均衡负载总量 env-imbalanceenv-imbalance - load;...}return detached;
}load_balance()-attach_tasks()
// 把detach_tasks()分离出来的进程重新添加到目标就绪队列中
static void attach_tasks(struct lb_env *env)
{...// 遍历env-tasks链表while (!list_empty(tasks)) {...// 把进程添加到目标CPU的就绪队列中attach_task(env-dst_rq, p);}...
}
