基于優(yōu)先級(jí)搶占系統(tǒng)的QNX調(diào)度算法

作為一個(gè)硬實(shí)時(shí)操作系統(tǒng)，QNX是一個(gè)基于優(yōu)先級(jí)搶占的系統(tǒng)。這也導(dǎo)致其基本調(diào)度算法相對(duì)比較簡單。因?yàn)椴恍枰駝e的通用操作系統(tǒng)考慮一些復(fù)雜的“公平性”，只需要保證“優(yōu)先級(jí)最高的線程最優(yōu)先得到 CPU”就可以了。

基本調(diào)度算法

調(diào)度算法，是基于優(yōu)先級(jí)的。QNX的線程優(yōu)先級(jí)，是一個(gè)0-255的數(shù)字，數(shù)字越大優(yōu)先級(jí)越高。所以，優(yōu)先級(jí)0是內(nèi)核中的idle線程。同時(shí)，優(yōu)先級(jí)64是一個(gè)分界嶺。就是說，優(yōu)先級(jí)1 – 63 是非特權(quán)優(yōu)先級(jí)，一般用戶都可以用，而64 – 255必須是有root權(quán)限的線程才以設(shè)。這個(gè)“優(yōu)先級(jí)64”分界線，如果有必要，還可以通過啟動(dòng)Procnto時(shí)傳 –P 來改變。 調(diào)度算法的對(duì)像是線程，而線程在QNX上，有大約20個(gè)狀態(tài)。（參考 /usr/include/sys/states.h）在這許多狀態(tài)中，跟調(diào)度有關(guān)的，其實(shí)只有 STATE_RUNNING和STATE_READY兩個(gè)狀態(tài)。STATE_RUNNING是線程當(dāng)前正在使用CPU，而STATE_READY是等著被執(zhí)行（被調(diào)度）的線程。其他狀態(tài)的線程，處于某種“阻塞”狀態(tài)中，調(diào)度算法不需要關(guān)注。 所以在調(diào)度算法看來，整個(gè)系統(tǒng)里的線程像這樣：

圖 1 有兩個(gè)CPU的系統(tǒng)里的線程 這是一個(gè)有兩個(gè)CPU的系統(tǒng)，所以可以看到有兩個(gè)RUNNING線程；對(duì)于 BLOCK THREAD，它們不參于調(diào)度，所以不需要考慮它們的優(yōu)先級(jí)。

調(diào)度策略

在QNX上實(shí)質(zhì)上只有三種基本調(diào)度策略，“輪詢”（Round Robin），“先進(jìn)先出”（First in first out）和＂零星調(diào)度”(Sporadic) 算法。雖然形式上還有一個(gè)“其他”，但“其他”跟“輪詢”是一樣的。這些調(diào)度策略，在 /usr/include/sched.h 里有定義。(SCHED_FIFO, SCHED_RR, SCHED_SPORADIC, SCHED_OTHER) 強(qiáng)調(diào)一下，調(diào)度策略只限于在READY隊(duì)列里的線程，優(yōu)線級(jí)最高的線程有不止一個(gè)時(shí)，才會(huì)用到。如果線程不再 READY，或是有別的更高優(yōu)先級(jí)的線程 READY了，那就高優(yōu)先級(jí)線程獲取CPU，沒有什么策略可言。 “輪詢調(diào)度”（Round Robin）跟平時(shí)生活里排隊(duì)的情形差不多，晚到的人排在隊(duì)尾，早到的人排在隊(duì)首，等到叫號(hào)（調(diào)度）的時(shí)候，隊(duì)首的人會(huì)被先叫到 。如下圖所示：

圖 2 論詢調(diào)度示意

首先在CPU 1上運(yùn)行的線程4，被挪入優(yōu)先級(jí)15的隊(duì)列末尾

然后重新搜索可執(zhí)行的最高優(yōu)先級(jí)線程，這里有優(yōu)先級(jí)15隊(duì)列上的線程3和4

線程3因?yàn)樵陉?duì)列最前端，它被選擇得到CPU，線程3的狀態(tài)變?yōu)镽UNNING，在CPU1上執(zhí)行

可以預(yù)期，當(dāng)下一次調(diào)度發(fā)生時(shí)，線程3會(huì)被挪入優(yōu)先級(jí)15隊(duì)列末尾，而線程4會(huì)被調(diào)度執(zhí)行，這樣線程3和4會(huì)分別得到CPU1. “先進(jìn)先出”（First in first out）調(diào)度則剛好相反，后來的人插在隊(duì)首，然后在叫號(hào)的時(shí)候被先叫到?？聪聢D： ?

圖 3 先進(jìn)先出調(diào)度示意

首先在CPU 1上運(yùn)行的線程4，被挪入優(yōu)先級(jí)15的隊(duì)列隊(duì)首

然后重新搜索可執(zhí)行的最高優(yōu)先級(jí)線程，這里有優(yōu)先級(jí)15隊(duì)列上的線程4和3

線程4因?yàn)樵陉?duì)列最前端，它被選擇得到CPU，線程4的狀態(tài)變?yōu)镽UNNING，在CPU1上執(zhí)行

可以看到，在這個(gè)調(diào)度算法下，如果沒有別的狀態(tài)發(fā)生，事實(shí)上線程4就會(huì)一直占據(jù)CPU1。 如果在優(yōu)先級(jí)15上的線程3和線程4都是FIFO會(huì)怎樣？按上面的描述，線程3還是始終無法獲得CPU1，因?yàn)榫€程4每次都會(huì)插在3的前面，再調(diào)度就又是4獲得CPU1。除非線層4進(jìn)入了阻塞狀態(tài)（從而不在READY隊(duì)列里了），那么線程3才能獲得CPU。 “零星調(diào)度”（Sporadic）算法比較特殊，它比較適合長時(shí)間占用CPU的線程。它的基本設(shè)計(jì)思想是給一個(gè)線程準(zhǔn)備兩個(gè)優(yōu)先級(jí)，“前臺(tái)”優(yōu)先級(jí)比較高，“后臺(tái)”優(yōu)先級(jí)稍微底一點(diǎn)。如果線程在高優(yōu)先級(jí)連續(xù)占用CPU超過一定時(shí)間后，線程會(huì)被強(qiáng)行降到“后臺(tái)”低優(yōu)先級(jí)上（這時(shí)線程能不能占用CPU取決于系統(tǒng)中有沒有比“后臺(tái)”優(yōu)先級(jí)高的別的線程了）；然后線程在低優(yōu)先級(jí)上經(jīng)過了一段時(shí)間后，會(huì)重新被調(diào)回高優(yōu)先級(jí)。

圖 4 零星調(diào)度示意 上圖是一個(gè)零星調(diào)度線程的示意。

開始的時(shí)候，線程在比較高的（正常）優(yōu)先級(jí) H 上運(yùn)行，一直到把預(yù)先分配給零星調(diào)度的時(shí)間用完（sched_ss_init_budget）

這時(shí)，線程會(huì)被自動(dòng)調(diào)整為低優(yōu)先級(jí)L（sched_ss_low_priority）；一旦被調(diào)低，線程也可能運(yùn)行（如果優(yōu)先級(jí)L依然是系統(tǒng)里最高優(yōu)先級(jí)的線程），也可能無法運(yùn)行呆在READY隊(duì)列里（系統(tǒng)里有比L更高的優(yōu)先級(jí)）

不管線程有沒有執(zhí)行，從最開始運(yùn)行時(shí)間點(diǎn)算起，當(dāng)線程“執(zhí)行補(bǔ)充時(shí)間"（sched_ss_repl_period）過了以后，線程的優(yōu)先級(jí)被重新提到優(yōu)先級(jí)H，并試圖取得CPU來。

“零星調(diào)度”看上去比較“公平”，但是實(shí)際在用QNX的項(xiàng)目中，這個(gè)調(diào)度算法很少被用戶用到。主要是因?yàn)橐话銇碚f在QNX上很少有線程能夠“連續(xù)占用CPU”的。而且當(dāng)系統(tǒng)變得復(fù)雜，線程數(shù)成百上千后，這種上下調(diào)優(yōu)先級(jí)的做法，很容易出現(xiàn)別的后遺癥。

什么時(shí)候會(huì)發(fā)生調(diào)度？

上面介紹了QNX支持的幾個(gè)調(diào)度算法。那么，什么時(shí)候才會(huì)發(fā)生調(diào)度呢？ QNX的設(shè)計(jì)目標(biāo)是一個(gè)硬實(shí)時(shí)操作系統(tǒng)，所以，保證最高優(yōu)先級(jí)的線程在第一時(shí)間占據(jù)CPU是很重要的?？紤]到線程的狀態(tài)都是在內(nèi)核中進(jìn)行變化的（都是因?yàn)榫€程進(jìn)行了某個(gè)內(nèi)核調(diào)用后變化的），所以QNX在每次從內(nèi)核調(diào)用退出時(shí)，都會(huì)進(jìn)行一次線程調(diào)度，以保證最高優(yōu)先級(jí)的線程可以占據(jù)CPU。 得益于微內(nèi)核結(jié)構(gòu)，QNX的內(nèi)核調(diào)用通常都非常短，或者說，每一個(gè)內(nèi)核調(diào)用，都能夠比較確定地知道要花多少時(shí)間。而且，因?yàn)槲?nèi)核系統(tǒng)的基本就是進(jìn)程間通信，所以在QNX上，一段程序非常容易進(jìn)入內(nèi)核并進(jìn)行線程狀態(tài)切換，很少能有長時(shí)間占滿CPU的，在實(shí)際系統(tǒng)上測，現(xiàn)實(shí)上很少能有線程執(zhí)行完整個(gè)時(shí)間片的。 舉個(gè)例子，哪怕程序里只寫一個(gè) printf("Hello World! "); 可是在libc庫里，最后這個(gè)會(huì)變成一個(gè)IO_WRITE消息，MsgSend() 給控制臺(tái)驅(qū)動(dòng)；這時(shí)，在MsgSend()這個(gè)內(nèi)核調(diào)用里，會(huì)把printf() 的線程置為阻塞狀態(tài)（REPLY BLOCK），同時(shí)會(huì)把控制臺(tái)驅(qū)動(dòng)的信息接收線程（從RECEIVE BLOCK）改到 READY狀態(tài)，并放入 READY 隊(duì)列。當(dāng)退出MsgSend() 內(nèi)核調(diào)用時(shí)，線程調(diào)度發(fā)生，通常情況下（如果沒有別的線程READY 的話）控制臺(tái)驅(qū)動(dòng)的信息接收線程被激活，并占據(jù)CPU. 如果用戶寫了一個(gè)既不內(nèi)核調(diào)用，也不放棄CPU的線程會(huì)怎么樣？那時(shí)候，時(shí)鐘中斷會(huì)發(fā)生，當(dāng)內(nèi)核記時(shí)到線程占據(jù)了一整個(gè)時(shí)間片（QNX上是4ms）后，內(nèi)核會(huì)強(qiáng)制當(dāng)前線程進(jìn)入 READY，并重新調(diào)度。如果同一優(yōu)先級(jí)只有這一個(gè)線程（這是優(yōu)先級(jí)最高線程），那么調(diào)度后，還是這個(gè)線程獲取CPU。如果同一優(yōu)先級(jí)有別的線程存在，那么根據(jù)調(diào)度算法來決定哪個(gè)線程獲得CPU。 另一種常見情況是，由于某些別的原因?qū)е赂邇?yōu)先級(jí)線程被激活，比如網(wǎng)卡驅(qū)動(dòng)中斷導(dǎo)致高優(yōu)先級(jí)驅(qū)動(dòng)線程READY，所設(shè)時(shí)鐘到達(dá)導(dǎo)致高優(yōu)先級(jí)線程從阻塞狀態(tài)返回READY狀態(tài)了，當(dāng)前線程開放互斥鎖之類的線程同步對(duì)象，導(dǎo)致別的線程返回READY狀態(tài)了。這些，都會(huì)在從內(nèi)核調(diào)用退出時(shí)，進(jìn)行調(diào)度。

中斷與優(yōu)先級(jí)

上面提到如果用戶線程長期占有CPU，時(shí)鐘中斷會(huì)打斷用戶線程。細(xì)心的讀者或許會(huì)有疑問，那中斷的優(yōu)先級(jí)是多少呢？ 答案是在QNX這樣的實(shí)時(shí)操作系統(tǒng)里，“硬件中斷”永遠(yuǎn)高于任何線程優(yōu)先級(jí)，哪怕你的線程優(yōu)先級(jí)到了255，只要有中斷發(fā)生，都要讓路，CPU會(huì)跳轉(zhuǎn)去執(zhí)行中斷處理程序，執(zhí)行完了再回歸用戶線程。事實(shí)上，能夠快速穩(wěn)定地響應(yīng)中斷處理，是一個(gè)實(shí)時(shí)操作系統(tǒng)的硬指標(biāo)。 我們這里說的是“硬件中斷”，就是說，當(dāng)外部設(shè)備，通過中斷控制器，向CPU發(fā)出中斷請(qǐng)求時(shí)，無論當(dāng)時(shí)CPU上執(zhí)行的線程優(yōu)先級(jí)是什么，都會(huì)先跳轉(zhuǎn)到內(nèi)核的中斷處理程序；中斷處理程序會(huì)去中斷控制器找到具體是哪一個(gè)源發(fā)生了中斷（中斷號(hào)），并據(jù)此，跳轉(zhuǎn)到該中斷號(hào)的中斷處理程序（通常是硬件驅(qū)動(dòng)程序 通過 InterruptAttach() 掛接的函數(shù)）。在這個(gè)過程中，如果當(dāng)前CPU正在處理另一個(gè)中斷，那么這時(shí)，會(huì)根據(jù)中斷的優(yōu)先級(jí)來決定是讓CPU繼續(xù)處理下去（當(dāng)前中斷進(jìn)入等待）；或者發(fā)生中斷搶占，新中斷的優(yōu)先級(jí)比舊中斷高，所以跳轉(zhuǎn)新中斷處理。 當(dāng)然，實(shí)際應(yīng)用中，特別是微內(nèi)核環(huán)境下，考慮中斷其實(shí)只是中斷設(shè)備給出的一個(gè)通知，對(duì)這中斷的響應(yīng)并不需要真的在中斷處理中進(jìn)行，驅(qū)動(dòng)程序可以選擇在普通線程中處理，QNX上有InterruptAttachEvent() 就是為了這個(gè)設(shè)計(jì)的。通常這里的“事件”會(huì)是一個(gè)“脈沖”，也就是說，當(dāng)硬件中斷發(fā)生，內(nèi)核檢查到相應(yīng)中斷綁定了事件。這時(shí)，不會(huì)跳轉(zhuǎn)到用戶中斷處理程序，而是直接發(fā)出那個(gè)脈沖，以激活一個(gè)外部（驅(qū)動(dòng)器中）線程，在這線程中，做設(shè)備中斷所需要的處理。這樣做，雖然稍微增加了一些中斷延遲，但也帶來了不少好處。首先，這個(gè)外部線程同普通的用戶線程一樣，所以可以調(diào)用任何庫函數(shù)，而中斷服務(wù)程序因?yàn)閳?zhí)行環(huán)境的不同，有好多限制。其次，因?yàn)槭瞧胀ㄓ脩艟€程，就可以用線程調(diào)度的方法規(guī)定其優(yōu)先級(jí)（脈沖事件是帶優(yōu)先級(jí)的），使不同的設(shè)備中斷處理，跟正常業(yè)務(wù)邏輯更好地一起使用。

多CPU上的線程調(diào)度

現(xiàn)在同步多處理器（SMP）已經(jīng)相當(dāng)普及了。在SMP上，也就是說當(dāng)有多個(gè)CPU時(shí)，我們的調(diào)度算法有什么變化呢？比如一個(gè)有2個(gè)CPU的系統(tǒng)，首先肯定，系統(tǒng)上可執(zhí)行線程中的最高優(yōu)先級(jí)線程，一定在2個(gè)CPU上的某一個(gè)上執(zhí)行；那，是不是第二高優(yōu)先級(jí)的線程就在另一個(gè)CPU上執(zhí)行呢？ 雖然直覺上我們覺得應(yīng)該是這樣的（系統(tǒng)里的第一，第二高優(yōu)先級(jí)的線程占據(jù)CPU1和CPU2），但事實(shí)上，第二高優(yōu)先級(jí)的線程占據(jù)CPU2這件事，并不是必要的。實(shí)時(shí)搶占系統(tǒng)的要求是最高優(yōu)先級(jí)”必須“能夠搶占CPU，但對(duì)第二高優(yōu)先級(jí)并沒有規(guī)定。拿我們最開始的雙CPU圖再看一眼。

圖 5 有兩個(gè)CPU的系統(tǒng)里的線程 線程4以優(yōu)先級(jí)15占據(jù)CPU1這是毫無疑問的，但線程5只有優(yōu)先級(jí)12，為什么它可以占據(jù)CPU2，而線程3明明也有優(yōu)先級(jí)15，但只能排隊(duì)等候，這是不是優(yōu)先級(jí)倒置了？其實(shí)并沒有，如上所述，系統(tǒng)確實(shí)保證了“最高優(yōu)先級(jí)占據(jù)CPU”的要求，但在CPU2上執(zhí)行什么線程，除了線程本身的優(yōu)先級(jí)以外，還有一些別的因素可以權(quán)衡，其中一個(gè)在SMP上比較重要的，就是“線程躍遷”。 “線程躍遷”指的是一個(gè)線程，一會(huì)兒在CPU1上執(zhí)行，一會(huì)兒在CPU2上執(zhí)行。在SMP系統(tǒng)上，線程躍遷而導(dǎo)致的緩存清除與重置，會(huì)給系統(tǒng)性能帶來很大的影響。所以在線程調(diào)度時(shí)，盡量把線程調(diào)度到上次執(zhí)行時(shí)用的CPU，是SMP調(diào)度算法里比較重要的一環(huán)。上述例子中，很有可能就是線程3上一次是在CPU1上執(zhí)行的，而線程5雖然優(yōu)先級(jí)比較低，很有可能上一次就是在CPU2上執(zhí)行的。 實(shí)際應(yīng)用中，因?yàn)镼NX的易于阻塞的特性，其實(shí)大多數(shù)情況下，還是符合“第一，第二高優(yōu)先級(jí)線程在CPU上執(zhí)行”的。只是，如果你觀察到了上述情形，也不需要擔(dān)心，設(shè)計(jì)上確實(shí)有可能不是第二高優(yōu)先級(jí)的線程在運(yùn)行。 另一個(gè)多處理器上常見的應(yīng)用，是線程綁定。在正常情況下，把可執(zhí)行線程調(diào)度到哪一個(gè)CPU上，是由操作系統(tǒng)完成的。當(dāng)然操作系統(tǒng)會(huì)考慮“線程躍遷”等情形來做決定。但是，QNX的用戶也可以把線程綁定到某一個(gè)（或者某幾個(gè)）CPU上，這樣操作系統(tǒng)在調(diào)度時(shí)，會(huì)考慮用戶的要求來進(jìn)行。綁定是通過ThreadCtl() 修改線程的 “RUNMASK” 來進(jìn)行的，如果你有0,1,2,3 總共4個(gè)CPU，那么 0x00000003意味著線程可以在CPU0和CPU1上執(zhí)行，具體例子可以參考ThreadCtl()函數(shù)說明。更簡單的辦法，是通過QNX特有的 on 命令的 –C 參數(shù)來指定，這個(gè)指定的 runmask，還會(huì)自動(dòng)繼承。所以你可以簡單的如下執(zhí)行： # on –C 0x00000003 Navigation &
# on –C 0x00000004 Media &
# on –C 0x00000008 System & 這樣來把不同的系統(tǒng)部署到不同的CPU上。 這樣做的好處當(dāng)然是可以減少比如因?yàn)橄到y(tǒng)繁忙而對(duì)導(dǎo)航帶來的影響，但不要忘了，另一面，如果所有 Media 線程都處于阻塞狀態(tài)，上述綁定也限制了導(dǎo)航線程使用CPU2的可能，CPU2這時(shí)候就會(huì)空轉(zhuǎn)（執(zhí)行內(nèi)核 idle 線程）。

自適應(yīng)分區(qū)調(diào)度算法

前面我們提到過，在討論優(yōu)先級(jí)調(diào)度時(shí)，只是討論當(dāng)有多個(gè)優(yōu)先級(jí)相同的線程時(shí)，系統(tǒng)怎樣取舍。優(yōu)先級(jí)不一樣時(shí)，肯定是優(yōu)先級(jí)高的贏。但是“高出多少”并不是一個(gè)考量因素。兩個(gè)線程，一個(gè)優(yōu)先級(jí)10，另一個(gè)優(yōu)先級(jí)11的情況，和一個(gè)10，另一個(gè)40的情況是一樣的。并不會(huì)因?yàn)?0和40差距比較大而有什么不同。 假如我們有紅藍(lán)兩個(gè)線程，它們的優(yōu)先級(jí)一樣，調(diào)度策略是RR，兩個(gè)線程都不阻塞，那么在10時(shí)間片的區(qū)間里，我們看到的就是這樣一個(gè)執(zhí)行結(jié)果： 也就是說，各占了50%的CPU。但只要把藍(lán)色線程提高哪怕1，執(zhí)行結(jié)果就成了下面這樣。 這種“非黑即白”的情形，是實(shí)時(shí)系統(tǒng)的基本要求（高優(yōu)先級(jí)搶占CPU）。但是當(dāng)然，現(xiàn)實(shí)情況有時(shí)候比較復(fù)雜。比如 “HMI渲染” 是需要經(jīng)常占據(jù)CPU的一個(gè)任務(wù)（這樣畫面才會(huì)順暢），但“用戶輸入”也是需要響應(yīng)比較快的（不然用戶的點(diǎn)擊就會(huì)沒有反應(yīng)）。如果“用戶輸入”的優(yōu)先級(jí)太高的話，那用戶拖拽時(shí)，畫面就會(huì)卡頓甚至沒有反應(yīng)？反之，如果”HMI 渲染“的優(yōu)先級(jí)太高，那么有用戶輸入時(shí)，因?yàn)樘幚沓绦騼?yōu)先級(jí)低而造成用戶輸入反應(yīng)慢。通常情況下，需要有經(jīng)驗(yàn)的系統(tǒng)工程師不斷調(diào)整這兩個(gè)任務(wù)的優(yōu)先級(jí)（因?yàn)閮?yōu)先級(jí)繼承與傳統(tǒng)，一個(gè)任務(wù)可能涉及到多個(gè)線程），來達(dá)到系統(tǒng)的最優(yōu)。那么，有沒有別的辦法呢?

分區(qū)調(diào)度

傳統(tǒng)上，有一種“分區(qū)調(diào)度”的方法，今天還有一些Hypervisor采取這個(gè)辦法。這個(gè)想法很簡單，就是把CPU算力隔成幾個(gè)分區(qū)，比如70%，30%這樣，然后把不同線程分到這些分區(qū)里，當(dāng)分區(qū)里的CPU預(yù)算被用完以后，那個(gè)分區(qū)里所有可執(zhí)行線程都會(huì)被”停住“，直到預(yù)算恢復(fù)。 假設(shè)我們把紅線程放入70%紅色分區(qū)，藍(lán)線程放入30%藍(lán)色分區(qū)，然后以10個(gè)時(shí)間片為預(yù)算滑動(dòng)窗口大小，各線程具體就會(huì)如下圖占據(jù)CPU：

圖 6 分區(qū)調(diào)度算力全滿示意 在前6個(gè)時(shí)間片中，藍(lán)紅分區(qū)分別占據(jù)CPU，注意在第7個(gè)時(shí)間片時(shí)，雖然藍(lán)分區(qū)中線程跟紅分區(qū)中線程有相同的優(yōu)先級(jí)，雖然調(diào)度策略是輪回，應(yīng)該輪到藍(lán)線程上了，但是因?yàn)樗{(lán)線程已經(jīng)用完了10個(gè)時(shí)間片里的3個(gè)，所以系統(tǒng)沒有執(zhí)行藍(lán)線程，而是繼續(xù)讓紅線程占據(jù)CPU，一直到第8第9和第10個(gè)時(shí)間片結(jié)束。 10個(gè)時(shí)間片結(jié)束后，窗口向右滑動(dòng)，這時(shí)我們等于又多了一個(gè)時(shí)間片的預(yù)算，在新的10個(gè)時(shí)間片中，藍(lán)線程只占了兩個(gè)(20%)，這樣，新的第11個(gè)時(shí)間片，就分給了藍(lán)分區(qū)。 同理再滑動(dòng)后，第12個(gè)時(shí)間片，分給紅線程；一直到17個(gè)時(shí)間片時(shí)，同樣的事情再度發(fā)生，藍(lán)分區(qū)線程又用完了10個(gè)時(shí)間片里的3個(gè)，而被迫等待它的預(yù)算重新補(bǔ)充進(jìn)來。 綜上，在任意一個(gè)滑動(dòng)窗口中，藍(lán)色分區(qū)總是只占30%，而紅色分區(qū)卻占了70%。QNX的自適應(yīng)分區(qū)調(diào)度，跟上面這個(gè)是類似的。只是傳統(tǒng)的分區(qū)調(diào)度，有一個(gè)明顯的弱點(diǎn)。 想一下這個(gè)情況，如果紅線程因?yàn)槟承┣闆r被阻塞了，會(huì)發(fā)生什么呢？

圖 7 分區(qū)調(diào)度算力有富余示意 對(duì)，藍(lán)線程是唯一可執(zhí)行線程，所以它一直占據(jù)CPU。但是，當(dāng)3個(gè)時(shí)間片輪轉(zhuǎn)之后，因?yàn)樗{(lán)分區(qū)只有30%的時(shí)間預(yù)算，它將不再占據(jù)CPU，而因?yàn)榧t線程無法執(zhí)行，接下來的7個(gè)時(shí)間片CPU處于空轉(zhuǎn)狀態(tài)（執(zhí)行Idle線程）。 一直到時(shí)間窗口移動(dòng)，那時(shí)，因?yàn)樗{(lán)分區(qū)只占用了20%的算力，所以它再次占據(jù)CPU…… 所以你也看到了，在傳統(tǒng)的分區(qū)調(diào)度里，當(dāng)一個(gè)分區(qū)的算力有富裕的時(shí)候，CPU就被浪費(fèi)了。

自適應(yīng)分區(qū)調(diào)度

QNX在傳統(tǒng)的分區(qū)調(diào)度上，增加了“自適應(yīng)”的部份。其基本思想是一樣的，給算力加分區(qū)，然后把不同的線程分到分區(qū)里。這樣，當(dāng)所有的線程都忙起來時(shí)，你會(huì)發(fā)現(xiàn)情況跟圖7是一樣的。但是當(dāng)分區(qū)算力有富裕時(shí)，“自適應(yīng)“允許把多出來的算力”借“給需要更多算力的分區(qū)。

圖 8 自適就分區(qū)算力有富裕示意 如上，當(dāng)藍(lán)色分區(qū)里的線程消耗完了他自己的分區(qū)預(yù)算后，自適應(yīng)分區(qū)會(huì)把有富裕算力的紅色分區(qū)的預(yù)算，借給藍(lán)色分區(qū)，藍(lán)分區(qū)內(nèi)線程得以繼續(xù)在CPU上運(yùn)行。注意，在第8個(gè)時(shí)間片時(shí)，紅色分區(qū)需要使用CPU，藍(lán)色分區(qū)立即讓路，把CPU讓給紅色分區(qū)。而當(dāng)紅色分區(qū)里的線程被阻塞住以后，藍(lán)色分區(qū)線程繼續(xù)使用CPU。 自適應(yīng)分區(qū)似乎確實(shí)帶來了好處，但是也帶來了一些潛在的問題，需要在系統(tǒng)設(shè)計(jì)的時(shí)候做好決定。

自適應(yīng)分區(qū)調(diào)度與線程優(yōu)先級(jí)

你可能會(huì)好奇，在分區(qū)調(diào)度的系統(tǒng)里，線程的優(yōu)先級(jí)代表了什么？ 答案取決于各個(gè)分區(qū)對(duì)各自算力的消耗情況。我們假設(shè)藍(lán)色分區(qū)里的線程優(yōu)先級(jí)比較高，紅色的優(yōu)先級(jí)比較低，當(dāng)兩個(gè)分區(qū)都有預(yù)算時(shí)，內(nèi)核會(huì)調(diào)度（所有分區(qū)里的）最高優(yōu)先級(jí)線程執(zhí)行。如果系統(tǒng)一直不是很忙，那么不論分區(qū)，永遠(yuǎn)是有最高優(yōu)先級(jí)的線程得到CPU，這個(gè)，跟一個(gè)標(biāo)準(zhǔn)的實(shí)時(shí)操作系統(tǒng)是一致的。 當(dāng)兩個(gè)分區(qū)中某一個(gè)有預(yù)算時(shí)（意味著那個(gè)分區(qū)中所有的線程都不在執(zhí)行狀態(tài)），那么多出來的CPU算力會(huì)被分給另一個(gè)分區(qū)，另一個(gè)分區(qū)中的最高優(yōu)先級(jí)線程（雖然用完了自己分區(qū)的預(yù)算，但得到了別的分區(qū)的算力），繼續(xù)占據(jù)CPU。這個(gè)，也是跟實(shí)時(shí)操作系統(tǒng)是一致的。 比較特殊的情況是，當(dāng)兩個(gè)分區(qū)都沒有預(yù)算，都需要占據(jù)CPU時(shí)，這時(shí)，藍(lán)色線程雖然有較高的優(yōu)先級(jí)，但因?yàn)榉謪^(qū)算力(30%)被用完，面且沒有別的算力可以“借”，所以它被留在READY隊(duì)列中，而比它優(yōu)先級(jí)低的紅色線程得以占據(jù)CPU。

自適應(yīng)分區(qū)調(diào)度富裕算力分配

我們上面的例子只有兩個(gè)分區(qū)，考慮這樣一個(gè)例子。假設(shè)我們現(xiàn)在有A (70%)，B (20%)，C (10%) 三個(gè)分區(qū)，A分區(qū)沒有可執(zhí)行線程，B分區(qū)有個(gè)優(yōu)先級(jí)為10的線程，C分區(qū)有個(gè)優(yōu)先級(jí)為20的線程。我們知道A分區(qū)的70%會(huì)分配給B和C，但具體是怎么分配的呢？ 如上所述，當(dāng)預(yù)算有富裕時(shí)，系統(tǒng)挑選所有分區(qū)中，優(yōu)先級(jí)最高的線程執(zhí)行，也就是說C分區(qū)中的線程得到運(yùn)行。在一個(gè)窗口以后，你會(huì)發(fā)現(xiàn)A的CPU使用率是0%，B是20%，C則達(dá)到了80%。也就是說A所有的富裕算力，都給了C分區(qū)（因?yàn)镃中的線程優(yōu)先級(jí)高）。 也許，在某些時(shí)候，這個(gè)不是你所期望的。也許C中有一些第三方程序你無法控制，你也不希望他們偷偷提高優(yōu)先級(jí)而占用全部富裕算力。QNX提供了SchedCtl()函數(shù)，可以設(shè)SCHED_APS_FREETIME_BY_RATIO 標(biāo)志。設(shè)了這個(gè)標(biāo)志后，富裕算力會(huì)按照各分區(qū)的預(yù)算比例分配給各分區(qū)。上面的例子下，最后的CPU使用率會(huì)變成 A 是0%， B是65%，而C是35%。A分區(qū)富裕的70%算力，按照大約 2: 1的比例，分給了分區(qū)B和C。

“關(guān)鍵線程”與“關(guān)鍵分區(qū)”

在實(shí)際使用中，有一些重要任務(wù)，可能需要響應(yīng)，不論其所在的分區(qū)還有沒有算力。比如一個(gè)緊急中斷服務(wù)線程，不管分區(qū)是不是還有預(yù)算，都需要響應(yīng)。為了解決這種情況，在QNX的自適應(yīng)分區(qū)調(diào)度里，除了給分區(qū)分配算力預(yù)算以外，還允許有權(quán)限的用戶為分區(qū)分配“關(guān)鍵響應(yīng)時(shí)間”，并把特定線程定義為“關(guān)鍵線程”。 當(dāng)一個(gè)“關(guān)鍵線程”需要執(zhí)行時(shí)，如果線程所在分區(qū)有預(yù)算，它就直接使用所在分區(qū)預(yù)算就好，如同普通線程；如果所在分區(qū)沒有預(yù)算了，但是別的分區(qū)還有預(yù)算，那么“自適應(yīng)”部份會(huì)把別分區(qū)的預(yù)算拿過來，并用于關(guān)鍵線程，這個(gè)跟普通的自適應(yīng)分區(qū)調(diào)度一樣。 只有當(dāng)系統(tǒng)里所有分區(qū)都沒有預(yù)算了，而有一個(gè)關(guān)鍵線程需要運(yùn)行，而且線程所在的分區(qū)已經(jīng)預(yù)先分配了關(guān)鍵響應(yīng)預(yù)算，那么線程允許“突破”分區(qū)的預(yù)算，使用“關(guān)鍵響應(yīng)預(yù)算”來執(zhí)行。在QNX里，一個(gè)關(guān)鍵線程消耗的時(shí)間，從退出RECEIVE_BLOCK開始，到下一次進(jìn)入RECEIVE_BLOCK。而且，關(guān)鍵線程的屬性是可傳遞的，如果關(guān)鍵線程在執(zhí)行中，給別的線程發(fā)送了消息，那個(gè)線程也會(huì)變成關(guān)鍵線程。 總的來說，關(guān)鍵線程是用來保證關(guān)鍵任務(wù)不會(huì)因?yàn)橄到y(tǒng)太忙而無法取得CPU時(shí)間。即使所有的分區(qū)都被占滿了，至少還有“關(guān)鍵響應(yīng)時(shí)間”可供關(guān)鍵線程來使用。當(dāng)然，一個(gè)系統(tǒng)里不應(yīng)該有太多的關(guān)鍵線程和關(guān)鍵響應(yīng)時(shí)間。理論上，假設(shè)所有的線程都是關(guān)鍵線程，那么整個(gè)系統(tǒng)其實(shí)就變成了一個(gè)普通的按優(yōu)先級(jí)調(diào)度的實(shí)時(shí)系統(tǒng)，所有的分區(qū)和預(yù)算都不起作用了。 在最緊急的情況下，關(guān)鍵線程可以使用“關(guān)鍵響應(yīng)時(shí)間”來完成它的任務(wù)。如果“關(guān)鍵響應(yīng)時(shí)間”還是不夠，會(huì)怎么樣？這個(gè)是系統(tǒng)設(shè)計(jì)問題，在設(shè)計(jì)系統(tǒng)的時(shí)候，你就應(yīng)該為關(guān)鍵線程分配它能夠完成任務(wù)所需要的最大時(shí)間。如果依然發(fā)生“關(guān)鍵響應(yīng)時(shí)間”不夠的狀況（被稱為“破產(chǎn)”狀態(tài)），這個(gè)就是一個(gè)設(shè)計(jì)錯(cuò)誤了。

關(guān)鍵線程的破產(chǎn)

如上所述，關(guān)鍵線程的破產(chǎn)是一個(gè)設(shè)計(jì)問題?；蛘呔€程完成的任務(wù)并不那么“關(guān)鍵”，或者設(shè)計(jì)時(shí)給出的預(yù)算不夠。這種情況下需要重新審視整個(gè)系統(tǒng)設(shè)計(jì)（因?yàn)橄到y(tǒng)在某些情況下無法保證關(guān)鍵任務(wù)在預(yù)定時(shí)間內(nèi)完成）。QNX在自適應(yīng)分區(qū)里提供了偵測到關(guān)鍵線程破產(chǎn)時(shí)的多種響應(yīng)辦法，可以是強(qiáng)行忽視，或者重啟系統(tǒng)，或者由自適應(yīng)分區(qū)系統(tǒng)自動(dòng)調(diào)整分區(qū)的預(yù)算。

自適應(yīng)分區(qū)繼承

想像這個(gè)場景，文件系統(tǒng)在System分區(qū)里，但另一個(gè)Others分區(qū)里的第三方應(yīng)用拼命調(diào)用文件系統(tǒng)，很有可能造成System分區(qū)的預(yù)算耗盡；這樣，首先可能導(dǎo)致別的應(yīng)用無法使用文件系統(tǒng)；更嚴(yán)重的，可能是System分區(qū)里別的系統(tǒng)，比如Audio也無法正常工作。這個(gè)，顯然是自適應(yīng)分區(qū)系統(tǒng)帶來的安全隱患。 解決辦法，就是跟優(yōu)先級(jí)在消息傳遞上可以繼承一樣，分區(qū)也是可以繼承的。文件系統(tǒng)雖然分配在System系統(tǒng)里，但根據(jù)它響應(yīng)的是誰的請(qǐng)求，時(shí)間被記到請(qǐng)求服務(wù)的線程分區(qū)里。這樣，如果一個(gè)第三方應(yīng)用拼命調(diào)用文件系統(tǒng)，最多能做的，也只是消耗它自己的分區(qū)，當(dāng)他自己分區(qū)的預(yù)算被耗盡時(shí)，影響它自己的CPU占用率。

自適應(yīng)分區(qū)的小結(jié)

自適應(yīng)分區(qū)有一些有趣的用法，比如我們常常被要求“系統(tǒng)需要保留30%的算力”。有了自適應(yīng)分區(qū)，就可以建一個(gè)有30%預(yù)算的分區(qū)，在里面跑一個(gè) for (;;); 這樣的死循環(huán)。這樣，剩下的系統(tǒng)就只有70%的算力了，可以在這個(gè)環(huán)境下檢驗(yàn)一下系統(tǒng)的性能和穩(wěn)定性。 自適應(yīng)分區(qū)的具體操作方法，可以參考QNX的文檔。不同版本的QNX有稍微不同的命令行，但基本設(shè)計(jì)是一樣的。這篇文章只是介紹了自適應(yīng)分區(qū)的基本概念，實(shí)際使用上，還是有許多細(xì)節(jié)需要考慮的，真的要使用，還是需要詳細(xì)參考QNX對(duì)應(yīng)文檔。 ?

編輯：黃飛

?