汪珊珊，高煒委，靳玲鴿，李 靖

(西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室, 陜西 西安 710071)

一種基于C-RAN載波遷移模型的緩沖區(qū)清空算法

汪珊珊，高煒委，靳玲鴿，李 靖

(西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室, 陜西 西安 710071)

在C-RAN架構(gòu)下的分層載波遷移過程中，遷移管理中心的緩存單元存儲著待處理的L2/L3層協(xié)議棧數(shù)據(jù)。為保證用戶業(yè)務(wù)的連續(xù)性，需及時清空緩沖區(qū)。針對該問題，提出一種動態(tài)改變L2/L3層協(xié)議棧進(jìn)程優(yōu)先級的載波遷移緩沖區(qū)清空(ECMB)算法，并通過與傳統(tǒng)EDF和HVF算法的仿真對比，驗證了該算法在清空緩沖區(qū)操作中的有效性。

C-RAN；載波遷移；緩沖區(qū)清空算法；進(jìn)程調(diào)度

隨著通信技術(shù)的發(fā)展，目前關(guān)于C-RAN架構(gòu)[1-2]下的載波遷移[3-4]技術(shù)的研究成為熱點。在分層載波遷移技術(shù)中，需利用緩沖區(qū)存儲遷移中斷期間待處理的L2/L3層協(xié)議棧數(shù)據(jù)。由于通信系統(tǒng)的實時性[5-7]要求，需要在遷移完成后快速清空緩沖區(qū)。在利用進(jìn)程調(diào)度清空緩沖區(qū)的傳統(tǒng)算法中，最早截止期限優(yōu)先[8-10](Earliest Deadline First ,EDF)算法將任務(wù)的執(zhí)行截止期限作為指標(biāo)。價值優(yōu)先[11](Highest Value First，HVF)算法將任務(wù)的價值度作為指標(biāo)。由于指標(biāo)單一，當(dāng)任務(wù)數(shù)增多時兩種算法性能均不理想。載波遷移緩沖區(qū)清空(Empty Carrier Migration Buffer，ECMB)算法是一種在EDF和HVF算法基礎(chǔ)上的改進(jìn)算法。該算法在兼顧系統(tǒng)其他任務(wù)正常運(yùn)行的條件下，通過動態(tài)調(diào)整L2/L3層協(xié)議棧進(jìn)程的調(diào)度參數(shù)使其多次利用CPU，達(dá)到快速清空緩沖區(qū)的目的。

1 EDF和HVF進(jìn)程調(diào)度算法

1.1 EDF算法

EDF算法將任務(wù)的執(zhí)行截止期限定義為任務(wù)的優(yōu)先級，是一種動態(tài)的優(yōu)先級調(diào)度算法，當(dāng)任務(wù)的截止期限越近，任務(wù)的調(diào)度優(yōu)先級就越高，反之亦然。當(dāng)就緒隊列中有新任務(wù)到來或者有未完成的任務(wù)時，就需要根據(jù)任務(wù)的優(yōu)先級來調(diào)整任務(wù)的執(zhí)行順序。任務(wù)的相關(guān)參數(shù)設(shè)置如表1所示, 假設(shè)用di表示任務(wù)Ti的截止期限。

圖1 EDF算法的多任務(wù)數(shù)據(jù)

表1 多任務(wù)參數(shù)表

任務(wù)名稱到達(dá)時刻執(zhí)行時間截止期限T101030T24314T351025

現(xiàn)通過分析如圖1所示的一組多任務(wù)數(shù)據(jù)來介紹EDF算法。

當(dāng)任務(wù)T1在0時刻到達(dá)時，因其是目前僅存的一個任務(wù)，所以會被立即執(zhí)行。當(dāng)任務(wù)T2在時刻4到達(dá)時，因其截止期限d2d2，因而任務(wù)T2繼續(xù)執(zhí)行直至任務(wù)結(jié)束。當(dāng)任務(wù)T2在時刻7執(zhí)行完成后，由于任務(wù)T3的截止期

1.2 HVF算法

HVF算法與EDF算法在本質(zhì)上相似，將任務(wù)的價值度作為優(yōu)先級參數(shù)。任務(wù)的價值度越高，任務(wù)的優(yōu)先級就越高，反之亦然。當(dāng)就緒隊列中有新任務(wù)到來或者有未完成的任務(wù)時，就需要根據(jù)任務(wù)的優(yōu)先級來調(diào)整任務(wù)的執(zhí)行順序。

2 ECMB算法分析

為了在提高L2/L3層協(xié)議棧進(jìn)程優(yōu)先級的同時又不嚴(yán)重影響系統(tǒng)其它進(jìn)程的正常運(yùn)行，可選取多個參數(shù)作為指標(biāo)來提高系統(tǒng)的任務(wù)調(diào)度性能。進(jìn)程執(zhí)行的時間緊迫性可結(jié)合EDF調(diào)度算法，進(jìn)程執(zhí)行的重要性可作為對EDF調(diào)度算法的一個修正。

由于任務(wù)剩余價值越大意味著任務(wù)的重要性越高，任務(wù)的裕度值越小意味任務(wù)被執(zhí)行的緊迫性越大。因此，用剩余價值和裕度值的比值來表示調(diào)度參數(shù)[14]fi，具體定義為

(1)

圖2 任務(wù)各項參數(shù)

當(dāng)前正在處理的任務(wù)Ji完成后再執(zhí)行。在系統(tǒng)內(nèi)進(jìn)行任務(wù)調(diào)度需要滿足式(2)和式(3)

(2)

(3)

滿足式(2)的系統(tǒng)進(jìn)程集合是可調(diào)度的，滿足式(3)的系統(tǒng)是一個穩(wěn)定的系統(tǒng)。其中，式(2)的推導(dǎo)過程如下：J={J1,J2,…,Jn-1,Jn}為送入就緒隊列的任務(wù)流，用n表示單位時間內(nèi)到達(dá)就緒隊列的進(jìn)程個數(shù)，單位時間內(nèi)n個進(jìn)程到達(dá)就緒隊列的概率P(n)應(yīng)該服從泊松分布

(4)

其中，λ表示到達(dá)率且λ>0，由期望值定義可知，每單位時間內(nèi)到達(dá)就緒隊列的進(jìn)程個數(shù)平均值為

(5)

所以，進(jìn)程到達(dá)就緒隊列的平均值是λ，即單位時間內(nèi)到達(dá)就緒隊列的進(jìn)程數(shù)為到達(dá)率λ。由式(4)可知，m個進(jìn)程在以時間長度為t的任意時間間隔內(nèi)到達(dá)的概率為

(6)

則至少有一個進(jìn)程在t時間間隔內(nèi)到達(dá)系統(tǒng)的概率是

P(n(t)>0)=1-e-λt

(7)

其進(jìn)入密度為

(8)

式(8)的期望值為

(9)

其中，密度函數(shù)期望值是指連續(xù)兩個進(jìn)程進(jìn)入就緒隊列的時間間隔，所以，平均每隔1/λ時間間隔就會有一個進(jìn)程進(jìn)入就緒隊列。

處理機(jī)在單位時間內(nèi)從就緒隊列中調(diào)度的進(jìn)程個數(shù)用n表示，則由進(jìn)程進(jìn)入就緒隊列的原理可知，單位時間間隔內(nèi)n個進(jìn)程被調(diào)度的概率為P(k)，且其服從泊松分布

(10)

在單位時間內(nèi)調(diào)度程序從就緒隊列中調(diào)度的進(jìn)程個數(shù)為φ，即就緒隊列中的進(jìn)程平均每隔1/φ時間就會有一個被調(diào)度。顯然，只有當(dāng)進(jìn)程進(jìn)入就緒隊列的時間間隔大于進(jìn)程被調(diào)度的時間間隔時才有可能實現(xiàn)系統(tǒng)穩(wěn)定，即要保證就緒隊列中的進(jìn)程不會無限制的增長，需保證式(11)成立

(11)

由隊列分析可知，此時就緒隊列中進(jìn)程數(shù)n應(yīng)滿足

(12)

(13)

3 仿真結(jié)果及性能分析

在以上算法分析基礎(chǔ)上，以截止期前完成百分比[15]、截止期前完成價值百分比和任務(wù)切換次數(shù)這3個性能參數(shù)為指標(biāo)對該算法進(jìn)行仿真并與兩種傳統(tǒng)算法進(jìn)行對比，仿真結(jié)果如圖3～圖5所示。其中，對3個性能參數(shù)的定義如下：

(1)截止期前完成百分比Dfp，指在截止期前完成的任務(wù)數(shù)與提交的總?cè)蝿?wù)數(shù)之比。M表示提交的總?cè)蝿?wù)數(shù)，F(xiàn)i=1表示任務(wù)Ti在截止期前正常執(zhí)行完成，F(xiàn)i=0表示任務(wù)Ti在截止前未正常執(zhí)行完成

(14)

(2)截止期前完成價值百分比Vfp，指在截止期前順利完成的任務(wù)的價值總和與提交任務(wù)的價值總和之比

(15)

(3)任務(wù)切換次數(shù)，指在整個任務(wù)調(diào)度過程中，前一個任務(wù)未完成而被后一個任務(wù)搶占CPU，導(dǎo)致前一個任務(wù)被加入到就緒隊列中的次數(shù)。

圖3 截止期前任務(wù)完成個數(shù)情況變化曲線

圖4 截止期前任務(wù)完成價值情況變化曲線

由圖3和圖4所示，當(dāng)負(fù)載較小時，ECMB算法的截止期前完成百分比和完成價值收益百分比，與傳統(tǒng)HVF和EDF算法相比，沒有明顯優(yōu)勢。而當(dāng)系統(tǒng)負(fù)載增高時，由于EDF算法對截止期限比較敏感，后續(xù)接入的任務(wù)若截止期靠前將會存在大量被搶占情況，致使很多任務(wù)在截止期前不能完成，因此EDF算法隨著任務(wù)負(fù)載的加重其性能急劇下降。并且，在仿真結(jié)果中ECMB算法獲得截止期前完成百分比明顯高于EDF算法。這是由于ECMB算法在考慮截止期的同時又考慮了任務(wù)本身的重要性，并在任務(wù)重要性方面進(jìn)行了二次判斷，所以那些截止期靠前且重要性較高的任務(wù)不會被輕易打斷。

雖然HVF算法隨著負(fù)載加重其截止期完成百分比在降低，但是由于其盡可能去完成重要性級別較高的任務(wù)，所以其完成價值百分比要高于EDF算法。在完成價值百分比方面，ECMB算法的略高于HVF算法，但ECMB算法有效地降低了任務(wù)截止期前的錯失率。因此ECMB算法與EDF算法相比，在保證網(wǎng)絡(luò)整體價值度方面有較大改進(jìn)。

圖5 任務(wù)切換次數(shù)圖示

如圖5所示，ECMB算法使得一部分原按照搶占式EDF算法必然會發(fā)生搶占的任務(wù)，由于調(diào)度參數(shù)的比較而被拒絕搶占。該算法在減少搶占次數(shù)的同時也保證了相對重要的任務(wù)能得到優(yōu)先傳送，并且由于任務(wù)在被打斷后再次被調(diào)度時存在上下文切換等開銷，而ECMB算法較其它兩種算法被打斷的次數(shù)少，性能更優(yōu)。

4 結(jié)束語

本文在EDF和HVF算法的基礎(chǔ)上，提出了ECMB算法。該算法通過提高L2/L3層協(xié)議棧進(jìn)程優(yōu)先級來盡可能多次的利用CPU清空緩沖區(qū)，從而保證用戶業(yè)務(wù)的連續(xù)性。由于在清空緩沖區(qū)數(shù)據(jù)時，L2/L3層協(xié)議棧進(jìn)程優(yōu)先級較高，可能會嚴(yán)重影響系統(tǒng)其它進(jìn)程的正常運(yùn)行。因此，本算法在考慮截止期參數(shù)的條件下，結(jié)合二次判斷調(diào)度參數(shù)，使截止期靠前且關(guān)鍵性又高的任務(wù)優(yōu)先執(zhí)行，并通過對比仿真驗證了該算法的有效性。

[1] Wu J, Zhang Z, Hong Y, et al. Cloud radio access network (C-RAN): a primer[J].IEEE Network,2015,29(1):35-41.

[2] 張若文,方韌,李覲,等.無線接入網(wǎng)演進(jìn)之C-RAN技術(shù)[J].電信工程技術(shù)與標(biāo)準(zhǔn)化,2012,25(4):79-84.

[3] 龍懇,蘭瑩菲,黎偉.一種C-RAN架構(gòu)下載波遷移的調(diào)度策略[J].重慶郵電大學(xué)學(xué)報:自然科學(xué)版,2015,27(1):1-5.

[4] 龍懇,黎偉,蘭瑩菲,等.C-RAN架構(gòu)下一種基于分形定理的載波遷移預(yù)測算法[J].科學(xué)技術(shù)與工程,2015,15(5):258-261,271.

[5] Shin K G,Ramanathan P.Real-time computing: A new discipline of computer science and engineering[J].Proceedings of the IEEE,1994,82(1):6-24.

[6] Klein M,Ralya T,Pollak B,et al.A practitioner’s handbook for real-time analysis: guide to rate monotonic analysis for real-time systems[M].Berlin:Springer Science & Business Media,2012.

[7] Klein M H,Lehoczky J P,Rajkumar R.Rate-monotonic analysis for real-time industrial computing[J].Computer,1994,27(1):24-33.

[8] Liu C L,Layland J W.Scheduling algorithms for multiprogramming in a hard-real-time environment[J].Journal of the ACM (JACM), 1973,20(1):46-61.

[9] Hoang H,Buttazzo G,Jonsson M,et al. Computing the minimum EDF feasible deadline in periodic systems[C].UT,USA:12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’06),IEEE,2006.

[10] 檀明,魏臻,韓江洪.非搶占式EDF算法下周期性任務(wù)的最小相對截止期計算[J].計算機(jī)應(yīng)用研究,2012,29(2):722-724.

[11] Jensen E D,Locke C D,Tokuda H.A time-driven scheduling model for real-time operating systems[C].TX,USA:RTSS,1985.

[12] 周本海,王溪波,喬建忠,等.基于多參數(shù)的μC/OS-Ⅱ任務(wù)優(yōu)先級和調(diào)度方法[J].計算機(jī)工程,2007,33(21):28-30.

[13] 王強(qiáng),徐俊剛,王宏安,等.一種新的基于優(yōu)先級表的實時調(diào)度算法[J].電子學(xué)報,2004,32(2):310-313.

[14] 王永炎,王強(qiáng),王宏安,等.基于優(yōu)先級表的實時調(diào)度算法及其實現(xiàn)[J].軟件學(xué)報,2004,15(3):360-370.

[15] 王強(qiáng),王宏安,金宏,等.實時系統(tǒng)中的非定期任務(wù)調(diào)度算法綜述[J].計算機(jī)研究與發(fā)展,2004,41(3):385-392.

歡迎訂閱《電子科技》

郵發(fā)代號：52-246

A Buffer Emptying Algorithm Based on the Carrier Migration Model of C-RAN

WANG Shanshan，GAO Weiwei，JIN Lingge，LI Jing

(State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an 710000, China)

In the process of layered carrier migration in a C-RAN architecture, the cache unit of migration management center should store the data to be processed of layerL2/L3protocol stack. Besides, emptying the data timely from the buffer is needed in order to ensure the continuity of the user business. Aiming at this problem, an algorithm called ECMB is proposed to dynamically change the priority of the layerL2/L3protocol stack. The effectiveness of this algorithm in emptying the buffer is verified by simulation comparison with the traditional EDF and HVF algorithms.

cloud-radio access network; carrier migration; empty carrier migration buffer (ECMB) algorithm; process scheduling

2016- 06- 26

國家科技重大專項(2014ZX03003003-004)；國家自然科學(xué)基金(61501347, 61372067)

汪珊珊(1992-)，女，碩士研究生。研究方向：移動通信和寬帶無線通信。高煒委(1992-)，女，碩士研究生。研究方向：移動通信和寬帶無線通信。靳玲鴿(1990-)，女，工程師。研究方向：無線通信。李靖(1980-)，男，博士，副教授，碩士生導(dǎo)師。研究方向：無線通信。

10.16180/j.cnki.issn1007-7820.2017.05.004

TN925

A

1007-7820(2017)05-012-04