Chinaunix首页 | 论坛 | 博客
  • 博客访问: 882258
  • 博文数量: 26
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 382
  • 用 户 组: 普通用户
  • 注册时间: 2019-09-08 12:19
个人简介

关于个人介绍,既然你诚心诚意的看了 我就大发慈悲的告诉你 为了防止世界被破坏 为了维护世界的和平 贯彻爱与真实的邪恶 可爱又迷人的反派角色 我们是穿梭在银河的火箭队 白洞,白色的明天在等着我们

文章分类

分类: LINUX

2020-06-01 18:08:42

今天主要来讲一下Linux的fair调度器,通常Linux下有dl, rt, cfs, idle四种调度器,其中,dl(deadline)调度器优先级最高,然后是RT(real time)调度器, 继而是CFS调度器,  最后才是idle调度。 fair调度器的初始化是在main.c的start_kernel中调用sched_init完成,程序栈为:

点击(此处)折叠或打开

  1. start_kernel
  2.     sched_init    // 主要是一些带宽控制相关的
  3.        init_sched_fair_class

但我们知道,其实,fair真正管用的是fair.c内部的结构体struct sched_class fair_sched_class, 本篇不讲sched_init函数的实现内容,只简单说明fair_sched_class结构体。如下是fair_sched_class的结构成员,

点击(此处)折叠或打开

  1. const struct sched_class fair_sched_class = {
  2.     .next         = &idle_sched_class,     // 下一个调度器是idle调度器(链表按照优先级顺序排列
  3.     .enqueue_task      = enqueue_task_fair, // 将一个task加入到cfs_rq
  4.     .dequeue_task      = dequeue_task_fair, // 将一个task从cfs_rq删除

  5.     .yield_task        = yield_task_fair,   // 当前指定rq的task放弃CPU执行
  6.     .yield_to_task     = yield_to_task_fair, // 当前rq的task放弃执行,并设置下次切换的task
  7.     .check_preempt_curr    = check_preempt_wakeup, // 检查指定task是否可以抢占当前task

  8.     .pick_next_task = pick_next_task_fair, // 切换task, 当前task加入到cfs_rq队列,取新的task设置成current

  9.     .put_prev_task      = put_prev_task_fair, // 将当前task加入cfs_rq队列
  10.     .set_curr_task      = set_curr_task_fair, // 设置task为当前task

  11.     .task_tick        = task_tick_fair,   // 一个tick到来,会调用该函数,用于检查是否需要调度
  12.     .task_fork        = task_fork_fair,   // 新创建一个task,需要调用这个分配虚拟时钟

  13.     .prio_changed        = prio_changed_fair,  // 改变优先级
  14.     .switched_from        = switched_from_fair, //进程改变调度器时使用
  15.     .switched_to        = switched_to_fair, // 进程改变调度器时使用

  16.     .update_curr        = update_curr_fair, // 更新当前task链上的虚拟时钟相关
  17. }

在开始讲结构体之前,有几个基本概念应该了解:一,一个核上只有一个run queue(rq), 一个rq下面可能有一个或者多个cfs_rq;二、所有的task都是用entity来表示(调度实体);三、所有的调度实体(entity)都是挂接到红黑树上进行管理,即运行队列是一棵红黑树;四,一个运行队列下面挂可能是一个task entity,也可能是一个group entity。

首先,当应用程序创建一个进程(fork)的时候,会调用task_fork和对应调度器进行关联,这里是fair的task_fork,

点击(此处)折叠或打开

  1. .task_fork    = task_fork_fair,
  2.                         update_curr   // 更新当前task的虚拟时钟
  3.                         place_entity  // 根据当前cfs_rq队列情况,计算出新task最佳虚拟时钟

然后,一个新的task创建,这时候,需要将新的task加入到cfs_rq队列,才能参与调度,即ready状态,调用如下,
点击(此处)折叠或打开

  1. .enqueue_task   = enqueue_task_fair,
  2.                        enqueue_entity  
  3.                            update_curr      // 更新entity的虚拟时钟
  4.                            __enqueue_entity // 将新的entity加入到红黑树
  5.                        on_rq = 1;           // on_rq设置为1

此后,该task就已经加入了调度。如果此后,该task需要休眠或者等待IO,则调用dequeue从运行队列上取下来,
点击(此处)折叠或打开

  1. .dequeue_task  = dequeue_task_fair,
  2.                       dequeue_entity
  3.                           update_curr // 更新entity的虚拟时钟
  4.                           clear_buddies // 清理buddy,buddy用于选择最佳task使用,是为了给有贡献的任务做补偿使用的,这里因为要休眠了, 所以清楚掉这个标记
  5.                          __dequeue_entity // 从红黑树上取下当前task
  6.                          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,而不需要休眠,则调用,

点击(此处)折叠或打开

  1. .yield_task    = yield_task_fair,
  2.                       clear_buddies
  3.                       update_curr
  4.                       set_skip_buddy   // 设置cfs_rq的skip值为当前task,表示下次调度的时候,不参与调度

有时候,task在运行的过程中, 需要短暂将CPU让给指定程序,
点击(此处)折叠或打开

  1. .yield_to_task  = yield_to_task_fair,
  2.                       set_next_buddy  // 将指定task设置成cfs_rq的next值,表示下次调度优先考虑分配
  3.                       yield_task_fair // 将当前task设置成skip值,下次不参与调度

由于系统在运行过程中,可能会出现从一个调度器切换到另一个调度器的情况(cfs->idle),意味着当前调度器里面没有任务需要运行,则需要调用put_prev_task,将对应task释放到它对应调度器的运行链表上面,则,
点击(此处)折叠或打开

  1. .put_prev_task = put_prev_task_fair,
  2.                      put_prev_entity //其实就是将当前task相关联的entity都加入到对应cfs_rq的红黑树

由于系统上次刚运行完idle或者其他调度器的task,现在需要切换到cfs调度器,那么就需要调用set_curr_task设置当前调度器的task为curr,
点击(此处)折叠或打开

  1. .set_curr_task = set_curr_task_fair,
  2.                       set_next_entity // 将指定task设置成cfs_rq的curr值,进行调度运行

: put_prev_entity函数 会将entity加入到红黑树,并把cfs_rq->curr 设置成NULL, set_next_entiry会将entity从红黑树中移除,并把cfs_rq->curr设置成当前这个entity。

点击(此处)折叠或打开

  1. static void
  2. set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
  3. {
  4.     /* 'current' is not kept within the tree. */
  5.     if (se->on_rq) {
  6.         __dequeue_entity(cfs_rq, se); // 加入红黑树
  7.     }

  8.     cfs_rq->curr = se; // 设置当前cfs_rq的curr值
  9.     se->prev_sum_exec_runtime = se->sum_exec_runtime;
  10. }

  11. static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
  12. {
  13.     if (prev->on_rq)
  14.         update_curr(cfs_rq);

  15.     if (prev->on_rq) {
  16.          __enqueue_entity(cfs_rq, prev); // 移除红黑树
  17.     }
  18.     cfs_rq->curr = NULL;
  19. }

当一个时钟到达后,会调用task_tick去管理自己的task,判断是否需要切换task,
点击(此处)折叠或打开

  1. .task_tick      = task_tick_fair,
  2.                       entity_tick
  3.                          update_curr
  4.                          check_preempt_tick // 如果在红黑树中有虚拟时钟更小的task,则设置当前task需要reschedule

判断一个task是否可以抢占当前task,
点击(此处)折叠或打开

  1. .check_preempt_curr = check_preempt_wakeup, // 主要是设置cfs_rq的next和last值,让下次调度优先选择这个task
  2.                       put_prev_task
  3.                       pick_next_entity
  4.                       set_next_entity

当一个进程schedule的时候,切换task的时候,调用如下,
点击(此处)折叠或打开

  1. schedule
  2.     __schedule
  3.         pick_next_task  // 调用调度器的pick_next_task切换进程。
  4.            fair_sched_class.pick_next_task(...
  5.         return;

点击(此处点击(此处)折叠或打开

  1. static inline struct task_struct *
  2. pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
  3. {
  4.     const struct sched_class *class;
  5.     struct task_struct *p;

  6.     for_each_class(class) { //这里的顺序是dl->rt->cfs->idle
  7.         p = class->pick_next_task(rq, prev, rf);
  8.         if (p) {
  9.             if (unlikely(p == RETRY_TASK))
  10.                 goto again;
  11.             return p;
  12.         }
  13.     }
  14. }

fair的pick_next_task,这里会详细讲解该函数, 实现如下,
点击(此处)折叠或打开

  1. static struct task_struct *
  2. pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
  3. {
  4.     struct cfs_rq *cfs_rq = &rq->cfs;
  5.     struct sched_entity *se;
  6.     struct task_struct *p;
  7.     int new_tasks;

  8. again:
  9.     if (!cfs_rq->nr_running)  // 如果cfs_rq的红黑树上没有程序,即没有ready的task,则跳转到idle
  10.         goto idle;

  11. #ifdef CONFIG_FAIR_GROUP_SCHED
  12.     if (prev->sched_class != &fair_sched_class)  // 如果当前进程不是cfs调度器,就用simple的通用调度切换方法
  13.         goto simple;
  14.  
  15.     // 这个do while主要是找到最应该被调度的entity,即找到下一个task实体, 这里是存在多个cfs_rq的情况。
  16.     do {
  17.         struct sched_entity *curr = cfs_rq->curr;

  18.         if (curr) {
  19.             if (curr->on_rq) // 如果当前cfs_rq的task在队列上,更新虚拟时钟
  20.                 update_curr(cfs_rq);
  21.             else
  22.                 curr = NULL;
  23.  
  24.             // 返回true,表示当前cfs已经超出运行时间,不能再进行组内调度,应该全局选择
  25.             if (unlikely(check_cfs_rq_runtime(cfs_rq))) {
  26.                 cfs_rq = &rq->cfs;

  27.                 if (!cfs_rq->nr_running)
  28.                     goto idle;

  29.                 goto simple;
  30.             }
  31.         }
  32.         // 从cfs_rq获取虚拟时钟最小或者最应该参与调度的task
  33.         se = pick_next_entity(cfs_rq, curr);
  34.         cfs_rq = group_cfs_rq(se);// 如果是调度组,会继续while,非调度组的group_cfs_rq返回NULL
  35.     } while (cfs_rq);

  36.     p = task_of(se); // 这里的se就是上面组调度里面,找到的最合适参与调度的task
  37.     if (prev != p) { // 这个prev != p里面,主要是更新prev和p相关的组(cfs_cq)内成员的虚拟时钟
  38.         struct sched_entity *pse = &prev->se;

  39.         while (!(cfs_rq = is_same_group(se, pse))) {
  40.             int se_depth = se->depth;
  41.             int pse_depth = pse->depth;

  42.             if (se_depth <= pse_depth) { // 表明pre所在的调度组 深度更深,需要更新prev所在的组的虚拟时钟
  43.                 put_prev_entity(cfs_rq_of(pse), pse);
  44.                 pse = parent_entity(pse);
  45.             }
  46.             if (se_depth >= pse_depth) { // curr所在的调度组更深,需要将curr所在调度组一连串设置成对应cfs_rq的curr
  47.                 set_next_entity(cfs_rq_of(se), se);
  48.                 se = parent_entity(se);
  49.             }
  50.         }

  51.         put_prev_entity(cfs_rq, pse);
  52.         set_next_entity(cfs_rq, se);
  53.     }

  54.     goto done;
  55. simple:
  56. #endif
  57.     // put_prev_task会将prev task释放到对应调度器的红黑树队列里面
  58.     put_prev_task(rq, prev);

  59.     do {
  60.         se = pick_next_entity(cfs_rq, NULL); // 从cfs_rq中选择一个task
  61.         set_next_entity(cfs_rq, se);  // 将该task设置成curr,参与调度
  62.         cfs_rq = group_cfs_rq(se);   // 如果当前Curr为调度组,继续找该调度组里面的成员
  63.     } while (cfs_rq);

  64.     p = task_of(se);

  65. done: __maybe_unused;
  66.     if (hrtick_enabled(rq))
  67.         hrtick_start_fair(rq, p);

  68.     return p;

  69. idle:
  70.     new_tasks = idle_balance(rq, rf);
  71.     if (new_tasks < 0)
  72.         return RETRY_TASK;

  73.     if (new_tasks > 0)
  74.         goto again;

  75.     return NULL;
  76. }

pick_next_entity的函数为选择最佳task的关键算法,实现如下,

点击(此处)折叠或打开

  1. static struct sched_entity *
  2. pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
  3. {
  4.     struct sched_entity *left = __pick_first_entity(cfs_rq);
  5.     struct sched_entity *se;
  6.  
  7.     // left是红黑树里面,拥有最小虚拟时钟的task,如果left为NULL或者curr的虚拟时钟比当前最小的left还要小,那么left就设置成curr,即curr还可以继续获得CPU,不进行任务切换
  8.     if (!left || (curr && entity_before(curr, left)))
  9.         left = curr;

  10.     se = left; // 这个se不是指向curr进程,就是指向红黑树的最小虚拟时钟进程
  11.  
  12.     // 发现se指向的task被设置成不参与调度(skip)
  13.     if (cfs_rq->skip == se) {
  14.         struct sched_entity *second;

  15.         if (se == curr) { // 如果这个不参与调度的task就是当前进程,那么就取红黑树的第一个实体
  16.             second = __pick_first_entity(cfs_rq);
  17.         } else { // 这个不参与调度的task不是curr进程,那说明这个task是红黑树的最小虚拟时钟task,因此,需要从红黑树中找到一个次小的虚拟时钟task
  18.             second = __pick_next_entity(se);
  19.             // 判断这个次小task是否能抢占curr,如果不能,second就还是变为curr
  20.             if (!second || (curr && entity_before(curr, second)))
  21.                 second = curr;
  22.         }
  23.  
  24.         // 判读这个新的task是否能抢占left,如果能,se就为它,这里的对比条件并没有最开始的严格,这里允许一个最小调度差值。
  25.         if (second && wakeup_preempt_entity(second, left) < 1)
  26.             se = second;
  27.     }
  28.  
  29.     // 发现设置了last值,则优先调度last指向的task
  30.     if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
  31.         se = cfs_rq->last;
  32.  
  33.     // 发现设置了last值,则优先调度last指向的task
  34.     if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
  35.         se = cfs_rq->next;
  36.  
  37.     // 清除task的next或last值,以免下次调度的时候,又把last和next加入判断,导致不公平
  38.     clear_buddies(cfs_rq, se);

  39.     return se;
  40. }

wakeup_preempt_entity用于比较是否可以被抢占的函数,实现如下,

点击(此处)折叠或打开

  1. static int
  2. wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
  3. {
  4.     s64 gran, vdiff = curr->vruntime - se->vruntime;

  5.     if (vdiff <= 0)  // curr的虚拟时钟值明显比se小,直接返回,可以抢占
  6.         return -1;

  7.     gran = wakeup_gran(se); // 计算curr的最小抢占期限粒度
  8.     if (vdiff > gran) // 如果当前curr的虚拟时钟比se的虚拟时钟多超过最小抢占粒度的时间,那么直接返回不支持抢占
  9.         return 1;

  10.     return 0; // 返回支持抢占
  11. }

schedule函数大概实现如下,
点击(此处)折叠或打开

  1. static void __sched notrace __schedule(bool preempt)
  2. {
  3.     struct task_struct *prev, *next;
  4.     unsigned long *switch_count;
  5.     struct rq_flags rf;
  6.     struct rq *rq;
  7.     int cpu;

  8.     cpu = smp_processor_id();
  9.     rq = cpu_rq(cpu);
  10.     prev = rq->curr; // 获取当前进程
  11.     .....
  12.     update_rq_clock(rq); //更新rq的时钟
  13.  
  14.     // 如果prev是不可运行的, 并且内核态不被抢占,说明该task是主动schedule的
  15.     if (!preempt && prev->state) {
  16.         // 如果当前进程有非阻塞等待信号,并且它的状态是TASK_INTERRUPTIBLE
  17.         if (unlikely(signal_pending_state(prev->state, prev))) {
  18.             prev->state = TASK_RUNNING;// 留着rq中,下次调度的时候,会处理自己的信号
  19.         } else { // 否则需要将prev进程从就绪队列中删除
  20.             deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);
  21.             prev->on_rq = 0;

  22.             if (prev->in_iowait) {
  23.                 atomic_inc(&rq->nr_iowait);
  24.                 delayacct_blkio_start();
  25.             }

  26.             if (prev->flags & PF_WQ_WORKER) { // 告诉工作队列唤醒相关
  27.                 struct task_struct *to_wakeup;

  28.                 to_wakeup = wq_worker_sleeping(prev);
  29.                 if (to_wakeup)
  30.                     try_to_wake_up_local(to_wakeup, &rf);
  31.             }
  32.         }
  33.         switch_count = &prev->nvcsw;
  34.     }

  35.     next = pick_next_task(rq, prev, &rf); // 挑选一个优先级最高的任务排进队列
  36.     clear_tsk_need_resched(prev);
  37.     clear_preempt_need_resched();

  38.     if (likely(prev != next)) {
  39.         rq->nr_switches++;
  40.         rq->curr = next;
  41.         
  42.         ++*switch_count; // 进程切换次数更新
  43.         rq = context_switch(rq, prev, next, &rf); // bsp相关的上下文切换,包含映射表和寄存器
  44.     } else { // 如果是同一个进程不需要切换
  45.         rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);
  46.         rq_unlock_irq(rq, &rf);
  47.     }
  48. }
context_switch函数实现如下,

点击(此处)折叠或打开

  1. static __always_inline struct rq *
  2. context_switch(struct rq *rq, struct task_struct *prev,
  3.      struct task_struct *next, struct rq_flags *rf)
  4. {
  5.     struct mm_struct *mm, *oldmm;

  6.     prepare_task_switch(rq, prev, next);

  7.     mm = next->mm;
  8.     oldmm = prev->active_mm;

  9.     arch_start_context_switch(prev);

  10.     if (!mm) { //内核线程是没有mm,内核task和应用进程的mm共享,因此内核线程延用上一个task的mm
  11.         next->active_mm = oldmm;
  12.         mmgrab(oldmm);
  13.         enter_lazy_tlb(oldmm, next);
  14.     } else
  15.         switch_mm_irqs_off(oldmm, mm, next);

  16.     if (!prev->mm) {
  17.         prev->active_mm = NULL;
  18.         rq->prev_mm = oldmm;
  19.     }

  20.     rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);

  21.     prepare_lock_switch(rq, next, rf);

  22.     switch_to(prev, next, prev); // 体系结构切换,主要是寄存器切换
  23.     barrier();

  24.     return finish_task_switch(prev);
  25. }


点击(此处)折叠或打开

  1. const struct sched_class fair_sched_class = {
  2. .enqueue_task    = enqueue_task_fair,
  3.                        enqueue_entity
  4.                            update_curr
  5.                            __enqueue_entity

  6. .dequeue_task    = dequeue_task_fair,
  7.                       dequeue_entity
  8.                           update_curr
  9.                           clear_buddies
  10.                          __dequeue_entity

  11. .yield_task    = yield_task_fair,
  12.                       clear_buddies
  13.                       update_curr
  14.                       set_skip_buddy

  15. .yield_to_task    = yield_to_task_fair,
  16.                         set_next_buddy
  17.                         yield_task_fair

  18. .check_preempt_curr = check_preempt_wakeup,
  19.                            set_next_buddy
  20.                            update_curr
  21.                            set_next_buddy

  22. .pick_next_task  = pick_next_task_fair,
  23.                        put_prev_task
  24.                        pick_next_entity
  25.                        set_next_entity

  26. .put_prev_task    = put_prev_task_fair,
  27.                         put_prev_entity

  28. .set_curr_task = set_curr_task_fair,
  29.                       set_next_entity

  30. .task_tick      = task_tick_fair,
  31.                       entity_tick
  32.                          update_curr
  33.                          check_preempt_tick

  34. .task_fork      = task_fork_fair,
  35.                       place_entity
  36. }
check_cfs_rq_runtime 检查 cfs_rq的是否没有可运行时间,true表示无运行时间,false表示还可以继续使用。
throttle_cfs_rq throttle对应的cfs_rq







阅读(563) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~