(注：基于4.4.42内核)

摘要

    我们使用fork()等类似系统调用创建一个任务时，内核会调用_do_fork() --> copy_process()为新任务创建、初始化task_struct以及thread_info等任务相关信息。
    在任务相关的主要数据结构task_struct创建好后，还需要根据任务调度类型，将任务挂到相应的运行队列上，以便有机会得到调度。这是通过wake_up_new_task()来实现。针对实时任务，会将新创建的rt任务挂到其所属的优先级运行队列rt_rq的优先级队列queue[prio]上。

一、整体流程

    内核在do_fork()的copy_process()阶段为新任务分配好了task_struct，并为其分配了内核堆栈，还指定了一个默认的运行cpu---即继承于parent的cpu。
    但这仅仅是第一步，针对我们这里讨论的实时任务，接下来还需要做如下事情以便cpu能够调度到新任务：
      1) 如果当前默认知道的cpu不适合新任务运行，就通过select_task_rq() 为新任务选择一个合适的cpu；
      2) 调用set_task_cpu()，根据第1步选择的cpu(有可能是新的cpu，也有可能就是原来默认的)设置新任务的运行cpu、运行队列rt_rq 、rt_se.parent ;
      3) 调用activate_task(rq，p，0)来将任务挂到运行队列rt_rq.active.queue[prio]上；

      4) 检查新任务是否需要抢占当前任务，如果条件具备则将当前任务(rq->curr)调度出去；

      5) 调用task_woken_rt()对当前cpu进行均衡。

     这些事情是在 wake_up_new_task()中来完成的。

二、选择cpu：select_task_rq()

    虽然内核在do_fork()的第一阶段copy_process()虽然已经为新创建的RT任务指定了一个运行cpu，但是这个cpu并不一定适合新任务运行，甚至新任务根本无法在这个默认cpu上得到运行。

    因此，出于亲和性以及负载均衡等等原因需要检查这个默认cpu是否适合新任务运行；如果不适合，就需要为其重新找一个运行cpu，这是通过函数select_task_rq(struct task_struct *p, int cpu, int sd_flags, int wake_flags)来实现的。

调用的流程为：

        wake_up_new_task(p)
            | set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0));

    其中参数p是新创建的实时任务的task_struct结构指针；cpu是新任务thread_info->cpu，也就是来自父进程的默认cpu；sd_flags为SD_BALANCE_FORK表示需要考虑负载均衡；wake_flags为0表示将新任务挂载运行队列的尾端；函数的返回值即是任务新选择的cpu。

2.1 检查默认cpu是否适合新任务

    由于新任务的许多内容都是复制于父进程，因而如果新任务就在被创建时的这个cpu上运行可以充分利用缓存；另一方面，如果有亲和性限制或者负载均衡方面的考虑有可能使得新任务不适合在默认cpu上运行，所以这里需要判断以做出正确选择：
    这就需要进行检查判断：
     1) p-＞nr_cpus_allowed ＞1 &&
     2) curr存在 &&
     3) curr-＞prio ＜ 100 &&
     4) ((curr-＞nr_cpus_allowed ＜ 2) || (curr-＞prio ＜= p-＞prio))
    其中，curr是当前就绪队列上正在运行的任务，即rq->curr，p是新创建的RT任务。
    如果上面4个条件依次满足，才会考虑为新任务寻找一个新的运行cpu，否则还是使用原来默认的cpu。

2.2 为新任务另寻新的cpu

    如果2.1中4个条件都依次满足，则需要通过find_lowest_rq(struct task_struct *task)函数为新任务task选择一个新的合适的运行cpu，调用链为：

        wake_up_new_task(p)
           | set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0));
               | find_lowest_rq(struct task_struct *task)

    这个查找选择的流程如下所示：

     1) 先从task_rq(task)->rd->cpupri中寻找优先级最低的cpu集合，并求出此 最低优先级cpu集合 与task->cpus_allowed交集的集合，放到lowest_mask中，后续都优先在此集合中进行选择；
     2) 首先检查新任务的默认cpu是否在lowest_mask这个集合中，如果是，则选择此cpu返回；
     3) 其次在当前就绪队列所在的各级sched_domain中查找存在的cpu，如果当前运行的this_cpu在lowest_mask中，且this_cpu又在sched_domain中就优先选择此cpu；(why？因为，this_cpu是task迁移"相对便宜"的cpu);
     4) 否则就退而求此次选择lowest_mask与sched_domain中有交集的cpu； 
     5) 如果在各级sched_domain中也未能找到合适的cpu，就检查正在运行的this_cpu是否在lowest_mask中，如果是的话就选择当前正在运行的this_cpu作为新任务的cpu；
     6) 如果前面没有能找到符合要求的cpu，则就在lowest_mask中随便选择一个cpu返回，如果lowest_mask中压根就没有cpu，则返回-1。
    如果上面最终没有能够找到一个合适的cpu，则需要通过select_fallback_rq(int cpu, struct task_struct *p)在其他集合中为新任务选择一个cpu，但这种情况比较罕见。

三、指定运行cpu：set_task_cpu()

    在通过select_task_rq()为新任务选择了cpu后，就可以通过set_task_cpu(struct task_struct *p, unsigned int new_cpu)函数重新为新任务设置运行cpu和就绪队列rq，调用流程为：

        wake_up_new_task(p)
            | set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0));

    实际上指定cpu的意义并不仅仅在于设置任务的thread_info->cpu，更重要的是：为任务指定到此cpu的运行队列。 在引入组调度之后，调度器的组织呈现层级结构，每一个任务组在各个cpu上都有对应的调度队列。而且调度队列上挂着的不再只是任务，而是抽象出来的调度实体：它既可以表示一个任务也可以表示一个组。对于实时任务，对应的调度实体为：struct sched_rt_entity。

    一个实时任务用 task_struct.rt 成员来表示对应的调度实体sched_rt_entity；每个实时调度实体又根据优先级挂到优先级队列rt_rq.queue[prio]上。

    其中调度实体挂接到所属的运行队列rt_rq是sched_rt_entity.rt_rq来结构类型；同时，由于加入了组调度，调度实体还可能有自己所属的上层实体parent (注意：这个parent与我们将进程创建时的父进程不是一个领域也不是一个概念)，这个是用sched_rt_entity.parent来表示的。

    关于实时任务中的调度实体、运行队列、优先级数组等等相关组织结构可以参考《RT任务调度概览》中的示意图。

    而set_task_cpu()的主要任务就是为新任务p指定自己的运行队列和上层调度实体parent。

    在2.2节找到新任务的运行cpu后，就需要设置新任务所属的运行队列和所属的parent实体等等信息了。
      1) 通过 struct task_group tg = p->sched_task_group 找到新任务p所属的任务组；
      2) p->rt.rt_rq  = tg->rt_rq[new_cpu] ，设置新任务的运行队列。每个任务组task_group在创建的时候会在各个cpu上创建rt_rq和sched_rt_entity。
      3) p->rt.parent = tg->rt_se[cpu]，设置新任务的调度实体parent。
    这样，新任务p就找到了自己归属的运行队列p->rt.rt_rq以及自己的上层调度实体p->rt.parent。

四、加入就绪队列

4.1 组织结构

    我们知道一个任务要得到cpu的调度，必须要加入到运行队列才有可能得到垂青。在第二节和第三节已经分别通过select_task_rq()和set_task_cpu()为新建的实时任务指定了运行cpu和合适运行队列，现在是时候将其挂到运行队列接受调度器的检验了。代码流程：  

        wake_up_new_task(p)
            | set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0));
            | activate_task(rq, p, 0);

    新任务p加入到运行队列以等待调度就是由activate_task()来实现的。在探讨activate_task()函数如何把任务加入运行队列之前，我们来看下一个rt_rq的组织结构，以明确我们的新任务该往哪里放，该怎么放，放进去了会有什么影响。

/* Real-Time classes' related field in a runqueue: */
struct rt_rq {
	struct rt_prio_array active;	/* 我们的调度实体最终是放到优先级数组active中 */
	unsigned int rt_nr_running;
#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
	struct {
		int curr; 		/* highest queued rt task prio */
#ifdef CONFIG_SMP
		int next; 		/* next highest */
#endif
	} highest_prio;
#endif
	......
	struct rq *rq;
	struct task_group *tg;
#endif
};

    这里展示了新任务相关的rt_rq结构成员，新任务最终的归属在优先级数组rt_rq.active成员中，其结构如下所示：

/*
 * This is the priority-queue data structure of the RT scheduling class:
 */
struct rt_prio_array {
	DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
	struct list_head queue[MAX_RT_PRIO];
};

    可以看到优先级数组结构有两个成员，一个是位图bitmap，一个是list_head数组。
    其中链表数组queue[]有MAX_RT_PRIO(即100)个list_head链表，每个链表上挂的任务都具有同一个优先级，即实时任务0~99个优先级，每个任务根据优先级挂到queue[MAX_RT_PRIO]数组的不同链表上；
    而bitmap的作用则是一个位图，实际是一个unsigned long型的数组，用以表示优先级队列queue[]上哪个优先级的队列上挂着调度实体，哪些队列是空的。
    新任务创建好后，最终最终是要根据自己的优先级prio，挂到自己p->rt.rt_rq(这个rt_rq在第三节已经指定妥当)中的active.queue[prio]队列上。

4.2 详细流程

    我们看看activate_task函数的主要处理流程：      

      activate_task(rq, p, 0)
        | enqueue_task(rq, p, flags)
            | update_rq_clock(rq);
            | enqueue_task_rt(rq, p, flags)
                | enqueue_rt_entity(rt_se, flags & ENQUEUE_HEAD)
                | enqueue_pushable_task(rq, p)

    我们已经知道现在的调度器中实际上是将调度组和任务抽象成了调度实体，所以任务入队，也就是调度实体rt_se入队的主要工作是由函数 enqueue_rt_entity(rt_se, flags & ENQUEUE_HEAD) 来完成。

    同时，由于组调度的层级关系，一个调度实体的优先级和调度信息都依赖于其子层级的调度实体和task。例如一个组的优先级就是其下属的优先级最高的那个task。因此实时调度中一个调度实体的“入队”、“出队”可以说是牵一发而动全身，其parent，parent的parent.....其所有的祖先都需要随之发生动荡。

    因此新任务加入到运行队列这个过程是相当复杂的。

    整个流程如下所示：
    1) 将rt_se及其所有祖先的各个调度实体从上到下层(top-rt_se到该rt_se)依次出队；
      1.1) 将rt_se的各个层级祖先从上往下组织起来；
      1.2) 更新rq->nr_running -= rt_rq->rt_nr_running;
      1.3) 从rt_se的顶层祖先开始，从上到下调用__dequeue_rt_entity(rt_se)将各个rt_se出队。
        1.3.1) 将rt_se从其所在的优先级队列出队并更新优先级位图；
        1.3.2) rt_se出队后需要更新相关信息
          1.3.2.1) 更新rt_se->rt_rq的rt_nr_running，即减去rt_se中的rt_nr_running；
          1.3.2.2) dec_rt_prio(rt_rq, rt_se_prio(rt_se)) 更新rt_rq的优先级
            1.3.2.2.1)  更新rt_rq->highest_prio.curr;
            1.3.2.2.2) 如果需要出队的rt_se所在的rt_rq是top rt_rq且top rt_rq的优先级已经改变(可能是在2.1得到更新)，则更新rq所在cpu的 cpu priority。
          1.3.2.3) 调用dec_rt_migration()更新过载和迁移信息；
            1.3.2.3.1) 如果rt_se是一个task，则更新rt_rq->rt_nr_total 、rt_rq->rt_nr_migratory；
            1.3.2.3.2) 根据前面更新的rt_nr_total和rt_nr_migratory再更新rt_rq->overload 和 rq->rd->rto_mask；
          1.3.2.4) 如果rt_se是boosted的(rt_se或者rt_se->my_q上有优先级翻转的任务)，则需要更新rt_rq->rt_nr_boosted。
    2) 将rt_se及其所有祖先的各个调度实体从下到上层(从该rt_se到top-rt_se)依次入队；
      2.1) 如果rt_se不是任务而是一个组且 (调度受到限制或者组内没有可运行的实体)则返回；
      2.2) 否则将rt_se挂到对应优先级队列queue的尾部，并设置rt_se优先级对应的位图；
      2.3) rt_se入队后需要更新相关信息，如所属rt_rq的rt_nr_running、rt_rq的优先级、cpu优先级、过载和迁移信息以及rt_nr_boosted等等，参考__dequeue_rt_entity。
    3) 调用enqueue_top_rt_rq(&rq->rt)将top rt_rq入队
      3.1) 如果top rt_rq调度受限(rt_throttled标志置位 且 rt_rq中没有优先级翻转的task) 或者 top rt_rq没有就绪的实体则直接返回；
      3.2) 否则将top rt_rq的rt_nr_running统计到rq->nr_running中，并置rt_rq->rt_queued。
    最后，如果新加入到运行队列的任务不是正在运行的，即不是rq->curr且新任务没有亲和性限制，则将新任务加入到pushable链表中并更新就绪队列上的highest prio pushable task。

五、调度curr

    一旦新任务加入到了运行队列就有可能比当前任务更有运行资格，这个时候就需要检查是否需要将当前任务rq->curr调度出去，这是调用check_preempt_curr(rq, p, WF_FORK)来实现的。             

     wake_up_new_task(p)
        | set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0));
        | activate_task(rq, p, 0);
        | check_preempt_curr(rq, p, WF_FORK);

    实际上它完成的主要工作是检查：
      1) 如果新任务p->sched_class与当前任务rq->curr->sched_class相等，则调用sched_class->check_preempt_curr(rq, p, flags)检查rq->curr是否需要调度出去；
      2) 否则判断新任务p的调度类是否比rq->curr调度类优先级“高”，如果高则将rq上的当前任务调度出去。
    由于我们这里讨论的是实时任务，而实时调度类比系统中的大部分任务优先级要“高”，因而当前任务很有可能被调度出去。
    然而如果rq->curr任务也是实时调度类，则需要通过check_preempt_curr_rt()函数来进行检查：
      1) 如果rq->curr优先级小于新任务p的优先级，则当前任务rq->curr被调度出去；
      2) 如果rq->curr优先级与新任务p的优先级相等：
        2.1) 若rq->curr不可迁移只能期望将p迁移出去而不将rq->curr调度出去；
        2.2) 否则，若新任务p可以迁移那么就期望将p迁移出去，而不将rq->curr调度出去；
        2.3) 否则，就是rq->curr可迁移而新任务不可迁移的情况，此时就将rq->curr调度出去，使其有机会到其他cpu的rq上运行。

    这里的调度类优先级“高”、“低”是什么意思呢？我们知道现在的调度器有许多不同的调度类，如我们熟悉的实时调度rt_sched_class、公平调度fair_sched_class等等。这些调度类通过一个next指针组织成一个链表，链表越靠前面的调度类越容易被先被cpu"垂青"，这就是我这里所说的优先级“高”、“低”。系统中所有的调度类简单组织情况如下：

【stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class】 

    其中stop_sched_class没有真正参与调度；dl_sched_class属于dead_line调度类，这类任务没有优先级概念，是系统中最紧迫的任务(这个还没有研究过)。而我们平时关注任务一般都是是rt和fair调度类。

六、队列均衡

    由于我们先加了一个rt任务到当前cpu上，这个很可能引发此cpu上的rt任务过载而打乱了cpu上的负载均衡。这个时候就需要调用task_woken_rt(rq, p)来进行检查，以确定是否需要对当前的cpu的rq就绪队列执行push操作，即将当前cpu上的实时任务“推”到其他空闲的cpu上，以达到cpu负载均衡。关于实时任务负载均衡的问题后续再讨论，这里我们重点关注task_woken_rt(rq,p)在满足什么条件才会执行push。   

      1) 新任务p的p->on_cpu为0 && 
       2) 当前任务rq->curr没有设置need reschedule &&
      3) 新任务p没有cpu允许迁移 &&
      4) rq->curr是dead_line或者rt类型的任务 &&
      5) rq->curr不许迁移或者rq->curr优先级高于等于p的优先级。
    只有同时满足上面5个条件才会执行push_rt_tasks(rq)，以尝试将本cpu的rq中的任务“推”给其他cpu。

七、总结

    一个实时任务的整个创建流程(与调度相关的)的主要如下所示：

_do_fork()
  | copy_process()
  | wake_up_new_task()
  | select_task_rq()
  | set_task_cpu()
  | activate_task()
    | enqueue_task_rt()
  | check_preempt_curr()       
  | task_woken_rt()

    其中工作量最大的就是activate_task()，因为实时任务的入队流程是“牵一发而动全身”。当然，由于水平有限，许多小细节都没有分析的明白，还有待加强。有任何建议或者意见都欢迎交流、指正和讨论。