CFS调度算法调度时机的理解

上一篇文章分析了cfs调度算法中vruntime的计算，cfs以vruntime的键值组成红黑树，CFS调度算法优先调度红黑树中最左边的最小值。vruntime的大小决定CFS调度算法优先选择就绪队列中的哪个进程进行调度。下一步就是如何进行调度，调度在什么时候发生，比如:是否分配给该进程的CPU时间消耗完了，就会主动让出CPU，设置可以被调度的标志？

进程的调度分为两种类型，第一种是自愿让出当前的CPU，这种情况可能是由于当前正在运行的CPU没有获取到继续运行的资源，需要让出当前的CPU，进入sleep状态，等待需要的资源获取到后继续运行，或者本身调用schedule()函数进行调度，第二种情况下是非自愿的情况下，需要让出当前占用的CPU，比如：当前进程在CPU上消耗的时间已经用完或者在周期调度中断中发现有更高优先级进程需要被调度，则当前进程会被优先级更高的进程进行抢占，这种情况下可能是由于：scheduler_tick()函数进行调度。

调度器：

内核中有两个调度器，一个是主调度器，一个是周期性调度器。主调度器的函数为schedule()函数，周期性调度器的函数为scheduler_tick。周期性调度器和系统的时钟中断有关，这个值可以在/boot/config 文件中的配置参数查看具体的值，目前大部分x86的机型为配置为：CONFIG_HZ=1000，也就是1ms发生一次中断，1ms调用一次scheduler_tick函数，在scheduler_tick函数中会有判断是否需要调度当前的进程，比如：当前进程的CPU时间是否用完， 是否有更高有优先级的进程在就绪队列，上述情况都有可能导致设置进程的标志为TIF_NEED_RESCHED，然后在中断返回时，调用schedule()进行进程切换。

       调用schedule()函数进行进程调度，进行切换的时机分为下面三种方式：

1） 在阻塞过程中的进程，比如因为下面的互斥量mutex,  信号量semaphore,等待队列waitqueue等导致的阻塞。都会调用schedule（）函数进行进程的调度。

2） 在中断返回和用户空间返回过程中，检测标志位：TIF_NEED_RESCHED，查看进程是否需要调度，在时间中断处理函数中scheduler_tick，为了任务之间可以抢占，会设置该标志位。

void scheduler_tick(void)
     {
        int cpu = smp_processor_id();
         struct rq *rq = cpu_rq(cpu);
         struct task_struct *curr = rq->curr;
         struct rq_flags rf;
         unsigned long thermal_pressure;
         u64 resched_latency;

         arch_scale_freq_tick();
         sched_clock_tick();

         rq_lock(rq, &rf);

         update_rq_clock(rq);
         thermal_pressure = arch_scale_thermal_pressure(cpu_of(rq));
         update_thermal_load_avg(rq_clock_thermal(rq), rq, thermal_pressure);
         curr->sched_class->task_tick(rq, curr, 0); // (1) 调用cfs调度程序周期调度函数task_tick_fair
         if (sched_feat(LATENCY_WARN))
             resched_latency = cpu_resched_latency(rq);
         calc_global_load_tick(rq);

         rq_unlock(rq, &rf);

         if (sched_feat(LATENCY_WARN) && resched_latency)
             resched_latency_warn(cpu, resched_latency);

       perf_event_task_tick();
}

3） 被唤醒的进程不会立刻调用schedule()函数进行调度，而是被加入到cfs调度队列的就绪队列中，并且被设置为TIF_NEED_RESCHED。如果内核的配置文件被设置了 CONFIG_PREEMPTION=y，内核会根据配置文件设置了是否可抢占，进行相应的处理。

整个调度过程中，调度的触发和执行是分开的。上述调度的时机是确定的，通过上面的三个时机，是无法完全保障进程的CPU消耗完成后，就主动调用调度函数，进行进程的切换。

在周期调度过程中，有几个和调度相关的变量：

unsigned int sysctl_sched_min_granularity = 750000ULL;//最小调度间隔
static unsigned int sched_nr_latency = 8; //进程数 8
unsigned int sysctl_sched_latency = 6000000ULL //调度周期6ms

static void
  check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
  {
       unsigned long ideal_runtime, delta_exec;
     struct sched_entity *se;
     s64 delta;

       ideal_runtime = sched_slice(cfs_rq, curr);
      delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
     if (delta_exec > ideal_runtime) {
           resched_curr(rq_of(cfs_rq));
           /*
           ?* The current task ran long enough, ensure it doesn't get
          ?* re-elected due to buddy favours.
           ?*/
          clear_buddies(cfs_rq, curr);
           return;
       }

       /*
      ?* Ensure that a task that missed wakeup preemption by a
       ?* narrow margin doesn't have to wait for a full slice.
       ?* This also mitigates buddy induced latencies under load.
       ?确保一个被唤醒抢占的进程不必等待一个完整的调度周期才能够被调度，目的就是减少调度时延，通过上面的注释其实得不出来，该值为进程占用的最小CPU运行时间,delta_exec是当前进程实际已经占用的CPU时间，如果进程delta_exec（实际运行时间）大于sysctl_sched_min_granularity 就有可能会被设置可调度标志，本意就是为了确保如果有唤醒的进程，在保障当前进程最小运行时间的情况下，尽快进行调度。而不是等该进程完全消耗完CPU时间*/
      if (delta_exec < sysctl_sched_min_granularity)
          return;
se = __pick_first_entity(cfs_rq);
     delta = curr->vruntime - se->vruntime;
  //计算当前的vruntime和红黑树最左边的vruntime的差值，如果当前的vruntime小于红黑树最左边的vruntime就不设置调度标志。继续运行，因为当前正在运行进程的vruntime是最小的。
       if (delta < 0)
           return;
   //如果差值大于ideal_runtime则设置可调度标志，这里的一个场景应该是，如果一个A进程刚被唤醒，为了补充A进程，设置A进程的vruntime较小，小于当前运行的进程， 其两者的差值大于ideal_runtime，则发送调度。主要是为了不让进程等待较多的时间。虽然当前进程的CPU时间还没有消耗完，也需要被设置可调度。
       if (delta > ideal_runtime)
          resched_curr(rq_of(cfs_rq));
   }

调度周期（延迟）：

调度周期的含义为在一个调度周期内，保证就绪队列中的所有进程都会被调度一遍，默认的调度周期为：unsigned int sysctl_sched_latency    = 6000000ULL //调度周期6ms，如果当前进程数大于sched_nr_latency ，则调度周期设置为当前就绪队列数乘以* sysctl_sched_min_granularity  在__sched_period（）函数中计算：

static u64 __sched_period(unsigned long nr_running)
 {
     if (unlikely(nr_running > sched_nr_latency))
         return nr_running * sysctl_sched_min_granularity;
     else
         return sysctl_sched_latency;
 }

从上面的分析可以得出，由于在实际调度过程中涉及到多种因素，进程的调度其实没有严格按照进程理论中计算的CPU时间一样运行，因为调度的时机是确定的，特别是时钟中断的调度，在时钟中断中对进程占用的CPU时间进行判断时，大部分情况发生调度是在进程占用的CPU时间已经大于理论运行时间，因为这个是和时钟中断函数的调用周期有关系的，这是一种被动的调度。或者由于其他优先级更高的进程需要调度，当前进程应该让出CPU等多种因素的影响。只有在绝对理想的情况下才有可能出现每个进程占用的CPU时间，等于理论运行时间。比如：当前单核CPU的服务器，系统的tick是1ms的情况下，一共三个优先级权重一样的进程，每个进程应该分为2ms，在一个调度周期内，每个进程会占用2ms的CPU时间。但是在现实系统中基本上不存在此类情况，环境中可能是多个CPU核，tick可能是2m或者4ms，可能不断的有进程加入到就绪队列，也有进程进入睡眠等。都可能导致CPU的调度复杂度提升。        所以在内核中使用delta_exec变量记录进程真正占用的CPU时间，使用这个变量和理论运行时间进行对比，来判断是否进行调度。而不是delta_exec大于理论运行时间后，就立刻被调度。

注：在较新的内核版本中上面的值都无法进行sysctl和proc进行配置。