Linux調(diào)度器中的PELT(Per-Entity Load Tracking)

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

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

1、它必須是公平的

2、快速響應(yīng)

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

4、功耗要小

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

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

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

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

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

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

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

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

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

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

（3）過(guò)去的負(fù)荷也會(huì)被累計(jì)，但是是以遞減的方式來(lái)影響負(fù)載計(jì)算。

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

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

一旦我們有了計(jì)算runnable調(diào)度實(shí)體負(fù)荷貢獻(xiàn)值的方法，那么這個(gè)負(fù)荷值可以向上傳遞，通過(guò)累加control group中的每一個(gè)調(diào)度實(shí)體負(fù)荷值可以得到該control group對(duì)應(yīng)的調(diào)度實(shí)體的負(fù)荷值。這樣的算法不斷的向上推進(jìn)，可以得到整個(gè)系統(tǒng)的負(fù)荷。
當(dāng)然，計(jì)算負(fù)荷不是那么簡(jiǎn)單。因?yàn)檎{(diào)度器本身就會(huì)定期的觀察記錄調(diào)度實(shí)體的信息，計(jì)算runnable調(diào)度實(shí)體的負(fù)荷貢獻(xiàn)是容易的。但沒(méi)有處于runnable狀態(tài)的調(diào)度實(shí)體就對(duì)系統(tǒng)負(fù)荷沒(méi)有貢獻(xiàn)了嗎？當(dāng)“密碼破解”進(jìn)程由于page fault而阻塞，它其實(shí)仍然會(huì)給 “系統(tǒng)列車”增加“負(fù)荷”。因此我們需要有一種計(jì)算進(jìn)入阻塞狀態(tài)的進(jìn)程對(duì)系統(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)度器在每個(gè)cfs_rq（每個(gè)control group都有自己的cfs rq）數(shù)據(jù)結(jié)構(gòu)中，維護(hù)一個(gè)“blocked load”的成員，這個(gè)成員記錄了所有阻塞狀態(tài)進(jìn)程對(duì)系統(tǒng)負(fù)荷的貢獻(xiàn)。
當(dāng)一個(gè)進(jìn)程阻塞了，它的負(fù)載會(huì)從總的運(yùn)行負(fù)載值（runnable load）中減去并添加到總的阻塞負(fù)載值（blocked load）中。該負(fù)載可以以相同的方式衰減（即每個(gè)周期乘以y）。當(dāng)阻塞的進(jìn)程再次轉(zhuǎn)換成運(yùn)行態(tài)時(shí)，其負(fù)載值（適當(dāng)進(jìn)行衰減）則轉(zhuǎn)移到運(yùn)行負(fù)荷上來(lái)。因此，跟蹤blocked load只是需要在進(jìn)程狀態(tài)轉(zhuǎn)換過(guò)程中有一點(diǎn)計(jì)算量，調(diào)度器并不需要由于跟蹤阻塞負(fù)載而遍歷一個(gè)進(jìn)入阻塞狀態(tài)進(jìn)程的鏈表。

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

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

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

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

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

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