Linux内核源码分析 (3)调度器的实现

Linux内核源码分析 (3)调度器的实现

一、概述

• 每次调用调度器时，它会挑选具有最高等待时间的进程，把CPU提供给该进程。如果经常发生这种情况，那么进程的不公平待遇不会累积，不公平会均匀分布到系统中的所有进程。
• 下图说明了调度器如何记录哪个进程已经等待了多长时间。由于可运行进程是排队的，该结构称之为就绪队列
  
  所有的可运行进程都按时间在一个红黑树中排序，所谓时间即其等待时间。等待CPU时间最长的进程是最左侧的项，调度器下一次会考虑该进程。等待时间稍短的进程在该树上从左至右排序。在一个调度周期里面，所有进程的虚拟运行时间是相同的，所以在进程调度时，只需要找到虚拟运行时间最小的进程调度运行即可。

二、调度器数据结构

• 调度器使用一系列数据结构，来排序和管理系统中的进程。调度器的工作方式与这些结构的设计密切相关。几个组件在许多方面彼此交互。下面概述了这些组件的关联。下文中将这两个组件称为通用调度器（generic scheduler）或核心调度器（core scheduler）。
  
  • 主调度器：通过调用schedule()函数来完成进程的选择和切换。
  • 周期性调度器：根据固定频率自动调用scheduler_tick()函数，不时检测是否有必要进行进程切换。
  • 上下文切换：主要做两个事情（切换地址空间、切换寄存器和栈空间）
• 调度器类用于判断接下来运行哪个进程。内核支持不同的调度策略（完全公平调度、实时调度、在无事可做时调度空闲进程），调度类使得能够以模块化方法实现这些策略，即一个类的代码不需要与其他类的代码交互。在调度器被调用时，它会查询调度器类，得知接下来运行哪个进程。
• 在选中将要运行的进程之后，必须执行底层任务切换。这需要与CPU的紧密交互。
• 每个进程都刚好属于某一调度类，各个调度类负责管理所属的进程。通用调度器自身完全不涉及进程管理，其工作都委托给调度器类。

1、task_struct中与调度有关的的成员

include/linux/<sched.h>

struct task_struct { ... /*prio和normal_prio表示动态优先级，static_prio表示进程的静态优先级*/int prio, static_prio, normal_prio; /*表示实时进程的优先级,范围是[0,99]*/unsigned int rt_priority; /*表示该进程所属的调度器类*/const struct sched_class *sched_class; /*调度实体的实例。注意：调度器不限于调度进程，还可以处理更大的实体。这可以用于实现组调度：可用的CPU时间可以首先在一般的进程组（例如，所有进程可以按所有者分组）之间分配，接下来分配的时间在组内再次分配。*/struct sched_entity se; /*policy保存了对该进程应用的调度策略,Linux支持5种可能的值：SCHED_NORMAL：	通过完全公平调度器来处理，用于普通进程SCHED_BATCH：	通过完全公平调度器来处理，用于非交互、CPU使用密集的批处理进程，不会干扰交互式进程SCHED_IDLE：	通过完全公平调度器来处理，其相对权重总是最小的。SCHED_RR：		通过实时调度器处理，用于实现软实时进程，实现了一种循环方法SCHED_FIFO：	通过实时调度器处理，用于实现软实时进程，实现了一种先进先出机制。*/unsigned int policy; /*一个位域，在多处理器系统上使用，用来限制进程可以在哪些CPU上运行*/cpumask_t cpus_allowed; /*是一个表头，用于维护包含各进程的一个运行表，该成员实时调度器需要，不用于CFS*/struct list_head run_list; /*指定进程可使用CPU的剩余时间段，该成员实时调度器需要，不用于CFS*/unsigned int time_slice; ... 
}

2、调度器类

• 调度器类提供了通用调度器和各个调度方法之间的关联，Linux内核抽象一个调度类struct sched_class结构体表示调度类，具体内核源码如下：
  kernel/sched/<sched.h>

  struct sched_class {/*系统当中有多个调度类，按照调度优先级排成一个链表,下一优先级的高类*/const struct sched_class *next;#ifdef CONFIG_UCLAMP_TASKint uclamp_enabled;
  #endif/*将进程加入到执行队列当中,即将调度实体(进程)存放到红黑树中,并对nr_running变量自动会加1。（nr_running指定了队列上可运行进程的数目，不考虑其优先级或调度类）*/void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);/*从执行队列当中删除进程，并对nr_running变量自动减1 */void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);/*放弃CPU执行权，实际上该函数执行先出队后入队，在这种情况下，它直接将调度实体放在红黑树的最右端*/void (*yield_task)   (struct rq *rq);bool (*yield_to_task)(struct rq *rq, struct task_struct *p, bool preempt);/*用于检杳当前进程是否可被新进程抢占*/void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);/*选择下一个应用要运行的进程*/struct task_struct *(*pick_next_task)(struct rq *rq);/*将进程放回到运行队列当中*/void (*put_prev_task)(struct rq *rq, struct task_struct *p);void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);#ifdef CONFIG_SMPint (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);/*为进程选择一个合适的CPU */int  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);/*迁移任务到处一个CPU */void (*migrate_task_rq)(struct task_struct *p, int new_cpu);/*专门用于唤醍进程*/void (*task_woken)(struct rq *this_rq, struct task_struct *task);/*修改进程在CPU的亲和力*/void (*set_cpus_allowed)(struct task_struct *p,const struct cpumask *newmask);/*启动运行队列*/void (*rq_online)(struct rq *rq);/*禁止运行队列*/void (*rq_offline)(struct rq *rq);
  #endif/*调用自time tick函数，它可能引起进程切换，将驱动运行时(running)抢占*/void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);/* 进程创建时调用，不同调度策略的进程初始化也是不一样的 */void (*task_fork)(struct task_struct *p);/*进程退出时会使用*/void (*task_dead)(struct task_struct *p);/** The switched_from() call is allowed to drop rq->lock, therefore we* cannot assume the switched_from/switched_to pair is serliazed by* rq->lock. They are however serialized by p->pi_lock.*//*专门用于进程切换操作*/void (*switched_from)(struct rq *this_rq, struct task_struct *task);void (*switched_to)  (struct rq *this_rq, struct task_struct *task);/*更改进程的优先级*/void (*prio_changed) (struct rq *this_rq, struct task_struct *task,int oldprio);unsigned int (*get_rr_interval)(struct rq *rq,struct task_struct *task);void (*update_curr)(struct rq *rq);#define TASK_SET_GROUP		0
  #define TASK_MOVE_GROUP		1#ifdef CONFIG_FAIR_GROUP_SCHEDvoid (*task_change_group)(struct task_struct *p, int type);
  #endif
  };
  

• 调度器类可分为：stop_sched_class、dl_sched_class、rt_sched_class、fair_sched_class和idle_sched_class
  kernel/sched/<sched.h>

  extern const struct sched_class stop_sched_class;//停机调度类
  extern const struct sched_class dl_sched_class;//限期调度类
  extern const struct sched_class rt_sched_class;//实时调度类
  extern const struct sched_class fair_sched_class;//公平调度类
  extern const struct sched_class idle_sched_class;//空闲调度类
  

  这5种调度类的优先级从高到低依次为：停机调度类、限期调度类、实时调度类、公平调度类、空闲调度类。其中，SCHED_NORMAL、SCHED_BATCH和SCHED_IDLE直接被映射到fair_sched_class；SCHED_FIFO和SCHED_RR与rt_sched_class向关联。Linux调度核心选择下一个合适的task运行时，会按照优先级顺序遍历调度类的pick_next_task函数

  • 停机调度类：优先级是最高的调度类，停机进程是优先级最高的进程，可以抢占所有其它进程，其他进程不可能抢占停机进程.

    const struct sched_class stop_sched_class = {.next			= &dl_sched_class,.enqueue_task		= enqueue_task_stop,.dequeue_task		= dequeue_task_stop,.yield_task		= yield_task_stop,.check_preempt_curr	= check_preempt_curr_stop,.pick_next_task		= pick_next_task_stop,.put_prev_task		= put_prev_task_stop,.set_next_task          = set_next_task_stop,...
    };
    

  • 限期调度类：最早使用优先算法，使用红黑树把进程按照绝对截止期限从小到大排序，每次调度时选择绝对截止期限最小的进程。

    const struct sched_class dl_sched_class = {.next			= &rt_sched_class,.enqueue_task		= enqueue_task_dl,.dequeue_task		= dequeue_task_dl,.yield_task		= yield_task_dl,.check_preempt_curr	= check_preempt_curr_dl,.pick_next_task		= pick_next_task_dl,.put_prev_task		= put_prev_task_dl,.set_next_task		= set_next_task_dl,...
    };
    

  • 实时调度类：为每个调度优先级维护一个队列。

    const struct sched_class rt_sched_class = {.next			= &fair_sched_class,.enqueue_task		= enqueue_task_rt,.dequeue_task		= dequeue_task_rt,.yield_task		= yield_task_rt,.check_preempt_curr	= check_preempt_curr_rt,.pick_next_task		= pick_next_task_rt,.put_prev_task		= put_prev_task_rt,.set_next_task          = set_next_task_rt,...
    };
    

  • 公平调度类：使用完全公平调度算法。完全公平调度算法引入虚拟运行时间的相关概念：虚拟运行时间 = 实际运行时间 * nice为0对应的权重 / 进程的权重。

    const struct sched_class fair_sched_class = {.next			= &idle_sched_class,.enqueue_task		= enqueue_task_fair,.dequeue_task		= dequeue_task_fair,.yield_task		= yield_task_fair,.yield_to_task		= yield_to_task_fair,.check_preempt_curr	= check_preempt_wakeup,.pick_next_task		= __pick_next_task_fair,.put_prev_task		= put_prev_task_fair,.set_next_task          = set_next_task_fair,...
    };
    

  • 空闲调度类：每个CPU上有一个空闲线程，即0号线程。空闲调度类优先级最低，仅当没有其他进程可以调度的时候，才会调度空闲线程。

    const struct sched_class idle_sched_class = {/* .next is NULL *//* no enqueue/yield_task for idle tasks *//* dequeue is not valid, we print a debug message there: */.dequeue_task		= dequeue_task_idle,.check_preempt_curr	= check_preempt_curr_idle,.pick_next_task		= pick_next_task_idle,.put_prev_task		= put_prev_task_idle,.set_next_task          = set_next_task_idle,...
    };
    

• 观察上述5个调度类的next成员变量，可以发现他们是串联在一起的。Linux调度核心选择下一个合适的task运行时，会按照优先级顺序遍历调度类的pick_next_task函数。

3、就绪队列

• 核心调度器用于管理活动进程的主要数据结构称之为就绪队列。各个CPU都有自身的就绪队列，各个活动进程只出现在一个就绪队列中。在多个CPU上同时运行一个进程是不可能的（但发源于同一进程的各线程可以在不同处理器上执行，因为进程管理对进程和线程不作重要的区分）。
• 注意，进程并不是由就绪队列（rq）的成员直接管理的！这是各个调度器类（如stop_sched_class、dl_sched_class、rt_sched_class、fair_sched_class和idle_sched_class）的职责，因此在各个就绪队列中嵌入了特定于调度器类的子就绪队列（struct cfs_rq cfs;和struct rt_rq rt;）。
• 就绪队列主要使用下列数据结构实现
  kernel/sched.c

  struct rq { /*指定了队列上可运行进程的数目，不考虑其优先级或调度类*/unsigned long nr_running; 
  ... /*提供了就绪队列当前负荷的度量,队列的负荷本质上与队列上当前活动进程的数目成正比。*/struct load_weight load; #define CPU_LOAD_IDX_MAX 5 /*用于跟踪此前的负荷状态*/unsigned long cpu_load[CPU_LOAD_IDX_MAX]; /*cfs和rt是嵌入的子就绪队列，分别用于完全公平调度器和实时调度器。*/struct cfs_rq cfs; struct rt_rq rt; /*curr指向当前运行的进程的task_struct实例。idle指向idle进程的task_struct实例，该进程亦称为idle线程，在无其他可运行进程时执行*/struct task_struct *curr, *idle; /*用于实现就绪队列自身的时钟。每次调用周期性调度器时，都会更新clock的值。*/u64 clock; 
  ... 
  };
  

• 系统的所有就绪队列都在runqueues数组中，该数组的每个元素分别对应于系统中的一个CPU。在单处理器系统中，由于只需要一个就绪队列，数组只有一个元素。
  kernel/sched.c

  static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
  

4、调度实体

• 由于调度器可以操作比进程更一般的实体（进程嵌入了sched_entity实例，所以进程是可调度实体，还有更大的可调度实体比如组调度等 ），因此需要一个适当的数据结构来描述此类实体。其定义如下：
  include/linux/<sched.h>

  struct sched_entity { /*用于负载均衡,决定了各个实体占队列总负荷的比例*/struct load_weight load; /*run_node是标准的树结点，使得实体可以在红黑树上排序*/struct rb_node run_node; /*表示该实体当前是否在就绪队列上接受调度*/unsigned int on_rq; /*记录消耗的CPU时间，以用于完全公平调度器。跟踪运行时间是由update_curr不断累积完成的，调度器中许多地方都会调用该函数，例如，新进程加入就绪队列时，或者周期性调度器中。每次调用时，会计算当前时间和exec_start之间的差值，exec_start则更新到当前时间。差值则被加到sum_exec_runtime。*/u64 sum_exec_runtime; u64 exec_start; /*在进程执行期间虚拟时钟上流逝的时间数量*/u64 vruntime; /*在进程被撤销CPU时，其当前sum_exec_runtime值保存到prev_exec_runtime。此后，在进程抢占时又需要该数据。注意：此过程并不会更新sum_exec_runtime。*/u64 prev_sum_exec_runtime; 
  ... 
  }
  

三、处理优先级

1、优先级的内核表示

• 在用户空间可以通过nice命令设置进程的静态优先级，这在内部会调用nice系统调用。进程的nice值为[-20,+19]。值越低，表明优先级越高。内核使用范围[0,139]来表示内部优先级。同样是值越低，优先级越高。实时进程范围为[0,99]。nice值[-20, +19]映射到范围100到139。如下图所示，实时进程的优先级总是比普通进程更高。
  
• Linux内核优先级源码如下：
  include/linux/sched/<prio.h>

  #define MAX_NICE	19
  #define MIN_NICE	-20/*nice值的范围*/
  #define NICE_WIDTH	(MAX_NICE - MIN_NICE + 1)/*实时进程最大优先级（不包含）*/
  #define MAX_USER_RT_PRIO	100 
  #define MAX_RT_PRIO		MAX_USER_RT_PRIO/*普通进程最大优先级（不包含）*/
  #define MAX_PRIO		(MAX_RT_PRIO + NICE_WIDTH) // 140#define DEFAULT_PRIO		(MAX_RT_PRIO + NICE_WIDTH / 2) // 120
  

2、计算优先级

• 由前文可知，task_struct采用了4个成员来表示进程的优先级：prio和normal_prio表示动态优先级，static_prio表示进程的静态优先级。rt_priority表示进程的实时优先级，只对实时进程有用。
  • 静态优先级static_prio是进程启动时分配的优先级。它可以用nice和sched_setscheduler系统调用修改，否则在进程运行期间会一直保持恒定。
  • 正常优先级normal_priority表示基于进程的静态优先级和调度策略计算出的优先级。因此，即使普通进程和实时进程具有相同的静态优先级，其普通优先级也是不同的。进程分支时，子进程会继承普通优先级。
  • 调度优先级prio被调度器考虑，数值越小 , 优先级越高 。一般情况下 prio 字段 等于 normal_prio 字段。 特殊情况 : 在锁同步机制中 , 如果 A 进程 占有了 实时互斥锁 , B 进程 等待该 实时互斥锁 , 假如 B 进程的优先级 高于 A 进程 的优先级 , 此时就会将 占有 实时互斥锁 的 A 进程的 prio 优先级 提高到与 B 进程 prio 优先级相等的地位 ;
  • 实时优先级rt_priority：对于“限期进程”和“普通进程”来说字段值总为0, 没有意义。对于“实时进程”来说，值为1~99, 其数值越大 , 优先级越高。
• 各种进程的四种优先级总结
  

3、计算负荷权重

• 进程的重要性不仅是由优先级指定的，而且还需要考虑保存在task_struct->se.load的负荷权重。负荷权重包含在数据结构load_weight中。set_load_weight负责根据进程类型及其静态优先级计算负荷权重。
• 进程每降低一个nice值，则多获得10%的CPU时间，每升高一个nice值，则放弃10%的CPU时间。为执行该策略，内核将优先级转换为权重值。我们首先看一下转换表。
  kernel/sched.c

  static const int 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, 
  };
  

  对内核使用的范围[0, 39]中的每个nice级别，该数组中都有一个对应项。在计算CFS算法虚拟运行时间是会用到nice级别为0权重值，该权重值为1024。执行转换的代码也需要考虑实时进程。实时进程的权重是普通进程的两倍。另一方面，SCHED_IDLE进程的权重总是非常小。

四、核心调度器

1、周期性调度器

2、主调度器

3、与fork交互

4、上下文切换