一種基于比特表的實(shí)時(shí)多任務(wù)新調度算法

關(guān)鍵詞：比特表 時(shí)間片 實(shí)時(shí)處理

引言

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

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

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

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

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

圖2 任務(wù)的啟動(dòng)順序和運行時(shí)間

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

表1 實(shí)時(shí)性要求和各任務(wù)運行時(shí)間表

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

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

T=GCD{Ti}

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

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

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

①滿(mǎn)足實(shí)時(shí)性要求；

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

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

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

綜上所述，設計圖1所示的比特表。

此比特表的時(shí)隙任務(wù)安排完全滿(mǎn)足實(shí)時(shí)性要求。A任務(wù)每時(shí)隙運行1次，每時(shí)隙運行2個(gè)時(shí)間片。A任務(wù)每5ms運行1次。B任務(wù)每10ms運行1次，C任務(wù)每20ms運行1次。由此可以得到各任務(wù)的啟動(dòng)順序及執行時(shí)間如圖2所示。圖2中，I表示時(shí)鐘中斷處理程序，它的優(yōu)先級最高。A、B、C、D為時(shí)鐘級任務(wù)，其中A的優(yōu)先級較高。將I、A、B、C、D處理完后余下的時(shí)間留給基本級E。

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

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

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

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

3 小結

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