異構(gòu)多處理器系統(tǒng)的混合任務(wù)調(diào)度算法

張俊祥，馮金富，于心一

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

0 引言

隨著實(shí)時應(yīng)用的日趨復(fù)雜，多處理器系統(tǒng)由于其高性能及可靠性，逐漸成為處理這種復(fù)雜應(yīng)用的有效計算手段。而實(shí)時多處理器系統(tǒng)的調(diào)度算法則成為一個重要的研究課題。文獻(xiàn)［1］指出，對于實(shí)時多處理器系統(tǒng)，并不存在最優(yōu)的任務(wù)調(diào)度算法，只能采用啟發(fā)式調(diào)度算法來解決這類問題。

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

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

1 基本概念

1.1 任務(wù)模型

異構(gòu)多處理器系統(tǒng)調(diào)度的對象多為混合實(shí)時任務(wù)，任務(wù)集中既包括周期任務(wù)，也包括非周期任務(wù)。任務(wù)可以是硬實(shí)時的，也可以是軟實(shí)時的。對于軟實(shí)時任務(wù)，根據(jù)系統(tǒng)的CPU可用計算帶寬的大小，可運(yùn)行在不同的QoS等級。下面給出各類任務(wù)的模型描述。

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

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

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

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

1.2 處理器模型

異構(gòu)多處理器系統(tǒng)中各處理器的計算性能各不相同，系統(tǒng)分配給各處理器的可用計算帶寬也各不相同?？梢杂萌缦碌哪Ｐ蛠砻枋霎悩?gòu)系統(tǒng)中的處理器集合。

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

定義6 處理器的計算性能表示處理器執(zhí)行任務(wù)的速度。性能高的處理器執(zhí)行任務(wù)的速度越快;反之，則越慢。在一個異構(gòu)多處理器系統(tǒng)中，將一個處理器的計算性能作為標(biāo)準(zhǔn)，將其值設(shè)為1，其他處理器的計算性能表示一個任務(wù)在標(biāo)準(zhǔn)處理器上的執(zhí)行時間與該任務(wù)在該處理器上的執(zhí)行時間的比值。即處理器Pci的計算性能ρi的計算公式為ρi=Cstd/Ci。其中:Cstd為任務(wù)在標(biāo)準(zhǔn)處理器上的執(zhí)行時間。

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

定義8 任務(wù)可調(diào)度是指任務(wù)的執(zhí)行實(shí)例能滿足其時限。如果一個任務(wù)集中的所有任務(wù)都是可調(diào)度的，則稱該任務(wù)集是可調(diào)度的。

為分析和計算方便，假設(shè):

1)系統(tǒng)中各任務(wù)之間相互獨(dú)立;

2)系統(tǒng)中的任務(wù)不存在除CPU的計算資源外的其他資源訪問;

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

2 調(diào)度算法

異構(gòu)多處理器系統(tǒng)的調(diào)度算法主要解決兩個問題:1)確定任務(wù)在處理器上的執(zhí)行時序;2)確定任務(wù)在何處理器上運(yùn)行。問題1)通過單處理器的調(diào)度算法來解決;問題2)由于不存在最優(yōu)分配方案，只能通過啟發(fā)式搜索算法來解決。

2.1 處理器上的任務(wù)調(diào)度算法

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

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

2)當(dāng)有非周期任務(wù)實(shí)例到達(dá)時，使它在非周期服務(wù)器的容量中運(yùn)行，包括存儲在周期性任務(wù)和其他非周期服務(wù)器中的部分。

3)周期任務(wù)和非周期服務(wù)器的優(yōu)先級根據(jù)EDF算法設(shè)置。

4)如果沒有非周期任務(wù)等待或執(zhí)行，比ASi低的周期性任務(wù)實(shí)例或非周期任務(wù)可以利用ASi的容量得到運(yùn)行，并將相應(yīng)的部分存儲在此周期性任務(wù)或?qū)?yīng)的非周期服務(wù)器中。

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

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

基于以上算法描述，給出任務(wù)集的可調(diào)度性判據(jù)。

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

證明:考慮系統(tǒng)處于最壞情況下，任務(wù)集的調(diào)度性。當(dāng)非周期任務(wù)實(shí)例以最快速度到達(dá)時，系統(tǒng)處于最壞情況，此時，非周期任務(wù)可以看成是周期為Pazi、執(zhí)行時間為Cazi、時限為Dazi的周期任務(wù)。如果此時任務(wù)集是可調(diào)度的，則任務(wù)集在任何時候都是可調(diào)度的。根據(jù)文獻(xiàn)［10］中給出的定理可以得到任務(wù)集此時的可調(diào)度條件為

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

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

2.2 任務(wù)分配算法

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

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

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

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

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

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

6)退出算法。

下面來分析上述任務(wù)分配算法的復(fù)雜度。

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

3 仿真實(shí)驗(yàn)

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

3.1 最小處理器數(shù)目仿真

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

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

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

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

3.2 任務(wù)分配仿真

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

表1 各處理器上的任務(wù)分配及最大可用計算帶寬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中的曲線表示分配給各處理器的最大可用計算帶寬，柱條表示任務(wù)分配后各處理器的實(shí)際負(fù)載。從圖3中可以看出，各處理器上的負(fù)載比較平衡。綜合兩個仿真的結(jié)果，可以看出文中給出的算法是有效的。

4 結(jié)論

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

［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］李建國，陳松橋，魯志輝.實(shí)時多處理器系統(tǒng)的動態(tài)分批優(yōu)化調(diào)度算法［J］.小型微型計算機(jī)系統(tǒng)，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］劉懷，黃建新，沈捷.異構(gòu)分布式控制系統(tǒng)中實(shí)時任務(wù)的調(diào)度算法［J］.小型微型計算機(jī)系統(tǒng)，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］淮曉永，鄒勇，李明樹.一種開放混合實(shí)時系統(tǒng)的開放自適應(yīng)調(diào)度算法［J］.軟件學(xué)報，2004，15(4):487-496.

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

［8］張寧，熊光澤.用EDF調(diào)度實(shí)時任務(wù)和GC［J］.航空學(xué)報，2008，29(5):1227-1233.

［9］徐久強(qiáng)，劉輝，朱建，等.一種基于時間片的搶占控制模型［J］.東北大學(xué)學(xué)報:自然科學(xué)版，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］朱小敏.異構(gòu)集群系統(tǒng)中實(shí)時任務(wù)若干調(diào)度問題研究［D］.上海:復(fù)旦大學(xué)，2009:60-63.