方 興

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

實時多核系統(tǒng)面向負載均衡的任務(wù)分區(qū)調(diào)度算法

方 興

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

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

多核; 實時; 負載均衡; 利用率; 可調(diào)度性

Class Number TP391

1 引言

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

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

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

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

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

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

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

2 算法設(shè)計

2.1 算法框架

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

2.2 負載均衡

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

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

3 分區(qū)實時任務(wù)調(diào)度

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

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

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

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

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

4 基于負載均衡的任務(wù)劃分

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

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

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

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

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

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

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

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

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

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

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

Ui≤1,tk∈∏i

(1)

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

Uj<1,st.minck∈CUk

(2)

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

Uk

(3)

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

Uj=Uj+uk

(4)

Uj<1

(5)

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

Ui=Ui-uk<1

(6)

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

5 實驗

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

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

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

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

6 結(jié)語

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

[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] 代聲馨,洪玫,郭兵,等.多處理器實時系統(tǒng)可調(diào)度性分析的UPPAAL模型[J].軟件學(xué)報,2015,2:279-296.

[6] 郭秀巖,張武,王勁林,等.基于改進EDF的多核處理器混合任務(wù)調(diào)度算法[J].高技術(shù)通訊,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] 陸一江,邢文訓(xùn).在線A形裝箱問題:模型及算法研究[J].清華大學(xué)學(xué)報(自然科學(xué)版),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日

方興,男,碩士,高級工程師,研究方向:艦載實時操作系統(tǒng)技術(shù)。

TP391

10.3969/j.issn.1672-9730.2017.01.008