操作系統(tǒng)應該如何在多CPU上調度工作？

本章將介紹多處理器調度（multiprocessor scheduling）的基礎知識。由于本章內(nèi)容相對較深，建議認真學習并發(fā)相關的內(nèi)容后再讀。

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

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

補充：高級章節(jié)

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

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

關鍵問題：如何在多處理器上調度工作

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

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

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

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

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

圖10.1　帶緩存的單CPU

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

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

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

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

，而不是正確的值D'

。哎呀！

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

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

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

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

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

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

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

10.5　多隊列調度

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

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

例如，假設系統(tǒng)中有兩個CPU（CPU 0和CPU 1）。這時一些工作進入系統(tǒng)：A、B、C和D。由于每個CPU都有自己的調度隊列，操作系統(tǒng)需要決定每個工作放入哪個隊列?？赡芟裣旅孢@樣做：

根據(jù)不同隊列的調度策略，每個CPU從兩個工作中選擇，決定誰將運行。例如，利用輪轉，調度結果可能如下所示：

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

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

如果對系統(tǒng)中每個隊列都執(zhí)行輪轉調度策略，會獲得如下調度結果：

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

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

所以可憐的多隊列多處理器調度程序應該怎么辦呢？怎樣才能克服潛伏的負載不均問題，打敗邪惡的……霸天虎軍團[1]

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

關鍵問題：如何應對負載不均

多隊列多處理器調度程序應該如何處理負載不均問題，從而更好地實現(xiàn)預期的調度目標？

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

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

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

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

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

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

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

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

10.7　小結

本章介紹了多處理器調度的不同方法。其中單隊列的方式（SQMS）比較容易構建，負載均衡較好，但在擴展性和緩存親和度方面有著固有的缺陷。多隊列的方式（MQMS）有很好的擴展性和緩存親和度，但實現(xiàn)負載均衡卻很困難，也更復雜。無論采用哪種方式，都沒有簡單的答案：構建一個通用的調度程序仍是一項令人生畏的任務，因為即使很小的代碼變動，也有可能導致巨大的行為差異。除非很清楚自己在做什么，或者有人付你很多錢，否則別干這種事。

網(wǎng)頁標題：操作系統(tǒng)應該如何在多CPU上調度工作？
文章URL：http://www.bm7419.com/news3/104103.html

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

廣告

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