引言

在微機(jī)控制領(lǐng)域中，許多單片機(jī)應(yīng)用系統(tǒng)是實時控制系統(tǒng)RTCS（Real Time Control System）。在實時控制系統(tǒng)中，為了很好地完成外界信息的實時測量、計算和相應(yīng)的多種實時控制操作，必須達(dá)到兩個設(shè)計目標(biāo)；實時性和并行性。即既要保證系統(tǒng)對外界信息以足夠快的速度進(jìn)行相應(yīng)處理，又要同時完成多種任務(wù)操作。在這里，多種任務(wù)之間的調(diào)度是個關(guān)鍵。

RTCS 中允許多個實時任務(wù)并行地運(yùn)行。例如，一測控系統(tǒng)中，具有數(shù)據(jù)采集、數(shù)據(jù)計算、鍵盤處理、定時打印等任務(wù)。在單機(jī)系統(tǒng)中，這些任務(wù)在宏觀上是同時運(yùn)行的，但在微觀上只有一個任務(wù)運(yùn)行。在RTCS中每個任務(wù)有三種狀態(tài)，即運(yùn)行狀態(tài)、就緒狀態(tài)和空閑狀態(tài)。某個任務(wù)一旦建立后即處于這三種狀態(tài)之一。處于運(yùn)行狀態(tài)的任務(wù)獨(dú)占CPU和其它一些資源；就緒狀態(tài)是某個任務(wù)現(xiàn)在應(yīng)該運(yùn)行，但由于其它任務(wù)正在運(yùn)行，故只能暫時等待；當(dāng)激發(fā)某個任務(wù)的條件不完備時，此任務(wù)就處于空閑狀態(tài)。

RTCS中的多個任務(wù)依靠任務(wù)調(diào)度程序來決定系統(tǒng)中哪個任務(wù)可以獲得CPU等資源或應(yīng)暫時退出運(yùn)行狀態(tài)等，從而完成每個任務(wù)三態(tài)間的轉(zhuǎn)換。在RTCS中，任務(wù)調(diào)度算法的優(yōu)劣直接關(guān)系到系統(tǒng)的實時性能與并行性能。

RTCS中較簡單的任務(wù)調(diào)度算法有“先來先執(zhí)行的調(diào)度算法”、“按時間片循環(huán)執(zhí)行的調(diào)度算法”。前者，當(dāng)實時性比較差的任務(wù)長時間占用CPU時，會使得實時性較高的任務(wù)得不到及時處理，影響系統(tǒng)的實時性；后者，按照“先入先出”的原則激活某個任務(wù)，并分配給它們相等的時間片，從而使得多個任務(wù)有平等的享用CPU的權(quán)利。當(dāng)時間片用完時，讓任務(wù)“暫時”又處于就緒狀態(tài)，并激活下一個任務(wù)。這種算法的實時性有一定程序的提高，但由于各任務(wù)簡單均勻地循環(huán)輪回，從而使得實時性要求較高的任務(wù)得不到優(yōu)先處理。由于各時間片相等且固定，很容易被某些緊急任務(wù)打斷。在實時性要求較高而且任務(wù)較多的復(fù)雜情況下，各個任務(wù)的實時性要求不盡相同，不能簡單地均勻分時處理任務(wù)。

基于比特表的任務(wù)調(diào)度算法，關(guān)鍵在于將CPU的全部時間化成若干個相等的時隙，同時根據(jù)任務(wù)的數(shù)目制定一張表格，以此來指示某一時刻的任務(wù)運(yùn)行。它把任務(wù)按照實時性要求分成中斷級、時鐘級、基本級三類，而且它們的優(yōu)先級依次遞減。優(yōu)先級越高，就越處于比特表的頂端位置。比特表是按照任務(wù)的優(yōu)先級排隊的，首先滿足實時性較強(qiáng)的中斷級和時鐘級，而不管實時性最低的基本級任務(wù)。這樣，時鐘級任務(wù)一定能得到即時有效的處理，其實時性可以得到較好的保障，基本級任務(wù)可以沒有時間限制。但是，時鐘級任務(wù)的實時性并不是完全能夠得到保障。下面舉例討論比特表算法的不足之處。

假定有表1所示的五種任務(wù)，按照常規(guī)比特表算法根本無法設(shè)計出這樣的比特表。當(dāng)時鐘級的各級每次運(yùn)行時間之和沒有達(dá)到5ms時，比特表算法能夠很好地滿足系統(tǒng)實時性要求；然而，當(dāng)中斷級和時鐘級的每次運(yùn)行時間之和大于或者等于最高級實時性要求，更有甚者，當(dāng)有一個時鐘級任務(wù)的運(yùn)行時間超過最高級實時性要求時，比特表算法就會失效。因為常規(guī)的比特表算法要求，只要激活比特表中安排的中斷級和時鐘級任務(wù)就必須一次執(zhí)行完，否則，如果這個任務(wù)被中斷就無法再得到執(zhí)行。由于圖像處理的運(yùn)行時間為5ms，加上中斷級任務(wù)執(zhí)行時間，因此設(shè)計時隙必須大于5ms；而比特表的設(shè)計方法時隙只可能小于等于5ms（中斷級任務(wù)和實時性最高的時鐘級任務(wù)決定的）。所以，無論安排怎樣的比徨表都無法使任務(wù)D滿足實時性要求?；谶@兩種情況，本文提出一種用賦有優(yōu)先權(quán)的時間來填充比特表的算法，以改善這兩種情況。

1 比特表的改進(jìn)算法

這種改進(jìn)算法的關(guān)系在于把各任務(wù)劃分為若干時間片，然后再根據(jù)實時性要求填入比特表中。根據(jù)比特表的設(shè)計方法，時隙間隔定為5ms，總時隙數(shù)為LCM（10/5，20/5，30/5）=6。把各中斷級和時鐘級任務(wù)運(yùn)行時間的最大公約數(shù)定為時間片。即有如下計算公式：

T=GCD{Ti}

T為時間片，Ti為時鐘級和中斷級任務(wù)實時性要求，GCD（Greatest Common Divisor）求最大公約數(shù)，LCM（Lowest Common Multiple）求最小公倍數(shù)。

本例中的時間片T=GCD{0.5，1，2.5，1，5}=0.5ms。（假設(shè)時鐘中斷處理時間為0.5ms）。

時間片的分配，必須遵循以下原則：

①滿足實時性要求；

②確保每一個時隙中所有分配的任務(wù)都必須完全運(yùn)行；

③均衡考慮CPU對各任務(wù)的運(yùn)行，優(yōu)先考慮時鐘級任務(wù)和中斷級任務(wù)。

按上述原則，中斷級任務(wù)分1個時間片，時鐘級1分配2個時間片，時鐘級2分配3個時間片，時鐘級3分配1個時間片，時鐘級4分配2個時間片，而將每個時隙剩余的時間分配給基本級任務(wù)。這樣，即使是在系統(tǒng)最繁忙的時候也有一個時間片分配給基本級任務(wù)，從而彌補(bǔ)了比特表算法的不足。

綜上所述，設(shè)計圖1所示的比特表。

此比特表的時隙任務(wù)安排完全滿足實時性要求。A任務(wù)每時隙運(yùn)行1次，每時隙運(yùn)行2個時間片。A任務(wù)每5ms運(yùn)行1次。B任務(wù)每10ms運(yùn)行1次，C任務(wù)每 20ms運(yùn)行1次。由此可以得到各任務(wù)的啟動順序及執(zhí)行時間如圖2所示。

圖2 任務(wù)的啟動順序和運(yùn)行時間

圖2中，I表示時鐘中斷處理程序，它的優(yōu)先級最高。A、B、C、D為時鐘級任務(wù)，其中A的優(yōu)先級較高。將I、A、B、C、D處理完后余下的時間留給基本級E。

2 程序設(shè)計值得注意的問題

在任務(wù)調(diào)度算法中，關(guān)鍵是如何確定就緒隊列、任務(wù)控制數(shù)據(jù)塊的數(shù)據(jù)結(jié)構(gòu)和解決資源沖突。就緒隊列指明了在某一時刻已就緒、可被執(zhí)行的任務(wù)隊列。在數(shù)據(jù)結(jié)構(gòu)上通?？捎梦挥诚竦姆椒▉韺崿F(xiàn)。如系統(tǒng)的最多任務(wù)為32個，可采用4個字節(jié)的每一位來對應(yīng)人某個任務(wù)。若此位為“1”，則表明該任務(wù)就緒；若為“0”，則表明任務(wù)空閑。并且可規(guī)定低位所代表的任務(wù)優(yōu)先級高于高位所指示的任務(wù)。

某個任務(wù)投入運(yùn)行時需保護(hù)現(xiàn)場數(shù)據(jù)，這些數(shù)據(jù)都存入一個地址固定的數(shù)據(jù)存儲區(qū)，稱為任務(wù)控制數(shù)據(jù)塊。需保護(hù)的內(nèi)容應(yīng)按應(yīng)用程序的特點(diǎn)來決定。對于常用的 MCS51系列的單片機(jī)來說，現(xiàn)場保護(hù)數(shù)據(jù)一般應(yīng)包括PC、ACC、PSW、SP、DPTR等寄存器內(nèi)容。任務(wù)控制數(shù)據(jù)塊一般放在外部數(shù)據(jù)存儲器內(nèi)。為了查找方便，可以按任務(wù)號將各個任務(wù)數(shù)據(jù)塊的首地址編成一個一維表格，表格的每行對應(yīng)各任務(wù)數(shù)據(jù)塊數(shù)據(jù)結(jié)構(gòu)首地址，如圖3所示。

在任務(wù)調(diào)度程序中，還應(yīng)很好地解決資源的互斥問題，即保證不可共享的資源只被一個任務(wù)所訪問。在RTCS中，各任務(wù)間并非完全隔絕，它們相互合作、相互競爭。例如，某系統(tǒng)中數(shù)據(jù)顯示任務(wù)要定時顯示某數(shù)據(jù)區(qū)的數(shù)據(jù)；數(shù)據(jù)計算任務(wù)也要在某種情況下計算、刷新此數(shù)據(jù)區(qū)內(nèi)容。在這里，數(shù)據(jù)計算任務(wù)在運(yùn)行時就不允許讓顯示任務(wù)中斷計算任務(wù)；否則，有可能導(dǎo)致顯示的數(shù)據(jù)不正確。解決資源競爭的方法往往是在主程序中設(shè)置一標(biāo)志字節(jié)或標(biāo)志位。例如，顯示任務(wù)在運(yùn)行時首先判斷此標(biāo)志，若發(fā)現(xiàn)計算任務(wù)尚未完成，則不做任何工作直接退出任務(wù)。

3 小結(jié)

RTCS 中的實時性和并行性是非常重要的，但兩者之間有一定的矛盾。完全實現(xiàn)在兩大特性的重要手段就是，采用有效的任務(wù)調(diào)度算法程序來協(xié)調(diào)兩者之間的矛盾，從而保證系統(tǒng)的實時性和并行性。在簡單系統(tǒng)中，“按時間片循環(huán)”調(diào)度算法已能初步滿足要求；但在較復(fù)雜和要求較高的系統(tǒng)中，這顯然不滿足需要。基于BitMap 的調(diào)度算法能較好地滿足比較復(fù)雜系統(tǒng)的要求，而對于前面講到的系統(tǒng)中要求執(zhí)行時間長、實時性要求較高的任務(wù)而言，單純的BitMap算法無法滿足要求，這個時候我們提出將比特表的時隙細(xì)分成時間片進(jìn)行分配，這比BitMap按照任務(wù)進(jìn)行分配的算法更能解決復(fù)雜任務(wù)的實時性要求。只要有效地確定任務(wù)數(shù)目和數(shù)據(jù)結(jié)構(gòu)，RTCS中的實時性和并行性就能得到有效提高。

責(zé)任編輯：gt