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

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

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

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

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

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

由上面的展示也可以看出來調(diào)度相關(guān)的這些信息是存儲在調(diào)度實(shí)體se中，【每個進(jìn)程描述符中都有每種調(diào)度類對應(yīng)的調(diào)度實(shí)體，調(diào)度實(shí)體存放與該調(diào)度類相關(guān)的調(diào)度信息，并參與調(diào)度，CFS調(diào)度器對應(yīng)的調(diào)度實(shí)體為struct sched_entity se,例如實(shí)時調(diào)度器對應(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)重，這個決定了進(jìn)程在CPU上的運(yùn)行時間和被調(diào)度次數(shù) */
    struct rb_node          run_node;
    unsigned int            on_rq;          /*  是否在就緒隊列上  */

    u64                     exec_start;         /*  上次啟動的時間*/

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