異構多處理器系統的混合任務調度算法

張俊祥，馮金富，于心一

(空軍工程大學工程學院，西安 710038)

0 引言

隨著實時應用的日趨復雜，多處理器系統由于其高性能及可靠性，逐漸成為處理這種復雜應用的有效計算手段。而實時多處理器系統的調度算法則成為一個重要的研究課題。文獻［1］指出，對于實時多處理器系統，并不存在最優的任務調度算法，只能采用啟發式調度算法來解決這類問題。

目前，實時多處理器系統的調度算法多是以啟發式搜索算法為基礎，如近似算法、節約算法、集中式任務調度方案等，均是在系統運行過程中，當某個任務實例到達后，按照一定的指標搜索可執行該任務實例的處理器。如近視算法是在傳統的基于啟發式搜索的基礎上，限定了在一次調度中被考慮的任務數，從而降低了算法的復雜度。任務分配的策略是在可滿足該任務截止期的處理器中，選擇一個最早可運行的［2］。而節約算法的任務分配策略是在可滿足該任務截止期的處理器中，選擇一個最遲可運行的［3］。以上算法都是面向同構系統的，且多采用集中式任務調度方案，即系統設置了一個集中任務調度器。以上算法存在兩個缺點:1)算法開銷大;2)如果任務調度器出現故障，整個系統將可能癱瘓［4］。

隨著異構計算的興起，實時異構系統已被廣泛應用于航天控制、核反應堆控制、遙感監測等領域。然而，目前大多數多處理器系統的調度算法都是針對同構系統提出的，對異構系統的考慮比較少。因此，有必要研究實時異構系統的調度算法，來滿足不斷增長的實時異構系統的應用需求。基于以上研究，本文提出了一種針對異構系統的靜態調度算法。該算法采用帶有非周期服務器的搶占式EDF調度算法來確定任務在處理器上的運行時間［5］，以最大剩余計算帶寬為指標來選擇任務分配的處理器。調度的任務可以是硬實時周期任務，也可以是軟實時非周期任務。對于軟實時非周期任務，引入QoS降級策略，提高了任務集的可調度性。

1 基本概念

1.1 任務模型

異構多處理器系統調度的對象多為混合實時任務，任務集中既包括周期任務，也包括非周期任務。任務可以是硬實時的，也可以是軟實時的。對于軟實時任務，根據系統的CPU可用計算帶寬的大小，可運行在不同的QoS等級。下面給出各類任務的模型描述。

定義1 整個系統的任務集T可以用一個二元組描述，即T={Tz，Taz}。其中:Tz為周期任務的集合;Taz為非周期任務的集合。

定義2 任務的計算帶寬需求u=C/P。其中:C為任務的計算時間;P為任務的周期。

定義3 周期任務集合 Tz={τz1，τz2，…，τzn}。其中:τzi∈Tz為一個周期任務，用一個四元組來描述其特性，即 τzi=(Czi，Pzi，Dzi，Pc);Czi為任務的執行時間;Pzi為任務的周期;Dzi為任務的時限;Pc為該任務運行的處理器。任務τzi的計算帶寬需求uzi=Czi/Pzi。

定義 4 非周期任務集合 Taz={τaz1，τaz2，…，τazn}。其中:τazi∈Taz是一個非周期任務，用一個六元組來描述其特性，即 τazi=(Cazi，Pazi，λazi，Dazi，Mazi，Pc);具體地，Cazi為任務的執行時間;Pazi為任務的最小到達時間間隔;λazi為任務的平均到達率;Dazi為任務的時限;Mazi為任務的QoS等級;Pc為該任務運行的處理器;Mazi為τazi的計算帶寬需求的大小，Mazi越大，表示任務的計算帶寬需求越大，反之，則表示任務的計算帶寬需求越小［6－7］。由定義 2 可知，任務 τazi的計算帶寬需求uazi=Cazi/Pazi。

1.2 處理器模型

異構多處理器系統中各處理器的計算性能各不相同，系統分配給各處理器的可用計算帶寬也各不相同。可以用如下的模型來描述異構系統中的處理器集合。

定義5 處理器集合 Ω={Pc1，Pc2，…，Pck}。其中:Pci可用一個二元組表示，即 Pci=(ρi，ui);ρi為處理器Pci的計算性能;ui為分配給處理器Pci的最大可用計算帶寬。分配給所有處理器的最大可用計算帶寬組成一個向量 urmax=［u1max，u2max，…，ukmax］。

定義6 處理器的計算性能表示處理器執行任務的速度。性能高的處理器執行任務的速度越快;反之，則越慢。在一個異構多處理器系統中，將一個處理器的計算性能作為標準，將其值設為1，其他處理器的計算性能表示一個任務在標準處理器上的執行時間與該任務在該處理器上的執行時間的比值。即處理器Pci的計算性能ρi的計算公式為ρi=Cstd/Ci。其中:Cstd為任務在標準處理器上的執行時間。

定義7 在異構多處理器系統中，由于各處理器的計算性能不同，導致同一個任務在不同的處理器上的執行時間不同。定義向量 Cτr=［C(τ，1)，C(τ，2)，…，C(τ，k)］為任務τ在各處理器上的執行時間。其中:C(τ，r)為任務τ在處理器r上的執行時間。由定義6可知，只要知道任務在標準處理器上的執行時間C(τ，std)和處理器r的計算性能ρr，便可計算出任務在處理器r上的執行時間，計算公式為 C(τ，r)=C(τ，std)/ρr。

定義8 任務可調度是指任務的執行實例能滿足其時限。如果一個任務集中的所有任務都是可調度的，則稱該任務集是可調度的。

為分析和計算方便，假設:

1)系統中各任務之間相互獨立;

2)系統中的任務不存在除CPU的計算資源外的其他資源訪問;

3)所有任務的時限和其周期存在相同的比例關系，即對周期任務Dzi=bPzi，對非周期任務Dazi=bPazi，其中，0 ＜b≤1。

2 調度算法

異構多處理器系統的調度算法主要解決兩個問題:1)確定任務在處理器上的執行時序;2)確定任務在何處理器上運行。問題1)通過單處理器的調度算法來解決;問題2)由于不存在最優分配方案，只能通過啟發式搜索算法來解決。

2.1 處理器上的任務調度算法

處理器上的任務調度算法主要負責分配到該處理器上任務的調度。基于單處理器的調度算法已研究得比較成熟，如RMS算法、EDF算法等。在異構多處理器系統中，考慮到系統的開發成本，要求在保證完成系統功能的前提下，使用的處理器數目越少越好。因此，在選擇單處理器的調度算法時，應盡量選擇CPU利用率高的調度算法。在單處理器的調度算法中，EDF算法是最優的動態調度算法，其可調度的上限為100%，使CPU的計算能力能夠被充分利用起來［8］。考慮到系統中的任務為混合實時任務，這里采用帶有非周期服務器的搶占式EDF調度算法來調度分配到處理器上的周期任務和非周期任務［9］。算法如下。

1)對于非周期任務，采用非周期服務器來分配CPU的計算帶寬。非周期服務器是周期地為非周期任務分配CPU計算帶寬的服務器，記為ASi。非周期任務的優先級與非周期服務器的優先級相同。

2)當有非周期任務實例到達時，使它在非周期服務器的容量中運行，包括存儲在周期性任務和其他非周期服務器中的部分。

3)周期任務和非周期服務器的優先級根據EDF算法設置。

4)如果沒有非周期任務等待或執行，比ASi低的周期性任務實例或非周期任務可以利用ASi的容量得到運行，并將相應的部分存儲在此周期性任務或對應的非周期服務器中。

5)如果在一個非周期服務器的服務周期內沒有非周期任務實例到達，則清除非周期服務器的容量，包括已被存儲在周期性任務和其他非周期服務器中的部分，并使ASi重新計時。

6)如果某個任務實例不能在其時限前完成，則將該實例丟棄。

基于以上算法描述，給出任務集的可調度性判據。

設分配到處理器 Pcr上的任務集為 Tzi={τz1，τz2，…，τzni}和 Tazi={τaz1，τaz2，…，τazmi}。在采用帶有非周期服務器的搶占式EDF調度算法時，任務集可調度的充分條件為

證明:考慮系統處于最壞情況下，任務集的調度性。當非周期任務實例以最快速度到達時，系統處于最壞情況，此時，非周期任務可以看成是周期為Pazi、執行時間為Cazi、時限為Dazi的周期任務。如果此時任務集是可調度的，則任務集在任何時候都是可調度的。根據文獻［10］中給出的定理可以得到任務集此時的可調度條件為

由假設 3 可知，Dzi=bPzi，Dazi=bPazi，代入式(2)得

將 uzi=C(τzi，Pcr)/Pzi，uazi=C(τazi，Pcr)/Pazi，代入式(3)即得結論。證畢。

2.2 任務分配算法

任務分配算法主要負責將系統任務集中的任務分配到各處理器。在進行任務分配時，有兩點需要考慮:1)要盡量使各處理器的負載平衡;2)要盡量提高任務集的調度成功率。這里采用啟發式搜索算法，以最大剩余計算帶寬為指標來選擇任務分配的處理器，這樣可以使各處理器的負載盡可能平衡，另外，在進行非周期軟實時任務的分配時，采用QoS降級機制來提高任務集的調度成功率［11］。算法的具體描述如下。

1)初始化任務集T和處理器集Ω。輸入定義3和定義4中給出的周期任務和非周期任務的各參數，輸入定義5中給出的處理器的各參數，其中非周期軟實時任務按最高級QoS服務所需的計算帶寬來初始化其執行時間Cazi的值。定義一個向量ush=［ush1，ush2，…，ushk］用來記錄各處理器的剩余計算帶寬，并用向量urmax來初始化 ush。

2)將周期任務 τzi∈Tz，1≤i≤n，按如下步驟分配到處理器集Ω中的各處理器上。

3)在Ω中選擇一個剩余計算帶寬最大的處理器Pcr，并令 ushr=ushr－ C(τzi，Pcr)/Pzi。若 ushr≥0，則把任務τzi分配到處理器Pcr上。當i＜n時，令i=i+1，并重復步驟3);否則，轉到步驟4)。若ushr＜0，則轉到步驟6)。

4)將非周期任務 τazi∈Taz，1≤i≤m 中的任務按如下步驟分配到處理器集Ω中的各處理器上。

5)在Ω中選擇一個剩余計算帶寬最大的處理器Pcr，并令 ushr=ushr－ C(τazi，Pcr)/Pazi。若 ushr≥0，則把任務τazi分配到處理器Pcr上。當i＜m時，令i=i+1，并重復步驟5);否則，轉到步驟6)。若ushr＜0，則依次降低τazi的QoS等級，并重新計算降級后的ushr，若某QoS等級M∈(Mmin≤M＜Mmax)對應的ushr≥0，則把任務τazi分配到處理器Pcr上。當i＜m時，令i=i+1，并重復步驟5)。若τazi的最低QoS等級Mmin對應的ushr＜0，則轉到步驟6)。

6)退出算法。

下面來分析上述任務分配算法的復雜度。

設系統的任務集中包含n個周期任務和m個非周期任務，每個非周期任務可運行在(Mmin≤M≤Mmax)中的任一QoS等級上，系統有k個處理器資源。在最壞情況下，每個周期任務需要考慮k個處理器的情況，因此，n個周期任務的計算復雜度為O(n×k)。在最壞情況下，每個非周期任務也需要考慮k個處理器的情況，同時，在每個處理器上還需考慮Mmax次QoS降級的情況，因此，m個周期任務的計算復雜度為O(m×k×Mmax)。由此可知，整個任務集的計算復雜度為O(n×k+m×k×Mmax)。從該式可以看出，整個算法的復雜度跟系統任務個數、處理器資源個數、非周期任務的QoS服務級數有關。任務數越多、處理器資源越多、非周期任務的QoS服務等級劃分越細，算法的復雜度越高。

3 仿真實驗

以一組模擬的數據來對算法的運行情況進行仿真實驗，以此來檢驗算法的有效性。仿真實驗主要針對最小處理器數目和任務在各處理器上的分配情況進行。

3.1 最小處理器數目仿真

模擬數據參照文獻［4］中的方法生成。將處理能力最小的處理器作為標準處理器，設其計算性能為1，其他處理器的計算性能滿足［1，1.5］上的均勻分布。設各處理器分配的最大可用計算帶寬服從［0.8，1］上的均勻分布。設周期任務的周期和非周期任務的最小時間間隔(ms)都服從［200，500］上的均勻分布，任務在標準處理器上的執行時間為在區間［0，0.3Pzi］、［0，0.3Pazi］上的均勻分布和［0，0.5Pzi］、［0，0.5Pazi］上的均勻分布兩種情況。設系統中周期任務和非周期任務的比例為1:1，分別模擬 b=0.6，b=0.8，b=1 時最小處理器數目情況，結果如圖1、圖2所示。

圖1 不同時限下最小處理器數和任務數的關系Fig.1 Relation of the minimum number of processors and the number of tasks under various deadline

圖2 不同時限下最小處理器數和任務數的關系Fig.2 Relation of the minimum number of processors and the number of tasks under various deadline

從圖1、圖2可以看出，最小處理器數目隨任務數目的增加而增加。這是因為當任務數目增多時，任務集的所需計算帶寬增加，因而需要增加處理器的數目來提供所需計算帶寬的增加量。在任務數目相同的情況下，最小處理器數目隨各任務執行時間的增加而增加，隨各任務時限的增加而減少。這是因為，當任務的執行時間增加時，相當于式(2)左邊的分子部分變大，導致任務的所需計算帶寬增加。而當任務的時限增加時，相當于式(2)左邊的分母部分變大，導致任務的所需計算帶寬減少。

3.2 任務分配仿真

任務分配仿真主要是對任務分配算法分配給各處理器的任務及各處理器的負載情況進行測試。仿真數據采用3.1節的方法生成。設任務的總數為48個，周期任務和非周期任務各24個，任務的執行時間分別服從［0，0.3Pzi］、［0，0.3Pazi］上的均勻分布，b=1。通過3.1節的仿真計算可知，在此條件下，所需的最小處理器數為7。根據任務分配算法仿真得到的各處理器上的任務分配情況如表1所示，各處理器的負載如圖3所示。

表1 各處理器上的任務分配及最大可用計算帶寬Table 1 The number of tasks and maximum available computation bandwidth of each processor

圖3 各處理器的計算帶寬利用情況Fig.3 Utilization of computation bandwidth of each processor

圖3中的曲線表示分配給各處理器的最大可用計算帶寬，柱條表示任務分配后各處理器的實際負載。從圖3中可以看出，各處理器上的負載比較平衡。綜合兩個仿真的結果，可以看出文中給出的算法是有效的。

4 結論

隨著實時異構系統的應用越來越普遍，實時異構系統的調度問題已成為研究的熱點。本文給出了一種異構多處理器系統的混合實時任務調度算法，該算法采用帶有非周期服務器的搶占式EDF調度算法來調度處理器上任務的運行，由于EDF算法是最優的動態調度算法，用它來調度處理器上任務的運行，可以提高單處理器的利用率，減少處理器的數目。該算法采用啟發式搜索算法來進行任務分配，以最大剩余計算帶寬為搜索指標可以確保各處理器的負載盡量平衡。同時，對軟實時任務采用QoS降級機制，可以提高任務集的整體調度成功率。從算法的復雜度分析可知，軟實時任務的QoS級數不宜過多，否則將導致算法的開銷過大。最后，仿真實驗的結果證明了算法的有效性。

［1］DERTOUZOS M L，MOK A K.Multiprocessor on-line scheduling of hard real-time tasks［J］.IEEE Trans on Software Engineering，1989，15(12):1497-1506.

［2］李建國，陳松橋，魯志輝.實時多處理器系統的動態分批優化調度算法［J］.小型微型計算機系統，2005，26(1):84-89.

［3］QIAO Ying，WANG Hong'an，DAI Guozhong.Developing a new dynamic scheduling algorithm for real-time multiprocessor system［J］.Journal of Software，2002，13(1):51-58.

［4］劉懷，黃建新，沈捷.異構分布式控制系統中實時任務的調度算法［J］.小型微型計算機系統，2005，26(2):230-234.

［5］AUDSLEY N C，BURNS A，RICHARDSON M F.Deadline monotonic scheduling［J］.8th Workshop on Real-time Operating Systems and Software，IEEE，1991，20(5):36-41.

［6］淮曉永，鄒勇，李明樹.一種開放混合實時系統的開放自適應調度算法［J］.軟件學報，2004，15(4):487-496.

［7］陳琳，汪健甄，安萬先，等.多路數據總線任務調度和仿真評價技術［J］.電光與控制，2005，12(2):22-26.

［8］張寧，熊光澤.用EDF調度實時任務和GC［J］.航空學報，2008，29(5):1227-1233.

［9］徐久強，劉輝，朱建，等.一種基于時間片的搶占控制模型［J］.東北大學學報:自然科學版，2009，30(11):1571-1574.

［10］LIU J X，WANG Y J.Matthew cartmell an improved rate monotonic schedulability test algorithm［J］.Journal of Software，2005，16(1):89-100.

［11］朱小敏.異構集群系統中實時任務若干調度問題研究［D］.上海:復旦大學，2009:60-63.