一种动态优先级实时任务调度算法

《一种动态优先级实时任务调度算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３５卷第１２期计算机学报Ｖｏｌ．３５Ｎｏ．１２２０１２年１２月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＤｅｃ．２０１２一种动态优先级实时任务调度算法夏家莉１）陈辉１）杨兵２）１）（江西财经大学软件与通信工程学院南昌３３００１３）２）（湖北大学教育学院武汉４３００６２）摘要现有实时任务调度算法往往根据任务的时间属性或者价值确定任务优先级，较少同时兼顾任务的价值和执行紧迫性．文中根据任务的价值和剩余执行时间讨论任务的剩余价值密度，根据任务的截止期和空余执行时间分析任务的紧迫性；然后综合任务的剩余价值密度和执行紧迫性，提出了动态分派任务优先级的ＤＰＡ

2、策略；最后提出了基于ＤＰＡ的抢占调度算法ＤＲＴＰ．ＤＲＴＰ算法分析了任务抢占调度的各种可能条件，分析了系统中可能出现的颠簸调度，并给出避免颠簸的条件．仿真实验结果显示，与其它同类算法相比，ＤＲＴＰ算法能够提高系统价值收益，降低任务截止期错失率，并大大减少任务抢占的次数．关键词实时任务；剩余价值密度；执行紧迫性；动态优先级分派中图法分类号ＴＰ３１６犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１２．０２６８５犃犚犲犪犾犜犻犿犲犜犪狊犽狊犛犮犺犲犱狌犾犻狀犵犃犾犵狅狉犻狋犺犿犅犪狊犲犱狅狀犇狔狀犪犿犻犮犘狉犻狅狉犻狋狔ＸＩＡＪｉａＬｉ１）ＣＨＥＮＨｕｉ

3、１）ＹＡＮＧＢｉｎｇ２）１）（犛犮犺狅狅犾狅犳犛狅犳狋狑犪狉犲犪狀犱犆狅犿犿狌狀犻犮犪狋犻狅狀犈狀犵犻狀犲犲狉犻狀犵，犑犻犪狀犵狓犻犝狀犻狏犲狉狊犻狋狔狅犳犉犻狀犪狀犮犲犪狀犱犈犮狅狀狅犿犻犮，犖犪狀犮犺犪狀犵３３００１３）２）（犛犮犺狅狅犾狅犳犈犱狌犮犪狋犻狅狀，犎狌犫犲犻犝狀犻狏犲狉狊犻狋狔，犠狌犺犪狀４３００６２）犃犫狊狋狉犪犮狋Ｍｏｓｔｏｆｔｈｅｅｘｉｓｔｉｎｇｒｅａｌｔｉｍｅｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｓａｓｓｉｇｎｔｈｅｐｒｉｏｒｉｔｉｅｓｏｆｔａｓｋｓａｃｃｏｒｄｉｎｇｔｏｔａｓｋｓ’ｔｉｍｅａｎｄｖａｌｕｅ，ｂｕｔｆｅｗｏｆｔ

4、ｈｅｍｃａｎｓｙｎｃｈｒｏｎｏｕｓｌｙｃｏｎｓｉｄｅｒｔｈｅｖａｌｕｅａｎｄｕｒｇｅｎｃｙｏｆａｔａｓｋ．Ｉｎｔｈｉｓｐａｐｅｒ，ｆｏｒａｒｅａｌｔｉｍｅｔａｓｋ，ｗｅｆｉｒｓｔｌｙｄｉｓｃｕｓｓｉｔｓｄｙｎａｍｉｃｖａｌｕｅｄｅｎｓｉｔｙａｃｃｏｒｄｉｎｇｔｏｉｔｓｖａｌｕｅａｎｄｒｅｍａｉｎｄｅｒｅｘｅｃｕｔｉｏｎｔｉｍｅ，ａｎｄａｎａｌｙｚｅｉｔｓｅｘｅｃｕｔｉｏｎｕｒｇｅｎｃｙｂｙｃｏｎｓｉｄｅｒｉｎｇｉｔｓｄｅａｄｌｉｎｅａｎｄｓｐａｒｅｔｉｍｅ．Ｂａｓｅｄｏｎｔｈｅｄｙｎａｍｉｃｖａｌｕｅｄｅｎｓｉｔｉｅｓａｎｄｅｘｅｃｕｔｉｏｎｕｒｇｅ

5、ｎｃｉｅｓｏｆｔｈｅｒｅａｌｔｉｍｅｔａｓｋｓ，ｗｅｐｒｏｐｏｓｅａｓｔｒａｔｅｇｙｎａｍｅｄＤＰＡｔｏｄｙｎａｍｉｃａｌｌｙａｓｓｉｇｎｔｈｅｐｒｉｏｒｉｔｉｅｓｏｆｔｈｅｒｅａｌｔｉｍｅｔａｓｋｓ．Ａｄｄｉｔｉｏｎａｌｌｙ，ｗｅａｌｓｏｐｒｅｓｅｎｔａＤＰＡｂａｓｅｄｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｎａｍｅｄＤＴＲＰ．Ｆｏｒｔｈｅａｌｇｏｒｉｔｈｍ，ｗｅａｎａｌｙｚｅａｌｌｔｈｅｓｉｔｕａｔｉｏｎｓｏｆｐｒｅｅｍｐｔｉｖｅｓｃｈｅｄｕｌｉｎｇ，ｄｉｓｃｕｓｓｔｈｅｔｈｒａｓｈｉｎｇａｎｄｔｈｅｃｏｎｄｉｔｉｏｎｏｆａｖｏｉｄｉｎｇｔｈｅｔｈ

6、ｒａｓｈｉｎｇ．ＴｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅＤＲＴＰａｌｇｏｒｉｔｈｍｉｓｐｒｉｏｒｔｏｏｔｈｅｒａｎａｌｏｇｏｕｓａｌｇｏｒｉｔｈｍｓｏｎｔｈｅａｃｃｒｕａｌｖａｌｕｅｏｆｒｅａｌｔｉｍｅｓｙｓｔｅｍ，ｔｈｅｄｅａｄｌｉｎｅｍｉｓｓｒａｔｉｏａｎｄｔｈｅｐｒｅｅｍｐｔｉｖｅｎｕｍｂｅｒ．犓犲狔狑狅狉犱狊ｒｅａｌｔｉｍｅｔａｓｋ；ｒｅｍａｉｎｄｅｒｖａｌｕｅｄｅｎｓｉｔｙ；ｅｘｅｃｕｔｉｏｎｕｒｇｅｎｃｙ；ｄｙｎａｍｉｃｐｒｉｏｒｉｔｙａｓｓｉｇｎｍｅｎｔ制［１２］、工业控制［３］、柔性制造网络控制［４］、机

7、器人智１引言能控制［５］、无线传感器网络［６８］、云计算［９］、多处理器下多媒体流调度［１０］以及嵌入式智能设备［１１］中．实时最近几年，实时任务系统广泛应用到航天控任务系统是用来处理有定时限制工作负载的任务处收稿日期：２００８１１０８．本课题得到国家自然科学基金（６０７６３００２，６０８６３０１６）、江西省自然科学基金（２００８ＧＺＳ００２１）、湖北省教育厅科学技术研究计划优秀中青年人才项目资助．夏家莉，女，１９６５年生，博士，教授，博士生导师，主要研究领域为实时系统、实时数据库系统、软件工程．陈辉，男，１９７６年生，博士，副教授，主要研究方向为实

8、时数据库系统、数据挖掘技术．Ｅｍａｉｌ：ｃｏｍｄｏｃ＠１２６．ｃ