閱讀材料cfs調(diào)度算法介紹

1、CFS 算法介紹一、 概述首先簡單介紹一下基本的設(shè)計思路。CFS 思路很簡單，就是根據(jù)各個進程的權(quán)重分配運行時間。進程的運行時間計算公式為：分配給進程的運行時間 = 調(diào)度周期 * 進程權(quán)重 / 所有進程權(quán)重之和(公式 1)調(diào)度周期，就是將所有處于 TASK_RUNNING 態(tài)進程都調(diào)度一遍的時間，差不多相當于 O(1)調(diào)度算法中運行隊列和過期隊列切換一次的時間。舉個例子，比如只有兩個進程 A、B，權(quán)重分別為 1 和 2，調(diào)度周期設(shè)為 30ms，那么分配給A 的CPU 時間為 30ms * (1/(1+2) = 10ms 而B 的CPU 時間為 30ms * (2/(1+2) = 20ms 那么

2、在這 30ms 中 A 將運行 10ms，B 將運行 20ms。調(diào)度的公平并不體現(xiàn)在實際運行時間上，而是體現(xiàn)在另外一個量上面：虛擬運行時間（vruntime）。實際運行時間到 vruntime 的換算公式：vruntime = 實際運行時間 * 1024 / 進程權(quán)重(公式 2)這里直接寫 1024， 實際上它等于 nice 為 0 的進程的權(quán)重，代碼中是 NICE_0_LOAD。也就是說，所有進程都以 nice 為 0 的進程的權(quán)重 1024 作為基準，計算自己的 vruntime 增加速度。還以上面 AB 兩個進程為例，B 的權(quán)重是 A的 2 倍，那么 B 的 vruntime 增加速度只

3、有 A 的一半?，F(xiàn)在把公式 2 中的實際運行時間用公式 1 來替換，可以得到如下結(jié)果：vruntime = (調(diào)度周期 * 進程權(quán)重 / 所有進程總權(quán)重) * 1024 / 進程權(quán)重= 調(diào)度周期 * 1024 / 所有進程總權(quán)重(公式 3)所有進程 vruntime 增長速度是一樣的，這就是“公平”。CFS 算法利用 vruntime 來選擇運行的進程，誰的 vruntime 值較小就說明它以前占用 cpu 的時間較短，受到了“”對待，因此下一個運行進程就是它。這樣既能公平選擇進程，又能保證高優(yōu)先級進程獲得較多的運行時間。這就是 CFS 的主要。補充一下權(quán)重的來源，權(quán)重跟進程 nice 值之間

4、有一一對應的關(guān)系，可以通過全局數(shù)組 prio_to_weight 來轉(zhuǎn)換，nice 值越大，權(quán)重越低。另外，與之前的 Linux 調(diào)度器不同，CFS 沒有將任務在運行隊列中，樹 是一個樹，CFS了一個以 vruntime 為順序的樹（參見圖 1 ）。具有很多有趣、有用的屬性。首先，它是自平衡的，這意味著樹上沒有路徑比任何其他路徑長兩倍以上。 第二，樹上的操作時間復雜度為 O(log n) （ n 是樹點的數(shù)量）。這意味著可以快速高效地或刪除任務。1圖 1任務在以時間為順序的樹中（由 sched_entity 對象表示），對處理器需求最多的任務 （vruntime 最低）在樹的左側(cè)，處理器需求最

5、少的任務（vruntime 最高）在樹的右側(cè)。 調(diào)度器選取樹最左端的節(jié)點調(diào)度為下一個以便保持公平性。被調(diào)度下 CPU 的任務，將其運行時間添加到其 vruntime，然后如果任務可運行，再插回到樹中。樹的內(nèi)容從右側(cè)遷移到左側(cè)以保持公平。因此，每個可運行的任務都會追趕其他任務以維持整個可運行任務集合的執(zhí)行平衡。2二、 重要數(shù)據(jù)結(jié)構(gòu)三個與調(diào)度相關(guān)的重要數(shù)據(jù)結(jié)構(gòu)：task_struct：任務描述符（進程描述符） sched_entity：調(diào)度實體 sched_class：調(diào)度策略Linux 內(nèi)的所有任務都由稱為 task_struct 的任務結(jié)構(gòu)表示。該結(jié)構(gòu)（以及其他相關(guān)內(nèi)容）完整地描述了任務并包括

6、了任務的當前狀態(tài)、其堆棧、進程標識、優(yōu)先級（靜態(tài)和動態(tài)）等等?？梢栽?./linux/include/linux/sched.h 中找到這些內(nèi)容。但是因為不是所有任務都是可運行的，在 task_struct 中不會發(fā)現(xiàn)任何與 CFS相關(guān)的字段。相反，會有一個名為 sched_entity 的新結(jié)構(gòu)來圖 2）。調(diào)度信息（參見圖 2CFS去掉了 struct prio_array，并引入調(diào)度實體（scheduling entity）和調(diào)度類（scheduling classes），分別由 struct sched_entity 和 struct sched_class 定義。因此，task_str

7、uct 包含關(guān)于 sched_entity 和 sched_class 這兩種結(jié)構(gòu)的信息：1. task_struct 結(jié)構(gòu)3struct task_struct /* Defined in 2.6.23:/usr/include/linux/sched.h */.-struct prio_array *array;struct sched_entity 該結(jié)構(gòu)包含了完整的信息，用于實現(xiàn)對單個任務或任務組的調(diào)度。它可用于實現(xiàn)組調(diào)度。調(diào)度實體可能與進程沒有關(guān)聯(lián)。2. sched_entity 結(jié)構(gòu)struct sched_class 該調(diào)度類類似于一個模塊鏈，協(xié)助內(nèi)核調(diào)度程序工作。每個調(diào)度程序模

8、塊需要實現(xiàn) struct sched_class建議的一組函數(shù)。3. sched_class結(jié)構(gòu)4struct sched_class /* Defined in 2.6.23:/usr/include/linux/sched.h */ struct sched_class *next;void (*enqueue_task) (struct rq *rq， struct task_struct *p，wakeup);void (*dequeue_task) (struct rq *rq， struct task_struct *p，sleep); void (*yield_task) (st

9、ruct rq *rq， struct task_struct *p);void (*check_preempt_curr) (struct rq *rq， struct task_struct *p);struct task_struct * (*pick_next_task) (struct rq *rq);void (*put_prev_task) (struct rq *rq， struct task_struct *p);unsigned long (*load_balance) (struct rq *this_rq，this_cpu， struct rq *busiest，uns

10、igned long max_nr_move， unsigned long max_load_move， struct sched_*sd， enum cpu_idle_type idle，*all_pinned，*this_best_prio);void (*set_curr_task) (struct rq *rq);void (*task_tick) (struct rq *rq， struct task_struct *p); void (*task_new) (struct rq *rq， struct task_struct *p);struct sched_entity /* D

11、efined in 2.6.23:/usr/include/linux/sched.h */long wait_runtime; /* Amount of time the entity must run toe compley */* fair and balanced.*/s64 fair_key;struct load_weight load;/* for load-balancing */struct rb_node run_node;/* To be part of Red-black tree data structure */ unsignedon_rq;.;+ struct s

12、ched_entity se;+ struct sched_class *sched_class;.;3 中的函數(shù)：enqueue_task：當某個任務進入可運行狀態(tài)時，該函數(shù)將得到調(diào)用。它將樹中，并對 nr_running 變量加 1。調(diào)度實體（進程）放入dequeue_task：當某個任務退出可運行狀態(tài)時調(diào)用該函數(shù)，它將從中去掉對應的調(diào)度實體，并從 nr_running 變量中減 1。樹yield_task：在 compat_yield sysctl 關(guān)閉的情況下，該函數(shù)實際上執(zhí)行先出隊隊；在這種情況下，它將調(diào)度實體放在樹的最右端。check_preempt_curr：該函數(shù)將檢查當前運行

13、的任務是否被搶占。在實際搶占正在運行的任務之前，CFS 調(diào)度程序模塊將執(zhí)行公平性測試。這將驅(qū)動喚醒式（wakeup）搶占。pick_next_task：該函數(shù)選擇接下來要運行的最合適的進程。 load_balance：每個調(diào)度程序模塊實現(xiàn)兩個函數(shù)，load_balance_start() 和 load_balance_next() ，使用這兩個函數(shù)實現(xiàn)一個迭代器，在模塊的 load_balance 例程中調(diào)用。內(nèi)核調(diào)度程序使用這種方法實現(xiàn)由調(diào)度模塊管理的進程的負載平衡。set_curr_task：當任務修改其調(diào)度類或修改其任務組時，將調(diào)用這個函數(shù)。 task_tick：該函數(shù)通常調(diào)用自 tim

14、e tick 函數(shù)；它可能引起進程切換。這將驅(qū)動運行時（running）搶占。task_new：內(nèi)核調(diào)度程序為調(diào)度模塊提供了管理新任務啟動的機會。CFS調(diào)度模塊使用它進行組調(diào)度，而用于實時任務的調(diào)度模塊則不會使用這個函數(shù)。運行隊列中與 CFS 有關(guān)的字段對于每個運行隊列，都提供了一種結(jié)構(gòu)來保存相關(guān)樹的信息。4. cfs_rq結(jié)構(gòu)5struct cfs_rq /* Defined in 2.6.23:kernel/sched.c */ struct load_weight load;unsigned long nr_running;s64 fair_clock; /* runqueue wide

15、 global clock */ u64 exec_clock;s64 wait_runtime; u64 sleeper_bonus;unsigned long wait_runtime_overruns， wait_runtime_underruns;struct rb_root tasks_timeline; /* Pos to the root of the rb-tree*/struct rb_node *rb_leftmost; /* Pos to mosigible task to give the CPU */ struct rb_node *rb_load_balance_c

16、urr;#ifdef CONFIG_FAIR_GROUP_SCHEDstruct sched_entity *curr; /* Currently running entity */struct rq *rq;/* cpu runqueue to which this cfs_rq is attached */.;6.#endif;三、 具體調(diào)度過程（代碼）3.1 進程創(chuàng)建主要流程：Linux 創(chuàng)建進程使用 fork 或者 clone 或者 vfork 等系統(tǒng)調(diào)用，最終都會到do_fork。如果沒有設(shè)置 CLONE_STOPPED，則會進入 wake_up_new_task 函數(shù)。wake_u

17、p_new_tasktask_new_fairplace_entitycheck_preempt_currwakeup_preempt_entitytask_new_fairplace_entity 是更新新進程的 vruntime 值，以便把它樹。它以 cfs 隊列的 min_vruntime 為基準，再加上進程在一次調(diào)度周期中所增長的虛擬運行時（sched_vslice）。這里把進程的已經(jīng)運行時間設(shè)為一個較大的值，這樣做的原因是：假設(shè)新進程都能獲得最小的 vruntime(min_vruntime)，那么新進程會第一個被調(diào)度運行，這樣程序員就能通過不斷的 fork 新進程來讓自己的程序一直

18、占據(jù) CPU，這顯然是不合理的。min_vruntime這是每個 cfs 隊列一個的變量，它一般小于等于所有就緒態(tài)進程的最小vruntime，也有例外，比如對睡眠進程進行時間補償會導致 vruntime小于 min_vruntime。至于 sched_vslice 計算細節(jié)暫且不細看，大體上說就是把概述中給出的兩個公式結(jié)合起來如下：sched_vslice = (調(diào)度周期 * 進程權(quán)重 / 所有進程總權(quán)重) * NICE_0_LOAD /進程權(quán)重也就是算出進程應分配的實際 cpu 時間，再把它轉(zhuǎn)化為 vruntime。把這個 vruntime 加在進程上之后，就相當于認為新進程在這一輪調(diào)度中已

19、經(jīng)運行過了。新進程的 vruntime 確定之后有一個判斷，同時滿足以下幾個條件時，交換父子進程的 vruntime：1.2.3.4.sysctl 設(shè)置了子進程優(yōu)先運行fork 出的子進程與父進程在同一個 cpu 上父進程不為空父進程的 vruntime 小于子進程的 vruntime最后，調(diào)用 enqueue_task_fair 將新進程CFS樹中。check_preempt_curr這個函數(shù)就直接調(diào)用了 check_preempt_wakeup。首先是有兩個指針與進程調(diào)度策略有很大關(guān)系，last 和 next。如果這兩個指針不為 NULL，那么 last 指向最近被調(diào)度出去的進程，next

20、 指向被調(diào)度上 cpu 的進程。例如 A 正在運行，被 B 搶占，那么 last 指向 A，next 指向 B。當 CFS 在調(diào)度點選擇下一個運行進程時，會優(yōu)先照顧這兩個進程。這兩個指使用一次，就是在上面這個函數(shù)退出后，返回用戶空間時會觸發(fā) schedule，7在那里選擇下一個調(diào)度進程時會優(yōu)先選擇 next，次優(yōu)先選擇 last，選擇完后，就會清空這兩個指針。這樣設(shè)計的原因是，在上面的函數(shù)中檢測結(jié)果是可以搶占并不代表已經(jīng)搶占，而只是設(shè)置了調(diào)度標志，在最后觸發(fā) schedule 時搶占進程 B 并不一定是最終被調(diào)度的進程。因為判斷能否搶占的根據(jù)是 vruntime 小，但樹中可能有比搶占進程 B

21、 的 vruntime 更小的進程 C，這樣在調(diào)度時就會選中 C 而不是 B。但是當然希望優(yōu)先調(diào)度 B，因為就是為了運行 B 才設(shè)置了調(diào)度標志，所以用 next 指針指向 B，以便給 B 一定優(yōu)待，如果 B 的 vruntime 太大，那還是繼續(xù)運行被搶占進程 A 比較合理，因此 last 指向被搶占進程，因此這里對 A 也是有一點優(yōu)待，如果被搶占進程 A 的 vruntime 也太大，只好從樹中挑一個vruntime 最小的了。不管 next 和 last 指向的進程是否被成功調(diào)度，一旦選出下一個進程，就立刻清空這兩個指針。然后調(diào)用 wakeup_preempt_entity 檢測是否滿足搶

22、占條件，如果滿足（返回值為 1）則對當前進程設(shè)置 TIF_NEED_RESCHED 標志，在退出系統(tǒng)調(diào)用時會觸發(fā) schedule 函數(shù)進行進程切換。wakeup_preempt_entity(se， pse)，如何判斷后者是否能夠搶占前者？這個函數(shù)返回-1 表示新進程 vruntime 大于當前進程，當然不能搶占；返回 0表示雖然新進程 vruntime 比當前進程小，但是沒有小到超過調(diào)度粒度，一般也不能搶占；返回 1 表示新進程 vruntime 比當前進程小的超過了調(diào)度粒度，可以搶占。調(diào)度粒度假設(shè)進程A 和B 的vruntime 很接近，那么 A 先運行了一個tick， vruntime

23、 比 B 大了，B 又運行一個 tick，vruntime 又比 A 大了，又切換到 A，這樣就會在 AB 間頻繁切換，對性能影響很大，因此如果當前進程的時間沒有用完，就只有當有進程的 vruntime 比當前進程小超過調(diào)度粒度時，才能進行進程切換。3.2 進程被喚醒主要看函數(shù) try_to_wake_up。該函數(shù)會調(diào)用相關(guān)函數(shù)計算進程的 vruntime 并將其樹。需要注意的是 try_to_wake_up 也會調(diào)用 place_entity 來計算 vruntime，但是與新建進程走不同的條件分支。設(shè)想一個任務睡眠了很長時間，它的 vruntime 就一直不會更新，這樣當它醒來時 vrun

24、time 會遠遠小于運行隊列上的任何一個任務，于是它會長期占用 CPU，這顯然是不合理的。所以這要對喚醒任務的 vruntime 進行一些調(diào)整，可以看到，這里是用min_vruntime 減去一個thresh，這個 thresh 的計算過程就是將sysctl_sched_latency換算成進程的 vruntime，而這個 sysctl_sched_latency 就是默認的調(diào)度周期，單核 CPU 上一般為 20ms。之所以要減去一個值是為了對睡眠進程做一個補償，能讓它醒來時可以快速得到 CPU。這個設(shè)計非常聰明，以前 O(1)調(diào)度器有一個復雜的公式，用來區(qū)分交互式進CPU 密集型進程，參考

25、ULK 等書，而現(xiàn)在 CFS 無須再使用那個復雜的公式了，只要是常睡眠的進程，它被喚醒時一定會有很小的 vruntime，可以立刻運行，省卻了很多特殊情況的處理。同時還要注意代碼中提到 ensure we never gain time by being placed8backwards，本來這里是給因為長時間睡眠而 vruntime 遠遠小于 min_vruntime 的進程補償?shù)模怯行┻M程只睡眠很短時間，這樣在它醒來后 vruntime 還是大于 min_vruntime，不能讓進程通過睡眠獲得額外的運行時間，所以最后選擇計算出的補償時間與進程原本 vruntime 中的較大者。3.3

26、 主動調(diào)度進程調(diào)度函數(shù) schedule。下面這兩個語句是調(diào)度算法的重點： prev-sched_class-put_prev_task(rq, prev);next = pick_next_task(rq, prev);首先看 put_prev_task，它等于 put_prev_task_fair，后者基本上就是直接調(diào)用 put_prev_entity。再回到 schedule pick_next_task_fair。中看看 pick_next_task 函數(shù)， 基本上也就是直接調(diào)用91. sic struct task_struct *pick_next_task_fair(struct

27、 rq *rq) 2. 3.struct task_struct *p;1. sic void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev) 2. 3./* If still on the runqueue then deactivate_task()* was not called and update_curr() has to be done:6.*/記得這里的 on_rq 嗎？在 schedule 函數(shù)中如果進程狀態(tài)不是 TASK_RUNNING，/那么會調(diào)用 deactivate_task 將 pr

28、ev 移出運行隊列，on_rq 清零。因此這里也是只有當/prev 進程仍然在運行態(tài)的時候才需要更新 vruntime 等信息。/如果 prev 進程因為被搶占或者因為時間到了而被調(diào)度出去則 on_rq 仍然為 1if (prev-on_rq)update_curr(cfs_rq);check_spread(cfs_rq, prev);/這里也一樣，只有當 prev 進程仍在運行狀態(tài)的時候才需要更新 vruntime 信息/實際上正在 cpu 上運行的進程是不在樹中的，只有在等待 CPU 的進程才在樹/因此這里將調(diào)度出的進程重新加入樹。on_rq 并不代表在樹中，而代表在運行狀態(tài)if (pre

29、v-on_rq) update_ss_wait_start(cfs_rq, prev);/* Put current backo the tree. */這個函數(shù)就是把進程以(vruntime-min_vruntime)為 key 加入到樹中 enqueue_entity(cfs_rq, prev);22./沒有當前進程了，這個當前進程將在 pick_next_task 中更新cfs_rq-curr = NULL;25. 主要看下 pick_next_entity 和 set_next_entity。101. sic struct sched_entity *pick_next_entity(

30、struct cfs_rq *cfs_rq) 2. / pick_next_entity 就是直接選擇樹緩存的最左結(jié)點，也就是 vruntime 最小的結(jié)點struct sched_entity *se = pick_next_entity(cfs_rq);/下面的 wakeup_preempt_entity 已經(jīng)講過，忘記的同學可以到上面看下/這里就是前面所說優(yōu)先照顧 next 和 last 進程，只有當 pick_next_entity 選出來的進程/的 vruntime 比 next 和 last 都小超過調(diào)度粒度時才輪到它運行，否則就是 next 或者 lastif (cfs_rq-n

31、ext & wakeup_preempt_entity(cfs_rq-next, se) next;if (cfs_rq-last & wakeup_preempt_entity(cfs_rq-last, se) last;return se;13. sic voidset_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)16. /* current is not kept withhe tree. */if (se-on_rq) * Any task has to be enqueued before it get to

32、execute on* a CPU. So account for the time it spent waiting on the* runqueue.22.*/update_ss_wait_end(cfs_rq, se);/就是把結(jié)點從樹上取下來。前面，占用 CPU 的進程不在樹上 dequeue_entity(cfs_rq, se);26.update_ss_curr_start(cfs_rq, se);cfs_rq-curr = se; /OK，在 put_prev_entity 中清空的 curr 在這里被更新struct cfs_rq *cfs_rq = &rq-cfs;struc

33、t sched_entity *se;if (unlikely(!cfs_rq-nr_running)return NULL;do /這兩個函數(shù)是重點，選擇下一個要執(zhí)行的任務se = pick_next_entity(cfs_rq);set_next_entity(cfs_rq, se);cfs_rq = group_cfs_rq(se); while (cfs_rq);p = task_of(se);hrtick_start_fair(rq, p);return p;17. 3.4 時鐘中斷主要函數(shù)是 entity_tick，entity_tick 函數(shù)就是更新狀態(tài)信息，然后檢測是否滿足搶占

34、條件。更新信息是通過調(diào)用 update_curr(cfs_rq)來完成的。111. sic void update_curr(struct cfs_rq *cfs_rq) 2. struct sched_entity *curr = cfs_rq-curr;u64 now = rq_of(cfs_rq)-clock; /這個 clock 剛剛在 scheduler_tick 中更新過unsigned long delta_exec;6./* Get the amount of time the current task was running* since the last time we c

35、hanged load (this cannot* overflow on 32 bits):10.*/exec_start的是上一次調(diào)用update_curr 的時間用當前時間減去exec_start/就得到了從上次計算 vruntime 到現(xiàn)在進程又運行的時間，用這個時間換算成 vruntime/然后加到 vruntime 上，這一切是在 update_curr 中完成的delta_exec = (unsigned long)(now - curr-exec_start); update_curr(cfs_rq, curr, delta_exec);curr-exec_start = no

36、w;if (entity_is_task(curr) struct task_struct *curtask = task_of(curr);ccct_charge(curtask, delta_exec);account_group_exec_runtime(curtask, delta_exec);21.22. 23. /* Update the current tasks runtime sistics. Skip current taskst* are not in our scheduling class.26. */sic inline void update_curr(struc

37、t cfs_rq *cfs_rq, struct sched_entity *curr,unsigned long delta_exec)30. unsigned long delta_exec_weighted;/前面說的 sum_exec_runtime 就是在這里計算的，它等于進程從創(chuàng)建開始占用 CPU 的總時間/將進程運行總時間保存到 prev_.中，這樣進程本次調(diào)度的運行時間可以用下面公式計算：/進程本次運行已占用 CPU 時間 = sum_exec_runtime - prev_sum_exec_runtime/這里 sum_exec_runtime 會在每次時鐘 tick 中更新se-prev_sum_exec_runtime = se-sum_exec_runtime;33. 更新完 CFS 狀態(tài)之后回到 entity_tick 中，這時需要檢