吳中杰，劉江瀾，宋偉，于俊杰，林景明,趙占鋒

1.哈爾濱工業(yè)大學(xué) 電子與信息工程學(xué)院，哈爾濱 150001 2.上海宇航系統(tǒng)工程研究所，上海 201109 3.山東航天電子技術(shù)研究所，煙臺(tái) 264003 4.哈爾濱工業(yè)大學(xué)(威海) 信息與電氣工程學(xué)院，威海264209

可搶占實(shí)時(shí)星載SpaceWire總線(xiàn)網(wǎng)絡(luò)研究

吳中杰1，劉江瀾2，宋偉3，于俊杰3，林景明3,趙占鋒4，*

1.哈爾濱工業(yè)大學(xué) 電子與信息工程學(xué)院，哈爾濱 150001 2.上海宇航系統(tǒng)工程研究所，上海 201109 3.山東航天電子技術(shù)研究所，煙臺(tái) 264003 4.哈爾濱工業(yè)大學(xué)(威海) 信息與電氣工程學(xué)院，威海264209

為基于SpaceWire構(gòu)建統(tǒng)一的星載總線(xiàn)網(wǎng)絡(luò)，需要保證消息傳輸?shù)拇_定性和實(shí)時(shí)性。針對(duì)傳統(tǒng)時(shí)間觸發(fā)通信靈活性不足的缺點(diǎn)，提出了一種支持通信任務(wù)傳輸標(biāo)志符廣播的改進(jìn)時(shí)間觸發(fā)通信SpaceWire總線(xiàn)網(wǎng)絡(luò)；在此基礎(chǔ)上建立了非破壞性可搶占通信機(jī)制，并討論了經(jīng)典的處理器實(shí)時(shí)調(diào)度算法在網(wǎng)絡(luò)通信中的應(yīng)用；最后分析比較了SpaceWire的事件觸發(fā)通信、傳統(tǒng)的時(shí)間觸發(fā)通信與所提出的可搶占實(shí)時(shí)通信的延時(shí)性能。研究表明，提出的通信機(jī)制能夠有效改善信息傳輸?shù)淖顗亩说蕉搜訒r(shí)，適合于多種優(yōu)先級(jí)通信任務(wù)的實(shí)時(shí)調(diào)度。

星載網(wǎng)絡(luò)；SpaceWire；可搶占；實(shí)時(shí)性；確定性

SpaceWire[1]是歐洲航天局面向航天應(yīng)用提出的高速數(shù)據(jù)傳輸總線(xiàn)標(biāo)準(zhǔn)，它采用點(diǎn)對(duì)點(diǎn)、全雙工、串行鏈路，將一系列終端、路由器互聯(lián)，為星載數(shù)據(jù)系統(tǒng)提供高效、靈活、可靠的數(shù)據(jù)傳輸服務(wù)，已成功應(yīng)用于ESA、NASA、JAXA的多個(gè)空間任務(wù)[2]。

總體上，星上數(shù)據(jù)可分為控制類(lèi)和數(shù)據(jù)類(lèi)[3]。前者如周期或非周期的衛(wèi)星時(shí)間、姿態(tài)廣播，注入遙控?cái)?shù)據(jù)等，占用帶寬小，但具有較高的可靠、實(shí)時(shí)性要求；后者如科學(xué)或工程遙測(cè)數(shù)據(jù)等，占用帶寬較大，但可靠性和延遲要求較低。通常采用分立的控制網(wǎng)和數(shù)據(jù)網(wǎng)以適應(yīng)不同數(shù)據(jù)業(yè)務(wù)的需求[4]，前者采用1553B、CAN等低速總線(xiàn)，后者采用同步串/并行LVDS、SpaceWire等高速總線(xiàn)。

分立的網(wǎng)絡(luò)不利于接口標(biāo)準(zhǔn)和通信協(xié)議的統(tǒng)一，基于標(biāo)準(zhǔn)技術(shù)構(gòu)建統(tǒng)一的星載網(wǎng)絡(luò)，簡(jiǎn)化系統(tǒng)設(shè)計(jì)與集成，是目前的研究熱點(diǎn)[5-6]?；赟paceWire的星載網(wǎng)絡(luò)的問(wèn)題在于網(wǎng)絡(luò)阻塞導(dǎo)致的傳輸延時(shí)的不確定性。SpaceWire路由器采用蟲(chóng)洞路由機(jī)制，事件觸發(fā)的數(shù)據(jù)傳輸對(duì)網(wǎng)絡(luò)資源的爭(zhēng)用會(huì)導(dǎo)致嚴(yán)重的阻塞。文獻(xiàn)[7]研究了SpaceWire時(shí)間觸發(fā)網(wǎng)絡(luò)的延時(shí)性能，指出最壞端到端延時(shí)隨通信鏈路的增長(zhǎng)而急劇增大，這對(duì)關(guān)鍵的星上命令、控制數(shù)據(jù)是不能接受的。因此，有必要研究保證SpaceWire網(wǎng)絡(luò)確定性和實(shí)時(shí)性的方法。文獻(xiàn)[8]采用靜態(tài)優(yōu)先級(jí)分配方法，但SpaceWire只有兩個(gè)優(yōu)先級(jí)，難以滿(mǎn)足復(fù)雜應(yīng)用需要。文獻(xiàn)[9]提出利用SpaceWire時(shí)間廣播機(jī)制，建立時(shí)間觸發(fā)同步網(wǎng)絡(luò)，其本質(zhì)上是一種網(wǎng)絡(luò)資源的時(shí)分復(fù)用TDMA。文獻(xiàn)[10]進(jìn)一步討論了SpaceWire時(shí)間觸發(fā)服務(wù)，設(shè)計(jì)了時(shí)間和事件觸發(fā)混合的通信方式。文獻(xiàn)[11]研究了混合模式下的傳輸延時(shí)。文獻(xiàn)[12]提出了SpaceWire-D協(xié)議，利用時(shí)間觸發(fā)傳輸、有限數(shù)據(jù)包長(zhǎng)和遠(yuǎn)程存儲(chǔ)器訪(fǎng)問(wèn)協(xié)議RMAP，確保數(shù)據(jù)傳輸?shù)目煽啃院痛_定性。文獻(xiàn)[13]綜合考慮網(wǎng)絡(luò)資源沖突、數(shù)據(jù)傳輸因果關(guān)系，統(tǒng)一規(guī)劃使節(jié)點(diǎn)在確定時(shí)間窗口內(nèi)發(fā)送數(shù)據(jù)，避免網(wǎng)絡(luò)資源沖突，保障傳輸確定性、實(shí)時(shí)性。

之前研究的主要不足之處有：時(shí)間觸發(fā)傳輸實(shí)質(zhì)上是一種離線(xiàn)的靜態(tài)調(diào)度，靈活性不足。時(shí)隙分配后即固定不變，難以適應(yīng)星上工作模式的變化。TDMA的周期性特點(diǎn)，使其適合調(diào)度周期信息，對(duì)于非周期信息，應(yīng)按照其最小間隔固定分配帶寬，造成資源浪費(fèi)。如果一個(gè)就緒消息時(shí)剛好錯(cuò)過(guò)了為其分配的時(shí)隙，只能等待下一個(gè)次時(shí)隙，增大了傳輸延時(shí)等。

為克服以上缺點(diǎn)，本文提出了改進(jìn)的通信機(jī)制，支持在線(xiàn)動(dòng)態(tài)的通信調(diào)度，旨在減小消息的最壞延遲，保證傳輸?shù)拇_定性和實(shí)時(shí)性，可用于構(gòu)建基于SpaceWire標(biāo)準(zhǔn)的統(tǒng)一的星載通信網(wǎng)絡(luò)。

1 改進(jìn)的時(shí)間觸發(fā)通信

傳統(tǒng)的時(shí)間觸發(fā)通信利用SpaceWire時(shí)間廣播機(jī)制將時(shí)間劃分成循環(huán)的基本通信周期，一個(gè)周期由若干等長(zhǎng)時(shí)隙構(gòu)成，每個(gè)終端僅在為其分配的一個(gè)或多個(gè)時(shí)隙內(nèi)通信。

1.1 網(wǎng)絡(luò)時(shí)間基準(zhǔn)及其精度

SpaceWire允許一個(gè)時(shí)間主節(jié)點(diǎn)周期性地廣播時(shí)間字符，以提供網(wǎng)絡(luò)時(shí)間基準(zhǔn)。廣播間隔稱(chēng)為網(wǎng)絡(luò)時(shí)間單位Tnet，即一個(gè)時(shí)隙長(zhǎng)度。時(shí)間字符結(jié)構(gòu)如圖1所示。

圖1 SpaceWire時(shí)間字符Fig.1 SpaceWire time character

由圖1可知，時(shí)間字符由一個(gè)轉(zhuǎn)義字符和一個(gè)數(shù)據(jù)字符組成。時(shí)間字符中，T0～T5為6位時(shí)間碼；C0～C1為2位控制碼，其含義由用戶(hù)自定義。

網(wǎng)絡(luò)時(shí)基精度取決于時(shí)間字符在網(wǎng)內(nèi)傳播的延時(shí)和抖動(dòng)。時(shí)間字符最大傳輸延時(shí)為：

式中：p為時(shí)間主節(jié)點(diǎn)到最遠(yuǎn)節(jié)點(diǎn)之間的鏈路數(shù)目；r為傳輸速率；系數(shù)14表示一個(gè)時(shí)間字符的長(zhǎng)度為14位。

如果要發(fā)送時(shí)間字符時(shí)，鏈路剛好正在發(fā)送一個(gè)數(shù)據(jù)字符，會(huì)導(dǎo)致時(shí)間字符發(fā)送抖動(dòng)，使各時(shí)隙的長(zhǎng)短有輕微差異。時(shí)間字符的最大傳輸抖動(dòng)為：

式中：系數(shù)10表示1個(gè)數(shù)據(jù)字符的長(zhǎng)度為10位。

顯然，網(wǎng)絡(luò)時(shí)間單位應(yīng)滿(mǎn)足：

Tnet≥tc_delay+tc_jitter

1.2 數(shù)據(jù)分片傳輸

SpaceWire標(biāo)準(zhǔn)未限制一次傳輸?shù)淖畲髷?shù)據(jù)長(zhǎng)度。為確保一次數(shù)據(jù)傳輸能夠在一個(gè)時(shí)隙內(nèi)完成，必須設(shè)置一個(gè)最大傳輸單元長(zhǎng)度。在發(fā)送端，需要有對(duì)應(yīng)用層數(shù)據(jù)幀進(jìn)行分片的機(jī)制；在接收節(jié)端，分片又被組合成完整的應(yīng)用層數(shù)據(jù)幀。圖2顯示了一個(gè)長(zhǎng)度為m字節(jié)的數(shù)據(jù)片在網(wǎng)絡(luò)中無(wú)阻塞傳輸時(shí)的端到端延時(shí)：

式中：p為端到端鏈路數(shù)目；tb為電信號(hào)在鏈路上的傳播時(shí)延；tsw為路由器交換時(shí)延；r為傳輸速率。式中忽略了因?yàn)榘l(fā)送流量控制字符和時(shí)間字符造成的延時(shí)。

要保證一個(gè)數(shù)據(jù)片在一個(gè)時(shí)隙內(nèi)傳輸完成，需滿(mǎn)足：

圖2 數(shù)據(jù)片在網(wǎng)絡(luò)中無(wú)阻塞傳輸時(shí)的端到端時(shí)延Fig.2 Minimum end-to-end delay of the data slice transferred across the network without block

式中：系數(shù)b的值應(yīng)略小于1，為保留的時(shí)隙余量和數(shù)據(jù)分片開(kāi)銷(xiāo)。由式(3)和式(4)可以解得：

應(yīng)當(dāng)適當(dāng)選擇m與Tnet的值。如果選擇太大，則分片與時(shí)隙的粒度太大；如果太小，則會(huì)增加數(shù)據(jù)分片與時(shí)間碼廣播開(kāi)銷(xiāo)。

1.3 改進(jìn)的時(shí)間觸發(fā)通信

在傳統(tǒng)時(shí)間觸發(fā)通信中，時(shí)間碼所代表當(dāng)前的系統(tǒng)時(shí)間，其值每隔Tnet加1。在本文提出的改進(jìn)的時(shí)間觸發(fā)通信中，時(shí)間碼還被賦予了傳輸標(biāo)識(shí)符(TID)的含義。每個(gè)通信任務(wù)都被指配了TID，全網(wǎng)廣播某TID時(shí)，擁有此TID的終端允許發(fā)起通信。因此，時(shí)間碼不一定連續(xù)遞增，也不一定按照固定時(shí)間間隔發(fā)送。時(shí)間字符中除了6位時(shí)間碼，還有2位控制碼，使用控制碼C1C0的值表示當(dāng)前網(wǎng)絡(luò)工作狀態(tài)和時(shí)間碼類(lèi)型，如表1所示。

表1 SpaceWire網(wǎng)絡(luò)工作狀態(tài)

Table 1 Operating states of theSpaceWire network

C1C0當(dāng)前網(wǎng)絡(luò)工作狀態(tài)C1C0當(dāng)前網(wǎng)絡(luò)工作狀態(tài)0靜止?fàn)顟B(tài)2無(wú)競(jìng)爭(zhēng)通信狀態(tài)1同步建立狀態(tài)3競(jìng)爭(zhēng)通信狀態(tài)

由表1可知，共定義了4種網(wǎng)絡(luò)工作狀態(tài)，對(duì)應(yīng)于4種類(lèi)型的時(shí)間碼。在靜止?fàn)顟B(tài)下，廣播0型時(shí)間碼，所有終端都不允許通信；無(wú)競(jìng)爭(zhēng)通信狀態(tài)下，廣播2型時(shí)間碼，只有TID指定的終端才可以發(fā)起通信，此時(shí)網(wǎng)絡(luò)資源被獨(dú)占，傳輸延遲可以保證；競(jìng)爭(zhēng)通信狀態(tài)下，廣播3型時(shí)間碼，所有終端隨時(shí)可以發(fā)起通信，此時(shí)網(wǎng)絡(luò)中可能發(fā)生阻塞。處于靜止、無(wú)競(jìng)爭(zhēng)通信或競(jìng)爭(zhēng)通信狀態(tài)時(shí)，時(shí)間碼以Tnet為間隔連續(xù)遞增，網(wǎng)絡(luò)保持時(shí)間同步；當(dāng)從靜止、競(jìng)爭(zhēng)通信狀態(tài)進(jìn)入無(wú)競(jìng)爭(zhēng)通信狀態(tài)，或者由一個(gè)無(wú)競(jìng)爭(zhēng)通信切換到另一個(gè)無(wú)競(jìng)爭(zhēng)通信時(shí)，時(shí)間主節(jié)點(diǎn)要停止連續(xù)時(shí)間碼的發(fā)送，轉(zhuǎn)而發(fā)送1型時(shí)間碼和指定的TID，重新同步網(wǎng)絡(luò)。

每個(gè)SpaceWire終端/路由器都有一個(gè)時(shí)間碼寄存器。當(dāng)終端/路由器收到一個(gè)新的時(shí)間字符時(shí)，會(huì)將時(shí)間碼值與寄存器的值進(jìn)行比較，如果時(shí)間碼值等于寄存器值加1，則判斷為有效時(shí)間碼，路由器向除收到此時(shí)間字符的端口外的所有端口廣播此時(shí)間字符，終端向用戶(hù)接口報(bào)告這個(gè)新時(shí)間字符；否則，被認(rèn)為是一個(gè)無(wú)效時(shí)間碼，路由器不會(huì)進(jìn)行廣播，終端也不會(huì)向用戶(hù)報(bào)告，但時(shí)間碼寄存器會(huì)被更新為新時(shí)間碼值。圖3顯示了不連續(xù)時(shí)間碼在網(wǎng)絡(luò)中傳播的情況。

圖3 不連續(xù)時(shí)間碼在網(wǎng)絡(luò)中的傳輸Fig.3 Broadcasting of discontinuous time codes in the network

設(shè)時(shí)間主節(jié)點(diǎn)到最遠(yuǎn)終端之間共有p段鏈路，重建同步需要至少?gòu)V播p+1個(gè)連續(xù)的1類(lèi)時(shí)間碼，且第一個(gè)1類(lèi)時(shí)間碼的值應(yīng)為T(mén)ID—p-1，設(shè)置廣播間隔tsync遠(yuǎn)小于Tnet且大于時(shí)間碼的延遲和抖動(dòng)。收到1型時(shí)間碼后，終端將中止當(dāng)前的發(fā)送，并將隨后收到的第一個(gè)2型時(shí)間碼當(dāng)作TID，持有此TID的節(jié)點(diǎn)允許發(fā)起傳輸，而其他終端保持靜默。此后，主節(jié)點(diǎn)以間隔Tnet廣播連續(xù)的2型時(shí)間碼，直到為本次傳輸分配的時(shí)隙用盡，或者本次傳輸被搶占。

圖4顯示了一個(gè)網(wǎng)絡(luò)工作狀態(tài)轉(zhuǎn)換過(guò)程的示例。網(wǎng)絡(luò)開(kāi)始處于靜止?fàn)顟B(tài)，隨后進(jìn)入競(jìng)爭(zhēng)通信狀態(tài)，隨后TID=3的傳輸占用網(wǎng)絡(luò)4個(gè)時(shí)隙，接著TID=22的傳輸占用網(wǎng)絡(luò)2個(gè)時(shí)隙，接下來(lái)的2個(gè)時(shí)隙又被TID=3的傳輸占用。之后，網(wǎng)絡(luò)又進(jìn)入競(jìng)爭(zhēng)通信狀態(tài)和靜止?fàn)顟B(tài)。

圖4 網(wǎng)絡(luò)狀態(tài)轉(zhuǎn)換示例Fig.4 An example of network states transition

2 可搶占實(shí)時(shí)SpaceWire通信

建立了改進(jìn)的SpaceWire時(shí)間觸發(fā)通信網(wǎng)絡(luò)，就可以實(shí)現(xiàn)時(shí)間主節(jié)點(diǎn)控制下的非破壞性可搶占實(shí)時(shí)通信調(diào)度。其中，可搶占指新就緒的無(wú)競(jìng)爭(zhēng)通信可以搶占競(jìng)爭(zhēng)通信，高優(yōu)先級(jí)競(jìng)爭(zhēng)通信可以搶占低優(yōu)先級(jí)競(jìng)爭(zhēng)通信；非破壞性指搶占不會(huì)導(dǎo)致不完整的數(shù)據(jù)包，這是通過(guò)將搶占點(diǎn)設(shè)置在時(shí)隙結(jié)束時(shí)刻保證的。實(shí)時(shí)指保證所有通信都在其截止時(shí)間前完成。

2.1 非破壞性可搶占通信

將SpaceWire總線(xiàn)網(wǎng)絡(luò)抽象為有向圖G(N,L)，N代表網(wǎng)絡(luò)中所有節(jié)點(diǎn)(終端與路由器)的集合，L代表連接兩節(jié)點(diǎn)的邊的集合。使用兩條反向的邊代表節(jié)點(diǎn)之間的雙向鏈路。不考慮SpaceWire組自適應(yīng)路由，即假設(shè)從源終端到目的終端的路徑是唯一的。將一個(gè)通信任務(wù)記為f，網(wǎng)絡(luò)中所有通信任務(wù)的集合記為F。對(duì)于?f∈F，可以表示為：

式中：c為一次通信數(shù)據(jù)量，單位為字節(jié)；t為任務(wù)兩次就緒的周期或最小間隔；d為任務(wù)截止時(shí)間；函數(shù)links(f)按序返回f所經(jīng)過(guò)的所有鏈路的集合；函數(shù)pri(f)返回f的優(yōu)先級(jí)，規(guī)定優(yōu)先級(jí)數(shù)值越小，優(yōu)先級(jí)越高。時(shí)間t內(nèi)需要為通信f分配的時(shí)隙數(shù)目：

(6)

式中：m表示一個(gè)時(shí)隙內(nèi)允許傳送的最大數(shù)據(jù)量，單位字節(jié)；符號(hào)「*?表示向上取整。

給出以下定義：

定義1 稱(chēng)通信f與f′為相容通信，如果滿(mǎn)足條件：

links(f)∩links(f′)=?

定義2 稱(chēng)集合E?F為相容通信集，如果對(duì)于?f,f′∈E，f與f′都是相容通信。

定義3 稱(chēng)H={E1,E2,…,Em}為F的一個(gè)劃分，如果滿(mǎn)足：

1)?Ei∈H，Ei為相容通信集；

2)?Ei,Ej∈H，Ei∩Ej=?；

3)∪Ei∈HEi=F。

顯然，相容通信可以同時(shí)在網(wǎng)絡(luò)中無(wú)阻塞地傳輸，搶占只發(fā)生在兩個(gè)不相容的通信之間。因此，沒(méi)有必要為每一個(gè)f分配一個(gè)TID，只需要為一個(gè)劃分H中的每個(gè)相容通信集E分配TID。

通信搶占過(guò)程描述如下：

步驟1 在調(diào)度時(shí)間點(diǎn)(即時(shí)隙結(jié)束時(shí)刻，一個(gè)數(shù)據(jù)分片剛好被傳輸完時(shí))，檢查就緒任務(wù)表。如果沒(méi)有無(wú)競(jìng)爭(zhēng)通信任務(wù)就緒，網(wǎng)絡(luò)進(jìn)入靜止或競(jìng)爭(zhēng)通信狀態(tài)，時(shí)間主節(jié)點(diǎn)繼續(xù)發(fā)送連續(xù)時(shí)間碼，仍處于步驟1；否則，記所有就緒的無(wú)競(jìng)爭(zhēng)通信的集合為Frdy，記其中優(yōu)先級(jí)最高的通信任務(wù)為f，其所屬的相容通信集為Ef，執(zhí)行步驟2。

步驟2 如果當(dāng)前網(wǎng)絡(luò)正處于靜止或競(jìng)爭(zhēng)通信狀態(tài)，重新同步網(wǎng)絡(luò)，廣播Ef的TID，通信任務(wù)集合Frdy∩Ef占用網(wǎng)絡(luò)，轉(zhuǎn)入無(wú)競(jìng)爭(zhēng)通信狀態(tài)，執(zhí)行步驟4；如果當(dāng)前網(wǎng)絡(luò)正處于無(wú)競(jìng)爭(zhēng)通信狀態(tài)，且占用網(wǎng)絡(luò)的優(yōu)先級(jí)最高的通信任務(wù)為fcurr，執(zhí)行步驟3。

步驟3 如果fcurr=f或者fcurr∈Ef，又或者pri(fcurr)

步驟4 調(diào)度算法決定的通信任務(wù)占用網(wǎng)絡(luò)，發(fā)送最長(zhǎng)m字節(jié)的數(shù)據(jù)片，時(shí)隙耗盡后，將該任務(wù)的剩余時(shí)隙數(shù)減1，執(zhí)行步驟1。

2.2 通信任務(wù)的實(shí)時(shí)調(diào)度

闡明了改進(jìn)的時(shí)間觸發(fā)通信與非破壞性可搶占通信的原理后，一些處理器經(jīng)典可搶占實(shí)時(shí)調(diào)度算法可以被用于通信任務(wù)的調(diào)度。

可以根據(jù)系統(tǒng)需要為通信任務(wù)人為指定優(yōu)先級(jí)。這種方式符合星載應(yīng)用簡(jiǎn)單、可靠的要求，但靈活性不足，難以實(shí)現(xiàn)最佳調(diào)度。

比率單調(diào)調(diào)度算法RMS是最佳靜態(tài)優(yōu)先級(jí)調(diào)度算法[14]，該算法的主要假設(shè)包括：所有任務(wù)都是周期性任務(wù)；任務(wù)截止時(shí)間等于任務(wù)周期；任務(wù)可以在任何位置被搶占，不存在臨界區(qū)；每次任務(wù)執(zhí)行時(shí)間為常量等。RMS算法令任務(wù)優(yōu)先級(jí)與任務(wù)周期成單調(diào)關(guān)系，任務(wù)周期越短，優(yōu)先級(jí)越高；任務(wù)周期越長(zhǎng)，優(yōu)先級(jí)越低。星上通信任務(wù)往往具有周期性特點(diǎn)，對(duì)于非周期性任務(wù)，可以將其最小間隔作為周期。當(dāng)時(shí)隙相對(duì)于任務(wù)總執(zhí)行時(shí)間足夠小時(shí)，可以認(rèn)為通信在任何時(shí)間點(diǎn)都能夠被搶占。因此，RMS算法的假設(shè)在本文的通信任務(wù)的實(shí)時(shí)調(diào)度中成立。假設(shè)所有通信任務(wù)都是不相容的，所有任務(wù)可以被實(shí)時(shí)調(diào)度的充分條件為：

式中：N為任務(wù)個(gè)數(shù)；ni表示為通信任務(wù)fi所分配的時(shí)隙個(gè)數(shù)；ti為任務(wù)周期。RMS調(diào)度算法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，缺點(diǎn)是網(wǎng)絡(luò)的利用率比較低。

截止時(shí)間優(yōu)先調(diào)度算法EDF是最優(yōu)的動(dòng)態(tài)調(diào)度算法[15]，該算法并不要求所有任務(wù)都是周期的，其余假設(shè)與RMS算法類(lèi)似。EDF算法令任務(wù)優(yōu)先級(jí)與任務(wù)的截止時(shí)間成單調(diào)關(guān)系，任務(wù)截止時(shí)間越近，優(yōu)先級(jí)越高；任務(wù)截止時(shí)間越遠(yuǎn)，優(yōu)先級(jí)越低。任務(wù)可以被實(shí)時(shí)調(diào)度的充分必要條件為：

式中：ti為任務(wù)的截止時(shí)間。EDF算法的優(yōu)點(diǎn)是網(wǎng)絡(luò)利用率較高，缺點(diǎn)是實(shí)現(xiàn)比較復(fù)雜。

3 SpaceWire網(wǎng)絡(luò)延時(shí)性能分析

下面分析比較幾種SpaceWire通信網(wǎng)絡(luò)的延時(shí)性能，推導(dǎo)了最小/最大延時(shí)的計(jì)算方法并通過(guò)算例進(jìn)行說(shuō)明。在分析中，進(jìn)行以下的理想化假設(shè)：

1) 忽略電信號(hào)在鏈路上的傳播延時(shí)和路由器的交換延時(shí)；

2) 忽略各終端節(jié)點(diǎn)內(nèi)部處理延時(shí)，如內(nèi)部總線(xiàn)讀寫(xiě)時(shí)間，中斷生成、響應(yīng)和處理時(shí)間，中斷造成的時(shí)間碼發(fā)送推遲等。

圖5給出了算例的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，表2列出了網(wǎng)絡(luò)中所有通信任務(wù)，所有任務(wù)都是不相容的。設(shè)數(shù)據(jù)傳輸速率r=20 Mbit/s；N6為時(shí)間主節(jié)點(diǎn)，網(wǎng)絡(luò)最長(zhǎng)鏈路p=3，根據(jù)式(1)、(2)計(jì)算可得，時(shí)間字符最大傳輸延遲和抖動(dòng)為3.6 μs，因此取網(wǎng)絡(luò)時(shí)間單位Tnet=100 μs；令系數(shù)b=0.8，根據(jù)式(5)計(jì)算得m=155 byte；根據(jù)式(6)可以計(jì)算得到為各任務(wù)分配的時(shí)隙數(shù)目ni；設(shè)置網(wǎng)絡(luò)重新同步時(shí)時(shí)間碼廣播間隔tsync=5 μs。

圖5 算例的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.5 Network topology of the example

fi源目的ci∕Kbyteti∕ms1N1N6142N3N62163N5N64404N2N610505N4N61001000

3.1 事件觸發(fā)通信延時(shí)性能

根據(jù)式(3)可以計(jì)算得到通信任務(wù)fi在事件觸發(fā)SpaceWire網(wǎng)絡(luò)中無(wú)阻塞傳輸時(shí)的最小延時(shí)dmin(fi)。

文獻(xiàn)[7]給出計(jì)算最大延時(shí)的遞推方法，這種方法假設(shè)所有通信任務(wù)隨時(shí)會(huì)就緒，但實(shí)際中一個(gè)通信任務(wù)兩次就緒之間一般存在最小時(shí)間間隔，因此需要進(jìn)行一定修正。

首先，給出如下約定：記通信任務(wù)fi經(jīng)過(guò)的第一條鏈路為l1st，最后一條鏈路為llast；函數(shù)next(fi,l)返回當(dāng)前鏈路l的下一跳鏈路，函數(shù)next(fi,l)返回當(dāng)前鏈路l的上一跳鏈路，規(guī)定next(fi,llast)=null。記d(fi,l)為從鏈路l到目的終端的最大延時(shí)。定義數(shù)據(jù)發(fā)送延時(shí)為：

下面給出遞推計(jì)算過(guò)程。當(dāng)l=llast時(shí)，有：

式中：Pl表示l的所有前一跳鏈路的集合，即

Pl={l′∈L|?f′∈F,l′=prev(f′,l)}；

Fl′l表示經(jīng)過(guò)鏈路l′和l的所有任務(wù)的集合，即

Fl′l={f∈F|l′,l∈links(f), l′=prev(f,l)}

當(dāng)l≠l1st且l≠llast時(shí)，有：

當(dāng)l=l1st時(shí)，有：

式中：Sf為與f具有相同源節(jié)點(diǎn)的所有任務(wù)的集合。任務(wù)fi的最大傳輸延遲可以表示為：

下面通過(guò)算例說(shuō)明計(jì)算過(guò)程，由式(8)～(11)可得：

d(f1,l1)=d(f1,l7)=

d(f1,l11)+d(f2,l11)+d(f4,l11)=

d(f1,null)+d(f2,null)+3d(f3,null)+

d(f4,null)+3d(f5,null)

式中的第一項(xiàng)表示f1的無(wú)阻塞通信時(shí)間，其他項(xiàng)表示f1被阻塞的時(shí)間，其中系數(shù)大于1的項(xiàng)表示該任務(wù)多次就緒阻塞f1。例如，式中f5就緒了3次，但實(shí)際上設(shè)定f5的周期為1 000 ms，在阻塞期內(nèi)只可能就緒1次。因此，需要引入修正項(xiàng)刪除這些重復(fù)就緒的任務(wù)，修正后：

dmax(f1)= d(f1,null)+d(f2,null)+

2d(f3,null)+d(f4,null)+

d(f5,null)

同理，可以計(jì)算得到其他通信任務(wù)的最大延遲。本算例中，在事件觸發(fā)通信機(jī)制下，各通信任務(wù)的最小/最大傳輸延時(shí)計(jì)算結(jié)果如表3所示。

3.2 傳統(tǒng)的時(shí)間觸發(fā)通信延時(shí)性能

在傳統(tǒng)的時(shí)間觸發(fā)通信機(jī)制中，通信任務(wù)fi的傳輸延時(shí)等于已就緒任務(wù)等待傳輸時(shí)隙的時(shí)間加上占用時(shí)隙進(jìn)行無(wú)阻塞傳輸?shù)臅r(shí)間。因此，當(dāng)數(shù)據(jù)恰好無(wú)等待地進(jìn)行傳輸時(shí)，有最小延時(shí)：

式中：ni表示為fi一次通信分配的時(shí)隙數(shù)；Tnet為網(wǎng)絡(luò)時(shí)間單位。最大延時(shí)應(yīng)等于兩次通信時(shí)隙之間的間隔：

式中：ti為通信任務(wù)fi兩次就緒的最小間隔。

本算例中，在傳統(tǒng)的時(shí)間觸發(fā)通信機(jī)制下，各通信任務(wù)的最小/最大延時(shí)計(jì)算結(jié)果如表3所示。

3.3 可搶占實(shí)時(shí)通信延時(shí)性能

在本文提出的通信機(jī)制中，如果通信任務(wù)fi剛就緒就立刻占用網(wǎng)絡(luò)直到傳輸完成時(shí)，有最小延時(shí)：

總延時(shí)包括網(wǎng)絡(luò)重新同步時(shí)間加上占網(wǎng)絡(luò)進(jìn)行傳輸?shù)臅r(shí)間。

最大延時(shí)可以表示為：

式中：Hf為優(yōu)先級(jí)高于f的通信任務(wù)的集合。式(16)等號(hào)右側(cè)第一項(xiàng)表示等待任務(wù)調(diào)度點(diǎn)的時(shí)間，第二項(xiàng)表示高優(yōu)先級(jí)通信任務(wù)搶占網(wǎng)絡(luò)造成的延時(shí)，第三項(xiàng)表示通信任務(wù)進(jìn)行數(shù)據(jù)發(fā)送的時(shí)間。由于式(16)中，dmax(fi)同時(shí)出現(xiàn)在等號(hào)的兩側(cè)，難以寫(xiě)出形式化的解，可以采用迭代的方法求解：

在算例中，將非周期性的通信任務(wù)看成周期性的，將就緒的最小間隔看作其周期，令任務(wù)的截止時(shí)間等于其周期。根據(jù)完成時(shí)限為各任務(wù)分配固定的優(yōu)先級(jí)，任務(wù)時(shí)限越短，優(yōu)先級(jí)越高。式(7)的計(jì)算結(jié)果表明，網(wǎng)絡(luò)中的通信任務(wù)可以被RMS算法調(diào)度。根據(jù)式(15)、式(17)計(jì)算得到可搶占實(shí)時(shí)通信網(wǎng)絡(luò)中各任務(wù)的最小/最大延時(shí)，見(jiàn)表3。

3.4 各類(lèi)通信機(jī)制延時(shí)性能分析

算例中的各通信任務(wù)在不同的通信機(jī)制下的最小/最大傳輸延時(shí)的計(jì)算結(jié)果如表3所示。

對(duì)于最小傳輸延時(shí)，事件觸發(fā)通信最小延時(shí)值最?。欢鴷r(shí)間觸發(fā)通信最小延時(shí)要略大，這是保留時(shí)隙余量和數(shù)據(jù)分片導(dǎo)致的；可搶占實(shí)時(shí)通信最小延時(shí)最大，因?yàn)檫€要再加上廣播TID的開(kāi)銷(xiāo)。

對(duì)于最大傳輸延遲，事件觸發(fā)通信中，各任務(wù)爭(zhēng)用網(wǎng)絡(luò)導(dǎo)致互相阻塞，使一些任務(wù)的最大延遲超過(guò)了其完成時(shí)限；在時(shí)間觸發(fā)的通信中，網(wǎng)絡(luò)資源的固定分配給各任務(wù)進(jìn)行時(shí)分復(fù)用，在最壞情況下也能保證任務(wù)在截止時(shí)間前完成；在無(wú)阻塞實(shí)時(shí)通信中，為各任務(wù)指定優(yōu)先級(jí)，實(shí)現(xiàn)網(wǎng)絡(luò)資源的“按需分配”，有效減小了最大延時(shí)。

可以通過(guò)改變?nèi)蝿?wù)的優(yōu)先級(jí)來(lái)改變最大延時(shí)，表4顯示了在其他任務(wù)相對(duì)優(yōu)先級(jí)與上文保持不變時(shí)，改變?nèi)蝿?wù)f5的優(yōu)先級(jí)時(shí)其最大延時(shí)的變化情況。

表3 通信任務(wù)的最小/最大延時(shí)

Table 3 The min./max.delay of communication tasks

傳輸延時(shí)/msfi事件觸發(fā)時(shí)間觸發(fā)可搶占實(shí)時(shí)minmaxminmaxminmax10 5060 500 704 000 720 8221 0060 501 3016 001 322 1632 0057 002 6040 002 625 5445 0060 506 5050 006 5213 56550 0057 0064 601000 0064 62131 38

表4 不同優(yōu)先級(jí)時(shí)任務(wù)f5的最大延時(shí)

Table 4 The min./max. delay of communication tasks

優(yōu)先級(jí)12345最大延時(shí)/ms64 7279 5289 78101 26131 38

4 結(jié)束語(yǔ)

星載電子系統(tǒng)的重要發(fā)展趨勢(shì)是采用統(tǒng)一的網(wǎng)絡(luò)技術(shù)連接星載設(shè)備，以增強(qiáng)組件的兼容性、重用性和可靠性，降低系統(tǒng)開(kāi)發(fā)成本和時(shí)間。為了基于SpaceWire標(biāo)準(zhǔn)構(gòu)建統(tǒng)一的星載總線(xiàn)網(wǎng)絡(luò)，本文對(duì)SpaceWire的無(wú)阻塞實(shí)時(shí)通信展開(kāi)研究。首先建立了改進(jìn)的時(shí)間觸發(fā)通信的概念，提出了非破壞性可搶占通信機(jī)制，采用實(shí)時(shí)調(diào)度算法保證通信任務(wù)滿(mǎn)足實(shí)時(shí)性要求。理論證明和算例分析表明，本文提出的通信機(jī)制可以有效改善網(wǎng)絡(luò)中消息的最壞時(shí)延，適合于多種優(yōu)先級(jí)通信任務(wù)的實(shí)時(shí)調(diào)度。

References)

[1] ECSS-E-ST-50-12C. SpaceWire: links, nodes, routers and networks[S]. Noordwijk: ECSS, 2008:13-14.

[2] STEVE P, PHILIPPE A, YURIY S, et al. SpaceWire missions and architectures[C]∥Proceedings of The 60th International Astronautical Congress. Paris: IAF, 2009: 2963-2970.

[3] 侯劍儒，陳曉敏. SpaceWire時(shí)延抖動(dòng)的仿真[J]. 國(guó)防科技大學(xué)學(xué)報(bào)，2013，35(5)：114-119.

HOU J R, CHEN X M. The simulation on the delay jitter of SpaceWire[J]. Journal of National University of Defense Technology, 2013, 35(5): 114-119(in Chinese).

[4] TUNESI L, ARMBRUSTER P. Onboard hierarchical network[C]∥Proceedings of SPIE. Bellingham: SPIE, 2004: 539-549.

[5] CORBACHEV S, SHEYNIN Y. Integrated modular spacecraft avionics: architecture and SpaceWire-based implementation[C]∥Proceedings of the 16th IFAC Symposium on Automatic Control in Aerospace. Laxenburg: IFAC, 2004: 240-245.

[6] FERRER A, PARKES S. Unified communication infrastructure for small satellites[C]∥The 60th International Astronautical Congress 2009. Paris: IAF, 2009: 3776-3780.

[7] FERRANDIZ T, FRANCES F, FRABOUL C. A method of computation for worst-case delay analysis on SpaceWire networks[C]∥2009 IEEE International Symposium on Industrial Embedded Systems. Piscataway: IEEE, 2009: 19-27.

[8] PARKES S, ARMBRUSTER P. SpaceWire: a spacecraft onboard network for real-time communications[C]∥The 14th IEEE-NPSS Real Time Conference. Piscataway: IEEE, 2005:6-10.

[9] PARKES S. The Operation and uses of the SpaceWire time-code[C]∥2003 International SpaceWire Seminar. Noordwijk: ESTEC, 2003: 223-230.

[10] WILFRIED S, REINHARD M. Time-triggered services for Space-Wire[C]∥Proceedings of the 2nd International SpaceWire Con-ference. Noordwijk: ESTEC, 2008:121-129.

[11] 代真，何鋒，熊華鋼. 混合機(jī)制下的SpaceWire傳輸延時(shí)仿真分析[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2015，36(1)：1-5.

DAI Z, HE F, XIONG H G. Transmission delay simulation and analysis in SpaceWire under combined mechanism[J]. Computer Engineering and Design, 2015, 36(1):1-5(in Chinese).

[12] PARKES S, FERRER A. SpaceWire D: deterministic data delivery with SpaceWire[C]∥Proceedings of the 3nd International SpaceWire Conference. Dundee: University of Dundee，2010：158-164.

[13] 楊志，李國(guó)軍，楊芳，等. SpaceWire星載網(wǎng)絡(luò)通信協(xié)議設(shè)計(jì)[J]. 宇航學(xué)報(bào)，2012，33(2)：200-209.

YANG Z, LI G J, YANG F, et al. Design of communication protocol for SpaceWire on-board network[J]. Journal of Astronautics, 2012, 33(2):200-209(in Chinese).

[14] LIU C L, LAYLAND J W. Scheduling algorithms for multi- programming in a hard real-time environment[J]. Journal of the ACM, 1973, 20(1):46-61.

[15] 羅蕾. 嵌入式實(shí)時(shí)操作系統(tǒng)及應(yīng)用開(kāi)發(fā)[M]. 3版. 北京：北京航空航天大學(xué)出版社，2011:161-162.

LUO L.Embedded real-time operating system and application development[M]. 3rd ed. Beijing: Beihang University Press, 2011: 161-162(in Chinese).

(編輯：高珍)

A pre-emptible real-time SpaceWire on-board network

WU Zhongjie1，LIU Jianglan2，SONG Wei3，YU Junjie3，LIN Jingming3,ZHAO Zhanfeng4,*

1.School of Electronics and Information Engineering, Harbin Institute of Technology，Harbin 150001,China 2.Shanghai Institute of Aerospace System Engineering, Shanghai 201109, China 3.Shandong Institute of Aerospace Electronics Technology, Yantai 264003, China 4.School of Information and Electrical Engineering,Harbin Institute of Technology,Weihai,Weihai 264209,China

To build unified on-board communication infrastructure based on SpaceWrie,research should be done to guarantee the deterministic and real-time performance of message transmission. To overcome the lack of flexibility in traditional time-triggered communication, a modified time-triggered SpaceWire network which supported the broadcasting of communication task transmission identifier was proposed. On this basis, a non-destructive pre-emptible communication mechanism was built and the application of classical processor real-time scheduling algorithm to communication task scheduling was discussed. At last, the transmission delay performance was analyzed and compared among event-triggered, traditional time-triggered and non-blocking real-time SpaceWire communication mechanisms. The research shows that this communication mechanism can reduce the worst-case end-to-end delay, and is suited for the scheduling of communication tasks with various priorities.

on-board network；SpaceWire；pre-emptible；real-time；deterministic

10.16708/j.cnki.1000-758X.2016.0063

2016-05-18；

2016-06-29；錄用日期：2016-08-22；

時(shí)間：2016-12-16 11:29:13

http:∥www.cnki.net/kcms/detail/11.1859.V.20161216.1129.008.html

吳中杰(1991-)，男，碩士研究生，hit_wzj@163.com，研究方向?yàn)樾禽d電子系統(tǒng)設(shè)計(jì)

*通訊作者：趙占鋒(1980-)，男，副教授，zhaozhanfeng@hitwh.edu.cn,研究方向?yàn)楝F(xiàn)代分析儀器、星載電子系統(tǒng)

吳中杰,劉江瀾,宋偉,等.可搶占實(shí)時(shí)星載SpaceWire總線(xiàn)網(wǎng)絡(luò)研究[J].中國(guó)空間科學(xué)技術(shù),2016,36(6)：

62-69.WUZJ,LIUJL,SONGW,etal.Apre-emptiblereal-timeSpaceWireon-boardNetwork[J].ChineseSpaceScienceandTechnology, 2016, 36(6)：62-69(inChinese).

V443

A

http:∥zgkj.cast.cn