基于多特征動態優先級的網絡實時調度算法

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

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

1 引言

實時系統是通過任務調度的方式，根據響應而對任務進行處理的系統。其應用已涉及計算機網絡系統、互聯網、工業控制及航天飛機系統等多個領域。實時調度作為實時系統的重要作業方式，是研究工作的重點內容。隨著實時系統應用領域的延伸，任務對調度效率及全面性也有了更高的要求。

實時調度是網絡調度中的一個熱點課題，它是相對于傳統的離線調度而提出的。實時調度決策基于即時的信息，也可以包含歷史信息和未來信息。網絡實時調度系統的調度指令與網絡的狀態有關，調度系統根據實時信息做出調度安排，并把調度安排發送給執行單元。

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

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

2 網絡實時調度系統任務模型的建立

2.1 實時調度系統體系結構的構建

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

圖1 基于城市?客戶端的實時調度系統的體系結構

服務器處于系統體系結構的頂層，這種并不復雜的樹狀結構具有更高的處理效率與可靠性。服務器通過調度器與各城市節點進行信息傳輸，完成任務分配及監控。客戶端在系統結構中被對應城市節點Ui分成小組{Cij}，從而完成調度器下派并行任務的運算，其關系與客戶機?服務器模型的運行模式相似。

2.2 任務模型的建立

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

圖2 任務集T 的時間屬性

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

系統的總客戶端資源利用率UC為

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

1) INic

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

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

3 實時調度系統的動態特征參數與測量指標

3.1 調度系統的任務迫切度

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

分析Ei、ti、di的關系，把絕對剩余時間與完成任務Ti的執行時間的比值定義為任務執行率αi，即

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

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

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

3.2 基于任務服務質量保證的松緊度

3.2.1 實時系統的監測服務質量保證

實時系統的監測服務質量保證（SLA,service-level assurance）是與被測實時系統之間進行的約定。根據約定的不同，SLA 主要分為以下3 種情況。

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

2) 城市服務質量保證。對城市監測總數進行約定。

3) 監測客戶端服務質量保證。對監測客戶端總數進行約定。

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

由于任務的分發情況和剩余時間會隨著監測任務的執行不斷發生變化，因此θ也相應變化。當任務分發和執行情況發生變化或者新增刪減任務時，需要重新計算任務的優先級。

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

3.2.2 基于SLA 的松緊度

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

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

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

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

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

1) 城市/監測客戶端服務質量保證

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

2) 城市服務質量保證

其中，INu為城市服務質量保證任務未分配的作業總數，NNu為城市服務質量保證分派任務的作業總數，US 為城市服務質量保證調節系數，任務分發調節因子。f(INu)為關于INu的單增函數，當INu從NNu變化到0 時，松緊度的取值范圍為。

3) 監測客戶端服務質量保證其中，INc為監測客戶端服務質量保證任務未分配的作業數，NNc為監測客戶端服務質量保證分派任務的作業總數，CS 為監測客戶端服務質量保證調節系數，任務分發調節因子。f(INc)為關于INc的單增函數，當INc從NNc變化到0 時，松緊度的取值范圍為。

根據SLA 下優先級策略的設計原則，任務選擇城市服務質量保證優先于城市/客戶端服務質量保證，最后選擇客戶端服務質量保證，并結合工程實際應用數據，選取αuc=20，αu=10，αc=10。

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

3.3 實時任務調度算法的性能測量指標

基于城市?客戶端體系結構的網絡實時調度系統的調度算法應用如表1 所示的性能測量指標。

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

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

4 基于多特征動態優先級的調度策略定義及流程

4.1 顛簸限度

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

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

假設在SLA 的城市/監測客戶端服務質量保證下，在ti時刻，執行任務T1服務質量保證的松緊度最大，為，執行迫切度最小，為βi；等待任務T2服務質量保證的松緊度最小，為0，執行迫切度也最小，為βi。經過ti時間后滿足顛簸門限，T2搶占T1，T1從執行狀態轉變為等待狀態，其等待迫切度將保持不變，服務質量保證的松緊度逐漸增大；T2從等待狀態轉變為執行狀態，其服務質量保證的松緊度保持不變，執行迫切度逐漸增大。到ti時刻，T1執行迫切度從最小值增加到最大值βj，有

表1 實時任務調度算法的性能測量指標

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

4.2 算法流程及步驟

1) 系統實時調度算法的流程

在系統調度過程中，對所有任務的動態優先級都進行實時監控，并進行重新排序，然后將執行任務的優先級與等待任務中優先級最高的任務進行比較，依據結果選用對應策略進行調度，從而使系統的運行性能最佳[12]。

圖4 基于多特征動態優先級的調度策略的流程

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

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

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

策略1積極搶占策略——T2搶占T1。中斷任務T1的執行進程，執行任務T2，T2完成后再繼續執行T1。

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

根據調度流程以及任務搶占策略，調度算法的具體步驟如下。

步驟1服務器向調度器下發任務集T={T1,T2,…,Tn}，初始化任務的優先級。

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

步驟3服務器會實時監控調度器的運行信息。一種情況是，由服務器根據SLA 不同情況，指定某城市的某些客戶端執行任務；另一種情況是，分析城市節點Ui接收的任務數量ni與其對應空閑客戶端節點數INCi的關系。

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

2) 當INCi

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

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

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

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

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

步驟5服務器返回任務分派的客戶端的任務信息和調度器中各城市節點所分配的客戶端數，調度完成。

5 實例分析與仿真實驗

為了驗證MDPSS 算法調度性能的優越性，將本文所提算法結合某“高并發業務性能的監測任務”相關項目實施，研究對監測客戶端的動態調度問題，要求根據任務列表產生任務切片，通過計算任務切片的優先級生成調度隊列，按任務調度監測客戶端完成監測任務。

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

5.1 算法調度成功率

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

圖5 調度成功率隨資源利用率的變化曲線

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

5.2 任務切換次數

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

圖6 3 種算法的切換次數

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

5.3 算法平均響應時間

平均響應時間表征執行任務的速度。采用以下方式對網絡監測任務調度時間進行統計：模擬測試環境主要在局域網中搭建，包括一臺服務器，運行任務分發程序，安裝MySQL 數據庫；一臺測試終端用以運行測試腳本，并記錄測試結果。在正常工作條件下隨機抽取100 ms，將返回數據記錄結果以直方圖的形式進行統計，如圖7 所示。

圖7 網絡檢測任務調度時間直方圖

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

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

圖8 調度平均響應時間隨資源利用率的變化曲線

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

6 結束語

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

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