**CFS調度算法：**摒棄固定時間片，采用進程權重值的比重來量化計算實際運行時間，并引入虛擬時間和真實時間的概念，真實時間就是在物理時鐘下實際運行的時間，虛擬時間是實際運行時間與nice值為0對應的權值的比值。

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

然而事實上每個進程會涉及不同的優(yōu)先級，此時不同的進程應該由于優(yōu)先級的原因導致【真實運行時間的所占權重】不同才行，那么如何評估進程運行時間的長短？如何選擇下一個進程進行調度？

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

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

如下所示，通過cat/proc/$pid/sched查看某個進程調度信息，第二行se.vruntime就是虛擬運行時間：

由上面的展示也可以看出來調度相關的這些信息是存儲在調度實體se中，【每個進程描述符中都有每種調度類對應的調度實體，調度實體存放與該調度類相關的調度信息，并參與調度，CFS調度器對應的調度實體為struct sched_entity se,例如實時調度器對應的調度實體為struct sched_rt_entity rt】，CFS調度器的調度實體如下：

struct sched_entity
{
    struct load_weight      load;           /* for load-balancing負荷權重，這個決定了進程在CPU上的運行時間和被調度次數(shù) */
    struct rb_node          run_node;
    unsigned int            on_rq;          /*  是否在就緒隊列上  */

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

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