本章將介紹多處理器調(diào)度（multiprocessor scheduling）的基礎(chǔ)知識(shí)。由于本章內(nèi)容相對(duì)較深，建議認(rèn)真學(xué)習(xí)并發(fā)相關(guān)的內(nèi)容后再讀。

過去很多年，多處理器（multiprocessor）系統(tǒng)只存在于高端服務(wù)器中?，F(xiàn)在，它們?cè)絹碓蕉嗟爻霈F(xiàn)在個(gè)人PC、筆記本電腦甚至移動(dòng)設(shè)備上。多核處理器（multicore）將多個(gè)CPU核組裝在一塊芯片上，是這種擴(kuò)散的根源。由于計(jì)算機(jī)的架構(gòu)師們當(dāng)時(shí)難以讓單核CPU更快，同時(shí)又不增加太多功耗，所以這種多核CPU很快就變得流行?，F(xiàn)在，我們每個(gè)人都可以得到一些CPU，這是好事，對(duì)吧？

當(dāng)然，多核CPU帶來了許多困難。主要困難是典型的應(yīng)用程序（例如你寫的很多C程序）都只使用一個(gè)CPU，增加了更多的CPU并沒有讓這類程序運(yùn)行得更快。為了解決這個(gè)問題，不得不重寫這些應(yīng)用程序，使之能并行（parallel）執(zhí)行，也許使用多線程（thread，本書的第2部分將用較多篇幅討論）。多線程應(yīng)用可以將工作分散到多個(gè)CPU上，因此CPU資源越多就運(yùn)行越快。

補(bǔ)充：高級(jí)章節(jié)

需要閱讀本書的更多內(nèi)容才能真正理解高級(jí)章節(jié)，但這些內(nèi)容在邏輯上放在一章里。例如，本章是關(guān)于多處理器調(diào)度的，如果先學(xué)習(xí)了中間部分的并發(fā)知識(shí)，會(huì)更有意思。但是，從邏輯上它屬于本書中虛擬化（一般）和CPU調(diào)度（具體）的部分。因此，建議不按順序?qū)W習(xí)這些高級(jí)章節(jié)。對(duì)于本章，建議在本書第2部分之后學(xué)習(xí)。

除了應(yīng)用程序，操作系統(tǒng)遇到的一個(gè)新的問題是（不奇怪！）多處理器調(diào)度（multiprocessor scheduling）。到目前為止，我們討論了許多單處理器調(diào)度的原則，那么如何將這些想法擴(kuò)展到多處理器上呢？還有什么新的問題需要解決？因此，我們的問題如下。

關(guān)鍵問題：如何在多處理器上調(diào)度工作

操作系統(tǒng)應(yīng)該如何在多CPU上調(diào)度工作？會(huì)遇到什么新問題？已有的技術(shù)依舊適用嗎？是否需要新的思路？

空間局部性。時(shí)間局部性是指當(dāng)一個(gè)數(shù)據(jù)被訪問后，它很有可能會(huì)在不久的將來被再次訪問，比如循環(huán)代碼中的數(shù)據(jù)或指令本身。而空間局部性指的是，當(dāng)程序訪問地址為x

的數(shù)據(jù)時(shí)，很有可能會(huì)緊接著訪問x

周圍的數(shù)據(jù)，比如遍歷數(shù)組或指令的順序執(zhí)行。由于這兩種局部性存在于大多數(shù)的程序中，硬件系統(tǒng)可以很好地預(yù)測(cè)哪些數(shù)據(jù)可以放入緩存，從而運(yùn)行得很好。

有趣的部分來了：如果系統(tǒng)有多個(gè)處理器，并共享同一個(gè)內(nèi)存，如圖10.2所示，會(huì)怎樣呢？

圖10.1　帶緩存的單CPU

圖10.2　兩個(gè)有緩存的CPU共享內(nèi)存

事實(shí)證明，多CPU的情況下緩存要復(fù)雜得多。例如，假設(shè)一個(gè)運(yùn)行在CPU 1上的程序從內(nèi)存地址A讀取數(shù)據(jù)。由于不在CPU 1的緩存中，所以系統(tǒng)直接訪問內(nèi)存，得到值D

。程序然后修改了地址A處的值，只是將它的緩存更新為新值D'

。將數(shù)據(jù)寫回內(nèi)存比較慢，因此系統(tǒng)（通常）會(huì)稍后再做。假設(shè)這時(shí)操作系統(tǒng)中斷了該程序的運(yùn)行，并將其交給CPU 2，重新讀取地址A的數(shù)據(jù)，由于CPU 2的緩存中并沒有該數(shù)據(jù)，所以會(huì)直接從內(nèi)存中讀取，得到了舊值D

，而不是正確的值D'

。哎呀！

這一普遍的問題稱為緩存一致性（cache coherence）問題，有大量的研究文獻(xiàn)描述了解決這個(gè)問題時(shí)的微妙之處[SHW11]。這里我們會(huì)略過所有的細(xì)節(jié)，只提幾個(gè)要點(diǎn)。選一門計(jì)算機(jī)體系結(jié)構(gòu)課（或3門），你可以了解更多。

硬件提供了這個(gè)問題的基本解決方案：通過監(jiān)控內(nèi)存訪問，硬件可以保證獲得正確的數(shù)據(jù)，并保證共享內(nèi)存的唯一性。在基于總線的系統(tǒng)中，一種方式是使用總線窺探（bus snooping）[G83]。每個(gè)緩存都通過監(jiān)聽鏈接所有緩存和內(nèi)存的總線，來發(fā)現(xiàn)內(nèi)存訪問。如果CPU發(fā)現(xiàn)對(duì)它放在緩存中的數(shù)據(jù)的更新，會(huì)作廢（invalidate）本地副本（從緩存中移除），或更新（update）它（修改為新值）?；貙懢彺?，如上面提到的，讓事情更復(fù)雜（由于對(duì)內(nèi)存的寫入稍后才會(huì)看到），你可以想想基本方案如何工作。

一段時(shí)間后，假設(shè)每個(gè)工作依次執(zhí)行一個(gè)時(shí)間片，然后選擇另一個(gè)工作，下面是每個(gè)CPU可能的調(diào)度序列：

由于每個(gè)CPU都簡(jiǎn)單地從全局共享的隊(duì)列中選取下一個(gè)工作執(zhí)行，因此每個(gè)工作都不斷在不同CPU之間轉(zhuǎn)移，這與緩存親和的目標(biāo)背道而馳。

為了解決這個(gè)問題，大多數(shù)SQMS調(diào)度程序都引入了一些親和度機(jī)制，盡可能讓進(jìn)程在同一個(gè)CPU上運(yùn)行。保持一些工作的親和度的同時(shí)，可能需要犧牲其他工作的親和度來實(shí)現(xiàn)負(fù)載均衡。例如，針對(duì)同樣的5個(gè)工作的調(diào)度如下：

這種調(diào)度中，A、B、C、D 這4個(gè)工作都保持在同一個(gè)CPU上，只有工作E不斷地來回遷移（migrating），從而盡可能多地獲得緩存親和度。為了公平起見，之后我們可以選擇不同的工作來遷移。但實(shí)現(xiàn)這種策略可能很復(fù)雜。

我們看到，SQMS調(diào)度方式有優(yōu)勢(shì)也有不足。優(yōu)勢(shì)是能夠從單CPU調(diào)度程序很簡(jiǎn)單地發(fā)展而來，根據(jù)定義，它只有一個(gè)隊(duì)列。然而，它的擴(kuò)展性不好（由于同步開銷有限），并且不能很好地保證緩存親和度。

10.5　多隊(duì)列調(diào)度

正是由于單隊(duì)列調(diào)度程序的這些問題，有些系統(tǒng)使用了多隊(duì)列的方案，比如每個(gè)CPU一個(gè)隊(duì)列。我們稱之為多隊(duì)列多處理器調(diào)度（Multi-Queue Multiprocessor Scheduling，MQMS）

在MQMS中，基本調(diào)度框架包含多個(gè)調(diào)度隊(duì)列，每個(gè)隊(duì)列可以使用不同的調(diào)度規(guī)則，比如輪轉(zhuǎn)或其他任何可能的算法。當(dāng)一個(gè)工作進(jìn)入系統(tǒng)后，系統(tǒng)會(huì)依照一些啟發(fā)性規(guī)則（如隨機(jī)或選擇較空的隊(duì)列）將其放入某個(gè)調(diào)度隊(duì)列。這樣一來，每個(gè)CPU調(diào)度之間相互獨(dú)立，就避免了單隊(duì)列的方式中由于數(shù)據(jù)共享及同步帶來的問題。

例如，假設(shè)系統(tǒng)中有兩個(gè)CPU（CPU 0和CPU 1）。這時(shí)一些工作進(jìn)入系統(tǒng)：A、B、C和D。由于每個(gè)CPU都有自己的調(diào)度隊(duì)列，操作系統(tǒng)需要決定每個(gè)工作放入哪個(gè)隊(duì)列。可能像下面這樣做：

根據(jù)不同隊(duì)列的調(diào)度策略，每個(gè)CPU從兩個(gè)工作中選擇，決定誰將運(yùn)行。例如，利用輪轉(zhuǎn)，調(diào)度結(jié)果可能如下所示：

MQMS比SQMS有明顯的優(yōu)勢(shì)，它天生更具有可擴(kuò)展性。隊(duì)列的數(shù)量會(huì)隨著CPU的增加而增加，因此鎖和緩存爭(zhēng)用的開銷不是大問題。此外，MQMS天生具有良好的緩存親和度。所有工作都保持在固定的CPU上，因而可以很好地利用緩存數(shù)據(jù)。

但是，如果稍加注意，你可能會(huì)發(fā)現(xiàn)有一個(gè)新問題（這在多隊(duì)列的方法中是根本的），即負(fù)載不均（load imbalance）。假定和上面設(shè)定一樣（4個(gè)工作，2個(gè)CPU），但假設(shè)一個(gè)工作（如C）這時(shí)執(zhí)行完畢?，F(xiàn)在調(diào)度隊(duì)列如下：

如果對(duì)系統(tǒng)中每個(gè)隊(duì)列都執(zhí)行輪轉(zhuǎn)調(diào)度策略，會(huì)獲得如下調(diào)度結(jié)果：

從圖中可以看出，A獲得了B和D兩倍的CPU時(shí)間，這不是期望的結(jié)果。更糟的是，假設(shè)A和C都執(zhí)行完畢，系統(tǒng)中只有B和D。調(diào)度隊(duì)列看起來如下：

因此CPU使用時(shí)間線看起來令人難過：

所以可憐的多隊(duì)列多處理器調(diào)度程序應(yīng)該怎么辦呢？怎樣才能克服潛伏的負(fù)載不均問題，打敗邪惡的……霸天虎軍團(tuán)[1]

？如何才能不要問這些與這本好書幾乎無關(guān)的問題？

關(guān)鍵問題：如何應(yīng)對(duì)負(fù)載不均

多隊(duì)列多處理器調(diào)度程序應(yīng)該如何處理負(fù)載不均問題，從而更好地實(shí)現(xiàn)預(yù)期的調(diào)度目標(biāo)？

最明顯的答案是讓工作移動(dòng)，這種技術(shù)我們稱為遷移（migration）。通過工作的跨CPU遷移，可以真正實(shí)現(xiàn)負(fù)載均衡。

來看兩個(gè)例子就更清楚了。同樣，有一個(gè)CPU空閑，另一個(gè)CPU有一些工作。

在這種情況下，期望的遷移很容易理解：操作系統(tǒng)應(yīng)該將B或D遷移到CPU0。這次工作遷移導(dǎo)致負(fù)載均衡，皆大歡喜。

更棘手的情況是較早一些的例子，A獨(dú)自留在CPU 0上，B和D在CPU 1上交替運(yùn)行。

在這種情況下，單次遷移并不能解決問題。應(yīng)該怎么做呢？答案是不斷地遷移一個(gè)或多個(gè)工作。一種可能的解決方案是不斷切換工作，如下面的時(shí)間線所示?？梢钥吹剑_始的時(shí)候A獨(dú)享CPU 0，B和D在CPU 1。一些時(shí)間片后，B遷移到CPU 0與A競(jìng)爭(zhēng)，D則獨(dú)享CPU 1一段時(shí)間。這樣就實(shí)現(xiàn)了負(fù)載均衡。

當(dāng)然，還有其他不同的遷移模式。但現(xiàn)在是最棘手的部分：系統(tǒng)如何決定發(fā)起這樣的遷移？

一個(gè)基本的方法是采用一種技術(shù)，名為工作竊取（work stealing）[FLR98]。通過這種方法，工作量較少的（源）隊(duì)列不定期地“偷看”其他（目標(biāo)）隊(duì)列是不是比自己的工作多。如果目標(biāo)隊(duì)列比源隊(duì)列（顯著地）更滿，就從目標(biāo)隊(duì)列“竊取”一個(gè)或多個(gè)工作，實(shí)現(xiàn)負(fù)載均衡。

當(dāng)然，這種方法也有讓人抓狂的地方——如果太頻繁地檢查其他隊(duì)列，就會(huì)帶來較高的開銷，可擴(kuò)展性不好，而這是多隊(duì)列調(diào)度最初的全部目標(biāo)！相反，如果檢查間隔太長(zhǎng)，又可能會(huì)帶來嚴(yán)重的負(fù)載不均。找到合適的閾值仍然是黑魔法，這在系統(tǒng)策略設(shè)計(jì)中很常見。

10.7　小結(jié)

本章介紹了多處理器調(diào)度的不同方法。其中單隊(duì)列的方式（SQMS）比較容易構(gòu)建，負(fù)載均衡較好，但在擴(kuò)展性和緩存親和度方面有著固有的缺陷。多隊(duì)列的方式（MQMS）有很好的擴(kuò)展性和緩存親和度，但實(shí)現(xiàn)負(fù)載均衡卻很困難，也更復(fù)雜。無論采用哪種方式，都沒有簡(jiǎn)單的答案：構(gòu)建一個(gè)通用的調(diào)度程序仍是一項(xiàng)令人生畏的任務(wù)，因?yàn)榧词购苄〉拇a變動(dòng)，也有可能導(dǎo)致巨大的行為差異。除非很清楚自己在做什么，或者有人付你很多錢，否則別干這種事。

網(wǎng)頁標(biāo)題：操作系統(tǒng)應(yīng)該如何在多CPU上調(diào)度工作？
文章URL：http://www.rwnh.cn/news3/104103.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、網(wǎng)站維護(hù)、服務(wù)器托管、小程序開發(fā)、域名注冊(cè)、定制網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)