CFS 调度器的vruntime

   CFS调度算法中有一个重要的概念，进程运行的虚拟时间vruntime，CFS调度算法时间是根据vruntime进行进程调度的。本文结合自己对vruntime的理解进行整理和梳理。

    下面是理论上计算vruntime的公式：

  从上面的公式推导可以看出，在一个调度周期（调度周期是一个可变量，在一个调度周期内，保证每个就绪队列的进程都能够有机会运行）内“虚拟运行时间”是相等的，但是在CFS调度算法中是以vruntime的值作为红黑树的健值，CFS也是根据红黑树的健值进行进程的调度的，CFS调度的优先级是vruntime的值越小，优先级越高，越能够进行优先调用。

  从上面的CFS调度的原理看，为什么“虚拟运行时间”相等，但是在调度的时候又是按照“虚拟机运行时间”最小的值优先进行调用的呢。根据上面的公式“虚拟运行时间”不应该相等吗？ 怎么又会出来最小的“虚拟运行时间”呢？

  如果按照上面的公式进行推导的话“虚拟运行时间”确实是相同的。但是上面的公式计算是一种理想化的场景，但是在实际情况下，进程的调度涉及到多种因素，比如：周期性调度，进程因为各种原因进行了休眠、唤醒进程的加入等。因此这里公式的唯一一个不确定的变量就是进程的实际运行时间（内核中的变量为delta_exec），其实内核中针对实际运行时间的计算不是按照上面的公式进行套用的。

  Update_curr函数在内核中会被频繁的调用，该函数就是计算和更新vruntime的。

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
      {
//如果权重等于NICE_0_LOAD的话，直接返回delta，说明delta就是进程的实际运行时间。
      if (unlikely(se->load.weight != NICE_0_LOAD))
            delta = __calc_delta(delta, NICE_0_LOAD, &se->load);

      return delta;
}

__calc_delta 函数根据上面的公式，通过移位的方式完成虚拟时间的计算。

进程的实际运行时间，并不是按照上面的公式1进行计算的，而是实际运行的一个时间差值。在update_curr函数中计算得到的。

在周期性调度函数中，有下面的针对ideal_runtime的计算，该变量为curr进程本次调度周期内应该占用的CPU时间，如果实际运行的时间已经大于理论运行时间，就设置为进程为TIF_NEED_RESCHED标志，表示可以调度。

check_preempt_tick函数里面计算了进程理想的ideal_runtime。

我们看一下，curr进程应该占用的时间是如何计算的。

static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
    {
         unsigned int nr_running = cfs_rq->nr_running;
         struct sched_entity *init_se = se;
         unsigned int min_gran;
         u64 slice;

         if (sched_feat(ALT_PERIOD))
             nr_running = rq_of(cfs_rq)->cfs.h_nr_running;
         //根据就绪队列中的进程数量，计算调度周期。内核中如果进程数量小于8的，默认的调度周期为6ms,如果大于8，调度周期为一个动态调度的值。
          slice = __sched_period(nr_running + !se->on_rq);

         for_each_sched_entity(se) {
            struct load_weight *load;
            struct load_weight lw;
             struct cfs_rq *qcfs_rq;

            qcfs_rq = cfs_rq_of(se);
             load = &qcfs_rq->load;

             if (unlikely(!se->on_rq)) {
                  lw = qcfs_rq->load;

                update_load_add(&lw, se->load.weight);
                  load = &lw;
              }
//这里传递的时间为调度周期，curr进程权重，就绪队列权重，根据这些参数，按照公式1进行计算wall_time。最后返回通过计算得出理想情况的实际运行时间。从这里也可以看出，内核代码中并没有直接使用该方式，进而推导进程的实际运行时间和虚拟时间，而是根据进程的调用和调出的时间差计算时间运行时间的。所以这里进程的虚拟时间是不相等的，伴随着周期调度、进程的唤醒等各类操作。
             slice = __calc_delta(slice, se->load.weight, load);
        }
if (sched_feat(BASE_SLICE)) {
           if (se_is_idle(init_se) && !sched_idle_cfs_rq(cfs_rq))
                 min_gran = sysctl_sched_idle_min_granularity;
              else
                 min_gran = sysctl_sched_min_granularity;

            slice = max_t(u64, slice, min_gran);
         }

       return slice;
    }

上面讨论的都是进程调度的优先级，也就是上一个进程运行结束后，应该从就绪队列中选择那个进程继续运行。后续需要分析一下进程是退出CPU的几种方式？ 进程退出占用的CPU，然后才能进行后续的调度。