Nucleus PLUS SMP的任務管理機制研究與測試

，，，

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

引 言

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

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

1 Nucleus PLUS SMP任務管理機制研究

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

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

1.1 軟親和性(soft-affinity)

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

1.2 硬親和性(hard-affinity)

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

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

Nucleus PLUS SMP的調(diào)度域分為兩種：SMP調(diào)度域和BCD調(diào)度域。一個CPU只能屬于一個調(diào)度域，且BCD調(diào)度域不能包含啟動CPU，每個任務也只能隸屬于一個調(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域分配任務(記為BCD tasks)，當某個任務屬于某個BCD調(diào)度域后，調(diào)度程序只在該BCD域上運行該任務，即使該BCD有CPU空閑，SMP調(diào)度程序仍不會將其用于其他任務。這一點與hard-affinity有所不同，對于硬親和性綁定的CPU，當其空閑或者優(yōu)先級比其綁定任務更高的其他任務就緒時，該CPU仍參與SMP調(diào)度。對于硬親和性綁定的任務，其隸屬的調(diào)度域為其綁定的CPU所在的調(diào)度域。

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

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

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

1.4 就緒隊列模型

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

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

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

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

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

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

1.5 任務管理相關數(shù)據(jù)結構及調(diào)度策略

1.5.1 任務管理相關的數(shù)據(jù)結構

(1)任務控制塊(TC_TCB)

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

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

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

每個CPU均具有一個獨立的上下文，該結構主要屬性如表2所列。

表2 TC_CPU_CB屬性

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

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

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

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

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

表4 就緒隊列的數(shù)據(jù)結構

(5)TCD_Sched_Change_CPUS

要在哪些CPU上進行任務調(diào)度，在進行任務調(diào)度前需設置此變量。

1.5.2 調(diào)度策略

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

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

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

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

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

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

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

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

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

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

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

圖3 TCCT_Control_To_System處理流程

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

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

1.6 多核下任務的互斥與同步

圖4 TCCT_Schedule處理流程

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

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

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

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

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

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

通過兩種手段查看測試結果：

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

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

圖6 任務時序分析圖

2.2 測試用例設計

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

2.2.1 任務狀態(tài)機測試

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

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

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

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

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

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

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

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

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

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

測試用例2：睡眠時間到。

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

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

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

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

2.2.3 負載均衡測試

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

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

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

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

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

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

2.2.4 軟親和性測試

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

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

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

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

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

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

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

2.2.6 硬親和性測試

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

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

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

2.2.7 核間通信測試

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

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

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

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

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

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

測試用例3：任務核間遷移。

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

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

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

2.2.8 任務同步/互斥測試

測試用例1：任務與任務之間使用自旋鎖進行同步/互斥。

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

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

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

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

測試用例2：任務與中斷之間使用自旋鎖進行同步/互斥。測試步驟同上。

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

結 語

浮明軍、姬希娜(高級工程師)，王振(工程師)，許英豪(助理工程師)：主要研究方向為智能變電站控制保護嵌入式軟件平臺的研發(fā)測試。