做云词图的网站,钉钉crm客户管理系统,专业做动漫的网站,网站怎么做能赚钱《Linux内核源码分析》(3)调度器及CFS调度器 文章目录 《Linux内核源码分析》(3)调度器及CFS调度器一、调度器1、调度器2、调度类sched_class结构体3、优先级4、内核调度策略 二、CFS调度器1、CFS调度器基本原理2、调度子系统各个组件模块3、CFS调度器就绪队列内核源码 一、调度…《Linux内核源码分析》(3)调度器及CFS调度器 文章目录 《Linux内核源码分析》(3)调度器及CFS调度器一、调度器1、调度器2、调度类sched_class结构体3、优先级4、内核调度策略 二、CFS调度器1、CFS调度器基本原理2、调度子系统各个组件模块3、CFS调度器就绪队列内核源码 一、调度器
1、调度器
Linux内核中用来安排调度进程一段程序的执行过程执行的模块称为调度器(Scheduler),它可以切换进程状态(Process status)。比如执行、可中断睡眠、不可中断睡眠、退出、暂停等。 调度器相当于CPU中央处理器的管理员主要负责完成做两件事情: 选择某些就绪进程来执行打断某些执行的进程让它们变为就绪状态
2、调度类sched_class结构体 调度器类提供了通用调度器和各个调度方法之间的关联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、优先级
在用户空间可以通过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)4、内核调度策略
struct task_struct中有成员变量unsigned int policy指代保存进程的调度策略。Linux内核提供一些调度策略供用户应用程序来选择调度器。Linux内核调度策略源码分析如下 include/uapi/linux/sched.h/** Scheduling policies*//*用于普通进程通过CFS调度器实现。*/
#define SCHED_NORMAL 0/* 先进先出调度算法实时调度策略相同优先级任务先到先服务高优先级的任务可以抢占低优先级的任务 */
#define SCHED_FIFO 1/*轮流调度算法实时调度策略*/
#define SCHED_RR 2/*用于非交互处理器消耗型进程相当于SCHED_NORMAL分化版本采用分时策略根据动态优先级分配CPU运行需要资源*/
#define SCHED_BATCH 3/* SCHED_ISO: reserved but not implemented yet *//*普通迸程调度策略使task以最低优先级选择CFS调度器来调度运行*/
#define SCHED_IDLE 5/*限期进程调度策略使task选择Deadline调度器来调度运行*/
#define SCHED_DEADLINE 6备注其中stop调度器和DLE-task调度器仅使用于内核用户没有办法进行选择。
二、CFS调度器
1、CFS调度器基本原理
完全公平调度算法体现在对待每个进程都是公平的让每个进程都运行—段相同的时间片这就是基于时间片轮询调度算法。CFS定义一种新调度模型它给cfs_rq (cfs的run queue)中的每一个进程都设置一个虚拟时钟:vruntime(virtual runtime)。如果一个进程得以执行随着执行时间的不断增长其vruntime也将不断增大没有得到执行的进程vruntime 将保持不变。下图说明了调度器如何记录哪个进程已经等待了多长时间。由于可运行进程是排队的该结构称之为就绪队列 所有的可运行进程都按时间在一个红黑树中排序所谓时间即其等待时间。等待CPU时间最长的进程是最左侧的项调度器下一次会考虑该进程。等待时间稍短的进程在该树上从左至右排序。在一个调度周期里面所有进程的虚拟运行时间是相同的所以在进程调度时只需要找到虚拟运行时间最小的进程调度运行即可。实现完全公平调度算法要为进程定义两个时间 实际运行时间 实际运行时间 调度周期 * 进程权重 / 所有进程权重之和 调度周期指所有进程运行一遍所需要的时间 进程权重根据进程的重要性分配给每个进程不同的权重 eg调度周期为60ms进程A的权重为1而且进程B的权重为2,那么 进程A实际运行时间为60ms * 1/1 220ms 进程B实际运行时间为60ms * 2/1 240ms 虚拟运行时间 虚拟运行时间 实际运行时间 * nice为0对应的权重1024 / 进程的权重 调度周期 * 进程权重 / 所有进程权重之和 * 1024 / 进程权重 调度周期 * 1024 / 所有进程总权重。
2、调度子系统各个组件模块
调度器通过各个组件模块及一系列数据结构来排序和管理系统中的进程。它们之间关系如下 主调度器通过调用schedule()函数来完成进程的选择和切换。周期性调度器根据固定频率自动调用scheduler_tick函数不时检测是否有必要进行进程切换。上下文切换主要做两个事情切换地址空间、切换寄存器和栈空间
3、CFS调度器就绪队列内核源码
struct cfs_rq {/*CFS运行队列中所有进程总负我*/struct load_weight load;unsigned long runnable_weight;/*cfs_rq中调度实体数量*/unsigned int nr_running;unsigned int h_nr_running; /* SCHED_{NORMAL,BATCH,IDLE} */unsigned int idle_h_nr_running; /* SCHED_IDLE */u64 exec_clock;u64 min_vruntime;
#ifndef CONFIG_64BITu64 min_vruntime_copy;
#endif/*红黑树的root*/struct rb_root_cached tasks_timeline;/*下一个调度结点(红黑树最左边结点就是下个调度实体*/struct rb node *rb leftmost;...
