Linux内核源码—CFS调度(4.20.17)

cfs_rq

每个 cpu 都有一个对应的运行队列 rq,在 rq 中维护着不同调度策略的调度队列。

cfs的调度队列通过红黑树维护,在 cfs_rq 的数据结构中,struct rb_root_cached tasks_timeline 包含了红黑树 struct rb_root rb_root 和 最左叶子节点缓存 struct rb_node *rb_leftmost 。

vruntime

那么CFS是根据什么来对任务进行排序呢?———-》 虚拟运行时间 vruntime

update_curr 函数(/kernel/sched/fair.c)实现了 vruntime 的更新,其步骤是计算出当前进程的运行时间 delta_exec,再结合当前可运行进程总数对delta_exec 进行加权运算。

calc_delta_fair(delta_exec, curr) 实现了虚拟运行时间的计算:

虚拟运行时间 = delta_exec * NICE_0_LOAD / 当前进程的权重

而具体在 __calc_delta 中,是通过 (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT 实现的,通过左移和右移避免浮点运算。

从公式可以得出,如果 一个进程的虚拟运行时间越小,说明实际运行的时间越少或者是进程的权重大,那么就应该具有更高的优先度。而红黑树维护的就是进程的 vruntime 值,每次选择 vruntime 最小的进程执行,该节点缓存在了最左叶子节点 struct rb_node *rb_leftmost 中。

进程选择

在进程变为可运行状态(被唤醒)或者是通过 fork() 调用第一次创建进程时,需要将进程插入红黑树,调用 __enqueue_entity 实现这一过程。删除节点也是同样的道理。

进程调度

进程调度的主要入口点是函数 schedule(/kernel/sched/core.c),它 通过 pick_next_task() 函数选择下一个进程,如果选出来的进程与当前运行进程不一致,则调用 context_switch() 函数进行上下文切换

pick_next_task() 函数的实现并不复杂,这里用到了一点优化,如果所有的可运行进程都在 cfs 中,那么就可以直接调用 cfs 的 pick_next_task(), 否则就需要按照调度器的优先级来选择。

References

Original: https://www.cnblogs.com/zyb993963526/p/15979450.html
Author: Kayden_Cheung
Title: Linux内核源码—CFS调度(4.20.17)

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/10038/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

发表回复

登录后才能评论
免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部