基于多處理器實時調度策略的研究

摘 要： 多處理器系統中實時調度算法起著重要的作用。在結合了RMS和EDF調度算法的基礎上提出了一種含閾值的多處理器實時任務調度策略，使任務能夠在閾值范圍內在各處理器上進行遷移，避免了部分處理器處于空閑，部分處理器過于繁忙導致任務被掛起的現象，保證了各處理器利用率的相對平衡。

關鍵詞： 多處理器系統； RMS調度算法： EDF調度算法； 實時任務調度模型

中圖分類號： TN40?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2013）21?0124?04

0 引 言

隨著計算機技術的不斷發展，對多處理器系統的需求不斷增加，特別是在航空、導航領域不僅要求系統擁有良好的并行性，還要保證系統的實時性。因此，好的調度策略就顯得尤為重要。在這里針對多處理器的結構提出了一種RMS和EDF算法相結合的實時任務調度模型，通過閾值的設定使任務能夠在處理器上進行遷移。該調度策略充分利用了RMS和EDF算法的優點，為了充分保證實時性在模型的驗證中對EDF算法做了改進，較大程度克服了EDF調度算法引起的多米諾效應，提供了較好的實時調度性能。

1 理論基礎

1.1 RMS算法

為解決周期性任務，提出了速率單調調度算法（Rate Monotonic Scheduling，RMS），任務優先級的確定基于任務的周期，優先級最高的任務周期最短。當有多個任務可供執行時，周期最短的任務首先得到服務。RMS算法需要滿足以下假設的前提[1]：

①所有任務都是周期性的；

②任務間不需要同步，沒有共享資源，任務間的切換時間可忽略不計；

③CPU必須總是執行優先級最高的任務，必須是可被搶占的。

在以上假設的基礎上衡量RMS算法有效性需保證不等式（1）成立：

若把任務的優先級描述成關于它們速率的函數，其結果是一個單調遞增函數。表1給出了這個上界的一些值。當任務數目增加時，調度上界收斂于ln 2。即在單處理器中它的使用率為69.3%。

RMS算法的優點是開銷小，在任務的截止時間等于其周期的條件下，速率單調算法已被證明是靜態最優的調度算法。

1.2 EDF算法

截止期最早的任務優先調度算法，該算法規定任務的截止期限越小，優先級越高。EDF（Earliest Deadline First）是一種動態的優先級調度算法，優先級與任務的最后截止期限成反比。理論上每個時刻都要計算處于等待調度狀態的任務調度優先級，系統下個時刻調度的任務是不確定的，與系統中其他任務有關系。其調度有效性的驗證需滿足不等式（2）成立：

EDF的主要優點是：任務的優先級能夠根據需要動態改變，使得系統適應性比較好。在軟實時消息的調度上要優于靜態調度算法。

EDF的缺陷是：如果一個實時任務在其執行時間之前提前完成本周期內的工作，則在這個周期內剩余的空閑時間里其他任務也不能運行，CPU將處于相對空閑狀態；如果一個實時任務超出了自己的執行時間，工作沒有結束，則將保持當前的優先級繼續執行，這樣就會順延本來已經安排的后續任務，形成多米諾效應，造成多個任務超出截止時間。

EDF算法的改進如下：

（1）當一個實時任務在分配的執行時間之前完成本周期的工作，并且此時有多個任務在等待，剩余的時間片應該分配給優先級最高的任務。

（2）當一個實時任務超出了自己的執行時間，工作沒有結束，這時采用向下一個周期借入的策略，以當前的優先級運行完成余下工作，保證到來的下一個任務的有效執行，解除了連續多個任務超出截止時間的多米諾效應。

2 多處理器系統的實時任務調度策略

多處理器調度就是將[n]個任務分配到[m]個處理器上（需要滿足前后約束關系），確保每個任務能準確迅速地完成。任務調度概念圖如圖1所示。

因此，在多處理器任務實時調度中涉及以下2個相關的問題：

（1）如何把任務分配到各處理器。在這里使用全局調度策略，任務到來時首先將任務放入公共就緒隊列中，使用RMS算法確定任務的優先級，完成任務到處理器的分派，周期越短優先級越高越優先被分配。接下來的工作就可被看做是單處理器上任務的調度。

（2）在單個處理器中如何調度就緒任務。當就緒任務被放入到各處理器就緒隊列時，我們使用改進后的EDF算法進行調度，保證任務的執行。

2.1 調度算法相關參數

任務集定義為[T={t1，t2，t3，…，tn}。]

任務使用4元祖定義[ti（Ai，Ci，Ti，Di）。]

其中，[Ai]：任務[i]的到達時間；[Ci]：任務[i]的執行時間；其中，[Ti]為任務[i]的周期；[Di]為任務[i]的最后截止期限。

定義：每一個處理器的利用率為總任務在特定的處理器上執行利用率之和，即：

2.2 算法思想

在這里使用全局調度機制來維護一個全局調度隊列，即公共就緒隊列將到來的等待被分配的任務分配到獨立的不同處理器上。在全局調度隊列中使用RMS算法將任務分配給各處理器，擁有最高優先級的任務被分配到第一個處理器所對應的就緒隊列中，依次分配；如圖2所示，當任務依次順序放入QUEUE（0…[n]）隊列后，等待各個處理器的調度（在初次任務分配時假設QUEUE（0…[n]）隊列均為空），在此處QUEUE（0…[n]）隊列要求與處理器一一對應。在各獨立的處理器中使用改進的EDF算法進一步執行任務調度。

對于單處理器而言，改進后的EDF算法能夠很好地完成調度工作，但是對于超負載的問題出現時改進后的EDF算法也不再有效。因此，在多處理器系統中，當系統超過它的利用率限制（即閾值）時需要進行任務的遷移。在任務遷移前先要對閾值做如下的計算：

（1）閾值計算：[f=U1+U2+…+Unn。]

（2）超負載處理器：該處理器的利用率[Ui]>1或者[Ui>f。]

（3）輕負載處理器：該處理器的利用率[Ui]<50%或者[Ui

（4）遷移任務的選擇：在此調度模型中，改進后的EDF算法根據截止期限的長短確定任務的優先調度順序。因此，處于最低優先級的任務就成為被遷移的對象。

此時，EDF算法的改進以及任務的遷移都有助于解決多米諾效應，并保證各獨立處理器利用率的平衡。

2.3 實時任務調度過程

實時任務調度流程圖如圖3所示。

具體過程如下：

（1）開始；

（2）周期任務集到達；

（3）根據RMS算法確定任務的周期指定任務的優先級；

（4）在任務優先級確定的基礎上將任務分派到各處理器上；

（5）在各處理器上使用改進后的EDF算法進行任務的調度，在此處被調度任務的優先級與任務的截止期限成反比，即截止期限越短優先級越高，越優先被調度；

（6）各處理器上利用率與計算的閾值做比較，如果[Ui>f，]則該處理器被認為超負載的，需要進行任務的遷移，將超負載處理器上的任務遷移到輕負載的處理器上進行調度；

（7）結束。

2.4 調度算法的實現

上節給出了多處理器實任務實時調度的模型，在本節將運用上面提出的調度模型對任務進行模擬調度，進一步了解所提出的調度模型的思想與調度過程。

在此多處理器系統中假設存在4個處理器，每一個處理器被視為同構本身無優先級高低之分，且每一個處理器對應一個QUEUQ（0…4）隊列；等待分派的任務集[T={t1，t2，t3，t4，t5，t6，t7，t8，t9}，][t1]（0，1，2，2），[t2]（1，3，6，6），[t3]（1，2，2，2），[t4]（1，2，4，4），[t5]（3，1，5，5），[t6]（4，2，8，8），[t7]（2，1，6，6），[t8]（5，2，10，10），[t9]（4，4，12，12）調度步驟如下：

步驟一：將任務集[T]中的任務分派到QUEUE（0…[n]）就緒隊列：

根據RMS調度算法的思想，任務集[T]按照任務的周期的大小排序依次為：

[t1]=[t3]<[t4]<[t5]<[t2]=[t7]<[t6]<[t8]<[t9]

周期越小越優先被分派，因此，任務[t1]被分派到處理器0所對應的QUEUR0隊列中，[t3]被分派到QUEUR1隊列中，同理， [t4]、[t5] [t2]、[t7]、[t6]、[t8]、[t9]依次順序被分派到QUEUR2、QUEUR3、QUEUR0、QUEUR1、QUEUR2、QUEUR3、QUEUR0隊列中。分派結束后在各QUEUR（0…[n]）隊列中的調度序列如圖4所示。

3 結 語

本本提出的多處理器實時任務調度模型，利用RMS算法在一定程度上既滿足了任務到處理器的分配，又保證了短任務優先被調度的優勢。在單處理器上任務的調度使用改進后的EDF算法并能夠對任務進行遷移，充分保證了任務調度的實時性。在未來的工作中將進一步完善實驗以提高系統的性能。

參考文獻

[1] 王永吉，陳秋萍.單調速率及其擴展算法的可調度性判斷[J].軟件學報，2009，15（6）：799?814.

[2] 尹江會，劉捷，管素清.實時系統中傳統調度方式的一種改進方法[J].計算機工程與應用，2005（6）：72?74.

[3] 謝敏，李橋梁.嵌入式實時操作系統任務調度算法優化[J].電子科技，2005（12）：24?26.

[4] LIU C L， LAYLAND J W. Scheduling algorithms for multiprogramming in a [hard?real?time] environment [J]. Journal of ACM， 1973， 20（1）： 174?189.

[5] 楊立身，王中海.嵌入式實時操作系統任務調度算法改進[J].計算機應用，2009，29（9）：2517?2519.

[6] 梁紅兵.《計算機操作系統》學習指導與題解[M].西安：西安電子科技大學出版社，2008.

[7] 譚耀鉻.操作系統[M].北京：中國人民大學出版社，2007.

[8] XU L H， BRUCK J. Deterministic voting in distributed systems using error?correcting codes [J]. IEEE Transactions on Paralled and Distributed Systems， 1998， 9（8）： 813?824.

[9] 瞿鴻鳴.單處理器系統的實時調度算法研究[J].微機發展，2003（10）：99?100.

[10] 秦嘯，韓宗芬，李勝利，等.多處理機系統的高效實時容錯調度算法[J].華中理工大學學報，1999，27（7）：14?16.