基于嵌入式多核系統的新型邊界公平調度器設計

朱長昊，張鳳登，楊甲豐

（上海理工大學光電信息與計算機工程學院，上海 200093）

0 引言

多核處理器經過十幾年發展，逐漸成為市場主流，應用于多媒體計算、嵌入式設備、個人計算機等多個領域?；诙嗪讼到y的調度算法成為關鍵技術點，而調度算法有效性直接影響整個系統實時響應能力與資源使用率［1］。

Liu 等［2］建立了實時調度系統模型，并首次提出系統利用率相關概念；Baruah 等［3-4］分析了多處理器平臺，提出公平調度（Boundary Fair，BF）的思想，在離散時間模型下，利用“特征字符串”標記任務優先級從而有效完成任務調度；Anderson 等［5］基于流體調度的思想簡化公平調度的概念，改進公平調度算法使其調度開銷更小，并在文獻［6-7］中首次針對公平調度中的任務在每個時間單元作出決策需大量調度開銷的問題，提出了早期釋放的概念，以保證空閑處理器資源可有效利用；文獻［8］對公平調度算法相關研究進行總結，并依次通過實驗評估算法優缺點；Zhu 等［9］結合公平調度的概念，提出一種在任務調度截止時間邊界位置進行調度決策的算法，有效解決了調度過程中任務切換與遷移造成的開銷過大的問題；Nelissen 等［10］將BF 算法擴展到零星任務集的調度問題上；張慧娟等［11］歸納了多核系統中較成熟的調度算法，分析了目前解決調度開銷過大問題的方法；吳星等［12］對BF 算法在多處理系統平臺上的調度進行研究，實現了周期任務和非周期任務混合的任務實時調度；劉碩［13］總結了任務可調度性概念；梁浩等［14］基于實際過程中處理器系統不能有效解決實時的調度問題，提出一種新的可調度分析方法以增加實時任務集中可調度任務數量；鄒圣雷［15］成功地將已有幾種經典的調度算法移植到Linux 系統上以驗證調度算法有效性。

本文基于現有BF 算法研究成果，依據流體調度思想簡化BF 調度算法原理，并給出相關證明。在此基礎上提出ER-BF 算法以解決任務中斷阻塞時空閑處理器內核無法得到有效利用的問題，最后設計出新的邊界公平調度器，通過實際任務參數對比驗證新調度器有效性。

1 系統模型與可調度性分析

1.1 系統模型

在m個具有相同處理能力的多核處理器系統平臺上，調度1 個包含n個任務集的周期性實時任務，1 個周期任務集τ={τ1,τ2,…τn}由n個周期任務組成，每個任務τi={pi,di,ei}由其周期pi、截止時間di和最壞執行時間ei組成，任務執行時間ei不可以超過周期pi，即ei≤pi，且為系統時間單元整數倍。算法研究是基于任務，具有隱式截止期，即di=pi。任務τi利用率為wi且wi=ei/pi，wi≤1(i=1,2…n)，若wi=1，該任務可直接分配1 個處理器內核執行。BF 算法以兩個連續的任務截止期為邊界，用bk表示調度邊界［9］，即調度器將在k時刻為下一時間片作出調度決策，k時刻對應的時間片表示為TSk，則TSk邊界為bk和bk+1。用B={b0,b1,b2,b3,…}表示調度邊界集合，其中b0=0，且bk

任務再被調度時有約束條件：①處理器內核不能同時共享同一個任務；②一個任務至多只能分配給一個處理器內核，即任務不容許并行［8］；③該任務集的任務需相互獨立，每個任務在執行期間不影響其他任務的釋放時間。

1.2 可調度性分析

在多核處理器系統調度問題中，1 個任務集若可被該系統調度，則該任務集中每個任務都要在其調度周期內滿足其截止期要求，這也是1 個任務集可被調度的充分必要條件［16］。

定理1 在具有隱式截止期的任務集中，只有所有任務利用率總量不超過所有處理器總系統利用率，任務集才可被調度。即：

證明：將任務τi被分割成時間單元的無限序列，稱為子任務［13］（Subtask）。每個子任務都有一個時間單元的執行時間，任務τi的第j個子任務表示為τi,j且j≥1。每個子任務都有其釋放時間r(τi)，截止時間d(τi)和運行窗口|w(τi)|，顯然對于子任務的釋放應該是在前一個子任務執行完畢后才釋放子任務，運行窗口應該處于釋放時間與截止期之間。表達為：

由式（3）可以計算得出式（4）。

為了保證同一個任務多個子任務不在同一調度窗口重疊，且每個子任務均可滿足在截止期前被調度，以一個子任務窗口為例，用U(τi,t)表示每個子任務在該窗口調度利用率分布情況，根據式（3）、式（4）可得：

根據式（5），在t=r(τi)時對于任意的正數x，都有≥x。由此可得：

在t=d(τi)-1 時，對于任意正數x，都有≥x，即-≤-x。由此可得：

綜上，對于任意的時間單元t，都有U(τi,t) ≤wi，即當時，滿足，則該任務集是可被調度的，原命題得證。

假設每個任務處理時間與任務利用率成比例，在離散時間系統中，任務總是執行系統單位時間整數倍，所以任務執行可能會偏離流體調度，為了測量流體調度偏差，引入任務分配誤差（lag），相關定義如下：

定義1 設一種調度為流體調度（Fluid Schedule）［5］，當且僅當對于任意時間t≥0，每個任務τi在時刻ai(t)釋放其作業，已執行Ui× (t-ai(t))個時間單元。任務τi的lag是在流體調度中相同時刻t應執行工作量與在實際調度中直到時刻t執行的τi激活任務工作量之差，如式（8）所示。

其中ai(t)是τi的激活任務到達時間。

定義2 對于任務τi的調度可被稱作邊界公平［20］，當且僅當在任何任務的執行邊界處滿足：

給定調度的分配誤差為lagi(t)，BF 調度要求任務在每個邊界進行調度的分配誤差總是小于系統時間單位，這主要因為系統是在離散的時間單元運行調度算法完成調度決策。

定理2 對于一個任務τi在時刻t，如果其實際執行時間比相應流體調度理論時間更短，即lagi(t) >0，表示該任務在時刻t滯后；如果實際執行時間比相應流體調度理論時間長，即lagi(t) <0，表示該任務在時刻t超前；如果其實際執行時間與相應流體調度時間相同，即lagi(t) <0，表示該任務在時刻t準時執行。

本文以1 個實際任務τi=(9,15,15)在處理器內核上進行調度的情況為例進行說明。該任務利用率為Ui=0.6 <1，滿足前文證明的可調度性條件。如圖1 所示，該任務在不同時刻執行時存在不同的調度可能性，在t=6 時刻系統分配的實際時間單元分別為3 和4 的情況下，任務出現的滯后與超前情況偏離了理想的流體調度（見圖1（a）線）。為了保證任務在其截止期前完成調度，在該時刻之后，系統需分配更多時間單元給出現滯后調度（見圖1（c）線）的情況，且應分配更少的執行時間單元給出現超前調度（見圖1（b）線）的情況。但是無論中間如何分配執行時間單元，最后在時刻t=15 時，任務均需執行完畢。

Fig.1 Ideal fluid scheduling，lagging scheduling and advanced scheduling圖1 任務理想流體調度、滯后調度與超前調度

綜上所述，只有在所有任務利用率總量不超過所有處理器核總系統利用率，且在每個調度邊界分配誤差不超過1 時，才可認定該任務集可被BF 算法調度。

2 邊界公平調度算法

2.1 基礎定義與定理

BF 調度算法為每個邊界時間與下一個截止期邊界之間的時間單元分配子任務執行，確定任務優先級時需考慮任務未來計算需求，保證任務在下一個時間點和未來任意邊界點均不會錯過截止期。所以對于有隱式截止期的周期性任務τi的下一邊界bk+1應該為當前邊界bk之后最早的截止時間，表達如式（10）所示。

為了確保每個邊界公平性，每個任務τi必須分配一些整數的強制性單元，如果在為每個任務分配強制執行時間單元后，某些邊界內還存在空閑的時間單元，則這些時間單元將動態地分配給符合條件的任務，BF 算法關鍵是要根據任務優先級分配這些可選單元。相關定義、定理及證明如下文所示。

定義3 BF 調度算法計算區間[bk,bk+1)內的最少執行時間，以滿足下個邊界區間內任務執行公平性，即lagi(bk+1)<1，這個最少的執行時間被稱作強制執行時間單元（Mandatory Time Units）［9］，分配給任務τi的強制執行時間定義為：

定義4 處理器核在邊界區間[bk,bk+1)執行完任務的強制執行時間后，某個任務可能存在沒有被執行的部分，這些未被執行的部分被稱作掛起的工作（Pending Task）［9］，記為PWik。一個任務被掛起的工作表示其在該邊界時刻分配誤差與執行時間和強制執行時間的差值，如式（12）所示。

任務在時間區間的執行時間為(bk+1-bk)·wi，被掛起的工作是該任務完成其強制執行時間后的小數部分，所以lagi(bk+1)=PWik+1-oik+1。

定理3 設任務已經分配完成強制執行時間，任務τi在下一個邊界時刻bk+1的分配誤差需要滿足lagi(bk)<1 以保證任務在邊界時刻的公平性，若在這個邊界區間內已經執行分配的強制時間，剩下未分配時間稱作可選分配時間（Remaining Time Unit），記為RU(bk,bk+1)。

證明：邊界區間[bk,bk+1)中，對于m個處理器內核來說，可用來分配的執行時間為m·(bk+1-bk)，但是每個任務均需有強制的執行時間，這些任務在邊界區間[bk,bk+1)強制執行時間結束后，m個處理器內核剩余下來的分配時間是可選分配時間的值。

可選分配時間應分配給任務，則每個任務都需競爭使用RU(bk,bk+1)個時間單元，以實現任務在截止期前完成調度，但是每個任務最多可競爭接收1 個時間單元的可選分配時間。任務τi在[bk,bk+1]的時間單元內若被分配1 個可選分配時間，記為oik+1=1，否則oi

k+1=0。定理4 如果任務利用率之和小于等于處理器內核個數，在所有邊界集合B={b0,b1,b2,b3,…bn-1}內，=0且lagin-1<1，對于所有處理器內核和在邊界內的總處理時間來說，滿足式（14）。

證明：通過反證法進行證明。在以上條件下，若假設原命題不成立，即(bk+1-bk)·m<，對于每個邊界處滿足總的分配誤差為0 且總系統利用率為m，則根據定義4，有以下等式成立：

顯然對于任意一個任務集，確定好強制執行時間后，其未被執行的部分不少于0，即，與假設相矛盾。所以假設不成立，原命題成立。

2.2 任務優先級判定

每個任務在每個邊界內的執行都有其優先級，根據定義1，如果1 個正在執行的任務τi在邊界時刻t被打斷執行，則發現這個任務分配誤差將逐漸增大，顯然它的值與任務利用率Ui成比例關系，當任務τi有x個時間單元未被執行，其分配誤差會變為：

根據定義2，任務分配誤差需滿足在任意一個邊界時刻t有lagi(t) <1，所以用最小的時間單位x表示任務τi的緊急因子（Urgency Factory），記為UFi(t)。如果τi從當前時刻t到時刻t+x沒有執行，則lagi(t+x)將超過1，這個量可通過式（17）求解。

定義5 任務τi在時刻t的緊急因子為UFi(t)，如果τi從時刻t到時刻t+x沒有執行，則其在時刻t+UFi(t)的分配誤差lagi(t+UFi(t))大于等于1，如式（18）所示。

假設在時刻t，停止執行任務τi，并在最后一個時間單元恢復任務執行，即不在t到t+UFi(t) -1 時間內執行任務τi，則根據定義1，任務在時刻t+UFi(t) -1 的分配誤差為：

為了保證τi趕上時刻t的流體調度偏差，需執行y個時間單元的任務，如式（20）所示。

其中，y值可被定義為在t時刻，τi恢復到分配誤差變為0 需要的時間單元，被稱為恢復時間（Recovery Time），記為ρi(t)，則可給出恢復時間的定義。

定義6 任務τi在時刻t上的恢復時間ρi(t)是任務τi準時完成執行所需要的最小執行時間，如式（21）所示。

根據定義5 與定義6，對于兩個任務τi與τj，在時刻t任務τi優先級高于τj，記作τi?τj，約束條件為：UFi(t) UFj(t) ∧ρi(t) >ρj(t)。

任務緊急因子越小說明任務如果再不執行，其分配誤差將會大于1，即任務優先級越高。而任務恢復時間越大，說明τi需要比τj用更多的執行時間彌補其在流體調度過程的延遲，但更長的時耗也限制了未來調度決策。若兩個任務緊急因子與恢復時間相同，即兩個任務優先級相同，則可由調度器決定哪個任務優先調度。

2.3 改進邊界公平調度算法原理

在BF 算法中，為了使所有任務在其截止期前完成，在確定強制執行時間后，由兩個條件判斷哪些任務可優先獲得可選執行時間。

條件1 根據定理4可知manki(bk+1-bk)<(bk+1-bk)，這樣可避免因1 個處理器核在邊界時間片[bk,bk+1)由于可分配給任務的時間單元不夠，導致任務進入下個處理器核執行，即任務在多個處理器核上并發執行的問題，

條件2 更高優先級的任務有資格獲得可選的執行時間單元。

這保證了在每個邊界的公平性。通過概念分析發現，BF 算法要求在每個邊界處分配誤差為0。如果去掉分配誤差必須大于1 的約束條件，即容許任務超前完成，以保證有效利用處于空閑狀態的處理器內核，稱之為連續型調度策略，更改可調度性約束后的算法稱為ER-BF 調度算法。

由于任務可提前釋放執行，ER-BF 算法給每個任務分配可選時間單元的數量沒有限制。同時為了讓處理器內核有效處理任務的中斷，提高調度效率，若Ui>m/2，表示系統為重載系統，相對應的為輕載系統。對于重載系統，ER-BF 算法需考慮將中斷任務分配到空閑的內核上執行，以此取代BF 算法使用的固定內核執行中斷，這樣可有效減少任務中斷過程中的阻塞問題。

（1）應該樹立科學的質量管理理念，整個建筑工程中的全部施工者都應該對自己應盡的責任和義務以及施工合同中的內容有一個清晰的了解，并且在施工的過程中，嚴格按照施工合同中的規定完成自己的工作。同時建立完備的施工安全和質量管理方案，在加強對建筑工程施工質量控制的前提下，通過實行有效的措施，杜絕施工過程中會發生的種種問題，從而確保建筑工程的施工質量。

根據McNaughton［17］提出的環繞算法，將執行時間分配到各個內核上并生成靜態調度表，規則描述如下：

（1）分配給每個處理器核的執行時間不容許超過該邊界時間長度TSk。即：

（2）分配給總處理器內核的執行時間不超過處理器內核在該邊界的可用來處理任務的總時間。即：

假設有可被BF 算法調度的任務集τ={τ1,τ2,τ3,τ4,τ5}，如圖2 所示，可以表示1 個邊界內任務在5 個內核上的執行情況。

Fig.2 Task set allocation圖2 任務集分配情況

圖2 中陰影部分指當前任務在該處理器內核上未執行完遷移到下1 個處理器內核上執行的部分。

3 ER-BF 調度器設計與仿真對比

3.1 ER-BF 調度器設計流程

基于ER-BF 算法原理，設計新型邊界公平調度器程序流程，如圖3 所示。

Fig.3 ER-BF scheduler program flow圖3 ER-BF 調度器程序流程

步驟1 輸入任務集并計算任務集每個任務利用率，對任務集進行可調度性分析，若任務集可使用ER-BF 調度算法進行調度，則可根據每個任務周期確定每個周期性任務的任務調度邊界bk，同時要確保bk小于該任務集所有任務周期最小公倍數（LCM）。

步驟2 計算任務在每個邊界處的分配誤差，即每個任務在其邊界處調度的分配誤差lagi(bk)<1，如果所有任務在其邊界處分配誤差小于1，則可證明任務在邊界前執行具有公平性。之后根據定義3 計算任務在某個邊界區間[bk,bk+1)內強制執行時間manki(bk,bk+1)，根據定理3 計算任務可選分配時間RU(bk,bk+1)，同時根據定義4 計算被掛起的工作PWi。

步驟3 通過定義5、定義6 計算兩個任務的緊急因子UFi(t)和恢復時間ρi(t)，并比較任務優先級。

步驟4 根據條件1 與條件2 確定哪些任務可獲得可選執行時間，按照每個任務在每個邊界內的優先級與執行的時間單元生成任務調度表。

3.2 實驗仿真設計

本文基于Litmus-RT 平臺對ER-BF 調度器進行設計［18］。Litmus-RT 平臺是基于Linux 系統為實時系統研究提供內核級別抽象的接口實驗平臺，可用于實時可調度性測試、任務集生成和實驗數據采集。實驗平臺搭建后，導入實驗任務參數，生成任務集，最后分配任務生成調度表，對比ER-BF 調度器與BF 調度器執行效率。ER-BF 調度器偽代碼為：

3.3 兩種調度器對比評估

完成兩種調度器設計后，輸入任務集Γ={τ1,τ2,τ3,τ4}，其中每個任務參數為τ1=(2,5,5)、τ2=(3,15,15)、τ3=(3,15,15)和τ4=(20,30,30)，任務ID 為{1,2,3,4}，將任務集Γ執行于兩個內核上。計算可得知UΓ=1.47 <2，滿足可調度性條件，且該系統為重載系統。任務集Γ通過BF 調度器執行生成的調度表，如圖4 所示，通過ER-BF 調度器執行生成的調度表，如圖5 所示。

Fig.4 Schedule generated by BF scheduler for task set Γ圖4 任務集Γ 通過BF 調度器生成的調度

Fig.5 Schedule generated by ER-BF scheduler for task set Γ圖5 任務集Γ 通過ER-BF 調度器生成的調度

基于同1 個任務集，從圖4 可看出，使用BF 調度器，最壞的情況是每5 個時間單元就有3 個被阻塞。從圖5 看出，通過增加連續工作機制，不僅可縮短任務完成時間，而且中斷阻塞時間點較圖4 明顯減少，由于中斷即可將任務傳遞至空閑的處理器內核，縮短了中斷響應時間［19］。由此可知BF 調度器是按一定進度執行任務，這使任務的lag在限定的(-1,1)之間，而ER-BF 調度器允許任務超前執行，在lagi(t) <0 的條件下，有更多時間裕度留給中斷響應以便進一步處理，可縮短中斷響應時間。

針對任務集Γ，用兩種調度器依次執行幾個任務周期，觀察隨著任務中斷的增多，中斷平均響應時間情況。由圖6 可知隨著任務中斷數增多，相比于BF 調度器，任務通過ER-BF 調度器調度的總平均中斷響應時間縮短56%以上。

Fig.6 Average response time of task set interruption under two schedulers圖6 兩種調度器下任務集中斷的平均響應時間

4 結語

本文首先基于多核系統，通過流體調度思想分析BF 調度算法原理，給出相關定義并證明其定理，分析簡化該算法后提出任務優先級對比規則，以支持任務集滿足其截止時間；由此去掉任務不可超前執行的約束條件，即分配誤差可容許小于-1，改進BF 調度算法后提出ER-BF 調度算法；最后基于ER-BF 算法設計調度器，將同1 個任務集通過這兩種調度器進行調度，生成調度表。實驗結果表明，ER-BF 可有效減少任務中斷阻塞概率，且任務平均中斷響應時間減少超過56%，大幅降低了系統開銷。但本文僅基于虛擬的多核系統條件下進行驗證，并沒有實際運用于多核處理器任務調度，調度器實際性能有待進一步檢驗。