??? CFS調(diào)度算法中有一個重要的概念，進程運行的虛擬時間vruntime，CFS調(diào)度算法時間是根據(jù)vruntime進行進程調(diào)度的。本文結(jié)合自己對vruntime的理解進行整理和梳理。

??? 下面是理論上計算vruntime的公式：

?

從上面的公式推導(dǎo)可以看出，在一個調(diào)度周期（調(diào)度周期是一個可變量，在一個調(diào)度周期內(nèi)，保證每個就緒隊列的進程都能夠有機會運行）內(nèi)“虛擬運行時間”是相等的，但是在CFS調(diào)度算法中是以vruntime的值作為紅黑樹的健值，CFS也是根據(jù)紅黑樹的健值進行進程的調(diào)度的，CFS調(diào)度的優(yōu)先級是vruntime的值越小，優(yōu)先級越高，越能夠進行優(yōu)先調(diào)用。

??? 從上面的CFS調(diào)度的原理看，為什么“虛擬運行時間”相等，但是在調(diào)度的時候又是按照“虛擬機運行時間”最小的值優(yōu)先進行調(diào)用的呢。根據(jù)上面的公式“虛擬運行時間”不應(yīng)該相等嗎？ 怎么又會出來最小的“虛擬運行時間”呢？

??? 如果按照上面的公式進行推導(dǎo)的話“虛擬運行時間”確實是相同的。但是上面的公式計算是一種理想化的場景，但是在實際情況下，進程的調(diào)度涉及到多種因素，比如：周期性調(diào)度，進程因為各種原因進行了休眠、喚醒進程的加入等。因此這里公式的唯一一個不確定的變量就是進程的實際運行時間（內(nèi)核中的變量為delta_exec），其實內(nèi)核中針對實際運行時間的計算不是按照上面的公式進行套用的。

??? Update_curr函數(shù)在內(nèi)核中會被頻繁的調(diào)用，該函數(shù)就是計算和更新vruntime的。

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
      {
//如果權(quán)重等于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 函數(shù)根據(jù)上面的公式，通過移位的方式完成虛擬時間的計算。

進程的實際運行時間，并不是按照上面的公式1進行計算的，而是實際運行的一個時間差值。在update_curr函數(shù)中計算得到的。

在周期性調(diào)度函數(shù)中，有下面的針對ideal_runtime的計算，該變量為curr進程本次調(diào)度周期內(nèi)應(yīng)該占用的CPU時間，如果實際運行的時間已經(jīng)大于理論運行時間，就設(shè)置為進程為TIF_NEED_RESCHED標(biāo)志，表示可以調(diào)度。

check_preempt_tick函數(shù)里面計算了進程理想的ideal_runtime。

我們看一下，curr進程應(yīng)該占用的時間是如何計算的。

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;
         //根據(jù)就緒隊列中的進程數(shù)量，計算調(diào)度周期。內(nèi)核中如果進程數(shù)量小于8的，默認的調(diào)度周期為6ms,如果大于8，調(diào)度周期為一個動態(tài)調(diào)度的值。
          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;
              }
//這里傳遞的時間為調(diào)度周期，curr進程權(quán)重，就緒隊列權(quán)重，根據(jù)這些參數(shù)，按照公式1進行計算wall_time。最后返回通過計算得出理想情況的實際運行時間。從這里也可以看出，內(nèi)核代碼中并沒有直接使用該方式，進而推導(dǎo)進程的實際運行時間和虛擬時間，而是根據(jù)進程的調(diào)用和調(diào)出的時間差計算時間運行時間的。所以這里進程的虛擬時間是不相等的，伴隨著周期調(diào)度、進程的喚醒等各類操作。
             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;
    }

?上面討論的都是進程調(diào)度的優(yōu)先級，也就是上一個進程運行結(jié)束后，應(yīng)該從就緒隊列中選擇那個進程繼續(xù)運行。后續(xù)需要分析一下進程是退出CPU的幾種方式？ 進程退出占用的CPU，然后才能進行后續(xù)的調(diào)度。