操作系統(tǒng)應該如何在多CPU上調(diào)度工作？
本章將介紹多處理器調(diào)度(multiprocessor scheduling)的基礎知識。由于本章內(nèi)容相對較深，建議認真學習并發(fā)相關的內(nèi)容后再讀。
過去很多年，多處理器(multiprocessor)系統(tǒng)只存在于高端服務器中。現(xiàn)在，它們越來越多地出現(xiàn)在個人PC、筆記本電腦甚至移動設備上。多核處理器(multicore)將多個CPU核組裝在一塊芯片上，是這種擴散的根源。由于計算機的架構師們當時難以讓單核CPU更快，同時又不增加太多功耗，所以這種多核CPU很快就變得流行。現(xiàn)在，我們每個人都可以得到一些CPU，這是好事，對吧?
當然，多核CPU帶來了許多困難。主要困難是典型的應用程序(例如你寫的很多C程序)都只使用一個CPU，增加了更多的CPU并沒有讓這類程序運行得更快。為了解決這個問題，不得不重寫這些應用程序，使之能并行(parallel)執(zhí)行，也許使用多線程(thread，本書的第2部分將用較多篇幅討論)。多線程應用可以將工作分散到多個CPU上，因此CPU資源越多就運行越快。
補充：高級章節(jié)
需要閱讀本書的更多內(nèi)容才能真正理解高級章節(jié)，但這些內(nèi)容在邏輯上放在一章里。例如，本章是關于多處理器調(diào)度的，如果先學習了中間部分的并發(fā)知識，會更有意思。但是，從邏輯上它屬于本書中虛擬化(一般)和CPU調(diào)度(具體)的部分。因此，建議不按順序?qū)W習這些高級章節(jié)。對于本章，建議在本書第2部分之后學習。
除了應用程序，操作系統(tǒng)遇到的一個新的問題是(不奇怪!)多處理器調(diào)度(multiprocessor scheduling)。到目前為止，我們討論了許多單處理器調(diào)度的原則，那么如何將這些想法擴展到多處理器上呢?還有什么新的問題需要解決?因此，我們的問題如下。
關鍵問題：如何在多處理器上調(diào)度工作
操作系統(tǒng)應該如何在多CPU上調(diào)度工作?會遇到什么新問題?已有的技術依舊適用嗎?是否需要新的思路?
10.1 背景：多處理器架構
為了理解多處理器調(diào)度帶來的新問題，必須先知道它與單CPU之間的基本區(qū)別。區(qū)別的核心在于對硬件緩存(cache)的使用(見圖10.1)，以及多處理器之間共享數(shù)據(jù)的方式。本章將在較高層面討論這些問題。更多信息可以其他地方找到[CSG99]，尤其是在高年級或研究生計算機架構課程中。
在單CPU系統(tǒng)中，存在多級的硬件緩存(hardware cache)，一般來說會讓處理器更快地執(zhí)行程序。緩存是很小但很快的存儲設備，通常擁有內(nèi)存中最熱的數(shù)據(jù)的備份。相比之下，內(nèi)存很大且擁有所有的數(shù)據(jù)，但訪問速度較慢。通過將頻繁訪問的數(shù)據(jù)放在緩存中，系統(tǒng)似乎擁有又大又快的內(nèi)存。
舉個例子，假設一個程序需要從內(nèi)存中加載指令并讀取一個值，系統(tǒng)只有一個CPU，擁有較小的緩存(如64KB)和較大的內(nèi)存。
程序***次讀取數(shù)據(jù)時，數(shù)據(jù)在內(nèi)存中，因此需要花費較長的時間(可能數(shù)十或數(shù)百納秒)。處理器判斷該數(shù)據(jù)很可能會被再次使用，因此將其放入CPU緩存中。如果之后程序再次需要使用同樣的數(shù)據(jù)，CPU會先查找緩存。因為在緩存中找到了數(shù)據(jù)，所以取數(shù)據(jù)快得多(比如幾納秒)，程序也就運行更快。
緩存是基于局部性(locality)的概念，局部性有兩種，即時間局部性和空間局部性。時間局部性是指當一個數(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é)，只提幾個要點。選一門計算機體系結(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)存的寫入稍后才會看到)，你可以想想基本方案如何工作。
10.2 別忘了同步
既然緩存已經(jīng)做了這么多工作來提供一致性，應用程序(或操作系統(tǒng))還需要關心共享數(shù)據(jù)的訪問嗎?依然需要!本書第2部分關于并發(fā)的描述中會詳細介紹。雖然這里不會詳細討論，但我們會簡單介紹(或復習)下其基本思路(假設你熟悉并發(fā)相關內(nèi)容)。
跨CPU訪問(尤其是寫入)共享數(shù)據(jù)或數(shù)據(jù)結(jié)構時，需要使用互斥原語(比如鎖)，才能保證正確性(其他方法，如使用無鎖(lock-free)數(shù)據(jù)結(jié)構，很復雜，偶爾才使用。詳情參見并發(fā)部分關于死鎖的章節(jié))。例如，假設多CPU并發(fā)訪問一個共享隊列。如果沒有鎖，即使有底層一致性協(xié)議，并發(fā)地從隊列增加或刪除元素，依然不會得到預期結(jié)果。需要用鎖來保證數(shù)據(jù)結(jié)構狀態(tài)更新的原子性。
為了更具體，我們設想這樣的代碼序列，用于刪除共享鏈表的一個元素，如圖10.3所示。假設兩個CPU上的不同線程同時進入這個函數(shù)。如果線程1執(zhí)行***行，會將head的當前值存入它的tmp變量。如果線程2接著也執(zhí)行***行，它也會將同樣的head值存入它自己的私有tmp變量(tmp在棧上分配，因此每個線程都有自己的私有存儲)。因此，兩個線程會嘗試刪除同一個鏈表頭，而不是每個線程移除一個元素，這導致了各種問題(比如在第4行重復釋放頭元素，以及可能兩次返回同一個數(shù)據(jù))。
- typedef struct __Node_t {
- int value;
- struct __Node_t *next;
- } Node_t;
- int List_Pop() {
- Node_t *tmp = head; // remember old head ...
- int value = head->value; // ... and its value
- head = head->next; // advance head to next pointer
- free(tmp); // free old head
- return value; // return value at head
- }
圖10.3 簡單的鏈表刪除代碼
當然，讓這類函數(shù)正確工作的方法是加鎖(locking)。這里只需要一個互斥鎖(即pthread_mutex_t m;)，然后在函數(shù)開始時調(diào)用lock(&m)，在結(jié)束時調(diào)用unlock(&m)，確保代碼的執(zhí)行如預期。我們會看到，這里依然有問題，尤其是性能方面。具體來說，隨著CPU數(shù)量的增加，訪問同步共享的數(shù)據(jù)結(jié)構會變得很慢。
10.3 ***一個問題：緩存親和度
在設計多處理器調(diào)度時遇到的***一個問題，是所謂的緩存親和度(cache affinity)。這個概念很簡單：一個進程在某個CPU上運行時，會在該CPU的緩存中維護許多狀態(tài)。下次該進程在相同CPU上運行時，由于緩存中的數(shù)據(jù)而執(zhí)行得更快。相反，在不同的CPU上執(zhí)行，會由于需要重新加載數(shù)據(jù)而很慢(好在硬件保證的緩存一致性可以保證正確執(zhí)行)。因此多處理器調(diào)度應該考慮到這種緩存親和性，并盡可能將進程保持在同一個CPU上。
10.4 單隊列調(diào)度
上面介紹了一些背景，現(xiàn)在來討論如何設計一個多處理器系統(tǒng)的調(diào)度程序。最基本的方式是簡單地復用單處理器調(diào)度的基本架構，將所有需要調(diào)度的工作放入一個單獨的隊列中，我們稱之為單隊列多處理器調(diào)度(Single Queue Multiprocessor Scheduling，SQMS)。這個方法***的優(yōu)點是簡單。它不需要太多修改，就可以將原有的策略用于多個CPU，選擇最適合的工作來運行(例如，如果有兩個CPU，它可能選擇兩個最合適的工作)。
然而，SQMS有幾個明顯的短板。***個是缺乏可擴展性(scalability)。為了保證在多CPU上正常運行，調(diào)度程序的開發(fā)者需要在代碼中通過加鎖(locking)來保證原子性，如上所述。在SQMS訪問單個隊列時(如尋找下一個運行的工作)，鎖確保得到正確的結(jié)果。
然而，鎖可能帶來巨大的性能損失，尤其是隨著系統(tǒng)中的CPU數(shù)增加時[A91]。隨著這種單個鎖的爭用增加，系統(tǒng)花費了越來越多的時間在鎖的開銷上，較少的時間用于系統(tǒng)應該完成的工作(哪天在這里加上真正的測量數(shù)據(jù)就好了)。
SQMS的第二個主要問題是緩存親和性。比如，假設我們有5個工作(A、B、C、D、E)和4個處理器。調(diào)度隊列如下：
一段時間后，假設每個工作依次執(zhí)行一個時間片，然后選擇另一個工作，下面是每個CPU可能的調(diào)度序列：
由于每個CPU都簡單地從全局共享的隊列中選取下一個工作執(zhí)行，因此每個工作都不斷在不同CPU之間轉(zhuǎn)移，這與緩存親和的目標背道而馳。
為了解決這個問題，大多數(shù)SQMS調(diào)度程序都引入了一些親和度機制，盡可能讓進程在同一個CPU上運行。保持一些工作的親和度的同時，可能需要犧牲其他工作的親和度來實現(xiàn)負載均衡。例如，針對同樣的5個工作的調(diào)度如下：
這種調(diào)度中，A、B、C、D 這4個工作都保持在同一個CPU上，只有工作E不斷地來回遷移(migrating)，從而盡可能多地獲得緩存親和度。為了公平起見，之后我們可以選擇不同的工作來遷移。但實現(xiàn)這種策略可能很復雜。
我們看到，SQMS調(diào)度方式有優(yōu)勢也有不足。優(yōu)勢是能夠從單CPU調(diào)度程序很簡單地發(fā)展而來，根據(jù)定義，它只有一個隊列。然而，它的擴展性不好(由于同步開銷有限)，并且不能很好地保證緩存親和度。
10.5 多隊列調(diào)度
正是由于單隊列調(diào)度程序的這些問題，有些系統(tǒng)使用了多隊列的方案，比如每個CPU一個隊列。我們稱之為多隊列多處理器調(diào)度(Multi-Queue Multiprocessor Scheduling，MQMS)
在MQMS中，基本調(diào)度框架包含多個調(diào)度隊列，每個隊列可以使用不同的調(diào)度規(guī)則，比如輪轉(zhuǎn)或其他任何可能的算法。當一個工作進入系統(tǒng)后，系統(tǒng)會依照一些啟發(fā)性規(guī)則(如隨機或選擇較空的隊列)將其放入某個調(diào)度隊列。這樣一來，每個CPU調(diào)度之間相互獨立，就避免了單隊列的方式中由于數(shù)據(jù)共享及同步帶來的問題。
例如，假設系統(tǒng)中有兩個CPU(CPU 0和CPU 1)。這時一些工作進入系統(tǒng)：A、B、C和D。由于每個CPU都有自己的調(diào)度隊列，操作系統(tǒng)需要決定每個工作放入哪個隊列。可能像下面這樣做：
根據(jù)不同隊列的調(diào)度策略，每個CPU從兩個工作中選擇，決定誰將運行。例如，利用輪轉(zhuǎn)，調(diào)度結(jié)果可能如下所示：
MQMS比SQMS有明顯的優(yōu)勢，它天生更具有可擴展性。隊列的數(shù)量會隨著CPU的增加而增加，因此鎖和緩存爭用的開銷不是大問題。此外，MQMS天生具有良好的緩存親和度。所有工作都保持在固定的CPU上，因而可以很好地利用緩存數(shù)據(jù)。
但是，如果稍加注意，你可能會發(fā)現(xiàn)有一個新問題(這在多隊列的方法中是根本的)，即負載不均(load imbalance)。假定和上面設定一樣(4個工作，2個CPU)，但假設一個工作(如C)這時執(zhí)行完畢。現(xiàn)在調(diào)度隊列如下：
如果對系統(tǒng)中每個隊列都執(zhí)行輪轉(zhuǎn)調(diào)度策略，會獲得如下調(diào)度結(jié)果：
從圖中可以看出，A獲得了B和D兩倍的CPU時間，這不是期望的結(jié)果。更糟的是，假設A和C都執(zhí)行完畢，系統(tǒng)中只有B和D。調(diào)度隊列看起來如下：
因此CPU使用時間線看起來令人難過：
所以可憐的多隊列多處理器調(diào)度程序應該怎么辦呢?怎樣才能克服潛伏的負載不均問題，打敗邪惡的……霸天虎軍團[1]
- 如何才能不要問這些與這本好書幾乎無關的問題?
關鍵問題：如何應對負載不均
多隊列多處理器調(diào)度程序應該如何處理負載不均問題，從而更好地實現(xiàn)預期的調(diào)度目標?
最明顯的答案是讓工作移動，這種技術我們稱為遷移(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ā)起這樣的遷移?
一個基本的方法是采用一種技術，名為工作竊取(work stealing)[FLR98]。通過這種方法，工作量較少的(源)隊列不定期地“偷看”其他(目標)隊列是不是比自己的工作多。如果目標隊列比源隊列(顯著地)更滿，就從目標隊列“竊取”一個或多個工作，實現(xiàn)負載均衡。
當然，這種方法也有讓人抓狂的地方——如果太頻繁地檢查其他隊列，就會帶來較高的開銷，可擴展性不好，而這是多隊列調(diào)度最初的全部目標!相反，如果檢查間隔太長，又可能會帶來嚴重的負載不均。找到合適的閾值仍然是黑魔法，這在系統(tǒng)策略設計中很常見。
10.6 Linux 多處理器調(diào)度
有趣的是，在構建多處理器調(diào)度程序方面，Linux社區(qū)一直沒有達成共識。一直以來，存在3種不同的調(diào)度程序：O(1)調(diào)度程序、完全公平調(diào)度程序(CFS)以及BF調(diào)度程序(BFS)[2]。從Meehean的論文中可以找到對這些不同調(diào)度程序優(yōu)缺點的對比總結(jié)[M11]。這里我們只總結(jié)一些基本知識。
O(1) CFS采用多隊列，而BFS采用單隊列，這說明兩種方法都可以成功。當然它們之間還有很多不同的細節(jié)。例如，O(1)調(diào)度程序是基于優(yōu)先級的(類似于之前介紹的MLFQ)，隨時間推移改變進程的優(yōu)先級，然后調(diào)度***優(yōu)先級進程，來實現(xiàn)各種調(diào)度目標。交互性得到了特別關注。與之不同，CFS是確定的比例調(diào)度方法(類似之前介紹的步長調(diào)度)。BFS作為三個算法中唯一采用單隊列的算法，也基于比例調(diào)度，但采用了更復雜的方案，稱為最早最合適虛擬截止時間優(yōu)先算法(EEVEF)[SA96]讀者可以自己去了解這些現(xiàn)代操作系統(tǒng)的調(diào)度算法，現(xiàn)在應該能夠理解它們的工作原理了!
10.7 小結(jié)
本章介紹了多處理器調(diào)度的不同方法。其中單隊列的方式(SQMS)比較容易構建，負載均衡較好，但在擴展性和緩存親和度方面有著固有的缺陷。多隊列的方式(MQMS)有很好的擴展性和緩存親和度，但實現(xiàn)負載均衡卻很困難，也更復雜。無論采用哪種方式，都沒有簡單的答案：構建一個通用的調(diào)度程序仍是一項令人生畏的任務，因為即使很小的代碼變動，也有可能導致巨大的行為差異。除非很清楚自己在做什么，或者有人付你很多錢，否則別干這種事。
參考資料
[A90]“The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors”Thomas E. Anderson
IEEE TPDS Volume 1:1, January 1990
這是一篇關于不同加鎖方案擴展性好壞的經(jīng)典論文。Tom Anderson是非常著名的系統(tǒng)和網(wǎng)絡研究者，也是一本非常好的操作系統(tǒng)教科書的作者。
[B+10]“An Analysis of Linux Scalability to Many Cores Abstract”
Silas Boyd-Wickizer, Austin T. Clements, Yandong Mao, Aleksey Pesterev, M. Frans Kaashoek, Robert Morris, Nickolai Zeldovich
OSDI ’10, Vancouver, Canada, October 2010
關于將Linux擴展到多核的很好的現(xiàn)代論文。
[CSG99]“Parallel Computer Architecture: A Hardware/Software Approach”David E. Culler, Jaswinder Pal Singh, and Anoop Gupta
Morgan Kaufmann, 1999
其中充滿了并行機器和算法細節(jié)的寶藏。正如Mark Hill幽默地在書的護封上說的——這本書所包含的信息比大多數(shù)研究論文都多。
[FLR98]“The Implementation of the Cilk-5 Multithreaded Language”Matteo Frigo, Charles E. Leiserson, Keith Randall
PLDI ’98, Montreal, Canada, June 1998
Cilk是用于編寫并行程序的輕量級語言和運行庫，并且是工作竊取范式的極好例子。
[G83]“Using Cache Memory To Reduce Processor-Memory Traffic”James R. Goodman
ISCA ’83, Stockholm, Sweden, June 1983
關于如何使用總線監(jiān)聽，即關注總線上看到的請求，構建高速緩存一致性協(xié)議的開創(chuàng)性論文。Goodman在威斯康星的多年研究工作充滿了智慧，這只是一個例子。
[M11]“Towards Transparent CPU Scheduling”Joseph T. Meehean
Doctoral Dissertation at University of Wisconsin—Madison, 2011
一篇涵蓋了現(xiàn)代Linux多處理器調(diào)度如何工作的許多細節(jié)的論文。非常棒!但是，作為Joe的聯(lián)合導師，我們可能在這里有點偏心。
[SHW11]“A Primer on Memory Consistency and Cache Coherence”Daniel J. Sorin, Mark D. Hill, and David A. Wood
Synthesis Lectures in Computer Architecture
Morgan and Claypool Publishers, May 2011
內(nèi)存一致性和多處理器緩存的權威概述。對于喜歡對該主題深入了解的人來說，這是必讀物。
[SA96]“Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Pro- portional Share Resource Allocation”
Ion Stoica and Hussein Abdel-Wahab
Technical Report TR-95-22, Old Dominion University, 1996
來自Ion Stoica的一份技術報告，其中介紹了很酷的調(diào)度思想。他現(xiàn)在是U.C.
伯克利大學的教授，也是網(wǎng)絡、分布式系統(tǒng)和其他許多方面的***專家。
[1] 一個鮮為人知的事實是，變形金剛的家鄉(xiāng)塞伯坦星球被糟糕的CPU調(diào)度決策所摧毀。
[2] 自己去查BF代表什么。預先警告，小心臟可能受不了。
本文摘自剛剛上架不久的《操作系統(tǒng)導論》
操作系統(tǒng)導論
作者：[美] 雷姆茲·H.阿帕希杜塞爾( Remzi H. Arpaci-Dusseau)， [美]安德莉亞·C.阿帕希杜塞爾(Andrea C. Arpaci-Dusseau)
譯者：王海鵬
