《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 通信與網(wǎng)絡(luò) > 業(yè)界動(dòng)態(tài) > 基于Petri網(wǎng)的嵌入式軟件組件的實(shí)時(shí)性研究

基于Petri網(wǎng)的嵌入式軟件組件的實(shí)時(shí)性研究

2009-05-21
作者:劉雪艷1,張 強(qiáng)1,,2,,寇曉東3

  摘 要: 根據(jù)嵌入式系統(tǒng)軟件的特點(diǎn)和發(fā)展需求,設(shè)計(jì)了一種新的嵌入式軟件組件模型SECOM,,給出了模型的基本組成元素,。同時(shí),利用時(shí)間Petri網(wǎng)TPN建立一個(gè)TPN計(jì)時(shí)器timer,,對(duì)該組件模型SECOM非功能性約束中的實(shí)時(shí)性進(jìn)行建模與分析, 形式化地驗(yàn)證了該組件的實(shí)時(shí)性,。
  關(guān)鍵詞: Petri網(wǎng);TPN,;組件,;非功能性約束

?

  隨著科技的發(fā)展,大多數(shù)的電子系統(tǒng)和產(chǎn)品含有特定的硬件器件和功能模塊,,顯然這些系統(tǒng)是多種類,、嵌入式的。嵌入式的軟/硬件設(shè)計(jì)是一項(xiàng)復(fù)雜工作,,為了滿足系統(tǒng)的可靠性,、運(yùn)行效果、內(nèi)存受限等要求,,嵌入式系統(tǒng)除了需要實(shí)現(xiàn)功能需求外,,非功能性的約束(Non-functional constraints)也是非常重要的。非功能性約束包括實(shí)時(shí)性,、程序性能,、穩(wěn)定性、可靠性,、安全性,、內(nèi)存限制、存儲(chǔ)空間限制等[1-2],。對(duì)于非功能性約束的考慮方法可以分為兩大類:面向過(guò)程(process-oriented)的方法和面向產(chǎn)品的方法(product-oriented),。面向過(guò)程的方法,指使用非功能性約束信息指導(dǎo)軟件的開(kāi)發(fā)過(guò)程,。面向產(chǎn)品的方法,,指在組件內(nèi)部描述非功能性約束信息,并檢查組件構(gòu)成的產(chǎn)品的非功能性約束信息判斷軟件是否滿足要求的非功能性約束。本文中使用面向產(chǎn)品的方法對(duì)嵌入式組件模型SECOM(Simple Embedded Component Object Model)的非功能性約束進(jìn)行分析,,在組件內(nèi)部采用Petri網(wǎng)方法描述非功能性約束信息,。
1 時(shí)間Petri網(wǎng)
  Petri網(wǎng)是一種可用圖形表示的組合模型,具有直觀、易懂和易用的優(yōu)點(diǎn),可用于模擬帶有并發(fā)性,、異步性,、分布式、非確定性,、并行性等特性的系統(tǒng),。而用時(shí)間Petri網(wǎng)[3-4](簡(jiǎn)稱時(shí)間網(wǎng)TPN)建立系統(tǒng)的動(dòng)態(tài)模型,可進(jìn)一步將系統(tǒng)中事件從發(fā)生到結(jié)束所需的時(shí)間描述出來(lái),。
  時(shí)間網(wǎng)TPN中表示事件的持續(xù)時(shí)間的方法有兩種:一種是將各事件的持續(xù)時(shí)間標(biāo)在庫(kù)所的旁邊,,表示庫(kù)所中產(chǎn)生的托肯要經(jīng)過(guò)一定的時(shí)間后才能參與網(wǎng)中的運(yùn)行,;另一種方法是將時(shí)間標(biāo)注在變遷的旁邊,,表示當(dāng)該變遷具有發(fā)生條件時(shí)要延遲一段時(shí)間后才能發(fā)生,或該變遷發(fā)生后,,立即從相應(yīng)的輸入庫(kù)所中移走相應(yīng)的托肯,,但要延遲一段時(shí)間后才在相應(yīng)的輸出庫(kù)所中產(chǎn)生相應(yīng)的托肯[5-6]。在下面的時(shí)間P/T網(wǎng)定義中采用的是后一種方法,。
  定義1:當(dāng)某一變遷的發(fā)生條件滿足時(shí),,若該變遷要延遲一段時(shí)間后才從相應(yīng)的輸入庫(kù)所中移走相應(yīng)的托肯并得到發(fā)生后果,或該變遷發(fā)生后,,立即從相應(yīng)的輸入庫(kù)所中移走相應(yīng)的托肯,,但要延遲一段時(shí)間后才得到發(fā)生后果,則稱這樣的變遷為時(shí)間變遷,。
  定義2:當(dāng)某一變遷的發(fā)生條件滿足時(shí),,若該變遷立即從相應(yīng)的輸入庫(kù)所中移走相應(yīng)的托肯,且立即得到發(fā)生后果,,則稱這樣的變遷為立即變遷,。
  在時(shí)間P/T網(wǎng)的圖形表示中約定,用矩形框表示時(shí)間變遷,,用黑線表示立即變遷,。下面是時(shí)間P/T網(wǎng)模型的形式化定義。
  

  根據(jù)延遲時(shí)間是一個(gè)固定值還是一個(gè)區(qū)間值,,TPN還可分為固定延遲時(shí)間P/T網(wǎng)和不固定延遲時(shí)間P/T網(wǎng),。在固定延遲時(shí)間P/T網(wǎng)中,對(duì)于任意的變遷t∈T1,,都有一個(gè)非負(fù)的實(shí)數(shù)r與之相對(duì)應(yīng),,使得變遷t的延遲時(shí)間為r。在不固定延遲時(shí)間P/T網(wǎng)中,對(duì)于任意的變遷t∈T1,,都有一個(gè)對(duì)偶[Bcet,,Wcet]與之相對(duì)應(yīng)(Bcet≥0,Wcet≥0),,使得若在a時(shí),,t的發(fā)生條件成立,則t可在時(shí)間區(qū)間[a+Bcet,,a+Wcet]內(nèi)執(zhí)行,,即t有效時(shí),其相應(yīng)的輸入庫(kù)所中的托肯將至少保留Bcet s,,直至(a+Wcet) s時(shí)才移出,,或t有效時(shí),其相應(yīng)的輸入庫(kù)所中的托肯立即移出,,但將至少保持Bcet s,,直至(a+Wcet) s時(shí)才產(chǎn)生后繼標(biāo)識(shí),本文中將采用第一種方式,。
2 SECOM組件模型
  基于嵌入式系統(tǒng)高度可裁剪性,、資源受限的特點(diǎn)和對(duì)當(dāng)前現(xiàn)狀的分析[6],本文給出一種新的,、基于源代碼復(fù)用的,、精簡(jiǎn)的嵌入式組件模型SECOM。該組件模型包含以下元素:
  (1)瘦組件:SECOM組件是設(shè)計(jì),、開(kāi)發(fā),、重用的單元,是程序的基本組成塊,,是在完成基本功能前提下的極小化,,所以稱之為“瘦組件”。組件與接口相互獨(dú)立,,是接口功能的具體實(shí)現(xiàn)者,。組件之間通過(guò)接口通信,互相協(xié)作完成軟件功能,。組件的定義是可遞歸的,。
  (2)簡(jiǎn)接口:接口用來(lái)定義功能函數(shù),是一組相關(guān)函數(shù)的集合,,分離了瘦組件的定義與實(shí)現(xiàn),,徹底消除了接口調(diào)用者和實(shí)現(xiàn)者之間的耦合關(guān)系,增強(qiáng)了信息封裝性,。接口具有唯一性,、不變性,、繼承性和多態(tài)性。同一接口在不同組件內(nèi)有不同的實(shí)現(xiàn)方式,。接口分為兩類:①服務(wù)接口(Provide Interface),,接口所在組件已經(jīng)實(shí)現(xiàn)了此接口類型的功能,可以向組件外部提供服務(wù),;②請(qǐng)求接口(Require Interface),,接口所在組件內(nèi)沒(méi)有實(shí)現(xiàn)此接口的功能,組件需要向外部請(qǐng)求此接口的實(shí)現(xiàn),。
  (3)靈敏橋接器:橋接器完成接口之間的連接,。根據(jù)現(xiàn)有條件的不同,采取不同的連接模式,。連接模式有:直接連接(connecting),,選擇連接(selecting)和代碼塊粘連(gluing)。接口之間的消息交換是通過(guò)一個(gè)橋接器連接兩個(gè)或更多的接口實(shí)例來(lái)實(shí)現(xiàn)[7-9],。組件模型類圖如圖1所示,。

?


3 建模實(shí)時(shí)分析
  嵌入式系統(tǒng)通常都是強(qiáng)實(shí)時(shí)性的,為了對(duì)實(shí)時(shí)性更有效地建模和分析,,首先建立一個(gè)如圖2所示的TPN計(jì)時(shí)器timer,,其中T1是一個(gè)時(shí)間變遷,延遲時(shí)間是一個(gè)固定值r,,且r=Wcet。經(jīng)過(guò)時(shí)間r s后,,P01中的托肯才會(huì)移出,,P02中則會(huì)出現(xiàn)托肯;否則,,當(dāng)小于時(shí)間r,,并且有其他條件滿足時(shí),finish變遷會(huì)發(fā)生,。


  下面對(duì)SECOM組件模型進(jìn)行實(shí)時(shí)建模分析,。圖3中圓圈表示組件狀態(tài),timer是前面利用TPN建立的計(jì)時(shí)器,。其中M0={1,,0,0,,0,,…}是初始標(biāo)識(shí);P={P1,,P2,,…,,P3,P4,,P5}是一個(gè)有限庫(kù)所集,;P1:接收其他組件訪問(wèn)該組件的一個(gè)請(qǐng)求require;P2:該組件處于連接和開(kāi)始工作狀態(tài),;P3:該組件處于工作結(jié)束狀態(tài),;P4:請(qǐng)求得到響應(yīng)后返回成功信息;P5:請(qǐng)求得不到響應(yīng),,返回錯(cuò)誤信息,。


  T={t1,t2,,t3,,t4}是一個(gè)有限變遷集,t1:請(qǐng)求P1經(jīng)過(guò)變遷t1連接要訪問(wèn)的組件,,同時(shí)激發(fā)計(jì)時(shí)器timer開(kāi)始計(jì)時(shí),;t2:這是一個(gè)時(shí)間變遷,延遲時(shí)間是一個(gè)區(qū)間值[Bcet,,Wcet],,至少經(jīng)過(guò)時(shí)間Bcet s,P2中的托肯才會(huì)移出,,則P3中經(jīng)過(guò)至少Bcet s時(shí)間才會(huì)出現(xiàn)托肯,;t3:當(dāng)t2的變遷時(shí)間小于等于Wcet時(shí)間時(shí),庫(kù)所P3和計(jì)時(shí)器中的庫(kù)所P01都擁有托肯,,則變遷t3的發(fā)生條件滿足,,即t3變遷發(fā)生,返回結(jié)果,;t4:當(dāng)t2的變遷時(shí)間大于Wcet時(shí)間時(shí),,計(jì)時(shí)器中的P02中擁有托肯,則變遷t4會(huì)發(fā)生,,返回失敗消息,。
  以上是對(duì)一個(gè)基本組件的實(shí)時(shí)建模。從P1狀態(tài)經(jīng)過(guò)P2和P3到達(dá)P4狀態(tài),,表明了該組件從收到請(qǐng)求,、建立連接開(kāi)始工作到結(jié)束工作,返回成功信息,。而從P1狀態(tài)不經(jīng)過(guò)P2和P3到達(dá)P5狀態(tài),,則說(shuō)明請(qǐng)求未能得到滿足,返回錯(cuò)誤信息,。在SECOM模型中,,t2變遷發(fā)生的時(shí)間處于[Bcet,,Wcet]區(qū)間,從而說(shuō)明該組件模型滿足實(shí)時(shí)性的要求,。
  當(dāng)訪問(wèn)一個(gè)不太復(fù)雜的復(fù)合組件時(shí),,有些訪問(wèn)子組件步驟之間會(huì)出現(xiàn)順序問(wèn)題,即會(huì)出現(xiàn)同步問(wèn)題,,因而需采取措施防止沖突發(fā)生,。所采取的措施為:在兩個(gè)請(qǐng)求之間加入一個(gè)控制庫(kù)所P00,由它來(lái)控制訪問(wèn)的次序,。從P11到t21的虛邊體現(xiàn)了require1比require2有優(yōu)先權(quán):非空的P11阻止了t21的點(diǎn)火,,其Petri網(wǎng)模型如圖4所示。

?


  對(duì)復(fù)合組件的分析,,比較簡(jiǎn)單的方法就是將每一個(gè)子組件作為一個(gè)子網(wǎng)連接起來(lái),,循環(huán)執(zhí)行。當(dāng)訪問(wèn)一個(gè)非常復(fù)雜的復(fù)合組件,、甚至整個(gè)系統(tǒng)時(shí),,調(diào)度任務(wù)繁瑣,可以考慮引進(jìn)一個(gè)單獨(dú)的調(diào)度決策,,由它完成對(duì)所有子組件的調(diào)度,。
  本文根據(jù)嵌入式系統(tǒng)的特點(diǎn)及其應(yīng)用需求,設(shè)計(jì)了一種新的,、簡(jiǎn)單的嵌入式組件模型SECOM,,給出了模型的基本組成元素。同時(shí),,引入了時(shí)間Petri網(wǎng),,并使用時(shí)間Petri網(wǎng)TPN,建立了一個(gè)TPN計(jì)時(shí)器timer,,利用其對(duì)該組件模型SECOM非功能性約束中的實(shí)時(shí)性進(jìn)行建模與分析,從而形式化地驗(yàn)證了該組件具有很好的實(shí)時(shí)性,。


參考文獻(xiàn)
[1] HUMMET T,,F(xiàn)ENGLER W.Design of embedded control?systems using hybrid Petri nets.The International Workshop?on Discrete-Event System Design,DESDes′01,,June27-29,,2001 Przytok near Zielona Gora,Poland
[2] Thomas Thomas GenBler,,Oscar Nierstrasz,,Bastiaan Schonhage.Components for embedded software[J].CASES 2002,10.

[3] Time Petri Nets.www.daimi.au.dk/PetriNets.
[4] Berthomieu B,,Diaz M.Modeling and veri_cation of time?dependent systems using time petri nets.IEEE Trans.Software Eng,,1991,,17:259-273.
[5] 袁崇義.Petri網(wǎng)原理.北京:電子工業(yè)出版社,1998.

[6] CAI X,,Michael R.Lyu,,WONG Kam Fai.Component-based embedded software engineering: development framework,?quality assurance and a generic assessment environment[J].International Journal of Software Engineering and Knowledge Engineering,2002,,2(12):107-133.
[7] Rob van Ommering,,F(xiàn)rank van de Linden.The Koala Component Model for Consumer Electronics Software[J].IEEE,2000:78-85.
[8] Wolfgang Emmerich,,Nima Kaveh.Component technologies:java beans, COM, CORBA,RMI, EJB and the CORBA?
Component Model[J].ACM2001:311-312.
[9] L.Fernando Friedrich,,John Stankovic.A survey configurable component-based operating systems for embedded?applications[J].IEEE,2001(1):54-68.

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,,并不代表本網(wǎng)站贊同其觀點(diǎn)。轉(zhuǎn)載的所有的文章,、圖片,、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無(wú)法一一聯(lián)系確認(rèn)版權(quán)者,。如涉及作品內(nèi)容,、版權(quán)和其它問(wèn)題,請(qǐng)及時(shí)通過(guò)電子郵件或電話通知我們,,以便迅速采取適當(dāng)措施,,避免給雙方造成不必要的經(jīng)濟(jì)損失。聯(lián)系電話:010-82306118,;郵箱:[email protected],。