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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 HVF算法

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

2 ECMB算法分析

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

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

(1)

圖2 任務(wù)各項(xiàng)參數(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)是一個(gè)穩(wěn)定的系統(tǒng)。其中，式(2)的推導(dǎo)過程如下：J={J1,J2,…,Jn-1,Jn}為送入就緒隊(duì)列的任務(wù)流，用n表示單位時(shí)間內(nèi)到達(dá)就緒隊(duì)列的進(jìn)程個(gè)數(shù)，單位時(shí)間內(nèi)n個(gè)進(jìn)程到達(dá)就緒隊(duì)列的概率P(n)應(yīng)該服從泊松分布

(4)

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

(5)

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

(6)

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

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

(7)

其進(jìn)入密度為

(8)

式(8)的期望值為

(9)

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

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

(10)

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

(11)

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

(12)

(13)

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

在以上算法分析基礎(chǔ)上，以截止期前完成百分比[15]、截止期前完成價(jià)值百分比和任務(wù)切換次數(shù)這3個(gè)性能參數(shù)為指標(biāo)對(duì)該算法進(jìn)行仿真并與兩種傳統(tǒng)算法進(jìn)行對(duì)比，仿真結(jié)果如圖3～圖5所示。其中，對(duì)3個(gè)性能參數(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)截止期前完成價(jià)值百分比Vfp，指在截止期前順利完成的任務(wù)的價(jià)值總和與提交任務(wù)的價(jià)值總和之比

(15)

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

[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ú)線接入網(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é)報(bào):自然科學(xué)版,2015,27(1):1-5.

[4] 龍懇,黎偉,蘭瑩菲,等.C-RAN架構(gòu)下一種基于分形定理的載波遷移預(yù)測(cè)算法[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ù)的最小相對(duì)截止期計(jì)算[J].計(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)先級(jí)和調(diào)度方法[J].計(jì)算機(jī)工程,2007,33(21):28-30.

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

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

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

歡迎訂閱《電子科技》

郵發(fā)代號(hào)：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

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

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

10.16180/j.cnki.issn1007-7820.2017.05.004

TN925

A

1007-7820(2017)05-012-04