Nucleus PLUS SMP的任務(wù)管理機(jī)制研究與測試

，，，

(許繼電氣股份有限公司，許昌 461000)

引 言

隨著電力系統(tǒng)繼電保護(hù)產(chǎn)品的集成度不斷增加和產(chǎn)品性能的要求持續(xù)提高，多核處理器技術(shù)的應(yīng)用應(yīng)運(yùn)而生。要想有效發(fā)揮多核處理器的性能，操作系統(tǒng)是關(guān)鍵，因而操作系統(tǒng)對多核處理器的支持也成為業(yè)界的研究熱點(diǎn)[1]。只有充分了解操作系統(tǒng)在多核模式下的任務(wù)調(diào)度機(jī)制和管理策略，在此基礎(chǔ)上結(jié)合應(yīng)用需求對任務(wù)進(jìn)行合理分配，才能達(dá)到兼顧性能和效率的目的。

本公司的電力系統(tǒng)保護(hù)控制產(chǎn)品基于美國ATI公司的Nucleus PLUS操作系統(tǒng)進(jìn)行開發(fā)，出于兼容性和繼承性的需要，在進(jìn)行多核處理器開發(fā)時(shí)選用支持對稱多核處理器的操作系統(tǒng)Nucleus PLUS SMP。單核版本和SMP版本最大的區(qū)別是任務(wù)管理，為了充分發(fā)揮多核處理器性能，本文基于SMP架構(gòu)處理器雙核ARM Cortex-A9 MPCore，研究分析了Nucleus PLUS SMP的任務(wù)管理機(jī)制，建立了測試環(huán)境，并提出了一套測試用例，實(shí)現(xiàn)了對多核操作系統(tǒng)任務(wù)調(diào)度的測試研究。

1 Nucleus PLUS SMP任務(wù)管理機(jī)制研究

任務(wù)是相對獨(dú)立的可執(zhí)行單元和基本調(diào)度單元。每個任務(wù)都有獨(dú)立的堆棧空間和任務(wù)控制塊(TCB)。TCB描述了任務(wù)的狀態(tài)、調(diào)度信息和控制信息。Nucleus任務(wù)優(yōu)先級的范圍為0～255(0代表最高優(yōu)先級)。Nucleus任務(wù)調(diào)度策略為高優(yōu)先級優(yōu)先調(diào)度和時(shí)間片輪轉(zhuǎn)[2]調(diào)度結(jié)合使用。將任務(wù)按優(yōu)先級分組，組間采用高優(yōu)先權(quán)優(yōu)先調(diào)度算法，而組內(nèi)優(yōu)先級相同的任務(wù)則按時(shí)間片輪轉(zhuǎn)法調(diào)度。

為支持在SMP處理器上運(yùn)行，Nucleus PLUS SMP任務(wù)管理模塊在就緒任務(wù)的CPU歸屬方面，支持軟親和性、硬親和性和調(diào)度域劃分[3]，就緒隊(duì)列模型和調(diào)度策略等也隨之改變。使用自旋鎖機(jī)制來實(shí)現(xiàn)多核間的互斥同步，通過核間中斷(IPI)來實(shí)現(xiàn)核間通信。

1.1 軟親和性(soft-affinity)

軟親和性即根據(jù)調(diào)度歷史來影響任務(wù)再次調(diào)度時(shí)的目標(biāo)CPU，其目的是提高CPU Cache命中率，提高運(yùn)行效率。任務(wù)上次運(yùn)行所在的core記為prev_core，任務(wù)重新調(diào)度時(shí)的軟親和性包括兩種情況：①多個CPU空閑，prev_core為其中之一;②多個CPU上運(yùn)行著優(yōu)先級相同的最低優(yōu)先級任務(wù)，prev_core為其中之一。這兩種情況下，任務(wù)被再次調(diào)度到prev_core上。軟親和性策略中任務(wù)和prev_core的親和性較弱，讓位于高優(yōu)先權(quán)調(diào)度策略。例如：任務(wù)A的prev_core為core0，高優(yōu)先級任務(wù)A被重新調(diào)度時(shí)，如果core0上運(yùn)行中優(yōu)先級的任務(wù)B，core1上運(yùn)行低優(yōu)先級任務(wù)C，任務(wù)A則被調(diào)度在低優(yōu)先級任務(wù)C所在的core1上。

1.2 硬親和性(hard-affinity)

硬親和性限制任務(wù)只能在一組CPU上運(yùn)行。硬親和性用于：①對于性能要求較高的任務(wù)，提高其Cache命中率；②任務(wù)使用了只對某些CPU可見的外設(shè)。

1.3 調(diào)度域(sched-domain)

Nucleus PLUS SMP的調(diào)度域分為兩種：SMP調(diào)度域和BCD調(diào)度域。一個CPU只能屬于一個調(diào)度域，且BCD調(diào)度域不能包含啟動CPU，每個任務(wù)也只能隸屬于一個調(diào)度域。

系統(tǒng)啟動后，只有一個SMP調(diào)度域(系統(tǒng)調(diào)度域)，它包含所有CPU。用戶可通過NU_BCD_Multicore_Create系統(tǒng)函數(shù)在某些CPU上創(chuàng)建BCD調(diào)度域，此操作會將這些CPU從SMP調(diào)度域中清除。通過NU_BCD_Task_Add函數(shù)為BCD域分配任務(wù)(記為BCD tasks)，當(dāng)某個任務(wù)屬于某個BCD調(diào)度域后，調(diào)度程序只在該BCD域上運(yùn)行該任務(wù)，即使該BCD有CPU空閑，SMP調(diào)度程序仍不會將其用于其他任務(wù)。這一點(diǎn)與hard-affinity有所不同，對于硬親和性綁定的CPU，當(dāng)其空閑或者優(yōu)先級比其綁定任務(wù)更高的其他任務(wù)就緒時(shí)，該CPU仍參與SMP調(diào)度。對于硬親和性綁定的任務(wù)，其隸屬的調(diào)度域?yàn)槠浣壎ǖ腃PU所在的調(diào)度域。

以8核SMP處理器架構(gòu)為例，假如：①在CPU2、CPU3、CPU4上創(chuàng)建一個BCD調(diào)度域(記為BCD1)；②在CPU5、CPU6上創(chuàng)建另一個BCD域(記為BCD2)；③創(chuàng)建任務(wù)T1～T8，其中T1和T2分配給BCD1， T3和T4分配給BCD2，T5和T8硬親和性綁定在CPU7上。

調(diào)度域劃分和任務(wù)隸屬情況如圖1所示。

圖1 調(diào)度域劃分和任務(wù)隸屬情況

1.4 就緒隊(duì)列模型

就緒隊(duì)列模型用于解決SMP系統(tǒng)中任務(wù)排隊(duì)時(shí)CPU歸屬問題。一般有兩種隊(duì)列模型：全局隊(duì)列模型和局部隊(duì)列模型。對于全局隊(duì)列模型，所有CPU共享一個就緒隊(duì)列，優(yōu)點(diǎn)是自然實(shí)現(xiàn)了負(fù)載均衡，缺點(diǎn)是互斥訪問全局隊(duì)列帶來的性能損耗以及Cache命中率低。對于局部隊(duì)列模型，每個CPU分配一個就緒隊(duì)列，優(yōu)點(diǎn)是充分利用CPU上的Cache熱度，缺點(diǎn)是負(fù)載均衡性差[4]。Nucleus SMP綜合使用了這兩種隊(duì)列模型，其就緒隊(duì)列模型設(shè)計(jì)如下：

① 為每個調(diào)度域設(shè)置一個全局就緒隊(duì)列(記為GRQ)，SMP或BCD調(diào)度域中的所有任務(wù)共享該GRQ。

② 為每個CPU設(shè)置了一個局部/私有就緒隊(duì)列(記為LRQ)，hard-affinity任務(wù)在其綁定的CPU的LRQ中排隊(duì)。

對于每個就緒隊(duì)列，Nucleus SMP按優(yōu)先級將其劃分成256個子隊(duì)列(實(shí)現(xiàn)為雙向鏈表)，并利用“任務(wù)控制塊指針”(TC_TCB*)數(shù)組來管理子隊(duì)列的頭指針。

對于第1.3節(jié)中所舉例子，假如T1～T8均為就緒狀態(tài)且優(yōu)先級均為5，則就緒隊(duì)列狀態(tài)如圖2所示。注意：T5和T8為hard-affinity任務(wù)，它們的調(diào)度域雖為SMP調(diào)度域，但在其綁定的CPU7的LRQ中排隊(duì)。

圖2 就緒隊(duì)列狀態(tài)

1.5 任務(wù)管理相關(guān)數(shù)據(jù)結(jié)構(gòu)及調(diào)度策略

1.5.1 任務(wù)管理相關(guān)的數(shù)據(jù)結(jié)構(gòu)

(1)任務(wù)控制塊(TC_TCB)

為支持affinity和sched-domain，Nucleus SMP在TC_TCB中主要增加表1所列的數(shù)據(jù)成員。

表1 任務(wù)控制塊中任務(wù)調(diào)度有關(guān)的屬性

(2)CPU調(diào)度上下文(TC_CPU_CB)

每個CPU均具有一個獨(dú)立的上下文，該結(jié)構(gòu)主要屬性如表2所列。

表2 TC_CPU_CB屬性

(3) “調(diào)度域”(TC_SCHED_DOMAIN)

每個調(diào)度域均定義了該類型的實(shí)例，如表3所列。

表3 調(diào)度域定義的數(shù)據(jù)類型

(4) “就緒隊(duì)列”(TC_RQ)

每個CPU的LRQ和每個調(diào)度域的GRQ均采用的數(shù)據(jù)結(jié)構(gòu)如表4所列。

表4 就緒隊(duì)列的數(shù)據(jù)結(jié)構(gòu)

(5)TCD_Sched_Change_CPUS

要在哪些CPU上進(jìn)行任務(wù)調(diào)度，在進(jìn)行任務(wù)調(diào)度前需設(shè)置此變量。

1.5.2 調(diào)度策略

下面介紹各種任務(wù)調(diào)度時(shí)機(jī)及每種情況下的任務(wù)調(diào)度策略。

(1)阻塞態(tài)變?yōu)榫途w態(tài)

在創(chuàng)建新任務(wù)、任務(wù)阻塞等待的系統(tǒng)資源可用等情況下發(fā)生。

當(dāng)任務(wù)從阻塞態(tài)變?yōu)榫途w態(tài)時(shí)，將該任務(wù)插入其對應(yīng)的就緒隊(duì)列。如果該任務(wù)的優(yōu)先級大于就緒隊(duì)列的tc_high_ready_task_priority，則根據(jù)任務(wù)所在調(diào)度域的tc_low_sched_task_priority、tc_low_sched_task_cpus、軟硬親和性，設(shè)置TCD_Sched_Change_CPUS。然后調(diào)用TCCT_Control_To_System函數(shù)觸發(fā)任務(wù)調(diào)度。在此策略中，高優(yōu)先級任務(wù)搶占其調(diào)度域中最低優(yōu)先級任務(wù)，減少了全局任務(wù)切換次數(shù)[5]。

(2)運(yùn)行態(tài)變?yōu)榫途w態(tài)

在更高優(yōu)先級任務(wù)就緒、任務(wù)主動出讓CPU和時(shí)間片用完等情況下發(fā)生。

將該任務(wù)插入其就緒隊(duì)列。TCD_Sched_Change_CPUS設(shè)置為任務(wù)當(dāng)前運(yùn)行的CPU，然后調(diào)用TCCT_Control_To_System函數(shù)觸發(fā)任務(wù)調(diào)度。

(3)運(yùn)行態(tài)變?yōu)樽枞麘B(tài)

在請求的系統(tǒng)資源不可用、進(jìn)入睡眠等情況下發(fā)生。

將TCD_Sched_Change_CPUS設(shè)置為任務(wù)當(dāng)前運(yùn)行的CPU，調(diào)用TCCT_Control_To_System函數(shù)觸發(fā)任務(wù)調(diào)度。

上述3種任務(wù)調(diào)度發(fā)生情況均調(diào)用了TCCT_Control_To_System，其處理流程如圖3所示。

圖3 TCCT_Control_To_System處理流程

從中看出，當(dāng)要發(fā)生任務(wù)調(diào)度的CPU不是當(dāng)前CPU時(shí)，會向目標(biāo)CPU發(fā)送IPI。目標(biāo)CPU接收到IPI后，在IPI處理程序(ICC_Handle_IPI)中保存當(dāng)前運(yùn)行任務(wù)上下文，并調(diào)用TCCT_Schedule進(jìn)行任務(wù)切換。

TCCT_Schedule函數(shù)處理流程如圖4所示。

1.6 多核下任務(wù)的互斥與同步

圖4 TCCT_Schedule處理流程

Nucleus PLUS SMP提供自旋鎖機(jī)制來實(shí)現(xiàn)任務(wù)/中斷間的互斥與同步。自旋鎖是防止多處理器并發(fā)的一種鎖機(jī)制[6]，它有兩種狀態(tài)：“加鎖”狀態(tài)和“解鎖”狀態(tài)。任務(wù)或中斷處理程序請求自旋鎖時(shí)，如果該鎖為“解鎖”狀態(tài)(該鎖可用)，則嘗試將該自旋鎖置為“加鎖”狀態(tài)；若加鎖成功，代碼繼續(xù)進(jìn)入臨界區(qū)；如果該鎖為“加鎖”狀態(tài)(該鎖不可用)，則進(jìn)入忙等?！凹渔i”動作是一次“read-modify-write”操作，這個操作必須是原子的，這樣才能保證即使多個任務(wù)在給定時(shí)間自旋，也只有一個線程能獲取該鎖。這就引入了一個新的問題：多核架構(gòu)下，如何保證“read-modify-write”操作的原子性? 對于單核架構(gòu)，簡單的關(guān)中斷即可實(shí)現(xiàn)原子操作。對于多核架構(gòu)，由于多核上任務(wù)真正并行執(zhí)行，用關(guān)中斷實(shí)現(xiàn)原子操作失效。本文使用ARM Cortex-A9處理器，其在內(nèi)存訪問上增加了獨(dú)占監(jiān)測(Exclusive monitors)機(jī)制，并增加了LDREX和STREX指令?；谠撎幚砥鞯淖孕i通過這兩條指令實(shí)現(xiàn)了“加鎖”的原子操作。

2 Nucleus PLUS SMP任務(wù)調(diào)度測試

2.1 測試環(huán)境搭建

測試環(huán)境是由PC機(jī)、BDI3000、目標(biāo)系統(tǒng)組成。在PC機(jī)上，使用Sourcery Code Bench集成開發(fā)環(huán)境來編輯、編譯測試程序。在目標(biāo)開發(fā)板Zynq-7000[7](雙核ARM Cortex-A9 MPCore)上運(yùn)行測試程序。

測試環(huán)境搭建如圖5所示。

圖5 測試環(huán)境搭建

通過兩種手段查看測試結(jié)果：

① 測試程序從目標(biāo)系統(tǒng)的串口輸出某些運(yùn)行節(jié)點(diǎn)下任務(wù)、信號量等內(nèi)核對象的狀態(tài)，將其發(fā)送至PC機(jī)。

② Nuclues Trace作為Nuclues Kernel的嵌入式代碼模塊，跟蹤Kernel運(yùn)行期間的數(shù)據(jù)，通過JTAG、仿真器將其發(fā)送給PC機(jī)。PC端使用可視化分析界面查看跟蹤這些數(shù)據(jù)。圖6為任務(wù)時(shí)序分析圖。

圖6 任務(wù)時(shí)序分析圖

2.2 測試用例設(shè)計(jì)

任務(wù)管理測試分為下面幾類：任務(wù)狀態(tài)機(jī)測試、調(diào)度算法測試、負(fù)載均衡測試、軟親和性測試、BCD調(diào)度域測試、硬親和性測試、核間通信測試。

2.2.1 任務(wù)狀態(tài)機(jī)測試

(1)就緒態(tài)轉(zhuǎn)運(yùn)行態(tài)/運(yùn)行態(tài)轉(zhuǎn)就緒態(tài)

測試用例1：優(yōu)先級位于Top-N(對于雙核，N為2)的任務(wù)A就緒后運(yùn)行。

測試用例2：TA主動出讓CPU(NU_Relinquish),就緒隊(duì)列中下一個同優(yōu)先級任務(wù)運(yùn)行。

測試用例3：TA時(shí)間片用完，就緒隊(duì)列中下一個同優(yōu)先級任務(wù)運(yùn)行。

(2)運(yùn)行態(tài)轉(zhuǎn)阻塞態(tài)

測試用例1：因請求系統(tǒng)資源而阻塞。

測試用例2：調(diào)用NU_Sleep，進(jìn)入睡眠。

測試用例3：調(diào)用NU_Suspend_Task,無條件阻塞。

(3)阻塞態(tài)轉(zhuǎn)就緒態(tài)

測試用例1：所請求信號量資源可用。

測試用例2：睡眠時(shí)間到。

測試用例3：調(diào)用NU_Resume_Task,喚醒無條件阻塞任務(wù)。

2.2.2 調(diào)度算法測試

測試用例1：高優(yōu)先級搶占原則。兩個核上分別運(yùn)行中等優(yōu)先級和低優(yōu)先級任務(wù)。高優(yōu)先級任務(wù)就緒后，應(yīng)搶占低優(yōu)先級任務(wù)。

測試用例2：同優(yōu)先級時(shí)間片輪轉(zhuǎn)。創(chuàng)建4個相同優(yōu)先級的SMP任務(wù)，它們應(yīng)輪流被調(diào)度。

2.2.3 負(fù)載均衡測試

對于N核SMP系統(tǒng)，Nucleus SMP 將就緒隊(duì)列中優(yōu)先級最高的前N個任務(wù)調(diào)度到N個可用核上。Nucleus SMP每個調(diào)度域內(nèi)共用一個就緒隊(duì)列，實(shí)現(xiàn)了負(fù)載均衡。負(fù)載均衡避免了核的忙閑不均，提高了系統(tǒng)吞吐量。

測試用例1：SMP調(diào)度域內(nèi)負(fù)載均衡測試。

① 創(chuàng)建SMP任務(wù)TA、 TB 和TC。優(yōu)先級關(guān)系：TA>TB>TC。預(yù)期優(yōu)先級最高的TA和TB任務(wù)分別調(diào)度到2個核上運(yùn)行。

② TA或TB運(yùn)行完畢或阻塞后，預(yù)期TC被調(diào)度到空閑核上運(yùn)行。

測試用例2：BCD調(diào)度域內(nèi)負(fù)載均衡測試。

用例與上面類似，區(qū)別為任務(wù)是BCD任務(wù)。

2.2.4 軟親和性測試

在下面情況下，TA應(yīng)調(diào)度到core-prev上：

① TA被重新調(diào)度時(shí)，當(dāng)前空閑的核包括core-prev。

② 多個相同優(yōu)先級的任務(wù)運(yùn)行在N個核上，其中包括TA的core-prev,更高優(yōu)先級的TA被重新調(diào)度運(yùn)行。

2.2.5 BCD調(diào)度域測試

Nucleus SMP允許某些CPU作為BCD，并為之分配任務(wù)。

測試用例1：任務(wù)只運(yùn)行在其指定的BCD域上，即使其他調(diào)度域的CPU空閑。

測試用例2：即使BCD域的某個CPU空閑，調(diào)度程序仍不會將其用于非本調(diào)度域中的其他任務(wù)。

2.2.6 硬親和性測試

測試用例1：任務(wù)只能運(yùn)行在其硬親和性綁定的CPU上。

測試用例2：對于被硬親和性綁定的CPU，當(dāng)其空閑時(shí)，仍可參與其所在調(diào)度域內(nèi)其他任務(wù)的調(diào)度。

測試用例3：對于被硬親和性綁定的CPU，當(dāng)其上運(yùn)行的硬親和性任務(wù)的優(yōu)先級小于調(diào)度域某個就緒任務(wù)的優(yōu)先級時(shí)，硬親和性任務(wù)被搶占。

2.2.7 核間通信測試

測試用例1：阻塞不同核上的任務(wù)。

① TA綁定在CPU0上；TB綁定在CPU1上。

② TA調(diào)用NU_Suspend_Task阻塞TB，預(yù)期TA被阻塞。

測試用例2：喚醒不同核上的任務(wù)。

① TA綁定在CPU0上；TB綁定在CPU1上。

② TA調(diào)用NU_Retrieve_Events獲取事件1，阻塞；TB調(diào)用NU_Set_Events，設(shè)置事件1。預(yù)期TA被喚醒。

測試用例3：任務(wù)核間遷移。

① 創(chuàng)建硬親和性綁定在CPU1上的任務(wù)TB，TB在CPU1上運(yùn)行。

② 創(chuàng)建SMP任務(wù)TA，TA優(yōu)先級大于TB，TA在CPU0上運(yùn)行。

③ 在CPU1上創(chuàng)建BCD，并將TA指定給BCD。預(yù)期結(jié)果為TA遷徙到CPU1，搶占TB運(yùn)行。

2.2.8 任務(wù)同步/互斥測試

測試用例1：任務(wù)與任務(wù)之間使用自旋鎖進(jìn)行同步/互斥。

① 創(chuàng)建自旋鎖。

② TA調(diào)用NU_Spinlock_Obtain請求自旋鎖，預(yù)期TA請求自旋鎖成功。

③ TB調(diào)用NU_Spinlock_Obtain請求自旋鎖，預(yù)期TB進(jìn)入“忙等”。

④ TA調(diào)用NU_Spinlock_Release釋放自旋鎖，預(yù)期TB請求自旋鎖成功。

測試用例2：任務(wù)與中斷之間使用自旋鎖進(jìn)行同步/互斥。測試步驟同上。

測試用例3：中斷與中斷之間使用自旋鎖進(jìn)行同步/互斥。測試步驟同上。

結(jié) 語

浮明軍、姬希娜(高級工程師)，王振(工程師)，許英豪(助理工程師)：主要研究方向?yàn)橹悄茏冸娬究刂票Ｗo(hù)嵌入式軟件平臺的研發(fā)測試。