[發明專利]一種實時系統任務調度方法

無效

• 申請號: 200710176704.4
• 申請日: 2007-11-01
• 公開（公告）號: CN101145112A
• 公開（公告）日: 2008-03-19
• 發明（設計）人: 侯亞榮;張書杰;李健;熊璋
• 申請（專利權）人: 北京工業大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 北京匯澤知識產權代理有限公司
• 代理人: 張穎玲

技術領域

本發明涉及任務調度，特別是涉及一種實時系統中的任務調度方法。

背景技術

實時系統是隨著計算機應用于實時控制和實時信息處理領域中而發展起來的，它要求計算機對于外來信息能以足夠快的速度進行處理，并在被控制對象允許的時間范圍內做出快速響應，其響應時間要求在秒級、毫秒級甚至微秒級或更小。實時系統的主要特征之一是響應的即時性，所謂響應的即時性是指要在時間約束之內完成運算。其中，時間約束是指截止時間或稱時限，是實時系統給出處理結果的最遲可以接受的時間。

在實時系統中，任務調度方法是直接影響實時系統響應即時性的關鍵因素，因而對任務調度方法的研究具有十分重要的意義。目前，實時系統中使用最普遍的是最早時限優先算法(EDF，Earliest?Deadline?First)，EDF算法是廣泛使用的最具代表性的一種實時調度算法。

具體來說，EDF調度的基本工作原理是：優先處理最緊迫任務，每當有資源空閑下來時，調度程序就選擇具有最早時限的任務，并賦給所選任務所需的資源，使所選任務獲得運行權。EDF調度已被證明對基于時限標準的單資源分配來說是最優的，但是，針對多個相同資源的分配問題，EDF調度卻無法實現整體最優化。例如，一個多CPU多任務調度系統，各CPU的主頻不同，各任務的運算量不同，如果采用EDF調度算法，則很有可能為具有最早時限但運算量大的任務分配一個最先空閑下來的低主頻CPU；而下一個擁有最早時限的任務，盡管運算量小，卻被分配一個高主頻CPU。因此，EDF調度并不能實現多資源多任務實時系統的最優調度。

發明內容

有鑒于此，本發明的主要目的在于提供一種實時系統任務調度方法，能實現對多資源多任務的最優調度，提高資源利用率和時限內到達任務比例。

為達到上述目的，本發明的技術方案是這樣實現的：

一種實時系統中的任務調度方法，包括：

A、根據時限和運算量對待調度任務進行順序排列；

B、有空閑資源時，按排列順序為一個或一個以上待調度任務分配資源，其中，為一個以上待調度任務分配資源時，所分配資源的多個任務間最大時延最小。

其中，步驟A中，先根據待調度任務的時限先后，將時限早的任務排在任務調度隊列前邊；對存在的多個時限相同的任務，再按任務運算量大小，將運算量大的任務排在任務調度隊列前邊；對多個時限和運算量均相同的任務，將所述任務隨機排列。

上述方案中，步驟B所述為待調度任務分配資源具體包括：

B1、初始化任務調度隊列；

B2、確定當前要調度的一個或一個以上任務；

B3、為步驟B2所確定的當前要調度任務分配資源，且所分配資源的多個任務間滿足其中，U_k為當前調度的任務，為確定要分配的資源；

B4、根據當前資源分配情況及資源恢復空閑情況，更新空閑資源集合；

B5、根據當前的任務調度情況，更新任務調度隊列；

B6、判斷是否調度完所有任務，如果調度完，則結束當前任務調度流程；如果未調度完，則返回步驟B2。

其中，所述每個任務調度隊列與每個可分配資源一一對應。

其中，步驟B4中所述更新空閑資源集合具體為：從空閑資源集合中刪除當前被占用的資源，并將當前恢復空閑的資源加入空閑資源集合中。步驟B5所述更新任務調度隊列為：將當前所分配的任務U_k添加到任務調度隊列中。步驟B6中所述判斷是否調度完所有任務為：判斷未調度任務隊列是否為空，如果為空，則調度完所有任務；否則，未調度完。

本發明所提供的實時系統任務調度方法，將所有需調度任務按時限先后順序排列，同時，對多個時限相同的任務，按任務運算量大小排列，運算量大的排在任務調度隊列前面；這樣，在有空閑資源時，按任務調度隊列的排序分配資源，且在對多個任務進行資源分配時采用聚類時延最小策略，如此，不僅能保證多個同時調度的任務的最大時延最小化；而且打破了單資源分配最優的局限性，進而提高了資源利用率和時限內到達任務比例等性能指標，為實時系統任務調度提供了一種可實現整體最優化的方法。

具體實施方式

本發明的任務調度方法首先對實時系統中的任務進行排隊，之后再對經過排隊的任務進行調度。具體的，所述對實時系統中的任務進行排隊一般采用如下策略：根據待調度任務的時限先后，時限早的任務排在任務調度隊列前邊；若存在多個任務時限相同，則按照任務運算量大小，運算量大的任務排在任務調度隊列前邊；若多個任務的時限和運算量均相同，則將這些任務隨機排列。