一種綜合嵌入式實時周期任務調度方法
2023-05-06 12:40:26
專利名稱：一種綜合嵌入式實時周期任務調度方法
技術領域：
本發明主要涉及計算機嵌入式實時系統領域，特別是一種適合嵌入式實時周期任 務調度方法。
背景技術：
嵌入式實時系統是目前計算機領域最重要的應用和研究方向，如何合理地進行任 務調度是整個嵌入式應用系統的關鍵。好的任務調度方法既可以保證關鍵任務得到及時運 行，又不至於讓其他任務盲等。嵌入式實時系統中運行的任務，一般都對應一個必須完成的時間期限，該時間期 限稱為為截止期限。從對錯過截止期限造成後果的嚴重程度來看，嵌入式實時任務又可分 為硬實時任務與軟實時任務。硬實時任務錯過截止期限可能會造成系統嚴重或致命的後 果，如有關航空航天、軍事、核工業等應用領域的嵌入式實時系統中的一些關鍵任務；而軟 實時任務錯過截止期限則可能僅會在一定程度上造成系統性能的下降或任務結果意義的 遞減，如消費電子類嵌入實時系統中運行的任務。由於很多嵌入式實時系統處於無人值守的環境，運行系統主要由周期任務組成， 即任務每隔一段時間重新啟動或就緒。一個具有截止期限的周期任務、可簡單描述如 下τ i = (Si, Ri, Ci, Di, Ti)，0 < Ci 彡 Di,0 < Ti,0 ^ Si其中，Si為任務的到達時間氓為任務有資格參與競爭計算機處理器的初始就緒 時間，一般而言，Si = Ri而為任務的執行時間，通常以最壞情形下的估計執行時間代替諷 為任務的相對截止期限Ji為任務的周期。對於周期任務τ i的第k次執行(k彡1)，其重新就緒的時間為氏+(1^-1)*1\，截止 期限為!^+(k-lhTi+Di。周期任務的一次執行稱為該周期任務的一個實例或一次執行請求。一個周期任務的處理器利用率定義為Ui = CiZti,—個周期任務集中所有任務的 處理器利用率之和為該周期任務集的處理器利用率。為了儘可能地保證重要任務不錯過截止期限，嵌入式實時系統的任務調度一般採 用優先級驅動的方式。每一個有資格參與調度的任務都對應一個惟一的調度優先級別，調 度發生時，總是選取調度優先級別最高的任務投入運行。因此，如何合理確定嵌入式實時系 統中各任務的優先級成為影響整個嵌入式實時系統性能的關鍵。對於硬實時周期任務集，一般採用單調速率調度方法。該方法為每一個硬實時周 期任務指定一固定優先級，該優先級與任務周期的長短緊密相關，周期越短，優先級越高， 調度總是最先運行周期最短的任務。如果嵌入式實時系統中任務滿足以下理想條件1)所有具有硬實時的任務均為周期任務，且周期等於其截止期限；2)所有硬實時任務必須在其時限到來前結束；3)任務之間都是獨立的，每個任務的請求不依賴於其它任務請求的開始或完成；4)所有具有硬時限的任務均具有恆定的運行時間，即假定任務運行在無中斷的情形下；5)調度和任務切換的時間忽略不計。則該調度方法具有如下一些性質1)單調速率調度方法是最優的。即在同樣條件下，對某一周期任務集只要別的固 定優先級調度方法能使所有任務不錯過截止期限，則使用單調速率調度方法肯定也能調度 成功。2)使用該調度方法的周期任務集可調度的處理器利用率的有一最小上界為 0. 693，即只要周期任務集處理器利用率小於該值，則該任務集一定可調度。對於軟實時任務集，最小空閒時間優先為傳統的常用動態優先級調度方法。該調 度方法是結合任務執行的緩急程度給任務分配優先級的一種動態調度方法。一個任務的空 閒時間定義為從當前時刻至其截止期限的時間距離與其剩餘尚未執行時間之間的差值。在 調度時刻，任務的優先級根據任務的空閒時間動態分配。空閒時間越短，任務的優先級越 高。使用該調度方法能充分利用處理機，在理想條件下，只要任務集的處理器利用率小於1， 這些任務均可順利得到調度，不會錯過截止期限。由於在一個實際的嵌入式實時系統中，硬實時任務、軟實時任務與非實時任務往 往是並存的，傳統的使用單一的調度方法無法有效完成所有類型任務的調度，因此需要設 計一種綜合的調度方法。
發明內容
本發明為解決上述技術問題，提出了一種採用多隊列多調度方式的綜合嵌入式實 時周期任務調度方法，該方法一方面優先確保系統中的硬實時任務的截止期限得到滿足; 另一方面儘量保證關鍵的軟實時任務不錯過截止期限；同時，在資源許可的情形下，也不至 於使低優先級的任務長時間等待，從而提高整個處理器的利用率。本發明的技術方案如下一種綜合嵌入式實時周期任務調度方法，其特徵在於將任務就緒隊列分為三個 一級就緒隊列硬實時任務就緒隊列、軟實時任務就緒隊列與非實時任務就緒隊列，對於三 個一級就緒隊列調度的優先規則為首先調度執行硬實時任務就緒隊列中的任務，其次調 度執行軟實時就緒隊列中的任務，最後調度執行非實時就緒任務隊列中的任務；在任務調 度時，當前面的一級就緒隊列中沒有就緒任務時才執行後一級就緒隊列中任務的調度。硬實時任務就緒隊列按照就緒任務的周期長短有序，周期越短在隊列中越靠前， 周期相同的任務則按照估計執行時間有序，估計執行時間越短的任務越靠前；對硬實時任 務就緒隊列中就緒任務的調度選取隊首任務，隊首任務的周期是最短的，即對該任務隊列 的調度實際上採用了單調速率調度方法。單調速率調度方法是一種適用於硬實時周期性任務的靜態優先級調度算法，使用 該方法進行調度時，為每一個周期任務指定一固定優先級，該優先級與任務周期的長短緊 密相關，周期越短，優先級越高，調度總是最先運行周期最短的任務。在理想條件下，該調度 方法有如下兩個特性1)如果一個任務集存在靜態優先級下的可調度方法，則單調速率法是最優的。所 謂最優是指在同樣條件下，對某一任務集只要別的方法能調度成功，則使用單調速率法肯定也能調度成功。2)具有固定優先級的周期任務集可調度的處理器利用率的最小上界為L(n)= η(2ιΛΜ)。即只要該任務集的處理器利用率小於等於該上界值，則該任務集使用單調速率法 是可調度的。最小上界L(n)與任務的周期和最壞執行時間無關。L(n)隨η單調遞減。當 η —⑴時，L(n) = 1η2 ^ 0. 693。軟實時任務就緒隊列按照就緒任務的關鍵程度分為三個二級就緒子隊列關鍵軟 實任務就緒子隊列、一般軟實時任務就緒子隊列和非關鍵軟實時任務就緒子隊列；各個軟 實時任務的關鍵程度在任務產生時指定，採取確定或模糊的方式進行賦值或分類。每個二 級就緒子隊列按空閒時間有序，任務空閒時間定義為SLi = Si+(k-l)*Ti+Di-(t+Ci-ei)其中t為系統當前時間，Si為任務τ 達到或初次就緒時間(如果所有任務在 系統初始時均同時就緒，該值為0)且當前為周期任務h的第k次執行，Ci為任務Ti的 估算執行時間，e,為任務τ i實際已執行時間，Di為任務τ ,的相對截止期時間，Ti為任務 ^的周期。對於軟實時任務就緒隊列的任務調度為Α、首先調度關鍵軟實時任務二級就緒子隊列中的任務空閒時間為0的任務，若沒 有空閒時間為0的任務，則轉到步驟B ；B、當一般軟實時任務二級就緒子隊列中有空閒時間為0的任務，則選該任務進行 調度，否則轉到步驟C;C、當非關鍵軟實時任務二級就緒子隊列中有空閒時間為0的任務，則選該任務進 行調度，否則轉到步驟D ；D、選取關鍵程度最高的就緒任務進行調度執行，即以關鍵軟實時任務二級就緒子 隊列、一般軟實時任務二級就緒子隊列、非關鍵軟實時任務二級就緒子隊列的優先順序選 取對應的非空二級就緒子隊列的隊首任務投入運行。該調度方法實際上是空閒時間優先與任務關鍵程度相結合的一種調度方式。當任 務的空閒時間為0時，當然必須進行調度，否則會錯過截止期限。當有多個不同關鍵程度的 任務都可能錯過截止期限時，首先保障最關鍵的任務儘可能不錯過截止期限。當沒有就緒 任務的空閒時間為0時，優先調度關鍵程度最高的任務。因此，該調度方式既考慮了任務的 空閒時間，也考慮到了任務的關鍵程度。所有非實時任務均進入非實時任務就緒隊列中，調度時採用時間片輪轉調度方 式。所述時間片輪轉調度方法的實現思想為給就緒隊列中的每個任務分配一個相同的 (當然也可不同的)處理器執行時間(該時長稱為時間片)，調度時取就緒隊列隊頭任務 投入運行，當前運行的任務用完自己的時間片但整個任務尚未結束，則把該任務重新放入 就緒隊列的尾部等待下一個時間片的到來，系統繼續選擇就緒隊列隊頭任務佔有處理器運 行。本發明的有益效果如下本發明主要通過把嵌入式實時系統中的任務分為硬實時周期任務，軟實時周期任 務和非實時任務三類，根據任務實時性的不同分別採用多級就緒隊列與不同的調度方法，與傳統的單一任務調度方法相比有著很好的靈活性，適用於絕大多數嵌入式實時系統領 域；當系統負載較高時，該方法能確保硬實時任務不錯過截止期限的同時降低關鍵軟實時 任務的截止時間錯失率，也大大提高了處理器利用率。
圖1為本發明的就緒隊列及調度流程示意圖
具體實施例方式如圖1所示，一種綜合嵌入式實時周期任務調度方法，根據就緒任務的實時屬性 將任務就緒隊列分為三個一級就緒隊列硬實時任務就緒隊列、軟實時任務就緒隊列與非 實時任務就緒隊列，對於三個一級就緒隊列調度的優先規則為首先調度執行硬實時任務 就緒隊列中的任務，其次調度執行軟實時就緒隊列中的任務，最後調度執行非實時就緒任 務隊列中的任務；在任務調度時，當前面的一級就緒隊列中沒有就緒任務時才執行後一級 就緒隊列中任務的調度。硬實時任務就緒隊列按照就緒任務的周期長短有序，周期越短在隊列中越靠前， 周期相同的任務則按照估計執行時間有序，估計執行時間越短的任務越靠前；對硬實時任 務就緒隊列中就緒任務的調度選取隊首任務，隊首任務的周期是最短的，即對該任務隊列 的調度實際上採用了單調速率調度方法。軟實時任務就緒隊列按照就緒任務的關鍵程度分為三個二級就緒子隊列關鍵軟 實任務就緒子隊列、一般軟實時任務就緒子隊列和非關鍵軟實時任務就緒子隊列；各個軟 實時任務的關鍵程度在任務產生時指定，採取確定或模糊的方式進行賦值或分類。每個二 級就緒子隊列按空閒時間有序，任務空閒時間定義為SLi = Si+(k-l)*Ti+Di-(t+Ci-ei)其中t為系統當前時間，Si為任務τ i的達到或初次就緒時間(如果所有任務在 系統初始時均同時就緒，該值為0)且當前為周期任務h的第k次執行，Ci為任務Ti的 估算執行時間，e,為任務τ i實際已執行時間，Di為任務τ ,的相對截止期時間，Ti為任務 ^的周期。對於軟實時任務就緒隊列的任務調度為Α、首先調度關鍵軟實時任務二級就緒子隊列中的任務空閒時間為0的任務，若沒 有空閒時間為0的任務，則轉到步驟B ；B、當一般軟實時任務二級就緒子隊列中有空閒時間為0的任務，則選該任務進行 調度，否則轉到步驟C;C、當非關鍵軟實時任務二級就緒子隊列中有空閒時間為0的任務，則選該任務進 行調度，否則轉到步驟D ；D、選取關鍵程度最高的就緒任務進行調度執行，即以關鍵軟實時任務二級就緒子 隊列、一般軟實時任務二級就緒子隊列、非關鍵軟實時任務二級就緒子隊列的優先順序選 取對應的非空二級就緒子隊列的隊首任務投入運行。該調度方法實際上是空閒時間優先與任務關鍵程度相結合的一種調度方式。當任 務的空閒時間為0時，當然必須進行調度，否則會錯過截止期限。當有多個不同關鍵程度的任務都可能錯過截止期限時，首先保障最關鍵的任務儘可能不錯過截止期限。當沒有就緒 任務的空閒時間為0時，優先調度關鍵程度最高的任務。因此，該調度方式既考慮了任務的 空閒時間，也考慮到了任務的關鍵程度。所有非實時任務均進入非實時任務就緒隊列中，調度時採用時間片輪轉調度方 式；調度時給每個任務分配一個相同的時間片，如果該時間片內未執行完，任務進入就緒隊 列尾部，等待下一個時間片的到來。本方法具體實施的過程如下為了適應嵌入式實時周期任務的調度，標識任務的數據結構一任務控制塊(Task Control Block, TCB)中需添加如下一些信息域任務當前狀態主要有就緒、阻塞、執行三種狀態；任務的類別主要分為硬實時、軟實時與非實時三類；任務的重要程度該屬性對軟實時有用，分為關鍵，一般和非關鍵三類；任務的周期任務實例重新就緒的時間間隔；任務的執行時間估計的任務最壞情形下的執行時間，以時鐘滴答為單位；任務已執行時間對於實時任務，指在系統某一時刻，該任務在某周期內已經使用 處理器的時間；對於非實時任務，指時間片內的已執行時間統計，當時間片用完時，重新歸 0 ；任務的空閒時間用於統計在系統某一時刻任務的空閒時間；任務的相對截止期限任務實例在某次請求中必須完成的時間點；任務所處隊列信息包括任務在當前隊列中的前一個任務與後一任務控制塊連接 fn息；任務的時間片信息分配給任務的執行時間片，主要用於非實時任務。一、系統初始化1、創建硬實時、軟實時和非實時三個任務就緒一級隊列，軟實時任務就緒隊列包 括用於存放關鍵、一般和非關鍵三類任務的二級就緒子隊列。2、對要創建的硬實時任務，根據任務的處理器利用率判斷可調度性，確保所創建 的硬實時任務能夠使用單調速率法成功得到調度，不會錯過截止期限。二、任務創建初始化任務創建時需指定任務的周期、估計執行時間、相對截止期限、任務的類別。如果 為軟實時任務，還需指定其關鍵程度。系統根據任務的創建時指定的信息初始化任務控制 塊相應的值域。任務創建時的任務控制塊中的當前狀態初始化為就緒，任務的已執行時間初始化 為0，任務的空閒時間初始化為起始就緒時間+相對截止期限_估計執行時間根據任務的類別進入不同的一級就緒隊列，如果為軟實時任務，則還需根據不同 的關鍵程度進入不同的二級就緒子隊列並按空閒時間有序。當創建的任務為非實時任務時，根據系統設定的時間片參數初始化任務控制塊中 的時間片信息值域，任務按創建的先後順序進入非實時任務就緒一級子隊列。三、任務調度方法
7
當任務調度時機到來時，採用的調度方法可描述如下步驟1 如果硬實時任務一級就緒隊列中有任務存在，選擇該任務佔有處理器；否 則轉步驟2 ；步驟2 如果軟實時任務一級就緒隊列不為空轉步驟3 ；否則轉步驟7 ；步驟3 如果關鍵軟實時任務二級就緒子隊列中有空閒時間為0的任務，則選該任 務進行調度；否則，轉步驟4;步驟4 如果一般軟實時任務二級就緒子隊列中有空閒時間為0的任務，則選該任 務進行調度；否則，轉步驟5;步驟5 如果非關鍵軟實時任務二級就緒子隊列中有空閒時間為0的任務，則選該 任務進行調度；否則，轉步驟6;步驟6 選取關鍵程度最高的就緒任務進行調度執行。即以關鍵軟實時任務二級 就緒子隊列、一般軟實時任務二級就緒子隊列、非關鍵軟實時任務二級就緒子隊列的優先 順序選取相應的非空二級子隊列的隊首任務投入調度運行；步驟7 如果非實時任務列就緒一級隊列中有任務存在，選擇隊首任務佔有處理
ο四、實時時鐘處理方法在嵌入式實時系統中，實時時鐘是整個系統的脈動，一切計時均是以實時時鐘為 基準的，每一次實時時鐘中斷稱為一個時鐘滴答。實時時鐘發生時要做的工作主要如下1、如果當前運行任務為軟實時任務，該任務的已執行時間加1 ；如果任務運行完 成而新的周期未到來則阻塞自己；2、重新計算所有的軟實時任務就緒子隊列中任務的空閒時間並，如果有空閒時間 域值為0的任務出現，重新引起調度；如果有空閒時間小於0的，則阻塞該任務，等待下一周 期重新就緒；調整該就緒隊列使之按空閒時間有序。3、如果當前運行的任務為非實時任務，該任務的已執行時間加1，如果達到該任務 的時間片值，該任務放入對應就緒隊列尾部，重新引起調度；4、如果有任務新的周期到來，喚醒該任務使之就緒，重新調度。
權利要求
一種綜合嵌入式實時周期任務調度方法，其特徵在於將任務就緒隊列分為三個一級就緒隊列硬實時任務就緒隊列、軟實時任務就緒隊列與非實時任務就緒隊列，對於三個一級就緒隊列調度的優先規則為首先調度執行硬實時任務就緒隊列中的任務，其次調度執行軟實時就緒隊列中的任務，最後調度執行非實時就緒任務隊列中的任務；在任務調度時，當前面的一級就緒隊列中沒有就緒任務時才執行後一級就緒隊列中任務的調度。
2.根據權利要求1所述的一種綜合嵌入式實時周期任務調度方法，其特徵在於硬實 時任務就緒隊列按照就緒任務的周期長短有序，周期越短在隊列中越靠前，周期相同的任 務則按照估計執行時間有序，估計執行時間越短的任務越靠前；對硬實時任務就緒隊列中 就緒任務的調度選取隊首任務，隊首任務的周期是最短的，即對該任務隊列的調度實際上 採用了單調速率調度方法。
3.根據權利要求1或2所述的一種綜合嵌入式實時周期任務調度方法，其特徵在於 軟實時任務就緒隊列按照就緒任務的關鍵程度分為三個二級就緒子隊列關鍵軟實任務就 緒子隊列、一般軟實時任務就緒子隊列和非關鍵軟實時任務就緒子隊列；各個軟實時任務 的關鍵程度在任務產生時指定，採取確定或模糊的方式進行賦值或分類。每個二級就緒子 隊列按空閒時間有序，任務空閒時間定義為SLi = Si+(k-l)*Ti+Di-(t+Ci-ei)其中t為系統當前時間，Si為任務τ i的達到或初次就緒時間(如果所有任務在系統 初始時均同時就緒，該值為0)且當前為周期任務h的第k次執行,Ci為任務^的估算執 行時間，ei為任務τ i實際已執行時間，Di為任務τ i的相對截止期時間，Ti為任務τ ,的周期。
4.根據權利要求3所述的一種綜合嵌入式實時周期任務調度方法，其特徵在於對於 軟實時任務就緒隊列的任務調度為Α、首先調度關鍵軟實時任務二級就緒子隊列中的任務空閒時間為0的任務，若沒有空 閒時間為0的任務，則轉到步驟B ；B、當一般軟實時任務二級就緒子隊列中有空閒時間為0的任務，則選該任務進行調 度，否則轉到步驟C;C、當非關鍵軟實時任務二級就緒子隊列中有空閒時間為0的任務，則選該任務進行調 度，否則轉到步驟D ；D、選取關鍵程度最高的就緒任務進行調度執行，即以關鍵軟實時任務二級就緒子隊 列、一般軟實時任務二級就緒子隊列、非關鍵軟實時任務二級就緒子隊列的優先順序選取 對應的非空二級就緒子隊列的隊首任務投入運行。
5.根據權利要求1或2或4所述的一種綜合嵌入式實時周期任務調度方法，其特徵 在於將所有非實時任務均進入非實時任務就緒隊列中，調度時採用時間片輪轉調度方式； 調度時給每個任務分配一個相同的時間片，如果該時間片內未執行完，任務進入就緒隊列 尾部，等待下一個時間片的到來。
全文摘要
本發明公開了一種綜合嵌入式實時周期任務調度方法，將任務就緒隊列分為硬實時任務就緒隊列、軟實時任務就緒隊列與非實時任務就緒隊列，對於三個隊列調度的規則為首先調度執行硬實時任務就緒隊列中的任務，其次調度執行軟實時就緒隊列中的任務，最後調度執行非實時就緒任務隊列中的任務；在任務調度時，當前面的一級就緒隊列中沒有就緒任務時才執行後一級就緒隊列中任務的調度；本發明通過對任務進行分類，根據任務實時性不同分別採用多級就緒隊列與不同的調度方法，有很好的靈活性，適用於絕大多數嵌入式實時系統；當系統負載較高時，能確保硬實時任務不錯過截止期限的同時降低關鍵軟實時任務的截止時間錯失率，也大大提高了處理器利用率。
文檔編號G06F9/46GK101923487SQ201010247159
公開日2010年12月22日 申請日期2010年8月6日 優先權日2010年8月6日
發明者何先波, 李明東, 楊莉 申請人:西華師範大學