住房与城乡建设部网站EPC,企业网站布局,丹东站,福州盈科网站建设有限公司怎么样Linux内核源码分析 (3)调度器的实现 文章目录 Linux内核源码分析 (3)调度器的实现一、概述二、调度器数据结构1、task_struct中与调度有关的的成员2、调度器类3、就绪队列4、调度实体 三、处理优先级1、优先级的内核表示2、计算优先级3、计算负荷权重 四、核心调度器1、周期性调…Linux内核源码分析 (3)调度器的实现 文章目录 Linux内核源码分析 (3)调度器的实现一、概述二、调度器数据结构1、task_struct中与调度有关的的成员2、调度器类3、就绪队列4、调度实体 三、处理优先级1、优先级的内核表示2、计算优先级3、计算负荷权重 四、核心调度器1、周期性调度器2、主调度器3、与fork交互4、上下文切换 一、概述
每次调用调度器时它会挑选具有最高等待时间的进程把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_classSCHED_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.cstruct 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.cstatic DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);4、调度实体
由于调度器可以操作比进程更一般的实体进程嵌入了sched_entity实例所以进程是可调度实体还有更大的可调度实体比如组调度等 因此需要一个适当的数据结构来描述此类实体。其定义如下 include/linux/sched.hstruct 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) // 1202、计算优先级
由前文可知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.cstatic 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、上下文切换
