分析Linux内核调度器源码之初始化

void __init sched_init(void)
{
    unsigned long ptr = 0;
    int i;
 
    /*
     * 初始化全局默认的rt和dl的CPU带宽控制数据结构
     *
     * 这里的rt_bandwidth和dl_bandwidth是用来控制全局的DL和RT的使用带宽，防止实时进程
     * CPU使用过多，从而导致普通的CFS进程出现饥饿的情况
     */
    init_rt_bandwidth(&def_rt_bandwidth, global_rt_period(), global_rt_runtime());
    init_dl_bandwidth(&def_dl_bandwidth, global_rt_period(), global_rt_runtime());
 
#ifdef CONFIG_SMP
    /*
     * 初始化默认的根域
     *
     * 根域是dl/rt等实时进程做全局均衡的重要数据结构，以rt为例
     * root_domain->cpupri 是这个根域范围内每个CPU上运行的RT任务的最高优先级，以及
     * 各个优先级任务在CPU上的分布情况，通过cpupri的数据，那么在rt enqueue/dequeue
     * 的时候，rt调度器就可以根据这个rt任务分布情况来保证高优先级的任务得到优先
     * 运行
     */
    init_defrootdomain();
#endif
 
#ifdef CONFIG_RT_GROUP_SCHED
    /*
     * 如果内核支持rt组调度(RT_GROUP_SCHED), 那么对RT任务的带宽控制将可以用cgroup
     * 的粒度来控制每个group里rt任务的CPU带宽使用情况
     *
     * RT_GROUP_SCHED可以让rt任务以cpu cgroup的形式来整体控制带宽
     * 这样可以为RT带宽控制带来更大的灵活性(没有RT_GROUP_SCHED的时候，只能控制RT的全局
     * 带宽使用，不能通过指定group的形式控制部分RT进程带宽)
     */
    init_rt_bandwidth(&root_task_group.rt_bandwidth,
            global_rt_period(), global_rt_runtime());
#endif /* CONFIG_RT_GROUP_SCHED */
 
    /* 为每个CPU初始化它的运行队列 */
    for_each_possible_cpu(i) {
        struct rq *rq;
 
        rq = cpu_rq(i);
        raw_spin_lock_init(&rq->lock);
        /*
         * 初始化rq上cfs/rt/dl的运行队列
         * 每个调度类型在rq上都有各自的运行队列，每个调度类都是各自管理自己的进程
         * 在pick_next_task()的时候，内核根据调度类优先级的顺序，从高到底选择任务
         * 这样就保证了高优先级调度类任务会优先得到运行
         *
         * stop和idle是特殊的调度类型，是为专门的目的而设计的调度类，并不允许用户
         * 创建相应类型的进程，所以内核也没有在rq里设计对应的运行队列
         */
        init_cfs_rq(&rq->cfs);
        init_rt_rq(&rq->rt);
        init_dl_rq(&rq->dl);
#ifdef CONFIG_FAIR_GROUP_SCHED
        /*
         * CFS的组调度(group_sched)，可以通过cpu cgroup来对CFS进行进行控制
         * 可以通过cpu.shares来提供group之间的CPU比例控制(让不同的cgroup按照对应
         * 的比例来分享CPU)，也可以通过cpu.cfs_quota_us来进行配额设定(与RT的
         * 带宽控制类似)。CFS group_sched带宽控制是容器实现的基础底层技术之一
         *
         * root_task_group 是默认的根task_group，其他的cpu cgroup都会以它做为
         * parent或者ancestor。这里的初始化将root_task_group与rq的cfs运行队列
         * 关联起来，这里做的很有意思，直接将root_task_group->cfs_rq[cpu] = &rq->cfs
         * 这样在cpu cgroup根下的进程或者cgroup tg的sched_entity会直接加入到rq->cfs
         * 队列里，可以减少一层查找开销。
         */
        root_task_group.shares = ROOT_TASK_GROUP_LOAD;
        INIT_LIST_HEAD(&rq->leaf_cfs_rq_list);
        rq->tmp_alone_branch = &rq->leaf_cfs_rq_list;
        init_cfs_bandwidth(&root_task_group.cfs_bandwidth);
        init_tg_cfs_entry(&root_task_group, &rq->cfs, NULL, i, NULL);
#endif /* CONFIG_FAIR_GROUP_SCHED */
 
        rq->rt.rt_runtime = def_rt_bandwidth.rt_runtime;
#ifdef CONFIG_RT_GROUP_SCHED
        /* 初始化rq上的rt运行队列，与上面的CFS的组调度初始化类似 */
        init_tg_rt_entry(&root_task_group, &rq->rt, NULL, i, NULL);
#endif
 
#ifdef CONFIG_SMP
        /*
         * 这里将rq与默认的def_root_domain进行关联，如果是SMP系统，那么后面
         * 在sched_init_smp的时候，内核会创建新的root_domain，然后替换这里
         * def_root_domain
         */
        rq_attach_root(rq, &def_root_domain);
#endif /* CONFIG_SMP */
    }
 
    /*
     * 注册CFS的SCHED_SOFTIRQ软中断服务函数
     * 这个软中断住要是周期性负载均衡以及nohz idle load balance而准备的
     */
    init_sched_fair_class();
 
    scheduler_running = 1;
}

/*
 * Called by boot processor to activate the rest.
 *
 * 在SMP架构里，BSP需要将其他的非boot cp全部bring up
 */
void __init smp_init(void)
{
    int num_nodes, num_cpus;
    unsigned int cpu;
 
    /* 为每个CPU创建其idle thread */
    idle_threads_init();
    /* 向内核注册cpuhp线程 */
    cpuhp_threads_init();
 
    pr_info("Bringing up secondary CPUs ...\n");
 
    /*
     * FIXME: This should be done in userspace --RR
     *
     * 如果CPU没有online，则用cpu_up将其bring up
     */
    for_each_present_cpu(cpu) {
        if (num_online_cpus() >= setup_max_cpus)
            break;
        if (!cpu_online(cpu))
            cpu_up(cpu);
    }
     
    .............
}

/*
 * Topology list, bottom-up.
 *
 * Linux默认的物理拓扑结构
 *
 * 这里只有三级物理拓扑结构，NUMA域是在sched_init_numa()自动检测的
 * 如果存在NUMA域，则会添加对应的NUMA调度域
 *
 * 注：这里默认的 default_topology 调度域可能会存在一些问题，例如
 * 有的平台不存在DIE域(intel平台)，那么就可能出现LLC与DIE域重叠的情况
 * 所以内核会在调度域建立好后，在cpu_attach_domain()里扫描所有调度
 * 如果存在调度重叠的情况，则会destroy_sched_domain对应的重叠调度域
 */
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, },
};

/*
 * NUMA调度域初始化(根据硬件信息创建新的sched_domain_topology物理拓扑结构)
 *
 * 内核在默认情况下并不会主动添加NUMA topology，需要根据配置(如果开启了NUMA)
 * 如果开启了NUMA，这里就要根据硬件拓扑信息来判断是否需要添加
 * sched_domain_topology_level 域(只有添加了这个域之后，内核才会在后面初始化
 * sched_domain的时候创建NUMA DOMAIN)
 */
void sched_init_numa(void)
{
    ...................
    /*
     * 这里会根据distance检查是否存在NUMA域(甚至存在多级NUMA域)，然后根据
     * 情况将其更新到物理拓扑结构里。后面的建立调度域的时候，就会这个新的
     * 物理拓扑结构来建立新的调度域
     */
    for (j = 1; j < level; i++, j++) {
        tl[i] = (struct sched_domain_topology_level){
            .mask = sd_numa_mask,
            .sd_flags = cpu_numa_flags,
            .flags = SDTL_OVERLAP,
            .numa_level = j,
            SD_INIT_NAME(NUMA)
        };
    }
 
    sched_domain_topology = tl;
 
    sched_domains_numa_levels = level;
    sched_max_numa_distance = sched_domains_numa_distance[level - 1];
 
    init_numa_topology_type();
}

/*
 * Set up scheduler domains and groups.  For now this just excludes isolated
 * CPUs, but could be used to exclude other special cases in the future.
 */
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();
    ndoms_cur = 1;
    doms_cur = alloc_sched_domains(ndoms_cur);
    if (!doms_cur)
        doms_cur = &fallback_doms;
    /*
     * doms_cur[0] 表示调度域需要覆盖的cpumask
     *
     * 如果系统里用isolcpus=对某些CPU进行了隔离，那么这些CPU是不会加入到调度
     * 域里面，即这些CPU不会参于到负载均衡(这里的负载均衡包括DL/RT以及CFS)。
     * 这里用 cpu_map & housekeeping_cpumask(HK_FLAG_DOMAIN) 的方式将isolate
     * cpu去除掉，从而在保证建立的调度域里不包含isolate cpu
     */
    cpumask_and(doms_cur[0], cpu_map, housekeeping_cpumask(HK_FLAG_DOMAIN));
    /* 调度域建立的实现函数 */
    err = build_sched_domains(doms_cur[0], NULL);
    register_sched_domain_sysctl();
 
    return err;
}

/*
 * Build sched domains for a given set of CPUs and attach the sched domains
 * to the individual CPUs
 */
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;
    struct sched_domain_topology_level *tl_asym;
    bool has_asym = false;
 
    if (WARN_ON(cpumask_empty(cpu_map)))
        goto error;
 
    /*
     * Linux里的绝大部分进程都为CFS调度类，所以CFS里的sched_domain将会被频繁
     * 的访问与修改(例如nohz_idle以及sched_domain里的各种统计)，所以sched_domain
     * 的设计需要优先考虑到效率问题，于是内核采用了percpu的方式来实现sched_domain
     * CPU间的每级sd都是独立申请的percpu变量，这样可以利用percpu的特性解决它们
     * 间的并发竞争问题(1、不需要锁保护 2、没有cachline伪共享)
     */
    alloc_state = __visit_domain_allocation_hell(&d, cpu_map);
    if (alloc_state != sa_rootdomain)
        goto error;
 
    tl_asym = asym_cpu_capacity_level(cpu_map);
 
    /*
     * Set up domains for CPUs specified by the cpu_map:
     *
     * 这里会遍历cpu_map里所有CPU，为这些CPU创建与物理拓扑结构对应(
     * for_each_sd_topology)的多级调度域。
     *
     * 在调度域建立的时候，会通过tl->mask(cpu)获得cpu在该级调度域对应
     * 的span(即cpu与其他对应的cpu组成了这个调度域)，在同一个调度域里
     * 的CPU对应的sd在刚开始的时候会被初始化成一样的(包括sd->pan、
     * sd->imbalance_pct以及sd->flags等参数)。
     */
    for_each_cpu(i, cpu_map) {
        struct sched_domain_topology_level *tl;
 
        sd = NULL;
        for_each_sd_topology(tl) {
            int dflags = 0;
 
            if (tl == tl_asym) {
                dflags |= SD_ASYM_CPUCAPACITY;
                has_asym = true;
            }
 
            sd = build_sched_domain(tl, cpu_map, attr, sd, dflags, i);
 
            if (tl == sched_domain_topology)
                *per_cpu_ptr(d.sd, i) = sd;
            if (tl->flags & SDTL_OVERLAP)
                sd->flags |= SD_OVERLAP;
            if (cpumask_equal(cpu_map, sched_domain_span(sd)))
                break;
        }
    }
 
    /*
     * Build the groups for the domains
     *
     * 创建调度组
     *
     * 我们可以从2个调度域的实现看到sched_group的作用
     * 1、NUMA域 2、LLC域
     *
     * numa sched_domain->span会包含NUMA域上所有的CPU，当需要进行均衡的时候
     * NUMA域不应该以cpu为单位，而是应该以socket为单位，即只有socket1与socket2
     * 极度不平衡的时候才在这两个SOCKET间迁移CPU。如果用sched_domain来实现这个
     * 抽象则会导致灵活性不够(后面的MC域可以看到)，所以内核会以sched_group来
     * 表示一个cpu集合，每个socket属于一个sched_group。当这两个sched_group不平衡
     * 的时候才会允许迁移
     *
     * MC域也是类似的，CPU可能是超线程，而超线程的性能与物理核不是对等的。一对
     * 超线程大概等于1.2倍于物理核的性能。所以在调度的时候，我们需要考虑超线程
     * 对之间的均衡性，即先要满足CPU间均衡，然后才是CPU内的超线程均衡。这个时候
     * 用sched_group来做抽象，一个sched_group表示一个物理CPU(2个超线程)，这个时候
     * LLC保证CPU间的均衡，从而避免一种极端情况：超线程间均衡，但是物理核上不均衡
     * 的情况，同时可以保证调度选核的时候，内核会优先实现物理线程，只有物理线程
     * 用完之后再考虑使用另外的超线程，让系统可以更充分的利用CPU算力
     */
    for_each_cpu(i, cpu_map) {
        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;
            }
        }
    }
 
    /*
     * Calculate CPU capacity for physical packages and nodes
     *
     * sched_group_capacity 是用来表示sg可使用的CPU算力
     *
     * sched_group_capacity 是考虑了每个CPU本身的算力不同(最高主频设置不同、
     * ARM的大小核等等)、去除掉RT进程所使用的CPU(sg是为CFS准备的，所以需要
     * 去掉CPU上DL/RT进程等所使用的CPU算力)等因素之后，留给CFS sg的可用算力(因为
     * 在负载均衡的时候，不仅应该考虑到CPU上的负载，还应该考虑这个sg上的CFS
     * 可用算力。如果这个sg上进程较少，但是sched_group_capacity也较小，也是
     * 不应该迁移进程到这个sg上的)
     */
    for (i = nr_cpumask_bits-1; i >= 0; i--) {
        if (!cpumask_test_cpu(i, cpu_map))
            continue;
 
        for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
            claim_allocations(i, sd);
            init_sched_groups_capacity(i, sd);
        }
    }
 
    /* Attach the domains */
    rcu_read_lock();
    /*
     * 将每个CPU的rq与rd(root_domain)进行绑定，并且会检查sd是否有重叠
     * 如果是的则需要用destroy_sched_domain()将其去掉(所以我们可以看到
     * intel的服务器是只有3层调度域，DIE域其实与LLC域重叠了，所以在这里
     * 会被去掉)
     */
    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);
    }
    rcu_read_unlock();
 
    if (has_asym)
        static_branch_inc_cpuslocked(&sched_asym_cpucapacity);
 
    if (rq && sched_debug_enabled) {
        pr_info("root domain span: %*pbl (max cpu_capacity = %lu)\n",
            cpumask_pr_args(cpu_map), rq->rd->max_cpu_capacity);
    }
 
    ret = 0;
error:
    __free_domain_allocs(&d, alloc_state, cpu_map);
 
    return ret;
}