0 引言

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

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

1 多核嵌入式實(shí)時調(diào)度

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

1.1 全局調(diào)度

全局調(diào)度即任務(wù)可運(yùn)行于任一處理器核，操作系統(tǒng)會根據(jù)任務(wù)優(yōu)先級、空閑處理器核的情況進(jìn)行任務(wù)的動態(tài)分配。全局調(diào)度是比較簡單的調(diào)度算法，通過構(gòu)建一個全局就緒隊(duì)列來管理就緒任務(wù)。系統(tǒng)有空閑處理器核時便會 從全局就緒隊(duì)列中調(diào)度一個最高優(yōu)先級的任務(wù)。

多核采用該調(diào)度策略時，任務(wù)執(zhí)行的時序關(guān)系將從單核原有的串行執(zhí)行序列完全變?yōu)椴⑿袌?zhí)行，較低優(yōu)先級的任務(wù)將會與高優(yōu)先級的任務(wù)在不同處理器核上同時運(yùn)行。多核全局調(diào)度示意圖如圖1所示，在四處理器核系統(tǒng)中，任務(wù)1、任務(wù)2、任務(wù)3雖然優(yōu)先級不同，但能夠同時在不同核上運(yùn)行，當(dāng)處理器核3空閑時調(diào)度器將較低優(yōu)先級任務(wù)調(diào)度到該空閑核上運(yùn)行。在任務(wù)完全不相關(guān)的情況下，采用全局調(diào)度算法可以充分利用多核特性，有效利用空閑處理器提高系統(tǒng)總體處理機(jī)的利用率，自動平衡整個系統(tǒng)負(fù)載。

圖1 多核全局調(diào)度

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

① 無執(zhí)行序列：多核全局調(diào)度在提高任務(wù)執(zhí)行性能的同時，任務(wù)的執(zhí)行序列發(fā)生改變，原有任務(wù)之間的執(zhí)行關(guān)系將因?yàn)椴⑿袌?zhí)行而發(fā)生變化，需要對任務(wù)的調(diào)度安排進(jìn)行統(tǒng)籌考慮。

② 緩存命中率低：多核處理器中每個處理器核都有自己的緩存，其中存儲任務(wù)的相關(guān)數(shù)據(jù)，而在全局調(diào)度中任務(wù)可能會被調(diào)度到其他處理器核上，這無疑會降低緩存命中率，從而大幅度降低系統(tǒng)性能。

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

1.2 劃分調(diào)度

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

圖2 多核劃分調(diào)度

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

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

② 處理器總體利用率相對較低：任務(wù)綁定在固定處理器核上運(yùn)行會導(dǎo)致系統(tǒng)難以利用空閑處理器核，出現(xiàn)有的核空閑、有的核忙綠的低效率現(xiàn)象。

1.3 半劃分調(diào)度

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

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

圖3 多核半劃分調(diào)度

2 基于核集的多核實(shí)時調(diào)度方法

由于半劃分調(diào)度基于全局調(diào)度與劃分調(diào)度的思想，系統(tǒng)在減少任務(wù)跨核調(diào)度的基礎(chǔ)上，還可以盡可能充分地利用空閑處理器。但該方法仍然容易出現(xiàn)負(fù)載不平衡的現(xiàn)象，例如在航空航天領(lǐng)域，由于確定性需求，需要將大部分任務(wù)與處理器核建立綁定關(guān)系，所以仍然可能由于任務(wù)分配的不均勻?qū)е虏糠挚臻e處理器無法得到利用、浪費(fèi)處理器資源。

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

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

圖4 基于核集的半劃分調(diào)度

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

圖5 處理器選擇任務(wù)過程

3 基于核集的多核實(shí)時調(diào)度流程

基于核集的實(shí)時調(diào)度流程圖如圖 6 所示。

圖6 基于核集的實(shí)時調(diào)度流程圖

步驟1：嵌入式系統(tǒng)通常在中斷服務(wù)程序結(jié)束、任務(wù)因等待資源阻塞、高優(yōu)先級任務(wù)就緒等觸發(fā)調(diào)度事件發(fā)生后開始調(diào)度。

步驟2：獲取當(dāng)前核號，用于獲取該核親和隊(duì)列以及篩選滿足核集配置要求的任務(wù)集合。

步驟3：遍歷該核親和就緒隊(duì)列，找到隊(duì)列上最高優(yōu)先級任務(wù)PrivateHightestTask。

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

步驟5：獲取步驟4中任務(wù)集合中優(yōu)先級最高的任務(wù) GlobalHightestTask。

步驟6：判斷 PriveteHightestTask 的優(yōu)先級是否高于 GlobalHightestTask 的優(yōu)先級，如果是，則繼續(xù)步驟7，否則繼續(xù)步驟8。

步驟7：將 GlobalHightestTask 置為處理器核調(diào)度的后繼任務(wù)，繼續(xù)步驟11。

步驟8：判斷PriveteHightestTask 的優(yōu)先級是否等于 GlobalHightestTask 的優(yōu)先級，如果是，則繼續(xù)步驟9,否則繼續(xù)步驟10。

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

步驟10：將 PrivateHightestTask 置為處理器核調(diào)度的后繼任務(wù)，繼續(xù)步驟11。

步驟11：處理器核調(diào)度確定的后繼任務(wù)運(yùn)行。

步驟12：一次任務(wù)調(diào)度結(jié)束，等待下次調(diào)度事件觸發(fā)，進(jìn)入下一次調(diào)度流程，執(zhí)行步驟1。

4 結(jié)語

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

審核編輯：劉清