一種實(shí)時(shí)多任務(wù)系統(tǒng)軟件設(shè)計(jì)方法

摘要：從進(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í)操作系統(tǒng)的基礎(chǔ)上進(jìn)行二次開發(fā);二是用戶自動(dòng)設(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ù)進(jì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)cDispiay不為0時(shí)，依次從aDlsplay中取出每個(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)重的問題。例如在Proc_5中，當(dāng)程序處于等待K1閉合的狀態(tài)時(shí)，其它任何進(jìn)程都無法得到服務(wù)，尤其當(dāng)K1出現(xiàn)故障時(shí)，系統(tǒng)將處于“掛起”狀態(tài)。如果一個(gè)進(jìn)程過多地占據(jù)了CPU時(shí)間，其他進(jìn)程將不能得到公平、均勻的服務(wù)，響應(yīng)時(shí)間無法得到保證，系統(tǒng)效率會(huì)降低。總之，只有將CPU時(shí)間的分配單位減小，才能解決上述問題。

2 線程的拆分

線程(Thread)是CPU的基本執(zhí)行單位。一個(gè)進(jìn)程可以由一個(gè)或多個(gè)線程構(gòu)成。如前所述，單一線程的進(jìn)程可能會(huì)存在諸多問題，而將一進(jìn)程拆分為多個(gè)線程是解決上述問題的有效手段。由圖1的Proc_5和Proc_9可以看出，一個(gè)進(jìn)程過多地占據(jù)CPU時(shí)間，是因?yàn)槠渲泻写螖?shù)不確定的等待循環(huán)、純延時(shí)和較為耗時(shí)的多重循環(huán)。其中，純延時(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í)行過的代碼，而不得重復(fù)運(yùn)行已運(yùn)行過的代碼。如果嚴(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)之間如無程序代碼，最小拆分?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è)線程的對(duì)待。如果原進(jìn)程中無循環(huán)，可將該進(jìn)程當(dāng)做單一線程對(duì)等。在圖1中，Proc_9中共有4個(gè)循環(huán)返回節(jié)點(diǎn)(①～④)，Nback=4。按最小拆分?jǐn)?shù)量拆分中循環(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的方法設(shè)度各線程就可以實(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è)置好其初值，由一個(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。[!--empirenews.page--]

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í)間按所有定時(shí)任務(wù)的最大公約數(shù)來選取，所選取中斷間隔時(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)格按照“前向分支”原則拆分線程是，拆分?jǐn)?shù)量不應(yīng)上于時(shí)程中的循環(huán)返回節(jié)點(diǎn)數(shù)Nback和Nback+1。這是拆分線程時(shí)重要的參考依據(jù)。但是，在實(shí)際應(yīng)用中，并不一定非要將線程中的循環(huán)徹底消除，應(yīng)當(dāng)根據(jù)具體情況和實(shí)際需求靈活掌握。

如果拆分粒度過細(xì)(即線程拆分?jǐn)?shù)量過多)，雖然對(duì)提高系統(tǒng)的響應(yīng)速度有幫助，但由于進(jìn)程切換過于頻繁，進(jìn)程切換所需的額外開銷會(huì)導(dǎo)致系統(tǒng)效率下降(即有效的CPU機(jī)時(shí)占CPU總機(jī)時(shí)的比例下降)。粒度越細(xì)，這種情況也就越嚴(yán)重。另外，粒度越細(xì)，源程序和程序文檔的可讀性越差，這程序的調(diào)試和維護(hù)以及文檔的維護(hù)帶來困難。因此，在能夠保證系統(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ì)于本文所介紹的模型來說，由于進(jìn)程都是確定的，響應(yīng)時(shí)間可以大致按以下方法估算：各地程中最耗時(shí)線程的運(yùn)行時(shí)間之和就是最不利的響應(yīng)時(shí)間，平均響應(yīng)時(shí)間應(yīng)等于各進(jìn)程中線程平均運(yùn)行時(shí)間之和的二分之一。根據(jù)以上估算，還可以大致推斷運(yùn)行期間發(fā)生過幾次定時(shí)中斷。將基礎(chǔ)定時(shí)中斷所占用的CPU時(shí)間也估算進(jìn)去，可以進(jìn)一步提高響應(yīng)時(shí)間估算的準(zhǔn)確度。當(dāng)然，響應(yīng)時(shí)間也可以通過實(shí)驗(yàn)來測(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)用和重入問題。

以上介紹模型的調(diào)度算法簡(jiǎn)單、實(shí)現(xiàn)方法規(guī)范、對(duì)CPU資源沒有特殊的要求。在實(shí)現(xiàn)應(yīng)用中，該模型可以根據(jù)項(xiàng)目的具體情況靈活地變通和擴(kuò)充。同時(shí)，該模型比較容易工程化實(shí)施，便于快速、低成本地構(gòu)造系統(tǒng)程序的原型。但該模型沒有對(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ù)。