基于MrsP協(xié)議的任務(wù)劃分優(yōu)化算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

或者

(5)

其中

nk=|map-1(pk)|

(6)

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

(7)

或者

(8)

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

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

(9)

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

(10)

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

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

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

3.1 任務(wù)劃分算法

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

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

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

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

3.2 單個(gè)任務(wù)分配

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

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

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

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

(11)

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

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

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

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

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

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

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

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

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

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

算法3利用率計(jì)算算法

輸入：任務(wù)τi，當(dāng)前劃分Φ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的一個(gè)關(guān)鍵區(qū)，0≤y≤Ni，s，zj，s是任務(wù)τj需要訪問共享資源rs的關(guān)鍵區(qū)集合，Θs是任務(wù)集Γ中所有任務(wù)訪問共享資源rs的關(guān)鍵區(qū)集合。

4 實(shí)驗(yàn)與結(jié)果

實(shí)驗(yàn)平臺(tái)主機(jī)采用Windows10操作系統(tǒng)，并虛擬機(jī)上安裝配置LITMUSRT實(shí)驗(yàn)平臺(tái)[16-17]。

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

表1 實(shí)驗(yàn)參數(shù)范圍

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

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

圖2的實(shí)驗(yàn)條件為：生成的任務(wù)集合的利用率為8，其中每個(gè)任務(wù)最多有3個(gè)臨界區(qū)，每個(gè)共享資源被10個(gè)任務(wù)訪問。在此實(shí)驗(yàn)條件下，改變?nèi)蝿?wù)訪問共享資源rs的時(shí)間cs，測(cè)試各個(gè)任務(wù)劃分算法的性能。隨著任務(wù)訪問共享資源時(shí)間的增大，任務(wù)被阻塞的時(shí)間也隨之增加，任務(wù)訪問共享資源的競(jìng)爭(zhēng)程度增大，這導(dǎo)致任務(wù)集合被調(diào)度所需要的處理器數(shù)目不斷增加。其中，WF算法在劃分中并未考慮共享資源因素的影響，而同步感知?jiǎng)澐炙惴ê妥枞兄獎(jiǎng)澐炙惴ㄍㄟ^盡量將訪問相同共享資源的任務(wù)劃分到同一個(gè)處理器上減少了任務(wù)的遠(yuǎn)程阻塞，提高了處理器利用率。本文的MrsP任務(wù)劃分算法在任務(wù)分類的基礎(chǔ)上，將超過單個(gè)處理器利用率的任務(wù)根據(jù)當(dāng)前劃分集合的實(shí)際情況劃分到使系統(tǒng)利用率增加最少的處理器上。由圖2的結(jié)果可知，WF算法的處理器數(shù)目增加最快，同步感知任務(wù)劃分算法和阻塞感知任務(wù)劃分算法的處理器數(shù)目增加稍慢一些，兩者中阻塞感知任務(wù)劃分算法效率略好，MrsP任務(wù)劃分算法所需處理器數(shù)目始終最少。相對(duì)于次優(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的實(shí)驗(yàn)條件為：生成的任務(wù)集合的利用率為8，其中每個(gè)任務(wù)最多有3個(gè)臨界區(qū)，并固定任務(wù)訪問共享資源的時(shí)間為5 ms。由圖3可以看出，由于WF任務(wù)劃分算法未考慮資源共享問題，所需處理器數(shù)量增加最快，而同步感知?jiǎng)澐炙惴ê妥枞兄獎(jiǎng)澐炙惴紤]了共享資源問題并減少了任務(wù)阻塞尤其是遠(yuǎn)程阻塞的發(fā)生。因此，這兩種算法分配給相同的任務(wù)集合的處理器數(shù)量明顯少于WF算法。本文提出的MrsP任務(wù)劃分算法在同步感知?jiǎng)澐炙惴ê妥枞兄獎(jiǎng)澐炙惴ǖ幕A(chǔ)上，考慮了任務(wù)類利用率高于單個(gè)處理器時(shí)的任務(wù)分配算法。對(duì)高于單個(gè)處理器利用率的任務(wù)，根據(jù)當(dāng)前的劃分分配到使系統(tǒng)利用率增加少的處理器上。相對(duì)于次優(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的實(shí)驗(yàn)條件為：任務(wù)訪問共享資源的時(shí)間為5 ms，其中每個(gè)任務(wù)最多有3個(gè)臨界區(qū)，每個(gè)共享資源被10個(gè)任務(wù)訪問。在此實(shí)驗(yàn)條件下，增加生成任務(wù)集合的利用率，測(cè)試各個(gè)任務(wù)劃分算法的性能。任務(wù)集合的利用率反映了系統(tǒng)的負(fù)載，隨著任務(wù)集合的利用率增大，所需的處理器數(shù)目不斷增加。由圖4可得，相對(duì)于次優(yōu)的同步感知任務(wù)劃分算法，MrsP任務(wù)劃分算法所需處理器數(shù)目減少了15%～20%。

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

5 結(jié)束語

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

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