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

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

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

補充：高級章節

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

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

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

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

10.1　背景：多處理器架構

為了理解多處理器調度帶來的新問題，必須先知道它與單CPU之間的基本區別。區別的核心在于對硬件緩存(cache)的使用(見圖10.1)，以及多處理器之間共享數據的方式。本章將在較高層面討論這些問題。更多信息可以其他地方找到[CSG99]，尤其是在高年級或研究生計算機架構課程中。

在單CPU系統中，存在多級的硬件緩存(hardware cache)，一般來說會讓處理器更快地執行程序。緩存是很小但很快的存儲設備，通常擁有內存中最熱的數據的備份。相比之下，內存很大且擁有所有的數據，但訪問速度較慢。通過將頻繁訪問的數據放在緩存中，系統似乎擁有又大又快的內存。

舉個例子，假設一個程序需要從內存中加載指令并讀取一個值，系統只有一個CPU，擁有較小的緩存(如64KB)和較大的內存。

程序***次讀取數據時，數據在內存中，因此需要花費較長的時間(可能數十或數百納秒)。處理器判斷該數據很可能會被再次使用，因此將其放入CPU緩存中。如果之后程序再次需要使用同樣的數據，CPU會先查找緩存。因為在緩存中找到了數據，所以取數據快得多(比如幾納秒)，程序也就運行更快。

緩存是基于局部性(locality)的概念，局部性有兩種，即時間局部性和空間局部性。時間局部性是指當一個數據被訪問后，它很有可能會在不久的將來被再次訪問，比如循環代碼中的數據或指令本身。而空間局部性指的是，當程序訪問地址為x

的數據時，很有可能會緊接著訪問x

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

有趣的部分來了：如果系統有多個處理器，并共享同一個內存，如圖10.2所示，會怎樣呢?

圖10.1　帶緩存的單CPU

圖10.2　兩個有緩存的CPU共享內存

事實證明，多CPU的情況下緩存要復雜得多。例如，假設一個運行在CPU 1上的程序從內存地址A讀取數據。由于不在CPU 1的緩存中，所以系統直接訪問內存，得到值D。程序然后修改了地址A處的值，只是將它的緩存更新為新值D'。將數據寫回內存比較慢，因此系統(通常)會稍后再做。假設這時操作系統中斷了該程序的運行，并將其交給CPU 2，重新讀取地址A的數據，由于CPU 2的緩存中并沒有該數據，所以會直接從內存中讀取，得到了舊值D，而不是正確的值D'。哎呀!

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

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

10.2　別忘了同步

既然緩存已經做了這么多工作來提供一致性，應用程序(或操作系統)還需要關心共享數據的訪問嗎?依然需要!本書第2部分關于并發的描述中會詳細介紹。雖然這里不會詳細討論，但我們會簡單介紹(或復習)下其基本思路(假設你熟悉并發相關內容)。

跨CPU訪問(尤其是寫入)共享數據或數據結構時，需要使用互斥原語(比如鎖)，才能保證正確性(其他方法，如使用無鎖(lock-free)數據結構，很復雜，偶爾才使用。詳情參見并發部分關于死鎖的章節)。例如，假設多CPU并發訪問一個共享隊列。如果沒有鎖，即使有底層一致性協議，并發地從隊列增加或刪除元素，依然不會得到預期結果。需要用鎖來保證數據結構狀態更新的原子性。

為了更具體，我們設想這樣的代碼序列，用于刪除共享鏈表的一個元素，如圖10.3所示。假設兩個CPU上的不同線程同時進入這個函數。如果線程1執行***行，會將head的當前值存入它的tmp變量。如果線程2接著也執行***行，它也會將同樣的head值存入它自己的私有tmp變量(tmp在棧上分配，因此每個線程都有自己的私有存儲)。因此，兩個線程會嘗試刪除同一個鏈表頭，而不是每個線程移除一個元素，這導致了各種問題(比如在第4行重復釋放頭元素，以及可能兩次返回同一個數據)。

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　簡單的鏈表刪除代碼

當然，讓這類函數正確工作的方法是加鎖(locking)。這里只需要一個互斥鎖(即pthread_mutex_t m;)，然后在函數開始時調用lock(&m)，在結束時調用unlock(&m)，確保代碼的執行如預期。我們會看到，這里依然有問題，尤其是性能方面。具體來說，隨著CPU數量的增加，訪問同步共享的數據結構會變得很慢。

10.3　***一個問題：緩存親和度

在設計多處理器調度時遇到的***一個問題，是所謂的緩存親和度(cache affinity)。這個概念很簡單：一個進程在某個CPU上運行時，會在該CPU的緩存中維護許多狀態。下次該進程在相同CPU上運行時，由于緩存中的數據而執行得更快。相反，在不同的CPU上執行，會由于需要重新加載數據而很慢(好在硬件保證的緩存一致性可以保證正確執行)。因此多處理器調度應該考慮到這種緩存親和性，并盡可能將進程保持在同一個CPU上。

10.4　單隊列調度

上面介紹了一些背景，現在來討論如何設計一個多處理器系統的調度程序。最基本的方式是簡單地復用單處理器調度的基本架構，將所有需要調度的工作放入一個單獨的隊列中，我們稱之為單隊列多處理器調度(Single Queue Multiprocessor Scheduling，SQMS)。這個方法***的優點是簡單。它不需要太多修改，就可以將原有的策略用于多個CPU，選擇最適合的工作來運行(例如，如果有兩個CPU，它可能選擇兩個最合適的工作)。

然而，SQMS有幾個明顯的短板。***個是缺乏可擴展性(scalability)。為了保證在多CPU上正常運行，調度程序的開發者需要在代碼中通過加鎖(locking)來保證原子性，如上所述。在SQMS訪問單個隊列時(如尋找下一個運行的工作)，鎖確保得到正確的結果。

然而，鎖可能帶來巨大的性能損失，尤其是隨著系統中的CPU數增加時[A91]。隨著這種單個鎖的爭用增加，系統花費了越來越多的時間在鎖的開銷上，較少的時間用于系統應該完成的工作(哪天在這里加上真正的測量數據就好了)。

SQMS的第二個主要問題是緩存親和性。比如，假設我們有5個工作(A、B、C、D、E)和4個處理器。調度隊列如下：

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

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

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

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

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

10.5　多隊列調度

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

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

例如，假設系統中有兩個CPU(CPU 0和CPU 1)。這時一些工作進入系統：A、B、C和D。由于每個CPU都有自己的調度隊列，操作系統需要決定每個工作放入哪個隊列。可能像下面這樣做：

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

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

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

如果對系統中每個隊列都執行輪轉調度策略，會獲得如下調度結果：

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

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

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

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

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

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

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

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

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

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

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

當然，還有其他不同的遷移模式。但現在是最棘手的部分：系統如何決定發起這樣的遷移?

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

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

10.6　Linux 多處理器調度

有趣的是，在構建多處理器調度程序方面，Linux社區一直沒有達成共識。一直以來，存在3種不同的調度程序：O(1)調度程序、完全公平調度程序(CFS)以及BF調度程序(BFS)[2]。從Meehean的論文中可以找到對這些不同調度程序優缺點的對比總結[M11]。這里我們只總結一些基本知識。

O(1) CFS采用多隊列，而BFS采用單隊列，這說明兩種方法都可以成功。當然它們之間還有很多不同的細節。例如，O(1)調度程序是基于優先級的(類似于之前介紹的MLFQ)，隨時間推移改變進程的優先級，然后調度***優先級進程，來實現各種調度目標。交互性得到了特別關注。與之不同，CFS是確定的比例調度方法(類似之前介紹的步長調度)。BFS作為三個算法中唯一采用單隊列的算法，也基于比例調度，但采用了更復雜的方案，稱為最早最合適虛擬截止時間優先算法(EEVEF)[SA96]讀者可以自己去了解這些現代操作系統的調度算法，現在應該能夠理解它們的工作原理了!

10.7　小結

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

參考資料

[A90]“The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors”Thomas E. Anderson

IEEE TPDS Volume 1:1, January 1990

這是一篇關于不同加鎖方案擴展性好壞的經典論文。Tom Anderson是非常著名的系統和網絡研究者，也是一本非常好的操作系統教科書的作者。

[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擴展到多核的很好的現代論文。

[CSG99]“Parallel Computer Architecture: A Hardware/Software Approach”David E. Culler, Jaswinder Pal Singh, and Anoop Gupta

Morgan Kaufmann, 1999

其中充滿了并行機器和算法細節的寶藏。正如Mark Hill幽默地在書的護封上說的——這本書所包含的信息比大多數研究論文都多。

[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

關于如何使用總線監聽，即關注總線上看到的請求，構建高速緩存一致性協議的開創性論文。Goodman在威斯康星的多年研究工作充滿了智慧，這只是一個例子。

[M11]“Towards Transparent CPU Scheduling”Joseph T. Meehean

Doctoral Dissertation at University of Wisconsin—Madison, 2011

一篇涵蓋了現代Linux多處理器調度如何工作的許多細節的論文。非常棒!但是，作為Joe的聯合導師，我們可能在這里有點偏心。

[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

內存一致性和多處理器緩存的權威概述。對于喜歡對該主題深入了解的人來說，這是必讀物。

[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的一份技術報告，其中介紹了很酷的調度思想。他現在是U.C.

伯克利大學的教授，也是網絡、分布式系統和其他許多方面的***專家。

[1]　一個鮮為人知的事實是，變形金剛的家鄉塞伯坦星球被糟糕的CPU調度決策所摧毀。

[2]　自己去查BF代表什么。預先警告，小心臟可能受不了。

本文摘自剛剛上架不久的《操作系統導論》

操作系統導論

作者：[美] 雷姆茲·H.阿帕希杜塞爾( Remzi H. Arpaci-Dusseau)， [美]安德莉亞·C.阿帕希杜塞爾(Andrea C. Arpaci-Dusseau)

譯者：王海鵬