**CFS調(diào)度算法：**摒棄固定時(shí)間片，采用進(jìn)程權(quán)重值的比重來量化計(jì)算實(shí)際運(yùn)行時(shí)間，并引入虛擬時(shí)間和真實(shí)時(shí)間的概念，真實(shí)時(shí)間就是在物理時(shí)鐘下實(shí)際運(yùn)行的時(shí)間，虛擬時(shí)間是實(shí)際運(yùn)行時(shí)間與nice值為0對(duì)應(yīng)的權(quán)值的比值。

**虛擬時(shí)間片引入：**假設(shè)進(jìn)程不存在優(yōu)先級(jí)區(qū)分，那么只要保證每個(gè)進(jìn)程的實(shí)際運(yùn)行時(shí)間相同即可，能做到絕對(duì)公平。調(diào)度時(shí)，調(diào)度器只需要記錄每個(gè)進(jìn)程的實(shí)際時(shí)間,每次調(diào)度時(shí)挑出【已經(jīng)運(yùn)行時(shí)間最短的進(jìn)程】。

然而事實(shí)上每個(gè)進(jìn)程會(huì)涉及不同的優(yōu)先級(jí)，此時(shí)不同的進(jìn)程應(yīng)該由于優(yōu)先級(jí)的原因?qū)е隆菊鎸?shí)運(yùn)行時(shí)間的所占權(quán)重】不同才行，那么如何評(píng)估進(jìn)程運(yùn)行時(shí)間的長短？如何選擇下一個(gè)進(jìn)程進(jìn)行調(diào)度？

由此引入虛擬運(yùn)行時(shí)間【希望不同的進(jìn)程根據(jù)優(yōu)先級(jí)在一個(gè)調(diào)度延遲【調(diào)度延遲就是保證每一個(gè)可運(yùn)行進(jìn)程都至少運(yùn)行一次的時(shí)間間隔】內(nèi)分配的物理時(shí)間通過一個(gè)公式計(jì)算得到一個(gè)相同的值，稱這個(gè)值為虛擬時(shí)間】，當(dāng)選擇下一個(gè)進(jìn)程執(zhí)行的時(shí)候，找出虛擬時(shí)間最小的進(jìn)程即可。虛擬時(shí)間要保證優(yōu)先級(jí)高的進(jìn)程的虛擬時(shí)間過得慢一些，優(yōu)先級(jí)低的進(jìn)程的虛擬時(shí)間快一些。

引入虛擬運(yùn)行時(shí)間，CFS中就緒隊(duì)列使用一棵以虛擬時(shí)間為鍵的紅黑樹將調(diào)度實(shí)體組織起來，利用紅黑樹的特性，虛擬時(shí)間最短的進(jìn)程在紅黑樹的最左端，調(diào)度器每次選擇位于紅黑樹最左端的虛擬時(shí)間對(duì)應(yīng)的調(diào)度實(shí)體參與調(diào)度。

如下所示，通過cat/proc/$pid/sched查看某個(gè)進(jìn)程調(diào)度信息，第二行se.vruntime就是虛擬運(yùn)行時(shí)間：

由上面的展示也可以看出來調(diào)度相關(guān)的這些信息是存儲(chǔ)在調(diào)度實(shí)體se中，【每個(gè)進(jìn)程描述符中都有每種調(diào)度類對(duì)應(yīng)的調(diào)度實(shí)體，調(diào)度實(shí)體存放與該調(diào)度類相關(guān)的調(diào)度信息，并參與調(diào)度，CFS調(diào)度器對(duì)應(yīng)的調(diào)度實(shí)體為struct sched_entity se,例如實(shí)時(shí)調(diào)度器對(duì)應(yīng)的調(diào)度實(shí)體為struct sched_rt_entity rt】，CFS調(diào)度器的調(diào)度實(shí)體如下：

struct sched_entity
{
    struct load_weight      load;           /* for load-balancing負(fù)荷權(quán)重，這個(gè)決定了進(jìn)程在CPU上的運(yùn)行時(shí)間和被調(diào)度次數(shù) */
    struct rb_node          run_node;
    unsigned int            on_rq;          /*  是否在就緒隊(duì)列上  */

    u64                     exec_start;         /*  上次啟動(dòng)的時(shí)間*/

    u64                     sum_exec_runtime;
    u64                     vruntime;        /* 虛擬運(yùn)行時(shí)間*/
    u64                     prev_sum_exec_runtime;
    /* rq on which this entity is (to be) queued: */
    struct cfs_rq           *cfs_rq;
    ...
};