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

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

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

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

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

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

6、了任務(wù)的當(dāng)前狀態(tài)、其堆棧、進(jìn)程標(biāo)識、優(yōu)先級（靜態(tài)和動(dòng)態(tài)）等等?？梢栽?./linux/include/linux/sched.h 中找到這些內(nèi)容。但是因?yàn)椴皇撬腥蝿?wù)都是可運(yùn)行的，在 task_struct 中不會(huì)發(fā)現(xiàn)任何與 CFS相關(guān)的字段。相反，會(huì)有一個(gè)名為 sched_entity 的新結(jié)構(gòu)來圖 2）。調(diào)度信息（參見圖 2CFS去掉了 struct prio_array，并引入調(diào)度實(shí)體（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)包含了完整的信息，用于實(shí)現(xiàn)對單個(gè)任務(wù)或任務(wù)組的調(diào)度。它可用于實(shí)現(xiàn)組調(diào)度。調(diào)度實(shí)體可能與進(jìn)程沒有關(guān)聯(lián)。2. sched_entity 結(jié)構(gòu)struct sched_class 該調(diào)度類類似于一個(gè)模塊鏈，協(xié)助內(nèi)核調(diào)度程序工作。每個(gè)調(diào)度程序模

8、塊需要實(shí)現(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：當(dāng)某個(gè)任務(wù)進(jìn)入可運(yùn)行狀態(tài)時(shí)，該函數(shù)將得到調(diào)用。它將樹中，并對 nr_running 變量加 1。調(diào)度實(shí)體（進(jìn)程）放入dequeue_task：當(dāng)某個(gè)任務(wù)退出可運(yùn)行狀態(tài)時(shí)調(diào)用該函數(shù)，它將從中去掉對應(yīng)的調(diào)度實(shí)體，并從 nr_running 變量中減 1。樹yield_task：在 compat_yield sysctl 關(guān)閉的情況下，該函數(shù)實(shí)際上執(zhí)行先出隊(duì)隊(duì)；在這種情況下，它將調(diào)度實(shí)體放在樹的最右端。check_preempt_curr：該函數(shù)將檢查當(dāng)前運(yùn)行

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

14、e tick 函數(shù)；它可能引起進(jìn)程切換。這將驅(qū)動(dòng)運(yùn)行時(shí)（running）搶占。task_new：內(nèi)核調(diào)度程序?yàn)檎{(diào)度模塊提供了管理新任務(wù)啟動(dòng)的機(jī)會(huì)。CFS調(diào)度模塊使用它進(jìn)行組調(diào)度，而用于實(shí)時(shí)任務(wù)的調(diào)度模塊則不會(huì)使用這個(gè)函數(shù)。運(yùn)行隊(duì)列中與 CFS 有關(guān)的字段對于每個(gè)運(yùn)行隊(duì)列，都提供了一種結(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 進(jìn)程創(chuàng)建主要流程：Linux 創(chuàng)建進(jìn)程使用 fork 或者 clone 或者 vfork 等系統(tǒng)調(diào)用，最終都會(huì)到do_fork。如果沒有設(shè)置 CLONE_STOPPED，則會(huì)進(jìn)入 wake_up_new_task 函數(shù)。wake_u

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

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

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

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

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

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

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

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

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

26、 主動(dòng)調(diào)度進(jìn)程調(diào)度函數(shù) schedule。下面這兩個(gè)語句是調(diào)度算法的重點(diǎn)： 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ù)中如果進(jìn)程狀態(tài)不是 TASK_RUNNING，/那么會(huì)調(diào)用 deactivate_task 將 pr

28、ev 移出運(yùn)行隊(duì)列，on_rq 清零。因此這里也是只有當(dāng)/prev 進(jìn)程仍然在運(yùn)行態(tài)的時(shí)候才需要更新 vruntime 等信息。/如果 prev 進(jìn)程因?yàn)楸粨屨蓟蛘咭驗(yàn)闀r(shí)間到了而被調(diào)度出去則 on_rq 仍然為 1if (prev-on_rq)update_curr(cfs_rq);check_spread(cfs_rq, prev);/這里也一樣，只有當(dāng) prev 進(jìn)程仍在運(yùn)行狀態(tài)的時(shí)候才需要更新 vruntime 信息/實(shí)際上正在 cpu 上運(yùn)行的進(jìn)程是不在樹中的，只有在等待 CPU 的進(jìn)程才在樹/因此這里將調(diào)度出的進(jìn)程重新加入樹。on_rq 并不代表在樹中，而代表在運(yùn)行狀態(tài)if (pre

29、v-on_rq) update_ss_wait_start(cfs_rq, prev);/* Put current backo the tree. */這個(gè)函數(shù)就是把進(jìn)程以(vruntime-min_vruntime)為 key 加入到樹中 enqueue_entity(cfs_rq, prev);22./沒有當(dāng)前進(jìn)程了，這個(gè)當(dāng)前進(jìn)程將在 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é)點(diǎn)，也就是 vruntime 最小的結(jié)點(diǎn)struct sched_entity *se = pick_next_entity(cfs_rq);/下面的 wakeup_preempt_entity 已經(jīng)講過，忘記的同學(xué)可以到上面看下/這里就是前面所說優(yōu)先照顧 next 和 last 進(jìn)程，只有當(dāng) pick_next_entity 選出來的進(jìn)程/的 vruntime 比 next 和 last 都小超過調(diào)度粒度時(shí)才輪到它運(yùn)行，否則就是 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é)點(diǎn)從樹上取下來。前面，占用 CPU 的進(jìn)程不在樹上 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 /這兩個(gè)函數(shù)是重點(diǎn)，選擇下一個(gè)要執(zhí)行的任務(wù)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í)鐘中斷主要函數(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; /這個(gè) 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 的時(shí)間用當(dāng)前時(shí)間減去exec_start/就得到了從上次計(jì)算 vruntime 到現(xiàn)在進(jìn)程又運(yùn)行的時(shí)間，用這個(gè)時(shí)間換算成 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 就是在這里計(jì)算的，它等于進(jìn)程從創(chuàng)建開始占用 CPU 的總時(shí)間/將進(jìn)程運(yùn)行總時(shí)間保存到 prev_.中，這樣進(jìn)程本次調(diào)度的運(yùn)行時(shí)間可以用下面公式計(jì)算：/進(jìn)程本次運(yùn)行已占用 CPU 時(shí)間 = sum_exec_runtime - prev_sum_exec_runtime/這里 sum_exec_runtime 會(huì)在每次時(shí)鐘 tick 中更新se-prev_sum_exec_runtime = se-sum_exec_runtime;33. 更新完 CFS 狀態(tài)之后回到 entity_tick 中，這時(shí)需要檢