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

版塊 |鑒源論壇 · 觀模

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

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

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

01AUTOSAR OS任務和調度表

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

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

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

?行為：激活任務或者是設置事件，一個終結點至少包含一個行為。當終結點被處理時，其包含的行為將被執(zhí)行。

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

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

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

圖1 調度表結構

02調度表的形式化模型

2.1 任務模型

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

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

（2）截止時間，即任務的最壞情況響應時間應當少于的時間；

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

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

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

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

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

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

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

2.2 調度表的形式化模型

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

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

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

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

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

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

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

03調度表可調度性分析

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

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

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

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

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

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

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

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

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

（1）將調度表集合中所有的任務組成一個任務集合t= T1,T2, . . . ,Tq，然后進入第二步。

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

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

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

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

圖2 調度表可調度算法

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

04小結

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

審核編輯：湯梓紅