操作系統(tǒng)對(duì)多核處理器的支持方法

1、隨著多核處理器的發(fā)展， 對(duì)軟件開發(fā)有非常大的影響， 而且核心的瓶頸在軟件上。軟件開發(fā)在多核環(huán)境下的核心是多線程開發(fā)。 這個(gè)多線程不僅代表了軟件實(shí)現(xiàn)上多線程，要求在硬件上也采用多線程技術(shù)。 可以說多核提供了可以大幅提升性能的機(jī)制，多核軟件就是可以真正利用這一特點(diǎn)的策略。 只有與多核硬件相適應(yīng)的軟件，才能真正地發(fā)揮多核的性能。 多核對(duì)軟件的要求包括對(duì)多核操作系統(tǒng)的要求和對(duì)應(yīng)用軟件的要求。多核操作系統(tǒng)的關(guān)注點(diǎn)在于進(jìn)程的分配和調(diào)度。 進(jìn)程的分配將進(jìn)程分配到合理的物理核上，因?yàn)椴煌暮嗽诠蚕硇院蜌v史運(yùn)行情況都是不同的。 有的物理核能夠共享二級(jí) cache，而有的卻是獨(dú)立的。如果將有數(shù)據(jù)共享的進(jìn)程分配給有

2、共享二級(jí) cache的核上，將大大提升性能；反之，就有可能影響性能。進(jìn)程調(diào)度會(huì)涉及到比較廣泛的問題，比如負(fù)載均衡、實(shí)時(shí)性等。面向多核體系結(jié)構(gòu)的操作系統(tǒng)調(diào)度目前多核軟件的一個(gè)熱點(diǎn)， 其中研究的熱點(diǎn)主要有下面幾方面： 程序的并行研究； 多進(jìn)程的時(shí)間相關(guān)性研究； 任務(wù)的分配與調(diào)度；緩存的錯(cuò)誤共享；一致性訪問研究；進(jìn)程間通信；多處理器核內(nèi)部資源競(jìng)爭(zhēng)等等。這些探討相互獨(dú)立又相互依賴。 考慮一個(gè)系統(tǒng)的性能時(shí)必須將其中的幾點(diǎn)同時(shí)加以考慮， 有時(shí)候?qū)σ恍c(diǎn)的優(yōu)化會(huì)造成另一些點(diǎn)的性能下降， 需要用程序進(jìn)行性能優(yōu)化評(píng)測(cè)，所以合適的多核系統(tǒng)軟件方案正在形成過程中。任務(wù)的分配是多核時(shí)代提出的新概念。在單核時(shí)代，沒有核

3、的任務(wù)分配的問題，一共只有一個(gè)核的資源可被使用。 而在多核體系下， 有多個(gè)核可以被使用。 如果系統(tǒng)中有幾個(gè)進(jìn)程需要分配， 是將他們均勻地分配到各個(gè)處理器核， 還是一起分配到一個(gè)處理器核， 或是按照一定的算法進(jìn)行分配。 并且這個(gè)分配還受底層系統(tǒng)結(jié)構(gòu)的影響，系統(tǒng)是 SMP 構(gòu)架還是 CMP 構(gòu)架，在 CMP 構(gòu)架中會(huì)共享二級(jí)緩存的核的數(shù)量，這是影響分配算法的因子。任務(wù)分配結(jié)束后，需要考慮任務(wù)調(diào)度。對(duì)于不同的核， 每個(gè)處理器核可以有自己獨(dú)立的調(diào)度算法來執(zhí)行不同的任務(wù)（實(shí)時(shí)任務(wù)或者交互性任務(wù)） ，也可以使用一致的調(diào)度算法。此外，還可以考慮一個(gè)進(jìn)程上一個(gè)時(shí)間運(yùn)行在一個(gè)核上，下一個(gè)時(shí)間片是選擇繼續(xù)運(yùn)行在這

4、個(gè)核上，還是進(jìn)行線程遷移； 怎樣直接調(diào)度實(shí)時(shí)任務(wù)和普通任務(wù)；系統(tǒng)的核資源是否要進(jìn)行負(fù)載均衡等等。任務(wù)調(diào)度是目前研究的熱點(diǎn)之一。在單核處理器中， 常見的調(diào)度策略有先到先服務(wù)（ FCFS）,最短作業(yè)調(diào)度（ SJF），優(yōu)先級(jí)調(diào)度（ Priority-scheduling algorithm ）,輪轉(zhuǎn)法調(diào)度（ round-robin RR），多級(jí)隊(duì)列調(diào)度（ multilevel queue-schedule algorithm）等。例如在 Linux 操作系統(tǒng)中對(duì)實(shí)時(shí)任務(wù)采取 FCFS 和 RR 兩種調(diào)度，普通任務(wù)調(diào)度采取優(yōu)先級(jí)調(diào)度。對(duì)于多核處理器系統(tǒng)的調(diào)度， 目前還沒有明確的標(biāo)準(zhǔn)與規(guī)范。 由于系統(tǒng)有

5、多個(gè)處理器核可用， 必須進(jìn)行負(fù)載分配， 有可能為每個(gè)處理器核提供單獨(dú)的隊(duì)列。 在這種情況下，一個(gè)具有空隊(duì)列的處理器就會(huì)空閑， 而另一個(gè)處理器會(huì)很忙。 所以如何處理好負(fù)載均衡問題是這種調(diào)度策略的關(guān)鍵問題所在。 為了解決這種情況， 可以考慮共同就緒隊(duì)列， 所有處理器公用一個(gè)就緒隊(duì)列。 但是這無疑對(duì)進(jìn)程上下文切換、鎖的轉(zhuǎn)換增加了執(zhí)行時(shí)間， 降低了性能。 另外一種想法就是選擇一個(gè)處理器來為其他處理器調(diào)度， 因而創(chuàng)建了主從結(jié)構(gòu)。 有的系統(tǒng)將主從結(jié)構(gòu)作進(jìn)一步擴(kuò)展，采用單一處理器來處理所有調(diào)度的調(diào)度策略、 I/O 處理和其他系統(tǒng)活動(dòng)只有一個(gè)處理器處理訪問系統(tǒng)數(shù)據(jù)， 減輕了數(shù)據(jù)共享需要， 然而它的執(zhí)行效率并不

6、高， I/O 的執(zhí)行和處理系統(tǒng)事務(wù)的主處理器成為瓶頸。目前為止，世界上還沒有對(duì) CMP 體系結(jié)構(gòu)多核操作系統(tǒng)一個(gè)成熟的調(diào)度算法的實(shí)現(xiàn)。雖然 Windows 與 Linux 操作系統(tǒng)可以作為 CMP 多核體系結(jié)構(gòu)的操作系統(tǒng)，但是它們對(duì)多核的支持并不是直接對(duì) CMP 多核體系結(jié)構(gòu)的支持，實(shí)際上都是針對(duì) SMP 體系的支持。Linux 操作系統(tǒng)是開源操作系統(tǒng)中的主流，在 2.6 內(nèi)核發(fā)布之前， CMP 體系結(jié)構(gòu)并不是市場(chǎng)中體系結(jié)構(gòu)的主體，但是 Linux2.6 內(nèi)核的調(diào)度策略對(duì) SMP 支持得很好。 Linux SMP 的調(diào)度算法已經(jīng)較為全面，很大程度上解決了資源利用不充分、調(diào)度時(shí)間長(zhǎng)、 解內(nèi)核鎖、

7、加內(nèi)核鎖而引起的過多資源消耗等問題， 可作為多核調(diào)度的借鑒。2.6 內(nèi)核的調(diào)度算法的時(shí)間復(fù)雜度為 O（1），只需要常數(shù)時(shí)間就能夠完成任務(wù)的調(diào)度。具體實(shí)現(xiàn)的原理簡(jiǎn)要而言是這樣的：（ 1）系統(tǒng)為每個(gè)處理器都維持一個(gè)單獨(dú)的就緒隊(duì)列，就緒隊(duì)列包括活動(dòng)的就緒隊(duì)列和擴(kuò)展的就緒隊(duì)列。活動(dòng)的就緒隊(duì)列包含當(dāng)前時(shí)間片還有剩余的就緒任務(wù)。而擴(kuò)展的就緒隊(duì)列包含的是那些時(shí)間片已經(jīng)用完的，重新分配時(shí)間片的就緒任務(wù)。（ 2）任務(wù)的調(diào)度是基于優(yōu)先級(jí)調(diào)度的。每個(gè)處理器上的任務(wù)共有 140 個(gè)優(yōu)先級(jí)（圖 1-7），而每個(gè)就緒任務(wù)的優(yōu)先級(jí)通過散列函數(shù)直接映射到處理器的位圖這個(gè)數(shù)據(jù)結(jié)構(gòu)上，通過位圖的 find-first-bit 可

8、以找到優(yōu)先級(jí)最高的任務(wù)執(zhí)行。圖 1-7 Linux2.6 內(nèi)核的就緒（ 3）當(dāng)活動(dòng)就緒隊(duì)列中的任務(wù)全部時(shí)間片結(jié)束或者等待 IO 掛起，只要進(jìn)行簡(jiǎn)單的指針操作，就可以相互轉(zhuǎn)換活動(dòng)就緒隊(duì)列和擴(kuò)展就緒隊(duì)列。（ 4）負(fù)載均衡的實(shí)現(xiàn)的方式有兩種：當(dāng)一個(gè)處理器上的任務(wù)全部結(jié)束之后，每1ms，它會(huì)使用系統(tǒng)調(diào)用到最忙處理器上獲得任意一個(gè)任務(wù)執(zhí)行；而在全部處理器都有任務(wù)在執(zhí)行時(shí)，則由時(shí)鐘每 200ms 喚起系統(tǒng)調(diào)用去檢查，若發(fā)現(xiàn)在 Linux 標(biāo)準(zhǔn)下不均衡，則會(huì)發(fā)生處理器之間的就緒任務(wù)遷移。但是 Linux 沒有考慮讓一個(gè)應(yīng)用程序的任務(wù)盡量在同一個(gè)處理器核上執(zhí)行， 盡量降低 cache的缺失率；當(dāng)負(fù)載不均衡發(fā)生

9、時(shí)，并未作出遷移任務(wù)的具體決策；在調(diào)度之前并未采取合適的任務(wù)分配決策等等。下面是幾個(gè)具有代表性的多核調(diào)度算法：（ 1）對(duì)任務(wù)的分配進(jìn)行優(yōu)化。使同一應(yīng)用程序的任務(wù)盡量在一個(gè)核上執(zhí)行，以便達(dá)到有共享數(shù)據(jù)的任務(wù)能夠盡量在一個(gè)核上進(jìn)行， 而共享數(shù)據(jù)量少或者沒有的任務(wù)盡量在不同核上進(jìn)行。這樣，可以顯著得降低 cache的缺失率，進(jìn)而很大程度上提升了系統(tǒng)的整體性能。（ 2）對(duì)任務(wù)的共享數(shù)據(jù)優(yōu)化。由于 CMP 體系結(jié)構(gòu)共享二級(jí)緩存，可以考慮改變?nèi)蝿?wù)在內(nèi)存中的數(shù)據(jù)分布，使任務(wù)在執(zhí)行時(shí)盡量增加二級(jí)緩存的命中率。（ 3）對(duì)任務(wù)的負(fù)載均衡優(yōu)化。當(dāng)任務(wù)在調(diào)度時(shí)，出現(xiàn)了負(fù)載不均衡，考慮將較忙處理器中與其他任務(wù)最不相關(guān)的

10、任務(wù)遷移，以達(dá)到數(shù)據(jù)的沖突量小。輸入輸出系統(tǒng)高級(jí)編程中斷控制器（ APIC）是基于中斷控制器分散在兩個(gè)基礎(chǔ)功能單元本地單元和 I/O 單元的分布式體系結(jié)構(gòu)。本地和 I/O 單元能夠通過一個(gè)叫中斷控制通信（ Interrupt Controller Communication 即 ICC）的總線互相之間通信。在多核系統(tǒng)中，多個(gè)本地和 I/O APIC 單元能夠作為一個(gè)整體通過 ICC 總線互相操作。 APIC 單元主要用于從中斷源傳送中斷到中斷目標(biāo)。APIC 具有如下功能：1.減緩與中斷相關(guān)的內(nèi)存總線傳輸壓力，從而似的內(nèi)存總線可用程度更高。2.幫助核之間更好的處理來自別的核的中斷。APIC 發(fā)揮

11、如下基本功能：1.APIC 接收來自處理器中斷引腳的來自內(nèi)部或外部 I/O APIC 的中斷。然后將這些中斷發(fā)送過處理器核處理。2.在多核處理器系統(tǒng)中， APIC 還能夠接受發(fā)送核內(nèi)中斷（ Interprocessor interrupt 即 IPI）消息。 APIC 能將 IPI 消息發(fā)送或接收系統(tǒng)總線上其他的處理器核的 IPI 消息。 IPI 消息能夠用來在系統(tǒng)時(shí)或者系統(tǒng)執(zhí)行的廣泛功能單元中分發(fā)中斷到不同的處理器核。 IPI 消息可以用來啟動(dòng)處理器核或者分配工作任務(wù)到不同的處理器核。多核體系處理器中， 必須將中斷處理分發(fā)給一組核處理。 當(dāng)系統(tǒng)中有多個(gè)核在并行執(zhí)行時(shí)，必須有一個(gè)能夠接收中斷并

12、將接收到的中斷分發(fā)給能夠提供服務(wù)的核的機(jī)制。多核處理中斷如同在其他的 MP 系統(tǒng)一樣。外部中斷通過 I/O APIC 接收，并被作為中斷信息分配給特定的核。 處理器核也能夠通過寫本地 APIC 的 ICR 寄存器來發(fā)送 IPI（ Interprocessor Interrupt）給其他的核。高級(jí)編程中斷控制器（ APIC ）最早由 IA-32 奔騰體系處理器引進(jìn)。 APIC 也被引入 P6 系列，奔騰 4，Intel Xeon處理器核其他最新的Intel 64 核 IA-32 處理器。APIC 能夠通過中斷命令寄存器（ Interrupt Command Register 即 ICR）來接收和

13、發(fā)送 IPI 消息。 ICR 提供如下功能：1.發(fā)送中斷到其他處理器核2.允許處理器核轉(zhuǎn)發(fā)接收到的其不服務(wù)的中斷到其他處理器核來服務(wù)。3.給處理器核自身發(fā)送中斷（一次自中斷）4.傳遞特殊 IPI 到其他處理器核，比如啟動(dòng)IPI（ Start-up IPI）消息。由 IPI 消息產(chǎn)生的中斷通過系統(tǒng)總線傳送給其他處理器核。通過這種方式發(fā)送最低優(yōu)先級(jí)的中斷需要特別建造而且必須避免BIOS 和操作系統(tǒng)軟件干預(yù)。存儲(chǔ)管理與文件系統(tǒng)多核環(huán)境下，存儲(chǔ)管理相對(duì)變化較小。其主要的一些改進(jìn)包括：為了充分使用多核的運(yùn)算能力，很多的庫函數(shù)（ memory allocation ）都要做成non blocking 的，

14、但這樣會(huì)導(dǎo)致數(shù)據(jù)沖突或不同步的問題，所以需要有能夠保證數(shù)據(jù)同步的機(jī)制。事務(wù)內(nèi)存管理 （transactional memory management）就是這樣的機(jī)制， 能夠協(xié)作程序，在并行運(yùn)行的同時(shí)，保證數(shù)據(jù)的同步。同時(shí)，為了提高內(nèi)存分配（ memory allocation）的效率，可以使用多線程內(nèi)存分配，這樣就可以提高效率， 降低 cache沖突，特別有利于空間和時(shí)間關(guān)聯(lián)性強(qiáng)的內(nèi)存操作。典型支持多核的操作系統(tǒng)雖然多核技術(shù)是近兩年才興起， 但是操作系統(tǒng)對(duì)多核的基本支持并不難解決。 傳統(tǒng)的通用的操作系統(tǒng)都是支持多任務(wù)執(zhí)行的， 對(duì)唯一的一個(gè)計(jì)算核心通過分時(shí)處理，即把 CPU 的運(yùn)算時(shí)間劃分成長(zhǎng)短

15、基本相同的時(shí)間片，輪流分配給各個(gè)任務(wù)使用，從而實(shí)現(xiàn)單個(gè) CPU 執(zhí)行多個(gè)任務(wù)的能力。對(duì)于多核（片上多處理器） 這種新的體系架構(gòu)， 操作系統(tǒng)并不需要多少修改就已經(jīng)能夠很好支持了，從軟件角度來看，多核處理器和多路處理器（ SMP）是一樣的，所有針對(duì)單核多處理器的軟件優(yōu)化方式都可以用在多核處理器系統(tǒng)上。 比如 windows NT 之后的 Windows 系列操作系統(tǒng)，其中可以支持 SMP 的都可以支持多核。而對(duì)于 Linux 操作系統(tǒng)內(nèi)核，其 SMP 版本的內(nèi)核能夠很好的支持多核 CPU， Linux 2.0 內(nèi)核是第一個(gè)支持對(duì)稱多處理器硬件的內(nèi)核， 在近 10 年的發(fā)展進(jìn)程中，尤其從 1999

16、年到現(xiàn)在， Linux 對(duì)多處理器的支持越來越受到重視。在早些時(shí)候， Linux2.0 內(nèi)核通過使用一種粗粒度的鎖來保證系統(tǒng)的完整性， 其原則就是：一個(gè)正在內(nèi)核態(tài)運(yùn)行的進(jìn)程除非交出控制權(quán)或者要求進(jìn)入睡眠， 否則不能被另一個(gè)欲進(jìn)入內(nèi)核態(tài)的進(jìn)程打斷。 也就是說在任意時(shí)刻只能有一個(gè)處理器是運(yùn)行內(nèi)核態(tài)的操作系統(tǒng)代碼。 這是一種安全而易于實(shí)現(xiàn)的方式， 不過這種方式對(duì)于充分利用多處理器的性能存在著很明顯的不足。在 Linux 以后改進(jìn)的版本中，操作系統(tǒng)內(nèi)核采用了一種細(xì)粒度的鎖來支持這種多處理器的體系機(jī)構(gòu)。 通過把操作系統(tǒng)的內(nèi)核代碼劃分為臨界區(qū)的方式， 在保證系統(tǒng)完整性的前提下， 提升了操作系統(tǒng)利用多處理器

17、的性能優(yōu)勢(shì)。不管是 WindowsNT 操作系統(tǒng)還是 Unix 的一些商業(yè)版本，如 Solaris，AIX 等以及開源的 Linux 操作系統(tǒng)，都采用一種核心級(jí)線程和用戶級(jí)線程兩種線程的模型，操作系統(tǒng)的調(diào)度在核心態(tài)完成， 這樣調(diào)度器可以專注于核心態(tài)線程在處理器上的調(diào)度。在 2.6 版本的 Linux 中，提出了一種新的 O（ 1）的進(jìn)程調(diào)度器，此調(diào)度器可以更好的支持 SMP 系統(tǒng)。它的優(yōu)勢(shì)就是在平衡了多個(gè) CPUs 的負(fù)載均衡的同時(shí)又能有效的兼顧 cache 的有效性。在傳統(tǒng)的調(diào)度過程中，當(dāng)某進(jìn)程從一個(gè) CPU 遷移到另一個(gè) CPU 上的時(shí)候，在原 CPU 上的 cache內(nèi)容即為失效，這將延

18、遲任務(wù)在新的 CPU 上訪問內(nèi)存的時(shí)間延遲。Linux 2.6 內(nèi)核設(shè)計(jì)為給每個(gè) CPU 建立一個(gè)就緒運(yùn)行隊(duì)列，并把就緒任務(wù)劃分為 140 個(gè)優(yōu)先級(jí)，高 100 個(gè)優(yōu)先級(jí)用于實(shí)時(shí)任務(wù)，低 40 個(gè)優(yōu)先級(jí)用戶普通任務(wù)。并給每個(gè)就緒任務(wù)一段時(shí)間片， 當(dāng)任務(wù)把時(shí)間片用完后轉(zhuǎn)移到另一個(gè)期滿就緒隊(duì)列并重新分配時(shí)間片， 等到原活動(dòng)就緒隊(duì)列的所有任務(wù)的時(shí)間片均用完之后啟用期滿就緒隊(duì)列來體會(huì)活動(dòng)就緒隊(duì)列。 這樣，調(diào)度器提供了一個(gè)各個(gè)任務(wù)公平使用 CPU 的機(jī)會(huì)，并實(shí)現(xiàn)了任務(wù)和 CPU 的綁定。通過給每一個(gè) CPU 設(shè)立單獨(dú)的任務(wù)隊(duì)列，可以有效的實(shí)現(xiàn)系統(tǒng)中各個(gè) CPUs 的負(fù)載均衡。為了支持 SMP 系統(tǒng)，在操

19、作系統(tǒng)啟動(dòng)階段， 把 CPUs 分為 BSP 和 AP 兩種類型，由于 BIOS 代碼并不是支持多線程的， 所以在 SMP 中，系統(tǒng)必須讓所有 AP 進(jìn)入中斷屏蔽狀態(tài)， 不與 BSP 一起執(zhí)行 BIOS 代碼。為了達(dá)到這一目的， 可以利用兩種手段：1.利用系統(tǒng)硬件本身進(jìn)行處理；2.系統(tǒng)硬件與 BIOS 程序一起處理。在后一種方法中， BIOS 程序?qū)⑵渌?AP 置于中斷屏蔽狀態(tài)，使其休眠，只選擇 BSP 執(zhí)行 BIOS 代碼中的后繼部分。 BIOS 要同時(shí)完成對(duì) APIC 以及其他與 MP 相關(guān)的系統(tǒng)組件初始化過程，并建立相應(yīng)的系統(tǒng)配置表格，以便操作系統(tǒng)使用。操作系統(tǒng)在BSP 上完成內(nèi)核加載，

20、操作基本初始化工作后，通過使用處理器間中斷系統(tǒng)（ IPI） BSP 初始化各個(gè) AP，最后讓各個(gè) AP 運(yùn)行 idle 進(jìn)程。最后 BSP創(chuàng)建 1 號(hào) init 進(jìn)程，由 init 進(jìn)程完成最后的系統(tǒng)啟動(dòng)工作。在中斷處理上，為了支持 SMP，在硬件上需要 APIC 中斷控制系統(tǒng)的支持。 Linux 操作系統(tǒng)的 SMP 版本和 UP 版本有所不同，對(duì)于 UP 版本，宏 Cli （關(guān)中斷）和Sti（開中斷）就是簡(jiǎn)單的 ch 和 sti 指令；而對(duì)于 SMP 版本，內(nèi)核不僅要禁止本地 CPU，還要暫時(shí)避免其它 CPU 處理 IRQ（中斷請(qǐng)求），宏 cli 和 sti 實(shí)際上是對(duì)函數(shù) _global_cli （）和 _glo