武汉绘芯科技有限公司欢迎您!
10余年经验沉淀展览展示运动控制的专家
全国咨询热线:027-87052087
联系我们
武汉绘芯科技有限公司
电话:027-87052087
手机:13329706647
邮箱:956693667@qq.com
地址:武汉市江夏区藏龙岛谭湖一路8号
联系人:黄先生
您的位置: 滑轨屏|绘芯科技 > 知识库 >
知识库

一个简单的EDF调度仿真器的设计与实现

日期:2016-07-30 10:45:24 来源:未知 点击

一个简单的EDF调度仿真器的设计与实现

 

  综述本课题国内外研究动态,说明选题的依据和意义

1.1本课题国内外研究动态

截止时间优先调度算法简称EDFEarliest Deadline First),是在比率单调调度算法RMSRate-Monotonic Scheduling algorithm)的基础上发展而来。由于RMS属于静态优先级调度算法,在任务比较多的情况下,CPU使用率上限为ln2,即有很低的CPU使用率,所以便提出了EDF算法。

EDF中,任务的优先级根据任务的截止时间确定。任务的绝对截止时间越近,任务的优先级越高;任务的绝对截止时间越远,任务的优先级越低。当有新的任务处于就绪状态时,任务的优先级就有可能进行调整。

在使用EDF算法时,需要几个假设:

a 没有任务有非抢先的区域。

b 只有处理要求是显著的,内存、I/O和别的资源要求都可以忽略。

c 所有任务都是独立的,没有优先约束。

d 任务几何中的所有任务不一定是周期的。

假设a表明,我们可以在任何时间抢占任何任务,此后还可以还原他,这个过程没有损失,一个任务呗抢占的次数不改变处理器的总工作负荷。从b可以得出,为了检查可行性,我们只需要保证足够的处理容量,以在时间期限的要求下执行任务,没有内存或者其他的约束条件而导致问题变得复杂。c则表明不存在优先约束,意味着任务的释放时间不依赖于其他任务的结束时间。但是对于部分系统不满足上述三条假设,则需要采用优先的和排斥的约束解决相应问题。

我们在这几个假设前提下研究EDF算法。在这些前提下,对于周期性的任务,并且对应时间等于它们的周期,那么可以对于任务集进行测试。测试表明:只要任务集的总利用率不大于1,那么任务集就可以由EDF算法在一个单处理器上进行合理的调度。

      最早截止时间优先EDFEarliest DeadlineFirst)算法是非常著名的实时调度算法之一。在每一个新的就绪状态,调度器都是从那些已就绪但还没有完全处理完毕的任务中选择最早截止时间的任务,并将执行该任务所需的资源分配给它。在有新任务到来时,调度器必须立即计算EDF,排出新的定序,即正在运行的任务被剥夺,并且按照新任务的截止时间决定是否调度该新任务。如果新任务的最后期限早于被中断的当前任务,就立即处理新任务。按照EDF算法,被中断任务的处理将在稍后继续进行。

用于EDF的容器打包分配方法:

假设任务集是周期性的、独立的、抢占式的,可是要将任务集分配给一个有相同处理器组成的多处理器。而且任务时间限等于其周期,除了处理器时间,任务不需要任何其他资源。此时,便可以使用EDF的容器打包分配方法。因为已知只要分配给某一处理器的所有任务的利用率之和小于等于1,此任务及集在该处理器上就是EDF调度,以此,问题简化为根据任务特性分配任务,使得每一个处理器上的所有任务利用率之和不超过1。这样就在多处理器中实现了EDF调度算法。

EDF算法的缺点:

虽然基于动态优先级调度的EDF算法拥有显著的优点,但是EDF具有很大的调度开销,此外,在系统出现过载的情况下,EDF算法不能确定哪个任务的截止时间会得不到满足。瞬时过载时,系统行为不可预测,可能发生多米诺骨牌现象,一个任务丢失时会引起一连串的任务接连丢失。

EDF的改造算法:

藉于EDF的缺点,LiuLayland提出了一种混合的调度算法,即大多数任务都采用RMS(比较单调调度算法)进行调度,只有少量任务采用EDF调度算法,尽管混合的调度算法不能达到100%CPU使用率,但确实综合了两种算法的优势,使得整个调度更容易实现。

    

1.2选题的依据和意义

最早期限优先调度算法是基于优先级的动态调度方法,是最优的单处理器调度算法,具有灵活性高,能充分利用CPU计算能力的特点。到后来产生了EDF算法的

优化算法NEDFDPDS,更能较好的平衡CPU使用率,响应时间等问题,随着计算机的发展,多道程序处理的出现需要强大的调度算法来对多任务进行调度,以确定多任务环境下任务的执行顺序以及占有CPU时间。相对于静态,不可抢占的调度方法,EDF的出现使之凭借灵活性高,CPU占有率很快成为最优的单处理器调度算法。

    1.执行时间:以执行时间为依据,执行时间越短,静态。2.任务周期:以任务周期为依据,任务周期越短,静态优先级越高。3.任务的CPU利用率:任务的CPU利用率为任务执行时间与任务周期的比值越高,静态优先级越高。4.任务紧急程度:根据任务的紧急程度,认为安排任务的优先级。任务越紧急,静态优先级越高。

EDF算法是最优的单处理器动态调度算法,其可调度上限为100%。也就是说,如果EDF算法不能够在一个处理器上合理的调度一个任务集,那么其他的调度算法也不能做到。

本课题的设计与开发,是对自已所学知识的检验,是将理论与实际的具体结合。对以后的学习历程具有重要意义

二、研究的基本内容,拟解决的主要问题

2.1研究的基本内容

该项目在理解实时系统的基础上,设计并实现一个使用EDF调度算法的实时系统仿真器。

(1)  根据CPU利用率动态变化的情形,设计一个EDf调度算法

   2  EDF调度算法如何完成调度

 3  完成一个简单的EDF调度算法的实时系统仿真器

2.2拟解决的主要问题

1.如何使用C/C++编程设计调度仿真器

2.如何描绘实时调度的图像

3.通过对国内在EDF算法核心技术方面文献的分析和研究,并在借鉴国外同行新技术的基础上,对所要开发的仿真器结构做了总体的设计:1)仿真的实时性问题。2)通过C/C++完成仿真工具可定制的仿真数据输出。

研究步骤、方法及措施

1.研究步骤

查阅实时系统相关知识以及调研国内外的文献资料,阅读技术方面的材料,对整个项目有一个整体的认识。总共分6个步骤:

1)通过对相关技术和知识的了解学习,对设计该算法的可行性进行分析;

2)找出实施实时调度的工作方式;

3)设计实时系统调度的仿真器;

4)任务调度程序的编写;

5)可定制的仿真数据输出;

6)测试该算法,检验实时任务调度效果.

2. 方法及措施

1)文献综述法

通过中国期刊网和Internet搜索,本人收集并阅读了大量的有关EDF实时系统仿真的研究报道以及有关此方面的研究,为本研究提供了理论基础。

2)资源下载系统内容分析法

参考网上或者书上一些优秀的CPU变化率的实时系统仿真器的编写,对各种页面的布局,整体的项目设计以及技术难点进行分析。

3)系统测试

按测试计划的要求对本系统进行测试,然后撰写该系统的测试分析报告,包括测试计划执行情况、软件需求测试结论、评价等内容。

 

 

 

五、主要参考文献

[1] 罗蕾 .嵌入式实时操作系统及应用开发, 北京航空航天大学出版社 20051

[2] C.M KrishnaKang G.Shin. 实时系统,戴琼海译. 清华大学出版社 20049

[3]董荣胜,赵岭忠,蔡国永,古天龙.基于对象的分布式实时系统调度模型研究.《计算机研究与发展》200211

[4]盛羽,余进,陈松乔,王建新.基于CPU仿真器的汇编语言学习系统设计与实现.中南大学学报(自然科学版)20106期  

[5] 李岩;钟兆君.Linux下改进EDF实时调度算法[J];中国新技术新产品;200905

[6]期刊论文 EDF调度算法的实时性改进 - 广西工学院学报 - 2010, 21(1)

 

 

 

 

 


在线客服
联系方式

热线电话

13329706647

上班时间

周一到周五

公司电话

027-87052087

二维码
线