摘? 要: 從進程和線程調度的角度出發,介紹了一種規范化的實時多任務系統軟件設計方法,提出了“前向分支”的設計原則,給出了完整的系統模型。
關鍵詞: 線程拆分? 前向分支? 實時多任務? 單片機
?
在機電產品研制開發中,經常要涉及到基于嵌入式系統或基于單片機系統的程序設計。實時多任務是這類系統最基本的要求之一。在實踐中通常采用以下兩種解決方案:一是在商業化實時操作系統的基礎上進行二次開發;二是用戶自行設計系統軟件。前者設計工作量小,設計周期短,系統的設計質量也容易得到保證。但由于商業化實時操作系統往往較多地考慮通用性,缺乏靈活性,對于一些特定的應用場合,其性能往往不能令人滿意。同時,這種方案還存在著成本高,依賴于特定硬件等缺點。第二種方案可以從系統的實際要求和硬件的實際情況出發靈活地進行系統設計,易于滿足一些特定場合的性能要求,成本也較低。但是,由于缺乏系統化、規范化的設計方法,缺少高層次抽象工具,使得系統的設計質量不容易得到保證,并嚴重地依賴于程序員的水平和經驗。
本文針對上述第二種方案的局限,從進程和線程調度的角度出發,介紹了一種系統化、規范化和易于工程化實施的實時多任務系統軟件設計方法,提出了“前向分支”的設計原則,并給出了完整的系統模型。
1 進程的劃分
對復雜的系統需求進行模塊化和層次化的劃分是軟件設計的基本方法。在實踐中,復雜的系統需求通常被劃分為一些功能相對獨立的任務模塊,每個任務模塊被視作一個進程(process)。系統中如有多個進程并發(concurrent)運行,該系統就是一個多任務的系統。在圖1所示的例子中,n個任務模塊構成了宏觀上并發運行的一組進程(即Proc_1～Proc_n)。Proc_5和Proc_9是兩個具有代表性的進程結構。Proc_5是斷續運行的進程,表示了某一順序邏輯控制的流程。Proc_9是LCD漢字顯示程序,其結構是典型的多重循環。其功能是將數組aDisplay中所描述的24×24點陣中文字符串送至LCD顯示屏。aDisplay的結構參見圖3(e)。Proc_9的基本工作原理如下:當cDisplay不為0時,依次從aDisplay中取出每個待顯示漢字的點陣位置及其在LCD內部顯存中的地址,根據這兩個參數將一個漢字的點陣順序發送到LCD內部顯存中。直至全部漢字顯示完,cDisplay減為0,Proc_9轉入空閑狀態,等待新的顯示請求。
?
系統程序的主要任務之一就是對進程進行調度,包括啟動和終止進程、管理進程之間的通訊、處理進程之間的優先級等。但是如果按圖1的結構順序調度進程、以進程為基本單位分配CPU時間的話,顯然存在嚴重的問題。例如在Proc_5中,當程序處于等待K1閉合的狀態時,其它任何進程都無法得到服務,尤其當K1出現故障時,系統將處于“掛起”狀態。如果一個進程過多地占據了CPU時間,其他進程將不能得到公平、均勻的服務,響應時間無法得到保證,系統效率會降低。總之,只有將CPU時間的分配單位減小,才能解決上述問題。
2 線程的拆分
線程(Thread)是CPU的基本執行單位。一個進程可以由一個或多個線程構成。如前所述,單一線程的進程可能會存在諸多問題,而將一進程拆分為多個線程是解決上述問題的有效手段。由圖1的Proc_5和Proc_9可以看出,一個進程過多地占據CPU時間，是因為其中含有次數不確定的等待循環、純延時和較為耗時的多重循環。其中,純延時可以用軟件延時和中斷定時兩種方法實現,這兩種方法在進程中又都可以歸結為循環。因此,在拆分線程時應盡量遵循“前向分支”原則,使線程中不含有或少含有循環。
循環結構本質上是由一個分支判斷和一個“反向”轉跳構成的。所謂“前向分支”原則是指:在一次調度中,當程序發生分支時,應使程序跳向一段未被執行過的代碼,而不得重復運行已運行過的代碼。如果嚴格按“前向分支”原則拆分線程,循環結構將被完全消除。圖2和圖3分別是Proc_5和Proc_9嚴格按“前向分支”原則拆分為線程的結果。
?
如果進程設計遵循結構化程序思想,那么在對某一進程嚴格按“前向分支”原則進行線程拆分時,最小拆分數量可按如下方法確定:進程入口至第一個循環返回節點之間如無程序代碼,最小拆分數量等于循環返回節點數Nback;進程入口至第一個循環返回節點之間如有程序代碼,最小拆分數量等于Nback+1。實際拆分數量可以大于最小拆分數量,但不應小于該數,否則必然有一個以上的線程中含有循環。兩個循環返回節點之間(或入口到第一個循環返回節點之間、最后一個循環返回節點到出口之間)的代碼就構成了一個線程的主體。如果原進程中無循環,可將該進程當做單一線程對待。在圖1中,Proc_9中共有4個循環返回節點(①～④),即Nback=4,按最小拆分數量拆分為4個線程(Proc_9Thread_1～Proc_9Thread_4)。Proc_5中循環返回節點數也為4,但其入口至第一個循環返回節點之間有代碼,所以,Proc_5按最小拆分數量拆分為5個線程。
線程號變量tProc_n是系統中實現線程調度、在各相關線程間建立聯系的核心。按“前向分支”原則進行線程拆分時,凡是遇到構成循環的“反向”分支時,就將該分支轉向當前線程的出口,并在出口前為所在進程的線程號變量賦一新值指向要轉去的線程。如果所要轉去的線程與當前所在線程一致時,線程號變量賦值可以省略。
在按“前向分支”原則設計的線程中,“結構上”的循環可以完全消除,但進程設計中“邏輯上”的循環仍然是存在的,否則進程的原有功能將不能正確地實現。事實上,線程號變量中包含有“邏輯循環”的信息。只要在主循環中按圖4的方法調度各線程就可以實現進程的“邏輯循環”。
?
?
為實現中斷定時,Proc_5中設置了兩個定時計數器cTimerAct_1和cTimerAct_2(以下稱之為“動作定時器”),在啟動定時時設置好其初值,由一個基礎定時中斷程序按一定的時間間隔(本例為1ms)減1。當動作定時器減為0時表示定時結束。
對于斷續運行的進程(如Proc_5),結束任務時應將線程號變量指向任意一個不用的空線程。為統一和方便起見,本文約定所有進程的0號線程均為空線程,進程結束時線程號變量應置為0。
3 總體模型
綜上所述,一個完整的、嚴格按“前向分支”原則進行線程拆分和進程調度的多任務系統模型可以歸納為圖5所示的結構。該模型由三部分構成:主循環、分屬于不同進程的“前向分支”的線程以及一個基礎定時中斷程序。該模型結構最大的特點是:除了主循環中最后一個回跳以外,其它任何地方都不存在循環結構。換言之,系統中所有的循環“反向”轉跳,都被歸并成了主循環中的一個回跳。這樣的結構能使主循環在各進程間快速地切換,有利于提高CPU的利用率,改善系統的響應,使得各進程能夠得到及時、均勻、公平的服務。同時,基礎定時中斷程序也完全是“前向分支”結構,有利于減少對CPU的占用。
考慮到各進程對響應時間和服務頻度的不同要求,在該模型中設置了對各進程進行定時同步的功能。在基礎定時中斷服務程序中增加了同步定時器cTimerSyn_i和同步定時標志fTimerSyn_i。同步定時器和動作定時器構成了基礎定時中斷服務程序的主體。基礎定時中斷的中斷間隔時間應按所有定時任務的最大公約數來選取,所選取中斷間隔時間越大,對CPU的占用越少,越有利于系統效率的提高。
?
?
進程定時同步的本質是為不同響應時間需求的任務安排不同的服務頻度。降低低優先級任務的服務頻度相當于提高了高優先級任務的服務頻度。在很多情況下,這樣的優先級處理已令人滿意。有一類進程出于功能(而不一定是優先級)的需要,也必須進行定時同步。
如前所述,嚴格按照“前向分支”原則拆分線程時,拆分數量不應小于進程中的循環返回節點數Nback或Nback+1。這是拆分線程時重要的參考依據。但是,在實際應用中,并不一定非要將線程中的循環徹底消除,應當根據具體情況和實際需求靈活掌握。
如果拆分粒度過細(即線程拆分數量過多),雖然對提高系統的響應速度有幫助,但由于進程切換過于頻繁,進程切換所需的額外開銷會導致系統效率下降(即有效的CPU機時占CPU總機時的比例下降)。粒度越細,這種情況也就越嚴重。另外,粒度越細,源程序和程序文檔的可讀性越差,為程序的調試和維護以及文檔的維護帶來困難。因此,在能夠保證系統的響應速度和調度的均勻性等前提之下,拆分粒度傾向于粗一些。在多數情況下,傾向于將次數不確定的等待循環、較為耗時的循環和較長的純延時拆分為線程。而那些循環次數確定且不太耗時的循環則建議保留。在這種情況下,線程拆分數小于Nback或Nback+1。
實時系統要求系統能夠對輸入做出快速的反應和處理。但是,“實時”只是一個相對的概念,響應時間快慢實際上是衡量一個系統是否“實時”的重要指標。由圖5可以看出,對于本文所介紹的模型來說,由于進程都是確定的,響應時間可以大致按以下方法估算:各進程中最耗時線程的運行時間之和就是最不利的響應時間,平均響應時間應等于各進程中線程平均運行時間之和的二分之一。根據以上估算,還可以大致推斷運行期間發生過幾次定時中斷。將基礎定時中斷所占用的CPU時間也估算進去,可以進一步提高響應時間估算的準確度。當然,響應時間也可以通過實驗來測定。如果響應時間不能滿足某一任務的要求,可以將長線程進一步拆分,或者應當考慮更換速度更高、能力更強的CPU。
子程序是程序設計中廣泛應用的一種程序結構。在本模型的基礎上,可以將子程序設計為子進程。子進程同樣可按“前向分支”原則拆分為子線程,這樣,系統中仍然可以消除所有的局部循環。子線程的拆分方法與上述線程的拆分方法類似,但需注意調用時的爭用和重入問題。
以上介紹模型的調度算法簡單、實現方法規范、對CPU資源沒有特殊的要求。在實際應用中,該模型可以根據項目的具體情況靈活地變通和擴充。同時,該模型比較容易工程化實施,便于快速、低成本地構造系統程序的原型。但該模型沒有對進程設置嚴格意義上的優先級,另外,源程序的可讀性也不太令人滿意。
與通用操作系統不同,該模型適用于靜態內存分配和資源分配的確定性任務(多數的單片機應用項目和機電設備控制系統屬于這種情形)。顯然,該模型不適合那些在運行時動態加載、需要進行動態內存分配和資源分配的不確定性任務。
?
參考文獻
1 Andrew S. Tanenbaum， Albert S. Woodhull.Operating System：design and implementation 2nd Ed.Prentice Hall，Inc.，1997
2 張海藩.軟件工程導論(第三版).北京:清華大學出版社,1998