CPU調(diào)度器調(diào)度

調(diào)度器的權(quán)衡：(包括但不限于如下)

• 調(diào)度開銷與調(diào)度效果：調(diào)度決策考慮的條件越多舍沙，調(diào)度決策越復(fù)雜就會導(dǎo)致決策時間變長朵栖，與決策后產(chǎn)生的效果之間存在權(quán)衡颊亮。
• 優(yōu)先級與公平性：一邊要保證高優(yōu)先級的先執(zhí)行，一邊又不能讓優(yōu)先級低的任務(wù)執(zhí)行時間過短甚至無法執(zhí)行
• 性能與消耗：調(diào)度器過分追求性能時能耗也變高

任務(wù)類型

• 批處理任務(wù)：
  如機(jī)器學(xué)習(xí)的訓(xùn)練陨溅，復(fù)雜的科學(xué)計算终惑，這類無需與用戶交互，其目標(biāo)是盡快得到結(jié)果门扇。其任務(wù)指標(biāo)是吞吐量盡可能大和周轉(zhuǎn)時間盡量短狠鸳。
• 交互式任務(wù):
  用戶關(guān)心自己的請求是否能得到快速的相應(yīng)，指標(biāo)是響應(yīng)時間悯嗓。
• 實(shí)時任務(wù)：
  在處理有截至?xí)r間要求的任務(wù)，比如視頻畫面的渲染卸察，每一幀都要在截止時間前完成渲染脯厨。指標(biāo)是實(shí)時性。

1. 響應(yīng)時間：任務(wù)從發(fā)起直至第一次向用戶返回輸出以及響應(yīng)用戶所需的時間
2. 周轉(zhuǎn)時間：任務(wù)從發(fā)起直至結(jié)束所需的時間
3. 吞吐量：單位時間內(nèi)處理的任務(wù)數(shù)量
4. 實(shí)時性：在截至?xí)r間之前完成任務(wù)
5. 計算密集型：類似機(jī)器學(xué)習(xí)任務(wù)等以大量使用CPU計算的任務(wù)
6. I/O密集型：通常會花費(fèi)大部分時間等待I/O坑质，僅有少量時間在CPU中處理請求

經(jīng)典調(diào)度方式

主要針對批處理任務(wù)的策略

7. FCFS (first come first served)

對I/O密集型任務(wù)不友好合武，在長短任務(wù)混合的情況下對短任務(wù)不友好，考慮周轉(zhuǎn)時間和響應(yīng)時間

8. SJF(short job first)短任務(wù)優(yōu)先

FCFS的優(yōu)點(diǎn)就是簡單涡扼，不用考慮其他條件稼跳，決策簡單快速。

在SJF的策略下吃沪，在長短任務(wù)混合的場景下任務(wù)的平均周轉(zhuǎn)周期是小于FCFS策略的汤善，但是SJF也不能適應(yīng)長短任務(wù)混合的場景，原因是必須預(yù)知任務(wù)的運(yùn)行時間，在固定任務(wù)場景下是可以的红淡，但是絕大多數(shù)情況下是很難預(yù)測任務(wù)時長的不狮。而且嚴(yán)重依賴任務(wù)到達(dá)時間，如果長任務(wù)先來此時調(diào)度器不知道后面會有短任務(wù)就會先執(zhí)行長任務(wù)

9. STCF (Short Time-to-Completion First)最短時間完成任務(wù)優(yōu)先

SJF面對的短任務(wù)遲到問題是因?yàn)樗?code>非搶占式調(diào)度在旱，將其改為搶占式調(diào)度即可在長任務(wù)沒執(zhí)行完且到來的短任務(wù)短于長任務(wù)的剩余時間時搶占長任務(wù)的CPU摇零。
這會造成長任務(wù)饑餓，長任務(wù)可能一直不會執(zhí)行

主要針對交互式程序的策略

10. RR (Round Robin 時間片輪轉(zhuǎn))

前幾種只有在任務(wù)結(jié)束和到來時才進(jìn)行調(diào)度桶蝎，無法及時響應(yīng)用戶的輸入驻仅。采用為任務(wù)設(shè)置時間片，進(jìn)行時間片的輪轉(zhuǎn)登渣，任務(wù)搶占時間片的方式可解決這個問題噪服。
關(guān)鍵點(diǎn)在于時間片的大小如何決定，時間片越小切換上下文次數(shù)越多绍豁。
在任務(wù)運(yùn)行時間相似的場景下平均周轉(zhuǎn)時間高芯咧。

優(yōu)先級調(diào)度

為了保持良好的用戶體驗(yàn)，應(yīng)盡量避免交互式任務(wù)被批處理任務(wù)阻塞

優(yōu)先級的概念可以讓操作系統(tǒng)區(qū)分批處理任務(wù)和交互任務(wù)竹揍，為每個任務(wù)設(shè)置優(yōu)先級敬飒，設(shè)置交互任務(wù)的優(yōu)先級高于批處理任務(wù)就可實(shí)現(xiàn)更好的交互體驗(yàn)

11. MLQ(Multi-Level Queue)多級隊列

對于擁有截止時間的實(shí)時任務(wù)應(yīng)該為其設(shè)置最高的優(yōu)先級；對于交互任務(wù)的響應(yīng)時間直接影響用戶的體驗(yàn)芬位，應(yīng)該為為其分配較高的優(yōu)先級无拗；對于批處理任務(wù)一般對時延和響應(yīng)時間的要求不高，可以為其設(shè)置低一點(diǎn)的優(yōu)先級昧碉。
每個優(yōu)先級對應(yīng)一個隊列英染，任務(wù)被存儲在對應(yīng)的隊列中。如果優(yōu)先級不同的任務(wù)同時處于預(yù)備狀態(tài)時調(diào)度器優(yōu)先調(diào)度高優(yōu)先級任務(wù)被饿。處于同級隊列中的任務(wù)四康，內(nèi)部的調(diào)度方式?jīng)]有統(tǒng)一的標(biāo)準(zhǔn)，可以針對性的為不同的隊列采用不同的調(diào)度策略狭握。
MLQ適合靜態(tài)的應(yīng)用場景(任務(wù)信息可以在執(zhí)行前獲知),但是也會導(dǎo)致優(yōu)先級低的任務(wù)饑餓闪金，為解決低優(yōu)先級任務(wù)饑餓問題，需要引入額外的機(jī)制監(jiān)控等待時間论颅，為等待時間過長的任務(wù)提升優(yōu)先級哎垦。
優(yōu)先級反轉(zhuǎn):多個任務(wù)可能會對同一份數(shù)據(jù)產(chǎn)生競爭，因此任務(wù)會使用鎖來保護(hù)共享數(shù)據(jù)恃疯。假設(shè)現(xiàn)在有優(yōu)先級為A>B>C的三個任務(wù)漏设，任務(wù)C運(yùn)行時持有鎖，然后他被A搶占了(此時C的鎖還沒釋放)今妄，此時任務(wù)A想持有C的鎖失敗郑口，因此進(jìn)入阻塞狀態(tài)鸳碧。此時任務(wù)B、C都處于可運(yùn)行狀態(tài)潘酗，B優(yōu)先級高于C杆兵，因此B先運(yùn)行，綜合觀察結(jié)果仔夺，表現(xiàn)得像B的優(yōu)先級高于A一樣琐脏，先于A執(zhí)行。
一個可行的解決方案：優(yōu)先級繼承缸兔，任務(wù)A可將自己的優(yōu)先級轉(zhuǎn)讓給C日裙，讓C優(yōu)先執(zhí)行并釋放鎖。任務(wù)A可在C釋放鎖后以搶占的方式立即執(zhí)行惰蜜，從而避免了優(yōu)先級反轉(zhuǎn)的問題昂拂。

12. MLFQ(multi-Level Feedback Queue)多級反饋隊列

隨著計算機(jī)的發(fā)展，任務(wù)可能同時要求低周轉(zhuǎn)和低響應(yīng)時間并且任務(wù)運(yùn)行時間無法預(yù)知抛猖。STCF和RR都無法同時滿足上述條件格侯。
1962年Corbatoo提出了多級反饋隊列
MLFQ也會維護(hù)多級隊列，其創(chuàng)新點(diǎn)是實(shí)現(xiàn)優(yōu)先級的動態(tài)設(shè)置财著。具體策略如下:

1. 短任務(wù)擁有更高的優(yōu)先級联四。主要有三點(diǎn)好處，1撑教、優(yōu)先調(diào)度短任務(wù)會有更好的平均周轉(zhuǎn)時間朝墩；2、I/O密集型任務(wù)一般在CPU中執(zhí)行時間很短伟姐，給短任務(wù)高優(yōu)先級就相當(dāng)于提高了I/O密集型任務(wù)的優(yōu)先級收苏；3、交互式任務(wù)一般也是短任務(wù)愤兵。
   (問題是如何判斷是短任務(wù)鹿霸？？秆乳？這是MLQ和MLFQ的限制)
   MLFQ根據(jù)統(tǒng)計每個任務(wù)已經(jīng)運(yùn)行時間的長短判斷該任務(wù)是長任務(wù)還是短任務(wù)懦鼠。首先任務(wù)剛進(jìn)入系統(tǒng)時認(rèn)為他是短任務(wù)，然后MLFQ會為每個隊列設(shè)置任務(wù)的最大運(yùn)行時間(任務(wù)多次執(zhí)行的總時間)矫夷，如果任務(wù)執(zhí)行時間超過了它所在該隊列的最大運(yùn)行時間就會將它的優(yōu)先級減一。
2. 低優(yōu)先級的任務(wù)采用更長的時間片憋槐。（這個調(diào)度策略運(yùn)行在IBM7090的CTSS相容分時系統(tǒng)上双藕，處于內(nèi)存保護(hù)和簡化設(shè)計的考慮，該系統(tǒng)一次只能將一個用戶的任務(wù)加載進(jìn)內(nèi)存阳仔，任務(wù)切換開銷非常大忧陪。這么做是為了降低切換上下文的次數(shù)扣泊。）
3. 定時將所有任務(wù)的優(yōu)先級調(diào)至最高。MLFQ也會導(dǎo)致低優(yōu)先級任務(wù)饑餓嘶摊，一個計算密集型的任務(wù)經(jīng)過幾次運(yùn)行后會被調(diào)至最低的優(yōu)先級延蟹，如果一直有短任務(wù)進(jìn)來就會導(dǎo)致計算密集型任務(wù)的饑餓。此策略可保證不會有任務(wù)饑餓叶堆。

這會造成最前面說的調(diào)度器權(quán)衡的問題阱飘，在MLFQ中，任務(wù)的優(yōu)先級被動態(tài)的提升(Boost)的降低(對應(yīng)于“懲罰”Penalty)虱颗。Boost和Penalty是用于動態(tài)調(diào)節(jié)任務(wù)優(yōu)先級的機(jī)制沥匈，被用在包括Linux的許多操作系統(tǒng)中。這些啟發(fā)式方法在提升調(diào)度器效果時也增加了設(shè)計的復(fù)雜度和難度忘渔。（許多參數(shù)需要調(diào)節(jié)高帖，優(yōu)先級隊列的數(shù)量、每個優(yōu)先級隊列的時間片畦粮、任務(wù)隊列的最大運(yùn)行時間散址、調(diào)度器定時提升優(yōu)先級的時間間隔等）如果參數(shù)設(shè)置不當(dāng)不僅效果沒有提升反而會下降，需要設(shè)計師非常豐富的經(jīng)驗(yàn)和對系統(tǒng)整體有細(xì)致的了解才可以實(shí)現(xiàn)出有效的基于MLFQ的調(diào)度器宣赔。

公平共享調(diào)度

當(dāng)用戶共享服務(wù)器資源時预麸，一個默認(rèn)的假設(shè)是：用戶使用的資源數(shù)（例如CPU時間）與所付出的資金是成正比的。

假設(shè)現(xiàn)在有兩個用戶小明和小亮一人出一半錢合資租賃了一臺云平臺上的單核服務(wù)器拉背，他們商定平分CPU時間师崎，并且小明同時開了三個任務(wù)（A、B椅棺、C）犁罩，而小亮只開了一個任務(wù)D，那么有什么調(diào)度策略能實(shí)現(xiàn)他平分CPU時間片的約定呢两疚？床估？？

好像前面說的策略都不可以诱渤。我想到的是再加一個調(diào)度用戶的層丐巫，沒有什么是不能通過加一個中間層來實(shí)現(xiàn)的，如果有就再加一層Ｉ酌馈５蓦省！

13. 彩票調(diào)度

我么們知道彩票分為彩票池和彩票赡茸，總份額相當(dāng)于彩票池缎脾，每個人的份額相當(dāng)于彩票（比如彩票池中有30份彩票，你擁有其中3份占卧，你的中將概率就是10%）遗菠，調(diào)度就是抽彩票联喘，抽中了誰的那份就調(diào)度誰。

// 調(diào)度策略偽代碼
R = random(0, total_tickets)
sum = 0
foreach(task in task_list){
      sum += task->total_ticket
      if(R < sum){
        schedle()
        break
      }
}

一些基于彩票調(diào)度的優(yōu)化方法：

• 彩票轉(zhuǎn)讓：類似于前文中的優(yōu)先級繼承辙纬，在系統(tǒng)實(shí)際運(yùn)行中豁遭，份額大的任務(wù)A可能會等待份額下的B持有的鎖，彩票調(diào)度會讓A有更高的概率運(yùn)行贺拣，造成CPU資源浪費(fèi)蓖谢。這時A將自己份額轉(zhuǎn)讓給B，讓B以高概率運(yùn)行纵柿。
• 彩票貨幣：增加一層抽象蜈抓，將自己所持有的份額以某比例兌換成彩票貨幣（如1：10）分發(fā)給用戶的任務(wù)們而不是直接分發(fā)份額給任務(wù)們。這樣在用戶的份額發(fā)生改變時（比如在彩票轉(zhuǎn)讓的時候）昂儒，不必改變用戶任務(wù)持有的貨幣只改變兌換比例就可以了（保持貨幣數(shù)量不變沟使，改變兌換比例）。優(yōu)化的點(diǎn)可能就是改動少了吧
• 彩票通脹：彩票通脹的思想是給任務(wù)一定的自由度渊跋，允許任務(wù)根據(jù)自己當(dāng)時對CPU資源的需求動態(tài)的決定自己的份額腊嗡。任務(wù)之間是需要信任的，如果有任務(wù)惡意提升自己的貨幣量拾酝，會很糟糕燕少。（書上就寫了這么多！］锒凇？兔恰）
  
  
  
  當(dāng)然彩票調(diào)度也有屬于自己局限，隨機(jī)數(shù)帶來的問題材诽。我認(rèn)為對那些持有彩票份額小而且持有時間短的用戶非常不友好底挫，因?yàn)榉蓊~越小，就越需要更多輪才能被抽中一次脸侥，在前期該任務(wù)被執(zhí)行的次數(shù)是小于他本應(yīng)被執(zhí)行的次數(shù)的建邓。

14. 步幅調(diào)度

這是一個確定性的公平共享調(diào)度策略唱凯。
引入了虛擬時間(virtual time)的概念茂洒，假設(shè)一臺機(jī)器上有兩個用戶A和B共享，A:B份額比例是5:6锄贼。為了讓其使用的CPU時間也是5:6外遇，將他們運(yùn)行的時間片設(shè)置為相同的T秒注簿，記錄他們運(yùn)行的虛擬時間（A每調(diào)度一次+6秒，B每調(diào)度一次+5秒）跳仿，每次調(diào)度當(dāng)前虛擬時間少的用戶诡渴。（步幅調(diào)度的意思就是，保持用戶并排走塔嬉，一個步子大邁步頻率低玩徊，一個步子小邁步頻率高。）

實(shí)時調(diào)度

//TODO 后面再補(bǔ)充吧

其他調(diào)度

//TODO 后面再補(bǔ)充吧

多核調(diào)度策略（重頭戲終于來了）

前文討論的都是單核的調(diào)度策略谨究，雖然多個任務(wù)并發(fā)的共享CPU恩袱，但是本質(zhì)上還是串行執(zhí)行。在多核系統(tǒng)中要考慮的會更多胶哲。

當(dāng)頭三問

• 當(dāng)前應(yīng)該調(diào)度哪個/哪些任務(wù)畔塔？
• 每個調(diào)度的任務(wù)該在哪個核心上執(zhí)行？
• 每個調(diào)度任務(wù)應(yīng)該執(zhí)行多久鸯屿？

題外話：線程是CPU調(diào)度的最小單位

負(fù)載分擔(dān)

多核共享一個全局優(yōu)先級隊列澈吨，用前文介紹的調(diào)度策略給每個CPU核心調(diào)度，這種方法就是負(fù)載分擔(dān)寄摆，因?yàn)橄到y(tǒng)的負(fù)載是被所有核心分擔(dān)的谅辣。

優(yōu)點(diǎn)：

• 設(shè)計實(shí)現(xiàn)簡單。通過負(fù)載分擔(dān)婶恼，可將多核調(diào)度問題規(guī)約為單核調(diào)度問題桑阶，使用已有調(diào)度策略和單核調(diào)度器就可實(shí)現(xiàn)一個全局的多核心調(diào)度策略。
• 每個CPU核心都會分擔(dān)系統(tǒng)負(fù)載勾邦，不會出現(xiàn)CPu浪費(fèi)的問題蚣录。

局限性：

• 多核心共享一個全局運(yùn)行隊列的同步開銷大（任務(wù)A依賴任務(wù)B的結(jié)果，A等待B的資源浪費(fèi)）
• 任務(wù)在多個核心之間切換的開銷大（重新載入緩存眷篇、TLB刷新等）

協(xié)同調(diào)度

多線程程序?yàn)榱死枚嗪颂幚砥魑樱ǔ⒐ぷ髁枯^大的任務(wù)切分為多個子任務(wù)，并將每個子任務(wù)交給不同的CPU核心處理蕉饼，這些子任務(wù)之間可能有依賴關(guān)系虐杯，另外某些子任務(wù)傾向于同時執(zhí)行(關(guān)聯(lián)任務(wù))。

在需要通信的線程也可能出現(xiàn)無端消耗CPU的情況椎椰。假設(shè)線程A和B對應(yīng)程序的子任務(wù)厦幅，他們可在一個時間片內(nèi)進(jìn)行多輪通信，但是調(diào)度器不知道他們的關(guān)聯(lián)慨飘，結(jié)果是A和B不在同一個時間片上進(jìn)行确憨，大大的降低了執(zhí)行效率。

為了滿足對一組任務(wù)進(jìn)行調(diào)度的需求瓤的，提出了協(xié)同調(diào)度的概念休弃，其目的是盡可能的讓一組任務(wù)并行執(zhí)行。避免調(diào)度器同時調(diào)度有依賴關(guān)系的任務(wù)圈膏，同時避免關(guān)聯(lián)任務(wù)(上述A和B的關(guān)系)效率降低的情況塔猾。

協(xié)同調(diào)度適用于有關(guān)聯(lián)任務(wù)和依賴關(guān)系的場景中，然而并不是所有應(yīng)用場景都符合這些條件稽坤。協(xié)同調(diào)度很適用于并行計算(parallel computing)場景丈甸，即將任務(wù)切分成多個子任務(wù)并行執(zhí)行糯俗。
在并行計算中，整體同步并行(Bulk Synchronous parallelism, BSP)^[1]計算模型于協(xié)同調(diào)度十分契合睦擂，它將程序的執(zhí)行分為以下部分：

• 并發(fā)計算：每個核心獨(dú)立計算自己的子任務(wù)
• 通信：CPu核心之間通信交換數(shù)據(jù)
• 同步：一個核心執(zhí)行到某個節(jié)點(diǎn)需等待另一個核心執(zhí)行的任務(wù)到達(dá)這個點(diǎn)得湘，才能執(zhí)行后續(xù)任務(wù)。

當(dāng)前比較熱門的機(jī)器學(xué)習(xí)顿仇，圖計算淘正，大數(shù)據(jù)處理等方向都用到了BSP模型，因此協(xié)同調(diào)度也適用于這類場景臼闻。

1. 群組調(diào)度(gang scheduling)

群組策略就是協(xié)同調(diào)度的一種經(jīng)典策略鸿吆。其基本思想是將關(guān)聯(lián)任務(wù)設(shè)為一組，并以組為單位調(diào)度任務(wù)組在多個核心上執(zhí)行述呐，使得他們開始時間和結(jié)束時間接近相同惩淳。

通過將任務(wù)以組為單位在多核處理器上進(jìn)行調(diào)度，群組策略可以提升特定應(yīng)用場景的任務(wù)執(zhí)行性能乓搬。然而黎泣，在場景不匹配的情況下，它會要求無關(guān)聯(lián)的任務(wù)必須同時進(jìn)入或退出CPU核心缤谎，無關(guān)聯(lián)任務(wù)之間的相互等待可能造成CPU資源的浪費(fèi)抒倚。

兩級調(diào)度

為每個CPU核心都引入一個本地調(diào)度器，并用本地調(diào)度器管理對應(yīng)核心上的任務(wù)坷澡，再由全局調(diào)度器根據(jù)系統(tǒng)當(dāng)前信息托呕，諸如每個核心的負(fù)載情況，決定任務(wù)被哪個核心執(zhí)行频敛。這樣構(gòu)成了層級化結(jié)構(gòu)项郊，稱為兩級調(diào)度。

一個任務(wù)被分給某個核心執(zhí)行后就一直再那個核心里調(diào)度斟赚，不會遷移到其他核心着降，提高了緩存的局部性，減少了數(shù)據(jù)競爭的沖突（怎么減少的拗军？任洞？？）

以Linux為代表的一系列操作系統(tǒng)都會為每個CPU核心分配一個本地運(yùn)行隊列发侵，可以理解為每個核心有一個本地調(diào)度器交掏。

負(fù)載追蹤與負(fù)載均衡

兩級調(diào)度因?yàn)橐婚_始就給任務(wù)分配了核心，又不能切換核心刃鳄，可能會導(dǎo)致核心間負(fù)載不均盅弛。為解決這一問題需要為兩級調(diào)度引入負(fù)載均衡策略。通過追蹤每個核心當(dāng)前負(fù)載情況，將處于高負(fù)載的CPU核心管理的任務(wù)遷移到低負(fù)載的CPU核心上挪鹏，盡可能保證每個核心的負(fù)載大致相同见秽。

1. 調(diào)度實(shí)體粒度負(fù)載追蹤（Per-Entity Load Tracking, PELT）

負(fù)載均衡的一大挑戰(zhàn)就是如何確定當(dāng)前任務(wù)的負(fù)載情況。

Linux3.8以前讨盒，內(nèi)核以每個CPU核心的運(yùn)行隊列為粒度來計算負(fù)載张吉，認(rèn)為運(yùn)行隊列長的就是負(fù)載高，導(dǎo)致負(fù)載追蹤不夠精確催植。

在linux3.8以后，Linux使用了以調(diào)度實(shí)體（單個任務(wù)）為粒度的負(fù)載計算方式勺择，做到了更細(xì)粒度的負(fù)載追蹤创南。

PELT的計算方式:調(diào)度器以1024微秒為一個周期，記錄任務(wù)處于可運(yùn)行狀態(tài)（運(yùn)行狀態(tài)和待運(yùn)行狀態(tài)）的時間省核，記為x微秒稿辙。該任務(wù)在第i個周期(Ti)內(nèi)對CPU的利用率為x/1024，而對應(yīng)的負(fù)載Li為scale_cpu_capacity*x/1024其中scale_cpu_capacity是CPU的容量（用于歸一化系統(tǒng)中CPU的處理能力）气忠，可以理解為對應(yīng)CPU核心的處理能力邻储。

在收集到任務(wù)每個周期內(nèi)的負(fù)載后，PELT需要計算一段時間內(nèi)任務(wù)所有周期的累計負(fù)載旧噪，記為L吨娜。距離當(dāng)前時間越近的參考意義越大，所以在累加時給前面周期的負(fù)載乘以一個衰減系數(shù)y淘钟。具體公式如下：

L = L0+ L1y + L2y^2 + ...
化簡：L` = L + y * Ln
總體來說PELT的好處就是他的開銷很小宦赠，且能幫助調(diào)度器更細(xì)粒度、更精確的監(jiān)測任務(wù)的負(fù)載米母。

2. 負(fù)載均衡

雖然PELT提供了相對精確的負(fù)載追蹤勾扭，但是設(shè)計實(shí)現(xiàn)一個高效的負(fù)載均衡策略也絕非易事。

當(dāng)前計算機(jī)的核心數(shù)越來越多铁瞒，系統(tǒng)架構(gòu)越來越復(fù)雜妙色，不能簡單地對所有核心進(jìn)行均衡。

• 一方面慧耍，考慮大量核心的負(fù)載均衡會引入很大的開銷身辨，要盡可能的減小負(fù)載均衡的開銷
• CPU核心間是不對等的，任務(wù)在多核間遷移的開銷也不一樣芍碧，要盡量在開銷小的核心間遷移

• 在NUMA(非一致性內(nèi)存訪問)的多核系統(tǒng)架構(gòu)下栅表，CPU訪問不同類型節(jié)點(diǎn)內(nèi)存的速度是不相同的，訪問本地節(jié)點(diǎn)的速度最快师枣，訪問遠(yuǎn)端節(jié)點(diǎn)的速度最慢怪瓶，即訪問速度與節(jié)點(diǎn)的距離有關(guān)，距離越遠(yuǎn)訪問速度越慢，此距離稱作Node Distance洗贰。正是因?yàn)橛羞@個特點(diǎn)找岖，所以應(yīng)盡量在同一節(jié)點(diǎn)內(nèi)的核心做遷移。

  
  
  非一致性內(nèi)存訪問.png
• 在超線程技術(shù)中敛滋，一個物理核心在邏輯上被分為兩個邏輯核许布，在同屬一個物理核心的兩個邏輯核上遷移開銷較小。

Linux的負(fù)載均衡策略通過層級化的方法解決了上述問題绎晃，其使用了兩個數(shù)據(jù)結(jié)構(gòu)：

調(diào)度域：擁有相同特性的CPU核心的集合蜜唾，這些核心間可以進(jìn)行負(fù)載均衡。

調(diào)度組：一個調(diào)度域保存了一個或多個調(diào)度組庶艾，調(diào)度組是一個調(diào)度域內(nèi)進(jìn)行負(fù)載均衡的整體單位袁余。

越高層級的調(diào)度域之間的負(fù)載均衡開銷越大，Linux通過自下而上的方式層級地進(jìn)行負(fù)載均衡咱揍，并且為了設(shè)計簡單颖榜，只允許出發(fā)負(fù)載均衡的CPU核心拉去其他核心的任務(wù)到本地，而且為不同層級的調(diào)度域設(shè)置了不同的負(fù)載均衡觸發(fā)閾值和觸發(fā)頻率煤裙。

能耗感知調(diào)度

隨著移動掩完、嵌入式設(shè)備應(yīng)用越來越廣泛，能耗也成了一個非常重要的調(diào)度指標(biāo)硼砰。如何在保持低能耗的情況下還能有著良好的性能表現(xiàn)是一個值得研究的問題且蓬。

混合處理器架構(gòu)十分適用在移動、嵌入式設(shè)備上题翰，架構(gòu)一般包含大核和小核兩種計算單元缅疟。大核處理速度更快，能耗更高遍愿，相對的小核性能較弱能耗較低但是續(xù)航能力強(qiáng)存淫。這種混合處理器架構(gòu)為調(diào)度器提供了優(yōu)化系統(tǒng)能耗的機(jī)會。

1. Linux的能耗感知調(diào)度(Energy Aware Scheduling,EAS)

ESA擴(kuò)展了Linux當(dāng)前使用的完全公平調(diào)度器沼填。在混合處理器機(jī)構(gòu)中桅咆，任務(wù)被放到不同核心中執(zhí)行帶來的能耗開銷是不同的，為了保證系統(tǒng)性能同時達(dá)到低能耗坞笙，調(diào)度器通過EAS決定任務(wù)在哪個核心上執(zhí)行岩饼。

ESA需要使用當(dāng)前處理器架構(gòu)的能耗模型(energy model)來了解每個CPU的容量（核心處理能力）和功率。

• 容量：當(dāng)前CPU核心在當(dāng)前頻率下的處理能力薛夜。容量被標(biāo)準(zhǔn)化在0~1024的范圍內(nèi)籍茧，整個系統(tǒng)內(nèi)最強(qiáng)核心在最高頻率下工作的容量是1024。CPU容量的單位與PELT機(jī)制追蹤的負(fù)載單位是統(tǒng)一的梯澜，即一個容量為1024的核心在一個單位時間內(nèi)可以處理一個負(fù)載1024的任務(wù)寞冯。通過CPU核心容量和PELT的負(fù)載信息，ESA可以最大限度的在不影響性能的情況下進(jìn)行降低能耗的調(diào)度。
• 功率：當(dāng)前CPU核心在當(dāng)前頻率下的功率吮龄，單位是毫瓦(mW)俭茧。通過功率以及任務(wù)所需完成的時間，可以計算出CPU核心完成任務(wù)所需的能耗漓帚。

更具體的母债，系統(tǒng)的CPU核心會被劃分為多個性能域(Performance Domain, PD),同一個性能域內(nèi)的核心具有相同的容量和功率的對應(yīng)關(guān)系，共用同一套能耗模型尝抖。

CPU核心的頻率是可以改變的毡们。一個能耗模型中有多個操作性能點(diǎn)(Operating Performance Point, OPP.其實(shí)這個點(diǎn)只得就是核心的某一頻率和電壓，讓核心只能在這幾個性能點(diǎn)之間切換)昧辽，相同性能域的核心在同一時間必須處于相同頻率衙熔。


下表為某混合處理器架構(gòu)能耗模型，該模型有兩個性能域奴迅，PD0對應(yīng)大核，PD1對應(yīng)小核挺据，每個性能域有三個OPP取具。假設(shè)現(xiàn)在有個任務(wù)性能需求實(shí)在一個單位時間內(nèi)執(zhí)行完畢，且當(dāng)前所有核心負(fù)載是0扁耐。通過PELT計算該任務(wù)的負(fù)載是200暇检，如何選擇核心和核心頻率？

可選容量為384的大核婉称，能耗為200/384300=156;選容量為256的小核能耗為200/256180=141块仆；所以選小核。

但是并不是任何時候都是選小核心能耗就地王暗，當(dāng)任務(wù)負(fù)載時300時就是大核更優(yōu)悔据。

表1：某混合處理器架構(gòu)能耗模型

EAS適用于中低負(fù)載場景。如果當(dāng)前所有核心都高負(fù)荷或滿負(fù)荷狀態(tài)俗壹，EAS是沒有空間進(jìn)行負(fù)載均衡的科汗。當(dāng)任一CPU核心的當(dāng)前負(fù)載超過80%的最高容量時，Linux會關(guān)閉EAS開啟負(fù)載均衡绷雏，反之則反头滔。

調(diào)度進(jìn)階機(jī)制

于單核調(diào)多調(diào)基礎(chǔ)操作系還提更調(diào)機(jī)主要程提接來影調(diào)決。

1. 處理器親和性(Processer affinity)

開發(fā)者更了解自己的程序涎显，他不希望調(diào)度器這樣調(diào)度坤检，為了更好的性能想按照自己的方法去調(diào)度。操作系統(tǒng)提供了處理器親和性的機(jī)制期吓，允許程序?qū)θ蝿?wù)可以使用的CPU核心進(jìn)行配置早歇。

在Linux中，任務(wù)通過設(shè)置cpu_set_t掩碼來表示可以執(zhí)行任務(wù)的核心的集合。

#include <sched.h>
// 對set初始化缺前，設(shè)置為空
void CPU_ZERO(cpu_set_t *set);
// 將對應(yīng)cpu核心加入set
void CPU_SET(int cpu, cpu_set_t *set);
// 將對應(yīng)cpu核心移出set
void CPU_CLR(int cpu, CPU_SET_T *set);
// 對應(yīng)cpu核心是否在set中
int CPU_ISSET(int cpu, cpu_set_t *set);
// 當(dāng)前set中核心的數(shù)量
int CPU_COUNT(cpu_set_t *set);
...

#include <sched.h>
// 設(shè)置任務(wù)對CPU核心的親和性蛀醉，pid為0代表當(dāng)前線程
int sched_setaffinity(pid_t pid, size_t cpusetsize, const cpu_set_t *mask);
// 獲得任務(wù)的親和性配置
int sched_getaffinity(pid_t pid, size_t cpusetsize, cpu_set_t *mask);

#include <sched.h>
#include <stdio.h>
#include <sys/sysinfo.h>
int main(){
    cpu_set_t mask;
    CPU_ZERO();
    CPU_SET(0, &mask);
    CPU_SET(2, &mask);
    sched_setaffinity(0, sizeof(mask), &mask);
}

2. 調(diào)度策略設(shè)置

Linux支持多種調(diào)度策略和調(diào)度器，允許程序根據(jù)不同場景選擇衅码。Linux主要提供完全公平調(diào)度器(Copletely Fair Scheduler,CFS)拯刁、實(shí)時調(diào)度器(Real-Time scheduler, RT)、截止時間調(diào)度器(DeadLine scheduler, DL)逝段。Linux也支持對不同任務(wù)設(shè)置不同的調(diào)度策略垛玻。
| 調(diào)度器 | 調(diào)度策略 | 描述 |
| ------ | -------------- | ---------------------------------- |
| CFS | SCHED_OTHER | 公平的分時調(diào)度策略 |
| CFS | SCHED_BATCH | 針對不會與用戶交互的批處理任務(wù) |
| CFS | SCHED_IDLE | 針對優(yōu)先級低的后臺任務(wù) |
| RT | SCHED_FIFO | 執(zhí)行直到結(jié)束或被更高優(yōu)先級任務(wù)搶占 |
| RT | SCHED_RR | 執(zhí)行一定時間片后不再執(zhí)行 |
| DL | SCHED_DEADLINE | 類似EDF的調(diào)度策略 |

#include <sched.h>
struct sched_attr{
    ...
    u32 sched_policy;
    ...
    // SCHED_OTHER, SCHED_BATCH
    s32 shced_nice;
    // SCHED_FIFO, SCHED_RR
    u32 shced_priority;
    // SCHED_DEADLINE
    u64 shced_runtime;
    u64 shced_deadline;
    u64 shced_period;
};
int sched_setattr(pid_t pid,
                    const struct shced_attr *attr,
                    unsigned int flags);
int sched_getattr(pid_t pid,
                    const struct shced_attr *attr,
                    unsigned int size,
                    unsigned int flags);

現(xiàn)代調(diào)度器

Linux的調(diào)度器

MacOS/IOS調(diào)度器

//TODO 未完待續(xù)

1. Leslie G Valiant. A bridging model for parallel computation [J]. Communications of the ACM,1990,33(8):103-111. DOI:10.1145/79173.79181 ?