基于贪心策略的EDF调度算法优化  

Optimization of EDF Scheduling Algorithm Based on Greedy Policy

作　　者：桑磊[1] 陆阳[1,2] 俞磊[3] 

机构地区：[1]合肥工业大学计算机与信息学院,合肥230009 [2]安徽省矿山物联网与安全监控技术重点实验室,合肥230088 [3]安徽中医药大学医药信息工程学院,合肥230012

出　　处：《计算机工程》2015年第12期96-100,共5页Computer Engineering

基　　金：国家"863"计划基金资助项目(2011AA060400);国家国际科技合作专项基金资助项目(2014DFB10060);教育部高等学校博士点基金资助项目(20120111110001);情感计算与先进智能机器安徽省重点实验室开放基金资助项目(ACAIM150101)

摘　　要：最早截止期优先(EDF)调度算法在系统过载的情况下会产生"多米诺效应",导致无法满足多数任务的实时性要求。针对该问题,提出一种基于贪心策略的最优调度集选择方法。通过引入一个表示任务价值的因子与任务的截止时间共同决定任务的优先级,当系统过载时,在EDF算法的可调度范围内选取重要任务作为优先调度对象。理论性能分析和实验结果表明,该算法不仅能在过载时降低实时系统的任务截止期错失率,而且能保证关键任务的优先调度。The Earliest Deadline First（EDF）scheduling algorithm has＂Domino effect＂when the system overloads causing most tasks＇ real time requirement can not be satisfied.Aiming at this problem,this paper proposes an algorithm of optimal scheduling set selecting based on greedy policy.Using a factor which reflects the value of task and deadline to decide the priority of task,it selects important task to schedule when system overloads.Theoretical performance analysis and experimental result show that the proposed algorithm can reduce Deadline Missing Ratio（DMR）and guarantee the key tasks to be scheduled firstly.

关 键 词：实时操作系统 调度算法 最早截止期优先调度 贪心策略 优先级 截止期错失率 

分 类 号：TP316.2[自动化与计算机技术—计算机软件与理论]