LET模型的時(shí)間語(yǔ)義編程語(yǔ)言

LET模型的時(shí)間語(yǔ)義編程語(yǔ)言

吳昊，章博，陳香蘭，王超，李曦中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥230026在實(shí)時(shí)系統(tǒng)中，如一個(gè)汽車、機(jī)器人系統(tǒng)，系統(tǒng)的正確性同時(shí)取決于邏輯和時(shí)間的正確性。系統(tǒng)行為的定時(shí)、及時(shí)發(fā)生需要在軟件中明確指定，并在實(shí)時(shí)平臺(tái)上正確執(zhí)行。然而，現(xiàn)有的編程語(yǔ)言缺乏顯示表達(dá)系統(tǒng)時(shí)間屬性的語(yǔ)法結(jié)構(gòu)，為此實(shí)時(shí)系統(tǒng)領(lǐng)域逐漸衍生出了各種實(shí)時(shí)語(yǔ)言來(lái)顯示表達(dá)系統(tǒng)的時(shí)間屬性。嵌入式實(shí)時(shí)系統(tǒng)編程模型根據(jù)其發(fā)展歷程和應(yīng)用場(chǎng)景的需求主要可以分為三類：有界執(zhí)行時(shí)間模型（boundedexecutiontime，BET）[1]、零執(zhí)行時(shí)間模型（zeroexecutiontime，ZET）[2]以及邏輯執(zhí)行時(shí)間模型（logicalexecutiontime，LET）[3]。目前的實(shí)時(shí)編程語(yǔ)言便基于這三種編程模型。有界執(zhí)行時(shí)間模型又叫作異步模型，模型通過(guò)優(yōu)先級(jí)決定任務(wù)的執(zhí)行順序，要求任務(wù)在既定的截止時(shí)間之前完成執(zhí)行。異步模型的代表性編程語(yǔ)言為Ada[4]。Ada通過(guò)調(diào)用時(shí)間控制函數(shù)來(lái)指定任務(wù)的時(shí)間屬性與時(shí)間行為，其運(yùn)行時(shí)系統(tǒng)是基于線程模型實(shí)現(xiàn)的執(zhí)行環(huán)境，在執(zhí)行環(huán)境里多個(gè)并發(fā)的Ada任務(wù)異步交錯(cuò)執(zhí)行。但在異步模型中，由于運(yùn)行時(shí)系統(tǒng)缺乏對(duì)任務(wù)時(shí)序行為的約束，可搶占線程在并發(fā)情況下的執(zhí)行過(guò)程具有不確定性，導(dǎo)致系統(tǒng)實(shí)際執(zhí)行的時(shí)序語(yǔ)義很難與模型層保持一致性，系統(tǒng)行為具有不可預(yù)測(cè)性。零執(zhí)行時(shí)間模型又叫作同步模型，模型基于同步假設(shè)，即在邏輯上任務(wù)的執(zhí)行時(shí)間為零。同步模型抽象層次高，具有數(shù)學(xué)抽象能力，可采用形式化工具證明其行為正確性。同步模型主要刻畫任務(wù)的因果關(guān)系，通過(guò)邏輯時(shí)間表達(dá)任務(wù)的時(shí)間行為。基于同步模型的編程語(yǔ)言有Esterel[5]、PRET-C[6]、Lustre[7]以及Signal[8]等。然而，在實(shí)際的物理平臺(tái)中，無(wú)法實(shí)現(xiàn)無(wú)限快的運(yùn)算速度，系統(tǒng)實(shí)際運(yùn)行過(guò)程中不可能按照Z(yǔ)ET的時(shí)序假設(shè)運(yùn)行。邏輯執(zhí)行時(shí)間模型介于異步模型和同步模型之間，模型為每個(gè)任務(wù)指定了一段邏輯執(zhí)行時(shí)間，任務(wù)只能在該時(shí)間段的開(kāi)始和結(jié)束時(shí)刻分別執(zhí)行輸入和輸出過(guò)程，即進(jìn)行任務(wù)間的同步，而計(jì)算過(guò)程異步進(jìn)行，且計(jì)算結(jié)果必須在輸出時(shí)刻之前有效。LET模型約束了決定任務(wù)時(shí)序行為的關(guān)鍵過(guò)程（輸入和輸出），能直接有效地刻畫任務(wù)的時(shí)間行為。Giotto[9]、HTL[10]、TDL[11]等現(xiàn)有的基于LET模型的編程語(yǔ)言，其語(yǔ)言只描述了系統(tǒng)的時(shí)間約束，而具體的功能代碼則通過(guò)C、Java等常見(jiàn)的高級(jí)語(yǔ)言來(lái)實(shí)現(xiàn)；語(yǔ)言通過(guò)特定編譯器編譯為中間代碼E-code[12]，在執(zhí)行時(shí)，虛擬機(jī)E-machine[12]根據(jù)E-code描述的時(shí)間行為驅(qū)動(dòng)功能代碼的執(zhí)行，虛擬機(jī)本身則是運(yùn)行在實(shí)時(shí)操作系統(tǒng)之上。這種將時(shí)間控制程序和功能代碼分開(kāi)的方式并不方便設(shè)計(jì)，希望通過(guò)擴(kuò)展一種高級(jí)語(yǔ)言的方式來(lái)實(shí)現(xiàn)一種實(shí)時(shí)編程語(yǔ)言。本文提出一種基于C擴(kuò)展的實(shí)時(shí)編程語(yǔ)言TBC。TBC基于LET編程模型，在語(yǔ)言層次上，從設(shè)計(jì)的時(shí)間需求出發(fā)，引入可觀測(cè)事件的概念，來(lái)簡(jiǎn)化系統(tǒng)內(nèi)部的時(shí)間約束，降低系統(tǒng)響應(yīng)延遲，并通過(guò)擴(kuò)展的語(yǔ)法結(jié)構(gòu)來(lái)表達(dá)系統(tǒng)中的各種時(shí)間屬性。在編譯器層次，本文提出了一種針對(duì)實(shí)時(shí)編程語(yǔ)言的編譯技術(shù)，通過(guò)在編譯器前端增加相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來(lái)表示語(yǔ)法結(jié)構(gòu)中的時(shí)間屬性，同時(shí)對(duì)中間語(yǔ)言LLVMIR進(jìn)行時(shí)間指令擴(kuò)展，使其可以表示系統(tǒng)的時(shí)間行為。在之前的工作中作者提出了包含時(shí)間語(yǔ)義的指令集TTI[13]，將其作為編譯器的目標(biāo)指令。1實(shí)時(shí)語(yǔ)言框架除了編程模型外，實(shí)時(shí)語(yǔ)言的區(qū)別主要在于其實(shí)現(xiàn)方式和編譯方式，本文針對(duì)這兩點(diǎn)提出一種實(shí)時(shí)語(yǔ)言設(shè)計(jì)框架，基于此架構(gòu)來(lái)設(shè)計(jì)實(shí)時(shí)語(yǔ)言TBC。如圖1所示，整個(gè)語(yǔ)言框架分為高級(jí)語(yǔ)言、中間語(yǔ)言和匯編語(yǔ)言三個(gè)層次。圖1語(yǔ)言設(shè)計(jì)整體架構(gòu)Fig.1Overallarchitectureoflanguagedesign高級(jí)語(yǔ)言指實(shí)時(shí)語(yǔ)言本身，在本文中通過(guò)基于C擴(kuò)展語(yǔ)法結(jié)構(gòu)的方式來(lái)實(shí)現(xiàn)語(yǔ)言時(shí)間語(yǔ)義的擴(kuò)展。在這里語(yǔ)法結(jié)構(gòu)是指如if、for一樣的語(yǔ)言結(jié)構(gòu)，通過(guò)編譯器來(lái)進(jìn)行分析處理，相對(duì)于Ada、RTOS通過(guò)API來(lái)指定時(shí)間屬性的方式，軟件程序更加簡(jiǎn)單，不需要大量的代碼來(lái)設(shè)置定時(shí)器，處理不同的時(shí)間格式。同時(shí)如果程序使用某個(gè)平臺(tái)依賴的API，則該程序的運(yùn)行不再靈活，時(shí)間操作必須是平臺(tái)依賴的，更重要的是，語(yǔ)法結(jié)構(gòu)可以通過(guò)形式化的方式表示其語(yǔ)法和語(yǔ)義，并能對(duì)語(yǔ)義進(jìn)行驗(yàn)證。在高級(jí)語(yǔ)言層次，通過(guò)擴(kuò)展的語(yǔ)法結(jié)構(gòu)來(lái)表達(dá)多個(gè)任務(wù)并發(fā)執(zhí)行的時(shí)間語(yǔ)義。現(xiàn)有的許多編程框架[14-15]或?qū)崟r(shí)語(yǔ)言基于RTOS來(lái)實(shí)現(xiàn)。如文獻(xiàn)[16]將實(shí)時(shí)語(yǔ)言Timed-C編譯成RTOS代碼，而本文將具有時(shí)間語(yǔ)義的指令集作為編譯器的目標(biāo)代碼，這使得目標(biāo)平臺(tái)不需要支持功能復(fù)雜的RTOS，只需要增加相應(yīng)定時(shí)器來(lái)支持時(shí)間語(yǔ)義指令的實(shí)現(xiàn)。具體的，編譯器基于LLVM[17]編譯器框架，分為前端和后端，并將LLVMIR作為編譯器的中間語(yǔ)言。擴(kuò)展的語(yǔ)法結(jié)構(gòu)在編譯器前端經(jīng)過(guò)分析處理轉(zhuǎn)換為中間語(yǔ)言中的時(shí)間指令，此時(shí)語(yǔ)法結(jié)構(gòu)所表示的任務(wù)并發(fā)的執(zhí)行行為轉(zhuǎn)換為時(shí)間指令所表示的串行執(zhí)行行為。最后中間語(yǔ)言通過(guò)編譯器后端轉(zhuǎn)換成具體的匯編語(yǔ)言，即中間語(yǔ)言中的時(shí)間指令映射到匯編語(yǔ)言中的時(shí)間指令。高級(jí)語(yǔ)言中的語(yǔ)法結(jié)構(gòu)和中間語(yǔ)言及匯編語(yǔ)言中的時(shí)間指令都是為了約束各個(gè)層次中系統(tǒng)的時(shí)間行為，但為了便于系統(tǒng)設(shè)計(jì)者進(jìn)行編程，語(yǔ)法結(jié)構(gòu)應(yīng)表示更高層次的時(shí)間約束，如任務(wù)級(jí)的任務(wù)周期、任務(wù)優(yōu)先關(guān)系等；而時(shí)間指令應(yīng)該更注重平臺(tái)實(shí)現(xiàn)，表示時(shí)間操作更具體，如延遲操作delay等。另外，本文注重時(shí)間的本身，即各層次語(yǔ)言都應(yīng)該明確語(yǔ)言中時(shí)間的連續(xù)離散與否、時(shí)間粒度等時(shí)間屬性。本文采用文獻(xiàn)[18]中時(shí)間域的概念來(lái)描述時(shí)間。時(shí)間域指時(shí)間所基于的一個(gè)數(shù)域（如R、N等），系統(tǒng)中的時(shí)間可取范圍為數(shù)域的值域。如圖1所示，各層次的時(shí)間隨著語(yǔ)言的轉(zhuǎn)換也進(jìn)行相應(yīng)的轉(zhuǎn)換。2TBC的語(yǔ)言模型2.1時(shí)間域本文將數(shù)域N作為語(yǔ)言TBC的時(shí)間域，即在TBC中，時(shí)間為離散的，并且時(shí)間域上的時(shí)間粒度為一段實(shí)時(shí)間，如1ms、1μs等，系統(tǒng)中的動(dòng)作發(fā)生在基于離散時(shí)間域的某個(gè)時(shí)間點(diǎn)上，多個(gè)動(dòng)作可以發(fā)生在同一個(gè)時(shí)刻。CCSL（clockconstraintspecificationlanguage）[19]是嵌入式實(shí)時(shí)系統(tǒng)的標(biāo)準(zhǔn)描述語(yǔ)言（UML）[20]中描述時(shí)鐘約束的規(guī)范語(yǔ)言，可以用來(lái)表示各種連續(xù)和離散的時(shí)鐘。本文通過(guò)CCSL來(lái)形式化地定義TBC的離散時(shí)間域，在TBC默認(rèn)時(shí)間粒度為1ms，時(shí)間域通過(guò)CCSL定義為：其中IdealClk在CCSL中表示一個(gè)連續(xù)時(shí)鐘，其單位為“s”，通過(guò)對(duì)該時(shí)鐘離散化可以得到一個(gè)離散時(shí)鐘。TBC的離散時(shí)間域std通過(guò)一個(gè)以1ms為tick間隔的離散時(shí)鐘來(lái)表示。2.2可觀測(cè)事件在TBC中，引入可觀測(cè)事件的概念。將系統(tǒng)中的事件根據(jù)外界環(huán)境是否可以觀測(cè)到，分為可觀測(cè)事件和不可觀測(cè)事件兩種。可觀測(cè)事件主要指獲取外部傳感器的信號(hào)、更新執(zhí)行器的值等動(dòng)作，這些事件都和外部環(huán)境有直接的關(guān)聯(lián)。不可觀測(cè)事件主要指系統(tǒng)內(nèi)部各個(gè)任務(wù)之間的數(shù)據(jù)通訊等，這些事件不被外界環(huán)境可見(jiàn)，其時(shí)間行為對(duì)外界環(huán)境也沒(méi)有直接的影響。從設(shè)計(jì)需求的角度來(lái)看，構(gòu)建實(shí)時(shí)系統(tǒng)時(shí)，所需的時(shí)間約束需求便是可觀測(cè)事件的時(shí)間約束，因此，主要關(guān)注可觀測(cè)事件的時(shí)間約束。本文以三元組(E,type,P)來(lái)表示可觀測(cè)事件的時(shí)間約束。其中E表示一個(gè)可觀測(cè)事件的標(biāo)識(shí)符；type為事件的種類，分為輸入事件I和輸出事件O；P表示事件發(fā)生的周期，為一段實(shí)時(shí)間，取時(shí)間粒度的整數(shù)倍。如：(E1,I,10)表示周期為10ms的輸入事件E1。本文以一個(gè)事件集合的形式作為系統(tǒng)設(shè)計(jì)的時(shí)間約束需求。2.3時(shí)間行為在TBC中，系統(tǒng)包括多個(gè)并發(fā)的周期性任務(wù)，每個(gè)任務(wù)分為相對(duì)獨(dú)立的I、C、O三部分。任務(wù)的輸入（輸出）可能包括一個(gè)或者多個(gè)事件來(lái)與外界或其他任務(wù)進(jìn)行交互，可以根據(jù)任務(wù)的輸入（輸出）是否包含可觀測(cè)事件，即是否與外界環(huán)境進(jìn)行通訊，將包含可觀測(cè)事件的輸入（輸出）叫作外部輸入（輸出），將包含不可觀測(cè)事件的輸入（輸出）叫作內(nèi)部輸入（輸出）。本文主要關(guān)注外部輸入（輸出）的時(shí)間約束。外部輸入（輸出）本身蘊(yùn)含了兩種時(shí)間語(yǔ)義：外部輸入（輸出）首先作為L(zhǎng)ET編程模型的輸入（輸出），應(yīng)在邏輯執(zhí)行時(shí)間的開(kāi)始（結(jié)束）時(shí)刻執(zhí)行；同時(shí)因?yàn)橥獠枯斎耄ㄝ敵觯┌丝捎^測(cè)事件，所以應(yīng)該滿足可觀測(cè)事件的時(shí)間約束。在TBC中，任務(wù)的邏輯執(zhí)行時(shí)間等于任務(wù)周期，因此在構(gòu)建任務(wù)時(shí)，通常將可觀測(cè)事件的周期作為其所在任務(wù)的任務(wù)周期。內(nèi)部輸入（輸出）適用于任務(wù)之間的數(shù)據(jù)通訊，從外部環(huán)境無(wú)法觀測(cè)，其時(shí)間行為并不直接影響系統(tǒng)與外界環(huán)境的通訊，因此不專門考慮內(nèi)部輸入（輸出）的時(shí)間行為。從編程模型的角度來(lái)看，TBC實(shí)際上基于一種放松的LET模型。2.4TBC的LET模型在單個(gè)任務(wù)內(nèi)部，擁有可觀測(cè)事件的外部輸入（輸出）基于時(shí)間觸發(fā)，每到任務(wù)邏輯執(zhí)行時(shí)間的開(kāi)始時(shí)刻（結(jié)束時(shí)刻）便會(huì)觸發(fā)任務(wù)的外部輸入（外部輸出）的執(zhí)行。如圖2所示，周期為T的任務(wù)T1的外部輸入輸出分別在0時(shí)刻和T時(shí)刻進(jìn)行觸發(fā)執(zhí)行。圖2外部輸入輸出的時(shí)間行為Fig.2Timebehavioronexternalinputsandoutputs任務(wù)的內(nèi)部輸入輸出用于兩個(gè)數(shù)據(jù)相關(guān)任務(wù)的數(shù)據(jù)同步，兩個(gè)任務(wù)會(huì)在邏輯執(zhí)行時(shí)間的某個(gè)時(shí)間點(diǎn)進(jìn)行同步。如圖3所示，兩個(gè)周期都為T的任務(wù)T1和T2，兩任務(wù)數(shù)據(jù)相關(guān)，T2依賴于T1的計(jì)算結(jié)果；在0時(shí)刻，T2讀取外界傳感器傳來(lái)的數(shù)據(jù)，并在對(duì)數(shù)據(jù)進(jìn)行計(jì)算后，在t1時(shí)刻便通過(guò)內(nèi)部輸出和任務(wù)T2的內(nèi)部輸入對(duì)計(jì)算結(jié)果進(jìn)行同步，任務(wù)T2在t1時(shí)刻得到T1的計(jì)算結(jié)果后，再經(jīng)過(guò)自己的計(jì)算過(guò)程，在T時(shí)刻通過(guò)外部輸出向外輸出計(jì)算結(jié)果；t1為基于離散時(shí)域的某個(gè)時(shí)刻，不過(guò)本文并不關(guān)注t1時(shí)刻的具體數(shù)值，t1時(shí)刻只需要處于T2的計(jì)算過(guò)程完成之后以及T3的計(jì)算過(guò)程開(kāi)始之前。圖3內(nèi)部輸入輸出的時(shí)間行為Fig.3TimebehavioroninternalinputsandoutputsTBC放松了LET編程模型的時(shí)間約束，允許任務(wù)存在內(nèi)部同步點(diǎn)，任務(wù)可在其邏輯執(zhí)行時(shí)間段內(nèi)進(jìn)行通信，消除了邏輯執(zhí)行時(shí)間模型中周期延遲問(wèn)題，提升了系統(tǒng)響應(yīng)能力。如圖4所示，對(duì)于圖3中的兩個(gè)任務(wù)T1和T2，在一般的LET模型中，系統(tǒng)在0時(shí)刻獲取傳感器的數(shù)據(jù)，在2T時(shí)刻才會(huì)產(chǎn)生相應(yīng)的輸出；而在TBC中，如圖5所示，由于系統(tǒng)可以通過(guò)T1的內(nèi)部輸出和T2的內(nèi)部輸入在t1時(shí)刻提前進(jìn)行同步，在T時(shí)刻便可向外產(chǎn)生同樣的輸出，提升了系統(tǒng)的響應(yīng)能力。TBC語(yǔ)言模型在保障系統(tǒng)與外界交互的時(shí)間行為不變的情況下，將系統(tǒng)的內(nèi)部同步提前，來(lái)降低系統(tǒng)的響應(yīng)延遲。圖4LET模型系統(tǒng)響應(yīng)延遲Fig.4SystemresponsedelayofLETmodel圖5TBC系統(tǒng)響應(yīng)延遲Fig.5SystemresponsedelayofTBC當(dāng)系統(tǒng)出現(xiàn)欠采樣和過(guò)采樣的情況時(shí)，需要指定系統(tǒng)的時(shí)間行為來(lái)保障輸入與輸出關(guān)系的確定性，本文規(guī)定系統(tǒng)在短周期任務(wù)的第一個(gè)周期內(nèi)進(jìn)行同步。如圖6所示，周期和諧的兩個(gè)任務(wù)T1和T2，T1周期為T2的兩倍，在0時(shí)刻T1讀取傳感器數(shù)據(jù)，在T和2T時(shí)刻T2向外界輸出結(jié)果，本文規(guī)定這種欠采樣情況下同步點(diǎn)t1位于任務(wù)T2的第一個(gè)周期內(nèi)，這樣保障T時(shí)刻和2T時(shí)刻的輸出結(jié)果對(duì)應(yīng)于0時(shí)刻的輸入，輸入和輸出之間可以相互確定。圖6系統(tǒng)欠采樣的時(shí)間行為Fig.6Timebehaviorofsystemunder-sampling同理，對(duì)于系統(tǒng)發(fā)生過(guò)采樣的情況，如圖7所示，周期和諧的兩個(gè)任務(wù)T1和T2，T2周期為T1的兩倍，在0時(shí)刻和T時(shí)刻T1讀取傳感器數(shù)據(jù)，在2T時(shí)刻T2向外界輸出結(jié)果，本文規(guī)定兩任務(wù)的同步點(diǎn)t1位于任務(wù)T1的第一個(gè)周期內(nèi)，保障2T時(shí)刻的輸出結(jié)果對(duì)應(yīng)于0時(shí)刻的輸入，輸入和輸出之間關(guān)系可以確定。圖7系統(tǒng)過(guò)采樣的時(shí)間行為Fig.7Timebehaviorofsystemover-sampling任務(wù)中的輸入輸出過(guò)程，在邏輯層次被認(rèn)為是在觸發(fā)時(shí)刻瞬時(shí)執(zhí)行，在具體的物理執(zhí)行平臺(tái)上，輸入輸出過(guò)程勢(shì)必要花費(fèi)一段時(shí)間來(lái)執(zhí)行（即使時(shí)間很短），執(zhí)行過(guò)程處于一個(gè)時(shí)間執(zhí)行區(qū)間上。如圖8所示，對(duì)于外部輸入過(guò)程，邏輯層次在0時(shí)刻執(zhí)行，到物理層次上，其執(zhí)行在一個(gè)時(shí)間區(qū)間[0,t1]上，其中t1為輸入的執(zhí)行時(shí)間長(zhǎng)度；同理，對(duì)于外部輸出過(guò)程，邏輯層次在T時(shí)刻執(zhí)行，到物理層次上，其執(zhí)行在一個(gè)時(shí)間區(qū)間[t2,T]上。圖8時(shí)間映射Fig.8Timemapping對(duì)于內(nèi)部輸入輸出過(guò)程，在邏輯層次上，由于其并非在某確定時(shí)間點(diǎn)定時(shí)觸發(fā)，只需要滿足進(jìn)行同步的兩個(gè)輸入輸出，輸出過(guò)程在輸入過(guò)程之前執(zhí)行。3語(yǔ)法結(jié)構(gòu)3.1組件本文用組件來(lái)統(tǒng)一表示任務(wù)中的I、C、O過(guò)程。組件一共有五種：內(nèi)部輸入組件、外部輸入組件、計(jì)算組件、外部輸出組件、內(nèi)部輸出組件。每個(gè)組件會(huì)被分配一個(gè)執(zhí)行區(qū)間（slot），組件在執(zhí)行區(qū)間執(zhí)行時(shí)不可搶占，組件若提前執(zhí)行完成，可主動(dòng)放棄處理器資源；對(duì)于任務(wù)的輸入輸出組件來(lái)說(shuō)，執(zhí)行區(qū)間即為從邏輯層次映射到物理層次的時(shí)間區(qū)間。組件的執(zhí)行區(qū)間通常設(shè)置為大于或等于其最壞情況執(zhí)行時(shí)間（worst-caseexecutiontime，WCET）的值，避免組件執(zhí)行出現(xiàn)超時(shí)的情況。為了便于分析計(jì)算，執(zhí)行區(qū)間的長(zhǎng)度以離散時(shí)域的時(shí)間粒度（ms）為單位，取整數(shù)值。3.2擴(kuò)展的語(yǔ)法結(jié)構(gòu)如表1所示，TBC擴(kuò)展了7種時(shí)間語(yǔ)法結(jié)構(gòu)，來(lái)表示系統(tǒng)中的任務(wù)、各種組件及其時(shí)間屬性。表1擴(kuò)展的語(yǔ)法結(jié)構(gòu)Table1ExtendedsyntaxstructureTask語(yǔ)法結(jié)構(gòu)用于定義一個(gè)并發(fā)的LET任務(wù)，語(yǔ)法結(jié)構(gòu)顯示聲明了任務(wù)的兩個(gè)參數(shù)：任務(wù)的唯一標(biāo)識(shí)符以及任務(wù)周期。如Task(T1,50){…}表示一個(gè)周期為50ms的LET任務(wù)，Task語(yǔ)法結(jié)構(gòu)大括號(hào)內(nèi)的部分為任務(wù)體，任務(wù)體由三個(gè)組件構(gòu)成，即一個(gè)輸入組件（內(nèi)部輸入組件或者外部輸入組件）、一個(gè)輸出組件（內(nèi)部輸出組件或者外部輸出組件）以及一個(gè)計(jì)算組件。E_I語(yǔ)法結(jié)構(gòu)和I語(yǔ)法結(jié)構(gòu)分別代表外部輸入組件和內(nèi)部輸入組件，兩個(gè)語(yǔ)法結(jié)構(gòu)顯示聲明了任務(wù)輸入的兩個(gè)參數(shù)：輸入組件的標(biāo)識(shí)符以及組件的執(zhí)行區(qū)間長(zhǎng)度；E_O語(yǔ)法結(jié)構(gòu)和O語(yǔ)法結(jié)構(gòu)分別代表外部輸出組件或者內(nèi)部輸出組件，兩個(gè)語(yǔ)法結(jié)構(gòu)顯示聲明了輸出組件的標(biāo)識(shí)符以及組件的執(zhí)行區(qū)間長(zhǎng)度；與PRET-C和文獻(xiàn)[21]中的語(yǔ)言相同，TBC采用全局變量作為任務(wù)間通訊方式。C語(yǔ)法結(jié)構(gòu)代表任務(wù)的計(jì)算組件，顯示聲明了組件標(biāo)識(shí)符和計(jì)算過(guò)程的執(zhí)行區(qū)間長(zhǎng)度。Pre語(yǔ)法結(jié)構(gòu)規(guī)定了任務(wù)之間的數(shù)據(jù)依賴關(guān)系，包括兩個(gè)參數(shù)，分別表示屬于不同任務(wù)的內(nèi)部輸出組件和內(nèi)部輸入組件，任務(wù)通過(guò)這兩個(gè)組件會(huì)進(jìn)行數(shù)據(jù)同步。如對(duì)于兩個(gè)任務(wù)T1、T2,T2數(shù)據(jù)依賴于T1,T2擁有一個(gè)內(nèi)部輸入P2,T1擁有一個(gè)內(nèi)部輸出P1，則可通過(guò)Pre(P1,P2)表示兩個(gè)任務(wù)之間的數(shù)據(jù)依賴關(guān)系。3.3形式化語(yǔ)法本文通過(guò)擴(kuò)展的巴科斯范式（extendedBackus-Naurform，EBNF）來(lái)形式化描述TBC的語(yǔ)法規(guī)則。EBNF是巴科斯范式（Backus-Naurform，BNF）的一種擴(kuò)展，通常作為計(jì)算機(jī)編程語(yǔ)言和形式語(yǔ)言的形式化語(yǔ)法表示方法。TBC的EBNF表示如下所示，其中"c_code"表示常規(guī)的C語(yǔ)言代碼。4編譯技術(shù)本章將介紹TBC特有的編譯技術(shù)。編譯器通過(guò)對(duì)TBC程序中的時(shí)間語(yǔ)法結(jié)構(gòu)進(jìn)行分析處理，最終將其轉(zhuǎn)換為特定的匯編指令。4.1編譯器總體架構(gòu)如圖9所示，TBC編譯器基于LLVM編譯器框架，主要包括編譯器前端、IR和編譯器后端三部分。圖9編譯器總體架構(gòu)Fig.9CompilergeneralarchitectureTBC前端分為詞法分析、語(yǔ)法分析、分析調(diào)度、中間代碼生成四個(gè)過(guò)程。詞法分析和語(yǔ)法分析分別通過(guò)Flex和Bison工具來(lái)實(shí)現(xiàn)。與常規(guī)的編譯器不同，TBC程序經(jīng)過(guò)詞法分析和語(yǔ)法分析后除了生成抽象語(yǔ)法樹(shù)（abstractsyntaxtree，AST）以外，還會(huì)生成TBC特有的中間表示DAG（directedacyclicgraph）和TAST（timedAST）。DAG和TAST分別用于表示TBC程序中的時(shí)序關(guān)系和時(shí)間值信息。兩種中間表示接下來(lái)作為分析調(diào)度器的輸入，經(jīng)過(guò)靜態(tài)分析、調(diào)度后會(huì)生成系統(tǒng)全局的靜態(tài)調(diào)度表。在中間代碼生成階段，抽象語(yǔ)法樹(shù)會(huì)結(jié)合靜態(tài)調(diào)度表的調(diào)度信息生成LLVM的中間語(yǔ)言IR。在TBC編譯器中，本文基于IR擴(kuò)展了具有時(shí)間操作的指令，使得IR擁有定時(shí)觸發(fā)的語(yǔ)義，這里將擴(kuò)展了時(shí)間指令的LLVMIR叫作TIR（timedLLVMIR）。在編譯器的后端，將基于RISCV的時(shí)間語(yǔ)義指令集TTI作為后端的目標(biāo)指令集。如圖10所示，TBC程序經(jīng)過(guò)編譯器各個(gè)步驟進(jìn)行了多次轉(zhuǎn)換，最終映射到匯編指令。在高級(jí)語(yǔ)言層次，TBC通過(guò)擴(kuò)展的語(yǔ)法結(jié)構(gòu)來(lái)表示程序中的時(shí)間語(yǔ)義；表示時(shí)間語(yǔ)義的語(yǔ)法結(jié)構(gòu)在編譯器前端轉(zhuǎn)換為中間表示TAST和DAG，分別表示程序中的時(shí)序關(guān)系和時(shí)間值信息；經(jīng)過(guò)分析調(diào)度后，程序中的時(shí)序關(guān)系和時(shí)間值信息再轉(zhuǎn)換為調(diào)度表所表示的串行時(shí)間行為；中間語(yǔ)言TIR通過(guò)擴(kuò)展時(shí)間操作指令，根據(jù)調(diào)度表中的調(diào)度信息以定時(shí)觸發(fā)的方式驅(qū)動(dòng)系統(tǒng)運(yùn)行；最后經(jīng)過(guò)編譯器后端的指令映射，TIR中的時(shí)間指令最終轉(zhuǎn)換為具有時(shí)間語(yǔ)義的匯編指令TTI。圖10程序轉(zhuǎn)換流程Fig.10Programtranslationflow4.2中間表示在編譯器前端，程序的功能部分和時(shí)間控制部分被分開(kāi)處理。TBC對(duì)于功能部分的處理和普通編譯器相同，通過(guò)詞法分析和語(yǔ)法分析得到AST，并對(duì)AST進(jìn)行相應(yīng)的的語(yǔ)義分析。為了使得編譯器能夠更好地分析處理時(shí)間，TBC編譯器將程序中所有與時(shí)間有關(guān)的信息分為時(shí)序關(guān)系和時(shí)間值信息兩部分，并分別用兩種中間數(shù)據(jù)結(jié)構(gòu)DAG圖和TAST表示。DAG圖用于表示組件之間的時(shí)序關(guān)系，時(shí)序關(guān)系分為兩種。DAG圖如圖11所示，圖中實(shí)線表示不同任務(wù)組件之間的時(shí)序關(guān)系，即程序中Pre語(yǔ)法結(jié)構(gòu)所聲明的任務(wù)之間的數(shù)據(jù)依賴關(guān)系；圖中虛線表示LET任務(wù)內(nèi)固有的時(shí)序關(guān)系，即任務(wù)的計(jì)算組件要在輸入組件和輸出組件之間執(zhí)行。圖11DAG圖Fig.11DAGfigureTAST主要有兩個(gè)作用：一是用于表示系統(tǒng)的結(jié)構(gòu)層次，二是充當(dāng)一個(gè)特殊符號(hào)表。如圖12所示，TAST展現(xiàn)了系統(tǒng)的整體結(jié)構(gòu)，根節(jié)點(diǎn)TBC中每個(gè)分支代表了一個(gè)并發(fā)的LET任務(wù)，而每個(gè)任務(wù)則包含多個(gè)不同類型的組件節(jié)點(diǎn)。同時(shí)作為一個(gè)符號(hào)表，樹(shù)儲(chǔ)存著系統(tǒng)的時(shí)間值信息：每個(gè)任務(wù)節(jié)點(diǎn)儲(chǔ)存任務(wù)的周期值，每個(gè)組件節(jié)點(diǎn)儲(chǔ)存著組件的執(zhí)行區(qū)間長(zhǎng)度。圖12TAST內(nèi)部結(jié)構(gòu)Fig.12InternalstructureofTAST4.3分析與調(diào)度本文采用靜態(tài)調(diào)度的方式，在編譯器前端生成靜態(tài)調(diào)度表，調(diào)度表中指定了組件執(zhí)行的順序和具體時(shí)刻。4.3.1必要性分析在得到TAST后，編譯器便可以檢查系統(tǒng)可調(diào)度的必要條件，即任務(wù)利用率和系統(tǒng)利用率都是否小于等于1。具體的，將任務(wù)各組件執(zhí)行區(qū)間長(zhǎng)度之和除以任務(wù)周期，作為任務(wù)的利用率，所有任務(wù)的利用率都必須要小于等于1，否則終止編譯，并給出錯(cuò)誤信息。將一個(gè)超周期內(nèi)，系統(tǒng)執(zhí)行所有組件用時(shí)總和除以系統(tǒng)的超周期，作為系統(tǒng)的利用率，系統(tǒng)利用率必須小于1，否則同樣終止編譯，并給出錯(cuò)誤信息。用P表示任務(wù)的周期，TT表示系統(tǒng)的超周期，其中TT為所有任務(wù)的最小公倍數(shù)，Ti(Mj)表示任務(wù)i的第j個(gè)組件，slot表示組件的執(zhí)行區(qū)間長(zhǎng)度。必要性分析形式化表示如下，其中N表示系統(tǒng)任務(wù)數(shù)量，Ni表示第i個(gè)任務(wù)組件的數(shù)量。4.3.2調(diào)度表在初步檢查滿足系統(tǒng)可調(diào)度的必要條件后，通過(guò)DAG圖和TAST中的信息進(jìn)行靜態(tài)調(diào)度。本文通過(guò)對(duì)多個(gè)周期任務(wù)進(jìn)行循環(huán)展開(kāi)，來(lái)集成一個(gè)周期為超周期的大循環(huán)塊，靜態(tài)調(diào)度表中的每一個(gè)表項(xiàng)用于表示組件一次執(zhí)行的具體時(shí)間行為，可以通過(guò)三元組(M,t1,t2)來(lái)形式化表示，其中M表示組件的標(biāo)識(shí)符，t1表示組件在循環(huán)塊中的開(kāi)始執(zhí)行時(shí)間，t2表示組件的執(zhí)行區(qū)間長(zhǎng)度。4.3.3調(diào)度規(guī)則對(duì)于系統(tǒng)復(fù)雜的情況，靜態(tài)調(diào)度有可能是個(gè)NP-hard問(wèn)題，常通過(guò)啟發(fā)式算法等來(lái)解決。本文不涉及具體的調(diào)度算法，而是規(guī)定調(diào)度中所要遵循的調(diào)度規(guī)則，調(diào)度規(guī)則主要指靜態(tài)調(diào)度需要遵循的優(yōu)先關(guān)系，主要包括以下兩部分：（1）靜態(tài)調(diào)度需要滿足DAG圖中指定的時(shí)序關(guān)系：同一任務(wù)的計(jì)算組件要在輸入組件和輸出組件之間執(zhí)行；進(jìn)行數(shù)據(jù)同步的兩個(gè)組件，輸入組件要在輸出組件之后執(zhí)行。（2）對(duì)于一個(gè)實(shí)際的系統(tǒng)，會(huì)出現(xiàn)多個(gè)任務(wù)的外部輸入（輸出）同時(shí)定時(shí)觸發(fā)的情況，如兩個(gè)任務(wù)的外部輸入同時(shí)在0時(shí)刻觸發(fā)執(zhí)行，需要指定多個(gè)任務(wù)同時(shí)輸入（輸出）的優(yōu)先順序：首先根據(jù)RM調(diào)度規(guī)則，即任務(wù)的周期越短，其輸入（輸出）越優(yōu)先執(zhí)行；若兩個(gè)任務(wù)的周期相同，則按照任務(wù)的標(biāo)識(shí)符的大小，如兩個(gè)周期相同的任務(wù)T1和T2,T1的輸入（輸出）優(yōu)先于T2的輸入（輸出）。4.3.4調(diào)度表處理調(diào)度表中兩個(gè)相鄰表項(xiàng)之間會(huì)出現(xiàn)存在空閑時(shí)間段的情況，如兩個(gè)相鄰的表項(xiàng)(M1,t1,t2),(M2,t3,t4)，如果t1+t2<t3，則說(shuō)明系統(tǒng)在執(zhí)行兩個(gè)組件之間存在一段空閑時(shí)間，需要在隊(duì)列中加入特定的空閑塊(d,t2,t3-t2)來(lái)表示系統(tǒng)處于空閑狀態(tài)，其中d為空閑塊的標(biāo)識(shí)符。調(diào)度表經(jīng)過(guò)處理后表項(xiàng)分為組件表項(xiàng)(m,t1,t2)和空閑表項(xiàng)(d,t1,t2)兩種，同時(shí)兩個(gè)相鄰的表項(xiàng)之間不存在時(shí)間間隔。<p>4.4中間語(yǔ)言在IR層次，本文擴(kuò)展了具有時(shí)間操作的指令，使得IR可以表示調(diào)度表中組件串行執(zhí)行的時(shí)間行為。本文中將具有時(shí)間指令的LLVMIR叫作TIR。在TIR中，采用時(shí)間觸發(fā)的系統(tǒng)執(zhí)行模式[22]，根據(jù)調(diào)度表中預(yù)先安排的組件時(shí)序行為，來(lái)定時(shí)驅(qū)動(dòng)組件的執(zhí)行，且一次只需要處理一個(gè)組件，時(shí)間觸發(fā)的方式不但可以提高系統(tǒng)的可預(yù)測(cè)性，更便于對(duì)系統(tǒng)功能和時(shí)序的正確性進(jìn)行驗(yàn)證。TIR和TBC基于同樣的離散時(shí)間域，以1ms為時(shí)間粒度，TIR的時(shí)間觸發(fā)方式通過(guò)點(diǎn)時(shí)間來(lái)展現(xiàn)：對(duì)于調(diào)度表中的一個(gè)表項(xiàng)(M1,t1,t2)，代表了系統(tǒng)會(huì)在點(diǎn)時(shí)間t1觸發(fā)組件M的開(kāi)始執(zhí)行，與TBC的并發(fā)執(zhí)行語(yǔ)義不同，在TIR中，組件根據(jù)調(diào)度表中的信息串行執(zhí)行，執(zhí)行時(shí)間為組件的執(zhí)行區(qū)間長(zhǎng)度。TIR擴(kuò)展了絕對(duì)延時(shí)指令delay_until指令，其語(yǔ)義表示從當(dāng)前時(shí)間開(kāi)始延遲到某個(gè)時(shí)間點(diǎn)，如delay_untili3210表示延遲到系統(tǒng)時(shí)間點(diǎn)10ms。同時(shí)TIR擴(kuò)展了兩條時(shí)間初始化指令timeinit和timegran。timegran用于設(shè)置系統(tǒng)的時(shí)間粒度，時(shí)間粒度為μs的整數(shù)倍，如timegrani322表示設(shè)置時(shí)間粒度為2μs。timeinit指令用于設(shè)置當(dāng)前系統(tǒng)時(shí)間。TIR程序的整體結(jié)構(gòu)為一個(gè)大的循環(huán)，TIR程序結(jié)構(gòu)如圖13所示，程序最開(kāi)始時(shí)設(shè)置系統(tǒng)時(shí)間粒度為1ms（與TBC保持一致），每個(gè)循環(huán)開(kāi)始時(shí)重置系統(tǒng)時(shí)間為0，每次循環(huán)系統(tǒng)按調(diào)度表中的調(diào)度信息定時(shí)執(zhí)行組件。圖13TIR程序結(jié)構(gòu)Fig.13TIRprogramstructure對(duì)于調(diào)度表中的表項(xiàng)，將其映射到的TIR指令如圖13所示，如果表項(xiàng)是一個(gè)組件表項(xiàng)，組件功能代碼的轉(zhuǎn)換和普通基于LLVM架構(gòu)的編譯器相同。圖13中，(M1,tstart1,tinterval1)是調(diào)度表中的第一個(gè)表項(xiàng)，組件M1從時(shí)刻tstart1=0開(kāi)始執(zhí)行，通過(guò)絕對(duì)延時(shí)指令delay_until保證M1占用系統(tǒng)時(shí)間到tstart2=tstart1+tinterval1時(shí)刻，因設(shè)置的執(zhí)行區(qū)間長(zhǎng)度tinterval1大于組件的WCET，不會(huì)出現(xiàn)超時(shí)的情況。4.5編譯器后端TIR通過(guò)定時(shí)觸發(fā)的方式來(lái)驅(qū)動(dòng)系統(tǒng)執(zhí)行，因此作為編譯器后端的目標(biāo)指令集需要支持TIR的定時(shí)觸發(fā)語(yǔ)義。本文使用時(shí)間指令集TTI作為TBC編譯器的目標(biāo)指令集，TTI指令集是本實(shí)驗(yàn)室提出的具有時(shí)間語(yǔ)義的指令集，TTI基于RISC-V指令集進(jìn)行時(shí)間語(yǔ)義擴(kuò)展。RISC-V是一個(gè)典型的三操作數(shù)、加載-存儲(chǔ)形式的RISC指令集架構(gòu)，其擴(kuò)展指令分為標(biāo)準(zhǔn)擴(kuò)展和非標(biāo)準(zhǔn)擴(kuò)展兩類，其中非標(biāo)準(zhǔn)擴(kuò)展作為一個(gè)高度特殊化的擴(kuò)展，由用戶根據(jù)功能需求自定義完成，TTI指令集基于RISC-V非標(biāo)準(zhǔn)擴(kuò)展進(jìn)行定義。在TTI中，時(shí)間采用時(shí)間點(diǎn)的形式來(lái)表示，對(duì)于段時(shí)間，通過(guò)段時(shí)間的開(kāi)始時(shí)間點(diǎn)和結(jié)束時(shí)間點(diǎn)來(lái)表示。TTI擴(kuò)展了多個(gè)時(shí)間語(yǔ)義的指令，用來(lái)表示時(shí)間觸發(fā)的語(yǔ)義，擴(kuò)展的指令如下：（1）時(shí)間管理指令：setti/getti指令用于設(shè)置/獲取系統(tǒng)當(dāng)前時(shí)間點(diǎn)；settg指令用于設(shè)置系統(tǒng)當(dāng)前時(shí)間粒度，為了和TIR的時(shí)間粒度統(tǒng)一，將TTI的時(shí)間粒度默認(rèn)設(shè)為1ms。（2）實(shí)時(shí)操作指令：delay指令用于將時(shí)間延遲到一個(gè)絕對(duì)時(shí)間點(diǎn)。LLVM的后端通?？梢苑譃橥ㄓ么a生成器和后端移植接口兩部分，而增加一個(gè)LLVM新后端主要指增加相關(guān)的后端移植接口。后端移植接口主要包括全局描述實(shí)現(xiàn)、寄存器描述實(shí)現(xiàn)、指令集描述實(shí)現(xiàn)、匯編輸出描述實(shí)現(xiàn)等。一般后端信息主要采用LLVM架構(gòu)中的Tablegen語(yǔ)言進(jìn)行后端的描述。TableGen是LLVM中用來(lái)專門描述目標(biāo)后端的語(yǔ)言，主要用于描述子目標(biāo)平臺(tái)、寄存器文件、調(diào)用慣例和指令集等目標(biāo)平臺(tái)相關(guān)信息。TBC編譯器后端基于開(kāi)源項(xiàng)目LLVM-RISCV進(jìn)行擴(kuò)展，擴(kuò)展主要包括TTI時(shí)間指令的擴(kuò)展和TIR時(shí)間指令與TTI時(shí)間指令之間的映射兩部分。本文通過(guò)Tablegen來(lái)描述指令的擴(kuò)展和指令的映射。TIR與TTI的映射關(guān)系如表2所示，本文通過(guò)Tablegen中的DAG匿名匹配模式來(lái)實(shí)現(xiàn)指令的映射。表2指令映射Table2Instructionmapping5實(shí)驗(yàn)設(shè)計(jì)與分析5.1基于TBC構(gòu)建遙控車控制系統(tǒng)本文通過(guò)一個(gè)遙控車控制實(shí)例來(lái)展示如何用TBC構(gòu)建實(shí)時(shí)系統(tǒng)。遙控車控制系統(tǒng)如下：遙控車每隔50ms接受手柄的控制信號(hào)，根據(jù)控制信號(hào)，計(jì)算得到小車當(dāng)前的速度、加速度等狀態(tài)信息，以及控制小車電機(jī)轉(zhuǎn)動(dòng)的PWM波；小車每隔100ms將狀態(tài)信息通過(guò)zigbee通訊模塊傳送給PC端，使得小車的狀態(tài)信息可以被實(shí)時(shí)獲??；同時(shí)小車每隔50ms將PWM波傳送給電機(jī)，電機(jī)驅(qū)動(dòng)車輪轉(zhuǎn)動(dòng)。以上信息可以規(guī)約為一個(gè)外部事件的集合：(E1,I,50),(E2,O,50),(E3,O,100)；事件E1表示接受手柄信號(hào)，E2表示將PWM波傳送給電機(jī)，E3表示將狀態(tài)信息傳送給PC端，該集合作為系統(tǒng)設(shè)計(jì)的時(shí)間需求。由此基于TBC模型構(gòu)建遙控車控制系統(tǒng)如表3所示。遙控車控制系統(tǒng)包括三個(gè)并發(fā)的任務(wù)，其中任務(wù)T1包含輸入事件E1，任務(wù)T2和T3的分別包含輸出事件E2和E3。表3遙控車控制系統(tǒng)任務(wù)集Table3Tasksetofremotecontrolvehiclesystem遙控車控制系統(tǒng)如偽代碼1所示，其中com1到com5表示任務(wù)中的計(jì)算函數(shù)。任務(wù)T1通過(guò)計(jì)算得到小車的狀態(tài)信息和PWM波，通過(guò)內(nèi)部輸出P2將這些數(shù)據(jù)傳送給其他任務(wù)，任務(wù)T2和T3分別通過(guò)內(nèi)部輸入P3和P5獲得T1的輸出數(shù)據(jù)。偽代碼1中的第24、25行“Pre(P2,P3)”“Pre(P2,P5)”用來(lái)表示三個(gè)任務(wù)之間的數(shù)據(jù)依賴關(guān)系。偽代碼1遙控車控制系統(tǒng)TBC程序偽代碼TBC程序經(jīng)過(guò)前端的分析調(diào)度后執(zhí)行序列如圖14所示。對(duì)于外部輸入輸出組件P1、P4和P6，其執(zhí)行位于周期開(kāi)始或結(jié)束的時(shí)刻，其余組件遵照調(diào)度規(guī)則中的優(yōu)先關(guān)系執(zhí)行。圖14組件執(zhí)行序列Fig.14Componentexecutionsequence具體的調(diào)度表信息如下：(P1,0,1),(C1,1,10),(P2,11,1),(P3,12,1),(C2,13,5),(P5,18,1),(C3,19,10),(D,29,20),(P4,49,1),(P1,50,1),(C1,51,10),(P2,61,1),(P3,62,1),(C2,63,5),(D,68,30),(P4,98,1)(P6,99,1)。其中(D,29,20)和(D,68,30)表示系統(tǒng)空閑狀態(tài)，對(duì)應(yīng)圖14中的空白部分。程序經(jīng)過(guò)前端的分析調(diào)度以及后端的指令映射后，最后轉(zhuǎn)換為TTI匯編代碼，匯編程序代碼如偽代碼2所示，這里主要展示TTI程序的時(shí)間行為。偽代碼2遙控車系統(tǒng)TTI程序偽代碼其中第1行到第2行表示系統(tǒng)時(shí)間粒度的設(shè)置，第4行表示每次循環(huán)系統(tǒng)時(shí)間的重