基于RMA的嵌入式系統(tǒng)代理調(diào)度模型設(shè)計(jì)

羅 奕 何振林 孟 麗 張慶蓉

（成都中醫(yī)藥大學(xué)管理學(xué)院，成都610075）

隨著嵌入式系統(tǒng)的應(yīng)用日益廣泛，以及應(yīng)用領(lǐng)域的不斷拓寬，其應(yīng)用環(huán)境和運(yùn)行狀態(tài)也隨之變得更加復(fù)雜。為了適應(yīng)嵌入式應(yīng)用不斷發(fā)展的需求，基于對(duì)實(shí)時(shí)性、并發(fā)性以及效率等因素的考慮，需要對(duì)傳統(tǒng)的嵌入式系統(tǒng)的設(shè)計(jì)架構(gòu)進(jìn)行更加完善的設(shè)計(jì)［1］。在目前的嵌入式系統(tǒng)中，融合了傳統(tǒng)硬件架構(gòu)和軟件計(jì)算功能的綜合式設(shè)計(jì)方法已逐漸成為發(fā)展趨勢(shì)。嵌入式系統(tǒng)能夠支持更多的應(yīng)用模塊，各模塊由相對(duì)獨(dú)立的進(jìn)程或線程控制，它們有機(jī)地結(jié)合在一起形成完整的系統(tǒng)［2～4］。具有多外設(shè)接口對(duì)于嵌入式系統(tǒng)是非常普遍的情況，外設(shè)的活動(dòng)通常是由設(shè)備驅(qū)動(dòng)程序控制。這些外設(shè)的工作相對(duì)獨(dú)立于中央處理模塊，同時(shí)，外設(shè)所負(fù)責(zé)的工作內(nèi)容也可能存在較大的差異。例如數(shù)據(jù)采集、數(shù)據(jù)處理和狀態(tài)控制等，都可能會(huì)導(dǎo)致處理延遲的不確定性。設(shè)備驅(qū)動(dòng)程序則將負(fù)責(zé)有效保持外設(shè)與中央處理模塊之間的聯(lián)系。在傳統(tǒng)的嵌入式體系設(shè)計(jì)中，設(shè)備驅(qū)動(dòng)進(jìn)程通常被設(shè)計(jì)成與中央處理模塊直接交互［5，6］。當(dāng)這類驅(qū)動(dòng)進(jìn)程數(shù)量增大，同時(shí)在這些進(jìn)程之間存在較多的協(xié)作或同步關(guān)聯(lián)時(shí)，這種直接耦合的設(shè)計(jì)模式可能會(huì)導(dǎo)致嵌入式系統(tǒng)的性能受到較大的影響。因此，需要對(duì)系統(tǒng)的體系結(jié)構(gòu)作細(xì)致考慮，以保證系統(tǒng)的整體性能。

既然直接耦合設(shè)計(jì)的架構(gòu)無(wú)法對(duì)上述情況提供好的解決方法，則適于并發(fā)和多道控制的軟件代理結(jié)構(gòu)是有效的可選設(shè)計(jì)方案［7，8］。軟件代理［8］可描述為軟件或硬件的組件，可用于為被代理用戶完成特定的事務(wù)。在本文中，軟件代理被設(shè)計(jì)用于代理多外設(shè)驅(qū)動(dòng)模塊實(shí)現(xiàn)對(duì)并發(fā)及同步處理事務(wù)的調(diào)度管理。該代理根據(jù)一定時(shí)間段內(nèi)發(fā)生的并發(fā)和同步請(qǐng)求情況，采用單調(diào)速率調(diào)度算 法 （Rate Monotonic Scheduling， 簡(jiǎn) 稱RMS）［12～14］對(duì)請(qǐng)求響應(yīng)進(jìn)行重新排序，使被代理模塊在串行化的調(diào)度處理后，能夠更合理地使用共享資源，提高多事務(wù)并發(fā)執(zhí)行的性能。

本文包括下述內(nèi)容：對(duì)嵌入式應(yīng)用系統(tǒng)的代理設(shè)計(jì)體系結(jié)構(gòu)進(jìn)行了描述，討論了代理采用RMS算法實(shí)現(xiàn)請(qǐng)求的接入控制，并在此基礎(chǔ)上實(shí)現(xiàn)對(duì)并發(fā)事務(wù)的重調(diào)度。在上述基礎(chǔ)上對(duì)一個(gè)典型的嵌入式應(yīng)用系統(tǒng)的并發(fā)處理場(chǎng)景進(jìn)行了用例分析，驗(yàn)證了該代理設(shè)計(jì)方法的有效性。最后，總結(jié)全文并展望今后進(jìn)一步的研究工作。

1 嵌入式系統(tǒng)的代理體系結(jié)構(gòu)設(shè)計(jì)

嵌入式系統(tǒng)的體系結(jié)構(gòu)通常包含了可編程的軟件組件和客戶訂制的集成單芯片硬件組件2個(gè)部分。嵌入式系統(tǒng)常見(jiàn)為異構(gòu)式的體系結(jié)構(gòu)，該設(shè)計(jì)架構(gòu)可有效地將軟硬件組件結(jié)合起來(lái)，實(shí)現(xiàn)一些常見(jiàn)或特定的計(jì)算目標(biāo)［4］。雖然根據(jù)不同的應(yīng)用需求，嵌入式應(yīng)用系統(tǒng)可能會(huì)包含不同的組件和集成方式，但從架構(gòu)上仍然體現(xiàn)出一定的相似性，如圖1所示。

圖1 異構(gòu)嵌入式系統(tǒng)設(shè)計(jì)架構(gòu)Fig.1 Heterogeneous embedded system architecture

圖1中，DSP是嵌入式系統(tǒng)的核心組件。隨著技術(shù)發(fā)展和應(yīng)用需求的提高，目前也出現(xiàn)了多處理器的設(shè)計(jì)架構(gòu)。除了核心組件之外，對(duì)其他硬件模塊的集成以及復(fù)雜軟件與硬件模塊的有效交互，是嵌入式設(shè)計(jì)中非常耗時(shí)和易于出錯(cuò)的工作內(nèi)容。尤其在這些集成的軟件與硬件部件之間，存在著如時(shí)間約束、資源共享或并發(fā)與同步的要求時(shí)，更需要進(jìn)行仔細(xì)的設(shè)計(jì)考慮以保證嵌入式系統(tǒng)的各類性能需求。

在傳統(tǒng)的設(shè)計(jì)架構(gòu)中，上述資源共享、時(shí)間約束問(wèn)題常采用在各模塊設(shè)備驅(qū)動(dòng)之間的直接耦合實(shí)現(xiàn)方式。例如，在各驅(qū)動(dòng)中使用多線程編程工具，通過(guò)對(duì)共享資源采用互斥或信號(hào)量等方式來(lái)實(shí)施存取保護(hù)來(lái)實(shí)現(xiàn)。但這樣的設(shè)計(jì)方式更多是一種局部沖突的解決辦法，對(duì)于系統(tǒng)的整體性能相對(duì)缺乏控制力。軟件代理的設(shè)計(jì)模式則能夠很好地適用于這類應(yīng)用場(chǎng)景。既然對(duì)共享資源的存取操作始終是串行化的處理過(guò)程，那么，以代理方式對(duì)多道事務(wù)請(qǐng)求進(jìn)行接入控制，是一種合理的設(shè)計(jì)思路。

軟件代理設(shè)計(jì)架構(gòu)在并發(fā)或協(xié)同計(jì)算中具有很好的控制潛力。根據(jù)文獻(xiàn)［6］的研究結(jié)果，上述直接的內(nèi)核通信設(shè)計(jì)模式可以采用軟件代理架構(gòu)的中間調(diào)度層來(lái)替代，以實(shí)現(xiàn)更好的系統(tǒng)性能。在軟件代理模塊中包含了一個(gè)事務(wù)調(diào)度器，用以決定被代理事務(wù)的活動(dòng)順序。圖2是采用了代理架構(gòu)的設(shè)計(jì)模型，由代理模塊負(fù)責(zé)與不同被代理事務(wù)的通信，以及資源分配和協(xié)調(diào)各被代理事務(wù)之間的協(xié)同工作。

圖2 采用代理的異構(gòu)嵌入式系統(tǒng)架構(gòu)Fig.2 Agent－based heterogeneous embedded system architecture

圖2的設(shè)計(jì)是基于軟件層面的，這樣可以盡可能小地避免改變嵌入式系統(tǒng)的硬件結(jié)構(gòu)。代理模塊主要包含了事務(wù)調(diào)度器和同步通信控制組件兩個(gè)部分。有并發(fā)和時(shí)間約束需求的被代理事務(wù)需要首先在代理模塊處進(jìn)行注冊(cè)，提交基本的事務(wù)處理信息。

代理模塊使用調(diào)度器為被代理事務(wù)計(jì)算出合理的執(zhí)行序列，并使用同步通信控制組件完成對(duì)被代理事務(wù)的調(diào)度結(jié)果通告。代理設(shè)計(jì)的方式可有效減少被代理事務(wù)間因資源共享及自同步過(guò)程中所產(chǎn)生的沖突，降低由此而導(dǎo)致的系統(tǒng)開(kāi)銷。同時(shí)，能夠針對(duì)全局性能實(shí)現(xiàn)優(yōu)化配置。代理模塊對(duì)并發(fā)性事務(wù)的管理是動(dòng)態(tài)的，當(dāng)并發(fā)事務(wù)的請(qǐng)求到達(dá)時(shí)，代理服務(wù)進(jìn)程被自動(dòng)激活，并重新計(jì)算當(dāng)前的調(diào)度隊(duì)列情況，用以確定新的事務(wù)請(qǐng)求能否加入當(dāng)前的調(diào)度序列。

目前，基于網(wǎng)絡(luò)的分布式應(yīng)用日益廣泛。采用代理架構(gòu)的設(shè)計(jì)方法可有效擴(kuò)展嵌入式系統(tǒng)的應(yīng)用領(lǐng)域。Steven描述了一種可提供高度并發(fā)服務(wù)的可編程模型［15］。而這種代理架構(gòu)的設(shè)計(jì)模型，也比較易于擴(kuò)展到網(wǎng)絡(luò)與分布式應(yīng)用的場(chǎng)景。

2 調(diào)度支持

如前所述，軟件代理依靠調(diào)度器來(lái)實(shí)現(xiàn)對(duì)被代理事務(wù)的調(diào)度管理工作。單調(diào)速率優(yōu)先（RMS）算法［16］是一種實(shí)時(shí)應(yīng)用中所廣泛采用的調(diào)度算法。本文采用RMS來(lái)實(shí)現(xiàn)代理模塊中的調(diào)度器。

在RMS中，設(shè)需調(diào)度的事務(wù)個(gè)數(shù)為n，可表示為S＝｛t1，t2，…，tn｝。并假定這些被調(diào)度事務(wù)之間相互獨(dú)立。這是調(diào)度中最簡(jiǎn)單的一種情況。則這組被調(diào)度事務(wù)可滿足的調(diào)度條件為

其中，是Ci執(zhí)行事務(wù)i的最壞執(zhí)行時(shí)間，Ti是該事務(wù)的執(zhí)行周期。

在實(shí)際情況中，一組事務(wù)之間往往并非完全不相關(guān)，在事務(wù)之間存在著同步和協(xié)作的需求。這種情況下，RMS算法適當(dāng)松弛式（1）中的約束條件，得到下式

Ci和Ti與式（1）中相同，Bi是事務(wù)i被同組中更低優(yōu)先級(jí)事務(wù)所阻塞的時(shí)間。低優(yōu)先級(jí)阻塞更高優(yōu)先級(jí)的情況稱為優(yōu)先級(jí)反轉(zhuǎn)。若該組事務(wù)符合公式（2）的約束條件，則這組事務(wù)能夠滿足RMS的實(shí)時(shí)調(diào)度需求。

Sprunt與Lehoczky對(duì)實(shí)時(shí)事務(wù)調(diào)度作了進(jìn)一步的改進(jìn)，改進(jìn)后的一組事務(wù)中可以存在非周期性的事務(wù)情況［17］。對(duì)于兩類非周期性的事務(wù)TE與TR，TE是突發(fā)性的臨時(shí)事務(wù)，該事務(wù)的時(shí)間約束為DE。另一類事務(wù)TR也是非周期性事務(wù)，但此類事務(wù)沒(méi)有或僅有很弱的時(shí)間約束要求。實(shí)際上，可將TR看作非周期性事務(wù)。因此，事務(wù)的平均響應(yīng)時(shí)間可由隊(duì)列的平均等待時(shí)間Wq和平均執(zhí)行時(shí)間We構(gòu)成。

Dq是隊(duì)列中任意連續(xù)事務(wù)完成后移出隊(duì)列的時(shí)間間隔。f是事務(wù)的發(fā)生頻率，用于評(píng)估平均CPU的占用率。I為事務(wù)的平均發(fā)生間隔時(shí)間?？傻玫较率降年?duì)列平均等待時(shí)間

用TR替代Dq，隊(duì)列的平均等待時(shí)間為

因此，可以用下式進(jìn)行估計(jì)

上式改進(jìn)后的計(jì)算公式可保證應(yīng)用事務(wù)能夠滿足實(shí)時(shí)時(shí)間約束的要求。在上述公式中，僅是給出了可滿足調(diào)度管理事務(wù)組的一種充分條件。即使在不滿足上述約束條件時(shí)，調(diào)度組仍然是有可能保證滿足每個(gè)進(jìn)程的時(shí)間約束要求。

使用上述RMS調(diào)度算法，可幫助代理對(duì)并發(fā)事務(wù)進(jìn)行管理。當(dāng)多道接入控制請(qǐng)求在一定的時(shí)間間隔內(nèi)產(chǎn)生，代理采用RMS調(diào)度算法計(jì)算該組事務(wù)的時(shí)間約束滿足情況，并根據(jù)計(jì)算結(jié)果調(diào)整對(duì)控制請(qǐng)求的響應(yīng)順序。若當(dāng)前調(diào)度組能夠接納新的請(qǐng)求事務(wù)，則將該新事務(wù)歸并入當(dāng)前的調(diào)度組進(jìn)行管理。否則，需要啟動(dòng)新的事務(wù)組來(lái)進(jìn)行接入控制管理。圖3是對(duì)代理的調(diào)度管理流圖的描述。

由圖3可見(jiàn)，該調(diào)度管理中沒(méi)有采用搶占式的調(diào)度管理模式，因此軟件代理在對(duì)事務(wù)的調(diào)度管理中并沒(méi)有采用硬實(shí)時(shí)的方式，可能存在事務(wù)不能保證時(shí)間約束的情況。上述采用代理進(jìn)行調(diào)度管理的情況，可以避免強(qiáng)耦合設(shè)計(jì)方式所導(dǎo)致事務(wù)資源競(jìng)爭(zhēng)所導(dǎo)致的沖突避免或解除等開(kāi)銷，有助于提高系統(tǒng)的整體性能。

圖3 代理工作流圖Fig.3 Agent work flow diagram

3 試驗(yàn)

試驗(yàn)是在一個(gè)典型的嵌入式組態(tài)軟件系統(tǒng)下設(shè)計(jì)并執(zhí)行。該組態(tài)軟件系統(tǒng)最初是采用了中央集中控制的組織結(jié)構(gòu)。系統(tǒng)中每個(gè)分散的受控節(jié)點(diǎn)由相對(duì)獨(dú)立的事務(wù)進(jìn)行管理，并由其負(fù)責(zé)對(duì)各節(jié)點(diǎn)數(shù)據(jù)的采集和局部操作的控制。各個(gè)分布節(jié)點(diǎn)之間存在著存儲(chǔ)資源和總線資源的共享。同時(shí)，各分布節(jié)點(diǎn)與中央控制節(jié)點(diǎn)之間存在直接的通信，以保證中央節(jié)點(diǎn)對(duì)各分布節(jié)點(diǎn)的有效監(jiān)控。分布式節(jié)點(diǎn)中存在部分PLC控制設(shè)備，這些設(shè)備以固定的周期完成特定的工作。試驗(yàn)采用軟件代理方式控制各個(gè)分布式節(jié)點(diǎn)的并發(fā)執(zhí)行，對(duì)共享資源的請(qǐng)求和存取進(jìn)行統(tǒng)一的調(diào)度管理。表1中給出了組態(tài)軟件中5個(gè)并發(fā)處理事務(wù)的基本參數(shù)，圖4則是采用了軟件代理管理的時(shí)間序列圖。

表1 并發(fā)事務(wù)的基本參數(shù)Table 1 Concurrency tasking arguments design

圖4 多事務(wù)并發(fā)處理軟件代理的序列圖Fig.4 Sequential diagram for multi－tasking concurrency time

由表1中所示，事務(wù)T1具有較高的時(shí)間約束要求的周期性的監(jiān)控?cái)?shù)據(jù)采集事務(wù)，T5是較低時(shí)間約束要求的顯示數(shù)據(jù)更新事務(wù)。T2，T3，T4是具有一般時(shí)間約束要求的設(shè)備數(shù)據(jù)采集事務(wù)。為了保證這組并發(fā)事務(wù)的有效執(zhí)行，采用軟件代理方式進(jìn)行分組管理。

圖4中標(biāo)記了軟件代理對(duì)并發(fā)事務(wù)進(jìn)行統(tǒng)一管理的過(guò)程。在主控程序中初始化階段啟動(dòng)各個(gè)分布節(jié)點(diǎn)上的處理事務(wù)。隨后，每個(gè)獨(dú)立的事務(wù)完成對(duì)所控設(shè)備的初始狀態(tài)和控制參數(shù)的設(shè)置。當(dāng)設(shè)備啟動(dòng)后，對(duì)應(yīng)的控制事務(wù)作為被代理客戶，向主控程序的代理模塊注冊(cè)相關(guān)的事務(wù)參數(shù)信息，例如注冊(cè)的定式器、共享資源請(qǐng)求、時(shí)間約束條件等。軟件代理在每當(dāng)有新的事務(wù)請(qǐng)求接入時(shí)觸發(fā)。軟件代理調(diào)用調(diào)度程序計(jì)算接入新事務(wù)是否能夠滿足整體的時(shí)間約束要求。如果能夠滿足時(shí)間約束條件，則該事務(wù)被接入當(dāng)前的調(diào)度隊(duì)列中，并將調(diào)度后的結(jié)果告知當(dāng)前管理組中的事務(wù)。如果計(jì)算結(jié)果不能滿足時(shí)間約束條件，則最新的事務(wù)將激活新的調(diào)度組管理。當(dāng)被代理事務(wù)獲得了代理模塊的響應(yīng)后，將根據(jù)響應(yīng)信息獨(dú)立進(jìn)行事務(wù)操作。并發(fā)的一組軟件事務(wù)在軟件代理調(diào)度后成為序列化的獨(dú)立進(jìn)程依次執(zhí)行。

表2是在使用和不使用軟件代理方式下分別對(duì)組態(tài)軟件一段時(shí)間內(nèi)的性能進(jìn)行統(tǒng)計(jì)得到的結(jié)果。

表2 采用與不采用軟件代理的性能比較Table 2 Performance comparison of agent method

在記錄的一段時(shí)間內(nèi)，采用了軟件代理實(shí)現(xiàn)的系統(tǒng)可多接入13%左右的并發(fā)請(qǐng)求，并且事務(wù)處理不能滿足時(shí)間約束條件的發(fā)生頻率也比不采用代理時(shí)有所下降。顯然，在使用了代理調(diào)度后，雖然損失了部分調(diào)度計(jì)算時(shí)間，使得事務(wù)的平均響應(yīng)等待時(shí)間有所增加，但可獲得更好的執(zhí)行序列，減少了由資源競(jìng)爭(zhēng)沖突所導(dǎo)致的額外時(shí)間開(kāi)銷。

4 結(jié)論

本文采用軟件代理的架構(gòu)的設(shè)計(jì)方式來(lái)管理嵌入式應(yīng)用系統(tǒng)中的并發(fā)事務(wù)處理。該設(shè)計(jì)模型比事務(wù)間直接耦合的并發(fā)處理方式更加合理，通過(guò)采用軟件代理的設(shè)計(jì)模式，可有效地管理事務(wù)組間的資源共享，提高事務(wù)的并發(fā)處理能力，進(jìn)而改善系統(tǒng)的整體性能。

［1］FRANK V，TONY G.Embedded System Design：A Unified Hardware／Software Introduction［M］.California：John Wiley ＆Sons，2004：14－22.

［2］LIN B，VERCAUTEREN S.Synthesis of concurrent system interface modules with automatic protocol conversion generation［C］／／ Proc of IEEE International Conference on Computer Aided Design.Belgium：IEEE Press，1994：101－108.

［3］LIN B，VERCAUTEREN S，DE MAN H.Embedded architecture co－synthesis and system integration［C］／／Proc of the Fourth International Workshop on Hardware／Software Co－Design.Pittsburgh，PA，USA，1996：2－9.

［4］BROOKS R A.A Robust Layered control system for a mobile robot［J］.IEEE Journal of Robotics and Automation，1986，2（1）：14－23.

［5］KARKOWSKI I.Computer aided embedded systems design［C］／／Proc of the Third Annual Conf of ASCI.Heijen：The Netherlands，Pittsburgh，PA，USA，1997：2－4.

［6］VERCAUTEREN S，LIN B，DE MAN H.Constructing application －specific heterogeneous embedded architectures from custom HW／SW applications［C］／／ Proc of the 33rdInternational Conference on Design Automation.Las Vegas，NV，USA，1996：521－526.

［7］EDWARD A L，STEPHEN N.Actor－oriented design of embedded hardware and software systems［J］.Journal of Circuits，Systems，and Computers，2003，2（3）：231－260.

［8］DICK R P，NIRAJ K.CORDS：hardware－software co－synthesis of reconfigurable real－time distributed embedded systems［C］／／IEEE／ACM International Conference on Computer Aided Design，1998：62－68.

［9］NWANA H S，WOOLDRIDGE M.Software agent technologies［J］.British Telecommunications Technology Journal，1996，14（4）：79－88.

［10］MONTE J D，KRISHNA R.Scheduling paralleliz－able tasks to minimize make－span and weighted response time［J］.IEEE Trans on Systems，Man，and Cybernetics－Part A：Ststemns and Humans，2002，32（3）：335－345.

［11］VERCAUTEREN S，LIN B，DE MAN H.A strategy for real－time kernel support in application －specific HW／SW embedded architectures［C］／／Proc of the 33rdInternational Conference on Design Automation，Las Vegas，NV，USA，1996：678－683.

［12］FOWLER P，LEVINE L.Technology transition push：a case study of rate monotonic analysis（Part 1）［R］.Technical Report CMU／SEI－93－TR－29ESCTR－93－203，1993.

［13］KLEIN M.A Practitioner’s Handbook for Real－Time Analysis：Guide to Rate－Monotonic Analysis for Real－Time Systems［M］.Santa Monica：Kluwer Academic Publishers，1993.

［14］LEHOCZKY J，SHA L，YE D.The rate monotonic scheduling algorithm：exact characterization and average case behavior［C］／／Proc IEEE 10thReal－Time Systems Symposium.Santa Monica：Kluwer Academic Publishers，1989：166－171.

［15］STEVEN D G，MATT W.The ninja architecture for robust internet－scale system and services［J］.Computer Networks，2001，35：473－497.

［16］LIU C L，JAMES W.Scheduling algorithms for multiprogramming in a hard real－time environment［J］.Journal of the ACM，1973，20（1）：46－61.

［17］SPRUNT B，SHA L，LEHOCZKY J.Aperiodic task scheduling for hard－real－time systems［J］.Real－Time Systems，1989，1（1）：261－270.