文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

深入理解Linux内核之主调度器(上)

2024-12-03 02:19

关注

1.开场白

环境:

本文步进到Linux内核进程管理的核心部分,打开调度器的黑匣子,来看看Linux内核如何调度进程的。实际上,进程调度器主要做两件事:选择下一个进程,然后进行上下文切换。而何时调用主调度器调度进程那是调度时机所关注的问题,而调度时机在之前的内核抢占文章已经做了详细讲解,在此不在赘述,而本文关注的调度时机是真正调用主调度器的时机。

本文分析的内核源代码主要集中在:

2.调用时机

关于调度时机,网上的文章也五花八门,之前在内核抢占文章已经做了详细讲解,而在本文我们从源码注释中给出依据(再次强调一下:本文的调度时机关注的是何时调用主调度器,不是设置重新调度标志的时机,之前讲解中我们知道他们都可以称为调度时机)。

先来说一下什么是主调度器,其实和主调度器并列的还有一个叫做周期性调度器的东西(后面有机会会讲解,主要用于时钟中断tick调来使夺取处理器的控制权),他们都是内核中的一个函数,在合适的时机被调用。

主调度器函数如下:

  1. kernel/sched/core.c 
  2.  
  3. __schedule() 

内核的很多路径会包装这个函数,主要分为主动调度和抢占式调度场景。

内核源码中主调度器函数也给出了调度时机的注释,下面我们就以此为依据来看下:

  1. kernel/sched/core.c 
  2.                                                               
  3. static void __sched notrace __schedule(bool preempt)             

我们对注释做出解释,让大家深刻理解调度时机(基本上是原样翻译,用颜色标注)。

1.显式阻塞场景:包括互斥体、信号量、等待队列等。

这个场景主要是为了等待某些资源而主动放弃处理器,来调用主调度器,如发现互斥体被其他内核路径所持有,则睡眠等待互斥体被释放的时候来唤醒我。

2.在中断和用户空间返回路径上检查TIF_NEED_RESCHED标志。例如,arch/x86/entry_64.S。为了在任务之间驱动抢占,调度程序在计时器中断处理程序scheduler_tick()中设置标志。

解释如下:这实际上是说重新调度标志(TIF_NEED_RESCHED)的设置和检查的情形。

1)重新调度标志设置情形:如scheduler_tick周期性调度器按照特定条件设置、唤醒的路径上按照特定条件设置等。当前这样的场景并不会直接调用主调度器,而会在最近的调度点到来时调用主调度器。

2)重新调度标志检查情形:是真正的调用主调度器,下面的场景都会涉及到,在此不在赘述。

3.唤醒并不会真正导致schedule()的进入。他们添加一个任务到运行队列,仅此而已。

现在,如果添加到运行队列中的新任务抢占了当前任务,那么唤醒设置TIF_NEED_RESCHED, schedule()在最近的可能情况下被调用:

1)如果内核是可抢占的(CONFIG_PREEMPTION=y)

-在系统调用或异常上下文中,最外层的preempt_enable()。(这可能和wake_up()的spin_unlock()一样快!)

-在IRQ上下文中,从中断处理程序返回到抢占上下文

注释中很简洁的几句话,但其中的含义需要深刻去体会。

首先需要知道一点是:内核抢占说的是处于内核态的任务被其他任务所抢占的情况(无论是不是可抢占式内核,处于用户态的任务都可以被抢占,处于内核态的任务是否能被抢占由是否开启内核抢占来决定),当然内核态的任务可以是内核线程也可以是通过系统调用请求内核服务的用户任务。

情况1:这是重新开启内核抢占的情况,即是抢占计数器为0时,检查重新调度标志(TIF_NEED_RESCHED),如果设置则调用主调度器,放弃处理器(这是抢占式调度)。

情况2:中断返回内核态的时候,检查重新调度标志(TIF_NEED_RESCHED),如果设置且抢占计数器为0时则调用主调度器,放弃处理器(这是抢占式调度)。

注:关于内核抢占可以参考之前发布的文章。

2)如果内核是不可抢占的(CONFIG_PREEMPTION=y)

解释如下:

cond_resched()是为了在不可抢占内核的一些耗时的内核处理路径中增加主动抢占点(抢占计数器是否为0且当前任务被设置了重新调度标志),则调用主调度器进行抢占式调度,所进行低延时处理。

显式的schedule()调用,这是主动放弃处理器的场景,如一些睡眠场景,像用户任务调用sleep。

系统调用或异常返回到用户空间使会判断当前进程是否设置重新调度标志(TIF_NEED_RESCHED),如果设置则调用主调度器,放弃处理器。

中断处理器返回到用户空间会判断当前进程是否设置重新调度标志(TIF_NEED_RESCHED),如果设置则调用主调度器,放弃处理器。

其实还有一种场景也会调用到主调度器让出处理器,那就是进程退出时,这里不在赘述。

下面给出总结:

1.主动调度:

2.抢占调度:

不可抢占式内核

可抢占式内核(增加一些抢占点)

3.主调度器调用时机源码窥探

下面给出主要的一些主调度器调用时机源码分析,作为学习参考。

3.1 常规场景

中断返回用户态场景:

  1. arch/arm64/kernel/entry.S 
  2.  
  3. el0_irq 
  4. -> ret_to_user 
  5. -> work_pending 
  6. -> do_notify_resume 
  7. -> if (thread_flags & _TIF_NEED_RESCHED) {         // arch/arm64/kernel/signal.c 
  8.          schedule(); 
  9.             -> __schedule(false);       //  kernel/sched/core.c   false表示主动调度 
  10.                    

异常返回用户态场景:

  1. arch/arm64/kernel/entry.S 
  2.  
  3. el0_sync 
  4. -> ret_to_user 
  5.     ... 

任务退出场景:

  1. kernel/exit.c 
  2.  
  3. do_exit 
  4.  ->do_task_dead 
  5.      ->__schedule(false);    //  kernel/sched/core.c   false表示主动调度 

显式阻塞场景(举例互斥体):

  1. kernel/locking/mutex.c 
  2.  
  3. mutex_lock 
  4.  ->__mutex_lock_slowpath 
  5.      ->__mutex_lock 
  6.          ->__mutex_lock_common 
  7.              ->schedule_preempt_disabled 
  8.                  ->schedule(); 
  9.                  -> __schedule(false);       //  kernel/sched/core.c   false表示主动调度 

3.2 支持内核抢占场景

中断返回内核态场景

  1. arch/arm64/kernel/entry.S 
  2.  
  3. el1_irq 
  4. #ifdef CONFIG_PREEMPTION 
  5. ->arm64_preempt_schedule_irq 
  6.     ->preempt_schedule_irq(); 
  7.         ->__schedule(true);   //kernel/sched/core.c  true表示抢占式调度 
  8. #endif 

内核抢占开启场景

  1. preempt_enable 
  2. ->if (unlikely(preempt_count_dec_and_test())) \   //抢占计数器减一  为0         
  3.     __preempt_schedule(); \                   
  4.         ->preempt_schedule  //kernel/sched/core.c    
  5.             -> __schedule(true)  //调用主调度器进行抢占式调度 

注:一般说异常/中断返回,返回是处理器异常状态,可能是用户态也可能是内核态,但是会看到很多资料写的都是用户空间/内核空间并不准确,但是我们认为表达一个意思,做的心中有数即可。

3.3.选择下一个进程

本节主要讲解主调度器是如何选择下一个进程的,这和调度策略强相关。

下面我们来看具体实现:

  1. kernel/sched/core.c 
  2.  
  3. __schedule 
  4. -> next = pick_next_task(rq, prev, &rf); 
  5.     ->if (likely(prev->sched_class <= &fair_sched_class &&               
  6.         ¦  rq->nr_running == rq->cfs.h_nr_running)) {              
  7.                                                                    
  8.         p = pick_next_task_fair(rq, prev, rf);                     
  9.         if (unlikely(p == RETRY_TASK))                             
  10.                 goto restart;                                      
  11.                                                                    
  12.            
  13.         if (!p) {                                                  
  14.                 put_prev_task(rq, prev);                           
  15.                 p = pick_next_task_idle(rq);                       
  16.         }                                                          
  17.                                                                    
  18.         return p;                                                  
  19. }       
  20.  
  21.  
  22.  for_each_class(class) {                      
  23.          p = class->pick_next_task(rq);       
  24.          if (p)                               
  25.                  return p;                    
  26.  }                                            

这里做了优化,当当前进程的调度类为公平调度类或者空闲调度类时,且cpu运行队列的进程个数等于cfs运行队列进程个数,说明运行队列进程都是普通进程,则直接调用公平调度类的pick_next_task_fair选择下一个进程(选择红黑树最左边的那个进程),如果没有找到说明当前进程调度类为空闲调度类,直接调用pick_next_task_idle选择idle进程。

否则,遍历调度类,从高优先级调度类开始调用其pick_next_task方法选择下一个进程。

下面以公平调度类为例来看如何选择下一个进程的:调用过程如下(这里暂不考虑组调度情况):

  1. pick_next_task 
  2. ->pick_next_task_fair   //kernel/sched/fair.c 
  3.     -> if (prev)                         
  4.          put_prev_task(rq, prev);  
  5.     
  6.     
  7.    se = pick_next_entity(cfs_rq, NULL);   
  8.    set_next_entity(cfs_rq, se);           

先看put_prev_task:

  1. put_prev_task 
  2. ->prev->sched_class->put_prev_task(rq, prev); 
  3.     ->put_prev_task_fair 
  4.         ->put_prev_entity(cfs_rq, se); 
  5.             ->  
  6.                 __enqueue_entity(cfs_rq, prev);          
  7.               cfs_rq->curr = NULL

这里会调用__enqueue_entity将前一个进程重新加入到cfs队列的红黑树。然后将cfs_rq->curr 设置为空。

再看pick_next_entity:

  1. pick_next_entity 
  2. ->left = __pick_first_entity(cfs_rq); 
  3.     ->left = rb_first_cached(&cfs_rq->tasks_timeline);   

将选择cfs队列红黑树最左边进程。

最后看set_next_entity:

  1. set_next_entity 
  2.  ->__dequeue_entity(cfs_rq, se); 
  3.     ->cfs_rq->curr = se; 

这里调用__dequeue_entity将下一个选择的进程从cfs队列的红黑树中删除,然后将cfs队列的curr指向进程的调度实体。

选择下一个进程总结如下:

通用的调度类选择顺序为:

stop_sched_class -> dl_sched_class ->rt_sched_class -> fair_sched_class ->idle_sched_class

比如:当前运行队列都是cfs的普通进程,某一时刻发生中断唤醒了一个rt进程,那么在最近的调度点到来时就会调用主调度器选择rt进程作为next进程。

做了以上的工作之后,红黑树中选择下一个进程的时候就不会再选择到当前cpu上运行的进程了,而当前进程调度实体又被cfs队列的curr来记录着(运行队列的curr也会记录当前进程)。

下面给出公平调度类选择下一个进程图解(其中A为前一个进程,即是当前进程,即为前一个进程,B为下一个进程):

 

来源: Linux内核远航者内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯