張海濤，張 通，張宇輝，管銀鳳，張鳳登

(上海理工大學 光電信息與計算機工程學院，上海 200093)

隨著計算機技術(shù)的進步和發(fā)展，越來越多的復雜系統(tǒng)依賴于計算機控制，實時系統(tǒng)在當今社會中扮演著至關(guān)重要的角色[1]。與此同時，人們對實時系統(tǒng)的功能和性能有了更高的要求，實時系統(tǒng)逐漸被構(gòu)建在多處理器平臺之上[2]。

多處理器實時調(diào)度算法主要解決兩個問題：任務(wù)劃分問題和優(yōu)先級分配問題[3]。其中，劃分調(diào)度中關(guān)鍵的就是任務(wù)劃分算法。這個劃分問題類似于經(jīng)典裝箱問題。使用P-RM調(diào)度算法時，文獻[4]研究了首次適應算法(First-Fit，F(xiàn)F)、最佳適應算法(Best-Fit，BF)和最壞適應算法(Worst-Fit，WF)等經(jīng)典的裝箱算法的性能，并得到了可調(diào)度的利用率上限條件。文獻[5]提出了在劃分EDF(Earliest Deadline First)和劃分固定優(yōu)先級調(diào)度下基于整數(shù)線性規(guī)劃(Integer Linear Programming，ILP)的劃分問題求解方法。然而，上述方法利用率上限都沒有考慮共享資源的影響。當考慮任務(wù)訪問共享資源時，由于任務(wù)可以通過訪問共享資源來阻塞其他處理器上的任務(wù)，會導致劃分問題的復雜化。文獻[6]提出了將任務(wù)訪問本地資源而導致的阻塞合并到ILP中的任務(wù)劃分方法。文獻[7]提出了多處理器共享資源訪問協(xié)議(Multiprocessor Resource Sharing Protocol，MrsP)，該協(xié)議使用了幫助機制來減小阻塞時間，這也是本文主要研究的多處理器共享資源訪問協(xié)議。然而，上述算法未解決任務(wù)分組的利用率大于單個處理器利用率時的拆分和再分配問題。

對此，本文的研究內(nèi)容主要分為兩個部分：第1部分研究使用劃分調(diào)度(Partitioned Scheduling)算法，并在每個處理器上使用單調(diào)速率(Rate Monotonic，RM)算法(以下簡稱P-RM算法)，而對共享資源的管理則使用多處理器共享資源訪問協(xié)議[7]。通過將P-RM算法和MrsP協(xié)議相結(jié)合，得出了多處理器實時系統(tǒng)的整體可調(diào)度性條件，為MrsP協(xié)議的實際使用奠定了基礎(chǔ)。第2部分則在研究共享資源約束的基礎(chǔ)上，針對MrsP協(xié)議的任務(wù)劃分算法，提出了任務(wù)劃分的優(yōu)化方法。

1 系統(tǒng)模型與假設(shè)

本文的研究基于同構(gòu)多處理器(Symmetric Multiprocessor)平臺[8]。處理器的集合記為P={p1，p2，…，pm}，pk表示第k個處理器，其中1≤k≤m且k為整數(shù)。實時任務(wù)則記為Γ={τ1，τ2， …，τn}，τi表示第i個的實時任務(wù)，其中1≤i≤n且i為整數(shù)。共享資源可以分為硬件共享資源和軟件共享資源兩種，針對硬件類共享資源的訪問控制可以使用相應的機制來同步[2，9]處理。本文的共享資源為軟件類的共享資源，例如任務(wù)之間數(shù)據(jù)結(jié)構(gòu)或者變量的共享。設(shè)共享資源的數(shù)量為q(q≥1)，記為R={r1，r2，…，rq}，用rs表示第s個共享資源，其中1≤s≤q且s為整數(shù)。此外，本文假設(shè)系統(tǒng)中的共享資源不存在嵌套訪問的情況，因此在實際使用時可以使用分組鎖解決該問題[10-11]。

在劃分調(diào)度下，映射G(rs)返回使用共享資源rs的任務(wù)集合，映射F(τi)返回任務(wù)τi使用的共享資源集合，映射map(Γ)返回任務(wù)集合劃分到的處理器集合，映射map-1(pk)返回劃分到處理器集合的任務(wù)集合。

本文規(guī)定對于給定任務(wù)集合Γ={τ1，τ2， …，τn}，任務(wù)優(yōu)先級按降序排序，使用Πi表示任務(wù)τi的優(yōu)先級，即pri(τi)=Πi。

由于本文的研究是基于劃分調(diào)度算法，對于實時任務(wù)集Γ到處理器集合P的劃分，定義為Φ={Ψ1，Ψ2，…，Ψm}，其中Ψk為分配到第k個處理器上的任務(wù)集合。

本文研究的任務(wù)模型是偶發(fā)任務(wù)模型。該模型中每個任務(wù)有3個參數(shù)：相對截止時間D以及參數(shù)最壞執(zhí)行時間C和周期T。偶發(fā)任務(wù)τi的模型表示為τi=(Ci，Di，Ti)。這樣的一個偶發(fā)任務(wù)會釋放一個無限的實例序列。任意兩個相鄰實例的釋放時間的間隔有一個最小的約束周期Ti。任務(wù)τi釋放的每個實例最壞執(zhí)行時間為Ci，相對截止時間Di是指從到達時間起始到截止時間的時間間隔。本文中一個任務(wù)系統(tǒng)通常被表示為Γ={τ1，τ2， …，τn}。

2 系統(tǒng)整體可調(diào)度性分析

原有的MrsP協(xié)議多側(cè)重于最壞響應時間分析，實時調(diào)度算法又多基于傳統(tǒng)的獨立任務(wù)模型。因此本節(jié)整體研究了實時調(diào)度算法、共享資源訪問協(xié)議，彌補了獨立研究的不足，并在資源共享下，得出系統(tǒng)可調(diào)度性條件。

MrsP協(xié)議可以解決多處理器平臺上實時任務(wù)訪問共享資源的任務(wù)同步問題。根據(jù)MrsP協(xié)議的定義和性質(zhì)，實時任務(wù)訪問共享資源的阻塞可以分為兩類：本地阻塞和遠程阻塞[12]。

本地阻塞指同一處理器上低優(yōu)先級任務(wù)通過訪問或者占用共享資源，使自身優(yōu)先級高于原來的高優(yōu)先級任務(wù)，造成對高優(yōu)先級任務(wù)的阻塞。

遠程阻塞是指在不同處理器上一個任務(wù)訪問一個已被占用的共享資源時的等待時間，例如在不同處理器上的任務(wù)τi和τj，任務(wù)τj首先鎖定共享資源，當任務(wù)τi試圖訪問共享資源時便會進入自旋等待，此時任務(wù)τj對任務(wù)τi的阻塞便稱為遠程阻塞。任務(wù)τi自旋等待時間被稱為忙等待(Busy Waiting，BW)時間。本文定義任務(wù)τi訪問所有共享資源的遠程阻塞時間為BW，除去任務(wù)自身訪問共享資源的時間后可得

(1)

由文獻[13]可知，在使用RM調(diào)度算法調(diào)度實時任務(wù)時，PCP協(xié)議管理共享資源的系統(tǒng)中的一組實時任務(wù)可以被調(diào)度的條件如式(2)所示。

(2)

在使用RM調(diào)度算法調(diào)度實時任務(wù)時，PCP協(xié)議管理共享資源的系統(tǒng)中，一組實時任務(wù)可以被調(diào)度的條件為式(3)。

(3)

對于實時任務(wù)集合Γ到處理器集合P的劃分Φ={Ψ1，Ψ2，…，Ψm}，由以上的定理和推論可得，劃分到處理器pk上的任務(wù)集合Ψk的可調(diào)度條件為

(4)

或者

(5)

其中

nk=|map-1(pk)|

(6)

定義系統(tǒng)單個處理器利用率為

(7)

或者

(8)

定義系統(tǒng)利用率為式(9)。

U(Φ)=max{U(Ψk)|?pk}

(9)

最后，可以得到如下可調(diào)度性條件：在使用P-RM調(diào)度算法和MrsP協(xié)議管理共享資源的多處理器平臺上，對于實時任務(wù)集合Γ到處理器集合P的劃分Φ={Ψ1，Ψ2，…，Ψm}，系統(tǒng)的可調(diào)度性條件為式(10)。

(10)

根據(jù)RM調(diào)度算法的可調(diào)度性條件和MrsP協(xié)議的最壞響應時間分析進行系統(tǒng)分析，得出系統(tǒng)的整體性可調(diào)度條件，這是后續(xù)劃分算法設(shè)計和系統(tǒng)可調(diào)度性判定的重要基礎(chǔ)。

3 MrsP協(xié)議下任務(wù)劃分算法

本節(jié)針對MrsP協(xié)議的規(guī)則特性，在考慮任務(wù)訪問共享資源造成的阻塞情況下，提出了MrsP任務(wù)劃分算法。

3.1 任務(wù)劃分算法

任務(wù)的劃分將直接影響遠程阻塞時間，進而影響系統(tǒng)的可調(diào)度性。在基于P-RM調(diào)度算法和MrsP協(xié)議的多處理器平臺上，任務(wù)執(zhí)行時的延遲來自3個方面：(1)本地阻塞；(2)遠程阻塞；(3)相同處理器上高優(yōu)先級任務(wù)的搶占。其中本地阻塞相對遠程阻塞占比較小，且本地阻塞是共享資源互斥訪問的必然結(jié)果，幫助機制解決了處理器上高優(yōu)先級任務(wù)搶占造成的阻塞。因此，為了避免浪費處理器計算能力，應該盡量減小不同處理器上的任務(wù)訪問共享資源時造成的遠程阻塞。

劃分調(diào)度中的任務(wù)劃分具有NP-Hard復雜度，針對此類問題，通常采用啟發(fā)式算法進行任務(wù)劃分。傳統(tǒng)的裝箱算法不考慮任務(wù)之間的資源共享關(guān)系，僅按照任務(wù)的利用率分配到處理器上。文獻[14]提出的同步感知劃分算法和文獻[15]提出阻塞感知劃分算法使用了相似的思想，即將訪問相同資源的任務(wù)劃分到同一處理器上以減小遠程阻塞。然而兩種算法均未解決任務(wù)分組大于單個處理器利用率時的任務(wù)拆分和再分配問題。本節(jié)將研究使任務(wù)之間遠程阻塞時間最小的任務(wù)劃分問題。

算法1MrsP任務(wù)劃分算法

輸入：實時任務(wù)集合Γ={τ1，τ2， …，τn}，處理器數(shù)量M。

輸出：可調(diào)度劃分Φ或者劃分失敗。

1Φ=Φc=?

2?！?TasksetClust(Γ)//任務(wù)聚類算法

3Φc=TaskClassPart(Γc，Φc，m)/*任務(wù)類分配算法(WFD)*/

4 ifΦc=? then

5 return fail

6 end if

7Φ=SingleTaskPart(Γs，Φc)//見算法2

8 ifΦ=? then

9 return fail

10 end if

11 returnΦ

算法1總體概述了MrsP任務(wù)劃分算法的基本步驟。算法輸入為實時任務(wù)集合Γ和處理器數(shù)量m，輸出為可調(diào)度劃分Φ或者劃分失敗。首先，第1行定義Φ為可調(diào)度劃分集合并初始化為空集，定義Φc為之后任務(wù)類劃分的結(jié)果并初始化為空集。算法第2行為任務(wù)聚類算法，聚類算法時任務(wù)集合為Γ，輸出為聚類后的任務(wù)集合為Γ′。算法第3行為任務(wù)類的劃分算法，該輸入為任務(wù)類集合Γc、任務(wù)類劃分的結(jié)果Φc(此時為空集)和處理器數(shù)量m，輸出為任務(wù)類劃分的結(jié)果Φc。算法第4～第6行判斷算法的任務(wù)類劃分結(jié)果Φc是否為空集，若Φc為空集，則算法返回劃分失敗，否則繼續(xù)執(zhí)行下一步驟。算法第7行為單個任務(wù)的劃分算法，輸入為單個任務(wù)集合Γs和任務(wù)類劃分結(jié)果Φc，輸出為可調(diào)度劃分Φ。算法2的詳細步驟見下文。算法第8行～第10行判斷可調(diào)度劃分Φ是否為空集，若Φ為空集，則算法返回劃分失敗，否則算法第11行返回可調(diào)度劃分Φ。

3.2 單個任務(wù)分配

在傳統(tǒng)的任務(wù)劃分算法中，待劃分的任務(wù)是按照固定的任務(wù)利用率來確定劃分順序。然而，在原始的MrsP協(xié)議最壞響應時間分析中，并沒有考慮任務(wù)訪問共享資源更細致的情況，這種分析方法在計算忙等待時間時可能存在對一個關(guān)鍵區(qū)進行重復計算的問題，這是一種過于悲觀的計算方法。

考慮圖1中所示的情況，在一個多處理器實時系統(tǒng)上，處理器數(shù)目m為3，系統(tǒng)共包括5個實時任務(wù)，其中pri(τi)=i，假設(shè)在任一任務(wù)的釋放期間，其余任務(wù)也僅釋放一次。對于任務(wù)τ3來說，需要訪問共享資源r3次，在任務(wù)的執(zhí)行期間，會受到處理器p1上任務(wù)τ1的3次阻塞和處理器p3上任務(wù)τ5的兩次阻塞，則任務(wù)τ3的執(zhí)行時間為C′3=C3+3cs+3cs+2cs=C3+8cs。然而，使用根據(jù)MrsP協(xié)議最壞響應時間分析可得C′3=C3+3×3cs=C3+9cs。對于任務(wù)τ4來說，使用MrsP協(xié)議最壞響應時間分析可得到C′4=C4+3×3cs=C4+9cs，然而，任務(wù)τ4只會受到處理器p1上任務(wù)τ2的兩次阻塞，任務(wù)τ4第3次請求訪問共享資源將不會受到阻塞。導致這種重復計算問題的原因是，原始的MrsP協(xié)議最壞響應時間分析計算假設(shè)任務(wù)的每次訪問共享資源都會受到所有處理器上任務(wù)的阻塞。因此，這種計算方式是過于悲觀的。

圖1 關(guān)鍵區(qū)重復計算問題示例Figure 1. An example of a critical area double-counting problem

在P-RM調(diào)度算法下，若在不同處理器上有任務(wù)τi和任務(wù)τj，則任務(wù)τi的一個實例在執(zhí)行過程中受到任務(wù)τj釋放的實例影響的個數(shù)為

(11)

式中，mod(x，y)表示x除以y得到的余數(shù)。

為解決重復計算問題，本節(jié)算法在劃分單個任務(wù)τi時考慮了3個因素，分別為：

(1)除map(τi)之外每個處理器對任務(wù)τi的阻塞次數(shù)；

(2)處理器集合對任務(wù)τi總的阻塞次數(shù)；

(3)任務(wù)之間的周期對阻塞次數(shù)的影響。

算法通過使用min函數(shù)取3種影響因素的最小值來解決重復計算問題。

算法2單個任務(wù)分配算法

輸入：單個任務(wù)集合Γs，任務(wù)類劃分Φc。

輸出：可調(diào)度劃分Φ。

1Φ=Φc

2 util[s]={0}

3 whileΓs≠? do

4 fori=1:sdo

5 util[i]=calU(τi，Φ)//見算法3

6 end for

7τi=getMax(util)/*返回util數(shù)組利用率最大的任務(wù)*/

8k=findProcessor(τi，Φ)//尋找處理器算法

9 ifk=0 then

10 return ?

11 end if

12Ψk=Ψk∪{τi}

13Φ={Ψ1，Ψ2，...，Ψm}

14Γs=Γs-{τi}

15 end while

16 returnΦ

算法2為單個任務(wù)分配算法。算法輸入為單個任務(wù)集合Γs和任務(wù)類劃分Φc，輸出為可調(diào)度劃分Φ。算法第1行使用任務(wù)類劃分Φc初始化可調(diào)度劃分結(jié)果Φ，第2行定義util數(shù)組并初始化為0，其中數(shù)組元素個數(shù)為單個任務(wù)的數(shù)量s。算法第3行～第15行循環(huán)將任務(wù)劃分到m個處理器上。算法第4行～第6行計算s個單獨任務(wù)相對于當前劃分Φ的任務(wù)利用率u。算法第7行的getMax函數(shù)返回util數(shù)組中利用率最大的任務(wù)τi。算法第8行定義的findProcessor函數(shù)為任務(wù)τi根據(jù)當前的劃分Φ尋找最合適的處理器，返回值為處理器代號k。算法第9行～第11行判斷處理器代號k是否為0，若為0，則表明任務(wù)τi為找到合適的處理器，返回劃分失??；若不為0，算法繼續(xù)執(zhí)行。第12行～第13行將任務(wù)τi劃分到處理器k的集合Ψk上，并從單個任務(wù)集合Γs中刪除任務(wù)τi，接著當集合Γs不為空時繼續(xù)循環(huán)，直到所有任務(wù)都劃分完成，算法返回可調(diào)度劃分結(jié)果Φ。

3.3 任務(wù)利用率算法

該算法的提出主要是解決任務(wù)利用率重復計算的問題。

算法3利用率計算算法

輸入：任務(wù)τi，當前劃分Φc。

輸出：利用率ui。

1ui=0

2 BW′i=0

3 forrs=Rido

4 max_block[k]=Ni，s

5 sum=(m-1)Ni，s

6 BW′is=0

7 forzj，s，y∈Θsdo

8 if ?k，τj∈Ψkthen

9 count=min(ai，j，sum， max_block[k])

10 max_block[k]-=count

11 else

12 count=min(ai，j，sum，Ni，s)

13 end if

14 BW′is+=count*Cs

15 sum-=count

16 if sum ==0

17 break

18 end if

19 end for

20 BW′i+= BW′is

21 end for

22ui=(Ci+ BW′i)/Ti

23 returnui

其中Ri為任務(wù)訪問的共享資源集合，zj，s，y是任務(wù)τj訪問共享資源rs的一個關(guān)鍵區(qū)，0≤y≤Ni，s，zj，s是任務(wù)τj需要訪問共享資源rs的關(guān)鍵區(qū)集合，Θs是任務(wù)集Γ中所有任務(wù)訪問共享資源rs的關(guān)鍵區(qū)集合。

4 實驗與結(jié)果

實驗平臺主機采用Windows10操作系統(tǒng)，并虛擬機上安裝配置LITMUSRT實驗平臺[16-17]。

任務(wù)集按表1生成，共設(shè)計了3個實驗。每次控制一個參數(shù)變動，算法性能評價指標為調(diào)度給定任務(wù)集所需處理器的數(shù)量。本文中，3個實驗分別研究了共享資源訪問時間、訪問共享資源任務(wù)數(shù)量和任務(wù)集合利用率3個變量變化時，調(diào)度任務(wù)集合所需的處理器數(shù)量[18]。

表1 實驗參數(shù)范圍

實驗的對比算法為WF算法、同步感知算法和阻塞感知算法。其中，WF算法在傳統(tǒng)裝箱算法中性能最好[18]，因此選擇WF算法作為傳統(tǒng)裝箱算法的代表。同步感知算法和阻塞感知算法都采用了任務(wù)捆綁分配的思想，即將訪問相同共享資源的任務(wù)劃分到同一個處理器上，以減小遠程阻塞。

圖2 共享資源訪問時間與所需處理器數(shù)量的關(guān)系Figure 2. The relationship between shared resource access time and the number of required processors

圖2的實驗條件為：生成的任務(wù)集合的利用率為8，其中每個任務(wù)最多有3個臨界區(qū)，每個共享資源被10個任務(wù)訪問。在此實驗條件下，改變?nèi)蝿?wù)訪問共享資源rs的時間cs，測試各個任務(wù)劃分算法的性能。隨著任務(wù)訪問共享資源時間的增大，任務(wù)被阻塞的時間也隨之增加，任務(wù)訪問共享資源的競爭程度增大，這導致任務(wù)集合被調(diào)度所需要的處理器數(shù)目不斷增加。其中，WF算法在劃分中并未考慮共享資源因素的影響，而同步感知劃分算法和阻塞感知劃分算法通過盡量將訪問相同共享資源的任務(wù)劃分到同一個處理器上減少了任務(wù)的遠程阻塞，提高了處理器利用率。本文的MrsP任務(wù)劃分算法在任務(wù)分類的基礎(chǔ)上，將超過單個處理器利用率的任務(wù)根據(jù)當前劃分集合的實際情況劃分到使系統(tǒng)利用率增加最少的處理器上。由圖2的結(jié)果可知，WF算法的處理器數(shù)目增加最快，同步感知任務(wù)劃分算法和阻塞感知任務(wù)劃分算法的處理器數(shù)目增加稍慢一些，兩者中阻塞感知任務(wù)劃分算法效率略好，MrsP任務(wù)劃分算法所需處理器數(shù)目始終最少。相對于次優(yōu)的同步感知任務(wù)劃分算法，MrsP任務(wù)劃分算法所需處理器數(shù)目減少了4%～10%。

圖3 共享資源任務(wù)數(shù)與所需處理器數(shù)量的關(guān)系Figure 3. The Relationship between the number of shared resource tasks and the number of required processors

圖3的實驗條件為：生成的任務(wù)集合的利用率為8，其中每個任務(wù)最多有3個臨界區(qū)，并固定任務(wù)訪問共享資源的時間為5 ms。由圖3可以看出，由于WF任務(wù)劃分算法未考慮資源共享問題，所需處理器數(shù)量增加最快，而同步感知劃分算法和阻塞感知劃分算法考慮了共享資源問題并減少了任務(wù)阻塞尤其是遠程阻塞的發(fā)生。因此，這兩種算法分配給相同的任務(wù)集合的處理器數(shù)量明顯少于WF算法。本文提出的MrsP任務(wù)劃分算法在同步感知劃分算法和阻塞感知劃分算法的基礎(chǔ)上，考慮了任務(wù)類利用率高于單個處理器時的任務(wù)分配算法。對高于單個處理器利用率的任務(wù)，根據(jù)當前的劃分分配到使系統(tǒng)利用率增加少的處理器上。相對于次優(yōu)的同步感知任務(wù)劃分算法，MrsP任務(wù)劃分算法所需處理器數(shù)目減少了2%～10%。

圖4 任務(wù)集利用率與所需處理器數(shù)量變化關(guān)系Figure 4. The relationship between the number of required processors and task set utilization

圖4的實驗條件為：任務(wù)訪問共享資源的時間為5 ms，其中每個任務(wù)最多有3個臨界區(qū)，每個共享資源被10個任務(wù)訪問。在此實驗條件下，增加生成任務(wù)集合的利用率，測試各個任務(wù)劃分算法的性能。任務(wù)集合的利用率反映了系統(tǒng)的負載，隨著任務(wù)集合的利用率增大，所需的處理器數(shù)目不斷增加。由圖4可得，相對于次優(yōu)的同步感知任務(wù)劃分算法，MrsP任務(wù)劃分算法所需處理器數(shù)目減少了15%～20%。

針對傳統(tǒng)裝箱算法、阻塞感知算法、同步感知算法和MrsP任務(wù)劃分算法，設(shè)計了3個實驗來驗證4種算法的劃分性能，3個實驗分別改變了共享資源訪問時間、訪問共享資源任務(wù)數(shù)量和任務(wù)集合利用率3個變量。根據(jù)調(diào)度任務(wù)集合所需的處理器數(shù)量來判斷4種劃分算法的性能，結(jié)果表明MrsP任務(wù)劃分算法調(diào)度給定的任務(wù)集合所需要的處理器數(shù)目少于其他幾種任務(wù)劃分算法。

5 結(jié)束語

本文結(jié)合P-RM算法和MrsP協(xié)議得出了多處理器實時系統(tǒng)的整體可調(diào)度性條件。隨后，根據(jù)MrsP協(xié)議的特性，改進任務(wù)利用率的計算方式，解決了關(guān)鍵區(qū)重復計算的問題，并在此基礎(chǔ)上提出了一種減小阻塞時間的任務(wù)劃分算法。相對于之前的任務(wù)劃分算法，該算法解決了對任務(wù)分類后進行適當拆分并再分配的問題。實驗表明，本文提出的任務(wù)劃分算法調(diào)度給定的任務(wù)集合所需要的處理器數(shù)目少于之前的任務(wù)劃分算法。

本文的研究基于同構(gòu)多處理器平臺。然而當前多處理器的發(fā)展趨勢是異構(gòu)多處理器系統(tǒng)[19-20]。未來的研究工作應當基于異構(gòu)多處理器平臺，其中異構(gòu)多處理器平臺上的實時調(diào)度和共享資源訪問問題是需要重點研究的方向。當在異構(gòu)多處理器平臺上使用劃分調(diào)度算法時，將任務(wù)劃分至不同大小的處理器上也是急需解決的問題。