實時多核系統面向負載均衡的任務分區調度算法

方 興

(武漢藏龍北路1號 武漢 430205)

實時多核系統面向負載均衡的任務分區調度算法

方 興

(武漢藏龍北路1號 武漢 430205)

實時應用對系統性能存在迫切需求,基于多核和眾核架構的并行處理成為提升性能的主要途徑。為了充分發揮多核處理器的性能,必需盡可能提高實時應用的并行度。只有如此,才能同時高效利用處理器的每個核心。為了保證實時性能,同時高效利用多核資源,需要一種同時考慮可調度性和負載均衡的任務調度方法。當前已有的針對多核系統的實時任務調度方法,僅考慮調度性或負載均衡,而未能對兩者進行全面考慮。文中提出了一種實時多核系統面向負載均衡的任務分區調度算法,不僅可以保證實時任務性能,而且能夠針對多核系統對任務進行高效分配。實驗結果表明,文中提出的方法在負載均衡效果和可調度性方面優于對比算法。此外,所提出算法的另外一個優點在于通過負載均衡降低了系統能耗。

多核; 實時; 負載均衡; 利用率; 可調度性

Class Number TP391

1 引言

實時處理在工業自動化、醫療設備、電子產品等應用領域發揮重要的作用[1]。計算技術在這些領域的應用需要具有實時性。隨著微處理器架構越來越多核化,處理器中實時任務的高效執行成為密集計算應用的重要保障。為了充分利用多核資源,實時應用必需具備一定的并行度,保證任務能同時分配到多個核心,這也是多核處理器相對于傳統單核處理器能夠提供更有效實時性能的主要途徑。

針對多核處理器中的實時應用,合理的任務調度算法需具備以下特征: 1) 高可調度性,即任務可以在滿足截止時間的前提下被調度; 2) 各個核心中的任務分配均保持負載均衡,資源利用不會引起過度配置和潛能浪費。

已有的多處理器實時任務調度方法可以分為分區調度和全局調度[2]。文獻[3]的研究表明,分區調度比全局調度具有更好的硬實時調度性。因此,本文采取分區調度方法,通過任務分區機制分配任務,單處理機調度器調度分配到每個處理器的任務,從而獲得高可調度性和良好的負載均衡。

目前分區任務調度方法相關的研究主要考慮可調度性[4～6],由于對任務分配中的并行度或負載均衡關注較少,常常會導致性能降低以及資源利用率不足。當前的大部分實時調度算法主要考慮可調度性,已有部分算法開始考慮降低能耗,低能耗特性在移動和嵌入式設備中顯得尤為重要。文獻[7]提出在動態電壓調節方式下,基于任務劃分的負載均衡方法可以降低能耗。但是,已有的負載均衡算法在實時任務的可調度性方面表現不佳。

隨著多核處理器的普及,保證多核心之間的負載均衡也愈發重要。負載均衡旨在均勻分配任務負載,保證每個核心承擔近似相同的工作量。通過均衡分配每個核心的任務量,資源得以有效利用,不會引起過度配置或浪費。此外,結合負載均衡技術和動態電壓[8]調節方式可以有效降低能耗。同時負載均衡還具備以下優勢:優化吞吐量,并提高可靠性。

基于分區調度方法,本文提出了一種實時多核系統面向負載均衡的任務分區調度算法(Real-Time Task Partitioning Scheduling for Multicore Systems with Load Balancing,RTTP),不僅可以實現負載均衡,還可以獲得高可調度性。所提出的算法主要面向彼此獨立、互不影響的任務,首先通過任務劃分機制獲得高可調度性,然后在不影響調度性的前提下實現負載均衡。

任務重新劃分過程中,任務重新劃分機制無需檢測是否滿足可調度標準,只需滿足負載均衡標準,從而獲得一個滿足截止時間限定條件的解決方案。重新劃分操作在無法進一步提高負載均衡時停止,這一特性可以降低劃分算法執行開銷。RTTP算法雖然從負載均衡的角度無法實現最有效的任務映射,但是在保證一定負載均衡的基礎上,實現了可調度性,通過動態電壓調節機制降低了能耗。實驗結果表明與考慮調度性的FFDU(First-Fit Decreasing Utilization)算法相比,RTTP算法與其調度性效果相近;與考慮負載均衡的WWDU(Worst-Fit Decreasing Utilization)算法相比,RTTP算法與其負載均衡效果類似。

2 算法設計

2.1 算法框架

通過降低處理器速度可以降低供電電壓,從而減少執行任務時的能耗。因此,為了降低每個任務的能耗,給每個核心上的任務分配一個最優速度。核心ci上所有任務的最優速度Si是一個常量,表示為Si=Ui,其中Ui表示ci的利用率。

2.2 負載均衡

不均衡程度越大,負載均衡算法的效果越差。文獻[4]中Aydin和Yang給出了利用核心的利用率和任務來表征任務分配的不均衡程度形式化描述。

定義1 當兩個核心ci和cj,如果其利用率滿足條件:Ui-Uj>uk,此處tk∈∏i,則上述兩個核心之間存在負載不平衡。

3 分區實時任務調度

云平臺在同一時刻會收到有多個用戶的服務請求,因此高效的資源分配和任務調度是云計算的一個重要方面。許多學者提出了多種分配、調度和衡量云資源的方法。云的調度過程可以歸納為以下三個過程:通過將多核處理器調度問題分解為多個單核處理器問題,可以獲得當前系統的分區任務調度方法。該方法因不依賴集中化數據結構,不會造成沖突和高速緩存一致性,從而獲得較好的可調度性,并且開銷較低。鑒于可擴展性和可調度性開銷在應用領域至關重要,本文采取分區實時任務調度方法。圖1表示分區方法的框架結構,包含以下操作:

步驟1:將任務分配到各個核心,保證任務可以在截止時間內完成。任務可以按照利用率、截止時間等進行分類。圖1中的分區模塊執行此操作。

步驟2:核心分配完成后,在每個核心的時間期限內,運用單核心調度算法(如EDF,RMS)調度分配的任務。圖1中的調度模塊執行此操作。

步驟1早于系統執行時間,步驟2在步驟1完成后,與系統執行時間同步。步驟1中,任務劃分用于將任務分配到符合可調度標準的合適核心,其本質而言是裝箱問題的一種衍生,可以用首次適應算法[9]、最佳匹配法[10]、下次匹配法[11]、最壞匹配法[12]等啟發式方法來解決。首次適應算法經證實可以保證高可調度性和低開銷,但其任務分配過程會導致多個核心之間的負載難以均衡。

同時,相對于首次適應算法,最壞匹配法可以保證較好的負載均衡,但可調度性不高。針對多核系統的高效實時算法不僅需要保證實時性能,即可調度性,也需要高效的資源利用率,即負載均衡。為解決上述問題,本文提出了一個實時任務劃分策略,不僅可以保證高可調度性,而且可以實現多個或多核系統的負載均衡。

4 基于負載均衡的任務劃分

如圖1所示,部署在劃分模塊的任務劃分機制對可調度性和負載均衡均有重大影響。為了同時保證可調度性和負載均衡,本文提出了一個實時多核系統面向負載均衡的任務分區調度算法,RTTP。RTTP算法執行以下操作:

1) 任務排序:根據利用率從高到底對任務進行排序。

2) 任務劃分:在符合截止時間限制條件的基礎上,將排序后的每個任務分配到符合要求的第一個核心上。

3) 任務重新劃分:若任務劃分后還可以調度,則進行重新劃分。排序后的任務按照逆序,即利用率從低到高,重新分配到對應的各個核心。重新劃分過程遵守負載均衡標準,而無需重新檢測是否符合可調度性標準。重新劃分操作得到的解決方案符合定理1。負載均衡無法進一步提高時,重新劃分操作結束。

FFDU算法可以保證高可調度性,首先采用該算法執行任務劃分,因為任務在截止時間內及時完成是實時系統任務調度的必要條件。任務劃分過程中,檢查每個可用核心上的任務是否符合可調度標準。任務劃分到符合可調度標準的第一個核心。本文引入EDF,作為RTTP算法中每個核心的本地調度器。對于EDF調度算法,核心ci上任務可調度的必要條件為Ui≤1,Ui為核心ci的利用率。若FFDU無法為給定的任務集生成合理的調度方案,則輸出一個值,表明任務劃分失敗。只有FFDU能生成調度方案時才會執行任務重新劃分。

然后,利用FFDU調度算法重新劃分任務,提高負載均衡。重新劃分機制遵循最壞匹配法,但有別于先前的劃分操作,任務按照利用率從低到高排序后進行重新劃分,從而在無需檢測是否滿足可調度性的前提下,獲得任務重新劃分的調度方案,盡管此調度方案與FFDU生成的調度方案可能不一致。此外,鑒于該調度方案操作過程中不會降低負載均衡效果,從而可以有效降低開銷。對任務按照利用率從低到高排序后進行重新劃分操作后,操作就已完成,因為任務之前已按照利用率從高到低的順序劃分過。FFDU算法與WF算法相結合,可以提高任務利用率,稱之為Worst-Fit Increasing Utilization(WFIU)。與WFDU算法相比,WFIU算法可調度性和負載均衡程度不高。但是,在FFDU算法操作之后,通過WFIU重新劃分,可以保證高可調度性和較好的負載均衡,降低調度開銷。當無法進一步提高負載均衡時,任務重劃分操作停止。

定義2 若對當前的任務進行重劃分后,利用率的差值大于或等于當前分配方案的(Umax-Umin),則對任務不進行重新分區。

論證:對任務進行重新劃分前,首先根據當前的任務分配方案分別求得核心利用率的最大值Umax和最小值Umin。當前任務分配方案可能與FFDU分配結果不同,因為在任務重新劃分過程會導致任務分配結果發生變化。基于定義1,對于需要重新劃分的任務,其最大利用率小于核心最大值和最小值的差值,若大于此差值,則無需重新劃分。鑒于任務是按照利用率由低到高的順序依次考慮是否需要重新劃分,當滿足上述條件時重新劃分機制停止,無需對剩余任務進行操作

RTTP算法在FFDU可以生成合理的解決方案的前提下,會得到合理的任務分配方案,在重新劃分過程中無需進行可調度性測試。因而,RTTP算法與FFDU算法的可調度性類似。

定理1 如果FFDU可以生成合理的解決方案,則RTTP也可以生成合理的解決方案。

證明:對于通過FFDU算法實現的分配,若每個核心ci(ci∈C)的利用率均不高于1,就可以滿足該核心上所有任務的截止時間限定條件。對于核心ci,任務tk當前分配于該核心上,核心ci的利用率小于等于1,因為截止時間必須得到滿足:

Ui≤1,tk∈∏i

(1)

任務將重新劃分到利用率值最低的目標核心,該核心利用率低于1,已分配的任務滿足截止時間要求因為重新劃分的核心利用率不能達到1。

Uj<1,st.minck∈CUk

(2)

假設任務tk的利用率小于當前分配核心的利用率與核心最低利用率的差值,則根據定義1,當前分配是不均衡的。

Uk

(3)

基于此,RTTP算法將任務tk從核心ci移出,并重新將任務tk分配到利用率最低的核心cj。根據式(1)、(3)和(4),隨著任務tk的遷入,核心cj的利用率升高,但仍低于1。

Uj=Uj+uk

(4)

Uj<1

(5)

隨著任務tk的遷出,核心ci的利用率低于1。uk>0且核心ci重新劃分后的利用率不會為1,即Ui≠1,同時:

Ui=Ui-uk<1

(6)

根據式(5)和式(6),核心的利用率小于1,表明重新劃分后的分配結果滿足截止時間條件。根據定義2,重新劃分機制終止:若下一個任務滿足以下條件,則不再進行重新劃分:uk≥(Umax-Umin)。此條件與式(3)相反。在重新劃分過程中,式(1)～式(6)中定義的關系均得到滿足。因此,若FFDU分配滿足所有截止時間限定條件,則RTTP分配也滿足截止時間限定條件。

5 實驗

為了驗證RTTP算法的有效性,本文對RTTP、FFDU和WFDU算法進行了分析比較。FFDU算法可以提供較好的可調度性,而WFDU算法可以提供較好的負載均衡。可調度性可以通過能夠被調度且滿足截止時間的任務在任務集中所占的比率進行衡量,而負載均衡可以通過被調度的任務集所在核心的利用率的歸一化標準差進行衡量。

實驗中,根據任務集的總利用率Utot和任務利用率因子α(α≤1)隨機生成各個任務集,其中α表示任務集中所有任務的最大利用率。任務利用率ui均勻分布在[0,1]區間內,并且任務利用率的總和不高于任務集總體利用率。

連續生成任務,直到任務的總利用率達到給定的任務集總利用率,從而獲得任務集。任務集的總利用率數值在1(輕負載)到核心數m(重負載)之間。圖中所示利用率(x軸)表示為Utot/m的百分比。核心的數量在8～1000之間。鑒于核心數量對結果沒有顯著影響,實驗采用48個核心。每個數據采樣點均生成1000個任務集。本文根據文獻[1]中的功耗模型和方法,采用DVS對功耗進行測量。

圖2表示FFDU、WFDU和RTTP三種算法在可調度性、負載均衡和功耗方面的性能對比。RTTP和FFDU算法可調度性相似,如定理1所述。實驗證明使用FFDU算法調度后,利用率高于WFDU。實驗結果表明,對于RTTP算法,即使在利用率達到98%的高負荷情況下,也能夠在截止時間之前執行完成任務。相比與WFDU算法,RTTP算法在同樣的利用率水平下,任務的可調度性提高了9%～12%,FFDU算法在任務的可調度性方面則具有和WFDU算法相當的性能表現。并且,RTTP算法的負載均衡性能是FFDU算法的5倍。實驗還表明,在通常情況下,結合DVS技術的使用,負載均衡有效地降低了單個核心的功耗,并從整體上降低了總體功耗。相比與FFDU算法,RTTP算法降低了高達65%的功耗。

6 結語

在多核平臺中運行實時應用需要一個高效的調度算法以保障任務的高可調度性和負載均衡。本文提出了一個任務劃分的算法。該算法不僅可以保證實時性能,也能夠針對多核系統對任務進行高效分配。實驗結果表明該算法性能明顯優于對比算法。此外,RTTP算法可以有效降低能耗。該算法稍作修改即可運用到現有的實時系統調度器。

[1] Robert Davis, Alan Burns. A Survey of Hard Real-time Scheduling for Multiprocessor Systems[J]. ACM Computing Surveys(CSUR),2011,43(4):1-44.

[2] Joel Goossens, Pascal Richard. Partitioned Scheduling of Multimode Multiprocessor Real-Time Systems with Temporal Isolation[C]//Proceedings of the 21st International Conference on Real-Time Networks and Systems(RTNS’13). Sophia Antipolis: ACM,2013:297-305.

[3] B. B. Brandenburg, J. M. Calandrino, J. H. Anderson. On the Scalability of Real-time Scheduling Algorithms on Multicore Platforms: A case Study[C]//Real-Time Systems Symp. Barcelona: IEEE,2008:157-169.

[4] Sanjoy B, Fisher N. The Partitioned Multiprocessor Scheduling of Deadline-constrained Sporadic Task Systems[J]. Computers, IEEE Transactions on,2006,55(7):918-923.

[5] 代聲馨,洪玫,郭兵,等.多處理器實時系統可調度性分析的UPPAAL模型[J].軟件學報,2015,2:279-296.

[6] 郭秀巖,張武,王勁林,等.基于改進EDF的多核處理器混合任務調度算法[J].高技術通訊,2012,22(3):231-239.

[7] H. Aydin, Q. Yang. Energy-aware Partitioning for Multiprocessor Real-time Systems[C]//Proc. IEEE International Symp. on Parallel and Distributed Processing(IPDPS’03), Nice: IEEE,2003:157-166.

[8] G. Magklis, G. Semeraro, D. H. Albonesi, et al. Dynamic Frequency and Voltage Scaling for a Multiple-Clock-Domain Microprocessor[J]. I Micro IEEE,2003,23(6):62-68.

[9] Binzhou Xia, Zhiyi Tan. Tighter Bounds of the First Fit Algorithm for the Bin-packing Problem[J]. Discrete Applied Mathematics,2010,158(15):1668-1675.

[11] S Martello, D Pisinger, D Vigo. The Three-Dimensional Bin Packing Problem[J]. Operations Research,1998,48(2):256-267.

[12] 陸一江,邢文訓.在線A形裝箱問題:模型及算法研究[J].清華大學學報(自然科學版),2001,41(12):1-4.

Real-Time Task Partitioning Scheduling for Multicore Systems with Load Balancing

FANG Xing

(No. 1 Canglong North Road, Wuhan 430205)

Real-time applications continuously drive the urgent demand for performance scaling. Parallel processing based on multicore and manycore architectures becomes the principal approach for enhancing system performance. To fully utilize multicore processors, it is necessary to improve parallelism, where tasks can use multiple cores simultaneously. To guarantee real-time performance and make full use of multicore resources requires a scheduling strategy that takes both schedulability and load balancing into consideration. Most existing real-time scheduling policies for multicore systems fail to consider both at the same time. To solve this problem, this paper proposes a real-time task partitioning scheduling for multicore systems with load balancing (RTTP) that not only ensures real-time performance but also achieves load balancing across the cores. The experimental results demonstrate that our algorithm performs well in terms of load balancing and schedulability. Besides, another benefit of the presented method is energy reduction through load balancing.

multicore, real-time, load balancing, utilization, schedulability

2016年7月1日,

2016年8月26日

方興,男,碩士,高級工程師,研究方向:艦載實時操作系統技術。

TP391

10.3969/j.issn.1672-9730.2017.01.008