- 相關推薦
一種基于比特表的實時多任務新調度算法
摘要：主要討論常見的幾種多任務實時性處理算法的優缺點，提出一種更能滿足多任務實時性處理的算法——基于比特表的時間片算法。這種算法主要是把常規的比特表中的任務按照時間片進行分配，以很好地完成實時性要求高且任務時間較長的任務，而不影響其它實時性要求更高的任務的完成。關鍵詞：比特表 時間片 實時處理
引言
在微機控制領域中，許多單片機應用系統是實時控制系統RTCS（Real Time Control System）。在實時控制系統中，為了很好地完成外界信息的實時測量、計算和相應的多種實時控制操作，必須達到兩個設計目標；實時性和并行性。即既要保證系統對外界信息以足夠快的速度進行相應處理，又要同時完成多種任務操作。在這里，多種任務之間的調度是個關鍵。
RTCS中允許多個實時任務并行地運行。例如，一測控系統中，具有數據采集、數據計算、鍵盤處理、定時打印等任務。在單機系統中，這些任務在宏觀上是同時運行的，但在微觀上只有一個任務運行。在RTCS中每個任務有三種狀態，即運行狀態、就緒狀態和空閑狀態。某個任務一旦建立后即處于這三種狀態之一。處于運行狀態的任務獨占CPU和其它一些資源；就緒狀態是某個任務現在應該運行，但由于其它任務正在運行，故只能暫時等待；當激發某個任務的條件不完備時，此任務就處于空閑狀態。
RTCS中的多個任務依靠任務調度程序來決定系統中哪個任務可以獲得CPU等資源或應暫時退出運行狀態等，從而完成每個任務三態間的轉換。在RTCS中，任務調度算法的優劣直接關系到系統的實時性能與并行性能。
(范文先生網m.baimashangsha.com收集整理)
RTCS中較簡單的任務調度算法有“先來先執行的調度算法”、“按時間片循環執行的調度算法”。前者，當實時性比較差的任務長時間占用CPU時，會使得實時性較高的任務得不到及時處理，影響系統的實時性；后者，按照“先入先出”的原則激活某個任務，并分配給它們相等的時間片，從而使得多個任務有平等的享用CPU的權利。當時間片用完時，讓任務“暫時”又處于就緒狀態，并激活下一個任務。這種算法的實時性有一定程序的提高，但由于各任務簡單均勻地循環輪回，從而使得實時性要求較高的任務得不到優先處理。由于各時間片相等且固定，很容易被某些緊急任務打斷。在實時性要求較高而且任務較多的復雜情況下，各個任務的實時性要求不盡相同，不能簡單地均勻分時處理任務。
基于比特表的任務調度算法，關鍵在于將CPU的全部時間化成若干個相等的時隙，同時根據任務的數目制定一張表格，以此來指示某一時刻的任務運行。它把任務按照實時性要求分成中斷級、時鐘級、基本級三類，而且它們的優先級依次遞減。優先級越高，就越處于比特表的頂端位置。比特表是按照任務的優先級排隊的，首先滿足實時性較強的中斷級和時鐘級，而不管實時性最低的基本級任務。這樣，時鐘級任務一定能得到即時有效的處理，其實時性可以得到較好的保障，基本級任務可以沒有時間限制。但是，時鐘級任務的實時性并不是完全能夠得到保障。下面舉例討論比特表算法的不足之處。
圖2 任務的啟動順序和運行時間
假定有表1所示的五種任務，按照常規比特表算法根本無法設計出這樣的比特表。當時鐘級的各級每次運行時間之和沒有達到5ms時，比特表算法能夠很好地滿足系統實時性要求；然而，當中斷級和時鐘級的每次運行時間之和大于或者等于最高級實時性要求，更有甚者，當有一個時鐘級任務的運行時間超過最高級實時性要求時，比特表算法就會失效。因為常規的比特表算法要求，只要激活比特表中安排的中斷級和時鐘級任務就必須一次執行完，否則，如果這個任務被中斷就無法再得到執行。由于圖像處理的運行時間為5ms，加上中斷級任務執行時間，因此設計時隙必須大于5ms；而比特表的設計方法時隙只可能小于等于5ms（中斷級任務和實時性最高的時鐘級任務決定的）。所以，無論安排怎樣的比徨表都無法使任務D滿足實時性要求。基于這兩種情況，本文提出一種用賦有優先權的時間來填充比特表的算法，以改善這兩種情況。
表1 實時性要求和各任務運行時間表
1 比特表的改進算法
這種改進算法的關系在于把各任務劃分為若干時間片，然后再根據實時性要求填入比特表中。根據比特表的設計方法，時隙間隔定為5ms，總時隙數為LCM（10/5，20/5，30/5）=6。把各中斷級和時鐘級任務運行時間的最大公約數定為時間片。即有如下計算公式：
T=GCD{Ti}
T為時間片，Ti為時鐘級和中斷級任務實時性要求，GCD（Greatest Common Divisor）求最大公約數，LCM（Lowest Common Multiple）求最小公倍數。
本例中的時間片T=GCD{0.5,1,2.5,1,5}=0.5ms。（假設時鐘中斷處理時間為0.5ms）。
時間片的分配，必須遵循以下原則：
①滿足實時性要求；
②確保每一個時隙中所有分配的任務都必須完全運行；
③均衡考慮CPU對各任務的運行，優先考慮時鐘級任務和中斷級任務。
按上述原則，中斷級任務分1個時間片，時鐘級1分配2個時間片，時鐘級2分配3個時間片，時鐘級3分配1個時間片，時鐘級4分配2個時間片，而將每個時隙剩余的時間分配給基本級任務。這樣，即使是在系統最繁忙的時候也有一個時間片分配給基本級任務，從而彌補了比特表算法的不足。
綜上所述，設計圖1所示的比特表。
此比特表的時隙任務安排完全滿足實時性要求。A任務每時隙運行1次，每時隙運行2個時間片。A任務每5ms運行1次。B任務每10ms運行1次，C任務每20ms運行1次。由此可以得到各任務的啟動順序及執行時間如圖2所示。圖2中，I表示時鐘中斷處理程序，它的優先級最高。A、B、C、D為時鐘級任務，其中A的優先級較高。將I、A、B、C、D處理完后余下的時間留給基本級E。
2 程序設計值得注意的問題
在任務調度算法中，關鍵是如何確定就緒隊列、任務控制數據塊的數據結構和解決資源沖突。就緒隊列指明了在某一時刻已就緒、可被執行的任務隊列。在數據結構上通常可用位映像的方法來實現。如系統的最多任務為32個，可采用4個字節的每一位來對應人某個任務。若此位為“1”，則表明該任務就緒；若為“0”，則表明任務空閑。并且可規定低位所代表的任務優先級高于高位所指示的任務。
某個任務投入運行時需保護現場數據，這些數據都存入一個地址固定的數據存儲區，稱為任務控制數據塊。需保護的內容應按應用程序的特點來決定。對于常用的MCS51系列的單片機來說，現場保護數據一般應包括PC、ACC、PSW、SP、DPTR等寄存器內容。任務控制數據塊一般放在外部數據存儲器內。為了查找方便，可以按任務號將各個任務數據塊的首地址編成一個一維表格，表格的每行對應各任務數據塊數據結構首地址，如圖3所示。
在任務調度程序中，還應很好地解決資源的互斥問題，即保證不可共享的資源只被一個任務所訪問。在RTCS中，各任務間并非完全隔絕，它們相互合作、相互競爭。例如，某系統中數據顯示任務要定時顯示某數據區的數據；數據計算任務也要在某種情況下計算、刷新此數據區內容。在這里，數據計算任務在運行時就不允許讓顯示任務中斷計算任務；否則，有可能導致顯示的數據不正確。解決資源競爭的方法往往是在主程序中設置一標志字節或標志位。例如，顯示任務在運行時首先判斷此標志，若發現計算任務尚未完成，則不做任何工作直接退出任務。
3 小結
RTCS中的實時性和并行性是非常重要的，但兩者之間有一定的矛盾。完全實現在兩大特性的重要手段就是，采用有效的任務調度算法程序來協調兩者之間的矛盾，從而保證系統的實時性和并行性。在簡單系統中，“按時間片循環”調度算法已能初步滿足要求；但在較復雜和要求較高的系統中，這顯然不滿足需要。基于BitMap的調度算法能較好地滿足比較復雜系統的要求，而對于前面講到的系統中要求執行時間長、實時性要求較高的任務而言，單純的BitMap算法無法滿足要求，這個時候我們提出將比特表的時隙細分成時間片進行分配，這比BitMap按照任務進行分配的算法更能解決復雜任務的實時性要求。只要有效地確定任務數目和數據結構，RTCS中的實時性和并行性就能得到有效提高。
【一種基于比特表的實時多任務新調度算法】相關文章：
一種DWT域基于IFS的數字水印算法08-06
一種新的實用安全加密標準算法——Camellia算法08-06
微型搶占式多任務實時內核設計08-06
一種基于“陷門收縮”原理的公鑰算法08-06
基于RTLinux的實時控制系統08-06
利用實時內核開發嵌入式多任務程序08-06
一種基于減少內存訪問的Pruning Fast DCT算法改進05-07
適應實時多任務的微控制器高效指令支持08-06