摘? 要: 從進程和線程調(diào)度的角度出發(fā),介紹了一種規(guī)范化的實時多任務系統(tǒng)軟件設計方法,提出了“前向分支”的設計原則,給出了完整的系統(tǒng)模型,。

　　關(guān)鍵詞: 線程拆分? 前向分支? 實時多任務? 單片機

?

　　在機電產(chǎn)品研制開發(fā)中,經(jīng)常要涉及到基于嵌入式系統(tǒng)或基于單片機系統(tǒng)的程序設計,。實時多任務是這類系統(tǒng)最基本的要求之一,。在實踐中通常采用以下兩種解決方案:一是在商業(yè)化實時操作系統(tǒng)的基礎上進行二次開發(fā);二是用戶自行設計系統(tǒng)軟件。前者設計工作量小,設計周期短,系統(tǒng)的設計質(zhì)量也容易得到保證,。但由于商業(yè)化實時操作系統(tǒng)往往較多地考慮通用性,缺乏靈活性,對于一些特定的應用場合,其性能往往不能令人滿意。同時,這種方案還存在著成本高,依賴于特定硬件等缺點,。第二種方案可以從系統(tǒng)的實際要求和硬件的實際情況出發(fā)靈活地進行系統(tǒng)設計,易于滿足一些特定場合的性能要求,成本也較低,。但是,由于缺乏系統(tǒng)化、規(guī)范化的設計方法,缺少高層次抽象工具,使得系統(tǒng)的設計質(zhì)量不容易得到保證,并嚴重地依賴于程序員的水平和經(jīng)驗,。

　　本文針對上述第二種方案的局限,從進程和線程調(diào)度的角度出發(fā),介紹了一種系統(tǒng)化,、規(guī)范化和易于工程化實施的實時多任務系統(tǒng)軟件設計方法,提出了“前向分支”的設計原則,并給出了完整的系統(tǒng)模型。

1 進程的劃分

　　對復雜的系統(tǒng)需求進行模塊化和層次化的劃分是軟件設計的基本方法,。在實踐中,復雜的系統(tǒng)需求通常被劃分為一些功能相對獨立的任務模塊,每個任務模塊被視作一個進程(process),。系統(tǒng)中如有多個進程并發(fā)(concurrent)運行,該系統(tǒng)就是一個多任務的系統(tǒng)。在圖1所示的例子中,n個任務模塊構(gòu)成了宏觀上并發(fā)運行的一組進程(即Proc_1～Proc_n),。Proc_5和Proc_9是兩個具有代表性的進程結(jié)構(gòu),。Proc_5是斷續(xù)運行的進程,表示了某一順序邏輯控制的流程。Proc_9是LCD漢字顯示程序,其結(jié)構(gòu)是典型的多重循環(huán),。其功能是將數(shù)組aDisplay中所描述的24×24點陣中文字符串送至LCD顯示屏,。aDisplay的結(jié)構(gòu)參見圖3(e)。Proc_9的基本工作原理如下:當cDisplay不為0時,依次從aDisplay中取出每個待顯示漢字的點陣位置及其在LCD內(nèi)部顯存中的地址,根據(jù)這兩個參數(shù)將一個漢字的點陣順序發(fā)送到LCD內(nèi)部顯存中,。直至全部漢字顯示完,cDisplay減為0,Proc_9轉(zhuǎn)入空閑狀態(tài),等待新的顯示請求,。

?

　　系統(tǒng)程序的主要任務之一就是對進程進行調(diào)度,包括啟動和終止進程、管理進程之間的通訊,、處理進程之間的優(yōu)先級等,。但是如果按圖1的結(jié)構(gòu)順序調(diào)度進程,、以進程為基本單位分配CPU時間的話,顯然存在嚴重的問題。例如在Proc_5中,當程序處于等待K1閉合的狀態(tài)時,其它任何進程都無法得到服務,尤其當K1出現(xiàn)故障時,系統(tǒng)將處于“掛起”狀態(tài),。如果一個進程過多地占據(jù)了CPU時間,其他進程將不能得到公平,、均勻的服務,響應時間無法得到保證,系統(tǒng)效率會降低?？傊?只有將CPU時間的分配單位減小,才能解決上述問題,。

2 線程的拆分

　　線程(Thread)是CPU的基本執(zhí)行單位。一個進程可以由一個或多個線程構(gòu)成,。如前所述,單一線程的進程可能會存在諸多問題,而將一進程拆分為多個線程是解決上述問題的有效手段,。由圖1的Proc_5和Proc_9可以看出,一個進程過多地占據(jù)CPU時間，是因為其中含有次數(shù)不確定的等待循環(huán),、純延時和較為耗時的多重循環(huán),。其中,純延時可以用軟件延時和中斷定時兩種方法實現(xiàn),這兩種方法在進程中又都可以歸結(jié)為循環(huán)。因此,在拆分線程時應盡量遵循“前向分支”原則,使線程中不含有或少含有循環(huán),。

　　循環(huán)結(jié)構(gòu)本質(zhì)上是由一個分支判斷和一個“反向”轉(zhuǎn)跳構(gòu)成的,。所謂“前向分支”原則是指:在一次調(diào)度中,當程序發(fā)生分支時,應使程序跳向一段未被執(zhí)行過的代碼,而不得重復運行已運行過的代碼。如果嚴格按“前向分支”原則拆分線程,循環(huán)結(jié)構(gòu)將被完全消除,。圖2和圖3分別是Proc_5和Proc_9嚴格按“前向分支”原則拆分為線程的結(jié)果,。

?

　　如果進程設計遵循結(jié)構(gòu)化程序思想,那么在對某一進程嚴格按“前向分支”原則進行線程拆分時,最小拆分數(shù)量可按如下方法確定:進程入口至第一個循環(huán)返回節(jié)點之間如無程序代碼,最小拆分數(shù)量等于循環(huán)返回節(jié)點數(shù)Nback;進程入口至第一個循環(huán)返回節(jié)點之間如有程序代碼,最小拆分數(shù)量等于Nback+1。實際拆分數(shù)量可以大于最小拆分數(shù)量,但不應小于該數(shù),否則必然有一個以上的線程中含有循環(huán),。兩個循環(huán)返回節(jié)點之間(或入口到第一個循環(huán)返回節(jié)點之間,、最后一個循環(huán)返回節(jié)點到出口之間)的代碼就構(gòu)成了一個線程的主體。如果原進程中無循環(huán),可將該進程當做單一線程對待,。在圖1中,Proc_9中共有4個循環(huán)返回節(jié)點(①～④),即Nback=4,按最小拆分數(shù)量拆分為4個線程(Proc_9Thread_1～Proc_9Thread_4),。Proc_5中循環(huán)返回節(jié)點數(shù)也為4,但其入口至第一個循環(huán)返回節(jié)點之間有代碼,所以,Proc_5按最小拆分數(shù)量拆分為5個線程。

　　線程號變量tProc_n是系統(tǒng)中實現(xiàn)線程調(diào)度,、在各相關(guān)線程間建立聯(lián)系的核心,。按“前向分支”原則進行線程拆分時,凡是遇到構(gòu)成循環(huán)的“反向”分支時,就將該分支轉(zhuǎn)向當前線程的出口,并在出口前為所在進程的線程號變量賦一新值指向要轉(zhuǎn)去的線程。如果所要轉(zhuǎn)去的線程與當前所在線程一致時,線程號變量賦值可以省略,。

　　在按“前向分支”原則設計的線程中,“結(jié)構(gòu)上”的循環(huán)可以完全消除,但進程設計中“邏輯上”的循環(huán)仍然是存在的,否則進程的原有功能將不能正確地實現(xiàn),。事實上,線程號變量中包含有“邏輯循環(huán)”的信息。只要在主循環(huán)中按圖4的方法調(diào)度各線程就可以實現(xiàn)進程的“邏輯循環(huán)”,。

?

?

　　為實現(xiàn)中斷定時,Proc_5中設置了兩個定時計數(shù)器cTimerAct_1和cTimerAct_2(以下稱之為“動作定時器”),在啟動定時時設置好其初值,由一個基礎定時中斷程序按一定的時間間隔(本例為1ms)減1,。當動作定時器減為0時表示定時結(jié)束。

　　對于斷續(xù)運行的進程(如Proc_5),結(jié)束任務時應將線程號變量指向任意一個不用的空線程,。為統(tǒng)一和方便起見,本文約定所有進程的0號線程均為空線程,進程結(jié)束時線程號變量應置為0,。

3 總體模型

　　綜上所述,一個完整的、嚴格按“前向分支”原則進行線程拆分和進程調(diào)度的多任務系統(tǒng)模型可以歸納為圖5所示的結(jié)構(gòu),。該模型由三部分構(gòu)成:主循環(huán),、分屬于不同進程的“前向分支”的線程以及一個基礎定時中斷程序,。該模型結(jié)構(gòu)最大的特點是:除了主循環(huán)中最后一個回跳以外,其它任何地方都不存在循環(huán)結(jié)構(gòu)。換言之,系統(tǒng)中所有的循環(huán)“反向”轉(zhuǎn)跳,都被歸并成了主循環(huán)中的一個回跳,。這樣的結(jié)構(gòu)能使主循環(huán)在各進程間快速地切換,有利于提高CPU的利用率,改善系統(tǒng)的響應,使得各進程能夠得到及時,、均勻、公平的服務,。同時,基礎定時中斷程序也完全是“前向分支”結(jié)構(gòu),有利于減少對CPU的占用,。

考慮到各進程對響應時間和服務頻度的不同要求,在該模型中設置了對各進程進行定時同步的功能。在基礎定時中斷服務程序中增加了同步定時器cTimerSyn_i和同步定時標志fTimerSyn_i,。同步定時器和動作定時器構(gòu)成了基礎定時中斷服務程序的主體,。基礎定時中斷的中斷間隔時間應按所有定時任務的最大公約數(shù)來選取,所選取中斷間隔時間越大,對CPU的占用越少,越有利于系統(tǒng)效率的提高,。

?

?

　　進程定時同步的本質(zhì)是為不同響應時間需求的任務安排不同的服務頻度,。降低低優(yōu)先級任務的服務頻度相當于提高了高優(yōu)先級任務的服務頻度。在很多情況下,這樣的優(yōu)先級處理已令人滿意,。有一類進程出于功能(而不一定是優(yōu)先級)的需要,也必須進行定時同步,。

　　如前所述,嚴格按照“前向分支”原則拆分線程時,拆分數(shù)量不應小于進程中的循環(huán)返回節(jié)點數(shù)Nback或Nback+1。這是拆分線程時重要的參考依據(jù),。但是,在實際應用中,并不一定非要將線程中的循環(huán)徹底消除,應當根據(jù)具體情況和實際需求靈活掌握。

　　如果拆分粒度過細(即線程拆分數(shù)量過多),雖然對提高系統(tǒng)的響應速度有幫助,但由于進程切換過于頻繁,進程切換所需的額外開銷會導致系統(tǒng)效率下降(即有效的CPU機時占CPU總機時的比例下降),。粒度越細,這種情況也就越嚴重,。另外,粒度越細,源程序和程序文檔的可讀性越差,為程序的調(diào)試和維護以及文檔的維護帶來困難。因此,在能夠保證系統(tǒng)的響應速度和調(diào)度的均勻性等前提之下,拆分粒度傾向于粗一些,。在多數(shù)情況下,傾向于將次數(shù)不確定的等待循環(huán),、較為耗時的循環(huán)和較長的純延時拆分為線程。而那些循環(huán)次數(shù)確定且不太耗時的循環(huán)則建議保留,。在這種情況下,線程拆分數(shù)小于Nback或Nback+1,。

實時系統(tǒng)要求系統(tǒng)能夠?qū)斎胱龀隹焖俚姆磻吞幚怼５?“實時”只是一個相對的概念,響應時間快慢實際上是衡量一個系統(tǒng)是否“實時”的重要指標,。由圖5可以看出,對于本文所介紹的模型來說,由于進程都是確定的,響應時間可以大致按以下方法估算:各進程中最耗時線程的運行時間之和就是最不利的響應時間,平均響應時間應等于各進程中線程平均運行時間之和的二分之一,。根據(jù)以上估算,還可以大致推斷運行期間發(fā)生過幾次定時中斷。將基礎定時中斷所占用的CPU時間也估算進去,可以進一步提高響應時間估算的準確度,。當然,響應時間也可以通過實驗來測定,。如果響應時間不能滿足某一任務的要求,可以將長線程進一步拆分,或者應當考慮更換速度更高、能力更強的CPU,。

　　子程序是程序設計中廣泛應用的一種程序結(jié)構(gòu),。在本模型的基礎上,可以將子程序設計為子進程。子進程同樣可按“前向分支”原則拆分為子線程,這樣,系統(tǒng)中仍然可以消除所有的局部循環(huán),。子線程的拆分方法與上述線程的拆分方法類似,但需注意調(diào)用時的爭用和重入問題,。

　　以上介紹模型的調(diào)度算法簡單,、實現(xiàn)方法規(guī)范、對CPU資源沒有特殊的要求,。在實際應用中,該模型可以根據(jù)項目的具體情況靈活地變通和擴充,。同時,該模型比較容易工程化實施,便于快速、低成本地構(gòu)造系統(tǒng)程序的原型,。但該模型沒有對進程設置嚴格意義上的優(yōu)先級,另外,源程序的可讀性也不太令人滿意,。

　　與通用操作系統(tǒng)不同,該模型適用于靜態(tài)內(nèi)存分配和資源分配的確定性任務(多數(shù)的單片機應用項目和機電設備控制系統(tǒng)屬于這種情形)。顯然,該模型不適合那些在運行時動態(tài)加載,、需要進行動態(tài)內(nèi)存分配和資源分配的不確定性任務,。

?

參考文獻

1 Andrew S. Tanenbaum， Albert S. Woodhull.Operating System：design and implementation 2nd Ed.Prentice Hall,，Inc.,，1997

2 張海藩.軟件工程導論(第三版).北京:清華大學出版社,1998