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

摘要：主要討論常見(jiàn)的幾種多任務(wù)實(shí)時(shí)性處理算法的優(yōu)缺點(diǎn)，提出一種更能滿足多任務(wù)實(shí)時(shí)性處理的算法——基于比特表的時(shí)間片算法。這種算法主要是把常規(guī)的比特表中的任務(wù)按照時(shí)間片進(jìn)行分配，以很好地完成實(shí)時(shí)性要求高且任務(wù)時(shí)間較長(zhǎng)的任務(wù)，而不影響其它實(shí)時(shí)性要求更高的任務(wù)的完成。

    關(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í)測(cè)量、計(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)行。例如，一測(cè)控系統(tǒng)中，具有數(shù)據(jù)采集、數(shù)據(jù)計(jì)算、鍵盤(pán)處理、定時(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)度程序來(lái)決定系統(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中較簡(jiǎn)單的任務(wù)調(diào)度算法有“先來(lái)先執(zhí)行的調(diào)度算法”、“按時(shí)間片循環(huán)執(zhí)行的調(diào)度算法”。前者，當(dāng)實(shí)時(shí)性比較差的任務(wù)長(zhǎng)時(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ù)簡(jiǎn)單均勻地循環(huán)輪回，從而使得實(shí)時(shí)性要求較高的任務(wù)得不到優(yōu)先處理。由于各時(shí)間片相等且固定，很容易被某些緊急任務(wù)打斷。在實(shí)時(shí)性要求較高而且任務(wù)較多的復(fù)雜情況下，各個(gè)任務(wù)的實(shí)時(shí)性要求不盡相同，不能簡(jiǎn)單地均勻分時(shí)處理任務(wù)。

基于比特表的任務(wù)調(diào)度算法，關(guān)鍵在于將CPU的全部時(shí)間化成若干個(gè)相等的時(shí)隙，同時(shí)根據(jù)任務(wù)的數(shù)目制定一張表格，以此來(lái)指示某一時(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ù)可以沒(méi)有時(shí)間限制。但是，時(shí)鐘級(jí)任務(wù)的實(shí)時(shí)性并不是完全能夠得到保障。下面舉例討論比特表算法的不

[1] [2] [3] [4] 

【一種基于比特表的實(shí)時(shí)多任務(wù)新調(diào)度算法】相關(guān)文章：

實(shí)時(shí)調(diào)度算法04-30

基于UKF的測(cè)速定軌實(shí)時(shí)算法04-30

基于A*算法的實(shí)時(shí)航跡規(guī)劃方法研究05-01

基于LabWindows的實(shí)時(shí)多任務(wù)加載總控臺(tái)軟件設(shè)計(jì)04-28

基于Memetic算法的飛機(jī)著陸調(diào)度優(yōu)化04-27

基于定點(diǎn)/插值算法的衛(wèi)星PVT實(shí)時(shí)計(jì)算的優(yōu)化設(shè)計(jì)04-27

基于遺傳算法的多配送中心運(yùn)輸調(diào)度研究04-30

基于改進(jìn)遺傳算法的公交車輛調(diào)度優(yōu)化04-29

基于遺傳算法的TT&C測(cè)控資源優(yōu)化調(diào)度05-02

席位分配問(wèn)題的一種新算法04-28