一種基于比特表的實(shí)時(shí)多任務(wù)新調(diào)度算法
掃描二維碼
隨時(shí)隨地手機(jī)看文章
關(guān)鍵詞:比特表 時(shí)間片 實(shí)時(shí)處理
引言
在微機(jī)控制領(lǐng)域中,許多單片機(jī)應(yīng)用系統(tǒng)是實(shí)時(shí)控制系統(tǒng)RTCS(Real Time Control System)。在實(shí)時(shí)控制系統(tǒng)中,為了很好地完成外界信息的實(shí)時(shí)測量、計(jì)算和相應(yīng)的多種實(shí)時(shí)控制操作,必須達(dá)到兩個(gè)設(shè)計(jì)目標(biāo);實(shí)時(shí)性和并行性。即既要保證系統(tǒng)對(duì)外界信息以足夠快的速度進(jìn)行相應(yīng)處理,又要同時(shí)完成多種任務(wù)操作。在這里,多種任務(wù)之間的調(diào)度是個(gè)關(guān)鍵。
RTCS中允許多個(gè)實(shí)時(shí)任務(wù)并行地運(yùn)行。例如,一測控系統(tǒng)中,具有數(shù)據(jù)采集、數(shù)據(jù)計(jì)算、鍵盤處理、定時(shí)打印等任務(wù)。在單機(jī)系統(tǒng)中,這些任務(wù)在宏觀上是同時(shí)運(yùn)行的,但在微觀上只有一個(gè)任務(wù)運(yùn)行。在RTCS中每個(gè)任務(wù)有三種狀態(tài),即運(yùn)行狀態(tài)、就緒狀態(tài)和空閑狀態(tài)。某個(gè)任務(wù)一旦建立后即處于這三種狀態(tài)之一。處于運(yùn)行狀態(tài)的任務(wù)獨(dú)占CPU和其它一些資源;就緒狀態(tài)是某個(gè)任務(wù)現(xiàn)在應(yīng)該運(yùn)行,但由于其它任務(wù)正在運(yùn)行,故只能暫時(shí)等待;當(dāng)激發(fā)某個(gè)任務(wù)的條件不完備時(shí),此任務(wù)就處于空閑狀態(tài)。
RTCS中的多個(gè)任務(wù)依靠任務(wù)調(diào)度程序來決定系統(tǒng)中哪個(gè)任務(wù)可以獲得CPU等資源或應(yīng)暫時(shí)退出運(yùn)行狀態(tài)等,從而完成每個(gè)任務(wù)三態(tài)間的轉(zhuǎn)換。在RTCS中,任務(wù)調(diào)度算法的優(yōu)劣直接關(guān)系到系統(tǒng)的實(shí)時(shí)性能與并行性能。
RTCS中較簡單的任務(wù)調(diào)度算法有“先來先執(zhí)行的調(diào)度算法”、“按時(shí)間片循環(huán)執(zhí)行的調(diào)度算法”。前者,當(dāng)實(shí)時(shí)性比較差的任務(wù)長時(shí)間占用CPU時(shí),會(huì)使得實(shí)時(shí)性較高的任務(wù)得不到及時(shí)處理,影響系統(tǒng)的實(shí)時(shí)性;后者,按照“先入先出”的原則激活某個(gè)任務(wù),并分配給它們相等的時(shí)間片,從而使得多個(gè)任務(wù)有平等的享用CPU的權(quán)利。當(dāng)時(shí)間片用完時(shí),讓任務(wù)“暫時(shí)”又處于就緒狀態(tài),并激活下一個(gè)任務(wù)。這種算法的實(shí)時(shí)性有一定程序的提高,但由于各任務(wù)簡單均勻地循環(huán)輪回,從而使得實(shí)時(shí)性要求較高的任務(wù)得不到優(yōu)先處理。由于各時(shí)間片相等且固定,很容易被某些緊急任務(wù)打斷。在實(shí)時(shí)性要求較高而且任務(wù)較多的復(fù)雜情況下,各個(gè)任務(wù)的實(shí)時(shí)性要求不盡相同,不能簡單地均勻分時(shí)處理任務(wù)。
基于比特表的任務(wù)調(diào)度算法,關(guān)鍵在于將CPU的全部時(shí)間化成若干個(gè)相等的時(shí)隙,同時(shí)根據(jù)任務(wù)的數(shù)目制定一張表格,以此來指示某一時(shí)刻的任務(wù)運(yùn)行。它把任務(wù)按照實(shí)時(shí)性要求分成中斷級(jí)、時(shí)鐘級(jí)、基本級(jí)三類,而且它們的優(yōu)先級(jí)依次遞減。優(yōu)先級(jí)越高,就越處于比特表的頂端位置。比特表是按照任務(wù)的優(yōu)先級(jí)排隊(duì)的,首先滿足實(shí)時(shí)性較強(qiáng)的中斷級(jí)和時(shí)鐘級(jí),而不管實(shí)時(shí)性最低的基本級(jí)任務(wù)。這樣,時(shí)鐘級(jí)任務(wù)一定能得到即時(shí)有效的處理,其實(shí)時(shí)性可以得到較好的保障,基本級(jí)任務(wù)可以沒有時(shí)間限制。但是,時(shí)鐘級(jí)任務(wù)的實(shí)時(shí)性并不是完全能夠得到保障。下面舉例討論比特表算法的不足之處。
圖2 任務(wù)的啟動(dòng)順序和運(yùn)行時(shí)間
假定有表1所示的五種任務(wù),按照常規(guī)比特表算法根本無法設(shè)計(jì)出這樣的比特表。當(dāng)時(shí)鐘級(jí)的各級(jí)每次運(yùn)行時(shí)間之和沒有達(dá)到5ms時(shí),比特表算法能夠很好地滿足系統(tǒng)實(shí)時(shí)性要求;然而,當(dāng)中斷級(jí)和時(shí)鐘級(jí)的每次運(yùn)行時(shí)間之和大于或者等于最高級(jí)實(shí)時(shí)性要求,更有甚者,當(dāng)有一個(gè)時(shí)鐘級(jí)任務(wù)的運(yùn)行時(shí)間超過最高級(jí)實(shí)時(shí)性要求時(shí),比特表算法就會(huì)失效。因?yàn)槌R?guī)的比特表算法要求,只要激活比特表中安排的中斷級(jí)和時(shí)鐘級(jí)任務(wù)就必須一次執(zhí)行完,否則,如果這個(gè)任務(wù)被中斷就無法再得到執(zhí)行。由于圖像處理的運(yùn)行時(shí)間為5ms,加上中斷級(jí)任務(wù)執(zhí)行時(shí)間,因此設(shè)計(jì)時(shí)隙必須大于5ms;而比特表的設(shè)計(jì)方法時(shí)隙只可能小于等于5ms(中斷級(jí)任務(wù)和實(shí)時(shí)性最高的時(shí)鐘級(jí)任務(wù)決定的)。所以,無論安排怎樣的比徨表都無法使任務(wù)D滿足實(shí)時(shí)性要求?;谶@兩種情況,本文提出一種用賦有優(yōu)先權(quán)的時(shí)間來填充比特表的算法,以改善這兩種情況。
表1 實(shí)時(shí)性要求和各任務(wù)運(yùn)行時(shí)間表
序 號(hào) | 任 務(wù) | 優(yōu)先級(jí) | 實(shí)時(shí)性要求/ms | 每次運(yùn)行時(shí)間/ms |
A | 數(shù)據(jù)采集 | 時(shí)鐘級(jí) | 5 | 1 |
B | 端口檢測 | 時(shí)鐘級(jí) | 10 | 2.5 |
C | 鍵盤掃描 | 時(shí)鐘級(jí) | 15 | 1 |
D | 圖像處理 | 時(shí)鐘級(jí) | 30 | 5 |
E | 打印數(shù)據(jù) | 基本級(jí) | 無實(shí)時(shí)要求 | 200 |
1 比特表的改進(jìn)算法
這種改進(jìn)算法的關(guān)系在于把各任務(wù)劃分為若干時(shí)間片,然后再根據(jù)實(shí)時(shí)性要求填入比特表中。根據(jù)比特表的設(shè)計(jì)方法,時(shí)隙間隔定為5ms,總時(shí)隙數(shù)為LCM(10/5,20/5,30/5)=6。把各中斷級(jí)和時(shí)鐘級(jí)任務(wù)運(yùn)行時(shí)間的最大公約數(shù)定為時(shí)間片。即有如下計(jì)算公式:
T=GCD{Ti}
T為時(shí)間片,Ti為時(shí)鐘級(jí)和中斷級(jí)任務(wù)實(shí)時(shí)性要求,GCD(Greatest Common Divisor)求最大公約數(shù),LCM(Lowest Common Multiple)求最小公倍數(shù)。
本例中的時(shí)間片T=GCD{0.5,1,2.5,1,5}=0.5ms。(假設(shè)時(shí)鐘中斷處理時(shí)間為0.5ms)。
時(shí)間片的分配,必須遵循以下原則:
①滿足實(shí)時(shí)性要求;
②確保每一個(gè)時(shí)隙中所有分配的任務(wù)都必須完全運(yùn)行;
③均衡考慮CPU對(duì)各任務(wù)的運(yùn)行,優(yōu)先考慮時(shí)鐘級(jí)任務(wù)和中斷級(jí)任務(wù)。
按上述原則,中斷級(jí)任務(wù)分1個(gè)時(shí)間片,時(shí)鐘級(jí)1分配2個(gè)時(shí)間片,時(shí)鐘級(jí)2分配3個(gè)時(shí)間片,時(shí)鐘級(jí)3分配1個(gè)時(shí)間片,時(shí)鐘級(jí)4分配2個(gè)時(shí)間片,而將每個(gè)時(shí)隙剩余的時(shí)間分配給基本級(jí)任務(wù)。這樣,即使是在系統(tǒng)最繁忙的時(shí)候也有一個(gè)時(shí)間片分配給基本級(jí)任務(wù),從而彌補(bǔ)了比特表算法的不足。
綜上所述,設(shè)計(jì)圖1所示的比特表。
此比特表的時(shí)隙任務(wù)安排完全滿足實(shí)時(shí)性要求。A任務(wù)每時(shí)隙運(yùn)行1次,每時(shí)隙運(yùn)行2個(gè)時(shí)間片。A任務(wù)每5ms運(yùn)行1次。B任務(wù)每10ms運(yùn)行1次,C任務(wù)每20ms運(yùn)行1次。由此可以得到各任務(wù)的啟動(dòng)順序及執(zhí)行時(shí)間如圖2所示。圖2中,I表示時(shí)鐘中斷處理程序,它的優(yōu)先級(jí)最高。A、B、C、D為時(shí)鐘級(jí)任務(wù),其中A的優(yōu)先級(jí)較高。將I、A、B、C、D處理完后余下的時(shí)間留給基本級(jí)E。
2 程序設(shè)計(jì)值得注意的問題
在任務(wù)調(diào)度算法中,關(guān)鍵是如何確定就緒隊(duì)列、任務(wù)控制數(shù)據(jù)塊的數(shù)據(jù)結(jié)構(gòu)和解決資源沖突。就緒隊(duì)列指明了在某一時(shí)刻已就緒、可被執(zhí)行的任務(wù)隊(duì)列。在數(shù)據(jù)結(jié)構(gòu)上通??捎梦挥诚竦姆椒▉韺?shí)現(xiàn)。如系統(tǒng)的最多任務(wù)為32個(gè),可采用4個(gè)字節(jié)的每一位來對(duì)應(yīng)人某個(gè)任務(wù)。若此位為“1”,則表明該任務(wù)就緒;若為“0”,則表明任務(wù)空閑。并且可規(guī)定低位所代表的任務(wù)優(yōu)先級(jí)高于高位所指示的任務(wù)。
某個(gè)任務(wù)投入運(yùn)行時(shí)需保護(hù)現(xiàn)場數(shù)據(jù),這些數(shù)據(jù)都存入一個(gè)地址固定的數(shù)據(jù)存儲(chǔ)區(qū),稱為任務(wù)控制數(shù)據(jù)塊。需保護(hù)的內(nèi)容應(yīng)按應(yīng)用程序的特點(diǎn)來決定。對(duì)于常用的MCS51系列的單片機(jī)來說,現(xiàn)場保護(hù)數(shù)據(jù)一般應(yīng)包括PC、ACC、PSW、SP、DPTR等寄存器內(nèi)容。任務(wù)控制數(shù)據(jù)塊一般放在外部數(shù)據(jù)存儲(chǔ)器內(nèi)。為了查找方便,可以按任務(wù)號(hào)將各個(gè)任務(wù)數(shù)據(jù)塊的首地址編成一個(gè)一維表格,表格的每行對(duì)應(yīng)各任務(wù)數(shù)據(jù)塊數(shù)據(jù)結(jié)構(gòu)首地址,如圖3所示。
在任務(wù)調(diào)度程序中,還應(yīng)很好地解決資源的互斥問題,即保證不可共享的資源只被一個(gè)任務(wù)所訪問。在RTCS中,各任務(wù)間并非完全隔絕,它們相互合作、相互競爭。例如,某系統(tǒng)中數(shù)據(jù)顯示任務(wù)要定時(shí)顯示某數(shù)據(jù)區(qū)的數(shù)據(jù);數(shù)據(jù)計(jì)算任務(wù)也要在某種情況下計(jì)算、刷新此數(shù)據(jù)區(qū)內(nèi)容。在這里,數(shù)據(jù)計(jì)算任務(wù)在運(yùn)行時(shí)就不允許讓顯示任務(wù)中斷計(jì)算任務(wù);否則,有可能導(dǎo)致顯示的數(shù)據(jù)不正確。解決資源競爭的方法往往是在主程序中設(shè)置一標(biāo)志字節(jié)或標(biāo)志位。例如,顯示任務(wù)在運(yùn)行時(shí)首先判斷此標(biāo)志,若發(fā)現(xiàn)計(jì)算任務(wù)尚未完成,則不做任何工作直接退出任務(wù)。
3 小結(jié)
RTCS中的實(shí)時(shí)性和并行性是非常重要的,但兩者之間有一定的矛盾。完全實(shí)現(xiàn)在兩大特性的重要手段就是,采用有效的任務(wù)調(diào)度算法程序來協(xié)調(diào)兩者之間的矛盾,從而保證系統(tǒng)的實(shí)時(shí)性和并行性。在簡單系統(tǒng)中,“按時(shí)間片循環(huán)”調(diào)度算法已能初步滿足要求;但在較復(fù)雜和要求較高的系統(tǒng)中,這顯然不滿足需要?;贐itMap的調(diào)度算法能較好地滿足比較復(fù)雜系統(tǒng)的要求,而對(duì)于前面講到的系統(tǒng)中要求執(zhí)行時(shí)間長、實(shí)時(shí)性要求較高的任務(wù)而言,單純的BitMap算法無法滿足要求,這個(gè)時(shí)候我們提出將比特表的時(shí)隙細(xì)分成時(shí)間片進(jìn)行分配,這比BitMap按照任務(wù)進(jìn)行分配的算法更能解決復(fù)雜任務(wù)的實(shí)時(shí)性要求。只要有效地確定任務(wù)數(shù)目和數(shù)據(jù)結(jié)構(gòu),RTCS中的實(shí)時(shí)性和并行性就能得到有效提高。