一种基于C-RAN载波迁移模型的缓冲区清空算法
2017-05-18汪珊珊高炜委靳玲鸽
汪珊珊，高炜委，靳玲鸽，李 靖
(西安电子科技大学 综合业务网理论及关键技术国家重点实验室, 陕西 西安 710071)
一种基于C-RAN载波迁移模型的缓冲区清空算法
汪珊珊，高炜委，靳玲鸽，李 靖
(西安电子科技大学 综合业务网理论及关键技术国家重点实验室, 陕西 西安 710071)
在C-RAN架构下的分层载波迁移过程中，迁移管理中心的缓存单元存储着待处理的L2/L3层协议栈数据。为保证用户业务的连续性，需及时清空缓冲区。针对该问题，提出一种动态改变L2/L3层协议栈进程优先级的载波迁移缓冲区清空(ECMB)算法，并通过与传统EDF和HVF算法的仿真对比，验证了该算法在清空缓冲区操作中的有效性。
C-RAN；载波迁移；缓冲区清空算法；进程调度
随着通信技术的发展，目前关于C-RAN架构[1-2]下的载波迁移[3-4]技术的研究成为热点。在分层载波迁移技术中，需利用缓冲区存储迁移中断期间待处理的L2/L3层协议栈数据。由于通信系统的实时性[5-7]要求，需要在迁移完成后快速清空缓冲区。在利用进程调度清空缓冲区的传统算法中，最早截止期限优先[8-10](Earliest Deadline First ,EDF)算法将任务的执行截止期限作为指标。价值优先[11](Highest Value First，HVF)算法将任务的价值度作为指标。由于指标单一，当任务数增多时两种算法性能均不理想。载波迁移缓冲区清空(Empty Carrier Migration Buffer，ECMB)算法是一种在EDF和HVF算法基础上的改进算法。该算法在兼顾系统其他任务正常运行的条件下，通过动态调整L2/L3层协议栈进程的调度参数使其多次利用CPU，达到快速清空缓冲区的目的。
1 EDF和HVF进程调度算法
1.1 EDF算法
EDF算法将任务的执行截止期限定义为任务的优先级，是一种动态的优先级调度算法，当任务的截止期限越近，任务的调度优先级就越高，反之亦然。当就绪队列中有新任务到来或者有未完成的任务时，就需要根据任务的优先级来调整任务的执行顺序。任务的相关参数设置如表1所示, 假设用di表示任务Ti的截止期限。
图1 EDF算法的多任务数据
表1 多任务参数表
任务名称到达时刻执行时间截止期限T101030T24314T351025
现通过分析如图1所示的一组多任务数据来介绍EDF算法。
当任务T1在0时刻到达时，因其是目前仅存的一个任务，所以会被立即执行。当任务T2在时刻4到达时，因其截止期限d2 1.2 HVF算法 HVF算法与EDF算法在本质上相似，将任务的价值度作为优先级参数。任务的价值度越高，任务的优先级就越高，反之亦然。当就绪队列中有新任务到来或者有未完成的任务时，就需要根据任务的优先级来调整任务的执行顺序。 为了在提高L2/L3层协议栈进程优先级的同时又不严重影响系统其它进程的正常运行，可选取多个参数作为指标来提高系统的任务调度性能。进程执行的时间紧迫性可结合EDF调度算法，进程执行的重要性可作为对EDF调度算法的一个修正。 由于任务剩余价值越大意味着任务的重要性越高，任务的裕度值越小意味任务被执行的紧迫性越大。因此，用剩余价值和裕度值的比值来表示调度参数[14]fi，具体定义为 (1) 图2 任务各项参数 当前正在处理的任务Ji完成后再执行。在系统内进行任务调度需要满足式(2)和式(3) (2) (3) 满足式(2)的系统进程集合是可调度的，满足式(3)的系统是一个稳定的系统。其中，式(2)的推导过程如下：J={J1,J2,…,Jn-1,Jn}为送入就绪队列的任务流，用n表示单位时间内到达就绪队列的进程个数，单位时间内n个进程到达就绪队列的概率P(n)应该服从泊松分布 (4) 其中，λ表示到达率且λ>0，由期望值定义可知，每单位时间内到达就绪队列的进程个数平均值为 (5) 所以，进程到达就绪队列的平均值是λ，即单位时间内到达就绪队列的进程数为到达率λ。由式(4)可知，m个进程在以时间长度为t的任意时间间隔内到达的概率为 (6) 则至少有一个进程在t时间间隔内到达系统的概率是 P(n(t)>0)=1-e-λt (7) 其进入密度为 (8) 式(8)的期望值为 (9) 其中，密度函数期望值是指连续两个进程进入就绪队列的时间间隔，所以，平均每隔1/λ时间间隔就会有一个进程进入就绪队列。 处理机在单位时间内从就绪队列中调度的进程个数用n表示，则由进程进入就绪队列的原理可知，单位时间间隔内n个进程被调度的概率为P(k)，且其服从泊松分布 (10) 在单位时间内调度程序从就绪队列中调度的进程个数为φ，即就绪队列中的进程平均每隔1/φ时间就会有一个被调度。显然，只有当进程进入就绪队列的时间间隔大于进程被调度的时间间隔时才有可能实现系统稳定，即要保证就绪队列中的进程不会无限制的增长，需保证式(11)成立 (11) 由队列分析可知，此时就绪队列中进程数n应满足 (12) (13) 在以上算法分析基础上，以截止期前完成百分比[15]、截止期前完成价值百分比和任务切换次数这3个性能参数为指标对该算法进行仿真并与两种传统算法进行对比，仿真结果如图3～图5所示。其中，对3个性能参数的定义如下： (1)截止期前完成百分比Dfp，指在截止期前完成的任务数与提交的总任务数之比。M表示提交的总任务数，Fi=1表示任务Ti在截止期前正常执行完成，Fi=0表示任务Ti在截止前未正常执行完成 (14) (2)截止期前完成价值百分比Vfp，指在截止期前顺利完成的任务的价值总和与提交任务的价值总和之比 (15) (3)任务切换次数，指在整个任务调度过程中，前一个任务未完成而被后一个任务抢占CPU，导致前一个任务被加入到就绪队列中的次数。 图3 截止期前任务完成个数情况变化曲线 图4 截止期前任务完成价值情况变化曲线 由图3和图4所示，当负载较小时，ECMB算法的截止期前完成百分比和完成价值收益百分比，与传统HVF和EDF算法相比，没有明显优势。而当系统负载增高时，由于EDF算法对截止期限比较敏感，后续接入的任务若截止期靠前将会存在大量被抢占情况，致使很多任务在截止期前不能完成，因此EDF算法随着任务负载的加重其性能急剧下降。并且，在仿真结果中ECMB算法获得截止期前完成百分比明显高于EDF算法。这是由于ECMB算法在考虑截止期的同时又考虑了任务本身的重要性，并在任务重要性方面进行了二次判断，所以那些截止期靠前且重要性较高的任务不会被轻易打断。 虽然HVF算法随着负载加重其截止期完成百分比在降低，但是由于其尽可能去完成重要性级别较高的任务，所以其完成价值百分比要高于EDF算法。在完成价值百分比方面，ECMB算法的略高于HVF算法，但ECMB算法有效地降低了任务截止期前的错失率。因此ECMB算法与EDF算法相比，在保证网络整体价值度方面有较大改进。 图5 任务切换次数图示 如图5所示，ECMB算法使得一部分原按照抢占式EDF算法必然会发生抢占的任务，由于调度参数的比较而被拒绝抢占。该算法在减少抢占次数的同时也保证了相对重要的任务能得到优先传送，并且由于任务在被打断后再次被调度时存在上下文切换等开销，而ECMB算法较其它两种算法被打断的次数少，性能更优。 本文在EDF和HVF算法的基础上，提出了ECMB算法。该算法通过提高L2/L3层协议栈进程优先级来尽可能多次的利用CPU清空缓冲区，从而保证用户业务的连续性。由于在清空缓冲区数据时，L2/L3层协议栈进程优先级较高，可能会严重影响系统其它进程的正常运行。因此，本算法在考虑截止期参数的条件下，结合二次判断调度参数，使截止期靠前且关键性又高的任务优先执行，并通过对比仿真验证了该算法的有效性。 [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] 张若文,方韧,李觐,等.无线接入网演进之C-RAN技术[J].电信工程技术与标准化,2012,25(4):79-84. [3] 龙恳,兰莹菲,黎伟.一种C-RAN架构下载波迁移的调度策略[J].重庆邮电大学学报:自然科学版,2015,27(1):1-5. [4] 龙恳,黎伟,兰莹菲,等.C-RAN架构下一种基于分形定理的载波迁移预测算法[J].科学技术与工程,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算法下周期性任务的最小相对截止期计算[J].计算机应用研究,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] 周本海,王溪波,乔建忠,等.基于多参数的μC/OS-Ⅱ任务优先级和调度方法[J].计算机工程,2007,33(21):28-30. [13] 王强,徐俊刚,王宏安,等.一种新的基于优先级表的实时调度算法[J].电子学报,2004,32(2):310-313. [14] 王永炎,王强,王宏安,等.基于优先级表的实时调度算法及其实现[J].软件学报,2004,15(3):360-370. [15] 王强,王宏安,金宏,等.实时系统中的非定期任务调度算法综述[J].计算机研究与发展,2004,41(3):385-392. 欢迎订阅《电子科技》 邮发代号：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)；国家自然科学基金(61501347, 61372067) 汪珊珊(1992-)，女，硕士研究生。研究方向：移动通信和宽带无线通信。高炜委(1992-)，女，硕士研究生。研究方向：移动通信和宽带无线通信。靳玲鸽(1990-)，女，工程师。研究方向：无线通信。李靖(1980-)，男，博士，副教授，硕士生导师。研究方向：无线通信。 10.16180/j.cnki.issn1007-7820.2017.05.004 TN925 A 1007-7820(2017)05-012-042 ECMB算法分析
3 仿真结果及性能分析
4 结束语
