EDF调度算法的实时性改进.pdfVIP

第21卷 第 1期 广 西工 学 院学 报 2010年3月 JOl瓜NAI．OFGUANGXIUNIVERSITYOFTECHNOLOGY V0l1．21No．1 Mar．2O1O 文章编号 i004-6410(2010)01．0o82．o4 EDF调度算法的实时性改进 余祖峰 ，蔡启先b，刘 明 (广西工学院a．电子信息与控制工程系；b．计算机工程系，广西柳州 545006) 摘 要：在实时调度算法中，常用的EDF调度算法是非抢占式的，针对这个问题，研究应用 SLAD算法和I~ACK． SLASH算法来改善EDF调度算法的实时性．对过载情况下的截止期错失率DMR的测试，结果表明其实时性确有所 改进． 关 键 词 ：实时调度算法；EDF算法 ；SLAD算法 ；BACKSLASH算法；截止期错失率 中图分类号 ：TP316 文献标志码：A 0 引言 嵌入式实时操作系统要求计算机能及时响应外部事件的请求，在规定时间内完成对该事件的处理，并控 制所有实时设备和实时任务协调一致地工作．应用软件方法实现实时控制的途径主要是对任务进程进行调 度[川．常用的进程调度算法主要有EDF(EarliestDeadlineFi)算法．该算法虽然有一定的动态适应性，但存 在一些进程错过截止期的问题．本文通过引进新近提出的SLAD算法和BACKSLASH算法，分析了这两种 算法对EDF算法的改进，并通过实测给以证实． 1 EDF调度算法及其不足 EDF算法是动态调度算法，根据任务的绝对时限来确定优先级．任务调度优先级定义为：d(t)一t，其 中d(￡)是任务时限，t是当前时间，两者的差值就表示任务的紧迫程度．任务的绝对时限越早，任务的优先 级也就越高，优先级最低的进程是距离最后期限最远的进程．这种调度优先级定义方式，表明在每个时刻，都 要计算下个时刻系统中哪个任务的时限最小，从而决定了系统在下个时刻应该调度哪个任务．系统下个时刻 调度任务的不确定性，使得系统的适应性比较好．此类算法根据任务的资源需求动态地分配任务的优先级， 目的就是在资源分配和调度时有更大的灵活性22【J． EDF的缺点在于，如果一个实时任务在分配的执行时间之前完成本周期内的工作 ，则在这个空闲时间 内其它实时任务也不能运行，CPU将处于相对空闲状态(可能执行非实时任务，可能空闲)；如果一个实时任 务超出了自己的执行时间，工作没有结束，则将保持当前的高优先级继续执行下去，这样就会顺延本来已经 安排的后续任务，形成 “多米诺”效应，造成多个任务超出截止时间33【J，在实际情况中会出现不能解决过载问 题的情况，并且发生过载时，导致CPU时间大量花费在调度上，性能退化很快，不能满足系统的实时性要 求[4I． 2 ISM 改进算法 2．1 ISM 思路 针对DEF调度算法出现的问题，在后来的关于此项算法的研究中出现了许多不同的改进思路，其中一 收稿 臼期：2010—01一l3 基金项 目：广西教育厅科技项 目(200708LX183)资助． 通信作者：蔡启先，研究方向：计算机系统结构研究，E—mail：eqx．gx@163．oom 第 1期 余祖峰等：EDF调度算法的实时性改进 种就是隔离服务法 ISM(IsolationServerMethod)[引．ISM 的思路是将实时任务分别分配到几个同级别服务 级(server)，各个sen，er按照一定比例分配CPU，如果某个servre上的实时任务overrun(超限)3【J继续运行下 去，则 占用该server的CPU，并顺延该esrver上的其它实时任务．这种策略不考虑任务间的影响，对减小截止 期错失率DMRt](deadlinemissratio)有一定效果． 2．2 SIA1)算法和BACKSLASH算法 SLAD(sLACKDonation)算法和BACKSLASH(BACKSLACKDonation)算法[51是最近由Lin和Brandt 提出的算法，是基于ISM方法的改进算法．这两种算法主要在于改进EDF对空闲时间(slacktime)的利用来 减小DMR，该