朱長昊，張鳳登，楊甲豐

（上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093）

0 引言

多核處理器經(jīng)過十幾年發(fā)展，逐漸成為市場主流，應(yīng)用于多媒體計(jì)算、嵌入式設(shè)備、個(gè)人計(jì)算機(jī)等多個(gè)領(lǐng)域?；诙嗪讼到y(tǒng)的調(diào)度算法成為關(guān)鍵技術(shù)點(diǎn)，而調(diào)度算法有效性直接影響整個(gè)系統(tǒng)實(shí)時(shí)響應(yīng)能力與資源使用率［1］。

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

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

1 系統(tǒng)模型與可調(diào)度性分析

1.1 系統(tǒng)模型

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

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

1.2 可調(diào)度性分析

在多核處理器系統(tǒng)調(diào)度問題中，1 個(gè)任務(wù)集若可被該系統(tǒng)調(diào)度，則該任務(wù)集中每個(gè)任務(wù)都要在其調(diào)度周期內(nèi)滿足其截止期要求，這也是1 個(gè)任務(wù)集可被調(diào)度的充分必要條件［16］。

定理1 在具有隱式截止期的任務(wù)集中，只有所有任務(wù)利用率總量不超過所有處理器總系統(tǒng)利用率，任務(wù)集才可被調(diào)度。即：

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

由式（3）可以計(jì)算得出式（4）。

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

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

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

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

假設(shè)每個(gè)任務(wù)處理時(shí)間與任務(wù)利用率成比例，在離散時(shí)間系統(tǒng)中，任務(wù)總是執(zhí)行系統(tǒng)單位時(shí)間整數(shù)倍，所以任務(wù)執(zhí)行可能會(huì)偏離流體調(diào)度，為了測量流體調(diào)度偏差，引入任務(wù)分配誤差（lag），相關(guān)定義如下：

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

其中ai(t)是τi的激活任務(wù)到達(dá)時(shí)間。

定義2 對于任務(wù)τi的調(diào)度可被稱作邊界公平［20］，當(dāng)且僅當(dāng)在任何任務(wù)的執(zhí)行邊界處滿足：

給定調(diào)度的分配誤差為lagi(t)，BF 調(diào)度要求任務(wù)在每個(gè)邊界進(jìn)行調(diào)度的分配誤差總是小于系統(tǒng)時(shí)間單位，這主要因?yàn)橄到y(tǒng)是在離散的時(shí)間單元運(yùn)行調(diào)度算法完成調(diào)度決策。

定理2 對于一個(gè)任務(wù)τi在時(shí)刻t，如果其實(shí)際執(zhí)行時(shí)間比相應(yīng)流體調(diào)度理論時(shí)間更短，即lagi(t) >0，表示該任務(wù)在時(shí)刻t滯后；如果實(shí)際執(zhí)行時(shí)間比相應(yīng)流體調(diào)度理論時(shí)間長，即lagi(t) <0，表示該任務(wù)在時(shí)刻t超前；如果其實(shí)際執(zhí)行時(shí)間與相應(yīng)流體調(diào)度時(shí)間相同，即lagi(t) <0，表示該任務(wù)在時(shí)刻t準(zhǔn)時(shí)執(zhí)行。

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

Fig.1 Ideal fluid scheduling，lagging scheduling and advanced scheduling圖1 任務(wù)理想流體調(diào)度、滯后調(diào)度與超前調(diào)度

綜上所述，只有在所有任務(wù)利用率總量不超過所有處理器核總系統(tǒng)利用率，且在每個(gè)調(diào)度邊界分配誤差不超過1 時(shí)，才可認(rèn)定該任務(wù)集可被BF 算法調(diào)度。

2 邊界公平調(diào)度算法

2.1 基礎(chǔ)定義與定理

BF 調(diào)度算法為每個(gè)邊界時(shí)間與下一個(gè)截止期邊界之間的時(shí)間單元分配子任務(wù)執(zhí)行，確定任務(wù)優(yōu)先級(jí)時(shí)需考慮任務(wù)未來計(jì)算需求，保證任務(wù)在下一個(gè)時(shí)間點(diǎn)和未來任意邊界點(diǎn)均不會(huì)錯(cuò)過截止期。所以對于有隱式截止期的周期性任務(wù)τi的下一邊界bk+1應(yīng)該為當(dāng)前邊界bk之后最早的截止時(shí)間，表達(dá)如式（10）所示。

為了確保每個(gè)邊界公平性，每個(gè)任務(wù)τi必須分配一些整數(shù)的強(qiáng)制性單元，如果在為每個(gè)任務(wù)分配強(qiáng)制執(zhí)行時(shí)間單元后，某些邊界內(nèi)還存在空閑的時(shí)間單元，則這些時(shí)間單元將動(dòng)態(tài)地分配給符合條件的任務(wù)，BF 算法關(guān)鍵是要根據(jù)任務(wù)優(yōu)先級(jí)分配這些可選單元。相關(guān)定義、定理及證明如下文所示。

定義3 BF 調(diào)度算法計(jì)算區(qū)間[bk,bk+1)內(nèi)的最少執(zhí)行時(shí)間，以滿足下個(gè)邊界區(qū)間內(nèi)任務(wù)執(zhí)行公平性，即lagi(bk+1)<1，這個(gè)最少的執(zhí)行時(shí)間被稱作強(qiáng)制執(zhí)行時(shí)間單元（Mandatory Time Units）［9］，分配給任務(wù)τi的強(qiáng)制執(zhí)行時(shí)間定義為：

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

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

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

證明：邊界區(qū)間[bk,bk+1)中，對于m個(gè)處理器內(nèi)核來說，可用來分配的執(zhí)行時(shí)間為m·(bk+1-bk)，但是每個(gè)任務(wù)均需有強(qiáng)制的執(zhí)行時(shí)間，這些任務(wù)在邊界區(qū)間[bk,bk+1)強(qiáng)制執(zhí)行時(shí)間結(jié)束后，m個(gè)處理器內(nèi)核剩余下來的分配時(shí)間是可選分配時(shí)間的值。

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

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

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

顯然對于任意一個(gè)任務(wù)集，確定好強(qiáng)制執(zhí)行時(shí)間后，其未被執(zhí)行的部分不少于0，即，與假設(shè)相矛盾。所以假設(shè)不成立，原命題成立。

2.2 任務(wù)優(yōu)先級(jí)判定

每個(gè)任務(wù)在每個(gè)邊界內(nèi)的執(zhí)行都有其優(yōu)先級(jí)，根據(jù)定義1，如果1 個(gè)正在執(zhí)行的任務(wù)τi在邊界時(shí)刻t被打斷執(zhí)行，則發(fā)現(xiàn)這個(gè)任務(wù)分配誤差將逐漸增大，顯然它的值與任務(wù)利用率Ui成比例關(guān)系，當(dāng)任務(wù)τi有x個(gè)時(shí)間單元未被執(zhí)行，其分配誤差會(huì)變?yōu)椋?/p>

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

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

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

為了保證τi趕上時(shí)刻t的流體調(diào)度偏差，需執(zhí)行y個(gè)時(shí)間單元的任務(wù)，如式（20）所示。

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

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

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

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

2.3 改進(jìn)邊界公平調(diào)度算法原理

在BF 算法中，為了使所有任務(wù)在其截止期前完成，在確定強(qiáng)制執(zhí)行時(shí)間后，由兩個(gè)條件判斷哪些任務(wù)可優(yōu)先獲得可選執(zhí)行時(shí)間。

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

條件2 更高優(yōu)先級(jí)的任務(wù)有資格獲得可選的執(zhí)行時(shí)間單元。

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

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

（1）應(yīng)該樹立科學(xué)的質(zhì)量管理理念，整個(gè)建筑工程中的全部施工者都應(yīng)該對自己應(yīng)盡的責(zé)任和義務(wù)以及施工合同中的內(nèi)容有一個(gè)清晰的了解，并且在施工的過程中，嚴(yán)格按照施工合同中的規(guī)定完成自己的工作。同時(shí)建立完備的施工安全和質(zhì)量管理方案，在加強(qiáng)對建筑工程施工質(zhì)量控制的前提下，通過實(shí)行有效的措施，杜絕施工過程中會(huì)發(fā)生的種種問題，從而確保建筑工程的施工質(zhì)量。

根據(jù)McNaughton［17］提出的環(huán)繞算法，將執(zhí)行時(shí)間分配到各個(gè)內(nèi)核上并生成靜態(tài)調(diào)度表，規(guī)則描述如下：

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

（2）分配給總處理器內(nèi)核的執(zhí)行時(shí)間不超過處理器內(nèi)核在該邊界的可用來處理任務(wù)的總時(shí)間。即：

假設(shè)有可被BF 算法調(diào)度的任務(wù)集τ={τ1,τ2,τ3,τ4,τ5}，如圖2 所示，可以表示1 個(gè)邊界內(nèi)任務(wù)在5 個(gè)內(nèi)核上的執(zhí)行情況。

Fig.2 Task set allocation圖2 任務(wù)集分配情況

圖2 中陰影部分指當(dāng)前任務(wù)在該處理器內(nèi)核上未執(zhí)行完遷移到下1 個(gè)處理器內(nèi)核上執(zhí)行的部分。

3 ER-BF 調(diào)度器設(shè)計(jì)與仿真對比

3.1 ER-BF 調(diào)度器設(shè)計(jì)流程

基于ER-BF 算法原理，設(shè)計(jì)新型邊界公平調(diào)度器程序流程，如圖3 所示。

Fig.3 ER-BF scheduler program flow圖3 ER-BF 調(diào)度器程序流程

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

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

步驟3 通過定義5、定義6 計(jì)算兩個(gè)任務(wù)的緊急因子UFi(t)和恢復(fù)時(shí)間ρi(t)，并比較任務(wù)優(yōu)先級(jí)。

步驟4 根據(jù)條件1 與條件2 確定哪些任務(wù)可獲得可選執(zhí)行時(shí)間，按照每個(gè)任務(wù)在每個(gè)邊界內(nèi)的優(yōu)先級(jí)與執(zhí)行的時(shí)間單元生成任務(wù)調(diào)度表。

3.2 實(shí)驗(yàn)仿真設(shè)計(jì)

本文基于Litmus-RT 平臺(tái)對ER-BF 調(diào)度器進(jìn)行設(shè)計(jì)［18］。Litmus-RT 平臺(tái)是基于Linux 系統(tǒng)為實(shí)時(shí)系統(tǒng)研究提供內(nèi)核級(jí)別抽象的接口實(shí)驗(yàn)平臺(tái)，可用于實(shí)時(shí)可調(diào)度性測試、任務(wù)集生成和實(shí)驗(yàn)數(shù)據(jù)采集。實(shí)驗(yàn)平臺(tái)搭建后，導(dǎo)入實(shí)驗(yàn)任務(wù)參數(shù)，生成任務(wù)集，最后分配任務(wù)生成調(diào)度表，對比ER-BF 調(diào)度器與BF 調(diào)度器執(zhí)行效率。ER-BF 調(diào)度器偽代碼為：

3.3 兩種調(diào)度器對比評估

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

Fig.4 Schedule generated by BF scheduler for task set Γ圖4 任務(wù)集Γ 通過BF 調(diào)度器生成的調(diào)度

Fig.5 Schedule generated by ER-BF scheduler for task set Γ圖5 任務(wù)集Γ 通過ER-BF 調(diào)度器生成的調(diào)度

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

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

Fig.6 Average response time of task set interruption under two schedulers圖6 兩種調(diào)度器下任務(wù)集中斷的平均響應(yīng)時(shí)間

4 結(jié)語

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