蘇洵，李艷芳，宗寧，魏巍，李娟，丁瑩

（1.61623 部隊，北京 100036；2.61516 部隊，北京 100074；3.北京航空航天大學機械工程及自動化學院，北京 100088）

1 引言

實時系統(tǒng)是通過任務(wù)調(diào)度的方式，根據(jù)響應(yīng)而對任務(wù)進行處理的系統(tǒng)。其應(yīng)用已涉及計算機網(wǎng)絡(luò)系統(tǒng)、互聯(lián)網(wǎng)、工業(yè)控制及航天飛機系統(tǒng)等多個領(lǐng)域。實時調(diào)度作為實時系統(tǒng)的重要作業(yè)方式，是研究工作的重點內(nèi)容。隨著實時系統(tǒng)應(yīng)用領(lǐng)域的延伸，任務(wù)對調(diào)度效率及全面性也有了更高的要求。

實時調(diào)度是網(wǎng)絡(luò)調(diào)度中的一個熱點課題，它是相對于傳統(tǒng)的離線調(diào)度而提出的。實時調(diào)度決策基于即時的信息，也可以包含歷史信息和未來信息。網(wǎng)絡(luò)實時調(diào)度系統(tǒng)的調(diào)度指令與網(wǎng)絡(luò)的狀態(tài)有關(guān)，調(diào)度系統(tǒng)根據(jù)實時信息做出調(diào)度安排，并把調(diào)度安排發(fā)送給執(zhí)行單元。

國內(nèi)外學者對實時調(diào)度系統(tǒng)的調(diào)度算法相關(guān)問題進行了大量研究。Semghouni 等[1]提出了一種分組最早截止時間優(yōu)先算法，通過使用所有任務(wù)截止時間的加權(quán)均值作為該組的優(yōu)先級，提高系統(tǒng)處理過載情況的能力。Muhuri 等[2]提出了直觀定義平滑隸屬函數(shù)的算法，通過復合立方指數(shù)厄米插值參數(shù)曲線，使現(xiàn)有的基于截止時間和執(zhí)行時間的調(diào)度算法更加現(xiàn)實化與具體化。Nasser 等[3]基于先來先服務(wù)分組調(diào)度機制，提出了動態(tài)多級優(yōu)先級分組調(diào)度方案，將實時數(shù)據(jù)放置于最高優(yōu)先級隊列，非實時數(shù)據(jù)根據(jù)預計時間放置于其他2 個隊列，以此減少端到端時延。為解決傳統(tǒng)調(diào)度方法時間復雜度問題，Benitez 等[4]提出了動態(tài)優(yōu)先級交換調(diào)度策略，把故障和時延這2 個特征參數(shù)作為擾動因素，來控制非線性時延耦合及固有局部故障的出現(xiàn)。洪雪玉等[5]提出了基于截止期和速率的調(diào)度算法，該算法優(yōu)先級取決于重要性和緊急性這2 個特征參數(shù)，提高了調(diào)度的效率和可行性。王永炎等[6]綜合考慮了任務(wù)的截止期和價值這2 個特征參數(shù)，從累積實現(xiàn)價值率、加權(quán)截止期保證率及差分截止期保證率這3個方面提出了一種基于優(yōu)先級表的實時任務(wù)調(diào)度算法。陳輝[7]提出了基于價值密度及緊迫性這2個特征參數(shù)的動態(tài)分配算法。陳佐瓚等[8]提出了多服務(wù)器節(jié)點協(xié)同調(diào)度算法和基于節(jié)點計算能力的調(diào)度策略，保證了調(diào)度器運行的可靠性和子任務(wù)的自適應(yīng)并行能力。

以上研究或是針對調(diào)度過程某一特征參數(shù)展開研究，或是將任務(wù)單一的時間屬性和價值作為多特征研究，并沒有針對網(wǎng)絡(luò)實時調(diào)度問題進行全面深入的討論。對此，本文提出了一種基于多特征動態(tài)優(yōu)先級的網(wǎng)絡(luò)實時調(diào)度算法。通過構(gòu)建實時調(diào)度系統(tǒng)結(jié)構(gòu)，建立調(diào)度系統(tǒng)的任務(wù)模型。根據(jù)任務(wù)的截止期、執(zhí)行時間以及間隔時間等時間屬性，提出了任務(wù)的迫切度；分析不同任務(wù)在實時調(diào)度系統(tǒng)中功能與重要度的相異程度，提出了基于服務(wù)質(zhì)量保證的任務(wù)松緊度。通過對任務(wù)迫切度與松緊度進行動態(tài)調(diào)節(jié)，給出了防止任務(wù)頻繁切換的顛簸限度，在減少任務(wù)切換次數(shù)的同時，保證了等待任務(wù)的搶占成功率，從而提高了全部任務(wù)執(zhí)行的成功率與客戶端執(zhí)行的利用率。

2 網(wǎng)絡(luò)實時調(diào)度系統(tǒng)任務(wù)模型的建立

2.1 實時調(diào)度系統(tǒng)體系結(jié)構(gòu)的構(gòu)建

基于城市?客戶端體系結(jié)構(gòu)構(gòu)建的實時調(diào)度系統(tǒng)模型是一個類似樹狀的層次結(jié)構(gòu)。以服務(wù)器表示系統(tǒng)控制中心，調(diào)度器處于服務(wù)器與城市節(jié)點之間，負責各任務(wù)的分配調(diào)度。調(diào)度器對各城市節(jié)點及其下屬客戶端的作業(yè)進行多城市節(jié)點協(xié)同調(diào)度的方案，客戶端Cij由其所屬城市節(jié)點Ui直接管理，每個城市節(jié)點管理多個客戶端，同時客戶端的任務(wù)執(zhí)行狀態(tài)信息實時反饋到調(diào)度器，從而調(diào)整任務(wù)的動態(tài)優(yōu)先級及排序，保證了服務(wù)器運行的可靠性。圖1 為基于城市?客戶端的實時調(diào)度系統(tǒng)的體系結(jié)構(gòu)。

圖1 基于城市?客戶端的實時調(diào)度系統(tǒng)的體系結(jié)構(gòu)

服務(wù)器處于系統(tǒng)體系結(jié)構(gòu)的頂層，這種并不復雜的樹狀結(jié)構(gòu)具有更高的處理效率與可靠性。服務(wù)器通過調(diào)度器與各城市節(jié)點進行信息傳輸，完成任務(wù)分配及監(jiān)控?？蛻舳嗽谙到y(tǒng)結(jié)構(gòu)中被對應(yīng)城市節(jié)點Ui分成小組{Cij}，從而完成調(diào)度器下派并行任務(wù)的運算，其關(guān)系與客戶機?服務(wù)器模型的運行模式相似。

2.2 任務(wù)模型的建立

在實時調(diào)度系統(tǒng)中被調(diào)度的任務(wù)被稱為實時任務(wù)，能被系統(tǒng)調(diào)度與執(zhí)行的任務(wù)單元稱為作業(yè)[9]。用T={τ1,τ2,…,τn}表示一列分派的任務(wù)集，τi={T1,T2,…,Tn}表示T的第i個子任務(wù)集，任務(wù)集中每個任務(wù)Ti定義為Ti={Ei,d i,t i,p i,βi,TDi}，并定義Tij為任務(wù)Ti的第j個作業(yè)。任務(wù)模型中，Ei是di是任任務(wù)務(wù)Ti理Ti論的執(zhí)絕行對時截間止，期b，i是ti是任當務(wù)前Ti任 的務(wù)開已始執(zhí)時行間的，時間，pi是2 個作業(yè)執(zhí)行的最小間隔時間，βi是任務(wù)Ti的執(zhí)行迫切度，TDi是任務(wù)Ti服務(wù)質(zhì)量保證的松緊度。圖2 為任務(wù)集T的時間屬性。

圖2 任務(wù)集T 的時間屬性

若一個任務(wù)集T中全部作業(yè)都能確保在絕對截止期前執(zhí)行完畢，則稱T可調(diào)度[9]。實時調(diào)度系統(tǒng)體系平臺包含個客戶端，城市節(jié)點Ui下屬的客戶端用Cij(1≤i≤m,1≤j≤k i,j為Ui下屬第j個客戶端) 表示。用T(Cij)表示任務(wù)集T中分配給客戶端Cij的任務(wù)子集，此處作業(yè)包含2 個部分：分配到此客戶端的任務(wù)Ti的所有作業(yè)和分配到此客戶端的任務(wù)Ti的部分作業(yè)?？蛻舳薈ij的執(zhí)行利用率uCij與客戶端數(shù)量NC作為反饋指標，來影響調(diào)度器對任務(wù)的分派，如式(1)所示。

系統(tǒng)的總客戶端資源利用率UC為

一般地，每個城市節(jié)點接受服務(wù)器分派下來的任務(wù)數(shù)量z遠小于任務(wù)總數(shù)n。例如某個任務(wù)集有10 000 個任務(wù)，即n=10 000，若有20 個城市節(jié)點，則每個城市節(jié)點平均分配了500 個任務(wù)，即z=500。此時，城市節(jié)點調(diào)度有3 種情況，其中INic表示Ui下屬空閑客戶端數(shù)量。

1) INic

2) INic=z。城市節(jié)點下屬的空閑客戶端數(shù)量恰好滿足全部分派的任務(wù)投入運行。這種理想狀態(tài)下，城市節(jié)點恰好將全部任務(wù)分派給每一個空閑客戶端執(zhí)行操作。

3) INic>z。能夠滿足所有分派的任務(wù)運行之外還有空余，資源處于充足狀態(tài)，理論上要把任務(wù)盡可能分配到處理能力強的客戶端運行。

3 實時調(diào)度系統(tǒng)的動態(tài)特征參數(shù)與測量指標

3.1 調(diào)度系統(tǒng)的任務(wù)迫切度

客戶端經(jīng)過需求界限函數(shù)（DBF,demand bound function）算法[10]可以實現(xiàn)合理的調(diào)度，傳統(tǒng)的基于任務(wù)時間屬性的調(diào)度策略一般僅依據(jù)任務(wù)的截止期或間隔時間來評判任務(wù)執(zhí)行的緊迫性[11-12]，而這種單一的時間屬性決策未能全面地表現(xiàn)出實時系統(tǒng)的迫切性。本文綜合考慮實時調(diào)度系統(tǒng)中任務(wù)的截止期、任務(wù)的剩余執(zhí)行時間及間隔時間等時間屬性，提出任務(wù)迫切度來度量評價任務(wù)執(zhí)行的迫切性，較全面地考慮了任務(wù)的時間約束，能更準確地對任務(wù)執(zhí)行的迫切程度進行度量。

分析Ei、ti、di的關(guān)系，把絕對剩余時間與完成任務(wù)Ti的執(zhí)行時間的比值定義為任務(wù)執(zhí)行率αi，即

其中，t為調(diào)度系統(tǒng)的時間。在t與ti隨著執(zhí)行時間的增加而增加的過程中，αi在不斷地變大，即執(zhí)行任務(wù)的任務(wù)執(zhí)行率要隨著距離截止期越近而變得越大，從而提高其在截止期前完成任務(wù)的機會。

為了降低執(zhí)行任務(wù)Ti因沒有足夠的執(zhí)行時間而夭折的風險，根據(jù)任務(wù)的執(zhí)行率，本文提出了執(zhí)行任務(wù)迫切度β，它表示為確保任務(wù)在任務(wù)截止期前完成，要求執(zhí)行此任務(wù)的迫切程度。任務(wù)Ti的迫切度βi為

其中，p為調(diào)節(jié)任務(wù)執(zhí)行利用率αi對迫切度βi的作用程度的參數(shù)，定義為任務(wù)任意相鄰2 個作業(yè)的間隔時間與任務(wù)作業(yè)最小間隔時間的比值，顯然p≥ 1，能夠得出。執(zhí)行任務(wù)Ti的迫切度會隨執(zhí)行時間的增加而增加，從而保證了正在執(zhí)行的任務(wù)保護自己的執(zhí)行狀態(tài)而不被其他任務(wù)搶占。

3.2 基于任務(wù)服務(wù)質(zhì)量保證的松緊度

3.2.1 實時系統(tǒng)的監(jiān)測服務(wù)質(zhì)量保證

實時系統(tǒng)的監(jiān)測服務(wù)質(zhì)量保證（SLA,service-level assurance）是與被測實時系統(tǒng)之間進行的約定。根據(jù)約定的不同，SLA 主要分為以下3 種情況。

1) 城市/監(jiān)測客戶端服務(wù)質(zhì)量保證。對每個城市監(jiān)測客戶端數(shù)以及任務(wù)監(jiān)測客戶端組中的城市數(shù)均進行約定，即約定了城市客戶端乘積數(shù)。

2) 城市服務(wù)質(zhì)量保證。對城市監(jiān)測總數(shù)進行約定。

3) 監(jiān)測客戶端服務(wù)質(zhì)量保證。對監(jiān)測客戶端總數(shù)進行約定。

在SLA 下，初始優(yōu)先級由調(diào)度器中的任務(wù)屬性與參數(shù)決定；除此之外，為了均衡任務(wù)分發(fā)過程，定義了任務(wù)分發(fā)調(diào)節(jié)因子θ，確保優(yōu)先調(diào)度完成情況較差的任務(wù)。任務(wù)分發(fā)調(diào)節(jié)因子主要與作業(yè)的完成情況相關(guān)，由任務(wù)執(zhí)行的剩余城市數(shù)或客戶端數(shù)決定。SLA 下的優(yōu)先級策略的設(shè)計應(yīng)該遵循以下原則。1) 為了保證監(jiān)測數(shù)據(jù)全面客觀，基于監(jiān)測城市的作業(yè)優(yōu)先級應(yīng)盡量高于基于監(jiān)測客戶端的作業(yè)；2) 為了保證每個監(jiān)測任務(wù)都有機會被執(zhí)行，應(yīng)盡量照顧作業(yè)分發(fā)情況較差的作業(yè)。

由于任務(wù)的分發(fā)情況和剩余時間會隨著監(jiān)測任務(wù)的執(zhí)行不斷發(fā)生變化，因此θ也相應(yīng)變化。當任務(wù)分發(fā)和執(zhí)行情況發(fā)生變化或者新增刪減任務(wù)時，需要重新計算任務(wù)的優(yōu)先級。

實時調(diào)度系統(tǒng)在滿足任務(wù)的時間約束條件與SLA 時，下一層的客戶端節(jié)點由確定的上一層城市節(jié)點管理，避免因動態(tài)性太強所引起的節(jié)點間的低效率傳輸和搜索，使系統(tǒng)更加適合于實時調(diào)度系統(tǒng)這樣的主?從系統(tǒng)的應(yīng)用。這樣，實時調(diào)度系統(tǒng)體系結(jié)構(gòu)的服務(wù)質(zhì)量保證受城市數(shù)量以及其下屬客戶端數(shù)量的共同作用影響。

3.2.2 基于SLA 的松緊度

由于調(diào)度器下發(fā)的不同任務(wù)在系統(tǒng)中功能有所差異，相同的任務(wù)在執(zhí)行或等待狀態(tài)中對系統(tǒng)的重要程度也會變化，因此定義任務(wù)服務(wù)質(zhì)量保證的松緊量來量化任務(wù)Ti對實時調(diào)度系統(tǒng)不同情況的重要性。顯然，松緊量并非在任務(wù)完成那一時刻才產(chǎn)生，而是伴隨任務(wù)執(zhí)行過程而如彈力一般漸漸增大的。

當某客戶端的實時任務(wù)Ti開始執(zhí)行ti時間后，其積累的服務(wù)質(zhì)量松緊量記為TQi，即松緊量是隨時間變化表示任務(wù)分發(fā)情況有關(guān)的函數(shù)，松緊量的計算式為

任務(wù)Ti預期的松緊量與其相應(yīng)執(zhí)行時間的比為平均松緊量，即。可以看出，只和Ti自身屬性相關(guān)，而與Ti執(zhí)行過程無關(guān)。不過反映的是一段執(zhí)行時間ti內(nèi)任務(wù)的平均松緊度，不能反映Ti的即時松緊質(zhì)量，因此定義服務(wù)質(zhì)量保證的松緊度TDi，TDi反映任務(wù)Ti松緊量的變化速度，可表示為

由式(5)和式(6)，顯然有式(7)成立。

根據(jù)SLA 約定的分類不同，松緊度計算式也不完全相同，而由于每個任務(wù)只能選擇一種SLA，因此任務(wù)松緊度有以下3 種情況。

1) 城市/監(jiān)測客戶端服務(wù)質(zhì)量保證

其中，INuc為城市/監(jiān)測客戶端服務(wù)質(zhì)量保證任務(wù)未分配的作業(yè)總數(shù)，NNuc為城市/監(jiān)測客戶端服務(wù)質(zhì)量保證分派任務(wù)的作業(yè)總數(shù)，UCS 為城市/監(jiān)測客戶端服務(wù)質(zhì)量保證調(diào)節(jié)系數(shù)，任務(wù)分發(fā)調(diào)節(jié)因子。f(INuc)為關(guān)于INuc的單增函數(shù)，當INuc從NNuc變化到0 時，松緊度的取值范圍為。

2) 城市服務(wù)質(zhì)量保證

其中，INu為城市服務(wù)質(zhì)量保證任務(wù)未分配的作業(yè)總數(shù)，NNu為城市服務(wù)質(zhì)量保證分派任務(wù)的作業(yè)總數(shù)，US 為城市服務(wù)質(zhì)量保證調(diào)節(jié)系數(shù)，任務(wù)分發(fā)調(diào)節(jié)因子。f(INu)為關(guān)于INu的單增函數(shù)，當INu從NNu變化到0 時，松緊度的取值范圍為。

3) 監(jiān)測客戶端服務(wù)質(zhì)量保證其中，INc為監(jiān)測客戶端服務(wù)質(zhì)量保證任務(wù)未分配的作業(yè)數(shù)，NNc為監(jiān)測客戶端服務(wù)質(zhì)量保證分派任務(wù)的作業(yè)總數(shù)，CS 為監(jiān)測客戶端服務(wù)質(zhì)量保證調(diào)節(jié)系數(shù)，任務(wù)分發(fā)調(diào)節(jié)因子。f(INc)為關(guān)于INc的單增函數(shù)，當INc從NNc變化到0 時，松緊度的取值范圍為。

根據(jù)SLA 下優(yōu)先級策略的設(shè)計原則，任務(wù)選擇城市服務(wù)質(zhì)量保證優(yōu)先于城市/客戶端服務(wù)質(zhì)量保證，最后選擇客戶端服務(wù)質(zhì)量保證，并結(jié)合工程實際應(yīng)用數(shù)據(jù)，選取αuc=20，αu=10，αc=10。

由基于SLA 的任務(wù)的松緊度可知，任務(wù)只在完全完成后才會給實時調(diào)度系統(tǒng)產(chǎn)生任務(wù)的松緊量“放松”，否則，其松緊度的“彈力”將一直存在而無法放松，若在絕對截止期前尚未釋放彈力，則表示任務(wù)未能成功執(zhí)行；而若夭折一個已產(chǎn)生松緊量的任務(wù)，那么不僅不能為系統(tǒng)釋放“彈力”，還用掉了任務(wù)執(zhí)行時消耗的系統(tǒng)資源。對于本文的實時調(diào)度系統(tǒng)，為了保護等待任務(wù)在絕對截止期前能夠得到“放松”，根據(jù)SLA 選擇原則及計量關(guān)系，在任務(wù)分派過程中，未分配的作業(yè)在減小，即執(zhí)行任務(wù)的松緊度在降低，這增加了等待任務(wù)搶占執(zhí)行位置的機會，從而為等待任務(wù)的作業(yè)分配空閑的客戶端，并提高其動態(tài)優(yōu)先級，在一定程度上減少等待任務(wù)Ti夭折的可能性，最終提高了實時調(diào)度系統(tǒng)的執(zhí)行成功率。

3.3 實時任務(wù)調(diào)度算法的性能測量指標

基于城市?客戶端體系結(jié)構(gòu)的網(wǎng)絡(luò)實時調(diào)度系統(tǒng)的調(diào)度算法應(yīng)用如表1 所示的性能測量指標。

以上實時任務(wù)調(diào)度算法的性能測量指標中，調(diào)度成功率是任務(wù)集全部完成的決定性評價標準。在執(zhí)行任務(wù)時，需要設(shè)定有關(guān)迫切度βi和松緊度TD(ti)的相關(guān)參數(shù)，圖3 為迫切度和松緊度對資源利用率的影響。

圖3 迫切度和松緊度對資源利用率的影響

4 基于多特征動態(tài)優(yōu)先級的調(diào)度策略定義及流程

4.1 顛簸限度

在實時調(diào)度系統(tǒng)中，多個任務(wù)優(yōu)先級交替上升而導致任務(wù)相互交叉搶占執(zhí)行，而每次搶占都發(fā)生一次任務(wù)切換，這種頻繁切換現(xiàn)象稱為系統(tǒng)顛簸現(xiàn)象[13]。顛簸現(xiàn)象會導致系統(tǒng)的額外開銷大大增加，消耗系統(tǒng)資源。為此本文提出了顛簸限度來提高任務(wù)的搶占門限，避免優(yōu)先級差別很小的任務(wù)之間的過度搶占。

在任務(wù)集T中，2 個任務(wù)T1與T2之間設(shè)定一個顛簸限度ω，其中T1是正在執(zhí)行的任務(wù)，T2是等待任務(wù)，它們在t時刻的動態(tài)優(yōu)先級分別是DP(T1)和DP(T2)。只有在滿足式(11)的條件下，才能夠讓T2搶占T1，從而避免頻繁搶占。

假設(shè)在SLA 的城市/監(jiān)測客戶端服務(wù)質(zhì)量保證下，在ti時刻，執(zhí)行任務(wù)T1服務(wù)質(zhì)量保證的松緊度最大，為，執(zhí)行迫切度最小，為βi；等待任務(wù)T2服務(wù)質(zhì)量保證的松緊度最小，為0，執(zhí)行迫切度也最小，為βi。經(jīng)過ti時間后滿足顛簸門限，T2搶占T1，T1從執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)榈却隣顟B(tài)，其等待迫切度將保持不變，服務(wù)質(zhì)量保證的松緊度逐漸增大；T2從等待狀態(tài)轉(zhuǎn)變?yōu)閳?zhí)行狀態(tài)，其服務(wù)質(zhì)量保證的松緊度保持不變，執(zhí)行迫切度逐漸增大。到ti時刻，T1執(zhí)行迫切度從最小值增加到最大值βj，有

表1 實時任務(wù)調(diào)度算法的性能測量指標

故對于任意任務(wù)集T，一定存在某個ω，使調(diào)度系統(tǒng)避免出現(xiàn)顛簸現(xiàn)象。如初始優(yōu)先級較高的任務(wù)A 和優(yōu)先級稍低一些的任務(wù)B 處于等待任務(wù)狀態(tài)，某一時刻任務(wù)A 進入執(zhí)行狀態(tài)，若ω=3，那么只有當DP(Ti) >3DP(Tj)時，任務(wù)B 才能搶占成功，進入執(zhí)行狀態(tài)。

4.2 算法流程及步驟

1) 系統(tǒng)實時調(diào)度算法的流程

在系統(tǒng)調(diào)度過程中，對所有任務(wù)的動態(tài)優(yōu)先級都進行實時監(jiān)控，并進行重新排序，然后將執(zhí)行任務(wù)的優(yōu)先級與等待任務(wù)中優(yōu)先級最高的任務(wù)進行比較，依據(jù)結(jié)果選用對應(yīng)策略進行調(diào)度，從而使系統(tǒng)的運行性能最佳[12]。

圖4 基于多特征動態(tài)優(yōu)先級的調(diào)度策略的流程

基于多特征動態(tài)優(yōu)先級的調(diào)度策略（MDPSS,multi-feature dynamic priority scheduling strategy）的流程如圖4 所示。當實時系統(tǒng)開始運行時，服務(wù)器將任務(wù)集下發(fā)到調(diào)度器繼而分派到城市節(jié)點，此時初始優(yōu)先級最高的任務(wù)率先搶占城市客戶端，進入任務(wù)執(zhí)行狀態(tài)，而所有任務(wù)的優(yōu)先級都伴隨執(zhí)行任務(wù)的進行而動態(tài)變化。對客戶端中的執(zhí)行任務(wù)，其執(zhí)行迫切度不變，但是其服務(wù)質(zhì)量保證的松緊度隨著已執(zhí)行時間的增加而不斷變大，“彈力”的張緊可以避免被非執(zhí)行任務(wù)過早搶占而發(fā)生顛簸現(xiàn)象的產(chǎn)生；對調(diào)度器中的等待任務(wù)與活動任務(wù)，其松緊度不變，但是其執(zhí)行迫切度隨著其等待時間的增加而變大，“等待”的迫切程度增大了它搶占任務(wù)執(zhí)行權(quán)的機會。

2) 實時調(diào)度算法的搶占策略及步驟

根據(jù)任務(wù)屬性以及調(diào)度流程，為任務(wù)之間的搶占制定一些搶占策略。在實時調(diào)度系統(tǒng)中，當任務(wù)集T中處于等待狀態(tài)的T2滿足搶占T1的條件，且沒有其他影響的情況下，無論T2是否搶占T1，最終T1與T2都滿足截止期，可以完成執(zhí)行任務(wù)，此時有以下2 個搶占策略可以選擇。

策略1積極搶占策略——T2搶占T1。中斷任務(wù)T1的執(zhí)行進程，執(zhí)行任務(wù)T2，T2完成后再繼續(xù)執(zhí)行T1。

策略2消極搶占策略——T2不搶占T1。T1全部完成后T2才開始執(zhí)行，此時設(shè)T2優(yōu)先級為max(DP′(T1),DP′(T2))，DP′(T1)與DP′(T2)是任務(wù)在切換時刻各自的動態(tài)優(yōu)先級。

根據(jù)調(diào)度流程以及任務(wù)搶占策略，調(diào)度算法的具體步驟如下。

步驟1服務(wù)器向調(diào)度器下發(fā)任務(wù)集T={T1,T2,…,Tn}，初始化任務(wù)的優(yōu)先級。

步驟2將任務(wù)在調(diào)度器中按初始動態(tài)優(yōu)先級{DP0(Ti)}進行排序，城市節(jié)點Ui把接收的作業(yè)集{Tij}按調(diào)度策略分派到下屬的客戶端Cij。

步驟3服務(wù)器會實時監(jiān)控調(diào)度器的運行信息。一種情況是，由服務(wù)器根據(jù)SLA 不同情況，指定某城市的某些客戶端執(zhí)行任務(wù)；另一種情況是，分析城市節(jié)點Ui接收的任務(wù)數(shù)量ni與其對應(yīng)空閑客戶端節(jié)點數(shù)INCi的關(guān)系。

1) 當INCi≥m時，說明資源比較充裕，此時任務(wù)分配到負載最小的城市節(jié)點，即選擇下屬空閑客戶端最多的城市節(jié)點進行下一步的調(diào)度。

2) 當INCi

步驟4在客戶端Cij的某時刻，動態(tài)優(yōu)先級最高的任務(wù)Tk處于執(zhí)行狀態(tài)，且已執(zhí)行tk個單位時間，其動態(tài)優(yōu)先級記DP(Tk)；在等待狀態(tài)的任務(wù)中，Tl為動態(tài)優(yōu)先級最高任務(wù)，且已執(zhí)行tl個單位時間，其動態(tài)優(yōu)先級記記DP(Tl)。

1) 若DP(Tl)<ωDP(Tk)，則Tl沒有滿足搶占Tk條件，Tk與Tl均保持原狀態(tài)。

2) 若DP(Tl)≥ωDP(Tk)，則Tl滿足搶占Tk條件，判定進入積極搶占策略（Tl搶占Tk）還是消極搶占策略（Tl不搶占Tk）。

3) 若Tl在Tk完成后再開始執(zhí)行，Tl依舊可保證其截止期；而如果Tl搶占Tk，T k在Tl完成后再繼續(xù)執(zhí)行，T k也能確保其截止期，則按積極搶占策略或消極搶占策略執(zhí)行。

4) 如果Tl不搶占Tk就不能保證截止期，則Tl必須執(zhí)行搶占。在這種情況下，若Tk在Tl完成后繼續(xù)執(zhí)行仍能滿足截止期，則執(zhí)行積極搶占策略；若Tl搶占Tk后，Tk不能滿足其截止期而夭折，則將Tk未完成部分自動分配到下一個周期或其他空閑客戶端。

步驟5服務(wù)器返回任務(wù)分派的客戶端的任務(wù)信息和調(diào)度器中各城市節(jié)點所分配的客戶端數(shù)，調(diào)度完成。

5 實例分析與仿真實驗

為了驗證MDPSS 算法調(diào)度性能的優(yōu)越性，將本文所提算法結(jié)合某“高并發(fā)業(yè)務(wù)性能的監(jiān)測任務(wù)”相關(guān)項目實施，研究對監(jiān)測客戶端的動態(tài)調(diào)度問題，要求根據(jù)任務(wù)列表產(chǎn)生任務(wù)切片，通過計算任務(wù)切片的優(yōu)先級生成調(diào)度隊列，按任務(wù)調(diào)度監(jiān)測客戶端完成監(jiān)測任務(wù)。

實驗采用MATLAB 軟件進行仿真。在仿真中模擬局域網(wǎng)中的運行環(huán)境，調(diào)度10 000 個分布在各地的模擬監(jiān)測客戶端，實驗中的參數(shù)設(shè)定為βi=2，TD(ti)=15，與之相比較的盡力交付（BE,best effort）算法中V=1，最早截止時間優(yōu)先（EDF,earliest deadline first）算法中Gr=0.4[14]。從調(diào)度成功率、任務(wù)切換次數(shù)、平均響應(yīng)時間3 個方面進行仿真結(jié)果比較。硬件測試平臺的配置為Intel Core i5 4590 處理器、DDR3 1600 8 GB內(nèi)存、HD4600 顯卡、Windows severe 2008 操作系統(tǒng)。

5.1 算法調(diào)度成功率

調(diào)度成功率是衡量調(diào)度算法的一個重要指標，目前流行的3 種算法均會優(yōu)先考慮成功率的問題，再去優(yōu)化其他性能指標。為驗證算法的優(yōu)越性，本節(jié)分別依據(jù)3種算法在客戶端資源利用率變化時抽取樣本進行測試，仿真出調(diào)度成功率的變化曲線，如圖5 所示。

圖5 調(diào)度成功率隨資源利用率的變化曲線

由圖5 可知，當資源豐富時，即客戶端資源利用率在不足1 的條件下，3 種算法的調(diào)度成功率幾乎都能達到100%；而在資源不足的條件下，隨著任務(wù)超載量的增加，調(diào)度成功率越來越低，此時MDPSS 算法的優(yōu)越性逐漸體現(xiàn)出來。

5.2 任務(wù)切換次數(shù)

在實施搶占策略的實時調(diào)度系統(tǒng)中，當滿足搶占條件時，正在執(zhí)行的任務(wù)會暫時中斷而將資源讓給優(yōu)先級更高的任務(wù)。在空閑客戶端數(shù)量有限的條件下，任務(wù)的相互搶占過程會引起資源的額外開銷，從而對系統(tǒng)性能造成嚴重的影響。在任務(wù)調(diào)度過程中，隨著客戶端資源利用率的變化，3 種算法的切換次數(shù)如圖6 所示。

圖6 3 種算法的切換次數(shù)

由圖6 可知，3 種算法在資源充足時，隨著客戶端資源利用率的增加，切換次數(shù)也在增加。當客戶端資源利用率為1 時，切換次數(shù)達到最大值；當客戶端資源利用率大于1 時，隨著資源的超載，3種算法均會更加顧及資源在其他方面的需求，隨著超載量的增加而減少了切換次數(shù)。與BE 算法和EDF 算法相比，MDPSS 算法由于引入了顛簸限度，因此切換次數(shù)遠遠小于這2 種算法。

5.3 算法平均響應(yīng)時間

平均響應(yīng)時間表征執(zhí)行任務(wù)的速度。采用以下方式對網(wǎng)絡(luò)監(jiān)測任務(wù)調(diào)度時間進行統(tǒng)計：模擬測試環(huán)境主要在局域網(wǎng)中搭建，包括一臺服務(wù)器，運行任務(wù)分發(fā)程序，安裝MySQL 數(shù)據(jù)庫；一臺測試終端用以運行測試腳本，并記錄測試結(jié)果。在正常工作條件下隨機抽取100 ms，將返回數(shù)據(jù)記錄結(jié)果以直方圖的形式進行統(tǒng)計，如圖7 所示。

圖7 網(wǎng)絡(luò)檢測任務(wù)調(diào)度時間直方圖

通過對測試數(shù)據(jù)進行分析可以看出，在局域網(wǎng)環(huán)境中，在網(wǎng)絡(luò)時延分組丟失忽略不計的情況下，平均每次任務(wù)調(diào)度時間可控制在7 ms 以內(nèi)，而絕大多數(shù)任務(wù)的調(diào)度時間集中在3～5 ms，因此每小時可調(diào)度任務(wù)片可達4×109～7×109個，高效地完成了任務(wù)的調(diào)度。

為驗證算法在響應(yīng)時間上的優(yōu)越性，需要在客戶端資源利用率變化時，尤其是在超載的情況下，比較3 種算法的調(diào)度平均響應(yīng)時間，分別依據(jù)3 種算法抽取樣本，擬合出客戶端資源利用率在0.5～1.8 上變化時的調(diào)度平均響應(yīng)時間曲線，如圖8 所示。

圖8 調(diào)度平均響應(yīng)時間隨資源利用率的變化曲線

由圖8 可以看出，隨著客戶端資源利用率的增加，調(diào)度平均響應(yīng)時間也相應(yīng)地逐漸增加，在資源豐富的條件下，即客戶端資源利用率小于1 時，3種算法的平均響應(yīng)時間相差不大；隨著過載量的增加，MDPSS 算法的優(yōu)勢逐漸顯現(xiàn)出來，平均響應(yīng)時間與BE 算法相差不大，且優(yōu)于EDF 算法。

6 結(jié)束語

本文通過構(gòu)建實時調(diào)度系統(tǒng)體系結(jié)構(gòu)，建立起任務(wù)模型，研究了實時調(diào)度系統(tǒng)中任務(wù)關(guān)于時間屬性的迫切度與任務(wù)服務(wù)質(zhì)量保證的松緊度的特性及其關(guān)系。根據(jù)任務(wù)的3 個時間屬性，改進了一種DBF 算法，提出了任務(wù)的迫切度；通過分析不同任務(wù)在城市?客戶端系統(tǒng)中功能與重要度的相異程度，定義了任務(wù)的服務(wù)質(zhì)量保證的松緊度。此外，綜合這2 個方面的特征，提出了顛簸限度來提高任務(wù)的搶占門限，由此提出了MDPSS 算法。

仿真實驗結(jié)果表明，與BE 算法和EDF 算法相比，MDPSS 算法不僅能根據(jù)任務(wù)動態(tài)優(yōu)先級有效而安全地進行任務(wù)切換，在減少任務(wù)切換次數(shù)的同時，也保證了等待任務(wù)的搶占成功率，從而提高了全部任務(wù)的調(diào)度成功率與客戶端資源利用率，縮短了平均響應(yīng)時間，具有明顯的優(yōu)越性。