今天主要来讲一下Linux的fair调度器,通常Linux下有dl, rt, cfs, idle四种调度器,其中,dl(deadline)调度器优先级最高,然后是RT(real time)调度器, 继而是CFS调度器, 最后才是idle调度。 fair调度器的初始化是在main.c的start_kernel中调用sched_init完成,程序栈为:
点击(此处)折叠或打开
- start_kernel
- sched_init // 主要是一些带宽控制相关的
- init_sched_fair_class
但我们知道,其实,fair真正管用的是fair.c内部的结构体struct sched_class fair_sched_class, 本篇不讲sched_init函数的实现内容,只简单说明fair_sched_class结构体。如下是fair_sched_class的结构成员,
点击(此处)折叠或打开
- const struct sched_class fair_sched_class = {
- .next = &idle_sched_class, // 下一个调度器是idle调度器(链表按照优先级顺序排列)
- .enqueue_task = enqueue_task_fair, // 将一个task加入到cfs_rq
- .dequeue_task = dequeue_task_fair, // 将一个task从cfs_rq删除
- .yield_task = yield_task_fair, // 当前指定rq的task放弃CPU执行
- .yield_to_task = yield_to_task_fair, // 当前rq的task放弃执行,并设置下次切换的task
- .check_preempt_curr = check_preempt_wakeup, // 检查指定task是否可以抢占当前task
- .pick_next_task = pick_next_task_fair, // 切换task, 当前task加入到cfs_rq队列,取新的task设置成current
- .put_prev_task = put_prev_task_fair, // 将当前task加入cfs_rq队列
- .set_curr_task = set_curr_task_fair, // 设置task为当前task
- .task_tick = task_tick_fair, // 一个tick到来,会调用该函数,用于检查是否需要调度
- .task_fork = task_fork_fair, // 新创建一个task,需要调用这个分配虚拟时钟
- .prio_changed = prio_changed_fair, // 改变优先级
- .switched_from = switched_from_fair, //进程改变调度器时使用
- .switched_to = switched_to_fair, // 进程改变调度器时使用
- .update_curr = update_curr_fair, // 更新当前task链上的虚拟时钟相关
- }
在开始讲结构体之前,有几个基本概念应该了解:一,一个核上只有一个run queue(rq), 一个rq下面可能有一个或者多个cfs_rq;二、所有的task都是用entity来表示(调度实体);三、所有的调度实体(entity)都是挂接到红黑树上进行管理,即运行队列是一棵红黑树;四,一个运行队列下面挂可能是一个task entity,也可能是一个group entity。
首先,当应用程序创建一个进程(fork)的时候,会调用task_fork和对应调度器进行关联,这里是fair的task_fork,
点击(此处)折叠或打开
- .task_fork = task_fork_fair,
- update_curr // 更新当前task的虚拟时钟
- place_entity // 根据当前cfs_rq队列情况,计算出新task最佳虚拟时钟
然后,一个新的task创建,这时候,需要将新的task加入到cfs_rq队列,才能参与调度,即ready状态,调用如下,
点击(此处)折叠或打开
- .enqueue_task = enqueue_task_fair,
- enqueue_entity
- update_curr // 更新entity的虚拟时钟
- __enqueue_entity // 将新的entity加入到红黑树
- on_rq = 1; // on_rq设置为1
此后,该task就已经加入了调度。如果此后,该task需要休眠或者等待IO,则调用dequeue从运行队列上取下来,
点击(此处)折叠或打开
- .dequeue_task = dequeue_task_fair,
- dequeue_entity
- update_curr // 更新entity的虚拟时钟
- clear_buddies // 清理buddy,buddy用于选择最佳task使用,是为了给有贡献的任务做补偿使用的,这里因为要休眠了, 所以清楚掉这个标记
- __dequeue_entity // 从红黑树上取下当前task
- on_rq = 0; // 将on_rq 设置成0
注意:entity的on_rq成员,只有在enqueue和dequeue的时候才会改变。而Linux总体有running, ready和sleep三种大的状态。一、当执行enqueue函数加入到cfs_rq红黑树上的时候(on_rq会同步设置为1),为ready状态,此后,task可参与调度;二、当task获取到运行权限的时候, 则要将task从红黑树上取下来,保存到current当中,但on_rq的值保持不变即on_rq = 1,此时为running状态(因为每次找最合适的task的时候总是从cfs_rq红黑树的最左边开始);三、当进程需要休眠或者等待IO的时候,则需要调用dequeue函数从红黑树上取下来,并且同步设置为on_rq = 0, 此时为sleep/io状态。四、调度器总是以在红黑树链表上的虚拟时钟最小的task来运行,当这个最小虚拟时钟的task在运行过程中,会在每个tick到来的时候,根据优先级,来增加它的虚拟时钟值,当前他的虚拟时钟值大于红黑树里面的其他最小虚拟时钟值task的时候,就会发生task切换。
有时候,task在运行过程中, 只需要短暂放弃CPU,而不需要休眠,则调用,
点击(此处)折叠或打开
- .yield_task = yield_task_fair,
- clear_buddies
- update_curr
- set_skip_buddy // 设置cfs_rq的skip值为当前task,表示下次调度的时候,不参与调度
有时候,task在运行的过程中, 需要短暂将CPU让给指定程序,
点击(此处)折叠或打开
- .yield_to_task = yield_to_task_fair,
- set_next_buddy // 将指定task设置成cfs_rq的next值,表示下次调度优先考虑分配
- yield_task_fair // 将当前task设置成skip值,下次不参与调度
由于系统在运行过程中,可能会出现从一个调度器切换到另一个调度器的情况(cfs->idle),意味着当前调度器里面没有任务需要运行,则需要调用put_prev_task,将对应task释放到它对应调度器的运行链表上面,则,
点击(此处)折叠或打开
- .put_prev_task = put_prev_task_fair,
- put_prev_entity //其实就是将当前task相关联的entity都加入到对应cfs_rq的红黑树
由于系统上次刚运行完idle或者其他调度器的task,现在需要切换到cfs调度器,那么就需要调用set_curr_task设置当前调度器的task为curr,
点击(此处)折叠或打开
- .set_curr_task = set_curr_task_fair,
- set_next_entity // 将指定task设置成cfs_rq的curr值,进行调度运行
注: put_prev_entity函数 会将entity加入到红黑树,并把cfs_rq->curr 设置成NULL, set_next_entiry会将entity从红黑树中移除,并把cfs_rq->curr设置成当前这个entity。
点击(此处)折叠或打开
- static void
- set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
- {
- /* 'current' is not kept within the tree. */
- if (se->on_rq) {
- __dequeue_entity(cfs_rq, se); // 加入红黑树
- }
- cfs_rq->curr = se; // 设置当前cfs_rq的curr值
- se->prev_sum_exec_runtime = se->sum_exec_runtime;
- }
- static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
- {
- if (prev->on_rq)
- update_curr(cfs_rq);
- if (prev->on_rq) {
- __enqueue_entity(cfs_rq, prev); // 移除红黑树
- }
- cfs_rq->curr = NULL;
- }
当一个时钟到达后,会调用task_tick去管理自己的task,判断是否需要切换task,
点击(此处)折叠或打开
- .task_tick = task_tick_fair,
- entity_tick
- update_curr
- check_preempt_tick // 如果在红黑树中有虚拟时钟更小的task,则设置当前task需要reschedule
判断一个task是否可以抢占当前task,
点击(此处)折叠或打开
- .check_preempt_curr = check_preempt_wakeup, // 主要是设置cfs_rq的next和last值,让下次调度优先选择这个task
- put_prev_task
- pick_next_entity
- set_next_entity
当一个进程schedule的时候,切换task的时候,调用如下,
点击(此处)折叠或打开
- schedule
- __schedule
- pick_next_task // 调用调度器的pick_next_task切换进程。
- fair_sched_class.pick_next_task(...)
- return;
点击(此处点击(此处)折叠或打开
- static inline struct task_struct *
- pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
- {
- const struct sched_class *class;
- struct task_struct *p;
- for_each_class(class) { //这里的顺序是dl->rt->cfs->idle
- p = class->pick_next_task(rq, prev, rf);
- if (p) {
- if (unlikely(p == RETRY_TASK))
- goto again;
- return p;
- }
- }
- }
fair的pick_next_task,这里会详细讲解该函数, 实现如下,
点击(此处)折叠或打开
- static struct task_struct *
- pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
- {
- struct cfs_rq *cfs_rq = &rq->cfs;
- struct sched_entity *se;
- struct task_struct *p;
- int new_tasks;
- again:
- if (!cfs_rq->nr_running) // 如果cfs_rq的红黑树上没有程序,即没有ready的task,则跳转到idle
- goto idle;
- #ifdef CONFIG_FAIR_GROUP_SCHED
- if (prev->sched_class != &fair_sched_class) // 如果当前进程不是cfs调度器,就用simple的通用调度切换方法
- goto simple;
- // 这个do while主要是找到最应该被调度的entity,即找到下一个task实体, 这里是存在多个cfs_rq的情况。
- do {
- struct sched_entity *curr = cfs_rq->curr;
- if (curr) {
- if (curr->on_rq) // 如果当前cfs_rq的task在队列上,更新虚拟时钟
- update_curr(cfs_rq);
- else
- curr = NULL;
- // 返回true,表示当前cfs已经超出运行时间,不能再进行组内调度,应该全局选择
- if (unlikely(check_cfs_rq_runtime(cfs_rq))) {
- cfs_rq = &rq->cfs;
- if (!cfs_rq->nr_running)
- goto idle;
- goto simple;
- }
- }
- // 从cfs_rq获取虚拟时钟最小或者最应该参与调度的task
- se = pick_next_entity(cfs_rq, curr);
- cfs_rq = group_cfs_rq(se);// 如果是调度组,会继续while,非调度组的group_cfs_rq返回NULL
- } while (cfs_rq);
- p = task_of(se); // 这里的se就是上面组调度里面,找到的最合适参与调度的task
- if (prev != p) { // 这个prev != p里面,主要是更新prev和p相关的组(cfs_cq)内成员的虚拟时钟
- struct sched_entity *pse = &prev->se;
- while (!(cfs_rq = is_same_group(se, pse))) {
- int se_depth = se->depth;
- int pse_depth = pse->depth;
- if (se_depth <= pse_depth) { // 表明pre所在的调度组 深度更深,需要更新prev所在的组的虚拟时钟
- put_prev_entity(cfs_rq_of(pse), pse);
- pse = parent_entity(pse);
- }
- if (se_depth >= pse_depth) { // 表明curr所在的调度组更深,需要将curr所在调度组一连串设置成对应cfs_rq的curr
- set_next_entity(cfs_rq_of(se), se);
- se = parent_entity(se);
- }
- }
- put_prev_entity(cfs_rq, pse);
- set_next_entity(cfs_rq, se);
- }
- goto done;
- simple:
- #endif
- // put_prev_task会将prev task释放到对应调度器的红黑树队列里面
- put_prev_task(rq, prev);
- do {
- se = pick_next_entity(cfs_rq, NULL); // 从cfs_rq中选择一个task
- set_next_entity(cfs_rq, se); // 将该task设置成curr,参与调度
- cfs_rq = group_cfs_rq(se); // 如果当前Curr为调度组,继续找该调度组里面的成员
- } while (cfs_rq);
- p = task_of(se);
- done: __maybe_unused;
- if (hrtick_enabled(rq))
- hrtick_start_fair(rq, p);
- return p;
- idle:
- new_tasks = idle_balance(rq, rf);
- if (new_tasks < 0)
- return RETRY_TASK;
- if (new_tasks > 0)
- goto again;
- return NULL;
- }
pick_next_entity的函数为选择最佳task的关键算法,实现如下,
点击(此处)折叠或打开
- static struct sched_entity *
- pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
- {
- struct sched_entity *left = __pick_first_entity(cfs_rq);
- struct sched_entity *se;
- // left是红黑树里面,拥有最小虚拟时钟的task,如果left为NULL或者curr的虚拟时钟比当前最小的left还要小,那么left就设置成curr,即curr还可以继续获得CPU,不进行任务切换
- if (!left || (curr && entity_before(curr, left)))
- left = curr;
- se = left; // 这个se不是指向curr进程,就是指向红黑树的最小虚拟时钟进程
- // 发现se指向的task被设置成不参与调度(skip)
- if (cfs_rq->skip == se) {
- struct sched_entity *second;
- if (se == curr) { // 如果这个不参与调度的task就是当前进程,那么就取红黑树的第一个实体
- second = __pick_first_entity(cfs_rq);
- } else { // 这个不参与调度的task不是curr进程,那说明这个task是红黑树的最小虚拟时钟task,因此,需要从红黑树中找到一个次小的虚拟时钟task
- second = __pick_next_entity(se);
- // 判断这个次小task是否能抢占curr,如果不能,second就还是变为curr
- if (!second || (curr && entity_before(curr, second)))
- second = curr;
- }
- // 判读这个新的task是否能抢占left,如果能,se就为它,这里的对比条件并没有最开始的严格,这里允许一个最小调度差值。
- if (second && wakeup_preempt_entity(second, left) < 1)
- se = second;
- }
- // 发现设置了last值,则优先调度last指向的task
- if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
- se = cfs_rq->last;
- // 发现设置了last值,则优先调度last指向的task
- if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
- se = cfs_rq->next;
- // 清除task的next或last值,以免下次调度的时候,又把last和next加入判断,导致不公平
- clear_buddies(cfs_rq, se);
- return se;
- }
wakeup_preempt_entity用于比较是否可以被抢占的函数,实现如下,
点击(此处)折叠或打开
- static int
- wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
- {
- s64 gran, vdiff = curr->vruntime - se->vruntime;
- if (vdiff <= 0) // curr的虚拟时钟值明显比se小,直接返回,可以抢占
- return -1;
- gran = wakeup_gran(se); // 计算curr的最小抢占期限粒度
- if (vdiff > gran) // 如果当前curr的虚拟时钟比se的虚拟时钟多超过最小抢占粒度的时间值,那么直接返回不支持抢占
- return 1;
- return 0; // 返回支持抢占
- }
schedule函数大概实现如下,
点击(此处)折叠或打开
- static void __sched notrace __schedule(bool preempt)
- {
- struct task_struct *prev, *next;
- unsigned long *switch_count;
- struct rq_flags rf;
- struct rq *rq;
- int cpu;
- cpu = smp_processor_id();
- rq = cpu_rq(cpu);
- prev = rq->curr; // 获取当前进程
- .....
- update_rq_clock(rq); //更新rq的时钟
- // 如果prev是不可运行的, 并且内核态不被抢占,说明该task是主动schedule的
- if (!preempt && prev->state) {
- // 如果当前进程有非阻塞等待信号,并且它的状态是TASK_INTERRUPTIBLE
- if (unlikely(signal_pending_state(prev->state, prev))) {
- prev->state = TASK_RUNNING;// 留着rq中,下次调度的时候,会处理自己的信号
- } else { // 否则需要将prev进程从就绪队列中删除
- deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);
- prev->on_rq = 0;
- if (prev->in_iowait) {
- atomic_inc(&rq->nr_iowait);
- delayacct_blkio_start();
- }
- if (prev->flags & PF_WQ_WORKER) { // 告诉工作队列唤醒相关
- struct task_struct *to_wakeup;
- to_wakeup = wq_worker_sleeping(prev);
- if (to_wakeup)
- try_to_wake_up_local(to_wakeup, &rf);
- }
- }
- switch_count = &prev->nvcsw;
- }
- next = pick_next_task(rq, prev, &rf); // 挑选一个优先级最高的任务排进队列
- clear_tsk_need_resched(prev);
- clear_preempt_need_resched();
- if (likely(prev != next)) {
- rq->nr_switches++;
- rq->curr = next;
-
- ++*switch_count; // 进程切换次数更新
- rq = context_switch(rq, prev, next, &rf); // bsp相关的上下文切换,包含映射表和寄存器
- } else { // 如果是同一个进程不需要切换
- rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);
- rq_unlock_irq(rq, &rf);
- }
- }
点击(此处)折叠或打开
- static __always_inline struct rq *
- context_switch(struct rq *rq, struct task_struct *prev,
- struct task_struct *next, struct rq_flags *rf)
- {
- struct mm_struct *mm, *oldmm;
- prepare_task_switch(rq, prev, next);
- mm = next->mm;
- oldmm = prev->active_mm;
- arch_start_context_switch(prev);
- if (!mm) { //内核线程是没有mm,内核task和应用进程的mm共享,因此内核线程延用上一个task的mm
- next->active_mm = oldmm;
- mmgrab(oldmm);
- enter_lazy_tlb(oldmm, next);
- } else
- switch_mm_irqs_off(oldmm, mm, next);
- if (!prev->mm) {
- prev->active_mm = NULL;
- rq->prev_mm = oldmm;
- }
- rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);
- prepare_lock_switch(rq, next, rf);
- switch_to(prev, next, prev); // 体系结构切换,主要是寄存器切换
- barrier();
- return finish_task_switch(prev);
- }
点击(此处)折叠或打开
- const struct sched_class fair_sched_class = {
- .enqueue_task = enqueue_task_fair,
- enqueue_entity
- update_curr
- __enqueue_entity
- .dequeue_task = dequeue_task_fair,
- dequeue_entity
- update_curr
- clear_buddies
- __dequeue_entity
- .yield_task = yield_task_fair,
- clear_buddies
- update_curr
- set_skip_buddy
- .yield_to_task = yield_to_task_fair,
- set_next_buddy
- yield_task_fair
- .check_preempt_curr = check_preempt_wakeup,
- set_next_buddy
- update_curr
- set_next_buddy
- .pick_next_task = pick_next_task_fair,
- put_prev_task
- pick_next_entity
- set_next_entity
- .put_prev_task = put_prev_task_fair,
- put_prev_entity
- .set_curr_task = set_curr_task_fair,
- set_next_entity
- .task_tick = task_tick_fair,
- entity_tick
- update_curr
- check_preempt_tick
- .task_fork = task_fork_fair,
- place_entity
- }
throttle_cfs_rq throttle对应的cfs_rq。