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

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

隨著新型汽車產(chǎn)業(yè)的發(fā)展，汽車上的電子控制裝置數(shù)量急劇增加，眾多傳感器和執(zhí)行器之間進(jìn)行通信傳輸?shù)男盘?hào)量也大幅度增多，導(dǎo)致傳統(tǒng)的CAN(Controller Area Network)總線已無(wú)法完全滿足新型汽車產(chǎn)業(yè)對(duì)通信總線的要求[1]。CAN FD(CAN with Flexible Data rate)總線的帶寬大，其傳輸速率可達(dá)CAN總線的3～8倍，且能夠降低錯(cuò)誤幀漏檢率，將會(huì)成為今后汽車電子領(lǐng)域的一個(gè)重要研究方向[2-4]。與此同時(shí)，為了保證傳感器與執(zhí)行器之間信號(hào)量傳輸?shù)膶?shí)時(shí)性，采用合適的調(diào)度算法對(duì)眾多信號(hào)量進(jìn)行快速、高效地調(diào)度，對(duì)汽車系統(tǒng)的安全及穩(wěn)定起著至關(guān)重要的作用[5]。因此，利用CAN FD總線來(lái)快速、準(zhǔn)確、實(shí)時(shí)地傳遞信息，對(duì)汽車內(nèi)信息進(jìn)行調(diào)度的研究具有重要的意義與價(jià)值[6]。目前基于優(yōu)先級(jí)的調(diào)度算法大體可分為靜態(tài)調(diào)度、動(dòng)態(tài)調(diào)度和混合調(diào)度等[7]。其中，靜態(tài)算法包括單調(diào)速率調(diào)度算法(Rate Monotonic，RM)和截止期單調(diào)調(diào)度算法(Deadline Monotonic，DM)[8]。然而這兩種算法均對(duì)總線利用率較低且對(duì)事件觸發(fā)的報(bào)文處理不夠靈活[9]。動(dòng)態(tài)算法包括最早截止期優(yōu)先算法(Earliest Deadline First，EDF)和最小松弛優(yōu)先算法(Least Laxity First，LLF)[10]，這兩種算法分別以消息的截止時(shí)期和剩余時(shí)間長(zhǎng)短來(lái)分配任務(wù)優(yōu)先級(jí)，提高了網(wǎng)絡(luò)的利用率。為了適應(yīng)不可搶占任務(wù)的需要，文獻(xiàn)[11]給出了不可搶占式EDF調(diào)度算法的可調(diào)度性判定方法。文獻(xiàn)[12]提出了一種分解算法來(lái)對(duì)應(yīng)用在多核處理器上的最早截止期優(yōu)先算法進(jìn)行優(yōu)化。文獻(xiàn)[13]通過(guò)使用調(diào)度技術(shù)減少了網(wǎng)絡(luò)引起的延遲，確定了CAN、以太網(wǎng)、TDMA(Time Division Multiple Access)以及F-DMA(Frequency Division Multiple Access)之間適合用于EDF調(diào)度的PID(Proportional Integral Derivative)控制網(wǎng)絡(luò)，并通過(guò)該算法減少了時(shí)延問題。文獻(xiàn)[14]中將EDF算法和LST(Least Slace Time First)算法相結(jié)合，提高了實(shí)時(shí)任務(wù)的調(diào)度性能。文獻(xiàn)[15]對(duì)編碼動(dòng)態(tài)更新和優(yōu)先級(jí)反轉(zhuǎn)的問題提出了優(yōu)化方法。其通過(guò)利用EDF算法來(lái)提高消息的實(shí)時(shí)性，且解決截止期編碼問題時(shí)，可以采用不同的分區(qū)編碼方式把變化范圍較大的截止期表示出來(lái)[16-17]。在綜合考慮截止期和價(jià)值度兩方面影響后，文獻(xiàn)[18]提出了基于截止期價(jià)值度優(yōu)先的DVF(Deadline Value First)算法，即在滿足消息的截止期的前提下，盡量讓價(jià)值度更高的消息優(yōu)先發(fā)送。

本文在對(duì)平均分區(qū)EDF調(diào)度算法研究的基礎(chǔ)上，改進(jìn)了適用于CAN FD通信的EDF調(diào)度算法。利用指數(shù)-冪函數(shù)的動(dòng)態(tài)編碼分區(qū)方法擴(kuò)大了截止期的編碼范圍，降低了出現(xiàn)優(yōu)先級(jí)反轉(zhuǎn)的概率，并合理分配了網(wǎng)絡(luò)帶寬，降低了總線負(fù)載，適當(dāng)提高了帶寬利用率。

1 EDF算法

1.1 平均分區(qū)EDF算法

為了提高單處理器系統(tǒng)的處理器利用率，EDF算法是動(dòng)態(tài)搶占式調(diào)度算法中非常重要的算法[19]。該算法根據(jù)報(bào)文的絕對(duì)截止時(shí)間Dm的大小動(dòng)態(tài)分配優(yōu)先級(jí)。報(bào)文的絕對(duì)截止時(shí)間越小，其優(yōu)先級(jí)越高。然而隨著時(shí)間的增加，報(bào)文的絕對(duì)截止時(shí)間也隨之增大，此時(shí)標(biāo)識(shí)符的表示范圍將無(wú)法涵蓋所有的截止期。因此，為了有效地減少標(biāo)識(shí)符ID(Identifier)中用來(lái)表示優(yōu)先級(jí)的位數(shù)，本文引入相對(duì)截止時(shí)間dm=Dm-tstart，其中tstart為總線仲裁開始時(shí)間。此外，通過(guò)對(duì)報(bào)文的截止時(shí)間進(jìn)行編碼來(lái)計(jì)算報(bào)文的優(yōu)先級(jí)，而采用不同的標(biāo)識(shí)符編碼方式得出的優(yōu)先級(jí)計(jì)算結(jié)果也會(huì)相應(yīng)不同，通常在EDF算法中采用如下所示的平均分區(qū)編碼方式。

對(duì)于一組報(bào)文{m1，m2，…，mn}，假設(shè)它們的相對(duì)截止時(shí)間從小到大排列為{d1，d2，…，dmax}。采用平均分區(qū)的方式是將時(shí)間軸以報(bào)文的最大相對(duì)截止時(shí)間dmax為上限等分成k段，則每段區(qū)間長(zhǎng)為dmax/k。假設(shè)對(duì)任意兩個(gè)報(bào)文mi與mj，其相對(duì)截止時(shí)間分別為di與dj且di

圖1 平均分區(qū)示意圖Figure 1. Schematic diagram of average partition

根據(jù)EDF調(diào)度算法，在每輪調(diào)度時(shí)，報(bào)文的優(yōu)先級(jí)根據(jù)其相對(duì)截止時(shí)間確定。圖1中報(bào)文mi與mj的相對(duì)截止時(shí)間di與dj被劃分在一個(gè)區(qū)間，即二者具有相同的優(yōu)先級(jí)。這與根據(jù)標(biāo)識(shí)符判定mi的優(yōu)先級(jí)高于mj的實(shí)際情況不符。因此，根據(jù)上述分區(qū)，會(huì)導(dǎo)致報(bào)文mi被mj推遲占用總線的優(yōu)先級(jí)反轉(zhuǎn)問題[20]。

1.2 可調(diào)度性判定

由于CAN FD總線屬于非搶占式總線，故參考信號(hào)調(diào)度中非搶占式調(diào)度理論對(duì)報(bào)文的可調(diào)度性判定進(jìn)行分析。首先給出定理1，以確?？偩€利用率滿足要求，接著用定理2給出非搶占截止期調(diào)度策略的可調(diào)度性判定。

定理1[11]由n個(gè)報(bào)文組成的報(bào)文集合{m1，m2，…，mn}，當(dāng)且僅當(dāng)在所有報(bào)文均滿足式(1)時(shí)，則稱其為可調(diào)度的

(1)

式中，Cm和Tm分別為報(bào)文m的傳輸時(shí)間和請(qǐng)求周期。

定理2[11]對(duì)實(shí)時(shí)任務(wù)τm=(Tm，Cm，dm)，m=1，2，…，n，當(dāng)且僅當(dāng)其滿足以下計(jì)算式時(shí)，非搶占截止期調(diào)度策略是可調(diào)度的

(2)

式中，dmin=min{dm:1≤m≤n}；Cp代表報(bào)文所需的最長(zhǎng)通信時(shí)間。

上述兩個(gè)定理成立的條件已在文獻(xiàn)[19]中得到證明。為了簡(jiǎn)化判定條件，假設(shè)報(bào)文傳輸在最壞情況下(即最壞的阻塞情況)發(fā)生，所有報(bào)文在同一時(shí)間t=0時(shí)釋放。由于任務(wù)執(zhí)行時(shí)是非搶占的，即此時(shí)無(wú)論請(qǐng)求執(zhí)行的新任務(wù)的優(yōu)先級(jí)高低，正在執(zhí)行的任務(wù)都無(wú)法被中斷，而新任務(wù)則必須在該任務(wù)執(zhí)行結(jié)束后才有機(jī)會(huì)使用總線。針對(duì)上述情況，可調(diào)度性的判定應(yīng)將高優(yōu)先級(jí)報(bào)文被低優(yōu)先級(jí)報(bào)文阻塞的時(shí)間包含在內(nèi)，如引理1所示。

引理1[21]假設(shè)由n個(gè)報(bào)文組成的報(bào)文集合{m1，m2，…，mn}。該消息集合在滿足式(3)時(shí)，可被EDF算法調(diào)度

(3)

式中，Cm、Tm、Bm分別為報(bào)文m傳輸時(shí)間、周期及最大阻塞時(shí)間。

2 改進(jìn)的EDF算法

2.1 指數(shù)分區(qū)的母區(qū)間

針對(duì)指數(shù)分區(qū)的方式，若使接近仲裁開始時(shí)間的區(qū)間較小，則精度會(huì)增高；而離仲裁開始時(shí)間遠(yuǎn)的區(qū)間較大，精度也會(huì)有所降低。因此，在這種分區(qū)方式下，能夠在較大程度上減少截止期相近的兩個(gè)報(bào)文被分到同一個(gè)母區(qū)間內(nèi)的概率，從而更好地保證報(bào)文的實(shí)時(shí)性[16]。本文對(duì)母區(qū)間采用指數(shù)分區(qū)的方式，其具體過(guò)程如下：

步驟1將報(bào)文集合中的各相對(duì)截止期dm按大小排列，取截止期中的最大值dmax作為截止期分區(qū)的上限值；

步驟2選取指數(shù)分區(qū)時(shí)的分區(qū)因子a，即采用以a為底的指數(shù)方式對(duì)相對(duì)截止時(shí)間范圍[0，dmax)進(jìn)行分區(qū)時(shí)，首先需要明確底數(shù)a的大小。由于分區(qū)因子a的大小和報(bào)文的數(shù)量有關(guān)，在本文中為了計(jì)算簡(jiǎn)單清晰故取a=2；

步驟3根據(jù)上述的指數(shù)分區(qū)方案，假設(shè)報(bào)文在0時(shí)刻釋放，將以0時(shí)刻為起始至dmax/2k的范圍定義為母區(qū)間0，則共計(jì)k+1個(gè)母區(qū)間，以{I0，I1，I2，…，Ik-1，Ik}形式表示，即分區(qū)后第1個(gè)母區(qū)間I0的范圍為[0，dmax/2k)，第2個(gè)母區(qū)間I1的范圍為[dmax/2k，dmax/2k-1)。以此類推，第i個(gè)指數(shù)分區(qū)Ii的范圍為[dmax/2k+1-i，dmax/2k-i)，最后1個(gè)母區(qū)間Ik的范圍為[dmax/2，dmax)。綜上，其區(qū)間范圍表示為

(4)

則第i個(gè)母區(qū)間的大小如式(5)所示。

(5)

母區(qū)間具體劃分如圖2所示，按照上述方法劃分出多個(gè)母區(qū)間，且各個(gè)母區(qū)間的長(zhǎng)度均不同。這種分區(qū)的優(yōu)點(diǎn)是能在一定程度降低截止期相近的報(bào)文在傳輸時(shí)分配同一優(yōu)先級(jí)的可能性，可以有效避免優(yōu)先級(jí)反轉(zhuǎn)的情況出現(xiàn)。

圖2 母區(qū)間指數(shù)分區(qū)Figure 2. Parent interval of exponential function partition

2.2 冪函數(shù)分區(qū)的子區(qū)間

在采用指數(shù)函數(shù)將截止期分成多個(gè)母區(qū)間后，本文將采用冪函數(shù)分區(qū)方式將每個(gè)母區(qū)間再細(xì)分成多個(gè)子區(qū)間。該操作的目的是再次在有限的范圍內(nèi)細(xì)分出不同長(zhǎng)度的截止期區(qū)間，以便在滿足不同報(bào)文的截止期要求的前提下，進(jìn)一步降低優(yōu)先級(jí)反轉(zhuǎn)出現(xiàn)的概率。假設(shè)對(duì)每個(gè)母區(qū)間Ii按照冪函數(shù)的方法再劃分出q個(gè)子區(qū)間，其中選取冪函數(shù)的冪次為1。圖3中給出在第i個(gè)母區(qū)間中劃分為q個(gè)子區(qū)間的分區(qū)情況。

圖3 子區(qū)間冪函數(shù)分區(qū)Figure 3. Subintervalof power function partition

經(jīng)過(guò)上述指數(shù)函數(shù)的分區(qū)后，在對(duì)每個(gè)母區(qū)間內(nèi)劃分子區(qū)間時(shí)，子區(qū)間的實(shí)際表示范圍需要考慮到母區(qū)間的起始下限值。因此，在第i個(gè)母區(qū)間的第1個(gè)子區(qū)間的范圍為[dmax/2k+1-i， (q+1)×dmax/q×2k+1-i)，第2個(gè)子區(qū)間的范圍為[(q+1)×dmax/q×2k+1-i，q×dmax/(q-1)×2k+1-i)。以此類推，即可得出第i個(gè)母區(qū)間的第j個(gè)子區(qū)間的范圍為

(6)

式中，i=0，1，2，…，k；j=2，3…，q。第i個(gè)母區(qū)間的最后1個(gè)子區(qū)間的范圍為[3×dmax/2k+2-i，dmax/2k-i)。

根據(jù)上式，將每個(gè)子區(qū)間稱為基本時(shí)間單元U，則第i個(gè)母區(qū)間的子區(qū)間j可利用基本時(shí)間單元Uij表示，而Uij的大小可以根據(jù)式(7)求出。

(7)

經(jīng)過(guò)分區(qū)編碼后，現(xiàn)存網(wǎng)絡(luò)中就有q×(k+1)個(gè)優(yōu)先級(jí)的信息。假設(shè)CAN FD總線的標(biāo)識(shí)符編碼位共有n位，如果要涵蓋所有的優(yōu)先級(jí)則必須滿足2n≥q×(k+1)。

2.3 優(yōu)先級(jí)的計(jì)算

假設(shè)所有報(bào)文的相對(duì)截止時(shí)間已知，且報(bào)文m的相對(duì)截止時(shí)間為dm，且dm≤dmax，則根據(jù)dm的大小及分區(qū)方式可以求出其所在的母區(qū)間和子區(qū)間，進(jìn)而求出報(bào)文m所對(duì)應(yīng)的優(yōu)先級(jí)。具體計(jì)算過(guò)程如下所示：

步驟1先計(jì)算出dm所在的母區(qū)間的區(qū)間號(hào)i。任一報(bào)文的截止期按照此分區(qū)方式進(jìn)行劃分，必定位于劃分的某個(gè)母區(qū)間范圍內(nèi)，即滿足

(8)

式中，i=0，1，2，…，k。

根據(jù)上式，利用截止期dm所在的范圍反求母區(qū)間i的范圍，化簡(jiǎn)可得

(9)

由于優(yōu)先級(jí)越高其所在區(qū)間號(hào)i應(yīng)該越小。因此確定區(qū)間號(hào)時(shí)采用向下取整的方式以獲得更高的優(yōu)先級(jí)，此時(shí)求出i的值為

(10)

步驟2確定截止期dm所處子區(qū)間的區(qū)段號(hào)j。報(bào)文的相對(duì)截止期必定落在子區(qū)間j所處范圍內(nèi)，即

(11)

根據(jù)式(11)計(jì)算子區(qū)間區(qū)段號(hào)的大小，得

(12)

整理上式可得子區(qū)間區(qū)段號(hào)j為

(13)

步驟3根據(jù)計(jì)算式計(jì)算得到的母區(qū)間號(hào)i和子區(qū)間號(hào)j的值，隨后即可計(jì)算報(bào)文的優(yōu)先級(jí)p，至此完成將報(bào)文的絕對(duì)截止時(shí)間轉(zhuǎn)化為報(bào)文優(yōu)先級(jí)操作，計(jì)算式如下

p=j+(i-1)×q

(14)

將求得的優(yōu)先級(jí)p為十進(jìn)制，可將其二進(jìn)制化即為報(bào)文的標(biāo)識(shí)符。

2.4 誤差及可調(diào)度性分析

在采用上述指數(shù)-冪函數(shù)方式進(jìn)行分區(qū)時(shí)，以各個(gè)報(bào)文的相對(duì)截止時(shí)間為基準(zhǔn)，可以求得各個(gè)報(bào)文的優(yōu)先級(jí)，進(jìn)而完成對(duì)標(biāo)識(shí)符的動(dòng)態(tài)編碼。然而，在計(jì)算優(yōu)先級(jí)的過(guò)程中對(duì)母區(qū)段號(hào)和子區(qū)段號(hào)的選取均為向下取整，這種做法不可避免地會(huì)產(chǎn)生誤差。將這種誤差定義為“量化誤差”[16，22]，記該誤差為Eij，式中，i=0，1，2，…，k；j=1，2，…，q，則其值為

(15)

根據(jù)上式中的誤差Eij，可以進(jìn)一步對(duì)EDF算法的可調(diào)度性判定引理1中的判別式進(jìn)行修正，得到式(16)，即

(16)

式中，Eij為正常傳輸過(guò)程中每個(gè)報(bào)文經(jīng)計(jì)算存在的誤差。量化誤差Eij一定為正且其大小不會(huì)超過(guò)基本時(shí)間單元Uij的大小，即0 ≤Eij≤Uij。在此誤差影響下，若要充分保證系統(tǒng)可調(diào)度，則可調(diào)度性判別式應(yīng)更新為式(17)，即

(17)

令Xf=Uij/Tm， 式中Xf≥0，f=1，2，…，k×q，化簡(jiǎn)上式得

(18)

若取X=max{Xf}，則最終的可調(diào)度性判定式為式(19)。

(19)

通過(guò)上述的可調(diào)度性判別計(jì)算式可知，量化誤差的存在對(duì)報(bào)文的可調(diào)度性產(chǎn)生了影響，使報(bào)文的可調(diào)度性判別更加嚴(yán)格。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 模型設(shè)計(jì)

為達(dá)到良好的仿真效果，以下將從通信網(wǎng)絡(luò)定義、ECU(Electronic Control Unit)定義及報(bào)文、信號(hào)等層面詳細(xì)進(jìn)行網(wǎng)絡(luò)分析規(guī)劃。整個(gè)網(wǎng)絡(luò)由以下4個(gè)可選用CAN FD總線傳輸?shù)腅CU組成[23]，總計(jì)傳輸15個(gè)報(bào)文，具體為：(1)用于控制車載3個(gè)電池狀態(tài)的BCM(Battery Control Management)ECU，共計(jì)收發(fā)3個(gè)報(bào)文；(2)用于實(shí)現(xiàn)數(shù)據(jù)在儀表盤上顯示傳送發(fā)動(dòng)機(jī)速度、狀態(tài)、溫度及油耗的電機(jī)狀態(tài)的IPC(Instrument Panel Cluster)ECU，共計(jì)收發(fā)4個(gè)報(bào)文；(3)用于控制車兩側(cè)的前后車門、車速、和車燈狀態(tài)的Gateway ECU，共計(jì)收發(fā)6個(gè)報(bào)文；(4)用于收發(fā)點(diǎn)火與熄火的開關(guān)Switch ECU，共計(jì)收發(fā)2個(gè)報(bào)文。網(wǎng)絡(luò)設(shè)計(jì)規(guī)劃如圖4，節(jié)點(diǎn)報(bào)文分配見表1。

表1 報(bào)文分配

圖4 CAN FD網(wǎng)絡(luò)規(guī)劃設(shè)計(jì)Figure 4. CAN FD network planning and design

3.2 仿真實(shí)驗(yàn)設(shè)計(jì)

按照?qǐng)D4網(wǎng)絡(luò)規(guī)劃將信號(hào)加入數(shù)據(jù)庫(kù)并搭建CANoe仿真實(shí)驗(yàn)平臺(tái)，電機(jī)狀態(tài)(儀表)ECU和Switch ECU所產(chǎn)生的報(bào)文設(shè)置為非周期性報(bào)文，而網(wǎng)關(guān)ECU和車身ECU均為周期性報(bào)文。電池狀態(tài)報(bào)文周期為400 ms，車門狀態(tài)相關(guān)報(bào)文及車速、車燈報(bào)文周期設(shè)置為500 ms，電機(jī)轉(zhuǎn)速及溫度與狀態(tài)報(bào)文周期為1 000 ms。周期性報(bào)文傳輸時(shí)間設(shè)定為0.115 ms，非周期性報(bào)文為0.08 ms。設(shè)置報(bào)文釋放時(shí)間為零，即假定報(bào)文的相對(duì)截止時(shí)間與其周期相等，按照指數(shù)-冪函數(shù)分區(qū)方式進(jìn)行編碼，并根據(jù)報(bào)文的初始相對(duì)截止時(shí)間計(jì)算報(bào)文的起始ID，具體參數(shù)設(shè)定如表2所示。

表2 報(bào)文及參數(shù)設(shè)定

3.3 結(jié)果及分析

為驗(yàn)證本文提出的方法的調(diào)度效果，分別對(duì)采用平均分區(qū)和指數(shù)-冪函數(shù)分區(qū)的EDF算法進(jìn)行仿真實(shí)驗(yàn)。首先進(jìn)行可調(diào)度判定，任意截取一段報(bào)文傳輸?shù)木唧w數(shù)據(jù)如表3所示。表中第4列為報(bào)文的周期Ti，其最小值為400 ms；第5列為計(jì)算的報(bào)文傳輸時(shí)間，即式(2)中的Ci，本文此處以t=2.0 s時(shí)刻具體舉例說(shuō)明。

表3 t=2.0 s時(shí)傳輸報(bào)文的具體數(shù)據(jù)

對(duì)表3中截取t=2.0 s傳輸?shù)膱?bào)文數(shù)據(jù)按照定理2進(jìn)行可調(diào)度性判定，即將所有Tm、Cm、dm、Cp數(shù)據(jù)帶入式(2)進(jìn)行計(jì)算。其中，最長(zhǎng)傳輸阻塞時(shí)間Cp= 0.109 ms，則有

(20)

經(jīng)過(guò)上式計(jì)算，滿足定理2對(duì)于可調(diào)度性的判定，即傳輸?shù)膱?bào)文集是可調(diào)度的。

驗(yàn)證可調(diào)度后，采用該組報(bào)文集進(jìn)行實(shí)驗(yàn)。為了對(duì)比實(shí)驗(yàn)，選定的報(bào)文傳輸速率分別為4 Mbit·s-1、8 Mbit·s-1，其中4 Mbit·s-1的波特率是Vector推薦的CAN FD的最佳傳輸速率。兩種分區(qū)方式下的調(diào)度結(jié)果如圖5和圖6所示。

(a)

(c)

根據(jù)仿真實(shí)驗(yàn)結(jié)果計(jì)算在不同波特率下各自的總線負(fù)載可得：(1)采用傳輸速率為4 Mbit·s-1下的指數(shù)-冪函數(shù)編碼的總線負(fù)載為0.28%，而平均分區(qū)的總線負(fù)載為0.49%；(2)當(dāng)傳輸速率為8 Mbit·s-1時(shí)，兩者各自的總線負(fù)載分別為0.25%和0.43%。經(jīng)計(jì)算，采用本文提出的指數(shù)-冪函數(shù)編碼方法進(jìn)行調(diào)度時(shí)，總線負(fù)載分別降低了42.90%和46.50%，表明本文對(duì)EDF算法的改進(jìn)是可行的。此外，在傳輸速率為4 Mbit·s-1的仿真實(shí)驗(yàn)過(guò)程中，報(bào)文被阻塞的最大時(shí)間為1.317 ms，最大誤差為31.25%。根據(jù)引理1可得

(21)

上式計(jì)算驗(yàn)證了系統(tǒng)是可調(diào)度的，這與仿真實(shí)驗(yàn)結(jié)果及定理2的判定結(jié)果一致。

4 結(jié)束語(yǔ)

本文在研究平均分區(qū)EDF調(diào)度算法的基礎(chǔ)上，提出了使用指數(shù)-冪函數(shù)的分區(qū)編碼方式改進(jìn)EDF算法。經(jīng)過(guò)仿真實(shí)驗(yàn)，驗(yàn)證了改進(jìn)后的算法通過(guò)劃分不同的母區(qū)間與子區(qū)間，使截止期各不相同的報(bào)文都能處在正確的區(qū)間內(nèi)，不僅可以優(yōu)化之前會(huì)出現(xiàn)的優(yōu)先級(jí)反轉(zhuǎn)問題，還能夠有效降低總線負(fù)載。但是本文的不足之處在于，對(duì)報(bào)文調(diào)度進(jìn)行的研究是假設(shè)系統(tǒng)處于一種理想狀況，忽略了報(bào)文傳輸延遲、釋放抖動(dòng)以及傳輸時(shí)可能出錯(cuò)的情況，從而存在一定誤差。日后可針對(duì)這種不足做出改進(jìn)，并可以搭建硬件節(jié)點(diǎn)進(jìn)行實(shí)物驗(yàn)證。