AUTOSAR調(diào)度表可調(diào)度性的形式化分析

作者 |郭建上?？匕部尚跑浖?chuàng)新研究院特聘專家

版塊 |鑒源論壇 · 觀模

汽車上大量軟件和電子控制單元（ECU,Electronic Control Unit）的使用導(dǎo)致了汽車電子架構(gòu)變得更為復(fù)雜，現(xiàn)如今從工廠生產(chǎn)的汽車更像是帶輪子的電腦?，F(xiàn)代汽車由大約50到上百個電子控制單元組成，而且每年的數(shù)量還在增加。每個電子控制單元負(fù)責(zé)特定的功能，它們之間通過某種總線相互通信，例如CAN、FlexRay、LIN等。每多一個連接到系統(tǒng)上的電子控制單元，系統(tǒng)的復(fù)雜性都會增加。汽車電子系統(tǒng)都必須配置對應(yīng)的應(yīng)用程序和軟件，而每次新硬件出現(xiàn)時，應(yīng)用程序都需要被重寫來支持硬件的更新。

為了應(yīng)對這種令汽車電子系統(tǒng)軟件難以管理的局面，德國汽車工業(yè)界共同提出了一個開放的標(biāo)準(zhǔn)接口OSEK/VDX。2003年，幾個在汽車領(lǐng)域領(lǐng)先的原始設(shè)備制造商和汽車行業(yè)的一級供應(yīng)商決定為了未來汽車電子的發(fā)展，共同在OSEK/VDX的基礎(chǔ)上制定一個新標(biāo)準(zhǔn)，而這個標(biāo)準(zhǔn)就是AUTOSAR（AUTomotive Open System ARchitecture）。其旨在成為行業(yè)內(nèi)的共享軟件架構(gòu)框架，而背后的原因是汽車電子系統(tǒng)復(fù)雜性的增加。AUTOSAR標(biāo)準(zhǔn)的產(chǎn)生可以通過提供一個各方共同認(rèn)可的架構(gòu)來允許制造商在功能而非架構(gòu)上展開競爭。共享同一個架構(gòu)的好處包括制造商和軟件公司可以開發(fā)適合汽車市場的通用軟件，提高汽車電子系統(tǒng)的靈活性、可擴(kuò)展性和質(zhì)量。

作為車載操作系統(tǒng)，實(shí)時性對于AUTOSAR OS的重要性不言而喻，如何保證操作系統(tǒng)中的計算單元在截止時間內(nèi)完成是極其重要的。而AUTOSAR OS提供的調(diào)度表機(jī)制是系統(tǒng)中一個重要的任務(wù)激活機(jī)制。調(diào)度表通過包含一組封裝了動作和偏移量的終結(jié)點(diǎn)來設(shè)定任務(wù)的激活方式。由于調(diào)度表機(jī)制的特殊性，任務(wù)的調(diào)度情況變得更加復(fù)雜，這使得調(diào)度表的可調(diào)度性非常重要。本文將針對AUTOSAR OS調(diào)度表進(jìn)行可調(diào)度性分析。

01AUTOSAR OS任務(wù)和調(diào)度表

任務(wù)是AUTOSAR OS中的一個重要概念，被看作是操作系統(tǒng)中最小的調(diào)度單位，也是最基本的功能單位，即使是最簡單的應(yīng)用也需要至少一個任務(wù)來完成它的功能。AUTOSAR OS中提供了兩種任務(wù)：基本任務(wù)和擴(kuò)展任務(wù)。

AUTOSAR OS 中使用靜態(tài)優(yōu)先級調(diào)度策略，不論是基本任務(wù)還是擴(kuò)展任務(wù)都被靜態(tài)地分配到一個優(yōu)先級，并且為了保證系統(tǒng)的運(yùn)行效率，任務(wù)的優(yōu)先級是在系統(tǒng)設(shè)計階段被靜態(tài)配置的，不允許在系統(tǒng)運(yùn)行時更改。因?yàn)锳UTOSAR OS允許多個任務(wù)共享同一個優(yōu)先級，在AUTOSAR OS中為每一個優(yōu)先級維持一個隊(duì)列，相同優(yōu)先級的任務(wù)采用先來先服務(wù)的調(diào)度方法。

調(diào)度表是AUTOSAR OS中新引入的一種調(diào)度機(jī)制，它是對OSEK/VDX OS中使用定時器激活周期性任務(wù)的一種改進(jìn)。調(diào)度表通過將一組任務(wù)靜態(tài)地封裝到終結(jié)點(diǎn)中，讓有關(guān)聯(lián)的任務(wù)按照規(guī)定的時間和順序激活。其中一個終結(jié)點(diǎn)封裝了：

?行為：激活任務(wù)或者是設(shè)置事件，一個終結(jié)點(diǎn)至少包含一個行為。當(dāng)終結(jié)點(diǎn)被處理時，其包含的行為將被執(zhí)行。

?偏移量：在一個調(diào)度表中，每個終結(jié)點(diǎn)都有一個唯一的偏移量，這個偏移量是一個相對時間，標(biāo)示終結(jié)點(diǎn)與調(diào)度表起點(diǎn)的距離。各個終結(jié)點(diǎn)偏移量之差代表了終結(jié)點(diǎn)被處理時間之間的的延遲。調(diào)度表中第一個終結(jié)點(diǎn)的偏移量被稱作此調(diào)度表的初始偏移量，最后一個終結(jié)點(diǎn)的偏移量到調(diào)度表結(jié)束的時間差被稱為最終延遲。

每個調(diào)度表都有一個持續(xù)時間表示它完全運(yùn)行一次需要的時間。在調(diào)度表啟動后，AUTOSAR OS會使用一個迭代器遍歷調(diào)度表，并按照偏移量遞增的順序依次處理每個終結(jié)點(diǎn)。AUTOSAR OS中定義了兩種調(diào)度表：周期性和非周期性調(diào)度表。如果一個調(diào)度表被配置為非周期性的，當(dāng)最后一個終結(jié)點(diǎn)被處理之后，AUTOSAR OS會停止遍歷此調(diào)度表。而當(dāng)周期性調(diào)度表的最后一個終結(jié)點(diǎn)被處理，經(jīng)過最終延遲之后，AUTOSAR OS會從調(diào)度表的開始處再次遍歷。

圖1展示了一個周期性調(diào)度表的實(shí)例。在這個調(diào)度表中共包含三個終結(jié)點(diǎn)，持續(xù)時間為17。

圖1 調(diào)度表結(jié)構(gòu)

02調(diào)度表的形式化模型

2.1 任務(wù)模型

作為比調(diào)度表更小的調(diào)度單位，在對調(diào)度表建立模型之前，首先需要對任務(wù)進(jìn)行合理的抽象，并建立任務(wù)模型。AUTOSAR OS中的任務(wù)被抽象為三個屬性：

（1）最壞情況執(zhí)行時間，即處理器執(zhí)行這段代碼最長的用時；

（2）截止時間，即任務(wù)的最壞情況響應(yīng)時間應(yīng)當(dāng)少于的時間；

（3）優(yōu)先級，數(shù)字越小說明優(yōu)先級越高。

綜上，描述AUTOSAR OS中任務(wù)的模型被定義如下：

定義1：一個任務(wù)是一個三元組 T=(CT, DT, PT)，其中：

● CT∈ N+任務(wù)的最壞執(zhí)行時間，下文簡稱執(zhí)行時間；

● DT∈ N+代表了這個任務(wù)的截止時間；

● PT∈ N+ 代表了這個任務(wù)的優(yōu)先級。

任務(wù)模型隱含地假設(shè)對所有任務(wù)T都滿足CT≤ DT ，因?yàn)榭烧{(diào)度性要求系統(tǒng)中所有任務(wù)都能夠在截止時間之內(nèi)完成計算。如果一個任務(wù)的執(zhí)行時間超出了它的截止時間，那么它將永遠(yuǎn)無法滿足時間特性需求，也就無法進(jìn)行可調(diào)度性分析。

2.2 調(diào)度表的形式化模型

AUTOSAR OS中的調(diào)度表提供了新的任務(wù)激活模式，一個調(diào)度表中各個任務(wù)的激活時間存在關(guān)聯(lián)：同一個終結(jié)點(diǎn)上的任務(wù)都會被同時激活，對于不同終結(jié)點(diǎn)上的任務(wù)，它們的激活時間之間存在固定延遲。雖然周期性調(diào)度表使其中的任務(wù)以周期性激活，但調(diào)度表模型應(yīng)當(dāng)能夠描述出任務(wù)激活時間之間的關(guān)系。這里給出了基于有向圖的模型來描述調(diào)度表的時間特性與行為，其定義如下：

定義2：一個調(diào)度表ST由一個有向圖G(ST)= (V (ST),E(ST)) 表示。其中V (ST) 是有向圖中頂點(diǎn)的集合，E(ST) 是頂點(diǎn)之間的邊的集合：

● V (ST) = {ep1, . . . ,epn}，表示調(diào)度表中所有終結(jié)點(diǎn)組成的集合，其中的一個終結(jié)點(diǎn)ep = {T1, . . . ,Tk}是一個集合，包含了終結(jié)點(diǎn)封裝的所有任務(wù)；

● G(ST) 中邊的指向表示了調(diào)度表中終結(jié)點(diǎn)被處理的順序。每一條邊(epu,epv ) ∈E(ST) 都有一個權(quán)值p(epu,epv )∈ N+ ，表示兩個終結(jié)點(diǎn)偏移量之差，即它們被處理時間之間的延遲。

在這個模型中，并沒有標(biāo)示第一個終結(jié)點(diǎn)和最后一個終結(jié)點(diǎn)。當(dāng)調(diào)度表是周期性的時候，最后一個終結(jié)點(diǎn)被處理后再經(jīng)過最終延遲加初始偏移量，調(diào)度表的第一個終結(jié)點(diǎn)會被再次處理。所以可以將最后一個終結(jié)點(diǎn)到第一個終結(jié)點(diǎn)之間的延遲看作是最終延遲與初始偏移量的和。在調(diào)度表模型中，每個ep ∈ V (ST) 都不是空集。為空集的ep對系統(tǒng)的運(yùn)行來說沒有任何用處，通過簡單的轉(zhuǎn)換就可以消除它們。

AUTOSAR OS中，多個任務(wù)可以共享同一個優(yōu)先級，所以當(dāng)多個相同優(yōu)先級的任務(wù)爭用處理器時，它們激活時間的不同導(dǎo)致了調(diào)度情況的不同。而定義的任務(wù)模型并不包括激活時間的屬性。為了將AUTOSAR OS任務(wù)的激活時間屬性表示出來定義了作業(yè)的概念。

定義3：作業(yè)表示一個任務(wù)在某個時間點(diǎn)被激活產(chǎn)生的實(shí)例。一個作業(yè)J=(CJ ,DJ ,PJ ,RJ ) 由一個四元組表示，除了與任務(wù)同樣使用CJ 、DJ 和PJ 來表示這個作業(yè)的執(zhí)行時間、截止時間以及優(yōu)先級之外，還使用了RJ∈ N+ 來表示這個作業(yè)被激活的時間。一個作業(yè)就代表著一個任務(wù)被激活一次。

03調(diào)度表可調(diào)度性分析

AUTOSAR OS調(diào)度表中一個作業(yè)被阻塞和搶占的時間可以分為三個部分：

● 第一部分是在作業(yè)激活之前，本地調(diào)度表激活的高優(yōu)先級或相等優(yōu)先級作業(yè)的執(zhí)行時間。

● 第二部分是作業(yè)激活之后，本地調(diào)度表激活的高優(yōu)先級作業(yè)的執(zhí)行時間。

● 第三部分是其他調(diào)度表激活的優(yōu)先級更高或優(yōu)先級相同，但激活時間更早作業(yè)的執(zhí)行時間。

它們分別對應(yīng)前綴需求函數(shù)、需求函數(shù)和最大需求函數(shù)的計算，用這種方法計算出的第一部分與第二部分之間有重疊，它們都包含了作業(yè)J所在終結(jié)點(diǎn)實(shí)例P(J)對作業(yè)J的影響值，需要減去這部分的重疊時間，就得到作業(yè)J被阻塞和搶占的時間。

除了使用需求函數(shù)、最大需求函數(shù)以及前綴需求函數(shù)外，還引入了忙碌窗口的概念。

對于一個優(yōu)先級P，P的忙碌窗口是一個時間段。在這個時間段中處理器持續(xù)地執(zhí)行優(yōu)先級高于或等于P的作業(yè)。即在這個時間段內(nèi)處理器不會執(zhí)行優(yōu)先級小于P的作業(yè)，也不會空閑。

最長的忙碌窗口并不一定能導(dǎo)致作業(yè)的響應(yīng)時間最長，而且也很難預(yù)測導(dǎo)致最壞情況響應(yīng)時間出現(xiàn)時忙碌窗口的確切大小。但是通過這個忙碌窗口長度的上限，可以列舉所有忙碌窗口大小的可能性。所以為了計算任務(wù)最壞情況響應(yīng)時間，遍歷所有忙碌窗口的大小直到上限，就可以得到此任務(wù)的可調(diào)度性。

對于AUTOSAR OS，其調(diào)度表集合T= {ST1,ST2, . . .STn}，分析AUTOSAR OS可調(diào)度性的完整的方法可以被分為以下四步:

（1）將調(diào)度表集合中所有的任務(wù)組成一個任務(wù)集合t= T1,T2, . . . ,Tq，然后進(jìn)入第二步。

（2）如果任務(wù)集合t為空，則此AUTOSAR OS 就是可調(diào)度的；如果不為空，任意選中t中一個任務(wù)Tk（k ∈[1,q]），然后進(jìn)入第三步。

（3）使用任務(wù)的前綴需求函數(shù)、需求函數(shù)、最大需求函數(shù)和忙碌窗口的分析，得出該人的可調(diào)度性，如果Tk 是不可調(diào)度的，那么此AUTOSAR OS 就是不可調(diào)度的；如果Tk 是可調(diào)度的，進(jìn)入第四步。

（4）更新任務(wù)集合t=t-Tk，然后再回到第二步。

上述步驟描述的AUTOSAR OS可調(diào)度性分析方法如圖2所示：

圖2 調(diào)度表可調(diào)度算法

算法SCHEDULABILITY (t) 的目的是找出AUTOSAR OS中一個不可調(diào)度的任務(wù)并聲明這個系統(tǒng)是不可調(diào)度的，或者當(dāng)系統(tǒng)中的所有任務(wù)都可調(diào)度時，聲明是可調(diào)度的。它的初始輸入是AUTOSAR OS中所有任務(wù)的集合t，輸出為真時說明系統(tǒng)是可調(diào)度的，輸出為假時說明系統(tǒng)是不可調(diào)度的。其中第一到四行對應(yīng)著步驟2，判斷任務(wù)集合為空并聲明系統(tǒng)可調(diào)度，或者在任務(wù)集合中任取一個任務(wù)。第五到十行對應(yīng)步驟3和步驟4，其中第五行使用算法TASK_ANALY SIS(T)檢查任務(wù)是否是可調(diào)度的，如果是可調(diào)度的，那么就在t中將該任務(wù)刪除，然后迭代執(zhí)行此算法；如果取到的任務(wù)不可調(diào)度，就直接聲明這個AUTOSAR OS是不可調(diào)度的。

04小結(jié)

本文研究了AUTOSAR OS中的任務(wù)、調(diào)度表機(jī)制，并使用了一個基于有向圖的模型描述AUTOSAR OS中調(diào)度表的時間特性及行為，繼而提出適用于AUTOSAR OS的可調(diào)度性分析方法。通過將路徑抽象成運(yùn)行時間，提出需求函數(shù)、最大需求函數(shù)以及前綴需求函數(shù)來分析作業(yè)被搶占和阻塞的時間，提出了針對AUTOSAR OS調(diào)度表的可調(diào)度性分析方法。

審核編輯：湯梓紅