趙立偉，賀紅衛(wèi)，劉 冰

（1.中國航天科工集團(tuán)第二研究院706所，北京100854；2.中國兵器工業(yè)計(jì)算機(jī)應(yīng)用技術(shù)研究所，北京100089）

0 引 言

早先的操作系統(tǒng)和軟件對于多核處理器的支持并不完美，不能充分地利用多核處理器資源，所以如何開發(fā)高效率、高穩(wěn)定性多核操作系統(tǒng)是如今計(jì)算機(jī)操作系統(tǒng)發(fā)展的重要方向，而支持SMP的嵌入式多核操作系統(tǒng)由于其共享內(nèi)存，負(fù)載平衡、功耗比高等優(yōu)點(diǎn)，更是成為嵌入式操作系統(tǒng)發(fā)展的重中之重，因此對于SMP多核操作系統(tǒng)的研究具有十分重要的意義。從目前來看，多核操作系統(tǒng)的發(fā)展嚴(yán)重滯后于多核處理器的發(fā)展，同時(shí)多核操作系統(tǒng)性能的落后反過來也嚴(yán)重制約著計(jì)算機(jī)整體性能的大幅提升。國外操作系統(tǒng)的發(fā)展相對國內(nèi)要早很多，早在1974年，卡內(nèi)基梅隆大學(xué)便提出了HYDRA操作系統(tǒng)，自此以后國外的各種操作系統(tǒng)如雨后春筍般出現(xiàn)，各大高校以及研究機(jī)構(gòu)開始投入大量人力財(cái)力進(jìn)行操作系統(tǒng)和多核處理器的研究。相比之下，而國內(nèi)操作系統(tǒng)的研究則起步比較晚，能夠進(jìn)行深入研究的機(jī)構(gòu)相對少很多，雖然也取得了一些成就，但是相對于國外還是落后很多。目前在國內(nèi)外的公開文件上，面向高性能DSP多核處理器的操作系統(tǒng)還沒有出現(xiàn)，很多國家和公司也已經(jīng)投入大量精力開始著手研究，所以基于DSP的嵌入式對稱多核操作系統(tǒng)必將是今后發(fā)展的一個(gè)重要趨勢。因此在核高基重大課題專項(xiàng)的支持下，開始進(jìn)行基于DSP多核處理器的嵌入式對稱多核操作系統(tǒng)的研究。本文對多核操作系統(tǒng)的研究方法進(jìn)行了總結(jié)，并在前人研究成果的基礎(chǔ)上進(jìn)行了擴(kuò)展與補(bǔ)充，使之能夠滿足DSP對于處理數(shù)據(jù)高效性的要求，由此設(shè)計(jì)出了一種基于TMS320C6678的對稱多核操作系統(tǒng)。

1 多核操作系統(tǒng)的關(guān)鍵問題

相對于單核操作系統(tǒng)，多核操作系統(tǒng)的設(shè)計(jì)存在如下幾個(gè)主要難點(diǎn)：一是多核處理器的運(yùn)行模式。二是臨界資源的訪問控制，必須采取某種策略實(shí)現(xiàn)對多核處理器臨界區(qū)資源的互斥訪問。三是任務(wù)調(diào)度，必須設(shè)計(jì)出性能良好的調(diào)度算法以滿足操作系統(tǒng)的實(shí)時(shí)性要求、同時(shí)還要保證處于最高優(yōu)先級(jí)的任務(wù)處于運(yùn)行狀態(tài)。四是多核cache一致性的管理。同時(shí)多核操作系統(tǒng)也應(yīng)該包括單核操作系統(tǒng)的所有功能與模塊，下文主要對各個(gè)技術(shù)難點(diǎn)進(jìn)行詳細(xì)介紹。

1.1 多核操作系統(tǒng)的運(yùn)行模式

多核操作系統(tǒng)的運(yùn)行模式包括以下2種：

非對稱多處理 （asymmetric multiprocessing，AMP）：在每一個(gè)CPU內(nèi)核獨(dú)自運(yùn)行著一個(gè)操作系統(tǒng)，各個(gè)核上的操作系統(tǒng)互不干涉，通過任務(wù)通信算法或者核間中斷來實(shí)現(xiàn)各個(gè)核之間的數(shù)據(jù)通信。

對稱多處理 （symmetric multiprocessing，SMP）：一個(gè)操作系統(tǒng)內(nèi)核負(fù)責(zé)管理所有的處理器核。同時(shí)所有的任務(wù)可以運(yùn)行在每一個(gè)CPU核上。

在AMP系統(tǒng)中，一個(gè)任務(wù) （process）只能運(yùn)行在某一個(gè)特定的CPU核上面，即便是其它內(nèi)核正在處于空轉(zhuǎn)狀態(tài)。這樣會(huì)導(dǎo)致某些內(nèi)核處于空閑狀態(tài)，而另外一些核在超負(fù)載運(yùn)轉(zhuǎn)，即負(fù)載不平衡。所以AMP系統(tǒng)雖然也能使多核操作系統(tǒng)正常的運(yùn)轉(zhuǎn)，但卻不能最大程度地利用多核處理器的資源，不能充分發(fā)揮其性能。然而一個(gè)設(shè)計(jì)良好的SMP操作系統(tǒng)可以允許多個(gè)任務(wù)協(xié)同地運(yùn)行在任何一個(gè)內(nèi)核上，這種協(xié)同性可以充分地利用多核處理器資源，使操作系統(tǒng)的性能大幅提高。所以SMP操作系統(tǒng)必定是多核操作系統(tǒng)發(fā)展的重要方向。

1.2 臨界資源的訪問控制

多核處理器是一個(gè)多任務(wù)系統(tǒng)，其主要特點(diǎn)是資源的共享，為使操作系統(tǒng)能夠正確運(yùn)行，需要維護(hù)一些共享資源的互斥訪問機(jī)制。而傳統(tǒng)的用于單核的共享資源的互斥訪問都是通過關(guān)中斷等方式實(shí)現(xiàn)，顯然這種解決機(jī)制并不能滿足多核CPU，因此需要利用硬件提供的 “讀－修改－寫”的原子操作或其它同步互斥機(jī)制來實(shí)現(xiàn)。

1.3 任務(wù)調(diào)度

任務(wù)調(diào)度的方式分為剝奪方式和非剝奪方式2種。非剝奪方式：一旦某個(gè)任務(wù)獲得了CPU資源后就會(huì)一直運(yùn)行下去，直到任務(wù)完成或發(fā)生任務(wù)調(diào)度等事件時(shí)，其余的任務(wù)才會(huì)獲得CPU資源。剝奪方式：操作系統(tǒng)可以基于某些原則，把一個(gè)正在運(yùn)行任務(wù)的CPU資源剝奪，并將其分配給其它任務(wù)。剝奪原則有：優(yōu)先權(quán)原則、短任務(wù)優(yōu)先原則、時(shí)間片原則。

任務(wù)調(diào)度策略：把處理器資源分配給按照一定的規(guī)則從就緒隊(duì)列中選取的任務(wù)，使其開始運(yùn)行。這些選取任務(wù)的規(guī)則就是任務(wù)調(diào)度策略，其基本要求是高效、公平。常見的任務(wù)調(diào)度策略有：優(yōu)先級(jí)高優(yōu)先調(diào)度策略、多重循環(huán)輪轉(zhuǎn)調(diào)度策略、時(shí)間片輪轉(zhuǎn)調(diào)度策略等。

任務(wù)隊(duì)列模型分為全局隊(duì)列模型和局部隊(duì)列模型2種方式。局部隊(duì)列模型是每個(gè)核維護(hù)自己的任務(wù)就緒隊(duì)列，這樣由于就緒隊(duì)列是每個(gè)核所私有，不存在互斥訪問的問題，所以多個(gè)核之間可以并行的進(jìn)行任務(wù)調(diào)度，具有較高的吞吐量。但是卻不能實(shí)現(xiàn)任務(wù)的負(fù)載平衡，需要操作系統(tǒng)維護(hù)額外的任務(wù)負(fù)載平衡算法，并且不能保證高優(yōu)先級(jí)的任務(wù)一定能夠處于運(yùn)行狀態(tài)，可預(yù)測性也比較低。全局隊(duì)列是所有核擁有同一個(gè)任務(wù)就緒隊(duì)列，這樣在每個(gè)核必須互斥訪問任務(wù)就緒隊(duì)列，因此在同一個(gè)時(shí)刻只能有一個(gè)核進(jìn)行任務(wù)調(diào)度，吞吐量較低。但是可以保證優(yōu)先級(jí)最高的幾個(gè)任務(wù)運(yùn)行在這些CPU核上，與局部隊(duì)列模型相比，可預(yù)測性有了很大提高，而且由于所有核共享同一個(gè)任務(wù)就緒隊(duì)列，每個(gè)核無需維護(hù)額外的任務(wù)負(fù)載平衡算法。

1.4 cache一致性管理

多核cache一致性是指，當(dāng)某個(gè)核把部分?jǐn)?shù)據(jù)加載到cache中運(yùn)行時(shí)，如果運(yùn)行過程中對某些全局變量進(jìn)行了修改，而內(nèi)存中和其它核的cache中的數(shù)據(jù)并沒有隨之而改變，會(huì)造成cache與內(nèi)存數(shù)據(jù)的不一致性，該問題將會(huì)導(dǎo)致程序執(zhí)行錯(cuò)誤，甚至引起系統(tǒng)崩潰。因此需要對cache的一致性進(jìn)行維護(hù)。同時(shí)，一個(gè)性能良好的cache一致性管理策略對于操作系統(tǒng)的性能具有相當(dāng)大的影響。

目前實(shí)現(xiàn)cache一致性的策略主要分為硬件cache一致性策略和軟件cache一致性策略。其中硬件cache一致性策略又分為監(jiān)聽cache一致性協(xié)議和目錄表法等。

2 基于TMS320C6678的SMP多核操作系統(tǒng)設(shè)計(jì)

2.1 啟動(dòng)的設(shè)計(jì)

在多核處理器的引導(dǎo)過程中，處理器內(nèi)核間是不平等的，有主次之分的。系統(tǒng)啟動(dòng)后，PM （primary CPU）首先對其自身進(jìn)行初始化，然后完成全局的初始化 （如PLL、內(nèi)存控制器初始化等），向各個(gè)PE （processor element）發(fā)送核間消息，通知各個(gè)PE進(jìn)行啟動(dòng)。從核在接收到消息之后便開始對其自身進(jìn)行初始化，同時(shí)在PE初始化的過程中，PM需要循環(huán)地檢測是否所有處理器核都完成了初始化，如果已經(jīng)全部完成，就可以同時(shí)進(jìn)入任務(wù)調(diào)度過程。

在引導(dǎo)過程中，所有的處理器核都需要進(jìn)行自身的初始化過程，而全局的初始化過程只需要PM執(zhí)行一次，PE無需執(zhí)行。

SMP啟動(dòng)流程如圖1所示。

2.2 共享資源的互斥訪問

我們沒有方法控制對共享資源訪問的有序性，但是有能力對共享資源采用鎖的保護(hù)機(jī)制，當(dāng)某個(gè)共享資源被鎖住時(shí)，只有獲取該鎖的CPU核能夠操作共享資源，其余試圖訪問共享資源的CPU核只能等待這個(gè)鎖的釋放，這就是自旋鎖的保護(hù)機(jī)制。

自旋鎖的設(shè)計(jì)思想是基于 Test－and－Set機(jī)制，對此C6678則提供了一組 （32個(gè)）硬件信號(hào)量semaphore，通過對相應(yīng)的寄存器的讀寫來保證互斥地獲得該信號(hào)量。

C6678硬件信號(hào)量包括3種工作方式，分別為：direct方式、indirect方式和combined方式，我們選擇direct方式對自旋鎖進(jìn)行實(shí)現(xiàn)，具體流程如圖2所示。

2.3 負(fù)載均衡的任務(wù)分配與調(diào)度

多核嵌入式操作系統(tǒng)的負(fù)載均衡管理是指依據(jù)某種管理機(jī)制將所有任務(wù)在各個(gè)核上進(jìn)行分配與調(diào)度，實(shí)現(xiàn)各個(gè)核的任務(wù)負(fù)載均衡，每個(gè)核的任務(wù)量大致相當(dāng)，不會(huì)出現(xiàn)某些核空閑，而某些核超負(fù)荷運(yùn)作的情況。負(fù)荷的有效管理能最大程度的發(fā)揮多核嵌入式處理器的并行計(jì)算資源，最大程度的實(shí)現(xiàn)處理器的有效利用。

同時(shí)任務(wù)調(diào)度是操作系統(tǒng)最重要的一個(gè)模塊，因?yàn)楫?dāng)新任務(wù)創(chuàng)建、任務(wù)延時(shí)、請求／釋放信號(hào)量、中斷返回時(shí)，不可避免的要采取任務(wù)調(diào)度，而上述活動(dòng)卻又是要頻繁發(fā)生的，因此，選擇一個(gè)好的任務(wù)調(diào)度策略對于操作系統(tǒng)的性能具有非常重要的意義。

對稱多核操作系統(tǒng)的任務(wù)管理與調(diào)度分為2種模式，即：全局隊(duì)列模式和局部隊(duì)列模式，全局隊(duì)列模式是指所有的處理器核共同維護(hù)一個(gè)全局任務(wù)就緒隊(duì)列，當(dāng)有一個(gè)或者若干個(gè)核空閑時(shí)，操作系統(tǒng)按照某種管理機(jī)制從全局隊(duì)列中取出一個(gè)或者若干個(gè)任務(wù)分配到相應(yīng)核上運(yùn)行，完成任務(wù)的動(dòng)態(tài)分配與調(diào)度管理。局部隊(duì)列模式是為每個(gè)任務(wù)維護(hù)一個(gè)局部任務(wù)就緒等待隊(duì)列，當(dāng)進(jìn)行任務(wù)調(diào)度時(shí)，每個(gè)核都需要從本核的任務(wù)就緒隊(duì)列中選取任務(wù)。2種模式的工作情況如圖3和圖4所示。

顯然，全局隊(duì)列調(diào)度相對于局部隊(duì)列調(diào)度具有較好的可預(yù)測性并且可以滿足負(fù)載平衡，而這兩者是實(shí)時(shí)系統(tǒng)中非常重要的指標(biāo)，故本設(shè)計(jì)選擇全局隊(duì)列調(diào)度。同時(shí)為了滿足最高優(yōu)先級(jí)的任務(wù)永遠(yuǎn)處于運(yùn)行狀態(tài)，必須要選擇可搶占式的任務(wù)調(diào)度策略，因此采用了剝奪方式中的優(yōu)先級(jí)高優(yōu)先調(diào)度策略。

為了獲得較高的執(zhí)行效率，采用了2種實(shí)現(xiàn)方法，即：為某個(gè)核調(diào)度一個(gè)任務(wù)和為任務(wù)選擇一個(gè)核。對此，任務(wù)延時(shí)、請求信號(hào)量、中斷返回應(yīng)該采用前者，而新任務(wù)創(chuàng)建、釋放信號(hào)量則應(yīng)該采用后者。2種實(shí)現(xiàn)方法的流程如圖5所示。

圖5 任務(wù)調(diào)度流程

2.4 cache一致性策略的實(shí)現(xiàn)

目前大多數(shù)的多核處理器架構(gòu)都提供硬件cache一致性維護(hù)策略，因此基于這種架構(gòu)的多核操作系統(tǒng)就無需對其cache一致性進(jìn)行軟件維護(hù)。然而TMS320C6678并沒有提供硬件cache一致性策略，因此需要軟件來進(jìn)行維護(hù)。

在討論軟件cache一致性策略之前，我們先對它的內(nèi)存架構(gòu)進(jìn)行簡單介紹。TMS320C6678的每個(gè)核都有各自的一級(jí)和二級(jí)cache，所有核共有共享內(nèi)存空間。具體情況如圖6所示。

軟件解決的方案主要包括2種，一種方案是每個(gè)核的程序在執(zhí)行過程中，如果需要訪問共享變量，為了防止取到的是cache中的過時(shí)數(shù)據(jù)，則需要首先置對應(yīng)cache無效，同時(shí)如果對全局變量進(jìn)行了修改，則需要將相應(yīng)的cache寫回到共享內(nèi)存中，以保證共享內(nèi)存中的數(shù)據(jù)保持最新狀態(tài)。另一種方案是全局變量不加載到cache中，僅僅將其放在共享內(nèi)存中，這樣所有訪問操作都要在共享內(nèi)存中進(jìn)行。以上方案都只能采取較為保守的方法，凡是可能發(fā)生不一致問題，都將會(huì)使cache無效，將會(huì)導(dǎo)致較高的cache不命中率，影響著操作系統(tǒng)性能的進(jìn)一步提升。但是相對于硬件維護(hù)策略，它們也具有不隨著處理器核的增多而變得復(fù)雜，并且不需要很多輔助硬件等優(yōu)點(diǎn)。

3 結(jié)束語

擁有了多核操作系統(tǒng)，可以更大限度的發(fā)揮多核處理器的性能，本研究實(shí)現(xiàn)的操作系統(tǒng)具有較強(qiáng)的實(shí)時(shí)性與健壯性，結(jié)合TMS320C6678多核處理器的高速數(shù)據(jù)處理能力，能夠滿足軍用計(jì)算機(jī)對于多核操作系統(tǒng)的需求，經(jīng)過TI公司發(fā)布的vlfft性能驗(yàn)證程序驗(yàn)證，本研究實(shí)現(xiàn)的系統(tǒng)與TI公司發(fā)布的sys／bios相比擁有更高的性能，并且更加適合數(shù)據(jù)的并行處理與流水線處理，可以更加完美的支持圖像處理等應(yīng)用程序。

［1］Robert Love.Linux kernel development ［M］.3rd ed.Beijing：China Machine Press，2010：41－67.

［2］Stallings W.Operating systems：Internals and design principles，6／E ［M］.Pearson Education India，2009.

［3］Boyd－Wickizer S，Chen H，Chen R，et al.Corey：An operating system for many cores［C］／／OSDI，2008：43－57.

［4］Yuan Q，Zhao J，Chen M，et al.GenerOS：An asymmetric operating system kernel for multi－core systems ［C］／／IEEE In－ternational Symposium on Parallel ＆ Distributed Processing.IEEE，2010：1－10.

［5］Texas Instruments Inc.KeyStone semaphore2hardware module［EB／OL］.http：／／www.ti.com.cn／cn／lit／ug／sprugs3a／sprugs3a.pdf，2011.

［6］Texas Instruments Inc.Tms320c66xDSP CorePac user guide［EB／OL］.http：／／www.ti.com.cn／cn／lit／ug／sprugw0b／sprugw0b.pdf，2011.

［7］Texas Instruments Inc.Multicore programming guide ［EB／OL］.http：／／www.ti.com.cn／cn／lit／an／sprab27b／sprab27b.pdf，2011.

［8］Kahn K C，Corwin W M，Dennis T D，et al.iMAX：A multiprocessor operating system for an object－based computer［C］／／Proc of the 8th Symposium on Operating System Principles，2009：127－136.

［9］Wulf W，Cohen E，Corwin W，et al.HYDRA：The kernel of a multiprocessor operating system ［J］.Communications of ACM，2009，17 （6）：337－345.

［10］Chunmao J，Guoyin Z，Chunmei H.Research of embedded operating system based on multi－core processor ［C］／／3rd IEEE International Conference on Computer Science and Information Technology.IEEE，2010：641－643.

［11］Loghi M，Poncino M，Benini L.Cache coherence tradeoffs in shared－memory MPSoCs ［J］.ACM Transactions on Embedded Computing Systems，2006，5 （2）：383－407.