CMP操作系統(tǒng)技術(shù)

1、運“芯”帷幄 CMP 的操作系統(tǒng)技術(shù)單芯片多處理器（ CMP ），特別是在一個芯片上集成了多個相同通用處理器的單芯片對稱多 處理器（同構(gòu) CMP ）的發(fā)展，是上世紀(jì) 90 年代以來集成電路制造工藝的進步與微處理器體 系結(jié)構(gòu)的發(fā)展所帶來的必然發(fā)展方向。和目前在服務(wù)器領(lǐng)域廣泛采用的對稱多處理器（ Symmetric Multi-Processor, SMP ）結(jié)構(gòu)類似，在 CMP 系統(tǒng)中，位于同一個芯片內(nèi)部所有處理器內(nèi)核以平等的身份參與任務(wù)調(diào)度和中斷處 理，共享內(nèi)存和外部設(shè)備，而且也可以共享片內(nèi)的 （部分或全部）高速緩存。CMP 的結(jié)構(gòu)相對簡單，可以直接使用現(xiàn)有的處理器內(nèi)核，因此開發(fā)周期與成本相對

2、較低， 結(jié)構(gòu)簡單帶來的另一個好處是更易獲得高的主頻。由于多個處理器集成在 一塊芯片上，且 共享cache,微處理器之間的通信延遲會明顯降低，有利于提高系統(tǒng)的整體性能。因此，CMP具有良好的發(fā)展前景和廣泛的應(yīng)用空間， 眾多著名大學(xué)、 科研機構(gòu)和商業(yè)公司都展開了廣泛 而積極的研究。而要想真正發(fā)揮 CMP 的優(yōu)勢,軟件,特別是操作系統(tǒng)和編譯工具等系統(tǒng)軟件的支持至關(guān)重 要,沒有這些軟件, CMP 將處于 “空轉(zhuǎn)”狀態(tài)。因此,每一個 CMP 系統(tǒng)都需要為其量身打造 的系統(tǒng)軟件。CMP 對操作系統(tǒng)提出的挑戰(zhàn)系統(tǒng)軟件對于 CMP 廣泛、深入的應(yīng)用有重要的意義,這里我們討論操作系統(tǒng)。操作系統(tǒng)是 計算機系統(tǒng)的基

3、本系統(tǒng)軟件, 在整個計算機系統(tǒng)中處于核心地位, 負責(zé)控制、 管理計算機的 所有軟件、硬件資源,是惟一直接和硬件系統(tǒng)打交道的軟件,是整個軟件系統(tǒng)的基礎(chǔ)部分, 同時還為計算機用戶提供良好的界面。對于普通用戶而言, 操作系統(tǒng)是一個資源管理者, 通過它提供的系統(tǒng)命令和界面操作等工具, 以某種易于理解的方式完成系統(tǒng)管理功能, 有效地控制各種硬件資源, 組織自己的數(shù)據(jù), 完 成自己的工作并和其他人共享資源。對于程序員來講, 操作系統(tǒng)提供了一個與計算機硬件等價的擴展或虛擬的計算平臺。操作系統(tǒng)提供給程序員的工具除了系統(tǒng)命令、界面操作之外,還有系統(tǒng)調(diào)用,系統(tǒng)調(diào)用抽象了許多硬件細節(jié), 程序可以以某種統(tǒng)一的方式進行

4、數(shù)據(jù)處理, 程序員可以避開許多具體的硬件細 節(jié),提高程序開發(fā)效率,改善程序移植特性。并行是計算機科學(xué)與技術(shù)的重要分支之一, 其核心思想是通過任務(wù)的合理劃分和分配,使得多個處理器可以同時執(zhí)行一個或多個任務(wù),以達到系統(tǒng)整體計算能力的大幅度提升。CMP的意義在于能夠提供任務(wù)并行執(zhí)行的一個新思路, 支持在一個芯片內(nèi)的多個處理器內(nèi)核之間 任務(wù)的劃分和分配（也就是調(diào)度） ,而任務(wù)的調(diào)度則需 要操作系統(tǒng)來完成。CMP 的發(fā)展對操作系統(tǒng)提出了新的挑戰(zhàn)。首先,如何合理組織、調(diào)度任務(wù)才能最大程度地 發(fā)揮 CMP 結(jié)構(gòu)的性能？其次,如何保持操作系統(tǒng)的外部接口的相對穩(wěn)定？對于一般用戶而 言，大家希望的是平滑的過渡，

5、一方面界面最好和以前的操作系統(tǒng)完全相同， 另一方面以前 能用的應(yīng)用程序最好還能夠不做任何修改就直接在 CMP 的機器上直接運行， 也就是說 CMP 對于用戶來講最好是透明的，這需要操作系統(tǒng)在用戶界面和編程接口方面都保持不變。如何更好地組織和調(diào)度任務(wù)以便將 CMP 結(jié)構(gòu)的性能發(fā)揮到極致是核心的問題，這是人們對CMP 最大的期望。要解決這個問題，需要軟硬件共同協(xié)作，從任務(wù)調(diào)度、中斷分配、資源 共享等幾個方面入手， 硬件方面則要求 CMP 系統(tǒng)提供全新的同步與互斥、 中斷分配以及 CPU 內(nèi)核之間的中斷等機制。支持 CMP 操作系統(tǒng)的關(guān)鍵技術(shù) 目前國際上對于 CMP 的研究還處于探索階段，相關(guān)操作系

6、統(tǒng)也處在積極研究時期。研究、 分析和借鑒支持 CMP 操作系統(tǒng)的關(guān)鍵技術(shù)對于我們認識、理解和設(shè)計用于 CMP 的操作系 統(tǒng)有著非常重要的意義，這里，我們簡單介紹支持 CMP 操作系統(tǒng)的引導(dǎo)和初始化、調(diào)度， 中斷處理和同步、互斥技術(shù)。系統(tǒng)引導(dǎo)和初始化操作系統(tǒng)的引導(dǎo)和初始化是指從系統(tǒng)加電到能夠在多個處理器內(nèi)核之間平等地進行任務(wù)調(diào) 度的過程， 這一過程是建立平等調(diào)度實施的基礎(chǔ)， 對于整個系統(tǒng)的運行具有重要意義。 雖然 說對稱多處理器系統(tǒng)中， 各處理器可以平等地并行工作， 但這是建立在系統(tǒng)有多個可并行執(zhí) 行任務(wù)的基礎(chǔ)之上， 而在引導(dǎo)和初始化過程中， 由于很多工作只能串行地執(zhí)行， 所以在這個 階段處理器

7、內(nèi)核是不平等的，是有主次之分的。系統(tǒng)加電之后，受到硬件控制，只啟動其中 一個處理器，稱為主 CPU 或者引導(dǎo)處理器( Booting Processor, BP) ，而其他處理器，稱為次 CPU 或者應(yīng)用處理器 (Application Processor, AP) ，則處于停機等待狀態(tài)。加電啟動之后，主 CPU 跳轉(zhuǎn)到特定的內(nèi)存地址，通常映射到只讀存儲器，這里保存著整個 計算機的引導(dǎo)程序， 其任務(wù)是進行簡單的硬件檢測、 初始化環(huán)境參數(shù)、 將操作系統(tǒng)內(nèi)核裝載 到內(nèi)存中，跳轉(zhuǎn)到操作系統(tǒng)的起始地址并開始執(zhí)行。這段引導(dǎo)過程完全由 BP 完成。進入操作系統(tǒng)內(nèi)核之后， BP 需要進行最初的草創(chuàng)性工作，完

8、成運行環(huán)境準(zhǔn)備、各種初識狀 態(tài)設(shè)置、 基本讀寫數(shù)據(jù)段清零、 bootloader 傳遞過來的各種環(huán) 境參數(shù)保存、 內(nèi)存棧的開辟以 及棧指針、全局指針設(shè)置。前面這部分工作全部由底層匯編代碼完成，之后， BP 跳轉(zhuǎn)到由 高級語言編寫的函數(shù)，開始第二個階段 CPU 本身的初始化。在 CPU 初始化過程中， BP 首先開始自檢，收集 CPU 相關(guān)的指令集、存儲管理、高速緩存 以及協(xié)處理器等基本信息。接著為次 CPU 準(zhǔn)備運行環(huán)境，同時為 AP 準(zhǔn)備一個鎖，之后喚 醒 AP ， AP 轉(zhuǎn)入主 CPU 設(shè)置好的地址，開始鎖測試而進入等待狀態(tài)。喚醒AP 之后， BP 輸出自身信息之后，繼續(xù)進行內(nèi)存等各種資源

9、的初始化。接下來的工作主要有 BP 進行開發(fā)板以及外部設(shè)備初始化，之后準(zhǔn)備用于所有 CPU 的空閑 進程，這是一個不參與調(diào)度的進程，當(dāng)某個 CPU 沒有需要執(zhí)行的任務(wù)， 就轉(zhuǎn)入這個進程。 準(zhǔn)備好空閑進程之后，由 BP 解除對 AP 的鎖，各 AP 逐個啟動，進行各種關(guān)于各自 CPU 的 初始化，將自身的狀態(tài)填寫到適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，最后相繼進入空閑狀態(tài)。所有的 AP 都完成初始化并進入空閑狀態(tài)后，由 BP 來完成整個系統(tǒng)最后階段的初始化，并 執(zhí)行系統(tǒng)的第一個進程，之后真正步入對稱多處理器環(huán)境，所有的 CPU 進入正常、平等的 調(diào)度。調(diào)度調(diào)度系統(tǒng)對于操作系統(tǒng)乃至整個計算機系統(tǒng)的整體性能有非常重要的影

10、響， 嵌入式、 桌面和 高端服務(wù)器系統(tǒng)對于調(diào)度器的要求是很不一樣的。在 CMP 結(jié)構(gòu)中調(diào)度機制的重點在于更好 地滿足多處理機并行性上，核心思想是通過降低 CPU 間調(diào)度競爭和選擇下一個運行進程的 開銷， 以及提高系統(tǒng)整體負載平衡的能力， 從而大幅度提高多處理機系統(tǒng)的執(zhí)行效率。 其特 性如下：1. 調(diào)度算法在傳統(tǒng)單 CPU 結(jié)構(gòu)的調(diào)度系統(tǒng)中，所有就緒進程（狀態(tài)為 TASK_RUNNING ）被組織到同 一個雙向鏈表之中， 稱為全局任務(wù)隊列， 調(diào)度過程中將遍歷此鏈表中的所有進程， 調(diào)用計算 每一個進程的權(quán)值，從中選擇權(quán)值最大的進程投入運行。由于調(diào)度器要遍歷所有就緒進程， 因此選擇下一個運行進程的時

11、間復(fù)雜度是O （n）（n 為就緒進程的個數(shù) ）。同時， 因為就緒隊列是全局性的，對單 CPU 系統(tǒng)來講只可能有一個 CPU 訪問這個隊列，而在多處理器結(jié)構(gòu)中， 必須通過一個全局的自旋鎖保證同一時刻只有一個 CPU 進行訪問，這樣導(dǎo)致系統(tǒng)中其他 CPU 的等待。如果就緒進程個數(shù)比較多，那么就緒隊列就會成為一個明顯的瓶頸。在支持 CMP 的操作系統(tǒng)中，每個 CPU 維護一個自己的就緒進程隊列，稱為局部任務(wù)隊列， 這樣大大降低了 CPU 間的競爭。就緒進程按時間片是否用完分為 active 和 expired 兩大類， active 類包括那些時間片沒用完、 當(dāng)前可被調(diào)度的就緒進程， expired

12、 類包括那些時間片已用 完的就緒進程。 同時，每類中的進程按照其優(yōu)先級的不同處于不同的優(yōu)先級鏈表中。調(diào)度時， active 隊列中非空的最高優(yōu)先級鏈表的第一項被作為候選進程，使得選擇下一個運 行進程的操作可以在固定時間內(nèi)完成。 同時內(nèi)核建立了一個位映射數(shù)組來對應(yīng)每一個優(yōu)先級 鏈表，使用標(biāo)志位的方式極大降低尋找非空的鏈表所需要的時間。 當(dāng)一個進程耗盡其時間片 后，內(nèi)核重新計算它的優(yōu)先級，并把它放置在 expired 隊列的相應(yīng)優(yōu)先級鏈表中。進程優(yōu)先 級的計算過程還可以分散到進程的執(zhí)行過程中進行。 這種將集中計算過程分散的做法， 保證 了調(diào)度器運行的時間上限， 降低了不必要的開銷； 同時在內(nèi)存中保

13、留更加豐富的信息的做法 也加速了候選進程的定位過程。 當(dāng) active 隊列中沒有可調(diào)度進程時，內(nèi)核簡單地對調(diào) active 和 expired 隊列，將原來的 expired 隊列作為新的 active 隊列后即可進行新一輪調(diào)度。此調(diào)度算法選擇下一個運行進程的時間復(fù)雜度是 O（1） ，與就緒進程的個數(shù)無關(guān)，調(diào)度效率 大大提高。2. 系統(tǒng)負載平衡支持 CMP 操作系統(tǒng)內(nèi)核的調(diào)度系統(tǒng)需要很好地解決進程與 CPU 之間的 “親和 ”問題。如果不 考慮親和，一個進程可能在 CPU 之間比較頻繁地遷移，交互式進程（或高優(yōu)先級的進程） 可能還會在 CPU 之間不斷 “跳躍 ”，這樣，每一次遷移之后，都可

14、能造成頻繁的內(nèi)存訪問， 導(dǎo)致整體性能下降。支持 CMP 操作系統(tǒng)內(nèi)核的調(diào)度系統(tǒng)盡量使得每個進程一直在固定的 CPU 上執(zhí)行，這樣可 以提高 Cache 的命中率；但是如果某個 CPU 的就緒隊列過長，不斷的進程切換反而造成 Cache命中率的下降，而且還造成其他CPU不能充分發(fā)揮效能。無論當(dāng)前CPU是繁忙或空閑，時鐘中斷每隔一段時間都會啟動一次以平衡負載。當(dāng)然，一旦當(dāng)前CPU 發(fā)現(xiàn)自己的就緒隊列為空時，也會主動進行負載平衡。為了進行 有效的負載平衡，操作 系統(tǒng)內(nèi)核根據(jù)系統(tǒng)結(jié)構(gòu) 的特點，引入調(diào)度域 （struct sched_domain）的概念將全體CPU 一層一層地劃分成不同的區(qū)域，每個調(diào)度

15、域中的 CPU分成 若干個 CPU 組， 且滿足任一 CPU 惟一存在于一個組 中。每個 CPU 屬于一個基本的調(diào)度域（該域至少包括本 CPU），但是CPU同時還屬于一個或多個更大的調(diào)度域。CPU的多個調(diào)度域通過構(gòu)成一個單向鏈表， 且必須滿足： 1.父調(diào)度域是子調(diào)度域的超集； 2.每個 CPU 的最 高層調(diào)度域必須包括系統(tǒng)中的全部處理器。例如在一個支持超線程的CMP 系統(tǒng)中，每個邏輯CPU的基本調(diào)度域包含所在傳統(tǒng)物理CPU上的全部的邏輯 CPU，基本域的每個 CPU分組包含一個邏輯 CPU ;基本調(diào)度域的父調(diào)度域是這個系統(tǒng)的最高層調(diào)度域，它包含系統(tǒng)中 所有的邏輯CPU，該域的每個 CPU分組包

16、含一個物理 CPU上的全部邏輯 CPU。對于 CMP 系統(tǒng)，每個芯片上的多個核天然地構(gòu)成一層調(diào)度域。一個單芯片CMP 系統(tǒng)和一個普通 SMP 系統(tǒng)的基本調(diào)度域的差別僅在于 CMP 基本調(diào)度域的 CPU 組包含的對象是一個“CPU核”，而SMP基本調(diào)度域的 CPU組包含的是一個傳統(tǒng)的物理CPU。對于像支持超線程和多核 SMP 這樣復(fù)雜的 CMP 系統(tǒng)，必須 增加一個基于芯片層面的新調(diào)度域。進行負載平衡時，從當(dāng)前 CPU 的基本調(diào)度域出發(fā)，遍歷所有的調(diào)度域。如果某個域有一段 時間沒有進行過負載平衡，先尋找域中負載最大的 CPU 組（ CPU 組的 負載等于組中所有 CPU的負載之和），然后尋找組中

17、最繁忙的CPU （該CPU的負載超過本 CPU至少25%），更新雙方的負載記錄， 確定需要遷移的進程數(shù) 為源 CPU 負載與本 CPU 負載之差的一半 （經(jīng) 過更新后的值） ，然后按照從 expired 隊列到 active 隊列、 從低優(yōu)先級進程到高優(yōu)先級進程 的順序進行遷移，但實際上真正執(zhí)行遷移的進程往往少于計劃遷移的數(shù)目。中斷處理傳統(tǒng)的單處理器通常都采用一個外部中斷控制器來解決外部設(shè)備到CPU 的通信，對于多處理器系統(tǒng)，處理器之間也需要通過中斷方式進行通信，對于CMP 而言，多個處理器之間的中斷控制器 （本地中斷控制器， 簡稱本地控制器） 也需要和處理器一起封裝到芯片內(nèi)部。此 外，還需要

18、一個全局的中斷控制器 （簡稱全局控制器） 負責(zé)各個處理器內(nèi)核之間的中斷分配， 也要設(shè)計在芯片內(nèi)部。1.中斷分配全局中斷控制器擔(dān)負著把來自外部設(shè)備的中斷請求提交和分配給片內(nèi)各CPU 的任務(wù)。對于每一個中斷向量， 可以采用靜態(tài)或動態(tài)兩種不同模式之一。 如果某個中斷向量是靜態(tài)分配的， 則控制器把這種中斷請求提交給預(yù)設(shè)的一個或多個CPU ；動態(tài)模式則可以發(fā)送給所有 CPU，或者隨機地發(fā)送給某個處理器。本地控制器處理本處理器內(nèi)部產(chǎn)生的中斷請求、 來自外部中斷控制器的中斷請求以及其他處 理器發(fā)送過來的中斷請求。2.處理器間中斷在 CMP 系統(tǒng)中，芯片內(nèi)部一個處理器常常要有目標(biāo)地向系統(tǒng)中的其他處理器發(fā)出中斷

19、請求， 這種中斷被稱為處理器間中斷 (IPI, Inter Processor Interrupt) 。 IPI 至少應(yīng)該包含以下兩種：重新調(diào)度”中斷。當(dāng)前CPU可以發(fā)送該中斷來指示目標(biāo) CPU可能需要一次進程調(diào)度，至于 目標(biāo) CPU 在處理完該中斷以后是否進行進程調(diào)度，那得要看事先或者在處理中斷的過程中 是否把當(dāng)前進程設(shè)置為需要調(diào)度?！罢埱髨?zhí)行 ”中斷。這個中斷被用來請求目標(biāo) CPU 執(zhí)行一個指定的函數(shù)。之所以要通過 IPI 請其他 CPU 執(zhí)行，是因為某個函數(shù)必須由目標(biāo) CPU 才能完成，而不能由別的 CPU 代替。 比如某個處理器改變了內(nèi)存中某個頁面映射目錄或頁面映射表的內(nèi)容，從而可能引

20、起其他處理器的 TLB 與其不一致時， 就向系統(tǒng)中正在使 用這個映射表的處理器發(fā)送這個中斷， 請它 們自己執(zhí)行代碼，廢棄各自 TLB 的內(nèi)容。3. 時鐘中斷在所有中斷請求中， 時鐘中斷扮演著特殊的重要角色， 每一個處理器都有自身的時鐘發(fā)生器。 在系統(tǒng)初始化階段， 系統(tǒng)先設(shè)置一個外部時鐘中斷源供所有 CPU 共 享， 并且以此基準(zhǔn)測算 各個 CPU 的運算速度，并校準(zhǔn)自身的時鐘中斷發(fā)生間隔。由于各處理器設(shè)計完全一致，所 有 CPU 都有基本相同的時鐘脈沖周期，為了不讓所有處理器都在同一時刻發(fā)生時鐘中斷， 操作系統(tǒng)應(yīng)該使各個 CPU 的時鐘中斷在相位上相互錯開，把這些中斷均勻地分布在時鐘中 斷的周

21、期中。同步與互斥技術(shù)在多任務(wù)系統(tǒng)中， 不同的任務(wù)可能需要同時訪問某些共享變量和共享資源，形成了競爭的關(guān)系。這就需要系統(tǒng)提供同步與互斥機制，使得這些共享變量和共享資源同一時刻只能被一個任務(wù)以獨占的方式訪問。 傳統(tǒng)單處理器系統(tǒng)中在宏觀上是并行， 微觀上， 由于只有一個處 理器，同一時刻只能執(zhí)行一個任務(wù)，同步和互斥的問題相對比較容易解決，而 CMP 的操作系統(tǒng)在運行時， 同一時刻有可能有多個任務(wù)執(zhí)行， 傳統(tǒng)的方法有時不能滿足這種特定的情 況，需要引入新的機制。同步和互斥機制需要底層硬件提供“讀-修改 -寫”類型的訪存原子操作。這樣的操作能夠讓CPU 從主存儲器中讀取一個值，修改之，再將修改過的值保存到存儲器的相同位置中。整個過程是一次完整的總線交易， 不能被其他 CPU 內(nèi)核的訪存操作所打斷。 “讀-修改 -寫”類型 的原子操作有多種實現(xiàn)方式， 最常見的包括 test_and_set， swap， load-linked/store-conditional 等方式。Test_and_set 指令從主存儲器中讀取一個值 (通常是一個字節(jié)或一個字) ，將它和 0 比較并根 據(jù)比較的結(jié)果設(shè)置條件碼，最后將 1 無條件地存放到存儲器的相應(yīng)單元。一旦一條test_and_set指令開始了它的總線周期，那么任何其