0 引言

在多任務環境下，嵌入式系統中通常運行著多于處理機數目的任務，這就要求操作系統能夠按照某種算法為處于就緒狀態的任務動態地分配處理機，處理機調度的實質是對處理器資源進行分配。調度算法的好壞直接影響系統運行時的性能(如響應的及時性、系統的吞吐量以及資源利用率等),是操作系統不可或缺的一部分。

多核處理器的引入使得嵌入式計算平臺中的任務能夠在不同處理器核心上并行運行，增加系統計算能力的同時也為系統調度帶來了新的挑戰。在單核處理器中調度程序僅需遍歷任務就緒表、找到最高優先級的任務即可，而在多核處理器中不僅要考慮優先級問題，還要考慮任務將在哪個 CPU 核上運行的問題。本文基于多核嵌入式實時操作系統半劃分調度算法，針對多核操作系統中任務調度存在的問題，在保證原有操作系統調度機制不被破壞的基礎上提出了一種基于核集的多核嵌入式調度方法。改進了原來調度策略中任務只運行于一個處理器核或者可以運行于所有核的狀況，使任務能夠運行于局部核，在一定程度上可以解決半劃分調度算法中負載不均衡問題。

1 多核嵌入式實時調度

多處理機調度分為全局調度(global scheduling)和劃分調度(partitioned scheduling)。全局調度允許任務在所有處理核心之間自由遷移；劃分調度則是將每個任務綁定到固定的處理核心上運行。全局調度能夠提高處理機的利用率，但卻會帶來額外的系統開銷；劃分調度則恰恰相反，任務只會在固定處理核上運行，緩存命中率較高，不會產生任務跨核遷移的花銷。但由于任務被綁定在固定核上，無法有效利用空閑處理器，處理機利用率較低。為了解決這一矛盾，研究者們提出一種半劃分調度算法，該方法將全局調度和劃分調度的行為特性進行綜合，吸納了兩種方法的優點。在任務調度過程中，一部分任務采用劃分調度思想，另外一部分任務則采用全局調度思想。這種策略可以均衡系統的負載，解決空閑處理器難以利用的問題。

1.1 全局調度

全局調度即任務可運行于任一處理器核，操作系統會根據任務優先級、空閑處理器核的情況進行任務的動態分配。全局調度是比較簡單的調度算法，通過構建一個全局就緒隊列來管理就緒任務。系統有空閑處理器核時便會 從全局就緒隊列中調度一個最高優先級的任務。

多核采用該調度策略時，任務執行的時序關系將從單核原有的串行執行序列完全變為并行執行，較低優先級的任務將會與高優先級的任務在不同處理器核上同時運行。多核全局調度示意圖如圖1所示，在四處理器核系統中，任務1、任務2、任務3雖然優先級不同，但能夠同時在不同核上運行，當處理器核3空閑時調度器將較低優先級任務調度到該空閑核上運行。在任務完全不相關的情況下，采用全局調度算法可以充分利用多核特性，有效利用空閑處理器提高系統總體處理機的利用率，自動平衡整個系統負載。

圖1 多核全局調度

雖然多核系統通過全局調度能夠帶來很多好處，但其存在著不可避免的缺點，主要包括以下三點：

① 無執行序列：多核全局調度在提高任務執行性能的同時，任務的執行序列發生改變，原有任務之間的執行關系將因為并行執行而發生變化，需要對任務的調度安排進行統籌考慮。

② 緩存命中率低：多核處理器中每個處理器核都有自己的緩存，其中存儲任務的相關數據，而在全局調度中任務可能會被調度到其他處理器核上，這無疑會降低緩存命中率，從而大幅度降低系統性能。

③ 全局就緒鏈表訪問沖突：系統中僅有一個全局就緒鏈表屬于核間共享數據，在某一時刻只能由一個核使用，訪問沖突會隨著核數的增大而愈加頻繁，增加系統任務切換花銷。

1.2 劃分調度

針對全局調度的上述缺點，一些多核嵌入式實時操作系統選擇使用劃分調度。劃分調度策略是對任務集進行劃分，每個任務都與特定的處理器核建立綁定關系(即指定任務的親和屬性),任務僅在預先分配的處理器核上執行。在任務執行的過程中，不會在處理器核間進行遷移。當創建一個任務時，完全由用戶來決定該任務在哪個處理器核上運行。劃分調度的基本思想如圖2所示，系統為每個處理器核建立一個任務就緒隊列，該隊列上的任務均為綁定親和屬性的任務，處理器核在進行任務調度時僅在對應自己核號的親和隊列(私有隊列)上選擇任務。

圖2 多核劃分調度

使用劃分調度策略時，任務運行的確定性比全局任務調度的確定性更好，且由于沒有任務的跨核調度，系統調度成本顯著降低，處理器的緩存命中率與單核情況下保持一致。相對全局調度，劃分調度主要存在以下缺點：

① 核間通信較為頻繁：由于任務綁定在核上執行，那么不同處理核上運行的任務之間交互較多時，將導致核間通信(中斷)的頻繁發生，如此會對任務的執行產生一定負面影響。

② 處理器總體利用率相對較低：任務綁定在固定處理器核上運行會導致系統難以利用空閑處理器核，出現有的核空閑、有的核忙綠的低效率現象。

1.3 半劃分調度

在全局調度模式下系統的總體處理機利用率較高，但卻可能帶來較大的系統開銷；劃分調度則恰恰相反，雖然調度花銷較少，但空閑處理機無法充分利用，處理機使用率較低。為了解決這一矛盾，學術界吸收了兩種調度方法的優點，基于劃分調度提出一種稱為半劃分調度的調度方法，該方法將全局調度與劃分調度結合，同時具有全局調度與劃分調度的行為特征。在系統進行任務調度時，大部分任務被預先劃分到一個固定的核心上運行，采用劃分調度策略；而剩余部分任務則采用全局調度策略，運行在多個核心上。

多核半劃分調度示意圖如圖3所示，半劃分調度中有兩種任務的就緒隊列，分別是全局就緒隊列和每核就緒隊列，當有 N 個處理器核時，共有 N+1 個就緒隊列。系統基于優先級的搶占式調度，處理器在調度時會選擇每核就緒隊列和全局就緒隊列中優先級最高的任務。這種策略可以緩解空閑處理器難以利用的問題、增強系統的負載均衡，同時在一定程度上彌補了全局調度與劃分調度的不足。

圖3 多核半劃分調度

2 基于核集的多核實時調度方法

由于半劃分調度基于全局調度與劃分調度的思想，系統在減少任務跨核調度的基礎上，還可以盡可能充分地利用空閑處理器。但該方法仍然容易出現負載不平衡的現象，例如在航空航天領域，由于確定性需求，需要將大部分任務與處理器核建立綁定關系，所以仍然可能由于任務分配的不均勻導致部分空閑處理器無法得到利用、浪費處理器資源。

此外，當全局就緒鏈中的任務較多時，處理器緩存命中率也會降低、影響系統性能。本文基于半劃分調度提出一種基于核集的嵌入式實時調度方法，為任務增加核集屬性。用戶在配置好任務的核集屬性后，如果設置任務的親和屬性，只能在指定核集范圍內設置；如果未設置親和屬性，則任務可全局調度，但此全局調度被限定為核集范圍，即局部全局調度。如果用戶沒有為任務配置核集，則默認核集為所有核。

基于核集的半劃分調度示意圖如圖4所示，任務A指定核集為[0,1],那么任務指定親和屬性只能是0核或者1核；如果不指定親和屬性，則任務進行全局調度，但調度范圍由最初的[0,1,2,3,…,N] 縮小為核集指定的[0,1],任務只能在0核或者1核上運行。

圖4 基于核集的半劃分調度

在處理器核選擇后繼任務時，對全局就緒隊列多加一層篩選，將任務核集中包含當前處理器核(即滿足核集配置的任務)單獨組成一個鏈表。在滿足核集配置的任務鏈表中找到最高優先級任務，并與親和就緒隊列中最高優先級任務進行比較，將優先級高的任務調度到該處理器核上運行。處理器選擇任務過程如圖5所示。核2目前空閑或者需要重調度，首先按優先級從低到高依次遍歷全局就緒隊列：任務A核集不包含核2，不滿足核集配置，繼續遍歷；任務B核集包含核2,加入到滿足核集配置的任務鏈表；以此類推，繼續遍歷直到最高優先級任務X，核集不包含核2,第一輪遍歷完畢，篩選出全局就緒隊列中滿足核集配置要求的任務集合。然后確認任務B是滿足核集配置要 求的任務集合中優先級最高的任務，將任務B的優先級與核2親和隊列中最高優先級進行比較，兩者取較高優先級的任務在核2上運行。

圖5 處理器選擇任務過程

3 基于核集的多核實時調度流程

基于核集的實時調度流程圖如圖 6 所示。

圖6 基于核集的實時調度流程圖

步驟1：嵌入式系統通常在中斷服務程序結束、任務因等待資源阻塞、高優先級任務就緒等觸發調度事件發生后開始調度。

步驟2：獲取當前核號，用于獲取該核親和隊列以及篩選滿足核集配置要求的任務集合。

步驟3：遍歷該核親和就緒隊列，找到隊列上最高優先級任務PrivateHightestTask。

步驟4：遍歷全局就緒隊列，將滿足核集配置的任務篩選出來單獨組成一個任務集合。

步驟5：獲取步驟4中任務集合中優先級最高的任務 GlobalHightestTask。

步驟6：判斷 PriveteHightestTask 的優先級是否高于 GlobalHightestTask 的優先級，如果是，則繼續步驟7，否則繼續步驟8。

步驟7：將 GlobalHightestTask 置為處理器核調度的后繼任務，繼續步驟11。

步驟8：判斷PriveteHightestTask 的優先級是否等于 GlobalHightestTask 的優先級，如果是，則繼續步驟9,否則繼續步驟10。

步驟9：將 PrivateHightestTask 與 GlobalHightest Task中就緒時間長的任務置為處理器核調度的后繼任務，繼續步驟11。

步驟10：將 PrivateHightestTask 置為處理器核調度的后繼任務，繼續步驟11。

步驟11：處理器核調度確定的后繼任務運行。

步驟12：一次任務調度結束，等待下次調度事件觸發，進入下一次調度流程，執行步驟1。

4 結語

多核嵌入式系統中半劃分調度使用一個全局運行隊列來實現負載均衡，以此來提高劃分調度的處理器利用率。本文針對半劃分調度方法存在的多核負載不均衡問題，提出了改進的基于核集的調度算法，與原來的半劃分調度算法相比，理論上該方法在不破壞原有系統調度的前提下，改善了半劃分調度算法中處理器負載不均衡的問題，同時能夠保證很好的實時性，也可為未來多核嵌入式容器運行配置提供支撐。目前已經在 FT1500-A 上完成了開發測試，任務可正常運行，且可配置任務核集屬性，任務只可在指定核集范圍內運行，下一步工作將通過實驗驗證該調度算法在負載均衡方面是否優于原來的半劃分調度。

審核編輯：劉清