(完整word版)操作系統(tǒng)對多核處理器的支持方法

1、對軟件開發(fā)有非常大的影響，而且核心的瓶頸在軟件上。軟件開發(fā)在多核環(huán)境下的核心是多線程開發(fā)。這個(gè)多線程不僅代表了軟件實(shí)現(xiàn)上多線程， 要求在硬件上也采用多線程技術(shù)?？梢哉f多核提供了可以大幅提升性能的機(jī)制， 多核軟件就是可以真正利用這一特點(diǎn)的策略。只有與多核硬件相適應(yīng)的軟件， 才能真正地發(fā)揮多核的性能。多核對軟件的要求包括對多核操作系統(tǒng)的要求和對應(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)程分配給有共享二 級(jí)cache的核上，將大大

2、提升性能；反之，就有可能影響性能。進(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)部資源競爭等等。 這些探討相互獨(dú)立又相互依賴?？紤]一個(gè)系統(tǒng)的性能時(shí)必須將其中的幾點(diǎn)同時(shí)加以考慮，有時(shí)候?qū)σ恍c(diǎn)的優(yōu)化會(huì)造成另一些點(diǎn)的性能下降，需要用程序進(jìn)行性能優(yōu)化評測，所以合適的多核系統(tǒng)軟件方案正在形成過程中。任務(wù)的分配是多核時(shí)代提出的新概念。在單核時(shí)代，沒有核的任務(wù)分配的問題，一共只有一個(gè)核的資源可被使

3、用。而在多核體系下，有多個(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)度。對于不同的核，每個(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)行在這個(gè)核上，還是進(jìn)行線程遷移；怎樣直接調(diào)度實(shí)時(shí)任務(wù)和普通任務(wù)；系統(tǒng)的核資

4、源是否要進(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)等。傷J如在Linux操作系統(tǒng)中對實(shí)時(shí)任務(wù)采取FCFS 和 RR 兩種調(diào)度，普通任務(wù)調(diào)度采取優(yōu)先級(jí)調(diào)度。對于多核處理器系統(tǒng)的調(diào)度，目前還沒有明確的標(biāo)準(zhǔn)與規(guī)范。由于系統(tǒng)有多個(gè)處理器核可用，必須進(jìn)行負(fù)載分配，有可能為每個(gè)處理器核提供單獨(dú)的隊(duì)列。在這種情況下

5、，一個(gè)具有空隊(duì)列的處理器就會(huì)空閑，而另一個(gè)處理器會(huì)很忙。所以如何處理好負(fù)載均衡問題是這種調(diào)度策略的關(guān)鍵問題所在。為了解決這種情況，可以考慮共同就緒隊(duì)列，所有處理器公用一個(gè)就緒隊(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í)行效率并不高，I/O 的執(zhí)行和處理系統(tǒng)事務(wù)的主處理器成為瓶頸。目前為止，世界上還沒有對CMP 體系結(jié)構(gòu)多核操作系統(tǒng)一個(gè)成熟的

6、調(diào)度算法的實(shí)現(xiàn)。 雖然 Windows 與 Linux 操作系統(tǒng)可以作為CMP 多核體系結(jié)構(gòu)的操作系統(tǒng)，但是它們對多核的支持并不是直接對CMP 多核體系結(jié)構(gòu)的支持，實(shí)際上都是針對 SMP 體系的支持。Linux 操作系統(tǒng)是開源操作系統(tǒng)中的主流，在2.6內(nèi)核發(fā)布之前，CMP 體系結(jié)構(gòu)并不是市場中體系結(jié)構(gòu)的主體，但是Linux2.6 內(nèi)核的調(diào)度策略對SMP 支持得很好。 Linux SMP 的調(diào)度算法已經(jīng)較為全面，很大程度上解決了資源利用不充分、調(diào)度時(shí)間長、解內(nèi)核鎖、加內(nèi)核鎖而引起的過多資源消耗等問題，可作為多核調(diào)度的借鑒。2.6內(nèi)核的調(diào)度算法的時(shí)間復(fù)雜度為O（ 1） ，只需要常數(shù)時(shí)間就能夠完成任

7、務(wù)的調(diào)度。具體實(shí)現(xià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 可以找到優(yōu)先級(jí)最高的任務(wù)執(zhí)行。圖 1-7 Linux2.6 內(nèi)核的就緒（ 3） 當(dāng)活動(dòng)就緒隊(duì)列中的任務(wù)全部時(shí)間片結(jié)束或者等待IO 掛起，

8、 只要進(jì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ā)生時(shí)，并未作出遷移任務(wù)的具體決策；在調(diào)度之前并未采取合適的任務(wù)分配決策等等。卜面是幾個(gè)具有代表性的多核調(diào)度算法:（ 1）對任務(wù)的分配進(jìn)行優(yōu)化

9、。使同一應(yīng)用程序的任務(wù)盡量在一個(gè)核上執(zhí)行，以便達(dá)到有共享數(shù)據(jù)的任務(wù)能夠盡量在一個(gè)核上進(jìn)行，而共享數(shù)據(jù)量少或者沒有的任務(wù)盡量在不同核上進(jìn)行。這樣，可以顯著得降低 cache的缺失率，進(jìn)而很大程度上提升了系統(tǒng)的整體性能。（ 2）對任務(wù)的共享數(shù)據(jù)優(yōu)化。由于CMP 體系結(jié)構(gòu)共享二級(jí)緩存，可以考慮改變?nèi)蝿?wù)在內(nèi)存中的數(shù)據(jù)分布，使任務(wù)在執(zhí)行時(shí)盡量增加二級(jí)緩存的命中率。（ 3）對任務(wù)的負(fù)載均衡優(yōu)化。當(dāng)任務(wù)在調(diào)度時(shí)，出現(xiàn)了負(fù)載不均衡，考慮將較忙處理器中與其他任務(wù)最不相關(guān)的任務(wù)遷移，以達(dá)到數(shù)據(jù)的沖突量小。1.4.2 輸入輸出系統(tǒng)高級(jí)編程中斷控制器（APIC）是基于中斷控制器分散在兩個(gè)基礎(chǔ)功能單元一一本地單元和I/

10、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ā)揮如下基本功能：1 .APIC 接收來自處理器中斷引腳的來自內(nèi)部或外部I/O APIC 的中斷。然后將這些中斷發(fā)送過處理器核處理。2 .在多核

11、處理器系統(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è)能夠接收中斷并將接收到的中斷分發(fā)給能夠提供服務(wù)的核的機(jī)制。多核處理中斷如同在其他的MP 系統(tǒng)一樣。外部中斷通過I/O APIC 接收，并被作為中斷信息分配給特定的核。處理器核也能

12、夠通過寫本地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)來接收和 發(fā)送 IPI 消息。 ICR 提供如下功能：1 .發(fā)送中斷到其他處理器核2 .允許處理器核轉(zhuǎn)發(fā)接收到的其不服務(wù)的中斷到其他處理器核來服務(wù)。3 .給處理器核自身發(fā)送中斷(一次自中斷)4 .傳遞特殊I

13、PI到其他處理器核，比如啟動(dòng)IPI (Start-up IPI)消息。由 IPI 消息產(chǎn)生的中斷通過系統(tǒng)總線傳送給其他處理器核。通過這種方式發(fā)送最低優(yōu)先級(jí)的中斷需要特別建造而且必須避免BIOS 和操作系統(tǒng)軟件干預(yù)。1.4.3 存儲(chǔ)管理與文件系統(tǒng)多核環(huán)境下，存儲(chǔ)管理相對變化較小。其主要的一些改進(jìn)包括：為了充分使用多核的運(yùn)算能力，很多的庫函數(shù)(memory allocation )都要做成non blocking 的，但這樣會(huì)導(dǎo)致數(shù)據(jù)沖突或不同步的問題，所以需要有能夠保證數(shù)據(jù)同步的機(jī)制。事務(wù)內(nèi)存管理(transactional memory management就是這樣的機(jī)制，能夠協(xié)作程 序，在并

14、行運(yùn)行的同時(shí)，保證數(shù)據(jù)的同步。同時(shí)，為了提高內(nèi)存分配(memory allocation)的效率，可以使用多線程內(nèi)存分 配，這樣就可以提高效率，降低cache沖突，特別有利于空間和時(shí)間關(guān)聯(lián)性強(qiáng)的 內(nèi)存操作。1.4.4 典型支持多核的操作系統(tǒng)雖然多核技術(shù)是近兩年才興起，但是操作系統(tǒng)對多核的基本支持并不難解決。傳統(tǒng)的通用的操作系統(tǒng)都是支持多任務(wù)執(zhí)行的，對唯一的一個(gè)計(jì)算核心通過分時(shí)處理，即把CPU 的運(yùn)算時(shí)間劃分成長短基本相同的時(shí)間片，輪流分配給各個(gè)任務(wù)使用，從而實(shí)現(xiàn)單個(gè)CPU 執(zhí)行多個(gè)任務(wù)的能力。對于多核 (片上多處理器)這種新的體系架構(gòu)，操作系統(tǒng)并不需要多少修改就已經(jīng)能夠很好支持了，從軟件角度來

15、看，多核處理器和多路處理器( SMP)是一樣的， 所有針對單核多處理器的軟件優(yōu)化方式都可以用在多核處理器系統(tǒng)上。比如windows NT 之后的 Windows 系列操作系統(tǒng)，其中可以支持SMP 的都可以支持多核。而對于Linux操作系統(tǒng)內(nèi)核，其SMP版本的內(nèi)核能夠很好的支持多核 CPU, Linux 2.0 內(nèi)核是第一個(gè)支持對稱多處理器硬件的內(nèi)核，在近 10 年的發(fā)展進(jìn)程中，尤其從 1999 年到現(xiàn)在，Linux 對多處理器的支持越來越受到重視。在早些時(shí)候，Linux2.0 內(nèi)核通過使用一種粗粒度的鎖來保證系統(tǒng)的完整性，其原則就是： 一個(gè)正在內(nèi)核態(tài)運(yùn)行的進(jìn)程除非交出控制權(quán)或者要求進(jìn)入睡眠，否

16、則不能被另一個(gè)欲進(jìn)入內(nèi)核態(tài)的進(jìn)程打斷。也就是說在任意時(shí)刻只能有一個(gè)處理器是運(yùn)行內(nèi)核態(tài)的操作系統(tǒng)代碼。這是一種安全而易于實(shí)現(xiàn)的方式，不過這種方式對于充分利用多處理器的性能存在著很明顯的不足。在Linux 以后改進(jìn)的版本中，操作系統(tǒng)內(nèi)核采用了一種細(xì)粒度的鎖來支持這種多處理器的體系機(jī)構(gòu)。通過把操作系統(tǒng)的內(nèi)核代碼劃分為臨界區(qū)的方式，在保證系統(tǒng)完整性的前提下，提升了操作系統(tǒng)利用多處理器的性能優(yōu)勢。不管是 WindowsNT 操作系統(tǒng)還是Unix 的一些商業(yè)版本，如Solaris， AIX 等以及開源的Linux 操作系統(tǒng)，都采用一種核心級(jí)線程和用戶級(jí)線程兩種線程的模型， 操作系統(tǒng)的調(diào)度在核心態(tài)完成，這樣

17、調(diào)度器可以專注于核心態(tài)線程在處理器上的調(diào)度。在 2.6 版本的 Linux 中，提出了一種新的O（ 1）的進(jìn)程調(diào)度器，此調(diào)度器可以更好的支持SMP 系統(tǒng)。它的優(yōu)勢就是在平衡了多個(gè)CPUs 的負(fù)載均衡的同時(shí)又能有效的兼顧cache的有效性。在傳統(tǒng)的調(diào)度過程中，當(dāng)某進(jìn)程從一個(gè) CPU遷 移到另一個(gè)CPU上的時(shí)候，在原CPU上的cache內(nèi)容即為失效，這將延遲任務(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ù)把

18、時(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),在操作系統(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

19、.系統(tǒng)硬件與BIOS 程序一起處理。在后一種方法中，BIOS 程序?qū)⑵渌麬P 置于中斷屏蔽狀態(tài)，使其休眠，只選擇BSP 執(zhí)行 BIOS 代碼中的后繼部分。BIOS 要同時(shí)完成對APIC 以及其他與MP相關(guān)的系統(tǒng)組件初始化過程，并建立相應(yīng)的系統(tǒng)配置表格，以便操作系統(tǒng)使用。操作系統(tǒng)在BSP 上完成內(nèi)核加載，操作基本初始化工作后，通過使用處理器間中斷系統(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版本有所不同，對于UP版本，宏Cli (關(guān)中斷)和 Sti (開中斷)就是簡單的ch和sti指令；而對于SMP版本，內(nèi)核不僅要禁止本 地CPU,還要暫時(shí)避免其它CPU處理IRQ (中斷請求)，宏cli和sti實(shí)際上是對 函數(shù)_global_cli