一、為何需要per-entity load tracking？

對于Linux內(nèi)核而言，做一款好的進(jìn)程調(diào)度器是一項(xiàng)非常具有挑戰(zhàn)性的任務(wù)，主要原因是在進(jìn)行CPU資源分配的時候必須滿足如下的需求：

1、它必須是公平的

2、快速響應(yīng)

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

4、功耗要小

其實(shí)你仔細(xì)分析上面的需求，這些目標(biāo)其實(shí)是相互沖突的，但是用戶在提需求的時候就是這么任性，他們期望所有的需求都滿足，而且不管系統(tǒng)中的負(fù)荷情況如何。因此，縱觀Linux內(nèi)核調(diào)度器這些年的發(fā)展，各種調(diào)度器算法在內(nèi)核中來來去去，這也就不足為奇了。當(dāng)然，2007年，2.6.23版本引入“完全公平調(diào)度器”（CFS）之后，調(diào)度器相對變得穩(wěn)定一些。最近一個最重大的變化是在3.8版中合并的Per-entity load tracking。

完美的調(diào)度算法需要一個能夠預(yù)知未來的水晶球：只有當(dāng)內(nèi)核準(zhǔn)確地推測出每個進(jìn)程對系統(tǒng)的需求，她才能最佳地完成調(diào)度任務(wù)。不幸的是，硬件制造商推出各種性能強(qiáng)勁的處理器，但從來也不考慮預(yù)測進(jìn)程負(fù)載的需求。
在沒有硬件支持的情況下，調(diào)度器只能祭出通用的預(yù)測大法：用“過去”預(yù)測“未來”，也就是說調(diào)度器是基于過去的調(diào)度信息來預(yù)測未來該進(jìn)程對CPU的需求。而在這些調(diào)度信息中，每一個進(jìn)程過去的“性能”信息是核心要考慮的因素。但有趣的是，雖然內(nèi)核密切跟蹤每個進(jìn)程實(shí)際運(yùn)行的時間，但它并不清楚每個進(jìn)程對系統(tǒng)負(fù)載的貢獻(xiàn)程度。

有人可能會問：“消耗的CPU時間”和“負(fù)載（load）”是否有區(qū)別？是的，當(dāng)然有區(qū)別，Paul Turner在提交per-entity load tracking補(bǔ)丁集的時候?qū)@個問題做了回答。一個進(jìn)程即便當(dāng)前沒有在cpu上運(yùn)行，例如：該進(jìn)程僅僅是掛入runqueue等待執(zhí)行，它也能夠?qū)pu負(fù)載作出貢獻(xiàn)。
“負(fù)載”是一個瞬時量，表示當(dāng)前時間點(diǎn)的進(jìn)程對系統(tǒng)產(chǎn)生的“壓力”是怎樣的？顯然runqueue中有10個等待運(yùn)行的進(jìn)程對系統(tǒng)造成的“壓力”要大于一個runqueue中只有1個等待進(jìn)程的場景。與之相對的“CPU使用率（usage）”不一樣，它不是瞬時量，而是一個累積量。有一個長時間運(yùn)行的進(jìn)程，它可能上周占用大量的處理器時間，但是現(xiàn)在可能占用很少的cpu時間，盡管它過去曾經(jīng)“輝煌”過（占用大量CPU時間），但這對現(xiàn)在的系統(tǒng)負(fù)荷貢獻(xiàn)很小。

3.8版本之前的內(nèi)核CFS調(diào)度器在計算CPU load的時候采用的是跟蹤每個運(yùn)行隊(duì)列上的負(fù)載（per-rq load tracking）。需要注意的是：CFS中的“運(yùn)行隊(duì)列”實(shí)際上是有多個，至少每個CPU就有一個runqueue。而且，當(dāng)使用“按組調(diào)度”（group scheduling）功能時，每個控制組（control group）都有自己的per-CPU運(yùn)行隊(duì)列。
對于per-rq的負(fù)載跟蹤方法，調(diào)度器可以了解到每個運(yùn)行隊(duì)列對整個系統(tǒng)負(fù)載的貢獻(xiàn)。這樣的統(tǒng)計信息足以幫助組調(diào)度器（group scheduler）在控制組之間分配CPU時間，但從整個系統(tǒng)的角度看，我們并不知道當(dāng)前負(fù)載來自何處。除此之外，per-rq的負(fù)載跟蹤方法還有另外一個問題，即使在工作負(fù)載相對穩(wěn)定的情況下，跟蹤到的運(yùn)行隊(duì)列的負(fù)載值也會變化很大。

二、如何進(jìn)行per-entity load tracking？

Per-entity load tracking系統(tǒng)解決了這些問題，這是通過把負(fù)載跟蹤從per rq推進(jìn)到per-entity的層次。所謂調(diào)度實(shí)體（scheduling entity）其實(shí)就是一個進(jìn)程或者control group中的一組進(jìn)程。為了做到Per-entity的負(fù)載跟蹤，時間（物理時間，不是虛擬時間）被分成了1024us的序列，在每一個1024us的周期中，一個entity對系統(tǒng)負(fù)載的貢獻(xiàn)可以根據(jù)該實(shí)體處于runnable狀態(tài)（正在CPU上運(yùn)行或者等待cpu調(diào)度運(yùn)行）的時間進(jìn)行計算。如果在該周期內(nèi)，runnable的時間是x，那么對系統(tǒng)負(fù)載的貢獻(xiàn)就是（x/1024）。
當(dāng)然，一個實(shí)體在一個計算周期內(nèi)的負(fù)載可能會超過1024us，這是因?yàn)槲覀儠鄯e在過去周期中的負(fù)載，當(dāng)然，對于過去的負(fù)載我們在計算的時候需要乘一個衰減因子。如果我們讓Li表示在周期pi中該調(diào)度實(shí)體的對系統(tǒng)負(fù)載貢獻(xiàn)，那么一個調(diào)度實(shí)體對系統(tǒng)負(fù)荷的總貢獻(xiàn)可以表示為：

L = L0+ L1*y + L2*y2+ L3*y3+ ...

其中y是衰減因子。通過上面的公式可以看出：

（1）調(diào)度實(shí)體對系統(tǒng)負(fù)荷的貢獻(xiàn)值是一個序列之和組成

（2）最近的負(fù)荷值擁有最大的權(quán)重

（3）過去的負(fù)荷也會被累計，但是是以遞減的方式來影響負(fù)載計算。

使用這樣序列的好處是計算簡單，我們不需要使用數(shù)組來記錄過去的負(fù)荷貢獻(xiàn)，只要把上次的總負(fù)荷的貢獻(xiàn)值乘以y再加上新的L0負(fù)荷值就OK了。

在3.8版本的代碼中，y已經(jīng)確定：y^32等于0.5。這樣選定的y值，一個調(diào)度實(shí)體的負(fù)荷貢獻(xiàn)經(jīng)過32個周期（1024us）后，對當(dāng)前時間的的符合貢獻(xiàn)值會衰減一半。

一旦我們有了計算runnable調(diào)度實(shí)體負(fù)荷貢獻(xiàn)值的方法，那么這個負(fù)荷值可以向上傳遞，通過累加control group中的每一個調(diào)度實(shí)體負(fù)荷值可以得到該control group對應(yīng)的調(diào)度實(shí)體的負(fù)荷值。這樣的算法不斷的向上推進(jìn)，可以得到整個系統(tǒng)的負(fù)荷。
當(dāng)然，計算負(fù)荷不是那么簡單。因?yàn)檎{(diào)度器本身就會定期的觀察記錄調(diào)度實(shí)體的信息，計算runnable調(diào)度實(shí)體的負(fù)荷貢獻(xiàn)是容易的。但沒有處于runnable狀態(tài)的調(diào)度實(shí)體就對系統(tǒng)負(fù)荷沒有貢獻(xiàn)了嗎？當(dāng)“密碼破解”進(jìn)程由于page fault而阻塞，它其實(shí)仍然會給 “系統(tǒng)列車”增加“負(fù)荷”。因此我們需要有一種計算進(jìn)入阻塞狀態(tài)的進(jìn)程對系統(tǒng)負(fù)載貢獻(xiàn)的方法，當(dāng)前不是調(diào)度器需要關(guān)注的。

當(dāng)然，內(nèi)核可以選擇記錄所有進(jìn)入阻塞狀態(tài)的進(jìn)程，像往常一樣衰減它們的負(fù)載貢獻(xiàn)，并將其增加到總負(fù)載中。但這么做是非常耗費(fèi)資源的。所以，相反，3.8版本的調(diào)度器在每個cfs_rq（每個control group都有自己的cfs rq）數(shù)據(jù)結(jié)構(gòu)中，維護(hù)一個“blocked load”的成員，這個成員記錄了所有阻塞狀態(tài)進(jìn)程對系統(tǒng)負(fù)荷的貢獻(xiàn)。
當(dāng)一個進(jìn)程阻塞了，它的負(fù)載會從總的運(yùn)行負(fù)載值（runnable load）中減去并添加到總的阻塞負(fù)載值（blocked load）中。該負(fù)載可以以相同的方式衰減（即每個周期乘以y）。當(dāng)阻塞的進(jìn)程再次轉(zhuǎn)換成運(yùn)行態(tài)時，其負(fù)載值（適當(dāng)進(jìn)行衰減）則轉(zhuǎn)移到運(yùn)行負(fù)荷上來。因此，跟蹤blocked load只是需要在進(jìn)程狀態(tài)轉(zhuǎn)換過程中有一點(diǎn)計算量，調(diào)度器并不需要由于跟蹤阻塞負(fù)載而遍歷一個進(jìn)入阻塞狀態(tài)進(jìn)程的鏈表。

另外一個比較繁瑣的地方是對節(jié)流進(jìn)程（throttled processes）負(fù)載的計算。所謂節(jié)流進(jìn)程是指那些在“CFS帶寬控制器”（CFS bandwidth controller）下控制運(yùn)行的進(jìn)程。當(dāng)這些進(jìn)程用完了本周期內(nèi)的CPU時間，即使它們?nèi)匀辉谶\(yùn)行狀態(tài)，即使CPU空閑，調(diào)度器并不會把CPU資源分配給它們。
因此節(jié)流進(jìn)程不會對系統(tǒng)造成負(fù)荷。正因?yàn)槿绱耍?dāng)進(jìn)程處于被節(jié)流狀態(tài)的時候，它們對系統(tǒng)負(fù)荷的貢獻(xiàn)值不應(yīng)該按照runnable進(jìn)程計算。在等待下一個周期到來之前，throttled processes不能獲取cpu資源，因此它們的負(fù)荷貢獻(xiàn)值會衰減。

三、per-entity load tracking有什么好處？

有了Per-entity負(fù)載跟蹤機(jī)制，在沒有增加調(diào)度器開銷的情況下，調(diào)度器現(xiàn)在對每個進(jìn)程和“調(diào)度進(jìn)程組”對系統(tǒng)負(fù)載的貢獻(xiàn)有了更清晰的認(rèn)識。有了更精細(xì)的統(tǒng)計數(shù)據(jù)（指per entity負(fù)載值）通常是好的，但人們可能會懷疑這些信息是否真的對調(diào)度器有用。

我們可以通過跟蹤的per entity負(fù)載值做一些有用的事情。最明顯的使用場景可能是用于負(fù)載均衡：即把runnable進(jìn)程平均分配到系統(tǒng)的CPU上，使每個CPU承載大致相同的負(fù)載。如果內(nèi)核知道每個進(jìn)程對系統(tǒng)負(fù)載有多大貢獻(xiàn)，它可以很容易地計算遷移到另一個CPU的效果。這樣進(jìn)程遷移的結(jié)果應(yīng)該更準(zhǔn)確，從而使得負(fù)載平衡不易出錯。目前已經(jīng)有一些補(bǔ)丁利用per entity負(fù)載跟蹤來改進(jìn)調(diào)度器的負(fù)載均衡，相信這些補(bǔ)丁會在不久的將來進(jìn)入到內(nèi)核主線。

small-task packing patch的目標(biāo)是將“小”進(jìn)程收集到系統(tǒng)中的部分CPU上，從而允許系統(tǒng)中的其他處理器進(jìn)入低功耗模式。在這種情況下，顯然我們需要一種方法來計算得出哪些進(jìn)程是“小”的進(jìn)程。利用per-entity load tracking，內(nèi)核可以輕松的進(jìn)行識別。

內(nèi)核中的其他子系統(tǒng)也可以使用per entity負(fù)載值做一些“文章”。CPU頻率調(diào)節(jié)器（CPU frequency governor）和功率調(diào)節(jié)器（CPU power governor）可以利用per entity負(fù)載值來猜測在不久的將來，系統(tǒng)需要提供多少的CPU計算能力。
既然有了per-entity load tracking這樣的基礎(chǔ)設(shè)施，我們期待看到開發(fā)人員可以使用per-entity負(fù)載信息來優(yōu)化系統(tǒng)的行為。雖然per-entity load tracking仍然不是一個能夠預(yù)測未來的水晶球，但至少我們對當(dāng)前的系統(tǒng)中的進(jìn)程對CPU資源的需求有了更好的理解。