【正文】 資源的時間分配也應(yīng)不同，這樣才能保證高優(yōu)先級的任務(wù)優(yōu)先執(zhí)行。對此方法的改進(jìn)是采用隨機(jī)時間設(shè)置法，即所有任務(wù)占有自旋鎖的時間不是固定的，可根據(jù)任務(wù)自身特性以及優(yōu)先級大小進(jìn)行設(shè)置，這樣既避免了某個任務(wù)長時間占有，其余任務(wù)一直處于饑餓狀態(tài)的想象，又使得高優(yōu)先級的任務(wù)更易于獲得資源的占有權(quán)。當(dāng)然改進(jìn)后的方法增加了系統(tǒng)開銷，如果使用不當(dāng)反而會降低系統(tǒng)的效率。選擇何種方法要根據(jù)具體的系統(tǒng)應(yīng)用類型而定，由于本文對共享內(nèi)存的訪問是基于消息包的，通信量小，操作簡單，因此選用第一種方法即可滿足系統(tǒng)要求。針對第二個問題，由于自旋鎖未實現(xiàn)當(dāng)前任務(wù)與本核中斷以及當(dāng)前中斷與本核中斷的互斥，而單核系統(tǒng)提供的關(guān)中斷機(jī)制正是為解決該問題而提出的，因此系統(tǒng)可以采用自旋鎖與關(guān)中斷相結(jié)合的策略。這樣系統(tǒng)提供中斷自旋鎖和任務(wù)自旋鎖兩種機(jī)制來保證多核下任務(wù)對資源的互斥訪問。 RTEMS多核下的同步互斥機(jī)制 信號量機(jī)制實現(xiàn)（一） 中斷自旋鎖的實現(xiàn)（1） 中斷自旋鎖的數(shù)據(jù)結(jié)構(gòu)要實現(xiàn)一個中斷自旋鎖，需要記錄自旋鎖歸屬字段，表示自旋鎖是否在某個處理器核上，并且給出是哪一個處理器核取得了該自旋鎖，以判斷該鎖是否正在被使用。另外處理器核在讀鎖過程中根據(jù)任務(wù)中斷自旋鎖的狀態(tài)標(biāo)記處理器核對該鎖的獲取情況。由于在讀鎖初始強(qiáng)制關(guān)閉中斷，因此需要一個字段記錄中斷級別，在解鎖或放棄等待時將中斷打開。根據(jù)以上解析，本文定義的中斷自旋鎖的數(shù)據(jù)結(jié)構(gòu)具體代碼實現(xiàn)如下：structure tSpinLockIsr{int CpuOwner；tCpu cpu[CPU_COUNT]；int key；TCB *pTcb；}structure tCpu{int flag；}包含的字段含義為CpuOwner：自旋鎖歸屬字段；CPU_COUNT：系統(tǒng)中包含的可用處理器核的總數(shù)；cpu[CPU_COUNT]：自旋鎖針對每一個處理器核的獨(dú)立字段；：自旋鎖在每個處理器核下的標(biāo)識，表示該處理器對于指定自旋鎖的使用情況?？稍O(shè)置為SPIN_LOCK_INTERESTED（正在準(zhǔn)備取鎖），SPIN_LOCK_EMPTY（沒有使用任何自旋鎖），SPIN_LOCK_WAIT（等待其它處理器核正在使用的自旋鎖）。key：該自旋鎖被取得后運(yùn)行的中斷級別。pTcb：獲得該鎖的任務(wù)的任務(wù)控制塊。（2） 中斷自旋鎖的初始化在定義了中斷自旋鎖的數(shù)據(jù)結(jié)構(gòu)后，在使用中斷自旋鎖之前要對其進(jìn)行初始化。在對中斷自旋鎖初始化時，先將中斷自旋鎖的歸屬字段設(shè)置為SPIN_LOCK_NOBODY (1),表示該自旋鎖當(dāng)前不被任何處理器核占有。再將屬于每個處理器核的flag字段設(shè)置為 SPIN_LOCK_EMPTY（0），表示當(dāng)前該處理器核沒有使用任何的自旋鎖。具體代碼實現(xiàn)如下：void spinLockIsrInit(tSpinLockIsr *pLock){int i；pLockCpuOwner = SPIN_LOCK_NOBODY；for (i = 0。 i CPU_COUNT。 i++){pLock cpu[i].flag = SPIN_LOCK_EMPTY；}}（3） 中斷自旋鎖的加鎖在被初始化以后，中斷自旋鎖就可以被使用了。加鎖過程要先判斷該鎖是否已經(jīng)被其它的任務(wù)或中斷取得，如果沒有則取鎖，改變鎖當(dāng)前狀態(tài)。若該鎖已被其它任務(wù)或中斷取得，則任務(wù)循環(huán)等待，直到鎖被釋放或到達(dá)一定的循環(huán)次數(shù)。在這個過程中必須保證對鎖中各個字段的修改操作是原子的。 中斷自旋鎖獲取流程（4） 中斷自旋鎖的解鎖在中斷自旋鎖的解鎖過程中，應(yīng)該將在獲得該鎖時關(guān)閉的中斷打開。 中斷自旋鎖釋放流程（二） 任務(wù)自旋鎖的實現(xiàn)（1） 任務(wù)自旋鎖的數(shù)據(jù)結(jié)構(gòu)為了實現(xiàn)一個任務(wù)自旋鎖，需要定義字段記錄任務(wù)對鎖的擁有權(quán)的標(biāo)識、下一個可獲取自旋鎖的任務(wù)的標(biāo)識、已獲取到自旋鎖的標(biāo)識以及相應(yīng)的處理器核，因此任務(wù)自旋鎖的數(shù)據(jù)結(jié)構(gòu)具體代碼實現(xiàn)如下：structure tSpinLocktask{myTicket；int nextTicket；int ticketInService；int cpuIndex；}包含的字段含義為：myTicket：調(diào)用該函數(shù)的任務(wù)對鎖的擁有權(quán)的標(biāo)識。nextTicket：下一個可獲取自旋鎖的任務(wù)的標(biāo)識。ticketInService：已獲取到自旋鎖的標(biāo)識。cpuIndex：相應(yīng)的處理器核。（2） 任務(wù)自旋鎖的初始化對任務(wù)自旋鎖的初始化，只要設(shè)置自旋鎖中變量值為初始值即可。其中nextTicket 為 0；ticketInService 為 0；cpuIndex 為1。具體代碼實現(xiàn)如下：void spinLockTaskInit(tSpinlocktask *pLock){pLocknextTicket = 0；pLockticketInService = 0；pLockcpuIndex = 1；}（3） 任務(wù)自旋鎖的加鎖任務(wù)自旋鎖在初始化后就可以被使用了，使用前要先獲取任務(wù)自旋鎖。任務(wù)自旋鎖的加鎖之前要等待該鎖空閑，即使用該鎖的任務(wù)將該鎖解鎖。 任務(wù)自旋鎖加鎖流程（4） 任務(wù)自旋鎖解鎖。 任務(wù)自旋鎖解鎖流程 本章小結(jié)詳細(xì)介紹了并行系統(tǒng)結(jié)構(gòu)、存儲結(jié)構(gòu)模型、通信機(jī)制和MPSL層三個模塊：MPCI接口層，共享內(nèi)存實現(xiàn)層，硬件相關(guān)實現(xiàn)層。探討了RTEMS支持SMP設(shè)計過程中采用的節(jié)點間通信機(jī)制。并在原有自旋鎖機(jī)制的基礎(chǔ)上提出了一種任務(wù)自旋鎖與中斷自旋鎖相結(jié)合的機(jī)制，解決了單核情況下的同步互斥機(jī)制在多核系統(tǒng)中不能保持原有的語義的問題。第4章 RTEMS多核任務(wù)調(diào)度機(jī)制第4章 RTEMS多核任務(wù)調(diào)度機(jī)制在實時系統(tǒng)中任務(wù)分配問題起著重要作用，直接決定著系統(tǒng)的實時性、高效性[46]。合理的分配任務(wù)將在保證系統(tǒng)實時性的前提下最大程度地提升系統(tǒng)的整體性能。RTEMS內(nèi)核對多核任務(wù)調(diào)度采用平均分配策略。由于任務(wù)具有不確定性，并且系統(tǒng)資源隨著任務(wù)執(zhí)行會不斷發(fā)生變化，如果簡單的采用平均策略，系統(tǒng)并行性不能得到很好的利用，嚴(yán)重影響系統(tǒng)整體性能。動態(tài)調(diào)度算法能夠根據(jù)系統(tǒng)的狀態(tài)信息動態(tài)決定任務(wù)分配，靈活性較高，更好的保證了系統(tǒng)負(fù)載平衡，提高了系統(tǒng)并行性。 任務(wù)分配問題任務(wù)分配是指將任務(wù)分配到系統(tǒng)最合適的位置運(yùn)行[47]，任務(wù)分配算法解決任務(wù)分配問題，一個好的任務(wù)分配算法可以縮小并行程序的執(zhí)行時間。在設(shè)計任務(wù)分配算法之前需要確定任務(wù)就緒隊列模型的選擇。在多核系統(tǒng)中，任務(wù)就緒隊列模型主要分為兩種：全局隊列模型和局部隊列模型[48]。全局隊列模型是指系統(tǒng)中所有節(jié)點共享一個全局任務(wù)就緒隊列，全局任務(wù)就緒隊列中記錄系統(tǒng)中所有處于就緒狀態(tài)的任務(wù)，由主控節(jié)點將就緒隊列中任務(wù)調(diào)度到系統(tǒng)中可用節(jié)點上執(zhí)行，一個任務(wù)在其生命周期中并不一定是在同一個節(jié)點上完成的，可能在不同時間運(yùn)行在不同的節(jié)點上。相反，局部就緒隊列模型是指每個節(jié)點都維護(hù)一個任務(wù)就緒隊列，每個任務(wù)自始至終都在同一個節(jié)點上執(zhí)行，系統(tǒng)中各節(jié)點的任務(wù)調(diào)度互不干擾。全局隊列模型由于所有節(jié)點共享一個就緒隊列，因此實現(xiàn)了系統(tǒng)的負(fù)載均衡。但是，由于全局就緒隊列是共享的，因此必須采取同步互斥機(jī)制實現(xiàn)多核的正確訪問，這樣多個節(jié)點不能同時進(jìn)行任務(wù)調(diào)度，嚴(yán)重影響了系統(tǒng)的并行性。另外cache命中率也會受影響，因為系統(tǒng)要實現(xiàn)負(fù)載均衡，所以會出現(xiàn)同個任務(wù)在不同核之間遷移的情況，這樣會增加cache不命中率，使得系統(tǒng)性能降低。而局部就緒任務(wù)隊列模型相對全局隊列模型來說，更好的利用了系統(tǒng)資源，首先系統(tǒng)中各個節(jié)點都維護(hù)一個就緒任務(wù)隊列，這樣可以同時進(jìn)行任務(wù)調(diào)度，提高了系統(tǒng)的并行性。其次，任務(wù)在其生命周期中很可能在同一個節(jié)點上執(zhí)行，因此cache命中率會有很大增加，提高系統(tǒng)性能?；谝陨蠈Ρ?，選擇將局部就緒任務(wù)隊列模型作為RTEMS多核化任務(wù)分配模型。如果采用局部就緒任務(wù)隊列模型，則必須考慮負(fù)載平衡實現(xiàn)問題。與全局隊列模型不同，局部隊列模型的負(fù)載平衡實現(xiàn)需要更多的機(jī)制提供支持。多核處理器的出現(xiàn)很大程度上提升了處理器性能。為了充分發(fā)揮多核處理器高并行性的優(yōu)勢，面臨的一個基本問題是如何將工作均衡的分配到各個節(jié)點。對于多核系統(tǒng)，由于任務(wù)到達(dá)時間不確定性、任務(wù)在運(yùn)行過程中產(chǎn)生的不確定變化，使得多核系統(tǒng)中的一些節(jié)點任務(wù)較多，負(fù)載過重，而另一些節(jié)點卻是空閑的。負(fù)載均衡是把任務(wù)根據(jù)所有節(jié)點的負(fù)載情況按照一定的任務(wù)調(diào)度策略和調(diào)度算法進(jìn)行分配，以實現(xiàn)各節(jié)點統(tǒng)一開始工作，統(tǒng)一結(jié)束，不會因為部分節(jié)點任務(wù)輕處于空閑狀態(tài)，而另一部分節(jié)點任務(wù)負(fù)載過重而一直處于忙碌狀態(tài)[49]。下面部分主要針對采取局部隊列模型進(jìn)行任務(wù)分配問題的研究，并設(shè)計一種高效的任務(wù)調(diào)度算法，以滿足系統(tǒng)性能需求。 任務(wù)調(diào)度算法分類任務(wù)調(diào)度算法根據(jù)任務(wù)調(diào)度時機(jī)可以分為靜態(tài)任務(wù)調(diào)度算法和動態(tài)任務(wù)調(diào)度算法兩種[50]。（1）靜態(tài)任務(wù)調(diào)度算法在靜態(tài)任務(wù)調(diào)度中，所有任務(wù)在編譯階段根據(jù)任務(wù)的通信開銷、計算開銷、任務(wù)之間的依賴關(guān)系等屬性來確定各個節(jié)點的運(yùn)行任務(wù)以及各任務(wù)的執(zhí)行順序，一旦任務(wù)確定執(zhí)行處理器后，在運(yùn)行過程中將不再調(diào)整，一直運(yùn)行在該處理器內(nèi)核上。靜態(tài)任務(wù)調(diào)度相對簡單，運(yùn)行時調(diào)度器開銷較小，系統(tǒng)具有很好的可預(yù)測性。但是由于靜態(tài)任務(wù)調(diào)度任務(wù)對應(yīng)的執(zhí)行處理器一經(jīng)確認(rèn)就不予更改，未考慮任務(wù)到達(dá)時間、任務(wù)在運(yùn)行過程中產(chǎn)生的不確定以及任務(wù)運(yùn)行過程中節(jié)點的負(fù)載狀況，因此這種算法缺少靈活性，在某些情況下嚴(yán)重影響系統(tǒng)的整體性能。（2）動態(tài)任務(wù)調(diào)度算法動態(tài)任務(wù)調(diào)度是指在并行任務(wù)運(yùn)行過程中，根據(jù)任務(wù)的運(yùn)行情況以及各節(jié)點的負(fù)載狀況決定每個任務(wù)的執(zhí)行處理器節(jié)點。該算法具有更強(qiáng)的執(zhí)行能力，能夠根據(jù)系統(tǒng)的狀態(tài)信息動態(tài)決定任務(wù)分配。動態(tài)任務(wù)調(diào)度相對靜態(tài)任務(wù)調(diào)度靈活性較高，根據(jù)任務(wù)的動態(tài)運(yùn)行情況以及各處理器的負(fù)載情況進(jìn)行調(diào)整，更好的保證了系統(tǒng)負(fù)載平衡，提高系統(tǒng)并行性。但是動態(tài)調(diào)度算法不可避免的加大了額外開銷，如信息搜集、分析、存儲以及任務(wù)的移動，因此動態(tài)任務(wù)調(diào)度算法應(yīng)該盡可能的簡單、高效，這樣才能抵消這些額外開銷，充分發(fā)揮動態(tài)任務(wù)調(diào)度算法的優(yōu)勢。RTEMS對多核處理器的支持如果采用動態(tài)調(diào)度策略，不但可以彌補(bǔ)平均分配策略帶來的不足，而且可以充分利用共享內(nèi)存獲取各節(jié)點的負(fù)載狀態(tài)，進(jìn)而對任務(wù)進(jìn)行均衡分配。下面首先對現(xiàn)有動態(tài)任務(wù)調(diào)度策略進(jìn)行分析，在此基礎(chǔ)上提出一種基于系統(tǒng)整體效能和系統(tǒng)整體負(fù)載均衡的動態(tài)任務(wù)調(diào)度算法。 現(xiàn)有集中式動態(tài)任務(wù)調(diào)度策略RandCentLB調(diào)度策略，是一個隨機(jī)調(diào)度策略，即當(dāng)多核系統(tǒng)出現(xiàn)負(fù)載不均衡情況時隨機(jī)選擇一個處理器，實現(xiàn)任務(wù)重分配。該策略實現(xiàn)簡單，當(dāng)任務(wù)數(shù)量很大，并且任務(wù)之間通信非常小時，調(diào)度結(jié)果比較滿意。但是該策略有非常大的局限和不確定性。GreedyLB調(diào)度策略，首先找到系統(tǒng)中負(fù)載最小的處理器，然后將當(dāng)前未分配任務(wù)的最大負(fù)載分配給該處理器。該策略未考慮通信開銷，對于任務(wù)之間通信頻繁、通信代價大的系統(tǒng)并不一定能提高效率。GreedyComm調(diào)度策略在GreedyLB的基礎(chǔ)上進(jìn)行改進(jìn)，在選擇目標(biāo)機(jī)的時候不但考慮節(jié)點當(dāng)前負(fù)載情況，而且加進(jìn)通信開銷因素，一定程度上彌補(bǔ)GreedyLB調(diào)度策略的不足。RefineLB調(diào)度策略，是在系統(tǒng)運(yùn)行過程中不斷調(diào)整系統(tǒng)負(fù)載分布，系統(tǒng)每個節(jié)點都設(shè)有一個閾值，當(dāng)存在任務(wù)負(fù)載超過該閾值的節(jié)點時，啟動系統(tǒng)調(diào)度模塊，進(jìn)行任務(wù)重分配。該策略屬于任務(wù)發(fā)起者調(diào)動策略。由于該策略只考慮了系統(tǒng)中重載節(jié)點，算法實現(xiàn)簡單，并且通信開銷較少。RefineCommLB調(diào)度策略，類似于RefineLB，但是該策略在選擇任務(wù)接收者時考慮到了任務(wù)之間的通信開銷，以尋求一種更有益的選擇[51]。為了充分發(fā)揮多核處理器并行性能，必須找到一個合理的任務(wù)分配策略。任務(wù)策略的選擇首先要考慮具體系統(tǒng)結(jié)構(gòu)和任務(wù)類型，再在此基礎(chǔ)上尋求最優(yōu)任務(wù)調(diào)度策略[39]。任務(wù)調(diào)度問題已被證明是NP完全問題，所以在大多數(shù)情況下，只能取得問題的近似最優(yōu)解。并且一種具體的調(diào)度算法是在很多限制和先設(shè)條件下提出的，只能適應(yīng)某些特定的情況和環(huán)境。系統(tǒng)任務(wù)重新分配會帶來兩種開銷[52]：任務(wù)在節(jié)點上的執(zhí)行時間和節(jié)點之間的通信開銷。為了提高系統(tǒng)性能，一個優(yōu)秀的任務(wù)調(diào)度策略需要滿足兩個目標(biāo)：減少節(jié)點的執(zhí)行時間；減少節(jié)點之間的通信開銷。這是兩個相互沖突的目標(biāo)，一方面要想減少節(jié)點的執(zhí)行時間，達(dá)到縮短整個任務(wù)的執(zhí)行時間目的，必須將任務(wù)均衡分配到各個節(jié)點上，但這勢必會加大節(jié)點之間的通信開銷。另一方面，如果減少節(jié)點之間的通信開銷，則任務(wù)要盡量分配到一個節(jié)點中運(yùn)行，這又會導(dǎo)致系統(tǒng)負(fù)載嚴(yán)重不均衡，影響任務(wù)執(zhí)行結(jié)束時間。因此任務(wù)調(diào)度策略需要在這兩個目標(biāo)中達(dá)到一個平衡。基于對以上考慮提出一種更加全面調(diào)度策略，該策略不但考慮了系統(tǒng)各節(jié)點的負(fù)載情況和節(jié)點之間的通信開銷，而且考慮了系統(tǒng)中每個任務(wù)優(yōu)先級和系統(tǒng)整體負(fù)載狀況，最大限度的利用系統(tǒng)的并行性，提高系統(tǒng)整體性能。 動態(tài)任務(wù)調(diào)度模型動態(tài)任務(wù)調(diào)度模型可以形象描述多核系統(tǒng)任務(wù)調(diào)度過程，動態(tài)任務(wù)調(diào)度模型包括任務(wù)集、負(fù)載估計、調(diào)度策略和任務(wù)映射。對動態(tài)任務(wù)調(diào)度模型的求解過程就是在多核處理器系統(tǒng)環(huán)境下，尋求一個優(yōu)秀的調(diào)度策略[53]，該策略以任務(wù)集和節(jié)點負(fù)載情況作為輸入，將任務(wù)到節(jié)點的映射作為輸出。 任務(wù)集多核處理器系統(tǒng)中的任務(wù)集可表示為一個四元組.定義1（任務(wù)集）：，其中：，任務(wù)集合，每個頂點表示一個任務(wù)，表示任務(wù)i；，任務(wù)關(guān)系集合，任務(wù)頂點和邊的關(guān)系可表示為，即任務(wù)i是任務(wù)j的前驅(qū)，任務(wù)j是任務(wù)i的后繼，只有任務(wù)i完成之后，任務(wù)j才能開始；，任務(wù)運(yùn)行時間集合，表示任務(wù)i運(yùn)行時間；，通信時間集合，其中，越大表示任務(wù)i與j之間的通信代價越大。=0表示兩個任務(wù)之間無通信。根據(jù)定義1描述，可將系統(tǒng)任務(wù)集表示為一個加權(quán)的有向無環(huán)路圖DAG。： DAG圖例該圖中頂點表示系統(tǒng)所有任務(wù)，本例中共包括三個任務(wù)，其中每個任務(wù)又可以進(jìn)行分解，T1，T2，T3，T4屬于任務(wù)1，T5，T6，T7，T8屬于任務(wù)2，T9，T10，T11，T12屬于任務(wù)3。圖中有向邊表示任