gpt4 book ai didi

极简cfs公平调度算法

转载 作者:我是一只小鸟 更新时间:2023-04-14 22:31:19 30 4
gpt4 key购买 nike

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 数据结构
                    
                      struct
                    
                    
                       sched_entity
{
    unsigned 
                    
                    
                      int
                    
                        on_rq;                           
                    
                      //
                    
                    
                       se是否在rq上,不在的话即使task是Ready状态也不会投入运行的
                    
                    
    u64             vruntime;                        
                    
                      //
                    
                    
                       cpu运行时长,cfs调度算法总是选择该值最小的se投入运行
                    
                    
                      };
 

                    
                    
                      struct
                    
                    
                       task
{
    
                    
                    
                      struct
                    
                     sched_entity se;                        
                    
                      //
                    
                    
                       调度实例
                    
                    
                      };
 

                    
                    
                      struct
                    
                    
                       rq
{
    
                    
                    
                      struct
                    
                     cfs_rq cfs;                          
                    
                      //
                    
                    
                       所有要调度的se都挂在cfs rq中
                    
                    
                      struct
                    
                     task_struct* curr;                   
                    
                      //
                    
                    
                       当前cpu上运行的task
                    
                    
                      };
 

                    
                    
                      struct
                    
                    
                       cfs_rq
{
    
                    
                    
                      struct
                    
                     rb_root tasks_timeline;              
                    
                      //
                    
                    
                       以vruntime为key,se为value的红黑树根节点,schedule时,cfs调度算法每次从这里挑选vruntime最小的se投入运行
                    
                    
                      struct
                    
                     rb_node* rb_leftmost;                
                    
                      //
                    
                    
                       tasks_timeline红黑树最左的叶子节点,即vruntime最小的se,直接取这个节点以加快速度
                    
                    
    sched_entity* curr;                         
                    
                      //
                    
                    
                       cfs_rq中当前正在运行的se
                    
                    
                      struct
                    
                     rq* rq;                              
                    
                      /*
                    
                    
                       cpu runqueue to which this  cfs_rq is attached 
                    
                    
                      */
                    
                    
                      
    unsigned 
                    
                    
                      int
                    
                     nr_running;                    
                    
                      //
                    
                    
                       cfs_rq队列上有多少个se
                    
                    
};
                  

  。

3.3 数据结构关系
 
2.3 极简task调度code
2.3.1 时钟中断
1> task调度的发动机时钟中断触发后,会在smp_apic_timer_interrupt()中处理,经过层层调用,最终会到entity_tick()
                    
                      entity_tick()
{
    update_curr();
    
                    
                    
                      //
                    
                    
                       如果当前cfs_rq上的se大于1,则检查是否要重新调度
                    
                    
                      if
                    
                     (cfs_rq->nr_running > 
                    
                      1
                    
                    
                      )
        check_preempt_tick(cfs_rq, curr);
}
                    
                  

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

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

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

                    
                      void
                    
                    
                       check_preempt_tick()
{
    
                    
                    
                      //
                    
                    
                       如果运行时间大于sched_slice,则resched
                    
                    
                      if
                    
                     (delta_exec >
                    
                       ideal_runtime)
        resched_task(rq_of(cfs_rq)
                    
                    ->
                    
                      curr);
        
    
                    
                    
                      //
                    
                    
                       如果比最小vruntime大一个sched_slice,则resched
                    
                    
    se = __pick_first_entity(cfs_rq);                
                    
                      //
                    
                    
                       选择cfs.rb_leftmost的se,即vruntime最小的se
                    
                    
    delta = curr->vruntime - se->
                    
                      vruntime;
    
                    
                    
                      if
                    
                     (delta >
                    
                       ideal_runtime)
        resched_task(rq_of(cfs_rq)
                    
                    ->
                    
                      curr);
}
                    
                  

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

                    
                      void
                    
                     resched_curr(
                    
                      struct
                    
                     rq*
                    
                       rq)
{
    
                    
                    
                      struct
                    
                     task_struct* curr = rq->
                    
                      curr;
    set_tsk_thread_flag(curr, TIF_NEED_RESCHED);
}
                    
                  

  。

2.3.2 schedule
1> 时钟中断返回后,会jump到ret_from_intr(有兴趣可以去分析这段汇编),如果resched标记被置位,就会调用schedule()进行调度
                    
                      void
                    
                    
                       schedule()
{
    prev 
                    
                    = rq->
                    
                      curr;
    put_prev_task_fair(rq, prev);        
                    
                    
                      //
                    
                    
                       对当前task进行处理,如果该task属于一个group,还要对组调度进行处理,这里不展开
    
                    
                    
                      //
                    
                    
                       选择下一个task并切换运行
                    
                    
    next = pick_next_task(rq);           
                    
                      //
                    
                    
                       选择一个vruntime最小的task进行调度
                    
                    
                          context_switch(rq, prev, next);
}
                    
                  

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

                    
                      struct
                    
                     sched_entity *__pick_first_entity(
                    
                      struct
                    
                     cfs_rq *
                    
                      cfs_rq)
{
    
                    
                    
                      struct
                    
                     rb_node *left = cfs_rq->
                    
                      rb_leftmost;
    
                    
                    
                      return
                    
                     rb_entry(left, 
                    
                      struct
                    
                    
                       sched_entity, run_node);
}
                    
                  

  。

 

最后此篇关于极简cfs公平调度算法的文章就讲到这里了,如果你想了解更多关于极简cfs公平调度算法的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com