极简cfs公平调度算法

林深不知归处

1. 说明1> linux内核关于task调度这块是比较复杂的，流程也比较长，要从源码一一讲清楚很容易看晕2> 本篇文章主要是讲清楚cfs公平调度算法如何将task在时钟中断驱动下切换调度，所以与此无关的代码一律略过3> 本篇只讲最简单的task调度，略过组调度，组调度在下一篇《极简组调度-CGroup如何限制cpu》中讲解4> 本篇源码来自CentOS7.6的3.10.0-957.el7内核 2. 极简task调度核心思想1> linux采用cfs公平调度算法，其用vruntime记录task运行的cpu时长，每次用重新调度时，总是选择vruntime最小的task进行调度2> 所有Ready状态的task会分配到不同cpu的rq队列上，等待调度运行3> 时钟中断中，++当前task运行时间vruntime，并检测当前task运行时间是否超过一个时间片，或者其vruntime比当前cpu rq队列中最小的vruntime task大一个时间片，则设置resched标记(但并不立马进行task切换，因为此时仍在中断上下文中)4> 所有中断返回后（当然也包括时钟中断），都会jump到ret_from_intr，这里会检查resched标记，如果置位，则调用schedule()选择vruntime最小的task进行调度

 3. 极简task调度相关数据结构3.1 名词解释

	全称	说明
se	schedule entity	调度实例，可以是一个task，也可以是一个group（当使用组调度时），linux支持组调度后，将调度实例从原来的task，抽象为se
rq	run queue	cpu的运行队列，每个cpu一个，处于Ready状态的se挂在对应的cpu运行队列上后，才会被选择投入运行
cfs_rq	cfs rq	公平调度运行队列，因为一般进程都是用cfs调度算法，一般进程的se都是挂在rq.cfs_rq上的
vruntime	virtual runtime	se的一个重要成员，记录调度实例的cpu运行时长，schedule时，cfs调度每次都选取vruntime最小的se投入运行，这就是cfs调度算法的核心原理

  3.2 数据结构

1. struct sched_entity
2. {
3.     unsigned int    on_rq;                           // se是否在rq上，不在的话即使task是Ready状态也不会投入运行的
4.     u64             vruntime;                        // cpu运行时长，cfs调度算法总是选择该值最小的se投入运行
5. };
7. struct task
8. {
9.     struct sched_entity se;                        // 调度实例
10. };
12. struct rq
13. {
14.     struct cfs_rq cfs;                          // 所有要调度的se都挂在cfs rq中
15.     struct task_struct* curr;                   // 当前cpu上运行的task
16. };
18. struct cfs_rq
19. {
20.     struct rb_root tasks_timeline;              // 以vruntime为key，se为value的红黑树根节点，schedule时，cfs调度算法每次从这里挑选vruntime最小的se投入运行
21.     struct rb_node* rb_leftmost;                // tasks_timeline红黑树最左的叶子节点，即vruntime最小的se，直接取这个节点以加快速度
22.     sched_entity* curr;                         // cfs_rq中当前正在运行的se
23.     struct rq* rq;                              /* cpu runqueue to which this  cfs_rq is attached */
24.     unsigned int nr_running;                    // cfs_rq队列上有多少个se
25. };

复制代码

 
3.3 数据结构关系

 2.3 极简task调度code2.3.1 时钟中断1> task调度的发动机时钟中断触发后，会在smp_apic_timer_interrupt()中处理，经过层层调用，最终会到entity_tick()

1. entity_tick()
2. {
3.     update_curr();
4.     // 如果当前cfs_rq上的se大于1，则检查是否要重新调度
5.     if (cfs_rq->nr_running > 1)
6.         check_preempt_tick(cfs_rq, curr);
7. }

复制代码

2> update_curr()主要是++当前task se的vruntime（当然这里还对组调度进行了处理，这里不讲组调度，先略过）

1. void update_curr(struct cfs_rq* cfs_rq)
2. {
3.     struct sched_entity* curr = cfs_rq->curr;
4.     curr->vruntime += delta_exec;                   // 增加se的运行时间
5. }

复制代码

 3> check_preempt_tick()判定当前运行的时间大于sched_slice时，即超过了时间片，或者其vruntime比当前cpu rq队列中最小的vruntime task大一个时间片，就会标记resched，然后等中断返回后会调用schedule()进行task切换

1. void check_preempt_tick()
2. {
3.     // 如果运行时间大于sched_slice，则resched
4.     if (delta_exec > ideal_runtime)
5.         resched_task(rq_of(cfs_rq)->curr);
6.         
7.     // 如果比最小vruntime大一个sched_slice，则resched
8.     se = __pick_first_entity(cfs_rq);                // 选择cfs.rb_leftmost的se，即vruntime最小的se
9.     delta = curr->vruntime - se->vruntime;
10.     if (delta > ideal_runtime)
11.         resched_task(rq_of(cfs_rq)->curr);
12. }

复制代码

 4> resched_curr()非常简单，就是设置一个resched标记位TIF_NEED_RESCHED

1. void resched_curr(struct rq* rq)
2. {
3.     struct task_struct* curr = rq->curr;
4.     set_tsk_thread_flag(curr, TIF_NEED_RESCHED);
5. }

复制代码

 
2.3.2 schedule1> 时钟中断返回后，会jump到ret_from_intr(有兴趣可以去分析这段汇编)，如果resched标记被置位，就会调用schedule()进行调度

1. void schedule()
2. {
3.     prev = rq->curr;
4.     put_prev_task_fair(rq, prev);        // 对当前task进行处理，如果该task属于一个group，还要对组调度进行处理，这里不展开
5.     // 选择下一个task并切换运行
6.     next = pick_next_task(rq);           // 选择一个vruntime最小的task进行调度
7.     context_switch(rq, prev, next);
8. }

复制代码

2> pick_next_task() → pick_next_task_fair() → pick_next_entity() → __pick_first_entity()，__pick_first_entity()选择vruntime最小的cfs_rq->rb_leftmost节点se进行调度

1. struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
2. {
3.     struct rb_node *left = cfs_rq->rb_leftmost;
4.     return rb_entry(left, struct sched_entity, run_node);
5. }

复制代码

 
 
来源:https://www.cnblogs.com/organic/p/17320040.html
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！