方 興

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

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

方 興

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

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

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

Class Number TP391

1 引言

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

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

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

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

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

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

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

2 算法設(shè)計

2.1 算法框架

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

2.2 負(fù)載均衡

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

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

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

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

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

步驟2:核心分配完成后,在每個核心的時間期限內(nèi),運(yùn)用單核心調(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)度標(biāo)準(zhǔn)的合適核心,其本質(zhì)而言是裝箱問題的一種衍生,可以用首次適應(yīng)算法[9]、最佳匹配法[10]、下次匹配法[11]、最壞匹配法[12]等啟發(fā)式方法來解決。首次適應(yīng)算法經(jīng)證實(shí)可以保證高可調(diào)度性和低開銷,但其任務(wù)分配過程會導(dǎo)致多個核心之間的負(fù)載難以均衡。

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

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

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

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

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

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

FFDU算法可以保證高可調(diào)度性,首先采用該算法執(zhí)行任務(wù)劃分,因?yàn)槿蝿?wù)在截止時間內(nèi)及時完成是實(shí)時系統(tǒng)任務(wù)調(diào)度的必要條件。任務(wù)劃分過程中,檢查每個可用核心上的任務(wù)是否符合可調(diào)度標(biāo)準(zhǔn)。任務(wù)劃分到符合可調(diào)度標(biāo)準(zhǔn)的第一個核心。本文引入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ù),提高負(fù)載均衡。重新劃分機(jī)制遵循最壞匹配法,但有別于先前的劃分操作,任務(wù)按照利用率從低到高排序后進(jìn)行重新劃分,從而在無需檢測是否滿足可調(diào)度性的前提下,獲得任務(wù)重新劃分的調(diào)度方案,盡管此調(diào)度方案與FFDU生成的調(diào)度方案可能不一致。此外,鑒于該調(diào)度方案操作過程中不會降低負(fù)載均衡效果,從而可以有效降低開銷。對任務(wù)按照利用率從低到高排序后進(jìn)行重新劃分操作后,操作就已完成,因?yàn)槿蝿?wù)之前已按照利用率從高到低的順序劃分過。FFDU算法與WF算法相結(jié)合,可以提高任務(wù)利用率,稱之為Worst-Fit Increasing Utilization(WFIU)。與WFDU算法相比,WFIU算法可調(diào)度性和負(fù)載均衡程度不高。但是,在FFDU算法操作之后,通過WFIU重新劃分,可以保證高可調(diào)度性和較好的負(fù)載均衡,降低調(diào)度開銷。當(dāng)無法進(jìn)一步提高負(fù)載均衡時,任務(wù)重劃分操作停止。

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

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

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

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

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

Ui≤1,tk∈∏i

(1)

任務(wù)將重新劃分到利用率值最低的目標(biāo)核心,該核心利用率低于1,已分配的任務(wù)滿足截止時間要求因?yàn)橹匦聞澐值暮诵睦寐什荒苓_(dá)到1。

Uj<1,st.minck∈CUk

(2)

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

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,重新劃分機(jī)制終止:若下一個任務(wù)滿足以下條件,則不再進(jìn)行重新劃分:uk≥(Umax-Umin)。此條件與式(3)相反。在重新劃分過程中,式(1)～式(6)中定義的關(guān)系均得到滿足。因此,若FFDU分配滿足所有截止時間限定條件,則RTTP分配也滿足截止時間限定條件。

5 實(shí)驗(yàn)

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

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

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

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

6 結(jié)語

在多核平臺中運(yùn)行實(shí)時應(yīng)用需要一個高效的調(diào)度算法以保障任務(wù)的高可調(diào)度性和負(fù)載均衡。本文提出了一個任務(wù)劃分的算法。該算法不僅可以保證實(shí)時性能,也能夠針對多核系統(tǒng)對任務(wù)進(jìn)行高效分配。實(shí)驗(yàn)結(jié)果表明該算法性能明顯優(yōu)于對比算法。此外,RTTP算法可以有效降低能耗。該算法稍作修改即可運(yùn)用到現(xiàn)有的實(shí)時系統(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] 代聲馨,洪玫,郭兵,等.多處理器實(shí)時系統(tǒng)可調(diào)度性分析的UPPAAL模型[J].軟件學(xué)報,2015,2:279-296.

[6] 郭秀巖,張武,王勁林,等.基于改進(jìn)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日

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

TP391

10.3969/j.issn.1672-9730.2017.01.008