實時機模型及時間語義指令集研究*

陳香蘭，李 曦，汪 超，周學海

(中國科學技術大學計算機科學與技術學院，安徽 合肥 230027)

1 引言

航空航天、汽車電子和軌道交通等硬實時HRT(Hard Real-Time)系統需要嚴格的時域控制，要求系統設計滿足時間可預測性，以保證時序行為確定性和安全隔離。所謂“時間可預測性”一般指靜態地計算程序執行時間(Execution Time)的安全和精確上界的能力，與計算機體系結構和任務執行機制密切相關?，F代的計算機系統通過在各個層次引入計算并行化和訪存緩存化等優化機制，雖然有效提升了系統的平均性能，卻也帶來了嚴重的時序不確定性問題。另一方面，傳統實時系統設計采用優先級調度策略，依賴定時器盡力而為地滿足任務執行的時間約束，但定時器為處理器外設，與指令執行異步，且優先級調度可能存在時序異常等問題。這兩方面的原因導致程序執行時間在設計階段難以緊致確定，且平臺依賴，難以驗證。因此，現有設計方法只能基于保守設計思想，以最壞情況執行時間WCET(Worst-Case Execution Time)分析理論為基礎，采用時序相對簡單的系統架構或過量資源預留策略，導致實際應用中的資源利用率甚至不足30%。即便如此，在設計時仍然無法保證可預測性，操作的正確性只能事后驗證。

未來的實時系統具有混合關鍵系統MCS(Mixed Critical System)特征，要求為時序關鍵(Timing Critical)應用提供實時性保證，為安全關鍵(Safety Critical)應用提供時空隔離能力，為其他應用提供高性能算力。因此，需要構建嚴格的緊致時間MTTT(Multi-Tier Tight Timing)設計方法，需要突破現有計算機體系結構理論和方法的局限，建立軟硬件混合系統的建模方法。

自20世紀90年代起，實時系統研究者認識到時間可預測性對硬實時系統設計的重要性，以構造時間行為可預測的實時系統為目標，從計算機系統結構、處理器微結構、編程模型和編程語言等方面展開了廣泛而深入的研究。研究表明，采用構件化軟件體系結構、基于時間觸發執行機制和LET(Logical Execution Time)編程模型[1]構建時序關鍵系統是實現MCS系統時序隔離、可預測、可組合和可擴展(Extensibility)的可行技術路線。

但是，受上述體系結構和任務執行機制限制，LET模型系統執行效率低下。為此，本文認為必須解決2個關鍵問題：(1)建立操作的時間語義模型，明確其時間行為、時間屬性和時間約束等要求；(2)突破現有計算機系統結構限制，提出具有時間語義的實時計算基礎架構模型(處理器體系結構、編程語言、分布式通信)和編程范式。目前廣泛應用的建模方法只提供了描述時序約束的語法糖，缺少時間語義，無法在設計時進行時序驗證和組合。

本文提出一種具有時間語義的處理器體系結構模型——實時機RTM(Real-Time Machine)，和時間觸發指令集TTI(Time-Triggered Instruction set)[2]，作為構建多層次協同的緊致時間MTTT設計方法的重要基礎。

2 相關研究

本節對當前支持實時計算的處理器體系結構和高級編程語言的研究現狀進行梳理。

2.1 實時計算處理器體系結構

實時處理器研究工作可分為3類：時間可預測處理器TPP(Time/Temporal/Timing Predictable Processor)、RTOS(Real-Time Operating System)加速器和反應式處理器。

LEOPARD(LEOn-based Probabilictically Analyzable processor Design)[3]基于通用處理器LEO，增加低開銷機制，支持基于測量的時序分析MBTA(Measurement-Based Timing Analysis)WCET時捕捉抖動(延時變化)資源的影響。在計算核級，分別控制Cache、TLB和延時可變的浮點計算單元的抖動。在芯片級，控制競爭，保證時間可組合。

DMT(Dominant Meta Thread)[4]為同步多線程SMT(Simultaneous MultiTreading)處理器。處理器中存在多個硬實時(HRT)和軟實時SRT(Soft Real-Time)或非實時線程。主線程DMT以看起來是處理器中的唯一線程的方式執行，因此可以采用單線程WCET分析技術。通過主時間共享技術DTS(Dominant Time Sharing)，多個HRT線程共享DMT的執行時間。各線程的時間片長度和周期可以在運行時調整。

FlexPRET[5]處理器為SMT處理器，采用特殊前推通路避免數據依賴，采用細粒度多線程技術通過并發降低不使用動態分支預測和Cache所導致的性能損失，達到WCET計算的復雜度與平均計算性能之間的平衡。同時執行HRT任務和SRT任務。流水線使用線程隔離技術(HRT線程時分多址)消除線程間干擾。指令調度對SRT任務透明，不影響HRT任務。

同時，FlexPRET以所謂PRET(PREcision-Timed)機模型[6]——一種提供可重復和可控制時序的處理器微結構模型——為基礎，針對時序可重復性問題進行指令集擴充，增加了一些時序控制指令，包括設定代碼段的執行時間下界指令delay_until、設定跳轉時間下界指令branch_expire以及設定在某個時刻拋出異常的指令interrupt_expire。PRET機采用物理與邏輯混合的時間概念。在FlexPRET中，時間表示為相對于系統加電或復位開始的納秒值而不是時鐘滴答數，時序精度為一個時鐘周期，時鐘寬度為32位，更長的相對時間需要軟件實現。這種表示方式使程序的時間值與處理器時鐘頻率無關，保證了二進制代碼的可移植性，并支持動態頻率調節技術。對分布式系統，可以通過調整定時器的增加值來實現時間同步，并維持亞納秒定時精度。FlexPRET將具有明確時序約束的硬實時線程(HRT)和傳統的軟實時線程(SRT)組合在一起，由應用程序平衡共享處理器資源，將HRT不占用的流水線周期讓給SRT使用。硬件多線程技術顯示，確定性隨著應用中并發性增加而增加，與傳統處理器差別顯著。只要有足夠的并發性，流水線停頓和訪存延遲較小，線程執行的時序更加規則和可預測，中斷響應延遲也降低幾個數量級，處理器利用率可達100%，但線程交替訪問，難以確定截止時間。

ARPRET(Auckland Reactive PRET)[7]處理器用于執行PRET-C程序。PRET-C是C語言的宏擴展，支持同步并發和表達邏輯時間的高級結構。ARPRET基于3級流水線軟核Microblaze和1個硬件調度器PFU(Predictable Functional Unit)。只使用片上存儲器，因此其讀寫訪存指令為1個時鐘周期。ARPRET以吞吐率和簡化最壞情況響應時間WCRT(Worst-Case Response Time)分析為目標。采用邏輯時間概念，通過靜態代碼分析實現邏輯時間和物理時間的映射。

JOP(Java Optimized Processor)處理器[8]使用2級棧緩存架構實現Java虛擬機的棧架構。采用3級流水線，使用2個寄存器存儲2個棧頂對象，棧的其他部分在SRAM中。由于分支延遲開銷很小，因此不使用分支預測。JOP中的所有字節碼被轉換為固定長度的微指令，每個微指令的執行周期數固定，獨立于其周圍的指令。

ARPA-MT(Advanced Real-time Processor Architecture-MultiThreaded)[9]是一種基于MIPS32架構的SMT處理器，針對多任務實時系統進行了優化。ARPA-MT的協處理器0負責內存管理、異常和中斷處理，協處理器2則實現了實時系統的硬件支持，如定時、任務調度、同步和切換，以及時序約束檢測。這些功能的硬件實現能夠更快、更加可預測地執行任務，減少了RTOS開銷，并改善其確定性。

與環境高效和可靠地交互(稱“反應”)是面向控制的嵌入式系統應用的關鍵特征，往往采用同步語言(如Esterel)和編程范式。反應式處理器不使用中斷而是使用ISA(Instruction-Set Architecture)指令與環境交互，且執行機制采用時間觸發而非事件觸發。REMIC(REactive MICroprocessor)[10]是帶有同步反應式功能單元和控制單元的反應式處理器，EMPEROR(Embedded MultiProcessor supporting Esterel Reactive OpeRations)[11]提供在多處理器之間分配同步線程的方法。

可以看出，TPP處理器通過限制使用分支預測、亂序執行和Cache等造成時序不確定的技術，提高WCET分析的緊致性。但是，TPP主要以滿足WCET分析緊致性要求為目標，損失了計算性能。RTOS加速器通過硬件實現任務調度和關鍵服務原語，降低RTOS的運行開銷和時間抖動，提升了可預測性，利于系統驗證(硬件執行時序是完全確定的)，但受硬件實現復雜度和資源限制，靈活性不佳，通信接口效率低、時延高。反應式處理器僅支持特定的同步編程語言和范式，通用性不佳，且計算性能有限。

2.2 實時計算高級語言和編程模型

現代編程語言反映了計算機體系結構的特征。面向通用計算的編程語言描述了操作的執行順序，操作的時間屬性與程序的邏輯正確性無關。實時系統編程可以基于同步范式(使用同步編程語言，如Esterel)或異步范式(使用異步編程語言，如Ada)。

同步模型基于邏輯時間模型和同步假設，即動作是原子的且瞬間完成，并發動作間無交互，動作與邏輯Tick同一時刻發生，無抖動。該抽象為確定性模型，利于系統行為分析驗證。同步語言中，邏輯Tick是語言語義的組成成分，用于事件定序，與實際物理時間無關。Esterel等同步語言基于虛擬時間抽象，與平臺的物理時間無關，其邏輯行為總是可預測的。實現時采用時鐘驅動的靜態調度技術，利于響應時間分析和因果關系保證，但表達復雜交互行為的能力不足。

異步語言基于物理時間的實時鐘模型，一般提供時鐘訪問、進程延遲、同步與通信超時等實時控制設施(包括原語與結構)。Ada編程語言基于物理時間概念提供了量化描述時序約束的語言結構，需要借助定時器中斷或操作系統所提供的時間服務控制程序的時序行為。Ada采用中斷驅動的優先級調度技術，利用定時器控制任務執行時間，且中斷是一種異步并發機制，必然導致應用程序的時間行為不確定和不可重復。因此，采用Ada等高級語言進行實時軟件編程是低效的，一方面其時序約束定義的粒度過粗(以任務為最小實體)，另一方面，這些語言的編程模型所表達的時序約束僅為程序中位置相鄰的前后2個任務之間的時序關系，無法表達任意操作(可能并行)的時間約束。由于沒有支持通過合適的方法定義時間需求和進行高精度時序分析的實時語言，實踐中HRT系統仍然只能采用低級編程語言，并手工對時間需求進行調優。

Chung等[12]針對靜態調度方法，對C語言進行擴展，基于所謂時間有向圖(Directed Timed Graph)模型，給出表達時序約束和優先約束的語言結構，包括時序塊(Timing Block)和Temporal表達式，描述操作的開始時間、完成時間和周期。

ZET(Zero Execution Time)模型是同步反應式編程的基礎抽象，BET(Bounded Execution Time)模型是實時調度理論的基礎抽象。實時程序的相關行為由輸入輸出時刻決定，而非程序代碼的執行時刻。因此，Henzinger等[1]結合ZET和BET模型，在2000年提出了實時編程范式LET模型。采用LET模型時，任務總是在其激活區間的開始處讀數據，結束處寫數據，使其可觀察的時態行為獨立于任務的物理執行。LET確定了讀程序輸入到寫程序輸出之間所需的時間，而不考慮執行程序所需的時間，具有平臺可移植性。雖然實際應用時LET模型的資源(緩存、時間)利用率較低，但LET為控制工程師和軟件工程師提供了清晰的時序模型接口。2017年以來，隨著多核平臺下可預測性(Predictability)成為關鍵問題，工業界認為LET對于解決多核MCS應用和分布式實時系統的通信確定性問題極具吸引力，甚至可能與Autosar相結合而成為新的工業標準。

3 實時機模型

計算機科學領域的時間概念相當原始。圖靈機和馮·諾依曼機模型基于順序控制抽象，指令一條接一條執行，時間先后關系(Temporal Succession)是當前機器語言級唯一可用的時序關系。雖然定義馮·諾依曼機的程序邏輯行為無需顯式地引用時間概念，但無法滿足實時系統所需要的實時間約束。

在時態邏輯、進程代數、自動機和斷言等形式化建模方法中，時間概念在模型語義中是隱式的，所考慮的唯一時間屬性是順序，不考慮絕對時間(時間點)或相對時間(持續時間)，因此只能表達和驗證離散事件系統行為的時態順序正確性，欠缺足夠的實時表達能力。它們的基本假設是程序代碼的執行速度足夠快，程序的時間屬性與其功能正確性無關。為了適應實時系統規約的需要，人們試圖擴展傳統的形式化方法，以允許定量地表達定時特性，如時間自動機和實時時態邏輯(Real-Time Temporal Logic)等。這些方法可應用于簡單系統的可調度性分析或時間行為驗證，但難以應用于具有嚴格時序行為約束的復雜實時系統。

現代計算機系統依賴基于定時器的時鐘中斷機制提供定時服務。定時器作為處理器外設，通過輪詢或中斷方式訪問。時鐘中斷是一種異步并發機制，精度低，開銷大，且存在副作用——中斷當前任務將導致其執行時間延長，可能產生危害性后果?；趦炏燃壍娜蝿照{度策略以中斷機制為基礎，行為難以預測，且驗證困難，平臺依賴性高。

可以看出，由于當前處理器體系結構不顯式地提供時間語義支持，系統模型和基礎設施缺乏時間語義，或僅基于邏輯時間，或僅基于物理時間。雖有研究者提出了一些引入時間概念的高級語言，但底層沒有時間語義而僅僅從高層引入是有問題的，導致系統設計、分析、驗證與實現的時間語義不一致?，F有時間可預測性保證依賴基于WCET的可調度分析，但由于系統行為內在的異步并發性，執行時間有界并不能保證操作的執行順序，因此不能保證時序行為可預測。

傳統的保守方法只適合簡單實時系統設計，MCS系統需要緊致時間設計方法。2005年以來，Bensalem等[13]多認識到當前研究的局限性，在不同場合提出實時計算需要重新思考甚至發展計算機科學的理論基礎。但迄今為止，由于實時應用涉及控制工程、電子工程、計算機工程和軟件工程等多學科交叉，各領域之間存在理論方法甚至文化差異，這一問題遠未解決。

本文認為，任務、動作和操作的時間語義應包含時間行為和時間屬性。前者與硬件實現無關，不應依賴于底層實現；后者與硬件實現相關，即具有平臺依賴性。前者為語義確定性問題，后者為可預測性問題。LET模型通過解耦計算與通信，保證了時態確定性，具有時域控制與值域控制相分離、時序行為可預測可組合且平臺無關等特點。另一方面，時間觸發TT(Time-Triggered)執行機制具有時序可預測性和時間隔離(分區)的特性。但是，兩者都需要具有確定時間行為的處理器架構和時間語義指令集支持，并以此為基礎形成緊致時間設計方法。

定義1實時機RTM模型對馮·諾依曼機進行以下擴充：

(1)計算機系統由運算器、控制器、存儲器、時鐘設備和I/O設備等功能部件構成；

(2)指令時鐘部件用于操作定時，與CPU的指令數據通路和控制器緊耦合，在保持馮·諾依曼機指令的邏輯功能不變的同時，增加特定操作的執行時刻和限定操作序列(動作)的執行時間等時間語義；

(3)RTM的指令字由操作碼、地址碼和定時碼構成，操作碼定義操作的功能，地址碼指定操作數和下一條指令的地址，定時碼指定操作的時間約束。

RTM如圖1所示，以支持緊致時間設計為目標，其核心思想不是僅僅在CPU中增加了時鐘部件，而在于明確了時間行為控制的概念，并通過提供時間語義指令集，使上層應用的時間行為與指令周期同步，實現了時域控制的原子性，減小了定時抖動。RTM以“關注分離(Separation of Concerns)”和“構建正確(Correct-by-Construction)”為設計原則，區分邏輯控制與時域控制，為實現從時序可預測設計到時序確定性設計轉變奠定了理論基礎，利于實時程序代碼自動生成和降低系統驗證的復雜度。

Figure 1 RTM architecture圖1 RTM結構

以RTM為基礎，時間語義指令集可提供at、delay-until和timestamp等控制時間行為的指令，支持邏輯執行時間(LET)模型和時間觸發等應用模式。

4 應用示例

本節對RISC-V[14]指令集進行時間語義擴展，定義時間觸發指令集TTI，并給出一個直升機飛控應用實例。

4.1 TTI指令集

TTI時間語義指令集擴展主要包含時間模型、時間寄存器和時間語義指令3個部分。其中，時間模型規范該指令集擴展時間相關的概念和應用方法；時間寄存器是在通用寄存器之外添加的新寄存器，用于存放時間值，該時間值符合時間模型規范；時間語義指令包括時鐘管理指令、時間寄存器管理指令和時間語義操作指令。

本文采用基于時間點(時刻)的絕對時間模型，即處理器時鐘的時間從設定時刻開始，一直以一定的速率增長。描述操作的時間時，采用某時刻的方式；描述一個時間段時，采用從某時刻開始到某時刻結束的方式。時間寄存器存放絕對時間模型的一個時間點。

時間語義指令功能如表1所示，包括：

(1)時間管理指令：setti/getti指令用于設置/獲取系統當前時間；settg指令用于設置系統當前時間粒度，即時間向前自增的單位。

(2)時間寄存器管理指令：tmove指令用于通用寄存器和時間寄存器之間的數據傳輸。

(3)實時操作指令：ttiat/ttoat指令用于在指定時刻I/O端口輸入輸出。

Table 1 Function of extend instructions

表1中，rs1、rs2和rd為通用寄存器，trs為時間寄存器地址，tg為系統當前時間粒度寄存器，ti為當前時間寄存器。

RISC-V是一個典型的三操作數、加載-存儲形式的RISC指令集架構，由基礎指令集和擴展指令集組成?；A指令由基本整數指令構成，擴展指令分為標準擴展和非標準擴展2大類?，F階段已經完成的標準擴展為一個包含標準乘法和除法(M)、原子(A)、單精度(F)和雙精度(D)運算的通用標量指令集。非標準擴展作為一個高度特殊化的擴展，由用戶根據功能需求自定義完成。TTI指令集基于RISC-V非標準擴展進行定義，如圖2所示。

Figure 2 Format extension for TTI instructions圖2 TTI擴展指令指令字格式

4.2 直升機飛控

直升機飛控系統的需求如圖3所示。若采用傳統的前后臺編程范式或輪詢范式實現飛控軟件，其架構和時序分別如圖4a和圖4b所示。可以看出，當某時刻需要執行多個動作時，采用這種編程模式必然存在定時抖動，如圖4b中時刻0,2和6。

Figure 3 Requirements of a helicopter flight control system

Figure 4 Software architecture and timing

LET編程模型將任務的邏輯行為“輸入-計算-輸出”過程相分離，如圖5所示，定義了嚴格的輸入輸出時刻，要求在指定時刻輸入，在輸出時刻之前計算出結果，并能夠將輸出結果保持到指定時刻輸出，具有時間行為可預測、可組合和平臺無關性等重要特征，利于設計時進行系統行為驗證。

Figure 5 LET programming model圖5 LET編程模型

基于LET編程模型的飛控系統的實現代碼如下所示：

1Init(); // init the system

2time_t1 =time_t2 =time_t3 =time_t4 = 0;/*suppose all tasks start at 0*/

3flag_t1 =TTI(all_sensor_data,time_t1);

4flag_t2 =TTI(keyboard_data,time_t2);

5flag_t3 =TTI(sensor_data,mode_data,time_t3);

6flag_t4 =TTI(loop_data1,loop_data2,loop_data3,time_t4);

7SetIntertup();/*set a interrupt, and only enable it to interrupt*/

8 /*t1～t4, every 1/180 second, when occur, store*/

9 /*context for current task and go to INT_LABEL*/

10while(TRUE) {

11 INT_LABEL:

12if(flag_t1) {

13load_context();

14t1();

15store_context();

16time_t1 += 1;

17TTO(sensor_data,time_t1);

18flag_t1 =TTI(all_sensor_data,time_t1);

19 }

20if(flag_t2) {

21load_context();

22t2();

23store_context();

24time_t2 += 6;

25TTO(mode_data,time_t2);

26flag_t2 =TTI(keyboard_data,time_t2);

27 }

28if(flag_t3) {

29load_context();

30t31();

31t32();

32t33();

33store_context();

34time_t3 += 2;

35TTO(loop_data1,loop_data2,loop_data3,time_t3);

36flag_t3 =TTI(sensor_data,mode_data,time_t3);

37 }

38if(flag_t4) {

39load_context();

40t4();

41store_context();

42time_t4 += 6;

43TTO(control_data,time_t4);

44flag_t4 =TTI(loop_data1,loop_data2,loop_data3,time_t4);

45 }

46 }

基于LET編程模型的飛控系統各任務的時序行為如圖6所示。其中，t1為傳感器任務，t2為模式任務，t31,t32,t33為內循環任務，t4為控制器任務。

Figure 6 Timing for the LET program of the helicopter flight control program圖6 直升機飛控LET程序的時序

每個任務的LET實現包含3個部分：基于TTI()的定時輸入、計算和基于TTO()的定時輸出。其中，TTI()和TTO()分別是對ttiat和ttoat指令的封裝。TTI()在指定時刻完成指定數據的輸入，TTO()在指定時刻完成指定數據的輸出。若指定的時刻未到，則等待，等待過程中TTI()的返回值始終為FALSE，指定時刻到來時，TTI()完成指定數據的輸入，此后返回值為TRUE。TTO()類似，但沒有返回值。每個任務通過TTI()顯式地請求在指定時刻執行指定數據的輸入。系統實現代碼中第3～6行分別是t1,t2,t3和t4的首次定時輸入請求，對應圖6中的“↑”標記。計算部分的代碼是位于load_contex()和store_context()中間的代碼，第14,22,30～32,40行所示。計算執行完畢，每個任務通過TTO()顯式地請求在指定時刻輸出指定數據，同時通過TTI()發出下一輪的定時輸入請求。系統實現代碼中第17,25,35,43行分別是這4個任務的定時輸出請求，第18,26,36,44行分別是它們的下一輪定時輸入請求，并且這4個任務都將本次輸出和下一輪的輸入放在同一時刻，對應圖6中的“?”標記?？梢钥闯觯蝿盏腖ET實現中，輸入輸出時間完全由TTI()和TTO()指定的時刻決定，而不受任務計算部分程序執行時間抖動的影響。

飛控系統中設置一個周期性時鐘中斷，如系統實現代碼中第7行將中斷頻率設置為每秒180次。該中斷只用于中斷代碼中while循環中的4個任務。每次中斷處理，系統跳到INT_LABEL處開始處理。系統按照代碼順序依次查看是否需要執行這4個任務的計算部分，如第12,20,28,38行的if語句。當某任務設置的TTI()返回值為TRUE就執行，如圖6中t1每次都執行。當某任務設置的TTI()返回值為FALSE，就跳過該任務不執行，如圖6中點C處就跳過t2執行t3。若沒有任務需要執行，系統idle，如圖6中陰影右下角的idle部分，此時可以執行其他軟實時或非實時任務。中斷發生時，若有當前任務正在執行，則該任務被中斷，保存該任務上下文，然后開始新一輪中斷處理，如圖6中點A處，中斷在t2執行過程中發生，此時保存t2上下文，轉到INT_LABEL處從t1重新開始依次執行。被中斷的任務在后續執行中輪到該任務執行時將繼續執行，如圖6中點B處，t1執行完后順次執行t2時，加載t2之前被中斷的上下文繼續執行。

由于輸入輸出定時由ttiat/ttoat指令控制，與任務計算邏輯的執行時間無關，保證了控制系統的魯棒性。

5 結束語

針對未來復雜的混合關鍵系統需要研究新的緊致時間控制設計方法，采用構件化軟件體系結構，基于時間觸發執行機制和LET編程模型構建時間關鍵系統是實現可預測性、時序隔離、可組合和可擴展的有效方案，但性能低效和分析驗證復雜是這一方案的瓶頸，需要實時計算機體系結構創新。

本文以馮·諾伊曼模型為基礎，定義新的支持時間語義的實時計算機體系結構模型，并以此為基礎實現緊致時間方法。文中提出了支持實時計算的RTM計算機模型和TTI指令集。RTM突破了馮·諾伊曼機模型在實時計算應用中的理論局限，分離時域控制和值域控制的時序約束，明確了時間行為控制的基本抽象。

目前本文正在對RISC-V指令集進行TTI擴展，實現一個實時處理器原型RPU(Realtime Processing Unit)，以驗證RTM的時序行為控制能力。RPU將采用硬件多線程技術，以滿足安全關鍵應用的高性能和時空隔離需求。支持時間行為約束表達的實時控制設施(原語與結構)、編程語言、中間語言以及時間安全性分析與驗證理論和技術都是重要的課題。