自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

Linux Kernel調(diào)度器的過去，現(xiàn)在和未來

作者：0xE8551CCB
系統(tǒng) Linux
Linux Kernel Development 一書中，關(guān)于 Linux 的進(jìn)程調(diào)度器并沒有講解的很全面，只是提到了 CFS 調(diào)度器的基本思想和一些實(shí)現(xiàn)細(xì)節(jié);并沒有 Linux 早期的調(diào)度器介紹，以及最近這些年新增的在內(nèi)核源碼樹外維護(hù)的調(diào)度器思想。

[[345860]]

本文轉(zhuǎn)載自微信公眾號「人人都是極客」，作者0xE8551CCB。轉(zhuǎn)載本文請聯(lián)系人人都是極客公眾號。  

 

 

 

引言

Linux Kernel Development 一書中，關(guān)于 Linux 的進(jìn)程調(diào)度器并沒有講解的很全面，只是提到了 CFS 調(diào)度器的基本思想和一些實(shí)現(xiàn)細(xì)節(jié);并沒有 Linux 早期的調(diào)度器介紹，以及最近這些年新增的在內(nèi)核源碼樹外維護(hù)的調(diào)度器思想。所以在經(jīng)過一番搜尋后，看到了這篇論文 A complete guide to Linux process scheduling，對 Linux 的調(diào)度器歷史進(jìn)行了回顧，并且相對細(xì)致地講解了 CFS 調(diào)度器。整體來說，雖然比較啰嗦，但是對于想要知道更多細(xì)節(jié)的我來說非常適合，所以就有了翻譯它的沖動(dòng)。當(dāng)然，在學(xué)習(xí)過程也參考了其它論文。下面開啟學(xué)習(xí)之旅吧，如有任何問題，歡迎指正~

需要注意的是，在 Linux 中，線程和進(jìn)程都是由同一個(gè)結(jié)構(gòu)體(task_struct，即任務(wù)描述符)表示的，所以文中會(huì)交叉使用進(jìn)程、線程和任務(wù)等術(shù)語，可以將它們視作同義詞。當(dāng)然，也可以將線程(任務(wù))稱為最小執(zhí)行單元。但 Linux 的調(diào)度算法(如 CFS)可以應(yīng)用更加通用的調(diào)度單元(如線程、cgroup、用戶等)?？傊?，不要過度糾結(jié)這里的術(shù)語，重要的是了解每種調(diào)度算法的思想!

為什么需要調(diào)度

Linux 是一個(gè)多任務(wù)的操作系統(tǒng)，這就意味著它可以「同時(shí)」執(zhí)行多個(gè)任務(wù)。在單核處理器上，任意時(shí)刻只能有一個(gè)進(jìn)程可以執(zhí)行(并發(fā));而在多核處理器中，則允許任務(wù)并行執(zhí)行。然而，不管是何種硬件類型的機(jī)器上，可能同時(shí)還有很多在內(nèi)存中無法得到執(zhí)行的進(jìn)程，它們正在等待運(yùn)行，或者正在睡眠。負(fù)責(zé)將 CPU 時(shí)間分配給進(jìn)程的內(nèi)核組件就是「進(jìn)程調(diào)度器」。

調(diào)度器負(fù)責(zé)維護(hù)進(jìn)程調(diào)度順序，選擇下一個(gè)待執(zhí)行的任務(wù)。如同多數(shù)其它的現(xiàn)代操作系統(tǒng)，Linux 實(shí)現(xiàn)了搶占式多任務(wù)機(jī)制。也就是說，調(diào)度器可以隨時(shí)決定任意進(jìn)程停止運(yùn)行，而讓其它進(jìn)程獲得 CPU 資源。這種違背正在運(yùn)行的進(jìn)程意愿，停止其運(yùn)行的行為就是所謂的「搶占」。搶占通?？梢栽诙〞r(shí)器中斷時(shí)發(fā)生，當(dāng)中斷發(fā)生時(shí)，調(diào)度器會(huì)檢查是否需要切換任務(wù)，如果是，則會(huì)完成進(jìn)程上下文切換。每個(gè)進(jìn)程所獲得的運(yùn)行時(shí)間叫做進(jìn)程的時(shí)間片(timeslice)。

任務(wù)通?？梢詤^(qū)分為交互式(I/O 密集型)和非交互式(CPU 密集型)任務(wù)。交互式任務(wù)通常會(huì)重度依賴 I/O 操作(如 GUI 應(yīng)用)，并且通常用不完分配給它的時(shí)間片。而非交互式任務(wù)(如數(shù)學(xué)運(yùn)算)則需要使用更多的 CPU 資源。它們通常會(huì)用完自己的時(shí)間片之后被搶占，并不會(huì)被 I/O 請求頻繁阻塞。當(dāng)然，現(xiàn)實(shí)中的應(yīng)用程序可能同時(shí)包含上述兩種分類任務(wù)。例如，文本編輯器，多數(shù)情況下，它會(huì)等待用戶輸入，但是在執(zhí)行拼寫檢查時(shí)也會(huì)需要占用大量 CPU 資源。

操作系統(tǒng)的調(diào)度策略就需要均衡這兩種類型的任務(wù)，并且保證每個(gè)任務(wù)都能得到足夠的執(zhí)行資源，而不會(huì)對其它任務(wù)產(chǎn)生明顯的性能影響。 Linux 為了保證 CPU 利用率最大化，同時(shí)又能保證更快的響應(yīng)時(shí)間，傾向于為非交互式任務(wù)分配更大的時(shí)間片，但是以較低的頻率運(yùn)行它們;而針對 I/O 密集型任務(wù)，則會(huì)在較短周期內(nèi)頻繁地執(zhí)行。

調(diào)度有關(guān)的進(jìn)程描述符

進(jìn)程描述符(task_struct)中的很多字段會(huì)被調(diào)度機(jī)制直接使用。以下僅列出一些核心的部分，并在后文詳細(xì)討論。

  1. struct task_struct { 
  2.     int prio, static_prio, normal_prio; 
  3.     unsigned int rt_priority; 
  4.     const struct sched_class *sched_class; 
  5.     struct sched_entity se; 
  6.     struct sched_rt_entity rt; 
  7.     … 
  8.     unsigned int policy; 
  9.     cpumask_t cpus_allowed; 
  10.     … 
  11. }; 

關(guān)于這些字段的說明如下：

  • prio 表示進(jìn)程的優(yōu)先級。進(jìn)程運(yùn)行時(shí)間，搶占頻率都依賴于這些值。rt_priority 則用于實(shí)時(shí)(real-time)任務(wù);
  • sched_class 表示進(jìn)程位于哪個(gè)調(diào)度類;
  • sched_entity 的意義比較特殊。通常把一個(gè)線程(Linux 中的進(jìn)程、任務(wù)同義詞)叫作最小調(diào)度單元。但是 Linux 調(diào)度器不僅僅只能夠調(diào)度單個(gè)任務(wù)，而且還可以將一組進(jìn)程，甚至屬于某個(gè)用戶的所有進(jìn)程作為整體進(jìn)行調(diào)度。這就允許我們實(shí)現(xiàn)組調(diào)度，從而將 CPU 時(shí)間先分配到進(jìn)程組，再在組內(nèi)分配到單個(gè)線程。當(dāng)引入這項(xiàng)功能后，可以大幅度提升桌面系統(tǒng)的交互性。比如，可以將編譯任務(wù)聚集成一個(gè)組，然后進(jìn)行調(diào)度，從而不會(huì)對交互性產(chǎn)生明顯的影響。這里再次強(qiáng)調(diào)下，**Linux 調(diào)度器不僅僅能直接調(diào)度進(jìn)程，也能對調(diào)度單元(schedulable entities)進(jìn)行調(diào)度。這樣的調(diào)度單元正是用 struct sched_entity 來表示的。需要說明的是，它并非一個(gè)指針，而是直接嵌套在進(jìn)程描述符中的。當(dāng)然，后面的談?wù)搶⒕劢乖趩芜M(jìn)程調(diào)度這種簡單場景。由于調(diào)度器是面向調(diào)度單元設(shè)計(jì)的，所以它會(huì)將單個(gè)進(jìn)程也視為調(diào)度單元，因此會(huì)使用 sched_entity 結(jié)構(gòu)體操作它們。sched_rt_entity 則是實(shí)時(shí)調(diào)度時(shí)使用的。
  • policy 表明任務(wù)的調(diào)度策略：通常意味著針對某些特定的進(jìn)程組(如需要更長時(shí)間片，更高優(yōu)先級等)應(yīng)用特殊的調(diào)度決策。Linux 內(nèi)核目前支持的調(diào)度策略如下：
    • SCHED_NORMAL：普通任務(wù)使用的調(diào)度策略;
    • SCHED_BATCH：不像普通任務(wù)那樣被頻繁搶占，可允許任務(wù)運(yùn)行盡可能長的時(shí)間，從而更好地利用緩存，但是代價(jià)自然是損失交互性能。這種非常適合批量任務(wù)調(diào)度(批量的 CPU 密集型任務(wù));
    • SCHED_IDLE：它要比 nice 19 的任務(wù)優(yōu)先級還要低，但它并非真的空閑任務(wù);
    • SCHED_FIFO 和 SCHED_RR 是軟實(shí)時(shí)進(jìn)程調(diào)度策略。它們是由 POSIX 標(biāo)準(zhǔn)定義的，由 里面定義的實(shí)時(shí)調(diào)度器負(fù)責(zé)調(diào)度。RR 實(shí)現(xiàn)的是帶有固定時(shí)間片的輪轉(zhuǎn)調(diào)度方式;SCHED_FIFO 則使用的是先進(jìn)先出的隊(duì)列機(jī)制。

cpus_allowed：用來表示任務(wù)的 CPU 親和性。用戶空間可以通過 sched_setaffinity 系統(tǒng)調(diào)用來設(shè)置。

優(yōu)先級 Priority

進(jìn)程優(yōu)先級：

普通任務(wù)優(yōu)先級：

所有的類 Unix 操作系統(tǒng)都實(shí)現(xiàn)了優(yōu)先級調(diào)度機(jī)制。它的核心思想就是給任務(wù)設(shè)定一個(gè)值，然后通過該值決定任務(wù)的重要程度。如果任務(wù)的優(yōu)先級一致，則一次重復(fù)運(yùn)行它們。在 Linux 中，每一個(gè)普通任務(wù)都被賦予了一個(gè) nice 值，它的范圍是 -20 到 +19，任務(wù)默認(rèn) nice 值是 0。

 

nice 值越高，任務(wù)優(yōu)先級越低(it's nice to others)。Linux 中可以使用 nice(int increment) 系統(tǒng)調(diào)用來修改當(dāng)前進(jìn)程的優(yōu)先級。該系統(tǒng)調(diào)用的實(shí)現(xiàn)位于 中。默認(rèn)情況下，用戶只能為該用戶啟動(dòng)的進(jìn)程增加 nice 值(即降低優(yōu)先級)。如果需要增加優(yōu)先級(減少 nice 值)，或者修改其它用戶進(jìn)程優(yōu)先級，則必須以 root 身份操作。

實(shí)時(shí)任務(wù)優(yōu)先級：

在 Linux 中，除了普通任務(wù)外，還有一類任務(wù)屬于實(shí)時(shí)任務(wù)。實(shí)時(shí)任務(wù)是確保它們能夠在一定時(shí)間范圍內(nèi)執(zhí)行的任務(wù)，有兩類實(shí)時(shí)任務(wù)，列舉如下：

  • 硬實(shí)時(shí)任務(wù)：會(huì)有嚴(yán)格的時(shí)間限制，任務(wù)必須在時(shí)限內(nèi)完成。比如直升機(jī)的飛控系統(tǒng)，就需要及時(shí)響應(yīng)駕駛員的操控，并做出預(yù)期的動(dòng)作。然而，Linux 本身并不支持硬實(shí)時(shí)任務(wù)，但是有一些基于它修改的版本，如 RTLinux(它們通常被稱為 RTOS)則是支持硬實(shí)時(shí)調(diào)度的。
  • 軟實(shí)時(shí)任務(wù)：軟實(shí)時(shí)任務(wù)其實(shí)也會(huì)有時(shí)間限制，但不是那么嚴(yán)格。也就是說，任務(wù)晚一點(diǎn)運(yùn)行任務(wù)，并不會(huì)造成不可挽回的災(zāi)難性事故。實(shí)踐中，軟實(shí)時(shí)任務(wù)會(huì)提供一定的時(shí)間限制保障，但是不要過度依賴這種特性。例如，VOIP 軟件會(huì)使用軟實(shí)時(shí)保障的協(xié)議傳來送音視頻信號，但是即便因?yàn)椴僮飨到y(tǒng)負(fù)載過高，而產(chǎn)生一點(diǎn)延遲，也不會(huì)造成很大影響。無論如何，軟實(shí)時(shí)任務(wù)總會(huì)比普通任務(wù)的優(yōu)先級更高。

Linux 中實(shí)時(shí)任務(wù)的優(yōu)先級范圍是 0~99，但是有趣的是，它和 nice 值的作用剛好相反，這里的優(yōu)先級值越大，就意味著優(yōu)先級越高。

 

類似其它的 Unix 系統(tǒng)，Linux 也是基于 POSIX 1b 標(biāo)準(zhǔn)定義的 「Real-time Extensions」實(shí)現(xiàn)實(shí)時(shí)優(yōu)先級。可以通過如下的命令查看系統(tǒng)中的實(shí)時(shí)任務(wù)：

  1. $ ps -eo pid, rtprio, cmd 

也可通過 chrt -p pid 查看單個(gè)進(jìn)程的詳情。Linux 中可以通過 chrt -p prio pid 更改實(shí)時(shí)任務(wù)優(yōu)先級。這里需要注意的是，如果操作的是一個(gè)系統(tǒng)進(jìn)程(通常并不會(huì)將普通用戶的進(jìn)程設(shè)置為實(shí)時(shí)的)，則必須有 root 權(quán)限才可以修改實(shí)時(shí)優(yōu)先級。

內(nèi)核視角下的進(jìn)程優(yōu)先級：

實(shí)時(shí)上，內(nèi)核看到的任務(wù)優(yōu)先級和用戶看到的并不相同，在計(jì)算和管理優(yōu)先級時(shí)也需要考慮很多方面。Linux 內(nèi)核中使用 0~139 表示任務(wù)的優(yōu)先級，并且，值越小，優(yōu)先級越高(注意和用戶空間的區(qū)別)。其中 0~99 保留給實(shí)時(shí)進(jìn)程，100~139(映射成 nice 值就是 -20~19)保留給普通進(jìn)程。

 

我們可以在 頭文件中看到內(nèi)核表示進(jìn)程優(yōu)先級的單位(scale)和宏定義(macros)，它們用來將用戶空間優(yōu)先級映射到到內(nèi)核空間。

  1. #define MAX_NICE 19 
  2. #define MIN_NICE -20 
  3. #define NICE_WIDTH (MAX_NICE - MIN_NICE + 1) 
  4. … 
  5. #define MAX_USER_RT_PRIO 100 
  6. #define MAX_RT_PRIO MAX_USER_RT_PRIO 
  7. #define MAX_PRIO (MAX_RT_PRIO + NICE_WIDTH) 
  8. #define DEFAULT_PRIO (MAX_RT_PRIO + NICE_WIDTH / 2) 
  9. /* 
  10. * Convert user-nice values [ -20 ... 0 ... 19 ] 
  11. * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ], 
  12. * and back. 
  13. */ 
  14. #define NICE_TO_PRIO(nice) ((nice) + DEFAULT_PRIO) 
  15. #define PRIO_TO_NICE(prio) ((prio) - DEFAULT_PRIO) 
  16. /* 
  17. * 'User priority' is the nice value converted to something we 
  18. * can work with better when scaling various scheduler parameters, 
  19. * it's a [ 0 ... 39 ] range. 
  20. */ 
  21. #define USER_PRIO(p) ((p)-MAX_RT_PRIO) 
  22. #define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio) 
  23. #define MAX_USER_PRIO (USER_PRIO(MAX_PRIO)) 

優(yōu)先級計(jì)算：

在 task_struct 中有幾個(gè)字段用來表示進(jìn)程優(yōu)先級：

  1. int prio, static_prio, normal_prio; 
  2. unsigned int rt_priority; 

static_prio 是由用戶或系統(tǒng)設(shè)定的「靜態(tài)」優(yōu)先級映射成內(nèi)核表示的優(yōu)先級：

  1. p->static_prio = NICE_TO_PRIO(nice_value); 

normal_prio 存放的是基于 static_prio 和進(jìn)程調(diào)度策略(實(shí)時(shí)或普通)決定的優(yōu)先級，相同的靜態(tài)優(yōu)先級，在不同的調(diào)度策略下，得到的正常優(yōu)先級是不同的。子進(jìn)程在 fork 時(shí)，會(huì)繼承父進(jìn)程的 normal_prio。

prio 則是「動(dòng)態(tài)優(yōu)先級」，在某些場景下優(yōu)先級會(huì)發(fā)生變動(dòng)。一種場景就是，系統(tǒng)可以通過給某個(gè)任務(wù)優(yōu)先級提升一段時(shí)間，從而搶占其它高優(yōu)先級任務(wù)，一旦 static_prio 確定，prio 字段就可以通過下面的方式計(jì)算：

  1. p->prio = effective_prio(p); 
  2. // kernel/sched/core.c 中定義了計(jì)算方法 
  3. static int effective_prio(struct task_struct *p) 
  4. { 
  5.     p->normal_prio = normal_prio(p); 
  6.     /* 
  7.     * If we are RT tasks or we were boosted to RT priority, 
  8.     * keep the priority unchanged. Otherwise, update priority 
  9.     * to the normal priority: 
  10.     */ 
  11.     if (!rt_prio(p->prio)) 
  12.         return p->normal_prio; 
  13.     return p->prio; 
  14. } 
  15.  
  16. static inline int normal_prio(struct task_struct *p) 
  17. { 
  18.     int prio; 
  19.     if (task_has_dl_policy(p)) 
  20.         prio = MAX_DL_PRIO-1; 
  21.     else if (task_has_rt_policy(p)) 
  22.         prio = MAX_RT_PRIO-1 - p->rt_priority; 
  23.     else  
  24.         prio = __normal_prio(p); 
  25.     return prio; 
  26. } 
  27.  
  28. static inline int __normal_prio(struct task_struct *p) 
  29. { 
  30.     return p->static_prio; 
  31. } 

負(fù)載權(quán)重(Load Weights)：

優(yōu)先級會(huì)讓一些任務(wù)比別的任務(wù)更重要，因此也會(huì)獲得更多的 CPU 使用時(shí)間。nice 值和時(shí)間片的比例關(guān)系是通過負(fù)載權(quán)重(Load Weights)進(jìn)行維護(hù)的，我們可以在 task_struct->se.load 中看到進(jìn)程的權(quán)重，定義如下：

  1. struct sched_entity { 
  2.     struct load_weight load; /* for load-balancing */ 
  3.     … 
  4. } 
  5. struct load_weight { 
  6.     unsigned long weight; 
  7.     u32 inv_weight; 
  8. }; 

為了讓 nice 值的變化反映到 CPU 時(shí)間變化片上更加合理，Linux 內(nèi)核中定義了一個(gè)數(shù)組，用于映射 nice 值到權(quán)重：

  1. static const int prio_to_weight[40] = { 
  2.     /* -20 */ 88761, 71755, 56483, 46273, 36291, 
  3.     /* -15 */ 29154, 23254, 18705, 14949, 11916, 
  4.     /* -10 */ 9548, 7620, 6100, 4904, 3906, 
  5.     /* -5 */ 3121, 2501, 1991, 1586, 1277, 
  6.     /* 0 */ 1024, 820, 655, 526, 423, 
  7.     /* 5 */ 335, 272, 215, 172, 137, 
  8.     /* 10 */ 110, 87, 70, 56, 45, 
  9.     /* 15 */ 36, 29, 23, 18, 15, 
  10. }; 

來看看如何使用上面的映射表，假設(shè)有兩個(gè)優(yōu)先級都是 0 的任務(wù)，每個(gè)都能獲得 50% 的 CPU 時(shí)間(1024 / (1024 + 1024) = 0.5)。如果突然給其中的一個(gè)任務(wù)優(yōu)先級提升了 1 (nice 值 -1)。此時(shí)，一個(gè)任務(wù)應(yīng)該會(huì)獲得額外 10% 左右的 CPU 時(shí)間，而另一個(gè)則會(huì)減少 10% CPU 時(shí)間。來看看計(jì)算結(jié)果：1277 / (1024 + 1277) ≈ 0.55，1024 / (1024 + 1277) ≈ 0.45，二者差距剛好在 10% 左右，符合預(yù)期。完整的計(jì)算函數(shù)定義在 中：

  1. static void set_load_weight(struct task_struct *p) 
  2. { 
  3.     int prio = p->static_prio - MAX_RT_PRIO; 
  4.     struct load_weight *load = &p->se.load; 
  5.     /* 
  6.     * SCHED_IDLE tasks get minimal weight: 
  7.     */ 
  8.     if (p->policy == SCHED_IDLE) { 
  9.         load->weight = scale_load(WEIGHT_IDLEPRIO); 
  10.         load->inv_weight = WMULT_IDLEPRIO; 
  11.         return; 
  12.     } 
  13.     load->weight = scale_load(prio_to_weight[prio]); 
  14.     load->inv_weight = prio_to_wmult[prio]; 
  15. } 

調(diào)度類 Scheduling Classes

雖說 Linux 內(nèi)核使用的 C 語言并非所謂的 OOP 語言(沒有類似 C++/Java 中的 class 概念)，但是我們可以在內(nèi)核代碼中看到一些使用 C 語言結(jié)構(gòu)體 + 函數(shù)指針(Hooks)的方式來模擬面向?qū)ο蟮姆绞?，抽象行為和?shù)據(jù)。調(diào)度類也是這樣實(shí)現(xiàn)的(此外，還有 inode_operations, super_block_operations 等)，它的定義如下(位于 )：

  1. // 為了簡單起見，隱藏了部分代碼（如 SMP 相關(guān)的） 
  2. struct sched_class { 
  3.     // 多個(gè) sched_class 是鏈接在一起的 
  4.     const struct sched_class *next; 
  5.     // 該 hook 會(huì)在任務(wù)進(jìn)入可運(yùn)行狀態(tài)時(shí)調(diào)用。它會(huì)將調(diào)度單元（如一個(gè)任務(wù)）放到 
  6.     // 隊(duì)列中，同時(shí)遞增 `nr_running` 變量（該變量表示運(yùn)行隊(duì)列中可運(yùn)行的任務(wù)數(shù)） 
  7.     void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags); 
  8.     // 該 hook 會(huì)在任務(wù)不可運(yùn)行時(shí)調(diào)用。它會(huì)將任務(wù)移出隊(duì)列，同時(shí)遞減 `nr_running` 
  9.     void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags); 
  10.     // 該 hook 可以在任務(wù)需要主動(dòng)放棄 CPU 時(shí)調(diào)用，但是需要注意的是，它不會(huì)改變 
  11.     // 任務(wù)的可運(yùn)行狀態(tài)，也就是說依然會(huì)在隊(duì)列中等待下次調(diào)度。類似于先 dequeue_task， 
  12.     // 再 enqueue_task 
  13.     void (*yield_task) (struct rq *rq); 
  14.     // 該 hook 會(huì)在任務(wù)進(jìn)入可運(yùn)行狀態(tài)時(shí)調(diào)用并檢查是否需要搶占當(dāng)前任務(wù) 
  15.     void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags); 
  16.     // 該 hook 用來選擇最適合運(yùn)行的下一個(gè)任務(wù) 
  17.     struct task_struct * (*pick_next_task) (struct rq *rq, struct task_struct *prev); 
  18.     // 該 hook 會(huì)在任務(wù)修改自身的調(diào)度類或者任務(wù)組時(shí)調(diào)用 
  19.     void (*set_curr_task) (struct rq *rq); 
  20.     // 通常是在時(shí)鐘中斷時(shí)調(diào)用，可能會(huì)導(dǎo)致任務(wù)切換 
  21.     void (*task_tick) (struct rq *rq, struct task_struct *p, int queued); 
  22.     // 當(dāng)任務(wù)被 fork 時(shí)通知調(diào)度器 
  23.     void (*task_fork) (struct task_struct *p); 
  24.     // 當(dāng)任務(wù)掛掉時(shí)通知調(diào)度器 
  25.     void (*task_dead) (struct task_struct *p); 
  26. }; 

關(guān)于調(diào)度策略的具體細(xì)節(jié)的實(shí)現(xiàn)有如下幾個(gè)模塊：

  • core.c 包含調(diào)度器的核心部分;
  • fair.c 實(shí)現(xiàn)了 CFS(Comple Faire Scheduler，完全公平任務(wù)調(diào)度器) 調(diào)度器，應(yīng)用于普通任務(wù);
  • rt.c 實(shí)現(xiàn)了實(shí)時(shí)調(diào)度，應(yīng)用于實(shí)時(shí)任務(wù);
  • idle_task.c 當(dāng)沒有其它可運(yùn)行的任務(wù)時(shí)，會(huì)運(yùn)行空閑任務(wù)。

內(nèi)核是基于任務(wù)的調(diào)度策略(SCHED_*)來決定使用何種調(diào)度類實(shí)現(xiàn)，并會(huì)調(diào)用相應(yīng)的方法。SCHED_NORMAL, SCHED_BATCH 和 SCHED_IDLE 進(jìn)程會(huì)映射到 fair_sched_class (由 CFS 實(shí)現(xiàn));SCHED_RR 和 SCHED_FIFO 則映射的 rt_sched_class (實(shí)時(shí)調(diào)度器)。

運(yùn)行隊(duì)列 runqueue

所有可運(yùn)行的任務(wù)是放在運(yùn)行隊(duì)列中的，并且等待 CPU 運(yùn)行。每個(gè) CPU 核心都有自己的運(yùn)行隊(duì)列，每個(gè)任務(wù)任意時(shí)刻只能處于其中一個(gè)隊(duì)列中。在多處理器機(jī)器中，會(huì)有負(fù)載均衡策略，任務(wù)就會(huì)轉(zhuǎn)移到其它 CPU 上運(yùn)行的可能。

運(yùn)行隊(duì)列數(shù)據(jù)結(jié)構(gòu)定義如下(位于 ):

  1. // 為了簡單起見，隱藏了部分代碼（SMP 相關(guān)） 
  2. // 這個(gè)是每個(gè) CPU 都會(huì)有的一個(gè)任務(wù)運(yùn)行隊(duì)列 
  3. struct rq 
  4. { 
  5.     // 表示當(dāng)前隊(duì)列中總共有多少個(gè)可運(yùn)行的任務(wù)（包含所有的 sched class） 
  6.     unsigned int nr_running; 
  7. #define CPU_LOAD_IDX_MAX 5 
  8.     unsigned long cpu_load[CPU_LOAD_IDX_MAX]; 
  9.     // 運(yùn)行隊(duì)列負(fù)載記錄 
  10.     struct load_weight load; 
  11.     // 嵌套的 CFS 調(diào)度器運(yùn)行隊(duì)列 
  12.     struct cfs_rq cfs; 
  13.     // 嵌套的實(shí)時(shí)任務(wù)調(diào)度器運(yùn)行隊(duì)列 
  14.     struct rt_rq rt; 
  15.     // curr 指向當(dāng)前正在運(yùn)行的進(jìn)程描述符 
  16.     // idle 則指向空閑進(jìn)程描述符（當(dāng)沒有其它可運(yùn)行任務(wù)時(shí)，該任務(wù)才會(huì)啟動(dòng)） 
  17.     struct task_struct *curr, *idle; 
  18.     u64 clock; 
  19.     int cpu; 
  20. } 

何時(shí)運(yùn)行調(diào)度器?

實(shí)時(shí)上，調(diào)度函數(shù) schedule() 會(huì)在很多場景下被調(diào)用。有的是直接調(diào)用，有的則是隱式調(diào)用(通過設(shè)置 TIF_NEED_RESCHED 來提示操作系統(tǒng)盡快運(yùn)行調(diào)度函數(shù))。以下三個(gè)調(diào)度時(shí)機(jī)值得關(guān)注下：時(shí)鐘中斷發(fā)生時(shí)，會(huì)調(diào)用 scheduler_tick() 函數(shù)，該函數(shù)會(huì)更新一些和調(diào)度有關(guān)的數(shù)據(jù)統(tǒng)計(jì)，并觸發(fā)調(diào)度類的周期調(diào)度方法，從而間接地進(jìn)行調(diào)度。以 2.6.39 源碼為例，可能的調(diào)用鏈路如下：

  1. scheduler_tick 
  2. └── task_tick 
  3.     └── entity_tick 
  4.         └── check_preempt_tick 
  5.             └── resched_task 
  6.                 └── set_tsk_need_resched 
  • 當(dāng)前正在運(yùn)行的任務(wù)進(jìn)入睡眠狀態(tài)。在這種情況下，任務(wù)會(huì)主動(dòng)釋放 CPU。通常情況下，該任務(wù)會(huì)因?yàn)榈却付ǖ氖录撸梢詫⒆约禾砑拥降却?duì)列，并啟動(dòng)循環(huán)檢查期望的條件是否滿足。在進(jìn)入睡眠前，任務(wù)可以將自己的狀態(tài)設(shè)置為 TASK_INTERRUPTABLE(除了任務(wù)要等待的事件可喚醒外，也可以被信號喚醒)或者 TASK_UNINTERRUPTABLE(自然是不會(huì)理會(huì)信號咯)，然后調(diào)用 schedule() 選擇下一個(gè)任務(wù)運(yùn)行。

Linux 調(diào)度器

早期版本:

Linux 0.0.1 版本就已經(jīng)有了一個(gè)簡單的調(diào)度器，當(dāng)然并非適合擁有特別多處理器的系統(tǒng)。該調(diào)度器只維護(hù)了一個(gè)全局的進(jìn)程隊(duì)列，每次都需要遍歷該隊(duì)列來尋找新的進(jìn)程執(zhí)行，而且對任務(wù)數(shù)量還有嚴(yán)格限制(NR_TASKS 在最初的版本中只有 32)。下面來看看這個(gè)調(diào)度器是如何實(shí)現(xiàn)的吧：

  1. // 'schedule()' is the scheduler function.  
  2. // This is GOOD CODE! There probably won't be any reason to change  
  3. // this, as it should work well in all circumstances (ie gives  
  4. // IO-bound processes good response etc)... 
  5. void schedule(void) 
  6. { 
  7.     int i, next, c; 
  8.     struct task_struct **p; 
  9.     // 遍歷所有任務(wù)，如果有信號，則需要喚醒 `TASK_INTERRUPTABLE` 的任務(wù) 
  10.     for (p = &LAST_TASK; p > &FIRST_TASK; --p) 
  11.         if (*p) { 
  12.             if ((*p)->alarm && (*p)->alarm < jiffies) { 
  13.                 (*p)->signal |= (1 << (SIGALRM - 1)); 
  14.                 (*p)->alarm = 0; 
  15.             } 
  16.             if ((*p)->signal && (*p)->state == TASK_INTERRUPTIBLE) 
  17.                 (*p)->state = TASK_RUNNING; 
  18.         } 
  19.     while (1) 
  20.     { 
  21.         c = -1; 
  22.         next = 0; 
  23.         i = NR_TASKS; 
  24.         p = &task[NR_TASKS]; 
  25.         // 遍歷所有任務(wù)，找到時(shí)間片最長的那個(gè) 
  26.         while (--i) { 
  27.             if (!*--p) 
  28.                 continue; 
  29.             if ((*p)->state == TASK_RUNNING && (*p)->counter > c) 
  30.                 c = (*p)->counter, next = i; 
  31.         } 
  32.         if (c) 
  33.             break; 
  34.         // 遍歷任務(wù)，重新設(shè)值時(shí)間片 
  35.         for (p = &LAST_TASK; p > &FIRST_TASK; --p) 
  36.             if (*p) 
  37.                 (*p)->counter = ((*p)->counter >> 1) + (*p)->priority; 
  38.     } 
  39.     // 切換到下一個(gè)需要執(zhí)行的任務(wù) 
  40.     switch_to(next); 
  41. } 

O(n)：

2.4 版本的 Linux 內(nèi)核使用的調(diào)度算法非常簡單和直接，由于每次在尋找下一個(gè)任務(wù)時(shí)需要遍歷系統(tǒng)中所有的任務(wù)(鏈表)，因此被稱為 O(n) 調(diào)度器(時(shí)間復(fù)雜度)。

當(dāng)然，該調(diào)度器要比 0.01 版本內(nèi)核中的調(diào)度算法稍微復(fù)雜點(diǎn)，它引入了 epoch 概念。也就是將時(shí)間分成紀(jì)元(epochs)，也就是每個(gè)進(jìn)程的生命周期。理論上來說，每個(gè)紀(jì)元結(jié)束，每個(gè)進(jìn)程都應(yīng)該運(yùn)行過一次了，而且通常用光了它當(dāng)前的時(shí)間片。但實(shí)際上，有些任務(wù)并沒有完全用完時(shí)間片，那么它剩余時(shí)間片的一半將會(huì)和新的時(shí)間片相加，從而在下一個(gè)紀(jì)元運(yùn)行更長的時(shí)間。

我們來看下 schedule() 算法的核心源碼：

  1. // schedule() 算法會(huì)遍歷所有的任務(wù)（O(N)），并且計(jì)算出每個(gè)任務(wù)的 
  2. // goodness 值，且挑選出「最好」的任務(wù)來運(yùn)行。 
  3. // 以下是部分核心源碼，主要是了解下它的思路。 
  4. asmlinkage void schedule(void) 
  5. { 
  6.     // 任務(wù)（進(jìn)程）描述符： 
  7.     // 1. prev: 當(dāng)前正在運(yùn)行的任務(wù) 
  8.     // 2. next: 下一個(gè)將運(yùn)行的任務(wù) 
  9.     // 3. p: 當(dāng)前正在遍歷的任務(wù) 
  10.     struct task_struct *prev, *next, *p; 
  11.     int this_cpu, c; // c 表示權(quán)重值 
  12. repeat_schedule: 
  13.     // 默認(rèn)選中的任務(wù) 
  14.     next = idle_task(this_cpu); 
  15.     c = -1000; 
  16.     list_for_each(tmp, &runqueue_head) { 
  17.         p = list_entry(tmp, struct task_struct, run_list); 
  18.         if (can_schedule(p, this_cpu)) { 
  19.             int weight = goodness(p, this_cpu, prev->active_mm); 
  20.             if (weight > c) 
  21.                 c = weight, next = p; 
  22.         } 
  23.     } 
  24. } 

源碼中的 goodness() 函數(shù)會(huì)計(jì)算出一個(gè)權(quán)重值，它的算法基本思想就是基于進(jìn)程所剩余的時(shí)鐘節(jié)拍數(shù)(時(shí)間片)，再加上基于進(jìn)程優(yōu)先級的權(quán)重值。返回值如下：

  • -1000 表示不要選擇該進(jìn)程運(yùn)行
  • 0 表示時(shí)間片用完了，需要重新計(jì)算 counters(可能會(huì)被選中運(yùn)行)
  • 正整數(shù)：表示 goodness 值(越大越好)
  • +1000 表示實(shí)時(shí)進(jìn)程，接下來就要選擇它運(yùn)行

最后，針對 O(n) 調(diào)度器做下總結(jié)：算法實(shí)現(xiàn)非常簡單，但是不高效(任務(wù)越多，遍歷耗費(fèi)時(shí)間越久)

沒有很好的擴(kuò)展性，多核處理器怎么辦?

對于實(shí)時(shí)任務(wù)調(diào)度支持較弱(無論如何作為優(yōu)先級高的實(shí)時(shí)任務(wù)都需要在遍歷完列表后才可以知道)

O(1)：

Ingo Molnár 大佬在 2.6 版本的內(nèi)核中加入了全新的調(diào)度算法，它能夠在常數(shù)時(shí)間內(nèi)調(diào)度任務(wù)，因此被稱為 O(1) 調(diào)度器。我們來看看它引入的一些新特性：

  • 全局優(yōu)先級單位，范圍是 0~139，數(shù)值越低，優(yōu)先級越高
  • 將任務(wù)拆分成實(shí)時(shí)(099)和正常(100139)兩部分。更高優(yōu)先級任務(wù)獲得更多時(shí)間片
  • 即刻搶占(early preemption)。當(dāng)任務(wù)狀態(tài)變成 TASK_RUNNING 時(shí)，內(nèi)核會(huì)檢查其優(yōu)先級是否比當(dāng)前運(yùn)行的任務(wù)優(yōu)先級更高，如果是的話，則搶占當(dāng)前正在運(yùn)行的任務(wù)，切換到該任務(wù)
  • 實(shí)時(shí)任務(wù)使用靜態(tài)優(yōu)先級
  • 普通任務(wù)使用使用動(dòng)態(tài)優(yōu)先級。任務(wù)優(yōu)先級會(huì)在其使用完自己的時(shí)間片后重新計(jì)算，內(nèi)核會(huì)考慮它過去的行為，決定它的交互性等級。交互型任務(wù)更容易得到調(diào)度

O(n) 的調(diào)度器會(huì)在每個(gè)紀(jì)元結(jié)束后(所有任務(wù)的時(shí)間片都使用過)，才會(huì)重新計(jì)算任務(wù)優(yōu)先級。而 O(1) 則是在每個(gè)任務(wù)時(shí)間片配額用完后就重新計(jì)算優(yōu)先級。O(1) 調(diào)度器為每個(gè) CPU 維護(hù)了兩個(gè)隊(duì)列，即 active 和 expired。active 隊(duì)列存放的是時(shí)間片尚未用完的任務(wù)，而 expired 則是時(shí)間片已經(jīng)耗盡的任務(wù)。當(dāng)一個(gè)任務(wù)的時(shí)間片用完后，就會(huì)被轉(zhuǎn)到 expired 隊(duì)列，而且會(huì)重新計(jì)算它的優(yōu)先級。當(dāng) active 隊(duì)列任務(wù)全部轉(zhuǎn)移到 expired 隊(duì)列后，會(huì)交換二者(讓 active 指向 expired 隊(duì)列，expired 指向 active 隊(duì)列)。可以看到，優(yōu)先級的計(jì)算，隊(duì)列切換都和任務(wù)數(shù)量多寡無關(guān)，能夠在 O(1) 時(shí)間復(fù)雜度下完成。

在先前介紹的調(diào)度算法中，如果想要取一個(gè)優(yōu)先級最高的任務(wù)，還需要遍歷整個(gè)任務(wù)鏈表才可以。而 O(1) 調(diào)度器則很特別，它為每種優(yōu)先級提供了一個(gè)任務(wù)鏈表。所有的可運(yùn)行任務(wù)會(huì)被分散在不同優(yōu)先級隊(duì)?wèi)?yīng)的鏈表中。

接下來看看全新的 runqueue 是怎么定義的吧：

  1. struct runqueue { 
  2.     unsigned long nr_running; /* 可運(yùn)行的任務(wù)總數(shù)（某個(gè) CPU） */ 
  3.     struct prio_array *active; /* 指向 active 的隊(duì)列的指針 */ 
  4.     struct prio_array *expired; /* 指向 expired 的隊(duì)列的指針 */ 
  5.     struct prio_array arrays[2]; /* 實(shí)際存放不同優(yōu)先級對應(yīng)的任務(wù)鏈表 */ 
  6. } 

通過下面的圖可以直觀感受下任務(wù)隊(duì)列：

 

接下來看看 prio_array 是怎么定義的：

  1. struct prio_array { 
  2.     int nr_active; /* 列表中的任務(wù)總數(shù) */ 
  3.     unsigned long bitmap[BITMAP_SIZE]; /* 位圖表示對應(yīng)優(yōu)先級鏈表是否有任務(wù)存在 */ 
  4.     struct list_head queue[MAX_PRIO]; /* 任務(wù)隊(duì)列（每種優(yōu)先級對應(yīng)一個(gè)雙向鏈表） */ 
  5. }; 

可以看到，在 prio_array 中存在一個(gè)位圖，它是用來標(biāo)記每個(gè) priority 對應(yīng)的任務(wù)鏈表是否存在任務(wù)的。接下來看看為何 O(1) 調(diào)度器可以在常數(shù)時(shí)間找到需要運(yùn)行的任務(wù)：

  • 常數(shù)時(shí)間確定優(yōu)先級：首先會(huì)在位圖中查找到第一個(gè)設(shè)置為 1 的位(總共有 140 bits，從第一個(gè) bit 開始搜索，這樣可以保證高優(yōu)先級的任務(wù)先得到機(jī)會(huì)運(yùn)行)，如果找到了就可以確定哪個(gè)優(yōu)先級有任務(wù)，假設(shè)找到后的值為 priority;
  • 常數(shù)時(shí)間獲得下一個(gè)任務(wù)：在 queue[priority] 對應(yīng)的任務(wù)鏈表中提取第一個(gè)任務(wù)來執(zhí)行(多個(gè)任務(wù)會(huì)輪轉(zhuǎn)執(zhí)行)。

 

好了，是時(shí)候總結(jié)下 O(1) 調(diào)度器的優(yōu)缺點(diǎn)了：設(shè)計(jì)上要比 O(n) 調(diào)度器更加復(fù)雜精妙;

相對來說擴(kuò)展性更好，性能更優(yōu)，在任務(wù)切換上的開銷更小;

用來標(biāo)記任務(wù)是否為交互類型的算法還是過于復(fù)雜，且容易出錯(cuò)。

CFS：單核調(diào)度

:CFS 的全稱是 Complete Fair Scheduler，也就是完全公平調(diào)度器。它實(shí)現(xiàn)了一個(gè)基于權(quán)重的公平隊(duì)列算法，從而將 CPU 時(shí)間分配給多個(gè)任務(wù)(每個(gè)任務(wù)的權(quán)重和它的 nice 值有關(guān)，nice 值越低，權(quán)重值越高)。每個(gè)任務(wù)都有一個(gè)關(guān)聯(lián)的虛擬運(yùn)行時(shí)間 vruntime，它表示一個(gè)任務(wù)所使用的 CPU 時(shí)間除以其優(yōu)先級得到的值。相同優(yōu)先級和相同 vruntime 的兩個(gè)任務(wù)實(shí)際運(yùn)行的時(shí)間也是相同的，這就意味著 CPU 資源是由它們均分了。為了保證所有任務(wù)能夠公平推進(jìn)，每當(dāng)需要搶占當(dāng)前任務(wù)時(shí)，CFS 總會(huì)挑選出 vruntime 最小的那個(gè)任務(wù)運(yùn)行。

內(nèi)核版本在 2.6.38 之前，每個(gè)線程(任務(wù))會(huì)被當(dāng)成獨(dú)立的調(diào)度單元，并且和系統(tǒng)中其它線程共享資源，這就意味著一個(gè)多線程的應(yīng)用會(huì)比單線程的應(yīng)用獲得更多的資源。之后，CFS 不斷改進(jìn)，目前已經(jīng)支持將一個(gè)應(yīng)用中的線程打包到 cgroup 結(jié)構(gòu)中，cgroup 的 vruntime 是其中所有線程的 vuntime 之和。然后 CFS 就可以將它的算法應(yīng)用于cgroup 之間，從而保證公平性。當(dāng)某個(gè) cgroup 被選中后，其中擁有最小 vruntime 的線程會(huì)被執(zhí)行，從而保證 cgroup 中的線程之間的公平性。cgroup 還可以嵌套，例如 systemd 會(huì)自動(dòng)配置 cgroup 來保證不同用戶之間的公平性，然后在用戶運(yùn)行的多個(gè)應(yīng)用之間維持公平性。

CFS 通過在一定時(shí)間內(nèi)運(yùn)行調(diào)度所有的線程來避免饑餓問題。當(dāng)運(yùn)行的 線程數(shù)在 8 個(gè)及以下時(shí)，默認(rèn)的時(shí)間周期是 48ms;而當(dāng)多于 8 個(gè)線程時(shí)，時(shí)間周期就會(huì)隨著線程數(shù)量而增加(6ms * 線程數(shù)，之所以選擇 6ms，是為了避免頻繁搶占，導(dǎo)致上下文切換頻繁切換的開銷)。由于 CFS 總是會(huì)挑選 vruntime 最小的線程執(zhí)行，它就需要避免某個(gè)線程的 vruntime 太小，以至于其它線程需要等待很久才能得到調(diào)度(會(huì)有饑餓問題)。所以在實(shí)踐中，CFS 會(huì)保證所有線程之間的 vruntime 之差低于搶占時(shí)間(6ms)，它是通過如下兩點(diǎn)來保證的：

  1. 當(dāng)線程創(chuàng)建時(shí)，它的 vruntime 值等于運(yùn)行隊(duì)列中等待執(zhí)行線程的最大 vruntime;
  2. 當(dāng)線程從睡眠中喚醒時(shí)，它的 vruntime 值會(huì)被更新為大于或等于所有待調(diào)度線程中最小的 vruntime。使用最小 vruntime 還可以保證頻繁睡眠的線程優(yōu)先被調(diào)度，這對于桌面系統(tǒng)非常適合，它會(huì)減少交互應(yīng)用的響應(yīng)延遲。

CFS 還引入了啟發(fā)式調(diào)度思想來改善高速緩存利用率。例如，當(dāng)線程被喚醒時(shí)，它會(huì)檢查該線程的 vruntime 和正在運(yùn)行的線程 vruntime 之差是否非常顯著(臨界值是 1ms)，如果不是的話，則不會(huì)搶占當(dāng)前正在運(yùn)行的任務(wù)。但是這種做法還是以犧牲調(diào)度延遲為代價(jià)的，算是一種權(quán)衡吧。

多核負(fù)載均衡:

在多核環(huán)境中，Linux CFS 會(huì)將工作(work)分?jǐn)偟蕉鄠€(gè)處理器核心中執(zhí)行。但是這不等同于將線程均分到多個(gè)處理器。比如，一個(gè) CPU 密集型的線程和 10 個(gè)頻繁睡眠的線程可能分別在兩個(gè)核上執(zhí)行，其中一個(gè)專門執(zhí)行 CPU 密集型線程;而另一個(gè)則處理那 10 個(gè)頻繁睡眠的線程。

為了多個(gè)處理器上的工作量均衡，CFS 使用了 load 指標(biāo)來衡量線程和處理器的負(fù)載情況。線程的負(fù)載和線程的 CPU 平均使用率相關(guān)：經(jīng)常睡眠的線程負(fù)載要低于不睡眠的線程負(fù)載。類似 vruntime，線程的負(fù)載也是線程的優(yōu)先級加權(quán)得到的。而處理器的負(fù)載是在該處理器上可運(yùn)行線程的負(fù)載之和。CFS 會(huì)嘗試均衡處理器的負(fù)載。

CFS 會(huì)在線程創(chuàng)建和喚醒時(shí)關(guān)注處理器的負(fù)載情況，調(diào)度器首先要決定將任務(wù)放在哪個(gè)處理器的運(yùn)行隊(duì)列中。這里也會(huì)涉及到啟發(fā)式思想，比如，如果 CFS 檢查到生產(chǎn)者-消費(fèi)者模型，那么它會(huì)將消費(fèi)者線程盡可能地分散到機(jī)器的多個(gè)處理器上，因?yàn)槎鄶?shù)核心都適合處理喚醒的線程。

負(fù)載均衡還會(huì)周期性發(fā)生，每隔 4ms，每個(gè)處理器都會(huì)嘗試從其它處理器偷取一些工作。當(dāng)然，這種 work-stealing 均衡方法還會(huì)考慮機(jī)器的拓?fù)浣Y(jié)構(gòu)：處理器會(huì)嘗試從距離它們「更近」的其它處理器上嘗試竊取工作，而非距離「更遠(yuǎn)」的處理器(如遠(yuǎn)程 NUMA 節(jié)點(diǎn))。當(dāng)處理器決定要從其它處理器竊取任務(wù)時(shí)，它會(huì)嘗試在二者之間均衡負(fù)載，并且會(huì)竊取多達(dá) 32 個(gè)線程。此外，當(dāng)處理器進(jìn)入空閑狀態(tài)時(shí)，它也會(huì)立刻調(diào)用負(fù)載均衡器。

在大型的 NUMA 機(jī)器上，CFS 并不會(huì)粗暴地比較所有 CPU 的負(fù)載，而是以分層的方式進(jìn)行負(fù)載均衡。以一臺有兩個(gè) NUMA 節(jié)點(diǎn)的機(jī)器為例，CFS 會(huì)先在 NUMA 節(jié)點(diǎn)內(nèi)部的處理器之間進(jìn)行負(fù)載均衡，然后比較 NUMA 節(jié)點(diǎn)之間的負(fù)載(通過節(jié)點(diǎn)內(nèi)部處理器負(fù)載計(jì)算得到)，再?zèng)Q定要不要在兩個(gè)節(jié)點(diǎn)之間進(jìn)行負(fù)載均衡。如果 NUMA 節(jié)點(diǎn)之間的負(fù)載差距在 25% 以內(nèi)，則不會(huì)進(jìn)行負(fù)載均衡?？偨Y(jié)來說，如果兩個(gè)處理器(或處理器組)之間的距離越遠(yuǎn)，那么只有在不平衡性差距越大的情況下才會(huì)考慮負(fù)載均衡。

運(yùn)行隊(duì)列:

CFS 引入了紅黑樹(本質(zhì)上是一棵半平衡二叉樹，對于插入和查找都有 O(log(N)) 的時(shí)間復(fù)雜度)來維護(hù)運(yùn)行隊(duì)列，樹的節(jié)點(diǎn)值是調(diào)度單元的 vruntime，擁有最小 vruntime 的節(jié)點(diǎn)位于樹的最左下邊。

 

接下來看看 cfs_rq 數(shù)據(jù)結(jié)構(gòu)的定義(位于 <kernel/sched/sched.h> )：

  1. struct cfs_rq 
  2. { 
  3.     // 所有任務(wù)的累計(jì)權(quán)重值 
  4.     struct load_weight load; 
  5.     // 表示該隊(duì)列中有多少個(gè)可運(yùn)行的任務(wù) 
  6.     unsigned int nr_running; 
  7.     // 運(yùn)行隊(duì)列中最小的 vruntime 
  8.     u64 min_vruntime; 
  9.     // 紅黑樹的根節(jié)點(diǎn)，指向運(yùn)行任務(wù)隊(duì)列 
  10.     struct rb_root tasks_timeline; 
  11.     // 下一個(gè)即將被調(diào)度的任務(wù) 
  12.     struct rb_node *rb_leftmost; 
  13.     // 指向當(dāng)前正在運(yùn)行的調(diào)度單元 
  14.     struct sched_entity *curr; 
  15. } 

CFS 算法實(shí)際應(yīng)用于調(diào)度單元(這是一個(gè)更通用的抽象，可以是線程、cgroups 等)，調(diào)度單元數(shù)據(jù)結(jié)構(gòu)定義如下(位于 )：

  1. struct sched_entity 
  2. { 
  3.     // 表示調(diào)度單元的負(fù)載權(quán)重（比如該調(diào)度單元是一個(gè)組，則該值就是該組下所有線程的負(fù)載權(quán)重的組合） 
  4.     struct load_weight load; /* for load-balancing */ 
  5.     // 表示紅黑樹的節(jié)點(diǎn) 
  6.     struct rb_node run_node; 
  7.     // 表示當(dāng)前調(diào)度單元是否位于運(yùn)行隊(duì)列 
  8.     unsigned int on_rq; 
  9.     // 開始執(zhí)行時(shí)間 
  10.     u64 exec_start; 
  11.     // 總共運(yùn)行的時(shí)間，該值是通過 `update_curr()` 更新的。 
  12.     u64 sum_exec_runtime; 
  13.     // 基于虛擬時(shí)鐘計(jì)算出該調(diào)度單元已運(yùn)行的時(shí)間 
  14.     u64 vruntime; 
  15.  
  16.     // 用于記錄之前運(yùn)行的時(shí)間之和 
  17.     u64 prev_sum_exec_runtime; 
  18. }; 

虛擬時(shí)鐘:

前面提到的 vruntime 究竟是什么呢?為什么叫作虛擬運(yùn)行時(shí)間呢?接下來就要揭開它的神秘面紗。為了更好地實(shí)現(xiàn)公平性，CFS 使用了虛擬時(shí)鐘來測量一個(gè)等待的調(diào)度單元在一個(gè)完全公平的處理器上允許執(zhí)行的時(shí)間。然而，虛擬時(shí)鐘并沒有真實(shí)的實(shí)現(xiàn)，它只是一個(gè)抽象概念。

我們可以基于真實(shí)時(shí)間和任務(wù)的負(fù)載權(quán)重來計(jì)算出虛擬運(yùn)行時(shí)間，該算法是在 update_cur() 函數(shù)中實(shí)現(xiàn)的，它會(huì)更新調(diào)度單元的時(shí)間記賬信息，以及 CFS 運(yùn)行隊(duì)列的 min_vruntime(完整定義位于 )：

  1. static void update_curr(struct cfs_rq *cfs_rq) 
  2. { 
  3.     struct sched_entity *curr = cfs_rq->curr; 
  4.     u64 now = rq_clock_task(rq_of(cfs_rq)); 
  5.     u64 delta_exec; 
  6.     if (unlikely(!curr)) 
  7.         return; 
  8.     // 計(jì)算出調(diào)度單元開始執(zhí)行時(shí)間和當(dāng)前之間的差值，即真實(shí)運(yùn)行時(shí)間 
  9.     delta_exec = now - curr->exec_start; 
  10.     curr->vruntime += calc_delta_fair(delta_exec, curr); 
  11.     update_min_vruntime(cfs_rq); 
  12. } 
  13.  
  14. static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se) 
  15. { 
  16.     // 如果任務(wù)的優(yōu)先級是默認(rèn)的優(yōu)先級（內(nèi)部 nice 值是 120），那么虛擬運(yùn)行時(shí)間 
  17.     // 就是真實(shí)運(yùn)行時(shí)間。否則，會(huì)基于 `__calc_delta` 計(jì)算出虛擬運(yùn)行時(shí)間。 
  18.     if (unlikely(se->load.weight != NICE_0_LOAD)) 
  19.         // 該計(jì)算過程基本等同于： 
  20.         // delta = delta_exec * NICE_0_LOAD / cur->load.weight; 
  21.         delta = __calc_delta(delta, NICE_0_LOAD, &se->load); 
  22.     return delta; 
  23. } 
  24.  
  25. static void update_min_vruntime(struct cfs_rq *cfs_rq) 
  26. { 
  27.     u64 vruntime = cfs_rq->min_vruntime; 
  28.     if (cfs_rq->curr) 
  29.         // 如果此時(shí)有任務(wù)在運(yùn)行，就更新最小運(yùn)行時(shí)間為當(dāng)前任務(wù)的 vruntime 
  30.         vruntime = cfs_rq->curr->vruntime; 
  31.     if (cfs_rq->rb_leftmost) 
  32.     { 
  33.         // 獲得下一個(gè)要運(yùn)行的調(diào)度單元 
  34.         struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost, 
  35.                                            struct sched_entity, 
  36.                                            run_node); 
  37.         if (!cfs_rq->curr) 
  38.             vruntime = se->vruntime; 
  39.         else 
  40.             // 保證 min_vruntime 是二者之間較小的那個(gè)值 
  41.             vruntime = min_vruntime(vruntime, se->vruntime); 
  42.     } 
  43.  
  44.     // 這里之所以去二者之間的最大值，是為了保證 min_vruntime 能夠單調(diào)增長 
  45.     // 可以想想為什么需要這樣做？ 
  46.     cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime); 
  47. } 

最后，來總結(jié)下使用虛擬時(shí)鐘的意義：當(dāng)任務(wù)運(yùn)行時(shí)，它的虛擬時(shí)間總是會(huì)增加，從而保證它會(huì)被移動(dòng)到紅黑樹的右側(cè);

對于高優(yōu)先級的任務(wù)，虛擬時(shí)鐘的節(jié)拍更慢，從而讓它移動(dòng)到紅黑樹右側(cè)的速度就越慢，因此它們被再次調(diào)度的機(jī)會(huì)就更大些。

 

選擇下一個(gè)任務(wù):

CFS 可以在紅黑樹中一直找到最左(leftmost)邊的節(jié)點(diǎn)作為下一個(gè)運(yùn)行的任務(wù)。但是真正實(shí)現(xiàn) __pick_first_entity() 的函數(shù)其實(shí)并沒有真正地執(zhí)行查找(雖然可以在 O(log(N)) 時(shí)間內(nèi)找到)，我們可以看下它的定義(完整定義位于 )：

  1. struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq) 
  2. { 
  3.     // 其實(shí)這里取的是緩存的 leftmost 節(jié)點(diǎn) 
  4.     // 所以執(zhí)行就會(huì)更快了 
  5.     struct rb_node *left = cfs_rq->rb_leftmost; 
  6.     if (!left) 
  7.         return NULL; 
  8.     return rb_entry(left, struct sched_entity, run_node); 
  9. } 

實(shí)時(shí)調(diào)度器:

Linux 實(shí)時(shí)任務(wù)調(diào)度器實(shí)現(xiàn)位于 <kernel/sched/rt.c，對于系統(tǒng)而言，實(shí)時(shí)任務(wù)屬于貴客，一旦存在實(shí)時(shí)任務(wù)需要調(diào)度，那就應(yīng)當(dāng)盡可能及時(shí)地為它們服務(wù)。對于實(shí)時(shí)任務(wù)而言，有兩種調(diào)度策略存在： 

  • SCHED_FIFO: 這個(gè)其實(shí)就是一個(gè)先到先服務(wù)的調(diào)度算法。這類任務(wù)沒有時(shí)間片限制，它們會(huì)一直運(yùn)行直到阻塞或者主動(dòng)放棄 CPU，亦或者被更高優(yōu)先級的實(shí)時(shí)任務(wù)搶占。該類任務(wù)總會(huì)搶占 SCHED_NORMAL 任務(wù)。如果多個(gè)任務(wù)具有相同的優(yōu)先級，那它們會(huì)以輪詢的方式調(diào)度（也就是當(dāng)一個(gè)任務(wù)完成后，會(huì)被放到隊(duì)列尾部等待下次執(zhí)行）；
  • SCHED_RR: 這種策略類似于 SCHED_FIFO，只是多了時(shí)間片限制。相同優(yōu)先級的任務(wù)會(huì)以輪詢的方式被調(diào)度，每個(gè)運(yùn)行的任務(wù)都會(huì)一直運(yùn)行，直到其用光自己的時(shí)間片，或者被更高優(yōu)先級的任務(wù)搶占。當(dāng)任務(wù)的時(shí)間片用光后，它會(huì)重新補(bǔ)充能量，并被加入到隊(duì)列尾部。默認(rèn)的時(shí)間片是 100ms，可以在 <include/linux/sched/rt.h> 找到其定義。

實(shí)時(shí)任務(wù)的優(yōu)先級是靜態(tài)的，不會(huì)像之前提到的算法，會(huì)重新計(jì)算任務(wù)優(yōu)先級。用戶可以通過 chrt 命令更改任務(wù)優(yōu)先級。

實(shí)現(xiàn)細(xì)節(jié):

實(shí)時(shí)任務(wù)有自己的調(diào)度單元數(shù)據(jù)結(jié)構(gòu)(位于 )，其定義如下：

  1. struct sched_rt_entity 
  2. { 
  3.     struct list_head run_list; 
  4.     unsigned long timeout; 
  5.     unsigned long watchdog_stamp; 
  6.     unsigned int time_slice; 
  7.     struct sched_rt_entity *back; 
  8.     struct sched_rt_entity *parent; 
  9.     /* rq on which this entity is (to be) queued: */ 
  10.     struct rt_rq *rt_rq; 
  11. }; 

SCHED_FIFO 的時(shí)間片是 0，可以在 中看到具體定義：

  1. int sched_rr_timeslice = RR_TIMESLICE; 
  2. static unsigned int get_rr_interval_rt(struct rq *rq, 
  3.                                        struct task_struct *task) 
  4. { 
  5.     if (task->policy == SCHED_RR) 
  6.         return sched_rr_timeslice; 
  7.     else 
  8.         return 0; 
  9. } 

而關(guān)于運(yùn)行隊(duì)列的定義如下：

  1. /* Real-Time classes' related field in a runqueue: */ 
  2. struct rt_rq 
  3. { 
  4.     // 所有相同優(yōu)先級的實(shí)時(shí)任務(wù)都保存在 `active.queue[prio]` 鏈表中 
  5.     struct rt_prio_array active; 
  6.     unsigned int rt_nr_running; 
  7.     struct rq *rq; /* main runqueue */ 
  8. }; 
  9.  
  10. /* 
  11. * This is the priority-queue data structure of the RT scheduling class: 
  12. */ 
  13. struct rt_prio_array 
  14. { 
  15.     /* include 1 bit for delimiter */ 
  16.     // 類似 O(1) 調(diào)度器，使用位圖來標(biāo)記對應(yīng)優(yōu)先級的鏈表是否為空 
  17.     DECLARE_BITMAP(bitmap, MAX_RT_PRIO + 1); 
  18.     struct list_head queue[MAX_RT_PRIO]; 
  19. }; 

類似于 CFS 中的 update_curr() 函數(shù)，update_curr_rt() 函數(shù)用來跟蹤實(shí)時(shí)任務(wù)的 CPU 占用情況，收集一些統(tǒng)計(jì)信息，更新時(shí)間片等，但這里使用的是真實(shí)時(shí)間，而沒有虛擬時(shí)間的概念。完整定義可以參考 kernel/sched/rt.c。

BFS & MuqSS調(diào)度器:

總體來說，BFS 是一個(gè)適用于桌面或移動(dòng)設(shè)備的調(diào)度器，設(shè)計(jì)地比較簡潔，用于改善桌面應(yīng)用的交互性，減小響應(yīng)時(shí)間，提升用戶體驗(yàn)。它采用了全局單任務(wù)隊(duì)列設(shè)計(jì)，不再讓每個(gè) CPU 都有獨(dú)立的運(yùn)行隊(duì)列。雖然使用單個(gè)全局隊(duì)列，需要引入隊(duì)列鎖來保證并發(fā)安全性，但是對于桌面系統(tǒng)而言，處理器通常都比較少，鎖的開銷基本可以忽略。BFS 每次會(huì)在任務(wù)鏈表中選擇具有最小 virtual deadline 的任務(wù)運(yùn)行。

MuqSS 是作者后來基于 BFS 改進(jìn)的一款調(diào)度器，同樣是用于桌面環(huán)境任務(wù)調(diào)度。它主要解決了 BFS 的兩個(gè)問題：

  1. 每次需要在對應(yīng)優(yōu)先級鏈表中遍歷查找需要執(zhí)行任務(wù)，這個(gè)時(shí)間復(fù)雜度為 O(n)。所以新的調(diào)度器引入了跳表來解決該問題，從而將時(shí)間復(fù)雜度降低到 O(1)。
  2. 全局鎖爭奪的開銷優(yōu)化，采用 try_lock 替代 lock。

 

責(zé)任編輯：武曉燕 來源： 人人都是極客
LinuxKernel調(diào)度器
相關(guān)推薦

2016-08-28 15:55:04

Hadoop大數(shù)據(jù)

2012-02-16 09:10:31

JavaScript

2017-08-08 15:40:26

OpenStack轉(zhuǎn)型基金會(huì)

2017-03-22 20:36:34

深度學(xué)習(xí)機(jī)器學(xué)習(xí)人工智能

2020-05-26 11:17:34

區(qū)塊鏈金融技術(shù)

2023-03-21 11:24:44

eSIM移動(dòng)通信

2020-11-17 13:00:37

物聯(lián)網(wǎng)IOT物聯(lián)網(wǎng)應(yīng)用

2019-09-08 17:37:47

2024-12-18 07:45:18

2021-07-16 10:05:34

項(xiàng)目企業(yè)系統(tǒng)

2021-08-16 08:44:54

Pravega Fli項(xiàng)目協(xié)議

2022-05-17 16:13:31

區(qū)塊鏈以太坊監(jiān)管

2022-07-14 08:17:59

中間件微服務(wù)開發(fā)

2009-05-15 17:23:56

2017-11-24 13:51:40

數(shù)據(jù)倉庫數(shù)據(jù)庫數(shù)據(jù)分析

2021-08-12 10:25:55

人工智能AI人工智能技術(shù)

2018-08-06 13:25:28

人工智能深度學(xué)習(xí)芯片

2020-11-30 11:06:52

數(shù)據(jù)中心數(shù)據(jù)中心融合

2012-06-25 14:57:27

HTML5

2018-08-09 20:41:29

人工智能AI神經(jīng)網(wǎng)絡(luò)
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號