一、前言

隨著內(nèi)核版本的演進(jìn)，其源代碼的膨脹速度也在遞增，這讓Linux的學(xué)習(xí)曲線變得越來(lái)越陡峭了。這對(duì)初識(shí)內(nèi)核的同學(xué)而言當(dāng)然不是什么好事情，滿腔熱情很容易被當(dāng)頭澆滅。我有一個(gè)循序漸進(jìn)的方法，那就是先不要看最新的內(nèi)核，首先找到一個(gè)古老版本的內(nèi)核（一般都會(huì)比較簡(jiǎn)單），將其吃透，然后一點(diǎn)點(diǎn)的迭代，理解每個(gè)版本變更背后的緣由和目的，最終推進(jìn)到最新內(nèi)核版本。

本文就是從2.4時(shí)代的任務(wù)調(diào)度器開始，詳細(xì)描述其實(shí)現(xiàn)并慢慢向前遞進(jìn)。當(dāng)然，為了更好的理解Linux調(diào)度器設(shè)計(jì)和實(shí)現(xiàn)，我們?cè)诘诙陆o出了一些通用的概念。之后，我們會(huì)在第四章講述O（1）調(diào)度器如何改進(jìn)并提升調(diào)度器性能。真正有劃時(shí)代意義的是CFS調(diào)度器，在2.6.23版本的內(nèi)核中并入主線。它的設(shè)計(jì)思想是那么的眩目，即便是目前最新的內(nèi)核中，完全公平的設(shè)計(jì)思想仍然沒有太大變化，這些我們會(huì)在第六章描述。第五章是關(guān)于公平調(diào)度思想的引入，通過這一章可以了解Con Kolivas的RSDL調(diào)度器，它是開啟公平調(diào)度的先鋒，通過這一章的鋪墊，我們可以更順暢的理解CFS。

二、任務(wù)調(diào)度器概述

為了不引起混亂，我們一開始先澄清幾個(gè)概念。進(jìn)程調(diào)度器是傳統(tǒng)的說(shuō)法，但是實(shí)際上進(jìn)程是資源管理的單位，線程才是調(diào)度的單位，但是線程調(diào)度器的說(shuō)法讓我覺得很不舒服，因此最終采用進(jìn)程調(diào)度器或者任務(wù)調(diào)度器的說(shuō)法。為了節(jié)省字，本文有些地方也直接簡(jiǎn)稱調(diào)度器，此外，除非特別說(shuō)明，本文中的“進(jìn)程”指的是task struct代表的那個(gè)實(shí)體，畢竟這是一篇講調(diào)度器的文檔。

任務(wù)調(diào)度器是操作系統(tǒng)一個(gè)很重要的部件，它的主要功能就是把系統(tǒng)中的task調(diào)度到各個(gè)CPU上去執(zhí)行滿足如下的性能需求：

1、對(duì)于time-sharing的進(jìn)程，調(diào)度器必須是公平的

2、快速的進(jìn)程響應(yīng)時(shí)間

3、系統(tǒng)的throughput要高

4、功耗要小

當(dāng)然，不同的任務(wù)有不同的需求，因此我們需要對(duì)任務(wù)進(jìn)行分類：一種是普通進(jìn)程，另外一種是實(shí)時(shí)進(jìn)程。對(duì)于實(shí)時(shí)進(jìn)程，毫無(wú)疑問快速響應(yīng)的需求是最重要的，而對(duì)于普通進(jìn)程，我們需要兼顧前三點(diǎn)的需求。相信你也發(fā)現(xiàn)了，這些需求是互相沖突的，對(duì)于這些time-sharing的普通進(jìn)程如何平衡設(shè)計(jì)呢？這里需要進(jìn)一步將普通進(jìn)程細(xì)分為交互式進(jìn)程（interactive processs）和批處理進(jìn)程（batch process）。交互式進(jìn)程需要和用戶進(jìn)行交流，因此對(duì)調(diào)度延遲比較敏感，而批處理進(jìn)程屬于那種在后臺(tái)默默干活的，因此它更注重throughput的需求。當(dāng)然，無(wú)論如何，分享時(shí)間片的普通進(jìn)程還是需要兼顧公平，不能有人大魚大肉，有人連湯都喝不上。功耗的需求其實(shí)一直以來(lái)都沒有特別被調(diào)度器重視，當(dāng)然在linux大量在手持設(shè)備上應(yīng)用之后，調(diào)度器不得不面對(duì)這個(gè)問題了，當(dāng)然限于篇幅，本文就不展開了。

為了達(dá)到這些設(shè)計(jì)目標(biāo)，調(diào)度器必須要考慮某些調(diào)度因素，比如說(shuō)“優(yōu)先級(jí)”、“時(shí)間片”等。很多RTOS的調(diào)度器都是priority-based的，官大一級(jí)壓死人，調(diào)度器總是選擇優(yōu)先級(jí)最高的那個(gè)進(jìn)程執(zhí)行。而在Linux內(nèi)核中，優(yōu)先級(jí)就是實(shí)時(shí)進(jìn)程調(diào)度的主要考慮因素。而對(duì)于普通進(jìn)程，如何細(xì)分時(shí)間片則是調(diào)度器的核心思考點(diǎn)。過大的時(shí)間片會(huì)嚴(yán)重?fù)p傷系統(tǒng)的響應(yīng)延遲，讓用戶明顯能夠感知到延遲，卡頓，從而影響用戶體驗(yàn)。較小的時(shí)間片雖然有助于減少調(diào)度延遲，但是頻繁的切換對(duì)系統(tǒng)的throughput會(huì)造成嚴(yán)重的影響。因?yàn)檫@時(shí)候大部分的CPU時(shí)間用于進(jìn)程切換，而忘記了它本來(lái)的功能其實(shí)就是推動(dòng)任務(wù)的執(zhí)行。

由于Linux是一個(gè)通用操作系統(tǒng)，它的目標(biāo)是星辰大海，既能運(yùn)行在嵌入式平臺(tái)上，又能在服務(wù)器領(lǐng)域中獲得很好的性能表現(xiàn)，此外在桌面應(yīng)用場(chǎng)景中，也不能讓用戶有較差的用戶體驗(yàn)。因此，Linux任務(wù)調(diào)度器的設(shè)計(jì)是一個(gè)極具挑戰(zhàn)性的工作，需要在各種有沖突的需求中維持平衡。還好，經(jīng)過幾十年內(nèi)核黑客孜孜不倦的努力，Linux內(nèi)核正在向著最終目標(biāo)邁進(jìn)。

三、2.4時(shí)代的O（n）調(diào)度器

網(wǎng)上有很多的linux內(nèi)核考古隊(duì)，挖掘非常古老內(nèi)核的設(shè)計(jì)和實(shí)現(xiàn)。雖然我對(duì)進(jìn)程調(diào)度器歷史感興趣，但是我只對(duì)“近代史”感興趣，因此，讓我們從2.4時(shí)代開始吧，具體的內(nèi)核版本我選擇的是2.4.18版本，該版本的調(diào)度器相關(guān)軟件結(jié)構(gòu)可以參考下面的圖片：

本章所有的描述都是基于上面的軟件結(jié)構(gòu)圖。

1、進(jìn)程描述符

對(duì)于2.4內(nèi)核，進(jìn)程切換有兩種，一種是當(dāng)進(jìn)程由于需要等待某種資源而無(wú)法繼續(xù)執(zhí)行下去，這時(shí)候只能是主動(dòng)將自己掛起（調(diào)用schedule函數(shù)），引發(fā)一次任務(wù)調(diào)度過程。另外一種是進(jìn)程歡快執(zhí)行，但是由于各種調(diào)度事件的發(fā)生（例如時(shí)間片用完）而被迫讓出CPU，被其他進(jìn)程搶占。這時(shí)候的調(diào)度并不是立刻發(fā)送，而是延遲執(zhí)行，具體的方法是設(shè)定當(dāng)前進(jìn)程的need_resched等于1，然后靜靜的等待最近一個(gè)調(diào)度點(diǎn)的來(lái)臨，當(dāng)調(diào)度點(diǎn)到來(lái)的時(shí)候，內(nèi)核會(huì)調(diào)用schedule函數(shù)，搶占當(dāng)前task的執(zhí)行。

nice成員就是普通進(jìn)程的靜態(tài)優(yōu)先級(jí)，通過NICE_TO_TICKS宏可以將一個(gè)進(jìn)程的靜態(tài)優(yōu)先級(jí)映射成缺省時(shí)間片，保存在counter成員中。因此在一次調(diào)度周期開始的時(shí)候，counter其實(shí)就是該進(jìn)程分配的CPU時(shí)間額度（對(duì)于睡眠的進(jìn)程還有些獎(jiǎng)勵(lì)，后面會(huì)描述），以tick為單位，并且在每個(gè)tick到來(lái)的時(shí)候減一，直到耗盡其時(shí)間片，然后等待下一個(gè)調(diào)度周期從頭再來(lái)。

Policy是調(diào)度策略，2.4內(nèi)核主要支持三種調(diào)度策略，SCHED_OTHER是普通進(jìn)程，SCHED_RR和SCHED_FIFO是實(shí)時(shí)進(jìn)程。SCHED_RR和SCHED_FIFO的調(diào)度策略在rt_priority不同的時(shí)候，都是誰(shuí)的優(yōu)先級(jí)高誰(shuí)先執(zhí)行，唯一的不同是相同優(yōu)先級(jí)的處理：SCHED_RR采用時(shí)間片輪轉(zhuǎn)，而SCHED_FIFO采用的策略是先到先得，先占有CPU的進(jìn)程會(huì)持續(xù)執(zhí)行，直到退出或者阻塞的時(shí)候才會(huì)讓出CPU。也只有這時(shí)候，其他同優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程才有機(jī)會(huì)執(zhí)行。如果進(jìn)程是實(shí)時(shí)進(jìn)程，那么rt_priority表示該進(jìn)程的靜態(tài)優(yōu)先級(jí)。這個(gè)成員對(duì)普通進(jìn)程是無(wú)效的，可以設(shè)定為0。除了上面描述的三種調(diào)度策略，policy成員也可以設(shè)定SCHED_YIELD的標(biāo)記，當(dāng)然它和調(diào)度策略無(wú)關(guān)，主要處理sched_yield系統(tǒng)調(diào)用的。

Processor、cpus_runnable和cpus_allowed這三個(gè)成員都是和CPU相關(guān)。Processor說(shuō)明了該進(jìn)程正在執(zhí)行（或者上次執(zhí)行）的邏輯CPU號(hào)；cpus_allowed是該task允許在那些CPU上執(zhí)行的掩碼；cpus_runnable是為了計(jì)算一個(gè)指定的進(jìn)程是否適合調(diào)度到指定的CPU上去執(zhí)行而引入的，如果該進(jìn)程沒有被任何CPU執(zhí)行，那么所有的bit被設(shè)定為1，如果進(jìn)程正在被某個(gè)CPU執(zhí)行，那么正在執(zhí)行的CPU bit設(shè)定為1，其他設(shè)定為0。具體如何使用cpus_runnable可以參考can_schedule函數(shù)。

run_list成員是鏈接入各種鏈表的節(jié)點(diǎn)，下一小節(jié)會(huì)描述內(nèi)核如何組織task，這里不再贅述。

2、如何組織task

Linux2.4版本的進(jìn)程調(diào)度器使用了非常簡(jiǎn)陋的方法來(lái)管理可運(yùn)行狀態(tài)的進(jìn)程。調(diào)度器模塊定義了一個(gè)runqueue_head的鏈表頭變量，無(wú)論進(jìn)程是普通進(jìn)程還是實(shí)時(shí)進(jìn)程，只要進(jìn)程狀態(tài)變成可運(yùn)行狀態(tài)的時(shí)候，它會(huì)被掛入這個(gè)全局runqueue鏈表中。隨著系統(tǒng)的運(yùn)行，runqueue鏈表中的進(jìn)程會(huì)不斷的插入或者移除。例如當(dāng)fork進(jìn)程的時(shí)候，新鮮出爐的子進(jìn)程會(huì)掛入這個(gè)runqueue。當(dāng)阻塞或者退出的時(shí)候，進(jìn)程會(huì)從這個(gè)runqueue中刪除。但是無(wú)論如何變遷，調(diào)度器始終只是關(guān)注這個(gè)全局runqueue鏈表中的task，并把最適合的那個(gè)任務(wù)丟到CPU上去執(zhí)行。由于整個(gè)系統(tǒng)中的所有CPU共享一個(gè)runqueue，為了解決同步問題，調(diào)度器模塊定義了一個(gè)自旋鎖來(lái)保護(hù)對(duì)這個(gè)全局runqueue的并發(fā)訪問

除了這個(gè)runqueue隊(duì)列，系統(tǒng)還有一個(gè)囊括所有task（不管其進(jìn)程狀態(tài)為何）的鏈表，鏈表頭定義為init_task，在一個(gè)調(diào)度周期結(jié)束后，重新為task賦初始時(shí)間片值的時(shí)候會(huì)用到該鏈表。此外，進(jìn)入sleep狀態(tài)的進(jìn)程分別掛入了不同的等待隊(duì)列中。當(dāng)然，由于這些進(jìn)程鏈表和調(diào)度關(guān)系不是那么密切，因此上圖中并沒有標(biāo)識(shí)出來(lái)。

3、動(dòng)態(tài)優(yōu)先級(jí)和靜態(tài)優(yōu)先級(jí)

所謂靜態(tài)優(yōu)先級(jí)就是task固有的優(yōu)先級(jí)，不會(huì)隨著進(jìn)程的行為而改變。對(duì)于實(shí)時(shí)進(jìn)程，靜態(tài)優(yōu)先級(jí)就是rt_priority，而對(duì)于普通進(jìn)程，靜態(tài)優(yōu)先級(jí)就是（20 – nice）。然而實(shí)際上調(diào)度器在進(jìn)行調(diào)度的時(shí)候，并沒有采用靜態(tài)優(yōu)先級(jí)，而是比對(duì)動(dòng)態(tài)優(yōu)先級(jí)來(lái)決定誰(shuí)更有資格獲得CPU資源，當(dāng)然動(dòng)態(tài)優(yōu)先級(jí)的計(jì)算是基于靜態(tài)優(yōu)先級(jí)的。

在計(jì)算動(dòng)態(tài)優(yōu)先級(jí)（goodness函數(shù)）的時(shí)候，我們可以分成兩種情況：實(shí)時(shí)進(jìn)程和普通進(jìn)程。對(duì)于實(shí)時(shí)進(jìn)程而言，動(dòng)態(tài)優(yōu)先級(jí)等于靜態(tài)優(yōu)先級(jí)加上一個(gè)固定的偏移：

之所以這么做是為了將實(shí)時(shí)進(jìn)程和普通進(jìn)程區(qū)別開，這樣的操作也保證了實(shí)時(shí)進(jìn)程會(huì)完全優(yōu)先于普通進(jìn)程的調(diào)度。而對(duì)于普通進(jìn)程，動(dòng)態(tài)優(yōu)先級(jí)的計(jì)算稍微有些復(fù)雜，我們可以摘錄部分代碼如下：

對(duì)于普通進(jìn)程，計(jì)算動(dòng)態(tài)優(yōu)先級(jí)的策略如下：

（1） 如果該進(jìn)程的時(shí)間片已經(jīng)耗盡，那么動(dòng)態(tài)優(yōu)先級(jí)是0，這也意味著在本次調(diào)度周期中該進(jìn)程已經(jīng)再也沒有機(jī)會(huì)獲取CPU資源了。

（2） 如果該進(jìn)程的時(shí)間片還有剩余，那么其動(dòng)態(tài)優(yōu)先級(jí)等于該進(jìn)程剩余的時(shí)間片和靜態(tài)優(yōu)先級(jí)之和。之所以用（20-nice value）表示靜態(tài)優(yōu)先級(jí)，主要是為了讓靜態(tài)優(yōu)先級(jí)變成單調(diào)上升。之所以要考慮剩余時(shí)間片是為了獎(jiǎng)勵(lì)睡眠的進(jìn)程，因?yàn)樗叩倪M(jìn)程剩余的時(shí)間片較多，因此動(dòng)態(tài)優(yōu)先級(jí)也就會(huì)高一些，更容易被調(diào)度器調(diào)度執(zhí)行。

調(diào)度器是根據(jù)動(dòng)態(tài)優(yōu)先級(jí)來(lái)進(jìn)行調(diào)度，誰(shuí)大就先執(zhí)行誰(shuí)。我們可以用普通進(jìn)程作為例子：如果進(jìn)程靜態(tài)優(yōu)先級(jí)高（即nice value?。?，剩余時(shí)間片多，那么必定是優(yōu)先執(zhí)行。如果靜態(tài)優(yōu)先級(jí)高，但是所剩時(shí)間片無(wú)幾，那么可能會(huì)讓位給其他剩余時(shí)間片較多，優(yōu)先級(jí)適中的任務(wù)。靜態(tài)優(yōu)先級(jí)低的任務(wù)毫無(wú)疑問是受到雙重打擊，因?yàn)楸緛?lái)它的缺省時(shí)間片就不多，而且優(yōu)先級(jí)也很低。不過，無(wú)論靜態(tài)優(yōu)先級(jí)如何高，只要時(shí)間片用完，那么低優(yōu)先級(jí)的任務(wù)總是能夠有機(jī)會(huì)執(zhí)行，不至于餓死。

在計(jì)算普通進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)的時(shí)候，除了考慮進(jìn)程剩余時(shí)間片信息和靜態(tài)優(yōu)先級(jí)，調(diào)度器也會(huì)酌情考慮cache和TLB的性能問題。例如，例如A和B進(jìn)程優(yōu)先級(jí)相同，剩余的時(shí)間片都是3個(gè)tick，但是A進(jìn)程上一次就是運(yùn)行在本CPU上，如果選擇A，可能會(huì)有更好的cache和TLB的命中率，從而提高性能。在這種情況下，調(diào)度器會(huì)提升A進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)。此外，如果備選進(jìn)程和當(dāng)前進(jìn)程共享同一個(gè)地址空間，那么在計(jì)算調(diào)度指數(shù)的時(shí)候也會(huì)做小小的傾斜。這里有兩種可能的情況：一種是備選進(jìn)程和當(dāng)前進(jìn)程在一個(gè)線程組中（即是進(jìn)程中的兩個(gè)線程），另外一種情況是備選進(jìn)程是內(nèi)核線程，這時(shí)候，它往往會(huì)借用上一個(gè)進(jìn)程地址空間。不論是哪一種情況，在進(jìn)程切換的時(shí)候，由于不需要進(jìn)行進(jìn)程地址空間的切換，因此也會(huì)有性能的優(yōu)勢(shì)。

3、調(diào)度時(shí)機(jī)

對(duì)于2.4內(nèi)核，產(chǎn)生調(diào)度的時(shí)機(jī)主要包括：

（1） 進(jìn)程主動(dòng)發(fā)起調(diào)度。

（2） 在timer中斷處理中發(fā)現(xiàn)當(dāng)前進(jìn)程耗盡其時(shí)間片

（3） 進(jìn)程喚醒的時(shí)候（例如喚醒一個(gè)RT進(jìn)程）。更詳細(xì)的信息可以參考下一個(gè)小節(jié)。

（4） 父進(jìn)程在fork的時(shí)候，其時(shí)間片會(huì)均分到父子進(jìn)程，但是如果只剩下一個(gè)tick，這個(gè)tick會(huì)分配給子進(jìn)程，而父進(jìn)程的時(shí)間片則被清零，這時(shí)候，進(jìn)程遭遇的場(chǎng)景等同與在timer中斷處理中發(fā)現(xiàn)當(dāng)前進(jìn)程耗盡其時(shí)間片。如果父進(jìn)程在fork的時(shí)候，其時(shí)間片較大，父子進(jìn)程的時(shí)間片都不為0，這時(shí)候的場(chǎng)景類似于喚醒進(jìn)程。因?yàn)檫@兩個(gè)場(chǎng)景都是向runqueue中添加了一個(gè)task node，從而引發(fā)的調(diào)度。

（5） 進(jìn)程切換的時(shí)候。當(dāng)在系統(tǒng)中的某個(gè)CPU上發(fā)生了進(jìn)程切換，例如A任務(wù)切換到了B任務(wù)，這時(shí)候是否A任務(wù)就失去了執(zhí)行的機(jī)會(huì)了呢？當(dāng)然也未必，因?yàn)殡m然競(jìng)爭(zhēng)本CPU失敗，但是也許其他的CPU上運(yùn)行的task動(dòng)態(tài)優(yōu)先級(jí)還不如A呢，抑或正好其他CPU有進(jìn)入idle狀態(tài)，正等待著新進(jìn)程入駐。

（6） 用戶進(jìn)程主動(dòng)讓出CPU的時(shí)候

（7） 用戶進(jìn)程修改調(diào)度參數(shù)的時(shí)候

上面的種種場(chǎng)景，除了進(jìn)程主動(dòng)調(diào)度之外，其他的場(chǎng)景都不是立刻調(diào)度schedule函數(shù)，而是設(shè)定need_resched標(biāo)記，然后等待調(diào)度點(diǎn)的到來(lái)。由于2.4內(nèi)核不是preemptive kernel，因此調(diào)度點(diǎn)總是在返回用戶空間的時(shí)候才會(huì)到來(lái)。當(dāng)調(diào)度點(diǎn)到來(lái)的時(shí)候，進(jìn)程調(diào)度就會(huì)在該CPU上啟動(dòng)。搶占的場(chǎng)景太多，我們選擇進(jìn)程喚醒的場(chǎng)景來(lái)詳細(xì)描述，其他場(chǎng)景大家自行分析吧。

4、進(jìn)程喚醒的處理

當(dāng)進(jìn)程被喚醒的時(shí)候（try_to_wake_up），該task會(huì)被加入到那個(gè)全局runqueue中，但是是否啟動(dòng)調(diào)度還需要進(jìn)行一系列的判斷。為了能清楚的描述這個(gè)場(chǎng)景，我們定義執(zhí)行喚醒的那個(gè)進(jìn)程是waker，而被喚醒的進(jìn)程是wakee。Wakeup有兩種，一種是sync wakeup，另外一種是non-sync wakeup。所謂sync wakeup就是waker在喚醒wakee的時(shí)候就已經(jīng)知道自己很快就進(jìn)入sleep狀態(tài)，而在調(diào)用try_to_wake_up的時(shí)候最好不要進(jìn)行搶占，因?yàn)閣aker很快就主動(dòng)發(fā)起調(diào)度了。此外，一般而言，waker和wakee會(huì)有一定的親和性（例如它們通過share memory進(jìn)行通信），在SMP場(chǎng)景下，waker和wakee調(diào)度在一個(gè)CPU上執(zhí)行的時(shí)候往往可以獲取較佳的性能。而如果在try_to_wake_up的時(shí)候就進(jìn)行調(diào)度，這時(shí)候wakee往往會(huì)調(diào)度到系統(tǒng)中其他空閑的CPU上去。這時(shí)候，通過sync wakeup，我們往往可以避免不必要的CPU bouncing。對(duì)于non-sync wakeup而言，waker和wakee沒有上面描述的同步關(guān)系，waker在喚醒wakee之后，它們之間是獨(dú)立運(yùn)作，因此在喚醒的時(shí)候就可以嘗試去觸發(fā)一次調(diào)度。

當(dāng)然，也不是說(shuō)sync wakeup就一定不調(diào)度，假設(shè)waker在CPU A上喚醒wakee，而根據(jù)wakee進(jìn)程的cpus_allowed成員發(fā)現(xiàn)它根本不能在CPU A上調(diào)度執(zhí)行，那么管他sync不sync，這時(shí)候都需要去嘗試調(diào)度（調(diào)用reschedule_idle函數(shù)），反正waker和wakee命中注定是天各一方（在不同的CPU上執(zhí)行）。

我們首先看看UP上的情況。這時(shí)候waker和wakee在同一個(gè)CPU上運(yùn)行（當(dāng)然系統(tǒng)中也只有一個(gè)CPU，哈哈），這時(shí)候誰(shuí)能搶占CPU資源完全取決于waker和wakee的動(dòng)態(tài)優(yōu)先級(jí)，如果wakee的動(dòng)態(tài)優(yōu)先級(jí)大于waker，那么就標(biāo)記waker的need_resched標(biāo)志，并在調(diào)度點(diǎn)到來(lái)的時(shí)候調(diào)用schedule函數(shù)進(jìn)行調(diào)度。

SMP情況下，由于系統(tǒng)的CPU資源比較多，waker和wakee沒有必要爭(zhēng)個(gè)你死我活，wakee其實(shí)也可以選擇去其他CPU執(zhí)行，相關(guān)的算法大致如下：

（1） 優(yōu)先調(diào)度wakee去系統(tǒng)其他空閑的CPU上執(zhí)行，如果wakee上次運(yùn)行的CPU恰好處于idle狀態(tài)的時(shí)候，可以考慮優(yōu)先將wakee調(diào)度到那個(gè)CPU上執(zhí)行。如果不是，那么需要掃描系統(tǒng)中所有的CPU找到最合適的idle CPU。所謂最合適就是指最近才進(jìn)入idle的那個(gè)CPU。

（2） 如果所有的CPU都是busy的，那么需要遍歷所有CPU上當(dāng)前運(yùn)行的task，比對(duì)它們的動(dòng)態(tài)優(yōu)先級(jí)，找到動(dòng)態(tài)優(yōu)先級(jí)最低的那個(gè)CPU。

（3） 如果動(dòng)態(tài)優(yōu)先級(jí)最低的那個(gè)task的優(yōu)先級(jí)仍然高于wakee，那么沒有必要調(diào)度，runqueue中的wakee需要耐心等待下一次機(jī)會(huì)。如果wakee的動(dòng)態(tài)優(yōu)先級(jí)高于找到的那個(gè)動(dòng)態(tài)優(yōu)先級(jí)最低的task，那么標(biāo)記其need_resched標(biāo)志。如果不是搶占waker，那么我們還需要發(fā)送IPI去觸發(fā)該CPU的調(diào)度。

當(dāng)然，這是2.4內(nèi)核調(diào)度器的設(shè)計(jì)選擇，實(shí)際上這樣的操作值得商榷。限于篇幅，本文就不再展開敘述，如果有機(jī)會(huì)寫負(fù)載均衡的文章就可以好好的把這些關(guān)系梳理一下。

5、主調(diào)度器算法

主調(diào)度器（schedule函數(shù)）核心代碼如下：

list_for_each用來(lái)遍歷runqueue_head鏈表上的所有的進(jìn)程，臨時(shí)變量p就是本次需要檢查的進(jìn)程描述符。如何判斷哪一個(gè)進(jìn)程是最適合調(diào)度執(zhí)行的進(jìn)程呢？我們需要計(jì)算進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)（對(duì)應(yīng)上面程序中的變量weight），它是通過goodness函數(shù)實(shí)現(xiàn)的。動(dòng)態(tài)優(yōu)先級(jí)最大的那個(gè)進(jìn)程就是當(dāng)前最適合調(diào)度到CPU執(zhí)行的進(jìn)程。一旦選中，調(diào)度器會(huì)啟動(dòng)進(jìn)程切換，運(yùn)行該進(jìn)程以替換之前的那個(gè)進(jìn)程。

根據(jù)代碼可知：即便鏈表第一個(gè)節(jié)點(diǎn)就是最合的下一個(gè)要調(diào)度執(zhí)行的進(jìn)程，調(diào)度器算法仍然會(huì)遍歷全局runqueue鏈表，一一比對(duì)。由此我們可以判斷2.4內(nèi)核中的調(diào)度器的算法復(fù)雜度是O（n）。一旦選中了下一個(gè)要執(zhí)行的進(jìn)程，進(jìn)程切換模塊就會(huì)在該CPU上執(zhí)行具體的進(jìn)程切換。

對(duì)于SCHED_RR的實(shí)時(shí)進(jìn)程，優(yōu)先級(jí)相等的情況下還需要有一個(gè)時(shí)間片輪轉(zhuǎn)的概念。因此，在遍歷鏈表之前我們就先處理該進(jìn)程的時(shí)間片處理：

如果時(shí)間片（對(duì)應(yīng)上面程序中的prev->counter）用完，SCHED_RR的實(shí)時(shí)進(jìn)程會(huì)被移到runqueue鏈表的尾部。通過這樣的處理，優(yōu)先級(jí)相等的SCHED_RR在遍歷runqueue鏈表的時(shí)候會(huì)命中鏈表中的第一個(gè)task，從而實(shí)現(xiàn)時(shí)間片輪轉(zhuǎn)的概念。這里有一個(gè)比較奇葩的事情就是SCHED_RR的時(shí)間片是根據(jù)其nice value設(shè)定，而實(shí)際上nice value應(yīng)該只適用于普通進(jìn)程的。

6、時(shí)間片處理

普通進(jìn)程的時(shí)間片處理思路是這樣：

（1）每個(gè)進(jìn)程根據(jù)其靜態(tài)優(yōu)先級(jí)可以固定分配一個(gè)缺省的時(shí)間片，靜態(tài)優(yōu)先級(jí)越大，分配的時(shí)間片就越大。

（2）一旦Runqueue中的進(jìn)程被調(diào)度執(zhí)行，那么其時(shí)間片就會(huì)在tick到來(lái)的時(shí)候遞減，如果進(jìn)程時(shí)間片耗盡，那么該進(jìn)程將失去分配CPU資源的資格。

（3）Runqueue中的進(jìn)程的時(shí)間片全部被用完之后，我們稱一個(gè)調(diào)度周期結(jié)束，這時(shí)候需要為runqueue中的進(jìn)程重新設(shè)定其缺省時(shí)間片，這樣，一個(gè)新的調(diào)度周期又開始了。

如何確定每個(gè)進(jìn)程的缺省時(shí)間片呢？由于時(shí)間片是按照tick來(lái)分配的，那么最小的時(shí)間片也是1個(gè)tick，也就是說(shuō)最低優(yōu)先級(jí)（nice value等于19）的缺省時(shí)間片就是1個(gè)tick。對(duì)于中間優(yōu)先級(jí)（nice value等于0）的時(shí)間片，我們將其設(shè)定為50ms左右，具體的算法大家可以自行參考NICE_TO_TICKS的代碼實(shí)現(xiàn)。不得不承認(rèn)這個(gè)根據(jù)nice value計(jì)算缺省時(shí)間片的過程還是很丑陋的，不同的HZ設(shè)定，計(jì)算得到的缺省時(shí)間片是不一樣的。也就是說(shuō)系統(tǒng)的調(diào)度行為和HZ的設(shè)定有關(guān)，這叫有代碼潔癖的同學(xué)如何能夠接受。不論如何，我們還是給出實(shí)際的例子來(lái)感受一下：

當(dāng)runqueue中所有進(jìn)程的時(shí)間片耗盡之后，這時(shí)候就會(huì)開啟一次重新加載進(jìn)程缺省時(shí)間片的過程，代碼如下（在schedule函數(shù)中）：

這里c就是遍歷runqueue鏈表之后找到的最大動(dòng)態(tài)優(yōu)先級(jí)，如果它等于0則說(shuō)明：首先，系統(tǒng)中沒有處于可運(yùn)行狀態(tài)的實(shí)時(shí)進(jìn)程，其次，所有的處于可運(yùn)行狀態(tài)的普通進(jìn)程都已經(jīng)消耗完了它們的時(shí)間片，這時(shí)候是需要重新“充值”了。for_each_task這個(gè)宏是遍歷所有系統(tǒng)中的進(jìn)程描述符，不論是否是可運(yùn)行狀態(tài)的。對(duì)于掛入runqueue鏈表中的普通進(jìn)程而言，其當(dāng)前的時(shí)間片p->counter已經(jīng)是等于0了，因此它獲得的新的時(shí)間片就是NICE_TO_TICKS(p->nice)，也就是根據(jù)nice value計(jì)算得到的缺省時(shí)間片。對(duì)于掛入等待隊(duì)列中處于睡眠狀態(tài)的進(jìn)程而言，其時(shí)間片p->counter還有剩余，當(dāng)然會(huì)累積到進(jìn)程時(shí)間片配額中，這也算是對(duì)睡眠進(jìn)程的一種獎(jiǎng)勵(lì)吧。為了防止經(jīng)常睡眠的交互式進(jìn)程獲得過于龐大的時(shí)間片，這里并不是累積其全部存留時(shí)間片，而是打了個(gè)對(duì)折(p->counter >> 1)。

新的一個(gè)周期開始了，當(dāng)前進(jìn)程已經(jīng)在CPU上奔跑了，消耗其時(shí)間片的代碼位于timer中斷處理中，如下：

每一個(gè)tick到來(lái)的時(shí)候，進(jìn)程的時(shí)間片都會(huì)減一，當(dāng)時(shí)間片是0的時(shí)候，調(diào)度器剝奪其執(zhí)行的權(quán)力，從而從而引發(fā)一次調(diào)度，選擇其他時(shí)間片不是0的進(jìn)程運(yùn)行，直到runqueue中的所有進(jìn)程時(shí)間片耗盡，又會(huì)重新賦值，開始一個(gè)新的周期。調(diào)度器就這樣周而復(fù)始，推動(dòng)整個(gè)系統(tǒng)的運(yùn)作。

四、2.6時(shí)代的O（1）調(diào)度器

1、Why O（1）調(diào)度器

如果簡(jiǎn)單是判斷調(diào)度器好壞的唯一標(biāo)準(zhǔn)，那么無(wú)疑O（n）調(diào)度器是最優(yōu)秀的調(diào)度器。雖然它非常的簡(jiǎn)單，容易理解，但是存在嚴(yán)重的擴(kuò)展性問題和性能問題。下面讓我們一起來(lái)控訴O（n）調(diào)度器的“七宗罪”，同時(shí)這也是Ingo Molnar發(fā)起O（1）調(diào)度器項(xiàng)目背后的原因。

（1）算法復(fù)雜度問題

讓人最不爽的就是對(duì)runqueue隊(duì)列的遍歷，當(dāng)系統(tǒng)中runnable進(jìn)程不多的時(shí)候，遍歷鏈表的開銷還可以接受，但是隨著系統(tǒng)中runnable狀態(tài)的進(jìn)程數(shù)目增多，那么調(diào)度器select next的運(yùn)算量也隨之呈線性的增長(zhǎng)，這也是我們?yōu)槭裁唇兴麿（n）調(diào)度器的原因。

此外，調(diào)度周期結(jié)束后，調(diào)度器會(huì)為所有進(jìn)程的時(shí)間片進(jìn)行“充值“的動(dòng)作。在大型系統(tǒng)中，同時(shí)存在的進(jìn)程（包括睡眠的進(jìn)程）可能會(huì)有數(shù)千個(gè)，為每一個(gè)進(jìn)程計(jì)算其時(shí)間片的過程太耗費(fèi)時(shí)間。

（2）SMP擴(kuò)展性問題

2.4內(nèi)核的O（n）調(diào)度器有非常差的SMP擴(kuò)展性。我們知道，O（n）調(diào)度器是通過一個(gè)鏈表來(lái)管理系統(tǒng)中的所有的等待調(diào)度的進(jìn)程，訪問這個(gè)runqueue鏈表的場(chǎng)景很多：進(jìn)行調(diào)度的時(shí)候，我們需要遍歷runqueue，找到合適的next task；wakeup或者block進(jìn)程的時(shí)候，我們需要從runqueue中增加節(jié)點(diǎn)或者刪除節(jié)點(diǎn)……在訪問runqueue這個(gè)鏈表的時(shí)候，我們都會(huì)首先會(huì)上自旋鎖，同時(shí)disable本地CPU中斷，然后訪問鏈表執(zhí)行相應(yīng)的動(dòng)作，完成之后釋放鎖，開中斷。通過這樣的內(nèi)核同步機(jī)制，我們可以保證來(lái)自多個(gè)CPU對(duì)runqueue鏈表的并發(fā)訪問。當(dāng)系統(tǒng)中的CPU數(shù)目比較少的時(shí)候，自旋鎖的開銷還可以接受，但是在大型系統(tǒng)中，CPU數(shù)目非常多，這時(shí)候runqueue spin lock就成為系統(tǒng)的性能瓶頸。

（3）CPU空轉(zhuǎn)問題

每當(dāng)runqueue鏈表中的所有進(jìn)程耗盡了其時(shí)間片，這時(shí)候就需要啟動(dòng)對(duì)系統(tǒng)中所有進(jìn)程時(shí)間片重新計(jì)算的過程。這個(gè)計(jì)算過程異常丑陋，需要遍歷系統(tǒng)中的所有進(jìn)程（注意：是所有進(jìn)程！），為進(jìn)程描述符的counter成員賦一個(gè)新值。而這個(gè)操作足以把該CPU上的L1 cache全部干掉。當(dāng)完成了時(shí)間片重新計(jì)算過程后，你幾乎面對(duì)的就是一個(gè)全空的L1 cache（當(dāng)然不是全空，主要是cache中的數(shù)據(jù)沒有任何意義，這時(shí)候L1 cache的命中率急劇下降）。除此之外，時(shí)間片重新計(jì)算過程會(huì)帶來(lái)CPU資源的浪費(fèi)，我們用下面的圖片來(lái)描述：

在runqueue隊(duì)列中的全部進(jìn)程時(shí)間片被耗盡之前，系統(tǒng)總會(huì)處于這樣一個(gè)狀態(tài)：最后的一組尚存時(shí)間片的進(jìn)程分分別調(diào)度到各個(gè)CPU上去。我們以4個(gè)CPU為例，T0～T3分別運(yùn)行在CPU0~CPU3上。隨著系統(tǒng)的運(yùn)行，CPU2上的T2首先耗盡了其時(shí)間片，但是這時(shí)候，其實(shí)CPU2上也是無(wú)法進(jìn)行調(diào)度的，因?yàn)楸闅vrunqueue鏈表，找不到適合的進(jìn)程調(diào)度運(yùn)行，因此它只能是處于idle狀態(tài)。也許隨后T0和T3也耗盡其時(shí)間片，從而導(dǎo)致CPU0和CPU3也進(jìn)入了idle狀態(tài)。現(xiàn)在只剩下最后一個(gè)進(jìn)程T1仍然在CPU1上運(yùn)行，而其他系統(tǒng)中的處理器處于idle狀態(tài)，白白的浪費(fèi)資源。唯一能改變這個(gè)狀態(tài)的是T1耗盡其時(shí)間片，從而啟動(dòng)一個(gè)重新計(jì)算時(shí)間片的過程，這時(shí)候，正常的調(diào)度就可以恢復(fù)了。隨著系統(tǒng)中CPU數(shù)目的加大，資源浪費(fèi)會(huì)越來(lái)越嚴(yán)重。

（4）task bouncing issue

一般而言，一個(gè)進(jìn)程最好是從一而終，假如它運(yùn)行在系統(tǒng)中的某個(gè)CPU中，那么在其處于可運(yùn)行狀態(tài)的過程中，最好是一直保持在該CPU上運(yùn)行。不過在O（n）調(diào)度器下，很多人都反映有進(jìn)程在CPU之間跳來(lái)跳去的現(xiàn)象。其根本的原因也是和時(shí)間片算法相關(guān)。在一個(gè)新的周期開后，runqueue中的進(jìn)程時(shí)間片都是滿滿的，在各個(gè)CPU上調(diào)度進(jìn)程的時(shí)候，它可選擇的比較多，再加上調(diào)度器傾向于調(diào)度上次運(yùn)行在本CPU的進(jìn)程，因此調(diào)度器有很大的機(jī)會(huì)把上次運(yùn)行的進(jìn)程調(diào)度到同一個(gè)處理器上。但是隨著runqueue中的進(jìn)程一個(gè)個(gè)的耗盡其時(shí)間片，cpu可選擇的余地在不斷的壓縮，從而導(dǎo)致進(jìn)程執(zhí)行在一個(gè)和它親和性不大的處理器（例如上次該進(jìn)程運(yùn)行在CPU0，但是這個(gè)將其調(diào)度到CPU1執(zhí)行，但是實(shí)際上該進(jìn)程和CPU0的親和性更大些）。

（5）RT進(jìn)程調(diào)度性能問題

實(shí)時(shí)調(diào)度的性能一般。通過上一節(jié)的介紹，我們知道，實(shí)時(shí)進(jìn)程和普通進(jìn)程掛在一個(gè)鏈表中。當(dāng)調(diào)度實(shí)時(shí)進(jìn)程的時(shí)候，我們需要遍歷整個(gè)runqueue列表，掃描并計(jì)算所有進(jìn)程的調(diào)度指數(shù)，從而選擇出心儀的那個(gè)實(shí)時(shí)進(jìn)程。按理說(shuō)實(shí)時(shí)進(jìn)程和普通進(jìn)程位于不同的調(diào)度空間，兩不相干，但是現(xiàn)在調(diào)度實(shí)時(shí)進(jìn)程還需要掃描計(jì)算普通進(jìn)程，這樣糟糕的算法讓那些關(guān)注實(shí)時(shí)性的工程師不能忍受。

當(dāng)然，上面的這些還不是關(guān)鍵，最重要的是整個(gè)linux內(nèi)核不是搶占式內(nèi)核，在整個(gè)內(nèi)核態(tài)都不能被搶占。對(duì)于一些比較耗時(shí)（可能幾個(gè)毫秒）的系統(tǒng)調(diào)用或者中斷處理，必須返回用戶空間才啟動(dòng)調(diào)度是不可接受的。除了內(nèi)核搶占性之外，優(yōu)先級(jí)翻轉(zhuǎn)問題也需要引起調(diào)度器的重視，否則即便一個(gè)rt進(jìn)程變成runnable狀態(tài)了，但是也只能眼睜睜的看著比它優(yōu)先級(jí)低的進(jìn)程運(yùn)行，直到該rt進(jìn)程等待的資源被釋放。

（6）交互式普通進(jìn)程的調(diào)度延遲問題

O（n）并不區(qū)分交互式進(jìn)程和批處理進(jìn)程，它只是獎(jiǎng)勵(lì)經(jīng)常睡眠的那些進(jìn)程。但是有些批處理進(jìn)程也屬于IO-bound進(jìn)程，例如數(shù)據(jù)庫(kù)服務(wù)進(jìn)程，它本身是一個(gè)后臺(tái)進(jìn)程，對(duì)調(diào)度延遲不敏感，但是由于它需要和磁盤打交道，因此也會(huì)經(jīng)常阻塞在disk IO上。對(duì)這樣的后臺(tái)進(jìn)程進(jìn)行動(dòng)態(tài)優(yōu)先級(jí)的升高其實(shí)是沒有意義的，會(huì)增大其他交互式進(jìn)程的調(diào)度延遲。另外一方面，用戶交互式進(jìn)程也可能是CPU-bound的，而這時(shí)候調(diào)度器不會(huì)正確的了解到該進(jìn)程的調(diào)度需求并對(duì)其進(jìn)行補(bǔ)償。

（7）時(shí)間片粒度問題。

用戶感知到的響應(yīng)延遲是和系統(tǒng)負(fù)載相關(guān)，我們可以用runnable進(jìn)程數(shù)目來(lái)粗略的描述系統(tǒng)的負(fù)載。當(dāng)系統(tǒng)負(fù)載高的時(shí)候，runqueue中的進(jìn)程數(shù)目會(huì)比較多，一次調(diào)度周期的時(shí)間就會(huì)比較長(zhǎng)，例如在HZ=100的情況下，runqueue上有5個(gè)runnable進(jìn)程，nice value是0，每個(gè)時(shí)間片配額是60ms，那么一個(gè)調(diào)度周期就是300ms。隨著runnable進(jìn)程增大，調(diào)度周期也變大。當(dāng)一個(gè)進(jìn)程耗盡其時(shí)間片之后，只能等待下一個(gè)調(diào)度周期到來(lái)。因此隨著調(diào)度周期變大，系統(tǒng)響應(yīng)也會(huì)變的較差。

雖然O（n）調(diào)度器存在不少的issue，但是社區(qū)的人還是基本認(rèn)可這套算法的，因此在設(shè)計(jì)新的調(diào)度器的時(shí)候并不是完全推翻O（n）調(diào)度器的設(shè)計(jì)，而是針對(duì)O（n）調(diào)度器的問題進(jìn)行改進(jìn)。在本章中我們選擇2.6.11版本的內(nèi)核來(lái)描述O（1）調(diào)度器如何運(yùn)作。鑒于O（1）調(diào)度器和O（n）調(diào)度器沒有本質(zhì)區(qū)別，因此我們只是描述它們之間不同的地方。

2、O（1）調(diào)度器的軟件功能劃分

下圖是一個(gè)O（1）調(diào)度器的軟件框架：

O（n）調(diào)度器中只有一個(gè)全局的runqueue，嚴(yán)重影響了擴(kuò)展性，因此在O（1）調(diào)度器中引入了per-CPU runqueue的概念。系統(tǒng)中所有的可運(yùn)行狀態(tài)的進(jìn)程首先經(jīng)過負(fù)載均衡模塊掛入各個(gè)CPU的runqueue，然后由主調(diào)度器和tick調(diào)度器驅(qū)動(dòng)該CPU上的調(diào)度行為。由于篇幅的原因，我們?cè)诒疚闹胁恢v解負(fù)載均衡模塊，把重點(diǎn)放在單個(gè)CPU上的任務(wù)調(diào)度算法。

由于引入了per-CPU runqueue，O（1）調(diào)度器刪除了全局runqueue的spin lock，而是把這個(gè)spin lock放入到per-CPU runqueue數(shù)據(jù)結(jié)構(gòu)中（rq->lock），通過把一個(gè)大鎖細(xì)分成小鎖，可以大大降低調(diào)度延遲，提升系統(tǒng)響應(yīng)時(shí)間。這種方法在內(nèi)核中經(jīng)常使用，是一個(gè)比較通用的性能優(yōu)化方法。

通過上面的軟件結(jié)構(gòu)劃分可以解決O（n）調(diào)度的SMP擴(kuò)展性問題和CPU空轉(zhuǎn)問題。此外，好的復(fù)雜均衡算法也可以解決O（n）調(diào)度器的task bouncing 問題。

3、O（1）調(diào)度器的runqueue結(jié)構(gòu)

O（1）調(diào)度器的基本優(yōu)化思路就是把原來(lái)runqueue上的單鏈表變成多個(gè)鏈表，即每一個(gè)優(yōu)先級(jí)的進(jìn)程被掛入不同鏈表中。相關(guān)的軟件結(jié)構(gòu)可以參考下面的圖片：

在調(diào)度器中，runqueue是一個(gè)很重要的數(shù)據(jù)結(jié)構(gòu)，它最重要的作用是管理那些處于可運(yùn)行狀態(tài)的進(jìn)程。O（1）調(diào)度器引入了優(yōu)先級(jí)隊(duì)列的概念來(lái)管理task，具體由struct prio_array抽象：

由于支持140個(gè)優(yōu)先級(jí)，因此queue成員中有140個(gè)分別表示各個(gè)優(yōu)先級(jí)的鏈表頭，不同優(yōu)先級(jí)的進(jìn)程掛入不同的鏈表中。bitmap 是表示各個(gè)優(yōu)先級(jí)進(jìn)程鏈表是空還是非空。nr_active表示這個(gè)隊(duì)列中有多少個(gè)task。在這些隊(duì)列中，100～139是普通進(jìn)程的優(yōu)先級(jí)，其他的是實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)。因此，在O（1）調(diào)度器中，RT進(jìn)程和普通進(jìn)程被區(qū)分開了，普通進(jìn)程根本不會(huì)影響RT進(jìn)程的調(diào)度。

Runqueue中有兩個(gè)優(yōu)先級(jí)隊(duì)列（struct prio_array）分別用來(lái)管理active（即時(shí)間片還有剩余）和expired（時(shí)間片耗盡）的進(jìn)程。Runqueue中有兩個(gè)優(yōu)先級(jí)隊(duì)列的指針，分別指向這兩個(gè)優(yōu)先級(jí)隊(duì)列。隨著系統(tǒng)的運(yùn)行，active隊(duì)列的task一個(gè)個(gè)的耗盡其時(shí)間片，掛入到expired隊(duì)列。當(dāng)active隊(duì)列的task為空的時(shí)候，切換active和expired隊(duì)列，開始一輪新的調(diào)度過程。

雖然在O（1）調(diào)度器中task組織的形式發(fā)生了變化，但是其核心思想仍然和O（n）調(diào)度器一致的，都是把CPU資源分成一個(gè)個(gè)的時(shí)間片，分配給每一個(gè)runnable的進(jìn)程。進(jìn)程用完其額度后被搶占，等待下一個(gè)調(diào)度周期的到來(lái)。

4、核心調(diào)度算法

主調(diào)度器（就是schedule函數(shù)）的主要功能是從該CPU的runqueue找到一個(gè)最合適的進(jìn)程調(diào)度執(zhí)行。其基本的思路就是從active優(yōu)先級(jí)隊(duì)列中尋找，代碼如下：

首先在當(dāng)前active優(yōu)先級(jí)隊(duì)列的bitmap尋找第一個(gè)非空的進(jìn)程鏈表，然后從該鏈表中找到的第一個(gè)節(jié)點(diǎn)就是最適合下一個(gè)調(diào)度執(zhí)行的進(jìn)程。由于沒有遍歷整個(gè)鏈表的操作，因此這個(gè)調(diào)度器的算法復(fù)雜度是一個(gè)常量，從而解決了O（n）算法復(fù)雜度的issue。

如果當(dāng)前active優(yōu)先級(jí)隊(duì)列中“空無(wú)一人”（nr_active等于0），那么這時(shí)候就需要切換active和expired優(yōu)先級(jí)隊(duì)列了：

切換很快，并沒有一個(gè)遍歷所有進(jìn)程重新賦default時(shí)間片的操作（大大縮減了runqueue臨界區(qū)的size）。這些都避免了O（n）調(diào)度器帶來(lái)的種種問題，從而提高了調(diào)度器的性能。

5、靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)

在前面的小節(jié)中，我們有意的忽略了優(yōu)先級(jí)隊(duì)列中“優(yōu)先級(jí)”的具體含義，現(xiàn)在是需要澄清的時(shí)候了。其實(shí)優(yōu)先級(jí)隊(duì)列中“優(yōu)先級(jí)”指的是動(dòng)態(tài)優(yōu)先級(jí)，從這個(gè)角度看，O（1）和O（n）調(diào)度器的調(diào)度算法又統(tǒng)一了，都是根據(jù)動(dòng)態(tài)優(yōu)先級(jí)進(jìn)行調(diào)度。

O（1）的靜態(tài)優(yōu)先級(jí)的概念和O（n）是類似的，對(duì)于實(shí)時(shí)進(jìn)程保存在進(jìn)程描述符的rt_priority成員中，取值范圍是1（優(yōu)先級(jí)最低）～99（優(yōu)先級(jí)最高）。對(duì)于普通進(jìn)程，靜態(tài)優(yōu)先級(jí)則保存在static_prio成員中，取值范圍是100（優(yōu)先級(jí)最高）～139（優(yōu)先級(jí)最低），分別對(duì)應(yīng)nice value的-20 ～ 19。

了解了靜態(tài)優(yōu)先級(jí)之后，我們一起來(lái)看看動(dòng)態(tài)優(yōu)先級(jí)（保存在進(jìn)程描述符的prio成員中）。鑒于在實(shí)際調(diào)度的時(shí)候使用的是動(dòng)態(tài)優(yōu)先級(jí)，我們必須要保證它是單調(diào)的（靜態(tài)優(yōu)先級(jí)未能保持單調(diào)，rt的99和普通進(jìn)程的100都是靜態(tài)優(yōu)先級(jí)的最高點(diǎn)，也就是說(shuō)在靜態(tài)優(yōu)先級(jí)數(shù)軸上，rt段是單調(diào)上升，而在普通進(jìn)程段是單調(diào)下降的）。為了解決這個(gè)問題，在計(jì)算實(shí)時(shí)進(jìn)程動(dòng)態(tài)優(yōu)先級(jí)的時(shí)候進(jìn)行了一個(gè)簡(jiǎn)單的映射：

通過這樣的轉(zhuǎn)換，rt的動(dòng)態(tài)優(yōu)先級(jí)在數(shù)軸上也是單調(diào)下降的了。普通進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)計(jì)算沒有那么簡(jiǎn)單，除了靜態(tài)優(yōu)先級(jí)，還需要考慮進(jìn)程的平均睡眠時(shí)間（保存在進(jìn)程描述符的sleep_avg成員中），并根據(jù)該值對(duì)進(jìn)程進(jìn)行獎(jiǎng)懲。具體代碼可以參考effective_prio函數(shù)，這里不再詳述，最終普通進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)是100（優(yōu)先級(jí)最高）～139（優(yōu)先級(jí)最低），和靜態(tài)優(yōu)先級(jí)的取值范圍是一致的。

在本小節(jié)的最后，我們一起來(lái)對(duì)比普通進(jìn)程在O（1）和O（n）調(diào)度器的動(dòng)態(tài)優(yōu)先級(jí)算法。這個(gè)兩個(gè)調(diào)度器的基本思路是一致的：考慮靜態(tài)優(yōu)先級(jí)，輔以對(duì)該進(jìn)程的“用戶交互指數(shù)”的評(píng)估，用戶交互指數(shù)高的，調(diào)升其動(dòng)態(tài)優(yōu)先級(jí)，反之則降低。不過在評(píng)估用戶交互指數(shù)上，O（1）顯然做的更好。O（n）調(diào)度器僅僅考慮了睡眠進(jìn)程的剩余時(shí)間片，而O（1）的“平均睡眠時(shí)間”算法顯然考慮更多的因素：在cpu上的執(zhí)行時(shí)間、在runqueue中的等待時(shí)間、睡眠時(shí)間、睡眠時(shí)候的進(jìn)程狀態(tài)（是否可被信號(hào)打斷），什么上下文喚醒（中斷上下文喚醒還是在進(jìn)程上下文中喚醒）……因此O（1）調(diào)度器更好的判斷了進(jìn)程是屬于interactive process還是batch process，從而精準(zhǔn)的為interactive process打call。

6、時(shí)間片處理

缺省時(shí)間片的計(jì)算是通過task_timeslice完成的，在O（1）調(diào)度器中，缺省時(shí)間片已經(jīng)和HZ無(wú)關(guān)了，無(wú)論如何設(shè)置HZ，靜態(tài)優(yōu)先級(jí)為[ -20 ... 0 ... 19 ]的普通進(jìn)程其缺省時(shí)間片為[800ms ... 100ms ... 5ms]。

在tick到來(lái)的時(shí)候，當(dāng)前task的時(shí)間片會(huì)遞減（--p->time_slice），當(dāng)時(shí)間片等于0的時(shí)候，會(huì)將該task從active優(yōu)先級(jí)列表中摘下，設(shè)定resched標(biāo)記，并且重置時(shí)間片，代碼如下：

task_timeslice函數(shù)就是用來(lái)計(jì)算進(jìn)程時(shí)間片的配額的。對(duì)于O（1）調(diào)度器，時(shí)間片的重新賦值是分散處理的，在各個(gè)task耗盡其時(shí)間片之后立刻進(jìn)行的。這樣的改動(dòng)也修正了O（n）調(diào)度器一次性的遍歷系統(tǒng)所有進(jìn)程，重新為時(shí)間片賦值的過程。

6、識(shí)別用戶交互式進(jìn)程

一般而言，時(shí)間片耗盡之后，該task會(huì)被掛入到expired優(yōu)先級(jí)隊(duì)列，這時(shí)候如果想要被調(diào)度只能等到下次active和expired切換了。不過，有些特殊的場(chǎng)景需要特殊處理：

這里TASK_INTERACTIVE是用來(lái)判斷一個(gè)進(jìn)程是否是一個(gè)用戶交互式進(jìn)程（也是和平均睡眠時(shí)間相關(guān)，由此可見，平均睡眠時(shí)間不僅用于計(jì)算動(dòng)態(tài)優(yōu)先級(jí)，還用來(lái)決定一個(gè)進(jìn)程是否回插入active隊(duì)列），如果是的話，說(shuō)明該進(jìn)程對(duì)用戶響應(yīng)比較敏感，這時(shí)候不能粗暴的掛入expired隊(duì)列，而是重新掛入active隊(duì)列，繼續(xù)有機(jī)會(huì)獲取調(diào)度執(zhí)行的機(jī)會(huì)。由此可見，O（1）調(diào)度器真是對(duì)用戶交互式進(jìn)程非常的照顧，一旦被判斷是用戶交互型進(jìn)程，那么它將獲取連續(xù)執(zhí)行的機(jī)會(huì)。當(dāng)然，調(diào)度器也不能太過分，如果用戶交互型進(jìn)程持續(xù)占用CPU，那么在expired隊(duì)列中苦苦等待進(jìn)程怎么辦？這時(shí)候就要看看expired隊(duì)列中的進(jìn)程的饑餓狀態(tài)了，這也就是EXPIRED_STARVING這個(gè)宏定義的功能。如果expired隊(duì)列中的進(jìn)程等待了太長(zhǎng)的時(shí)間，那么說(shuō)明調(diào)度器已經(jīng)出現(xiàn)嚴(yán)重不公平的現(xiàn)象，因此這時(shí)候即便是判斷當(dāng)前耗盡時(shí)間片的進(jìn)程是用戶交互型進(jìn)程，也把它掛入expired隊(duì)列，盡快的完成本次調(diào)度周期，讓active和expired發(fā)生切換。

O（1）調(diào)度器使用非常復(fù)雜的算法來(lái)判斷進(jìn)程的用戶交互指數(shù)以及進(jìn)程是否是交互式進(jìn)程，hardcode了很多的不知其所以然的常數(shù)，估計(jì)也是通過各種大量的實(shí)驗(yàn)場(chǎng)景總結(jié)出來(lái)的。這部分的設(shè)計(jì)概念我是在是沒有勇氣去探索，因此這里就略過了。但是無(wú)論如何，它總是比僅僅考慮睡眠時(shí)間的O（n）調(diào)度器性能要好。

7、搶占式內(nèi)核

2.4時(shí)代，大部分的Linux應(yīng)用都集中在服務(wù)器領(lǐng)域，因此非搶占式內(nèi)核的設(shè)計(jì)選擇也無(wú)可厚非。不過隨著Linux在桌面和嵌入式上的滲透，系統(tǒng)響應(yīng)慢慢的稱為用戶投訴的主要方面，因此，在2.5的開發(fā)過程中，Linux引入了搶占式內(nèi)核的概念（CONFIG_PREEMPT），如果沒有配置該選項(xiàng)，那么一切和2.4內(nèi)核保持一致，如果配置了該選項(xiàng)，那么不需要在返回用戶空間的時(shí)候才苦苦等到調(diào)度點(diǎn)，大部分的內(nèi)核執(zhí)行路徑都是可以被搶占的。同樣的，限于篇幅，這里不再展開描述。

五、公平調(diào)度思想的引入

1、傳統(tǒng)調(diào)度器時(shí)間片悖論

在O（n）和O（1）調(diào)度器中，時(shí)間片是固定分配的，靜態(tài)優(yōu)先級(jí)高的進(jìn)程獲取更大的time slice。例如nice value等于20的進(jìn)程獲取的default timeslice是5ms，而nice value等于0的進(jìn)程獲取的是100ms。直觀上，這樣的策略沒有毛病（高優(yōu)先級(jí)的獲取更多的執(zhí)行時(shí)間），但是，這樣的設(shè)定潛臺(tái)詞就是：高優(yōu)先級(jí)的進(jìn)程會(huì)獲得更多的連續(xù)執(zhí)行的機(jī)會(huì)，這是CPU-bound進(jìn)程期望的，但是實(shí)際上，CPU-bound進(jìn)程往往在后臺(tái)執(zhí)行，其優(yōu)先級(jí)都是比較低的。

因此，假設(shè)我們調(diào)度策略就是根據(jù)進(jìn)程靜態(tài)優(yōu)先級(jí)確定一個(gè)固定大小的時(shí)間片，這時(shí)候我們?cè)谌绾畏峙鋾r(shí)間片上會(huì)遇到兩難的狀況：想要給用戶交互型進(jìn)程設(shè)定高優(yōu)先級(jí)，以便它能有更好的用戶體驗(yàn)，但是分配一個(gè)大的時(shí)間片是毫無(wú)意義的，因?yàn)檫@種進(jìn)程多半是處于阻塞態(tài)，等待用戶的輸入。而后臺(tái)進(jìn)程的優(yōu)先級(jí)一般不高，但是根據(jù)其優(yōu)先級(jí)分配一個(gè)較小的時(shí)間片往往會(huì)影響其性能，這種類型的進(jìn)程最好是趁著cache hot的時(shí)候狂奔。

怎么辦？或者傳統(tǒng)調(diào)度器固定分配時(shí)間片這個(gè)設(shè)計(jì)概念就是錯(cuò)誤的。

2、傳統(tǒng)調(diào)度器的卡頓問題

在Linux 2.5版本的開發(fā)過程中，Ingo Molnar設(shè)計(jì)的O（1）調(diào)度器替換掉了原始的、簡(jiǎn)陋的O（n）調(diào)度器，從而解決了擴(kuò)展性很差，性能不佳的問題。在大部分的場(chǎng)景中，該調(diào)度器都獲得了滿意的性能，在商用的Linux 2.4發(fā)行版中，O（1）調(diào)度器被很多廠商反向移植到Linux 2.4中，由此可見O（1）調(diào)度器性能還是優(yōu)異的。

然而O（1）并非完美，在實(shí)際的使用過程中，還是有不少的桌面用戶在抱怨用戶交互性比較差。當(dāng)一個(gè)相當(dāng)消耗CPU資源的進(jìn)程啟動(dòng)的時(shí)候，現(xiàn)存的那些用戶交互程序（例如你在通過瀏覽器查看網(wǎng)頁(yè)）都可以感覺到明顯的延遲。針對(duì)這些issue，很多天才工程師試圖通過對(duì)用戶交互指數(shù)算法的的修改來(lái)解決問題，這里面就包括公平調(diào)度思想的提出者Con Kolivas。不過無(wú)論如何調(diào)整算法，總是有點(diǎn)拆東墻補(bǔ)西墻的感覺，一個(gè)場(chǎng)景的issue修復(fù)了，另外一個(gè)場(chǎng)景又冒出來(lái)交互性不好的issue，刁鉆的客戶總是能夠在邊邊角角的場(chǎng)景中找到讓用戶感覺到的響應(yīng)延遲。

在反反復(fù)復(fù)修復(fù)用戶卡頓issue的過程中，工程師最容易煩躁，而往往這時(shí)候最需要冷靜的思考。Con Kolivas仔細(xì)的檢視了調(diào)度器代碼，他發(fā)現(xiàn)出問題的是評(píng)估進(jìn)程用戶交互指數(shù)的代碼。為何調(diào)度器要根據(jù)進(jìn)程的行為猜測(cè)其對(duì)交互性的需求？這根本是一項(xiàng)不可能完成的任務(wù)，因?yàn)槟憧偸遣粫?huì)100％全部猜中，就好像你去猜測(cè)你喜歡的女孩子的心事一樣，你細(xì)心的收集了關(guān)于這個(gè)女孩子的性格特點(diǎn)，業(yè)余愛好，做事風(fēng)格，邏輯思維水平，星座……甚至生理周期，并期望著能總是正確的猜中其心中所想，坦率的講這是不可能的。在進(jìn)程調(diào)度這件事情上為何不能根據(jù)實(shí)實(shí)在在確定的東西來(lái)調(diào)度呢？一個(gè)進(jìn)程的靜態(tài)優(yōu)先級(jí)已經(jīng)完成的說(shuō)明了其調(diào)度需求了，這就足夠了，不需要猜測(cè)進(jìn)程對(duì)交互性的需求，只要維持公平就OK了，而所謂的公平就是進(jìn)程獲取和其靜態(tài)優(yōu)先級(jí)匹配的CPU執(zhí)行時(shí)間。在這樣的思想指導(dǎo)下，Con Kolivas提出了RSDL（Rotating Staircase Deadline）調(diào)度器。

3、RSDL調(diào)度器

RSDL調(diào)度器仍然沿用了O（1）調(diào)度的數(shù)據(jù)結(jié)構(gòu)和軟件結(jié)構(gòu)，當(dāng)然刪除了那些令人毛骨悚然的評(píng)估進(jìn)程交互指數(shù)的代碼。我們這一小節(jié)不可能詳細(xì)描述RSDL算法，不過只要講清楚Rotating、Staircase和Deadline這三個(gè)基本概念，大家就應(yīng)該對(duì)RSDL有基本的了解了。

首先看Staircase概念，它更詳細(xì)表述應(yīng)該是priority staircase，即在進(jìn)程調(diào)度過程中，其優(yōu)先級(jí)會(huì)象下樓梯那樣一點(diǎn)點(diǎn)的降低。在傳統(tǒng)的調(diào)度概念中，一個(gè)進(jìn)程有一個(gè)和其靜態(tài)優(yōu)先級(jí)相匹配的時(shí)間片，在RSDL中，同樣也存在這樣的時(shí)間片，但是時(shí)間片是散布在很多優(yōu)先級(jí)中。例如如果一個(gè)進(jìn)程的優(yōu)先級(jí)是120，那么整個(gè)時(shí)間片散布在120～139的優(yōu)先級(jí)中，在一個(gè)調(diào)度周期，進(jìn)程開始是掛入120的優(yōu)先級(jí)隊(duì)列，并在其上運(yùn)行6ms（這是一個(gè)可調(diào)參數(shù)，我們假設(shè)每個(gè)優(yōu)先級(jí)的時(shí)間配額是6ms），一旦在120級(jí)別的時(shí)間配額使用完畢之后，該進(jìn)程會(huì)轉(zhuǎn)入121的隊(duì)列中（優(yōu)先級(jí)降低一個(gè)level），發(fā)生一次Rotating，更準(zhǔn)確的說(shuō)是Priority minor rotating。之后，該進(jìn)程沿階而下，直到139的優(yōu)先級(jí)，在這個(gè)優(yōu)先級(jí)上如果耗盡了6ms的時(shí)間片，這時(shí)候，該進(jìn)程所有的時(shí)間片就都耗盡了，就會(huì)被掛入到expired隊(duì)列中去等待下一個(gè)調(diào)度周期。這次rotating被稱為major rotating。當(dāng)然，這時(shí)候該進(jìn)程會(huì)掛入其靜態(tài)優(yōu)先級(jí)對(duì)應(yīng)的expired隊(duì)列，即一切又回到了調(diào)度的起點(diǎn)。

Deadline是指在RSDL算法中，任何一個(gè)進(jìn)程可以準(zhǔn)確的預(yù)估其調(diào)度延遲。一個(gè)簡(jiǎn)單的例子，假設(shè)runqueue中有兩個(gè)task，靜態(tài)優(yōu)先級(jí)分別是130的A進(jìn)程和139的B進(jìn)程。對(duì)于A進(jìn)程，只有在進(jìn)程沿著優(yōu)先級(jí)樓梯從130走到139的時(shí)候，B進(jìn)程才有機(jī)會(huì)執(zhí)行，其調(diào)度延遲是9 x 6ms ＝ 54ms。

多么簡(jiǎn)潔的算法，只需要維持公平，沒有對(duì)進(jìn)程睡眠/運(yùn)行時(shí)間的統(tǒng)計(jì)，沒有對(duì)用戶交互指數(shù)的計(jì)算，沒有那些奇奇怪怪的常數(shù)……調(diào)度，就是這么簡(jiǎn)單。

六、CFS調(diào)度器

Con Kolivas的RSDL調(diào)度器始終沒有能夠進(jìn)入kernel mainline，取而代之的是同樣基于公平調(diào)度思想的CFS調(diào)度器，在CFS調(diào)度器并入主線的同時(shí)，仍然提供了模塊化的設(shè)計(jì)，為RSDL或者其他的調(diào)度器可以進(jìn)入內(nèi)核提供了方便。然而Con Kolivas帶著對(duì)內(nèi)核開發(fā)模式的不滿永遠(yuǎn)的退出了社區(qū)，正所謂有人的地方就有江湖，其中的是非留給后人評(píng)說(shuō)吧。

CFS的設(shè)計(jì)理念就是一句話：在真實(shí)的硬件上實(shí)現(xiàn)理想的、精準(zhǔn)、完全公平的多任務(wù)調(diào)度。當(dāng)然，這樣的調(diào)度器不存在，在實(shí)際設(shè)計(jì)和實(shí)現(xiàn)的時(shí)候還是需要做一些折衷。其實(shí)CFS調(diào)度器的所有的設(shè)計(jì)思想在上一章都已經(jīng)非常明晰，本章我們唯一需要描述的是Ingo Molnar如何把完全公平調(diào)度的理想照進(jìn)現(xiàn)實(shí)。

1、模塊化思想的引入

從2.6.23內(nèi)核開始，調(diào)度器采用了模塊化設(shè)計(jì)的思想，從而把進(jìn)程調(diào)度的軟件分成了兩個(gè)層次，一個(gè)是core scheduler layer，另外一個(gè)是specific scheduler layer：

從功能層面上看，進(jìn)程調(diào)度仍然分成兩個(gè)部分，第一個(gè)部分是通過負(fù)載均衡模塊將各個(gè)runnable task根據(jù)負(fù)載情況平均分配到各個(gè)CPU runqueue上去。第二部分的功能是在各個(gè)CPU的Main scheduler和Tick scheduler的驅(qū)動(dòng)下進(jìn)行單個(gè)CPU上的調(diào)度。調(diào)度器處理的task各不相同，有RT task，有normal task，有Deal line task，但是無(wú)論哪一種task，它們都有共同的邏輯，這部分被抽象成Core scheduler layer，同時(shí)各種特定類型的調(diào)度器定義自己的sched_class，并以鏈表的形式加入到系統(tǒng)中。這樣的模塊化設(shè)計(jì)可以方便用戶根據(jù)自己的場(chǎng)景定義specific scheduler，而不需要改動(dòng)Core scheduler layer的邏輯。

2、關(guān)于公平

和RSDL調(diào)度器一樣，CFS調(diào)度器追求的公平是CPU資源分配的公平，即CPU的運(yùn)算資源被精準(zhǔn)的平均分配給在其上運(yùn)行的task。例如：如果有2個(gè)靜態(tài)優(yōu)先級(jí)一樣的task運(yùn)行在某一個(gè)CPU上，那么每一個(gè)task都消耗50％的CPU計(jì)算資源。如果靜態(tài)優(yōu)先級(jí)不一樣，那么，CPU資源是根據(jù)其靜態(tài)優(yōu)先級(jí)來(lái)具體分配。具體如何根據(jù)優(yōu)先級(jí)來(lái)分配CPU資源呢？這里就需要引入一個(gè)load weight的概念。

在CFS中，我們是通過一個(gè)常量數(shù)組（sched_prio_to_weight）可以把進(jìn)程靜態(tài)優(yōu)先級(jí)映射成進(jìn)程權(quán)重，而所謂的權(quán)重就是進(jìn)程應(yīng)該占有cpu資源的比重。例如：系統(tǒng)中有3個(gè)runnable thread A、B和C，權(quán)重分別是a、b、c，那么A thread應(yīng)該分配到的CPU資源是a/(a+b+c)。因此CFS調(diào)度器的公平就是保證所有的可運(yùn)行狀態(tài)的進(jìn)程按照權(quán)重分配其CPU資源。

3、時(shí)間粒度

CPU資源分配是一個(gè)抽象的概念，最終在實(shí)現(xiàn)調(diào)度器的時(shí)候，我們需要把它具體化。一個(gè)最簡(jiǎn)單的方法就是把CPU資源的分配變成CPU時(shí)間片的分配?？吹健皶r(shí)間片”這個(gè)術(shù)語(yǔ)，你可能本能的覺得CFS和O（1）也沒有什么不同，不都是分配時(shí)間片嗎？其實(shí)不然，Linux內(nèi)核的CFS調(diào)度器已經(jīng)摒棄了傳統(tǒng)的固定時(shí)間片的概念了。O（1）調(diào)度器會(huì)為每一個(gè)進(jìn)程分配一個(gè)缺省的時(shí)間片，當(dāng)進(jìn)程使用完自己的時(shí)間片之后就會(huì)被掛入expire隊(duì)列，當(dāng)系統(tǒng)中的所有進(jìn)程都耗光了自己的時(shí)間片，那么一切從來(lái)，所有的進(jìn)程又恢復(fù)了自己的時(shí)間片，進(jìn)入active隊(duì)列。CFS調(diào)度器沒有傳統(tǒng)的靜態(tài)時(shí)間片的概念，她的時(shí)間片是動(dòng)態(tài)的，和當(dāng)前CPU的可運(yùn)行狀態(tài)的進(jìn)程以及它們的優(yōu)先級(jí)相關(guān)，因此CFS調(diào)度器中，時(shí)間片是動(dòng)態(tài)變化的。

對(duì)于理想的完全公平調(diào)度算法，無(wú)論觀察的時(shí)間段多么短，CPU的時(shí)間片都是公平分配的。以100ms的粒度來(lái)觀察，那么兩個(gè)可運(yùn)行狀態(tài)的進(jìn)程A和B（靜態(tài)優(yōu)先級(jí)一樣）各分50ms。當(dāng)然，也不是一定是A執(zhí)行50ms，切換到B，然后再執(zhí)行50ms，在觀察過程中，A和B可能切換了很多次，但是A進(jìn)程總共占用CPU的時(shí)間和就是50ms，B進(jìn)程亦然。如果用1ms的粒度來(lái)觀察呢？是否A和B個(gè)運(yùn)行500us？如果繼續(xù)縮減觀察時(shí)間，在一個(gè)微秒的時(shí)間段觀察呢？顯然，不太可能每個(gè)進(jìn)程運(yùn)行500ns，如果那樣的話，CPU的時(shí)間大量的消耗在了進(jìn)程切換上，真正做事情的CPU時(shí)間變得越來(lái)越少了。因此，CFS調(diào)度器是有一個(gè)時(shí)間粒度的定義，我們稱之調(diào)度周期。也就是說(shuō)，在一個(gè)調(diào)度周期內(nèi)，CFS調(diào)度器可以保證所有的可運(yùn)行狀態(tài)的進(jìn)程平均分配CPU時(shí)間。下一小節(jié)我們會(huì)詳細(xì)描述調(diào)度周期的概念。

4、如何保證有界的調(diào)度延遲？

傳統(tǒng)的調(diào)度器無(wú)法保證調(diào)度延遲，為了說(shuō)明這個(gè)問題我們?cè)O(shè)想這樣一個(gè)場(chǎng)景：CPU runqueue中有兩個(gè)nice value等于0的runnable進(jìn)程A和B，傳統(tǒng)調(diào)度器會(huì)為每一個(gè)進(jìn)程分配一個(gè)固定的時(shí)間片100ms，這時(shí)候A先運(yùn)行，直到100ms的時(shí)間片耗盡，然后B運(yùn)行。這兩個(gè)進(jìn)程會(huì)交替運(yùn)行，調(diào)度延遲就是100ms。隨著系統(tǒng)負(fù)荷的加重，例如又有兩個(gè)兩個(gè)nice value等于0的runnable進(jìn)程C和D掛入runqueue，這時(shí)候，A、B、C、D交替運(yùn)行，調(diào)度延遲就是300ms。因此，傳統(tǒng)調(diào)度器的調(diào)度延遲是和系統(tǒng)負(fù)載相關(guān)的，當(dāng)系統(tǒng)負(fù)載增加的時(shí)候，用戶更容易觀察到卡頓現(xiàn)象。

CFS調(diào)度器設(shè)計(jì)之初就確定了調(diào)度延遲的參數(shù)，我們稱之targeted latency，這個(gè)概念類似傳統(tǒng)調(diào)度器中的調(diào)度周期的概念，只不過在過去，一個(gè)調(diào)度周期中的時(shí)間片被固定分配給了runnable的進(jìn)程，而在CFS中，調(diào)度器會(huì)不斷的檢查在一個(gè)targeted latency中，公平性是否得到了保證。下面的代碼說(shuō)明了targeted latency的計(jì)算過程：

當(dāng)runqueue中的runnable進(jìn)程的數(shù)目小于sched_nr_latency（8個(gè)）的時(shí)候，targeted latency就是sysctl_sched_latency（6ms），當(dāng)runqueue中的runnable進(jìn)程的數(shù)目大于等于sched_nr_latency的時(shí)候，targeted latency等于runnable進(jìn)程數(shù)目乘以sysctl_sched_min_granularity（0.75ms）。顯然sysctl_sched_min_granularity這個(gè)參數(shù)就是一段一個(gè)進(jìn)程被調(diào)度執(zhí)行，它需要至少執(zhí)行的時(shí)間片大小，設(shè)立這個(gè)參數(shù)是為了防止overscheduling而產(chǎn)生的性能下降。

CFS調(diào)度器保證了在一個(gè)targeted latency中，所有的runnable進(jìn)程都會(huì)至少執(zhí)行一次，從而保證了有界的、可預(yù)測(cè)的調(diào)度延遲。

5、為何引入虛擬時(shí)間？

雖然Con Kolivas提出了精采絕倫的設(shè)計(jì)思想，但是在具體實(shí)現(xiàn)的時(shí)候相對(duì)保守。CFS調(diào)度器則不然，它采用了相對(duì)激進(jìn)的方法，把runqueue中管理task的優(yōu)先級(jí)鏈表變成了紅黑樹結(jié)構(gòu)。有了這樣一顆runnable進(jìn)程的紅黑樹，在插入操作的時(shí)候如何確定進(jìn)程在紅黑樹中的位置？也就是說(shuō)這棵樹的“key”是什么？

CFS的紅黑樹使用vruntime（virtual runtime）作為key，為了理解vruntime，這里需要引入一個(gè)虛擬時(shí)間軸的概念。在上一章中，我們已經(jīng)清楚的表述了公平的含義：按照進(jìn)程的靜態(tài)優(yōu)先級(jí)來(lái)分配CPU資源，當(dāng)然，CPU資源也就是CPU的時(shí)間片，因此在物理世界中，公平就是分配和靜態(tài)優(yōu)先級(jí)匹配的CPU時(shí)間片。但是紅黑樹需要一個(gè)單一數(shù)軸上的量進(jìn)行比對(duì)，而這里有兩個(gè)度量因素：靜態(tài)優(yōu)先級(jí)和物理時(shí)間片，因此我們需要把它們映射到一個(gè)虛擬的時(shí)間軸上，屏蔽掉靜態(tài)優(yōu)先級(jí)的影響，具體的計(jì)算公式如下：

Virtual runtime ＝ （physical runtime） X （nice value 0的權(quán)重）/進(jìn)程的權(quán)重

通過上面的公式，我們構(gòu)造了一個(gè)虛擬的世界。二維的（load weight，physical runtime）物理世界變成了一維的virtual runtime的虛擬世界。在這個(gè)虛擬的世界中，各個(gè)進(jìn)程的vruntime可以比較大小，以便確定其在紅黑樹中的位置，而CFS調(diào)度器的公平也就是維護(hù)虛擬世界vruntime的公平，即各個(gè)進(jìn)程的vruntime是相等的。

根據(jù)上面的公式，我們可以看出：實(shí)際上對(duì)于靜態(tài)優(yōu)先級(jí)是120（即nice value等于0）的進(jìn)程，其物理時(shí)間軸等于虛擬時(shí)間軸，而其他的靜態(tài)優(yōu)先級(jí)的虛擬時(shí)間都是根據(jù)其權(quán)重和nice 0的權(quán)重進(jìn)行尺度縮放。對(duì)于更高優(yōu)先級(jí)的進(jìn)程，其虛擬時(shí)間軸過的比較慢，而對(duì)于優(yōu)先級(jí)比較低的進(jìn)程，其虛擬時(shí)間軸過的比較快。

我們可以舉一個(gè)簡(jiǎn)單的例子來(lái)描述虛擬世界的公平性：例如在時(shí)間點(diǎn)a到b之間（虛擬時(shí)間軸），如果有兩個(gè)可運(yùn)行狀態(tài)的進(jìn)程A和B，那么從a到b這個(gè)時(shí)間段上去觀察，CPU的時(shí)間是平均分配到每個(gè)一個(gè)進(jìn)程上，也就是說(shuō)A和B進(jìn)程各自運(yùn)行了（b-a）/2的時(shí)間，也就是各占50％的時(shí)間片。在b時(shí)間點(diǎn)，一個(gè)新的可運(yùn)行狀態(tài)的進(jìn)程C產(chǎn)生了，直到c時(shí)間點(diǎn)。那么從b到c這個(gè)時(shí)間段上去觀察，進(jìn)程A、B和進(jìn)程C都是執(zhí)行了（c-b）/3的時(shí)間，也就是各占1/3的CPU資源。再?gòu)?qiáng)調(diào)一次，上面說(shuō)的時(shí)間都是虛擬時(shí)間。

6、如何計(jì)算virtual runtime

想要計(jì)算時(shí)間我們必須有類似手表這樣的計(jì)時(shí)工具，對(duì)于CFS調(diào)度器，這個(gè)“手表”保存在runqueue中（clock和clock_task成員）。Runqueue戴兩塊表，一塊記錄實(shí)際的物理時(shí)間，另外一塊則是記錄執(zhí)行task的時(shí)間（clock_task）。之所以有clock_task是為了更準(zhǔn)確的記錄進(jìn)程執(zhí)行時(shí)間。實(shí)際上一個(gè)task執(zhí)行過程中不免會(huì)遇到一些異步事件，例如中斷。這時(shí)候，進(jìn)程的執(zhí)行被打斷從而轉(zhuǎn)入到對(duì)異步事件的處理過程。如果把這些時(shí)間也算入該進(jìn)程的執(zhí)行時(shí)間會(huì)有失偏頗，因此clock_task會(huì)把這些異步事件的處理時(shí)間去掉，只有在真正執(zhí)行任務(wù)的時(shí)候，clock_task的counter才會(huì)不斷累加計(jì)時(shí)。

有了clock進(jìn)程計(jì)時(shí)變得比較簡(jiǎn)單了，當(dāng)進(jìn)程進(jìn)入執(zhí)行狀態(tài)的時(shí)候，看一下clock_task這塊“手表”，記錄數(shù)值為A。在需要統(tǒng)計(jì)運(yùn)行時(shí)間的時(shí)候，再次看一下clock_task這塊“手表”，記錄數(shù)值為B。B-A就是該進(jìn)程已經(jīng)運(yùn)行的物理時(shí)間。當(dāng)然，CFS關(guān)心的是虛擬時(shí)間，這時(shí)候還需要通過calc_delta_fair函數(shù)將這個(gè)物理時(shí)間轉(zhuǎn)換成虛擬時(shí)間，然后累積的該進(jìn)程的virtual runtime中（sched_entity中的vruntime），而這個(gè)vruntime就是紅黑樹的key。

7、CFS調(diào)度器的運(yùn)作

對(duì)于CFS調(diào)度器，沒有固定分配時(shí)間片的概念，只有一個(gè)固定權(quán)重的概念，是根據(jù)進(jìn)程靜態(tài)優(yōu)先級(jí)計(jì)算出來(lái)的。CFS調(diào)度器一旦選擇了一個(gè)進(jìn)程進(jìn)入執(zhí)行狀態(tài)，會(huì)立刻開啟對(duì)其virtual runtime的跟蹤過程，并且在tick到來(lái)時(shí)會(huì)更新這個(gè)virtual runtime。有了這個(gè)virtual runtime信息，調(diào)度器就可以不斷的檢查目前系統(tǒng)的公平性（而不是檢查是否時(shí)間片用完），具體的方法是：根據(jù)當(dāng)前系統(tǒng)的情況計(jì)算targeted latency（調(diào)度周期），在這個(gè)調(diào)度周期中計(jì)算當(dāng)前進(jìn)程應(yīng)該獲得的時(shí)間片（物理時(shí)間），然后計(jì)算當(dāng)前進(jìn)程已經(jīng)累積執(zhí)行的物理時(shí)間，如果大于當(dāng)前應(yīng)該獲得的時(shí)間片，那么更新本進(jìn)程的vruntime并標(biāo)記need resched flag，并在最近的一個(gè)調(diào)度點(diǎn)發(fā)起調(diào)度。

在進(jìn)行進(jìn)程調(diào)度時(shí)候，調(diào)度器需要選擇下一個(gè)占用CPU資源的那個(gè)next thread。對(duì)于CFS而言，其算法就是從紅黑樹中找到left most的那個(gè)task并調(diào)度其運(yùn)行。這時(shí)候，失去CPU執(zhí)行權(quán)的那個(gè)task會(huì)被重新插入紅黑樹，其在紅黑樹中的位置是由task的vruntime值決定的。