混合任務集的層次調度方案

摘要：實時系統的關鍵技術在于系統如何調度應用程序。由于多類型的實時任務并存于一個系統，單一的調度算法無法滿足這一需要，于是提出了層次調度方案。該文介紹了這一方案的設計思想，并給出了該方案的具體實現。

關鍵詞：層次調度；EDF；DBS

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)35-2167-02

The Level Scheduling Program of the Mixed Task

LI Ting1， WANG Hai-rui2， ZHANG Ji-yan1

(1.Faculty of Information Engineering and Automation， Kunming University of Science and Technology， Kunming 650051， China; 2. Faculty of Information Engineering and Automation， Kunming University of Science and Technology， Kunming 650051， China)

Abstract: Real-time systems technology is the key to how the scheduling system applications. Due to multi-task real-time co-exist in a system， single scheduling algorithm can not meet this need， then raised the level scheduling program. This article describes the design ideas， and gives concrete realization of the program.

Key words: level scheduling; EDF; DBS

1 引言

實時調度是實時系統研究中的一個關鍵問題。自從20世紀70年代中期以來，實時調度算法幾乎是呈指數增長[1]。實時調度算法的好壞，直接影響到系統的吞吐量、系統的響應時間，甚至是任務能否得以成功調度。對實時調度算法的研究，是實時領域的一個重要的研究課題[2]。 隨著實時系統應用范圍的不斷擴大，實時應用變得日趨復雜，任務量和數據量的增加以及計算復雜度的加大，調度算法會向面向分布、動態、弱實時、混合調度以及實時多處理機系統調度的方向發展。這就提出了實時系統中混合任務集的層次調度方案。

本文描述一個周期性、偶發性（釋放時間是隨機的，但是強時限的）和非周期性任務（釋放時間是隨機的，是弱時限或沒有時限）混合調度的層次調度方案，它能夠為在單處理器上執行的各個應用提供定時隔離。每個應用包含任意數目和類型的任務。 通過這樣的設計，此方案允許不同的應用使用不同的調度算法。因此，每個應用可以用最適合的方式調度。

2 層次調度方案的設計思想

根據層次調度方案，每類應用都由一個服務器執行。底層為調度層，上層為調度策略分配層。在調度層，處于較低級的調度程序被稱為系統調度器。系統調度器維護EDF和DBS（dynamic bandwidth server ，動態帶寬服務器）調度服務器，并基于EDF算法調度所有就緒服務器。在較高級別，每個服務器的調度程序調度由服務器執行的應用程序中的就緒作業。其調度結構圖如圖1所示。

2.1 測試與篩選器

測試與篩選器主要負責任務集的讀取和分析，并決定使用的調度策略。其主要功能：

1) 負責原始任務集的讀取和分析。根據任務的類型區分是周期性任務、偶發性任務，還是非周期性任務，并設置相應的參數；通過調度篩選器來選擇合適的調度器。例如周期性任務選擇EDF調度服務器，非周期性任務選擇DBS調度服務器，偶發性任務則選擇接受測試，通過測試的插入EDF維護的周期性隊列，否則拒絕。

2) 對周期性任務進行可調度性測試。

3) 對偶發性任務進行接受測試。所采取的算法是每釋放一個偶發作業，調度程序便對其進行一個接受測試。若根據現有的調度算法，在其時限之前如果有足夠的時間能夠完成該偶發作業，并且不會導致其它作業錯過時限，調度程序就接受并調度該作業，否則拒絕。調度程序在拒絕了釋放后無法及時調度的偶發作業之后，會給應用系統足夠的時間采取必要的恢復行動。已接受的偶發作業與周期作業一起，基于EDF算法進行調度。

2.2 EDF調度服務器

EDF調度服務器主要負責周期性任務和偶發性任務的調度。

對于EDF調度服務器，本文采用三元組Sh=< Uh，Eh，Dh >表示，其中Uh表示服務器所占用的CPU帶寬，Eh表示服務器預算，Dh表示服務器的時限。服務器的時限Dh，等于它所維護的任務隊列中的第一個任務的時限。其主要功能如下：

1) 在有任務加入隊列或是任務完成退出隊列時，根據在EDF算法中，任務調度優先級的定義：pr= di(t)-t（pr為優先級，di(t)為任務第i個作業的時限，t為當前時刻）動態更新任務的優先級并對隊列重新排序。

2) 帶寬計算：根據公式（1）估算周期性任務和偶發性任務所需要的帶寬U。 并把它傳給系統調度器。

（1）

2.3 DBS調度服務器

DBS調度服務器主要負責非周期性任務的調度。

對于DBS調度服務器，本文采用三元組Ss=表示， 其中Us 表示調度器占用CPU的帶寬，Es表示調度器預算，Ds表示調度器的時限，其主要功能為：在有作業加入隊列或是作業完成退出隊列時，按照FCFS算法為隊列重新排序。

DBS的消耗和補充規則如下：

消耗規則(Consumption Rule)：

服務器只有在它執行時才消耗其預算，其執行預算按照每單位時間一個的速率消耗。

補充規則(Replenishment Rule)：

R1 初始狀態，Es=0，并且Ds=0。

R2 當一個執行時間為e的非周期性作業在時刻t到達一個空的非周期性作業隊列時，令d等于max(Ds，t)+Es/Us， 并且Es =e。

R3 當服務器完成了當前的非周期性作業時，就把這個作業從它的隊列中刪除。

1) 如果服務器有儲備，就把服務器的時限設置為Ds+Es/Us，并且Es=e。

2) 如果服務器空閑，則不做任何操作。

2.4 系統調度器

系統調度器的主要任務是維護EDF和DBS調度服務器，并基于EDF算法調度所有就緒服務器。其主要功能如下：

1) 維護EDF和DBS調度服務器。根據EDF調度服務器傳過來的帶寬U，把U調整為Uh（U ≤Uh≤1），（為了避免了過度頻繁的帶寬調整，根據U的波動情況，估算一個合理的區間。僅當U的變化超過該區間時，才調整它的帶寬Uh [3]）。然后把Uh利用公式：Uh+ Us + U0= 1（假設其它消耗占用的CPU帶寬為一個固定值U0，由于EDF和DBS調度服務器共享一個CPU，如果令CPU的運行帶寬為1，那么有：Uh + U s + U0= 1），計算時刻t時，DBS調度服務器所占用CPU的帶寬Us，并把Us傳給DBS調度服務器，同時把Uh傳給EDF調度服務器。

2) 根據需要對服務器預算進行補充。因為EDF調度服務器不存在沒有預算的情況，Eh可設為無窮大[3]。對于DBS調度服務器，是根據Us，按照DBS算法進行預算補充。

3) EDF和DBS調度服務器通過各自的算法得到各自的時限，系統調度器就會依據它們的時限，采用EDF算法對它們進行調度，時限短的服務器將被優先執行。

4) EDF調度服務器為主調度服務器，可以根據需要，無條件占用CPU帶寬。當EDF調度服務器需要帶寬時，系統調度器根據相應的調整策略將DBS調度服務器所占用CPU帶寬的部分或全部轉讓給EDF調度服務器。

3 小結

1) 通過把調度過程分為兩個階段，將調度器的篩選和具體的調度分開來，使多種調度策略都得到支持，相對于只對單種調度策略提供支持的方案，拓展了系統的可使用范圍。

2) 混合任務的層次調度方案就是利用測試與篩選器來為預定義的任務集按合理的方式分配調度策略，再利用任務調度器來調度就緒隊列中的任務分配處理機使之執行。

參考文獻：

[1] Krishna C M，Kang G S.實時系統[M].戴海瓊，譯.北京:清華大學出版社，2004.

[2] 王娟，吳秀文，張鐘澍.實時操作系統集成調度的兩級方案設計[J].成都信息工程學院學報，2007，22(1):36-40.

[3] 田沛，王建成.一種用于混合任務系統的可變帶寬調度算法[C]//袁東風.現代電子信息技術理論與應用--中國電子學會第十一屆青年學術年會.北京:新華出版社2005:1403-1406.