基于時間觸發機制的實時通信架構研究與設計

蔣笑寒，李 牧，孫思杰，馮逸駿

(1.北京航空航天大學 中法工程師學院，北京 100191；2.北京工業大學 樊恭烋學院，北京 100124；3.北京航空航天大學 宇航學院，北京 100191)

0 引 言

信息-物理系統(cyber physical systems，CPS)[1]是集成計算、通信與控制于一體的下一代智能系統，目前已廣泛應用于各個安全攸關領域(safety-critical)，為提升智能系統的計算能力、安全性以及可靠性，亟需建立一套能夠用于CPS系統的單節點多核心分布式實時操作系統。

時間觸發理論作為一種高確定性的實時理論，已經在安全攸關領域[2,3]有了多年的應用。Pont MJ提出時間觸發原理；Hermann Kopetz等設計了時間觸發架構，并提出了時間觸發協議TTP(time-triggered protocol)；Yan[4]基于傳統TTP協議設計了C類時間觸發協議TTP/C。在傳統分布式實時操作系統領域，Kane Kim提出了基于NT和Linux的時間觸發支持的操作系統架構；Giotto把時間觸發架構提升到了編程語言的層面。此后，有關時間觸發架構的研究大量涌現[5,6]。隨著單機內計算核心數目的增多，傳統操作系統會產生嚴重的性能下降，針對此，Andrew Baumann和Paul Barham等提出了Multikernel架構。Barrelfish作為開源的Multikernel操作系統，為分布式的多核異構系統提供了更高效的操作系統基礎設施。

本文將時間觸發架構的設計思想應用于以Barrelfish為代表的Multikernel系統中，依靠SMT[7]理論，對Barrelfish的消息進行建模，從而生成滿足所有約束的消息調度表，設計和實現時間觸發的任務調度模型、系統通信服務以及配套的時間觸發任務和通信的配置管理工具，形成可用的Multikernel架構分布式硬實時系統。

1 基于Barrelfish的時間觸發實時通信框架設計

基于Barrelfish的時間觸發通信框架主要包含運行時和離線兩部分，其中，運行時部分的架構如圖1所示。運行時部分負責支撐Barrelfish在部署及啟動后的時間觸發實時消息通信。圖1中描述了兩個通過實時交換機相連的SoC節點，每個SoC節點共有兩塊通過TTNoC相連的多核CPU。每個多核CPU上需要抽調出一個單獨的核心以運行時間觸發實時消息服務，該消息服務是一個CPU上所有應用程序與其它CPU上的應用進行通信的網關[8]。此外，一些實時應用有并行多線程的需要，而Barrelfish本身并不支持同一個進程中的線程在多個CPU核心上運行，缺乏這種并行特性會導致一些消息無法及時生成，使得整個系統不可調度，因此，該運行時還包含有一個以Group為核心組件的動態SMP(symmetrical multi-processing)子系統。

圖1 時間觸發通信框架-運行時部分

消息服務是整個系統運行時的基礎設施。該消息服務在系統啟動時負責讓系統到達一致狀態，在系統運行期間，解析時間觸發消息調度表，提供消息在SoC內部或跨SoC的消息轉發功能，并以API的形式為時間觸發實時應用程序提供通信接口。此外，消息服務不僅需要在系統運行期間進行各個節點時間的同步，還需要維護各個節點的組籍狀態，在節點失效時，利用冗余備份機制恢復系統的可用性。以Group為核心的動態SMP子系統可以在運行時動態地改變某一系統分區的計算能力，提高此分區的多核并行計算能力，防止過多的分區和單核有限的計算能力對系統的可調度性產生影響。

基于Barrelfish的時間觸發通信框架的離線部分包含一個時間觸發消息調度器，在對整個時間觸發系統完成設計，得到應用程序的消息規范之后，調度器可以根據硬件網絡約束和應用程序約束得到一組滿足系統整體約束的消息調度表。該消息調度表規定了在何時有什么消息從何發送節點發送到哪些接收節點。運行時中的消息服務會解析該調度表，并依據全局時間基，在調度表規定的時間槽執行相應的消息轉發動作。圖2展示了基于Barrelfish的時間觸發通信框架的離線和運行時部分的關系。

圖2 時間觸發通信框架-離線和運行時部分的關系

下面分別從消息服務、動態SMP子系統和時間觸發消息調度器等3個方面展開敘述。

1.1 消息服務設計

針對時間觸發的實時消息通信，本文設計了一套稱之為MDL(message description list)的領域特定的調度表格式。靜態消息調度器負責生成MDL，消息服務通過解析MDL語句，按照MDL描述的調度時機和要采取的動作進行消息的調度。消息調度器在解析MDL的過程中，會保證數據幀的完整性和正確性，同時也會保證數據傳輸的時序正確。

MDL通過全局時間基給出的時間槽為最小時隙單位。MDL設計了一種多等級的結構：最上層為集群描述符，一個集群描述符可以包含多個節點描述符，一個節點描述符又由多個時隙描述符組成。為了保證MDL語言的二進制兼容性，MDL在所有架構上都采用小端模式儲存。

為了簡化基本消息服務的設計，保證整個系統的一致性，無論是SoC內部還是SoC間的消息傳輸皆使用同一套數據幀格式。本節所采用的數據幀格式由幀頭和數據體構成，其結構如圖3所示。

圖3 實時消息幀格式

幀頭主要包含協議相關的語義屬性，數據校驗位等。數據幀的類型由幀頭中的相關位確定。數據幀一共有兩種類型：一種稱為普通幀，搭載用戶數據的幀屬于此種類型；第二種幀稱為節點控制幀，用于節點間維護在線關系，同步時鐘等；此外，幀頭中還包括校驗位，為了減少校驗算法帶來的額外開銷，本框架采用CRC校驗法作為消息完整性的檢查算法。

1.2 動態SMP子系統設計

Barrelfish無法利用多核并行能力的原因是其CPU Driver與CPU Core的對應關系高度耦合，在目前的實現中，CPU Driver與CPU Core為多對一關系。SpaceJMP[9]提出把虛擬地址空間當作操作系統的一種頭等對象，允許一個進程可以在多個地址空間中快速切換，從而實現共享大段內存的目的。這種編程模型可以模擬出傳統的Unix線程，但是由于添加了特殊的編程語言，需要特殊的編譯器。頻繁的切換地址空間對TLB和Cache都不友好，軟硬件兼容性方面都不是非常優秀。我們可以通過設計一種新的消息傳遞基礎設施，開發了一種基于任務派生—合并的并行任務模型(類似于MapReduce算法)，但由于涉及了大量小任務的遷移、調度和同步，這種編程框架本身會產生較大的消息通信開銷和同步等待的開銷，此外，該編程模型只適用于解決分治算法，無法使用常規并行多線程算法。

為了解決這個問題，本文設計了一個稱為Group的核心系統組件，其架構如圖4所示。

圖4 Barrelfish的Group架構

為了減少對已有服務程序的更改，需要考慮到現有的服務程序都以線程不安全的方式實現，無法并行執行多線程，因此需要提供一種機制，在執行線程不安全的服務程序時，禁用并行的特性，只允許一個CPU Core串行的執行程序。本文采用如下方案解決這個問題。當Group中包含多個Core時，選取其中一個核心為主核心，負責Group的合并和拆分以及系統進程的運行；其它的Core則成為成員核心，負責運行其它的進程。主核心不可以脫離當前Group，成員核心則可以自由地附著到其它的核心。

1.3 時間觸發消息調度器設計

本文定義了一個時間觸發實時網絡中的所有約束條件。為了簡化約束的書寫，本節做了如下假定：

(1)整個集群的超周期被劃分為長度相等的時間片，該時間片的長度為全局時間基的時間粒度的整數倍，稱之為集群超周期。超周期的值可用所有幀的周期的最小公倍數計算得到。

(2)每個節點在發送或者中繼消息時，發送一個數據幀只占用一個時間槽。

(3)對于同一個應用發送的消息，將以相同的路徑到達接收者。

在此基礎上，可以對約束條件進行簡化的表示。本文把約束條件分為硬件約束條件和軟件約束條件兩類進行描述：

(1)硬件約束條件

硬件約束條件中最基礎的是發送端口獨占約束，即無競爭約束。該條件意味著一個發送節點或者一個中繼節點只有在前一條數據幀完全發送完畢之后，才可以開始發送下一條數據幀。

(2)軟件約束條件

端到端消息傳輸約束描述了應用程序要求的數據幀端到端傳輸的最大時延，該最大延遲必須小于應用發送幀的周期。對于多播傳輸，假設所有的接收者都具有相同的端到端傳輸時延要求。

求解最優數據虛鏈路時，本文采用以下目標函數

(1)

該目標函數要求整個系統調度數據幀的最大延遲最小，最大數據幀延遲越小，總體延遲越小，系統利用率越高。

最優解算法在面對較大規模數據集時，無法在可以接受的時間內得到一個解[10]，因此本文不采用最優解算法，而是使用目前比較成熟的近似算法(如Wang[11]、Lee[12]等)，在多項式時間內，求出該問題的近似最優解。

2 基于Barrelfish的時間觸發實時通信框架實現

2.1 消息服務實現

時間觸發實時通信框架提供的消息服務API接口見表1。

表1 Barrelfish實時通信框架操作接口

其中，最核心的功能是消息收發接口，時間觸發的實時應用程序可以調用這兩個接口進行消息的收發。當發送消息時，調用該接口后，應用程序將要發送的消息數據會被復制到相應消息通道的緩沖區內，當調度表規定的消息傳輸時刻到來時，消息服務會把該消息從緩沖區中取出，并復制到目標緩沖區中。當接收消息時，調用該接口后，會根據調度表的時刻，等待到消息到來的時刻。在此期間，消息服務會把要接收的消息從發送者的緩沖區復制到接收者消息通道緩沖區內，當時刻到來后，該接口會將消息從消息通道中復制到應用程序的數據緩沖區，供應用程序使用，然后喚醒應用程序進行后續的計算操作。

2.2 動態SMP子系統實現

系統的實現主要可分為兩部分，一方面是對CPU Dri-ver 的更改，將CPU Driver對CPU Core的依賴，更改為對Group的依賴，并將CPU Driver修改為線程安全的實現。另一方面是對libbarrelfish的更改。libbarrelfish把各個系統服務提供的各項功能整合到了一起，封裝成為易用的API，應用程序借助該庫能獲得完備的操作系統功能。

(1)針對CPU Driver的SMP實現

CPU Driver中的數據段，根據數據使用者的不同，可分為兩類。一類數據代表了CPU Core的狀態，另一類數據則代表了該CPU Driver本身的狀態。

對于前者，代表CPU Core狀態的數據由Group組件統一管理，Group組件會將這些數據項復制多份，保證每個核心都有相對應的唯一的數據，并由Group組件為CPU Driver提供相關的讀取、寫入接口。

對于后者，考慮到需要保護的關鍵代碼段通常不是很大，可以使用自旋鎖對這部分數據進行保護。在多核并行場景下，自旋鎖可以保證核間臨界資源的正確性[13]。自旋鎖與互斥鎖、信號量類似，只是自旋鎖不會引起調用者阻塞。如果自旋鎖已經被其它執行體占有，調用者就一直循環檢測自旋鎖是否被釋放，是否處于空閑狀態，這個循環過程就是自旋。自旋鎖的占有時間非常短，因此調用者不被阻塞而在那自旋，比上下文切換節省時間開銷，效率遠高于互斥鎖、信號量。但普通自旋鎖具有隨機占有的特性，這帶來了調度上的不公平。為了避免這個不公平問題，本文使用了被稱為輪轉自旋鎖的技術，與普通自旋鎖的隨機占有鎖的方式不同，每個核心采用排隊的方式獲取自旋鎖，這樣每個CPU核心都有相同的概率獲得鎖的使用權。

(2)針對libbarrelfish的SMP實現

本文采用一種稱為代理執行的方法來解決libbarrelfish中存在的數據競爭問題。這種方法的核心在于，在一個Group中，只允許主核心執行Disabled狀態的Dispatcher。成員核心只允許執行用戶創建的線程的代碼和線程調度器。當成員核心上的線程需要切換到Disabled狀態時，會首先將線程遷移到主核心上，其中，線程的遷移可以利用線程對處理器核心的親和性來完成。

另一個需要改動的點是Barrelfish的消息機制，Barrelfish系統中的LMP消息是基于Upcall實現的，UMP消息則是通過輪詢實現。為了避免在消息處理相關的代碼中產生數據競爭，新的消息機制只允許Group內的主核心執行相關的代碼，負責所有消息的轉發和輪詢。

2.3 時間觸發消息調度器實現

本文設計了兩種實時調度器，一種是基礎時間觸發實時消息調度器，另一種是增量時間觸發實時消息調度器。SMT求解器選用微軟的開源求解器Z3，并使用它提供的Python API進行編寫。增量時間觸發實時消息調度器會在兩個求解階段間多次切換，并使用Z3提供的回溯功能。

(1)基礎時間觸發實時消息調度器實現

基礎求解器的實現較為簡單，在基礎求解器中，會首先把所有數據幀的約束條件添加到SMT求解器上下文中，然后調用SMT求解器的求解函數，SMT求解器會首先檢查這些約束條件是否具有一致性，若滿足一致性，便可以計算得到本組約束的解。這組解可以通過SMT求解器提供的API函數得到。

(2)增量時間觸發實時消息調度器實現

由于SMT求解器對一次求解的約束條件數目有所限制，當約束規模較大時，無法將全部約束一次性全部添加到求解器中。為了解決這個問題，本文設計的增量調度器不會一次性生成全部的約束條件，而是逐次地將約束條件的子集加入到SMT求解器中并進行多次求解。在每次子集的求解完成之后，會按照這一部分的求解結果，把數據幀的偏移固定下來，作為下一次求解的約束輸入。這樣的方案可能會導致求解器在中間某次求解過程中返回失敗，對于錯誤的處理，本文采用回溯的方法，逐步增大之前的約束子集的數目。當SMT求解器無法在規定的時間內得到一組解，或是約束子集的數目超過了預先設定的閾值，則認為調度失敗。

增量調度算法開始時，首先生成這一數據幀范圍內的約束，并檢查是否存在針對這一部分的可行解。若存在可行解，則從求解器中獲取解，并把這些解保存到本地變量中，作為新的常量約束并用于下一輪的約束。最后，把輸入的幀集合更新為下一輪的集合。

在最壞情況下，回溯過程有可能回溯到數據幀序列的第一幀。在這種情況下，增量調度器等價于基礎調度器。當調度器沒有能在合理時間內得到解時，便會終止求解算法，回溯到前面得到部分解的步驟，并返回當前已經得到的時間表。調度算法求解的中斷可采用封裝好的信號中斷函數。

至此，基于Barrelfish的時間觸發實時通信框架的設計與實現已經完成。

3 基于Barrelfish的時間觸發實時通信框架實驗結果與分析

本文先分別針對如下3個部分做了驗證和測試：消息通信服務的正確性及其功能實現的完整性、時間觸發通信消息調度算法及調度器的正確性、Barrelfish的動態SMP子系統的性能，最后對整個框架進行綜合測試。

為了對通信框架和動態SMP子系統兩部分的結果進行驗證，本文采用了軟件模擬和真實硬件兩套環境開展實驗。其中，軟件模擬部分使用QEMU，硬件部分使用NVIDIA Jetson TK1作為實驗平臺。兩者皆以ARM為計算平臺架構。具體的硬件參數見表2。

表2 實驗平臺硬件參數

對于調度算法的驗證，本文首先通過一定規則生成了一個測試集合，然后對調度算法的性能、正確性和調度結果的質量做了評測。

(1)消息服務性能測試

本部分主要測量了時間觸發通信的延遲，該延遲是SMT調度表求解的重要參數。測試時，在系統的兩個核心上分別建立服務端和客戶端兩個進程，客戶端向服務端發送請求后，服務端立刻返回一條消息。通過消息的往返發送，可以測量出延遲。本次測試中，每經過一萬個消息往返，記錄一次時延，測試結果如圖5所示。

圖5 Barrelfish實時通信延遲

從圖5中可以看出，SMP通信機制容易受到內核調度器和其它系統進程的影響，消息的時延抖動相對較大，但是依然滿足實時應用的要求。對于通過消息轉發服務收發的SoC內部消息，由于采取了輪詢機制，平均延遲較小，且抖動較小。對于跨SoC的消息，由于目前采用普通TCP/IP網絡進行測量，抖動比較嚴重。

(2)調度算法性能測試

本文一共測試了3種網絡拓撲，分別是星狀網絡，樹狀網絡和雪花狀網絡。針對每種網絡拓撲，隨機生成一系列的幀集合，并隨機生成一定比例的約束條件(本文使用幀數的20%作為應用級約束)，然后使用求解器進行求解。調度器求解時間的統計結果如圖6所示。

圖6 各種網絡拓撲數據幀調度耗時

(3)動態SMP子系統測試

動態SMP子系統本質上是實現了共享地址空間的并行方案。共享內存實際上是共享部分物理內存，而動態SMP子系統則是共享整個虛擬地址空間，本質上來看兩者區別只是共享空間的大小不同，但是動態SMP子系統提供了一個更友好的編程接口。為了驗證兩種方案對性能的影響，本文通過矩陣相乘算法，對兩種方法的性能進行了測試。

測試結果如圖7和圖8所示。

圖7 Qemu中共享內存與動態SMP子系統性能對比

圖8 Jetson TK1中共享內存與動態SMP子系統性能對比

由測試結果可以看出，共享內存方案由于存在通信延遲，其性能比動態SMP子系統方案要略微差一些。但是兩者都能起到并行執行的效果，相比于單核心執行，并行執行能夠明顯地提高性能。

(4)綜合測試

為了對整個系統進行驗證，本文設計了如圖9所示的網絡結構，由于缺乏時間觸發實時網絡硬件的支撐，本節將使用Qemu搭建虛擬網絡進行模擬驗證。

圖9 綜合實驗組網

網絡中，每個節點上運行有X64架構的四核心處理器，節點間通過Qemu虛擬交換機相連。每個節點內部的通信不受限制，相當于CPU內部的核心間有兩兩相連的通信鏈路，節點間產生通信時，每個節點在一個時間槽只能發出一條消息。每個有依賴應用的應用，只有在接收到依賴應用發來的消息之后間隔一個時間槽，才可以發送消息。

本文設計了如表3所示的綜合實驗應用。

表3 綜合實驗應用設計

由表3可知，集群的超周期為24。針對應用的周期，調度器生成了實時調度表，如圖10所示。

圖10 實時調度器生成調度表

調度表的成功生成表明了基于Barrelfish的時間觸發實時通信框架的正確性與可行性。

4 結束語

本文在Barrelfish的基礎上設計與實現了一套基于時間觸發機制的實時通信架構，該架構包括一套獨立的時間觸發實時消息服務、接口以及用于時間觸發實時系統消息調度的靜態離線調度算法和調度器。該通信架構為Multikernel架構在分布式CPS實時系統上的應用打下了基礎。

該通信架構仍有如下地方有待改進：

(1)每個SoC上都需要分出單獨核心運行時間觸發實時消息服務，對CPU資源產生了較大浪費。

(2)目前尚未給出綜合消息調度與任務調度的完整解決方案。

(3)當前測試所使用的硬件系統規模較小。