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

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

?

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

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

1 進(jìn)程的劃分

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

?

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

2 線程的拆分

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

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

?

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

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

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

?

?

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

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

3 總體模型

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

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

?

?

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

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

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

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

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

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

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

?

參考文獻(xiàn)

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

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