论文部分内容阅读
EDF是1973年由海外学者提出的一个实时调度算法,作为一个经典算法,它出现在很多的实时系统教材中,至今尽管己跨越了数十年的历史,但关于EDF的动态性能方面,仍有许多问题有待解决。实时领域著名学者Buttazzo早在2002年的时候就给出了一个弹性调度模型。经过众多海内外学者对它不断的改进和补充,研究成果可以说是十分丰硕。但直至今日,该模型依然没有完善,尤其是关于任务的选择性压缩方向还有许多值得我们进行深入研究的地方。本文正是在这个研究背景的基础上对EDF动态模型中的任务选择性压缩方向进行的再深入探究。提出了最晚截止期压缩算法(Latest Deadline First,简称LDF). LDF算法是一种基于任务截止期的算法,通过比较所有受压的任务的截止期,找出具有最晚截止期的那个受压任务进行压缩。在超过80%的情况下LDF算法只需1-2次的比较就能实现新任务的最快插入。考虑到单靠压缩单个任务出让的带宽毕竟有限,文章同时又对多个任务联合压缩的问题进行了探讨。很显然,单靠压缩现有任务出让的即时带宽终归是有限的,所以我们对新任务的插入方式也做了一定的研究。考虑到很多场景下新任务是弹性任务,本文提出了一个专门针对弹性任务的新任务分步插入策略(Part Utilization First,简称PUF). PUF的具体做法就是当系统出让的即时带宽不足以让新任务以最小周期插入时,就让新任务先以最大周期插入系统运行,等到过了被压缩任务的截止期后再让新任务全速运行,它能实现弹性任务的更早插入。本文在PUF的基础上还提出了3种基于多任务的分步插入的策略,即最低需求策略,平均需求策略,优先需求策略。通过结合使用LDF算法和PUF算法,能够实现新任务的最早插入。为了更好地验证文中提出的LDF算法和PUF算法,在文章的最后我们在仿真工具Switchsim上对它们进行了仿真。通过在Switchsim下模拟LDF算法,PUF算法,以及3种多任务分步插入策略的具体调度效果,更好的说明了本文研究成果的意义。