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

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

版塊 |鑒源論壇 · 觀模

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 任務(wù)模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

04小結(jié)

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

審核編輯：湯梓紅