????????上一篇文章分析了cfs調(diào)度算法中vruntime的計(jì)算，cfs以vruntime的鍵值組成紅黑樹，CFS調(diào)度算法優(yōu)先調(diào)度紅黑樹中最左邊的最小值。vruntime的大小決定CFS調(diào)度算法優(yōu)先選擇就緒隊(duì)列中的哪個(gè)進(jìn)程進(jìn)行調(diào)度。下一步就是如何進(jìn)行調(diào)度，調(diào)度在什么時(shí)候發(fā)生，比如:是否分配給該進(jìn)程的CPU時(shí)間消耗完了，就會(huì)主動(dòng)讓出CPU，設(shè)置可以被調(diào)度的標(biāo)志？

????????進(jìn)程的調(diào)度分為兩種類型，第一種是自愿讓出當(dāng)前的CPU，這種情況可能是由于當(dāng)前正在運(yùn)行的CPU沒有獲取到繼續(xù)運(yùn)行的資源，需要讓出當(dāng)前的CPU，進(jìn)入sleep狀態(tài)，等待需要的資源獲取到后繼續(xù)運(yùn)行，或者本身調(diào)用schedule()函數(shù)進(jìn)行調(diào)度，第二種情況下是非自愿的情況下，需要讓出當(dāng)前占用的CPU，比如：當(dāng)前進(jìn)程在CPU上消耗的時(shí)間已經(jīng)用完或者在周期調(diào)度中斷中發(fā)現(xiàn)有更高優(yōu)先級(jí)進(jìn)程需要被調(diào)度，則當(dāng)前進(jìn)程會(huì)被優(yōu)先級(jí)更高的進(jìn)程進(jìn)行搶占，這種情況下可能是由于：scheduler_tick()函數(shù)進(jìn)行調(diào)度。

調(diào)度器：

????????內(nèi)核中有兩個(gè)調(diào)度器，一個(gè)是主調(diào)度器，一個(gè)是周期性調(diào)度器。主調(diào)度器的函數(shù)為schedule()函數(shù)，周期性調(diào)度器的函數(shù)為scheduler_tick。周期性調(diào)度器和系統(tǒng)的時(shí)鐘中斷有關(guān)，這個(gè)值可以在/boot/config 文件中的配置參數(shù)查看具體的值，目前大部分x86的機(jī)型為配置為：CONFIG_HZ=1000，也就是1ms發(fā)生一次中斷，1ms調(diào)用一次scheduler_tick函數(shù)，在scheduler_tick函數(shù)中會(huì)有判斷是否需要調(diào)度當(dāng)前的進(jìn)程，比如：當(dāng)前進(jìn)程的CPU時(shí)間是否用完， 是否有更高有優(yōu)先級(jí)的進(jìn)程在就緒隊(duì)列，上述情況都有可能導(dǎo)致設(shè)置進(jìn)程的標(biāo)志為TIF_NEED_RESCHED，然后在中斷返回時(shí)，調(diào)用schedule()進(jìn)行進(jìn)程切換。

?????? 調(diào)用schedule()函數(shù)進(jìn)行進(jìn)程調(diào)度，進(jìn)行切換的時(shí)機(jī)分為下面三種方式：

1. 在阻塞過程中的進(jìn)程，比如因?yàn)橄旅娴幕コ饬縨utex, ?信號(hào)量semaphore,等待隊(duì)列waitqueue等導(dǎo)致的阻塞。都會(huì)調(diào)用schedule（）函數(shù)進(jìn)行進(jìn)程的調(diào)度。
2. 在中斷返回和用戶空間返回過程中，檢測(cè)標(biāo)志位：TIF_NEED_RESCHED，查看進(jìn)程是否需要調(diào)度，在時(shí)間中斷處理函數(shù)中scheduler_tick，為了任務(wù)之間可以搶占，會(huì)設(shè)置該標(biāo)志位。

   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) 調(diào)用cfs調(diào)度程序周期調(diào)度函數(shù)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. 被喚醒的進(jìn)程不會(huì)立刻調(diào)用schedule()函數(shù)進(jìn)行調(diào)度，而是被加入到cfs調(diào)度隊(duì)列的就緒隊(duì)列中，并且被設(shè)置為TIF_NEED_RESCHED。如果內(nèi)核的配置文件被設(shè)置了 CONFIG_PREEMPTION=y，內(nèi)核會(huì)根據(jù)配置文件設(shè)置了是否可搶占，進(jìn)行相應(yīng)的處理。整個(gè)調(diào)度過程中，調(diào)度的觸發(fā)和執(zhí)行是分開的。上述調(diào)度的時(shí)機(jī)是確定的，通過上面的三個(gè)時(shí)機(jī)，是無法完全保障進(jìn)程的CPU消耗完成后，就主動(dòng)調(diào)用調(diào)度函數(shù)，進(jìn)行進(jìn)程的切換。

在周期調(diào)度過程中，有幾個(gè)和調(diào)度相關(guān)的變量：

unsigned int sysctl_sched_min_granularity?????????? = 750000ULL;//最小調(diào)度間隔

static unsigned int sched_nr_latency = 8;???? //進(jìn)程數(shù) 8

unsigned int sysctl_sched_latency?????????? = 6000000ULL //調(diào)度周期6ms

我們重點(diǎn)分析一下?check_preempt_tick函數(shù)：

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.
       |確保一個(gè)被喚醒搶占的進(jìn)程不必等待一個(gè)完整的調(diào)度周期才能夠被調(diào)度，目的就是減少調(diào)度時(shí)延，通過上面的注釋其實(shí)得不出來，該值為進(jìn)程占用的最小CPU運(yùn)行時(shí)間,delta_exec是當(dāng)前進(jìn)程實(shí)際已經(jīng)占用的CPU時(shí)間，如果進(jìn)程delta_exec（實(shí)際運(yùn)行時(shí)間）大于sysctl_sched_min_granularity 就有可能會(huì)被設(shè)置可調(diào)度標(biāo)志，本意就是為了確保如果有喚醒的進(jìn)程，在保障當(dāng)前進(jìn)程最小運(yùn)行時(shí)間的情況下，盡快進(jìn)行調(diào)度。而不是等該進(jìn)程完全消耗完CPU時(shí)間*/
      if (delta_exec < sysctl_sched_min_granularity)
          return;
se = __pick_first_entity(cfs_rq);
     delta = curr->vruntime - se->vruntime;
  //計(jì)算當(dāng)前的vruntime和紅黑樹最左邊的vruntime的差值，如果當(dāng)前的vruntime小于紅黑樹最左邊的vruntime就不設(shè)置調(diào)度標(biāo)志。繼續(xù)運(yùn)行，因?yàn)楫?dāng)前正在運(yùn)行進(jìn)程的vruntime是最小的。
       if (delta < 0)
           return;
   //如果差值大于ideal_runtime則設(shè)置可調(diào)度標(biāo)志，這里的一個(gè)場(chǎng)景應(yīng)該是，如果一個(gè)A進(jìn)程剛被喚醒，為了補(bǔ)充A進(jìn)程，設(shè)置A進(jìn)程的vruntime較小，小于當(dāng)前運(yùn)行的進(jìn)程， 其兩者的差值大于ideal_runtime，則發(fā)送調(diào)度。主要是為了不讓進(jìn)程等待較多的時(shí)間。雖然當(dāng)前進(jìn)程的CPU時(shí)間還沒有消耗完，也需要被設(shè)置可調(diào)度。
       if (delta > ideal_runtime)
          resched_curr(rq_of(cfs_rq));
   }

調(diào)度周期（延遲）：

調(diào)度周期的含義為在一個(gè)調(diào)度周期內(nèi)，保證就緒隊(duì)列中的所有進(jìn)程都會(huì)被調(diào)度一遍，默認(rèn)的調(diào)度周期為：unsigned int sysctl_sched_latency?? ?= 6000000ULL //調(diào)度周期6ms，如果當(dāng)前進(jìn)程數(shù)大于sched_nr_latency ，則調(diào)度周期設(shè)置為當(dāng)前就緒隊(duì)列數(shù)乘以* sysctl_sched_min_granularity ?在__sched_period（）函數(shù)中計(jì)算：

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;
 }

?總結(jié)：

????????從上面的分析可以得出，由于在實(shí)際調(diào)度過程中涉及到多種因素，進(jìn)程的調(diào)度其實(shí)沒有嚴(yán)格按照進(jìn)程理論中計(jì)算的CPU時(shí)間一樣運(yùn)行，因?yàn)檎{(diào)度的時(shí)機(jī)是確定的，特別是時(shí)鐘中斷的調(diào)度，在時(shí)鐘中斷中對(duì)進(jìn)程占用的CPU時(shí)間進(jìn)行判斷時(shí)，大部分情況發(fā)生調(diào)度是在進(jìn)程占用的CPU時(shí)間已經(jīng)大于理論運(yùn)行時(shí)間，因?yàn)檫@個(gè)是和時(shí)鐘中斷函數(shù)的調(diào)用周期有關(guān)系的，這是一種被動(dòng)的調(diào)度。或者由于其他優(yōu)先級(jí)更高的進(jìn)程需要調(diào)度，當(dāng)前進(jìn)程應(yīng)該讓出CPU等多種因素的影響。只有在絕對(duì)理想的情況下才有可能出現(xiàn)每個(gè)進(jìn)程占用的CPU時(shí)間，等于理論運(yùn)行時(shí)間。比如：當(dāng)前單核CPU的服務(wù)器，系統(tǒng)的tick是1ms的情況下，一共三個(gè)優(yōu)先級(jí)權(quán)重一樣的進(jìn)程，每個(gè)進(jìn)程應(yīng)該分為2ms，在一個(gè)調(diào)度周期內(nèi)，每個(gè)進(jìn)程會(huì)占用2ms的CPU時(shí)間。但是在現(xiàn)實(shí)系統(tǒng)中基本上不存在此類情況，環(huán)境中可能是多個(gè)CPU核，tick可能是2m或者4ms，可能不斷的有進(jìn)程加入到就緒隊(duì)列，也有進(jìn)程進(jìn)入睡眠等。都可能導(dǎo)致CPU的調(diào)度復(fù)雜度提升。 ???????所以在內(nèi)核中使用delta_exec變量記錄進(jìn)程真正占用的CPU時(shí)間，使用這個(gè)變量和理論運(yùn)行時(shí)間進(jìn)行對(duì)比，來判斷是否進(jìn)行調(diào)度。而不是delta_exec大于理論運(yùn)行時(shí)間后，就立刻被調(diào)度。

注：在較新的內(nèi)核版本中上面的值都無法進(jìn)行sysctl和proc進(jìn)行配置。

?