作者 |郭建上海控安可信軟件創新研究院特聘專家

版塊 |鑒源論壇 · 觀模

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

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

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

01AUTOSAR OS任務和調度表

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

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

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

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

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

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

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

圖1 調度表結構

02調度表的形式化模型

2.1 任務模型

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

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

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

（3）優先級，數字越小說明優先級越高。

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

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

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

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

● PT∈ N+ 代表了這個任務的優先級。

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

2.2 調度表的形式化模型

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

定義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+ ，表示兩個終結點偏移量之差，即它們被處理時間之間的延遲。

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

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

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

03調度表可調度性分析

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

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

● 第二部分是作業激活之后，本地調度表激活的高優先級作業的執行時間。

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

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

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

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

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

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

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

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

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

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

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

圖2 調度表可調度算法

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

04小結

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

審核編輯：湯梓紅