C語言中文網
首頁 > 編程筆記 > 操作系統筆記 閱讀:363

多處理器調度完全攻略

迄今為止,我們主要集中討論單處理器系統的 CPU 調度問題。如果有多個 CPU,則負載分配成為可能,但是調度問題就相應地更為復雜。許多可能的方法都已試過,但與單處理器調度一樣,沒有最好的解決方案。

多處理器調度的方法

對于多處理器系統,CPU 調度的一種方法是讓一個處理器(主服務器)處理所有調度決定、I/O 處理以及其他系統活動,其他的處理器只執行用戶代碼。這種非對稱多處理很簡單,因為只有一個處理器訪問系統數據結構,減少了數據共享的需要。

第二種方法是使用對稱多處理(SMP),即每個處理器自我調度。所有進程可能處于一個共同的就緒隊列中,或每個處理器都有它自己的私有就緒進程隊列。不管如何,調度這樣進行:每個處理器的調度程序都檢查共同就緒隊列,以便選擇執行一個進程。如果多個處理器試圖訪問和更新一個共同的數據結構,那么每個處理器必須仔細編程,必須確保兩個處理器不會選擇同一進程,而且進程不會從隊列中丟失。

幾乎所有現代操作系統,包括 Windows、Linux 和 Mac OSX,都支持 SMP。本節余下部分討論有關 SMP 系統的多個問題。

處理器親和性

考慮一下,當一個進程運行在一個特定處理器上時緩存會發生些什么。進程最近訪問的數據更新了處理器的緩存。結果,進程的后續內存訪問通常通過緩存來滿足。

現在考慮一下,如果進程移到其他處理器上則會發生什么。第一個處理器緩存的內容應設為無效,第二個處理器緩存應重新填充。由于緩存的無效或重新填充的代價高,大多數 SMP 系統試圖避免將進程從一個處理器移到另一個處理器,而是試圖讓一個進程運行在同一個處理器上。這稱為處理器親和性,即一個進程對它運行的處理器具有親和性。

處理器的親和性具有多種形式。當一個操作系統試圖保持進程運行在同一處理器上時(但不保證它會這么做),這種情況稱為軟親和性。這里,操作系統試圖保持一個進程在某個處理器上,但是這個進程也可遷移到其他處理器。相反,有的系統提供系統調用以便支持硬親和性,從而允許某個進程運行在某個處理器子集上。

許多系統提供軟的和硬的親和性。例如,Linux 實現軟親和性,但是它也提供系統調用 sched_setaffinity() 以支持硬親和性。

NUMA與CPU調度
圖 1 NUMA 與 CPU 調度

系統的內存架構可以影響處理器的親和性。圖 1 為采用非統一內存訪問的一種架構,其中一個 CPU 訪問內存的某些部分會比其他部分更快。通常情況下,這類系統包括組合 CPU 和內存的板卡。每個板的 CPU 訪問本板內存快于訪問其他板的內存。

如果操作系統的 CPU 調度和內存分配算法一起工作,那么當一個進程分配到一個特定的親和處理器時,它應分配到同板上的內存。這個例子還說明操作系統通常不按教科書描述的那樣清楚地定義與實現。實際上,操作系統的各個部分的“實線”通常應是“虛線”,因為有些算法創建連接以便優化性能和可靠性。

負載平衡

對于 SMP 系統,重要的是保持所有處理器的負載平衡,以便充分利用多處理器的優點。否則,一個或多個處理器會空閑,而其他處理器會處于高負載狀態,且有一系列進程處于等待狀態。

負載平衡設法將負載平均分配到 SMP 系統的所有處理器。需要注意的是,對于有些系統(它們的處理器具有私有的可執行進程的隊列),負載平衡是必需的;而對于具有公共隊列的系統,負載平衡通常沒有必要,因為一旦處理器空閑,它立刻從公共隊列中取走一個可執行進程。同時,要注意對于大多數支持SMP的現代操作系統,每個處理器都有一個可執行進程的私有隊列。

負載平衡通常有兩種方法:推遷移和拉遷移

推遷移和拉遷移不必相互排斥,事實上,在負載平衡系統中它們常被并行實現。例如,Linux 調度程序和用于 FreeBSD 系統的 ULE 調度程序實現了這兩種技術。

有趣的是,負載平衡往往會抵消處理器親和性的好處。也就是說,保持一個進程運行在同一處理器上的好處是進程可以利用它在該處理器緩存內的數據。無論是從一個處理器向另一處理器推或拉進程,都會失去這個好處。

與通常的系統工程情況一樣,關于何種方式是最好的,沒有絕對規則。因此,在某些系統中,空閑的處理器總是會從非空閑的處理器中拉進程;而在其他系統中,只有當不平衡達到一定程度后才會移動進程。

多核處理器

傳統上,SMP 系統具有多個物理處理器,以便允許多個線程并行運行。然而,計算機硬件的最近做法是,將多個處理器放置在同一個物理芯片上,從而產生多核處理器。每個核都保持架構的狀態,因此對操作系統而言它似乎是一個單獨的物理處理器。

采用多核處理器的 SMP 系統與采用單核處理器的 SMP 系統相比,速度更快,功耗更低。多核處理器的調度問題可能更為復雜。下面我們來分析一下原因。

研究人員發現,當一個處理器訪問內存時,它花費大量時間等待所需數據。這種情況稱為內存停頓,它的發生原因多種多樣,如高速緩存未命中(訪問數據不在高速緩沖里)。圖 2 顯示了內存停頓。

內存停頓
圖 2 內存停頓

在這種情況下,處理器可能花費高達 50% 的時間等待內存數據變得可用。為了彌補這種情況,許多最近的硬件設計都采用了多線程的處理器核,即每個核會分配到兩個(或多個)硬件線程。這樣,如果一個線程停頓而等待內存,該核可以切換到另一個線程。圖 3 顯示了一個雙線程的處理器核,這里線程 0 和線程 1 的執行是交錯的。

多線程多核系統
圖 3 多線程多核系統

從操作系統的角度來看,每一個硬件線程似乎作為一個邏輯處理器,以便運行軟件線程。因此,在雙線程雙核系統中,操作系統會有 4 個邏輯處理器。UltraSPARC T3 CPU 具有 16 個處理器核,而每個核有 8 個硬件線程,從操作系統的角度,就有 128 個邏輯處理器。

一般來說,處理器核的多線程有兩種方法:粗粒度細粒度的多線程。

對于粗粒度的多線程,線程一直在處理器上執行,直到一個長延遲事件(如內存停頓)發生。由于長延遲事件造成的延遲,處理器應切換到另一個線程來開始執行。然而,線程之間的切換成本是高的,因為在另一個線程可以在處理器核上開始執行之前,應刷新指令流水線。一旦這個新的線程開始執行,它會開始用指令來填充流水線。

細粒度(或交錯)的多線程在更細的粒度級別上(通常在指令周期的邊界上)切換線程。而且,細粒度系統的架構設計有線程切換的邏輯。因此,線程之間的切換成本很小。

注意,一個多線程多核處理器實際需要兩個不同級別的調度。一個級別的調度決策由操作系統做出,用于選擇哪個軟件線程運行在哪個硬件線程(邏輯處理器)。對于這個級別的調度,操作系統可以選擇任何調度算法。

另一個級別的調度指定每個核如何決定運行哪個硬件線程。在這種情況下,有多種策略可以采用。前面提到的 UltraSparc T3 采用一個簡單的輪轉算法,安排 8 個硬件線程到每個核。

再比如,Intel Itanium 為雙核處理器,而且每個核有兩個硬件線程。每個硬件線程有一個動態的緊迫值,它的取值范圍為 0?7,用 0 表示最低的緊迫性,而 7 表示最高的。Itanium 有 5 個不同的事件,用于觸發線程切換。當這些事件發生時,線程切換邏輯會比較兩個線程的緊迫性,并選擇緊迫性較高的線程在處理器核上執行。

所有教程

優秀文章

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo