本篇我們來講講另一種調(diào)度方式-公平調(diào)度方式院峡。公平調(diào)度模式基于一個(gè)基本概念：相對(duì)于MLFQ優(yōu)化周轉(zhuǎn)時(shí)間和相應(yīng)時(shí)間，公平調(diào)度模式是保證每個(gè)任務(wù)都獲得一定比例的cpu時(shí)間系宜。

基本概念：票據(jù)數(shù)量代表應(yīng)該分配的多少

任務(wù)擁有多少票據(jù)的比例就應(yīng)該分配多少比例的資源照激。假如有2個(gè)任務(wù)A和B，A擁有75張票據(jù)盹牧，B擁有25張票據(jù)俩垃，那么A應(yīng)該占有75%的cpu時(shí)間励幼，B占有25%的cpu時(shí)間。
獎(jiǎng)池調(diào)度法通過經(jīng)常（一個(gè)時(shí)間片的間隔）抽獎(jiǎng)的方式來決定誰中獎(jiǎng)了口柳。系統(tǒng)中有任務(wù)A和任務(wù)B苹粟，一共票據(jù)數(shù)量有100張。其中A有75張票據(jù)跃闹，0號(hào)到74號(hào)嵌削。B擁有25張，75號(hào)到99號(hào)望艺。然后開始抽獎(jiǎng)掷贾，如果抽到0到74就選擇A，否則選擇B荣茫。調(diào)度器會(huì)把加載選擇的進(jìn)程狀態(tài)然后運(yùn)行它想帅。
我們可以觀察到，通過隨機(jī)來保證正確的可能性啡莉，但并不是保證正確港准。這個(gè)很容易理解，如果隨機(jī)的次數(shù)比較少咧欣，偶然性就比較大浅缸，如果隨機(jī)次數(shù)很多，就很接近我們想要的比例了魄咕。
這里在談?wù)勲S機(jī)的好處衩椒，隨機(jī)的好處其一是不會(huì)有個(gè)特定的輸出會(huì)導(dǎo)致性能很差，比如算法中的隨機(jī)化快排就是為了避免特定的場(chǎng)景下有很差的性能哮兰。其二隨機(jī)很輕量化毛萌，只需要跟蹤很小的狀態(tài)。比如要統(tǒng)計(jì)每個(gè)進(jìn)程使用的cpu時(shí)間喝滞，需要運(yùn)行每個(gè)進(jìn)程后再統(tǒng)計(jì)阁将。隨機(jī)化只需要知道每個(gè)進(jìn)程擁有票據(jù)的數(shù)量就可以了。其三隨機(jī)速度很快右遭，一個(gè)最簡(jiǎn)單的偽隨機(jī)算法是線性同余法做盅，只有一個(gè)加法和乘法的運(yùn)算。

票據(jù)機(jī)制

樂透調(diào)度法提供了一些操作票據(jù)不同的方法窘哈。

• 票據(jù)貨幣化吹榴，允許任務(wù)給自己的子任務(wù)分發(fā)票據(jù)，這些票據(jù)最終可以兌換成全局票據(jù)滚婉。
  舉個(gè)例子图筹，用戶A和B分別擁有100張票據(jù)，用戶A運(yùn)行了2個(gè)任務(wù)A1和A2满哪，給它們分別500張內(nèi)部票據(jù)（一共1000張）婿斥。B只運(yùn)行了一個(gè)任務(wù)B1給它10張內(nèi)部票據(jù)（一共10張）劝篷。系統(tǒng)把A1和A2的500張票據(jù)對(duì)應(yīng)到全局票據(jù)上分別是50張。而B1的10張內(nèi)部票據(jù)對(duì)應(yīng)系統(tǒng)全局票據(jù)為100張民宿。
  User A -> 500 (A’s currency) to A1 -> 50 (global currency)
  -> 500 (A’s currency) to A2 -> 50 (global currency)
  User B -> 10 (B’s currency) to B1 -> 100 (global currency)

• 票據(jù)轉(zhuǎn)移娇妓。使用票據(jù)轉(zhuǎn)移，一個(gè)進(jìn)程可以臨時(shí)性的把自己的票據(jù)交給另外一個(gè)進(jìn)程活鹰。這個(gè)在client/server的環(huán)境中尤為有用哈恰，當(dāng)client發(fā)送一個(gè)消息給server要求為它提供一些服務(wù)時(shí)，client可以把自己的票據(jù)交給server志群，最大化加快server的運(yùn)行着绷，運(yùn)行完畢后，server歸還client的票據(jù)锌云。

• 通貨膨脹在某些時(shí)候可能是比較有用的技術(shù)荠医，一個(gè)進(jìn)程可以臨時(shí)的增加或者降低它的票據(jù)數(shù)量。當(dāng)然桑涎，在相互競(jìng)爭(zhēng)的場(chǎng)景下彬向，進(jìn)程之間相互不信任，這就沒有意義了攻冷。一個(gè)貪婪的進(jìn)程可以給自己派發(fā)大量的票據(jù)娃胆，進(jìn)而得到幾乎獨(dú)占整個(gè)機(jī)器。通貨膨脹可以應(yīng)用到一組進(jìn)程等曼，大家相互信任彼此的里烦，在這種場(chǎng)景下，一個(gè)進(jìn)程如果知道自己需要更多cpu時(shí)間禁谦，它就可以提高自己票據(jù)數(shù)量胁黑，整個(gè)過程無需和其他進(jìn)程進(jìn)行商量。

樂透調(diào)度偽代碼如下：

1 // counter: used to track if we’ve found the winner yet
2 int counter = 0;
3
4 // winner: use some call to a random number generator to
5 // get a value, between 0 and the total # of tickets
6 int winner = getrandom(0, totaltickets);
7
8 // current: use this to walk through the list of jobs
9 node_t *current = head;
10 while (current) {
11 counter = counter + current->tickets;
12 if (counter > winner)
13 break; // found the winner
14 current = current->next;
15 }
16 // ’current’ is the winner: schedule it...

實(shí)現(xiàn)

首先我們要隨機(jī)出400以內(nèi)的隨機(jī)數(shù)，然后遍歷鏈表就能選擇合適的任務(wù)去運(yùn)行了氮发。為了讓鏈表更高效的運(yùn)行渴肉，最好從大到小的排序這個(gè)鏈表。排序后并不影響算法的正確性爽冕，但是可以減少遍歷的次數(shù)仇祭，尤其是當(dāng)有個(gè)進(jìn)程擁有大量票據(jù)的情況下。

如何分配票據(jù)

為什么不能使用確定性

使用隨機(jī)的策略的調(diào)度器只能提供大概的準(zhǔn)確性颈畸，尤其對(duì)短任務(wù)而言這種調(diào)度方式不能提供準(zhǔn)確性乌奇。因?yàn)檫@種原因 Waldspurger發(fā)明出步調(diào)度没讲，一種確定的公平調(diào)度器。
步調(diào)度也是很直接的礁苗，每個(gè)任務(wù)都擁有步長爬凑，步長與擁有票據(jù)數(shù)量成反比。用上面的例子A试伙，B嘁信，C分別擁有票據(jù)100，50疏叨，250潘靖。那么步長的計(jì)算，為一個(gè)較大的數(shù)蚤蔓，這里我么用10000 除票據(jù)數(shù)量卦溢。那么步長就分別是100，200秀又，40单寂。進(jìn)程每次運(yùn)行時(shí)，我們都用步長來遞增計(jì)數(shù)器涮坐，通過這種方式來跟蹤它的全局進(jìn)度凄贩。
調(diào)度器決定下一個(gè)運(yùn)行的進(jìn)程通過步長，選擇目前來說運(yùn)行了最短的路徑的進(jìn)程袱讹。
偽代碼如下：

curr = remove_min(queue); // pick client with min pass
schedule(curr); // run for quantum
curr->pass += curr->stride; // update pass using stride
insert(queue, curr); // return curr to queue

linux的完全公平的調(diào)度模式

基于上述的關(guān)于公平調(diào)度模式的準(zhǔn)備工作疲扎，當(dāng)前的linux的調(diào)度模式使用輪詢的方式達(dá)到相似的目標(biāo)。這種調(diào)度模式叫做Completely Fair Scheduler(CFS)捷雕，實(shí)現(xiàn)它的方式具有高效性和可擴(kuò)展性椒丧。
為了很高效的實(shí)現(xiàn)，在CFS整個(gè)設(shè)計(jì)中就只準(zhǔn)備花少量時(shí)間來做調(diào)度決策救巷，它使用了十分聰明的數(shù)據(jù)結(jié)構(gòu)來組織任務(wù)壶熏。最近的研究表明，調(diào)度器的高效性是很令人驚奇的重要浦译，在研究Google的數(shù)據(jù)中心表明棒假，甚至通過積極的優(yōu)化，調(diào)度本身仍然占據(jù)了5%的整個(gè)數(shù)據(jù)中心的cpu時(shí)間精盅。減少調(diào)度的負(fù)載架構(gòu)現(xiàn)代調(diào)度器的關(guān)鍵目標(biāo)帽哑。

基本操作

大部分基于此概念的調(diào)度器都使用定長的時(shí)間片，但是CFS有些不同叹俏。它的目標(biāo)是在多個(gè)競(jìng)爭(zhēng)的進(jìn)程之間公平的劃分cpu時(shí)間妻枕，通過簡(jiǎn)單的統(tǒng)計(jì)virtual runtime (vruntime)，物理時(shí)間的一個(gè)比例。
隨著每個(gè)進(jìn)程的運(yùn)行屡谐，調(diào)度器會(huì)統(tǒng)計(jì)virtual runtime述么。每個(gè)進(jìn)程大部分情況下以相同的速率增加，當(dāng)調(diào)度決策發(fā)生時(shí)愕掏，調(diào)度器會(huì)選擇一個(gè)最小vruntime的進(jìn)程去運(yùn)行度秘。
這就帶來一個(gè)問題，調(diào)度決策應(yīng)該何時(shí)發(fā)生亭珍，多久發(fā)生一次敷钾？如果CFS決策太頻繁了 ，公平性保證了肄梨，但是會(huì)帶來性能的消耗（太多的上下文切換）阻荒，如果CFS決策時(shí)間太久了，公平性就難以保障了众羡。
CFS通過一個(gè)參數(shù)來控制調(diào)度時(shí)間侨赡。第一個(gè)為sched latency，CFS使用這個(gè)值來進(jìn)行判斷多久決策一次粱侣，一個(gè)典型的數(shù)值為48ms羊壹，當(dāng)系統(tǒng)中有n個(gè)進(jìn)程運(yùn)行時(shí)，sched latency / n為調(diào)度周期齐婴。
舉個(gè)例子油猫，假設(shè)系統(tǒng)中有4個(gè)進(jìn)程在運(yùn)行，用sched latency除以4柠偶，所以到達(dá)每個(gè)進(jìn)程的時(shí)間片為12ms情妖，調(diào)度器首選選出一個(gè)進(jìn)程運(yùn)行直到用完時(shí)間片，然后在最小vruntime的進(jìn)程去運(yùn)行诱担，循環(huán)如此毡证。需要注意的是當(dāng)任務(wù)數(shù)量發(fā)生變化時(shí)，時(shí)間片長度也會(huì)動(dòng)態(tài)發(fā)生變化蔫仙。
如果我們系統(tǒng)中有很多進(jìn)程運(yùn)行時(shí)呢料睛，是不是可能會(huì)導(dǎo)致太短的時(shí)間片呢？為了解決這個(gè)問題CFS引入了第二個(gè)參數(shù)min_granularity摇邦，通常這個(gè)值被設(shè)置成6ms恤煞，當(dāng)劃分后的時(shí)間片長度小于min_granularity，就強(qiáng)制設(shè)置成min_granularity的值施籍，目的在于避免太多的調(diào)度消耗阱州。
舉個(gè)例子系統(tǒng)中有10個(gè)進(jìn)程運(yùn)行，時(shí)間片長度本該是4.8ms法梯，有了min_granularity所以時(shí)間片長度被設(shè)置成6ms了。
CFS利用了周期性的時(shí)鐘中斷，當(dāng)中斷發(fā)生時(shí)立哑，CFS就有機(jī)會(huì)進(jìn)行調(diào)度決策了夜惭。就算一個(gè)任務(wù)擁有不是整數(shù)倍調(diào)度周期的時(shí)間片，也沒關(guān)系铛绰，因?yàn)関runtime被精確記錄了诈茧，隨著時(shí)間的增加，慢慢就會(huì)拿到合適的cpu時(shí)間的捂掰。

權(quán)重

CFS同樣可以控制進(jìn)程的權(quán)重敢会，允許系統(tǒng)管理員給某些進(jìn)程更多的cpu時(shí)間。這里并不是票據(jù)而是進(jìn)程的nice等級(jí)这嚣，nice值從-20到19之間鸥昏，默認(rèn)值為0。正數(shù)代表低優(yōu)先級(jí)姐帚，負(fù)數(shù)代表高優(yōu)先級(jí)吏垮。具體優(yōu)先級(jí)對(duì)應(yīng)的權(quán)重如下

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

根據(jù)權(quán)重值，可以計(jì)算每個(gè)進(jìn)程的時(shí)間片長度罐旗，計(jì)算公式如下：

除此之外膳汪，vruntime的計(jì)算方法也發(fā)生改變了。

這里注意2個(gè)概念九秀，調(diào)度器的調(diào)度周期以及每個(gè)進(jìn)程劃分的時(shí)間片遗嗽。是否加入不同權(quán)重后，調(diào)度器的調(diào)度周期也發(fā)生改變呢鼓蜒？調(diào)度進(jìn)行決策周期和時(shí)鐘周期有關(guān)而時(shí)鐘周期固定周期發(fā)生的痹换，所以可能發(fā)生的情況是時(shí)間片是不同的，但是決策周期是相同的友酱。時(shí)鐘中斷大概是每2ms到3ms發(fā)生一次晴音，這個(gè)在內(nèi)核編譯期間就決定的，可能會(huì)稍微丟失一點(diǎn)精度缔杉。

使用紅黑樹

調(diào)度器必須要高效锤躁，現(xiàn)在談?wù)摰揭粋€(gè)問題，如何調(diào)度器找到下一個(gè)需要調(diào)度的任務(wù)』蛳辏現(xiàn)代操作系統(tǒng)可能運(yùn)行1000個(gè)任務(wù)呢系羞，不可能使用鏈表去遍歷。
CFS解決進(jìn)程的組織任務(wù)通過紅黑樹霸琴，通過vruntime的大小椒振，紅黑樹是二叉平衡樹，對(duì)比簡(jiǎn)單的樹而言梧乘，簡(jiǎn)單的樹可能最壞情況下退化成鏈表澎迎。紅黑樹只需要簡(jiǎn)單的一些維護(hù)的工作就可以保證樹的高度在logN庐杨。CFS并不把所有的進(jìn)程都維護(hù)在這個(gè)數(shù)據(jù)結(jié)構(gòu)上，只是包含running以及runable狀態(tài)的進(jìn)程夹供。如果進(jìn)程阻塞了灵份，就從這里移除。紅黑樹插入哮洽，查找以及刪除都是logN的復(fù)雜度填渠，有良好的性能。

處理在I/O以及sleep的進(jìn)程

假想一個(gè)場(chǎng)景鸟辅，有2個(gè)正在運(yùn)行的進(jìn)程A和B氛什，A都是繼續(xù)運(yùn)行的，這時(shí)候B睡眠了10秒匪凉。如果按照之前的調(diào)度策略保持vruntime保持不變的話枪眉，A喚醒后，接下來會(huì)獨(dú)占cpu10秒鐘以便能補(bǔ)上之前落后的10秒的時(shí)間洒缀，這顯然是不能接受的瑰谜。
CFS在這種情況下回修改剛剛喚醒后的任務(wù)的vruntime為在集合中能查找到的最小的vruntime的值。通過這種方式來避免餓死任務(wù)發(fā)生的可能性树绩，但是一個(gè)經(jīng)常睡眠一小段時(shí)間的任務(wù)就不能獲得它本該公平獲得的cpu時(shí)間了萨脑。

最后的總結(jié)

我們談到了比例分配調(diào)度的方式，提到了3種方式：樂透法饺饭，步長法以及l(fā)inux的完全公平調(diào)度模式渤早。完全公平的調(diào)度方法有點(diǎn)像具有權(quán)重的RR調(diào)度法。
沒有任何一個(gè)調(diào)度器是完美的瘫俊，公平調(diào)度模式也有它的問題鹊杖，比如對(duì)經(jīng)常I/O的程序不夠友好，還有個(gè)問題就是如何分配進(jìn)程的權(quán)重扛芽，這個(gè)問題任然存在骂蓖。其他的調(diào)度器比如MLFQ會(huì)自動(dòng)調(diào)整進(jìn)而更容易部署。
好消息是很多場(chǎng)景下對(duì)這些問題并不敏感川尖，完全公平的調(diào)度能很高效的運(yùn)行登下。比如在一個(gè)數(shù)據(jù)中心中，需要分配1/4的cpu給windows VM叮喳，剩下的給linux安裝程序被芳。按比例分配會(huì)很簡(jiǎn)單和高效。