论文研究-能够提供QoS保证的固定优先级调度.pdf

所需积分/C币:10 2019-09-12 16:19:35 519KB .PDF
5
收藏 收藏
举报

弱硬实时应用要求调度算法必须确保提供满足其弱硬实时QoS(Quality of Service)参数要求的服务,一种新的能够提供(m,k)-firm保证的固定优先级调度算法被提出,该算法能够根据任务的周期以及所要求的QoS参数进行调度优先级的设定,并通过将任务设置为抢占和可选来反映其紧迫程度。文中给出该算法的可调度判定不等式,并且通过对经典任务集的调度结果,验证了算法的有效性和灵活性。
2009,45(14) Computer Engineering and Applications计算机工程与应用 强制或可选,如果任务的到达序号符合公式(1),则将其设置为确保满足其弱硬实吋QoS参数的要求。而按照本调度方法进 强制,否则设置为可选。同时,该算法为了确保强制任务满足截行优先级设置则不然,如图3(b)所示,任务r1和r2抢占任务 至期要求,基于RM调度策略分配优先级,假定T≤T2≤…≤的执行都满足了其弱硬实时QoS参数的要求。由此可见本算 T,设置r的强制任务的优先级为i,其中n为系统中任务总数,法的灵活性。 1为最高优先级。将所有可选任务的优先级设置为最低的n+1 (1) h 6 例1假设在一个实时系统中有如下T1、T2、73组成的任务 (a)文献8算法 集,其中 r1:1(0,1)3(1,2)1(0,1)3(1,2)1(0,1)3(1,2)1(0,1)3(1,2) 2:2(0,1)2(0,2)1(0,1)2(0,2)1(0,1)20,2)2(0,1)2(0,2) T1=(1,3,(1,1));72=(2,4,(2,3));7=(3,12,(3,5) 文献8中的算法如下设置示例1中的任务:由于r1的弱硬实 时Q0S参数为(1,1),因此r1的每次请求都是强制的;任务r2的 3 7 每三次请求中就有一次为可选;对于τ3时刻0,12,36,60 (b)本文算法 72,96…到达的请求被设置为强制,而在时刻24,48,84,108 图3例2的调度序列 到达的请求设置为可选。然后该算法采用RM调度算法分配调 例2假设在一个实时应用中有如下周期任务r1和r2,其中: 度优先级。由于T<T2<T3,则分别设置三个周期任务强制任务 T1=(1,1,(1,2)),T2=(1,1,(1,2) 的调度优先级为:P=1,P=2,P3=3;设置所有可选任务的优先级 为4。于是对于上例得到如图1所示一个超周期60内强制任5结论 务的执行序列。 首先定义了弱硬实时系统的周期任务模型,然后提出了 R多RBR、R、R1R1、R,R, R, R RIR 种基于RM调度策略的固定优先级分配算法,该算法首先根据 013467 1011121315161819212223 可调度判定不等式,对能否为所有任务提供满足其弱硬实时 R多R多影多R 多R多RR3RR QoS参数的服务进行判断,并根据任务的周期和弱硬实时QoS 232425272830313334 39404243454647 参数设置其调度优先级。本调度算法在调度的过程中,将任务 Rb多R影RR 47484951525455575860 在抢占和可选之间切换,以反映任务的紧迫程度。最后,本文的 图1例1调度序列1 示例分析说明了本算法的有效性和灵活性。 从图1可以看出,采用文献[8的固定优先级设置方法,在 参考文献: 个超周期內,所有周期任务的强制任务都能够满足截至期的 要求,从而达到了弱硬实时QoS参数的要求 [1 Gendy M A E, Bose A, Shin K G. Evolution of the Internet Qos and support for soft real-time applications J). Proceeding of IEEE 若采用本调度算法对该任务集进行调度,由于T×k1<T2 2003,91(7):1086-1104 k2<Txk3,因此分别设置r1,r2和r3抢占任务的优先级为1,2和 [2 Buttazzo G, Spur M, Sensini FValue vs deadline scheduling in 3,将所有可选任务的优先级设置为4,得到一个超周期内如图 overload condictions[C/Proceedings of 16th IEEE Real-Time Sys- 2所示的调度序列,其中调度序列的上方给出任务每次到达时 tems Symposium. Pisa: IEEE Computer Society Press, 1995: 90-99 系统分配的优先级以及当前任务窗口内的执行情况统计。 3 Koren G, Shasha D Skip-over: Algorithms and complexity for over T1:1(0,1)1(0,1)1(0,1)1(0,1)1(0,1)1(0,1)1(0,1)1(0,1) loaded system that allows skips[ C/proceedings of Real-Time Sys r2:2(0,1)2(1,2)4(2,3)2(0,1)2(1,2)4(2,3) tems Symposium. Pisa: IEEE Computer Society Press, 1995: 110-117 3(0,1) 3 [4] Hamdaoui M, Ramanathan P a dynamic prioirty assignment thech 爹1缓1图口影1 0123456789101112131415161718192021222324 nique for streams with(m, k)-firm deadlines[J].IEEE Transactions T1:1(0,1)1(0,1)1(0,1)1(0,1)1(0,1)1(0,1)1(0,1)1(0,1) on Computers,1995,44(4):1443-1451 72:2(0,1)2(1,2)4(2,3)2(0,1)2(1,2)4(2,3) 5] Bernat GSpecification and analysis of weakly hard real-time 1多1缓131日1多1多①1 tems[D].Spain: Universitat de les Illes Balears, 1998 2425 2627282930313233343536 42 43 44 45 46 47 48[6]Bernat G, Burns A, Liamosi A Weakly hard real -time systems JI 丌1:1(0,1)1(0,1)1(0,1)1(0,1) IEEE Transactions on Coumputers, 2001, 50(4): 308-321 72:2(0,1)2(1,2)4(2,3) 7:4(3,5) [7 West R, Zhang Y T, Schwan K, et al. Dynamic window-constrained scheduling of real-time streams in media servers[J.IEEE Transac- 48495051525354555657585960 tions on Computers, 2004, 53(6): 744-759 图2例1的调度厅列2 8 Ramanathan P Overload management in real-time control applica- 从图2可以看出,采用本算法设置任务的优先级,在一个 tions using(m, k)-firm guarantee[J].IEEE Transaction on Parallel 超周期内,所有任务执行情况都达到了弱硬实时QoS参数的要 and Distributed Systems(Special Issue on Dependable Real-time ),1999,10(6):549-5 求,同时任务执行的u- pattern并不是预先设定,而是在系统运 [9] Quan G, Hu X B. Ehnaneed fixed-priority seheduling with(m,h 行过程中动态产生的。 irm guarantee(Cy/Proceedings of 2 lst IEEE Real-Time System Sym 而对于如下所示例2,若采用文献[8中的优先级设置方 posium. Florida: IEEE Computer Society Press, 2000: 79-88 法,如图3(a)所示,很显然由于在0时刻处于紧急临界状态,72[10 Liu w s.Real- time systems[ M, Beijing: Higher education press 的强制任务无法保证满足截止期要求,因此,τ2的执行情况无法 2002:152-156

...展开详情
试读 3P 论文研究-能够提供QoS保证的固定优先级调度.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_38743506 你的留言是对我莫大的支持
2019-09-12
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

    成功上传501个资源即可获取
关注 私信
上传资源赚积分or赚钱
    最新推荐
    论文研究-能够提供QoS保证的固定优先级调度.pdf 10积分/C币 立即下载
    1/3
    论文研究-能够提供QoS保证的固定优先级调度.pdf第1页

    试读结束, 可继续阅读

    10积分/C币 立即下载 >