Linux CFS虛擬時間

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

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

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

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

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

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

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

struct sched_entity
{
    struct load_weight      load;           /* for load-balancing負荷權重，這個決定了進程在CPU上的運行時間和被調(diào)度次數(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;
    ...
};