2023年最早期限优先调度算法EDF实验报告.pdf

实验报告实验名称:最初期限优先调度算法(EDF)实验一、实险目的1)了解实时调度，了解最早截止期优先算法(EDF算法)；2)使用C语言实现最早截止期优先算法(EDF算法)：3)计算多个任务的调度顺序。二、实验原理最早截止期优先算法(EDF),也称为最早死限调度算法(DDS),是•种采用动态调度的优先级调度算法，任务的优先级根据任务的截止时间来拟定。任务的截止时间越近，任务的优先级越高;任务的截止时间越远，任务额优先级越低。当有新的任务处在就绪状态时，任务的优先级就有也许需要进行调整。EDF算法的测试假如所有的任务都是周期性的,并且相应的时间限等于它们的周期,对任务集的调度性的测试是非常简朴的：假如任务集的总运用率不大于1,那么任务集就可以由EDF算法在一个单解决器上进行合理的调度。对于那些任务的时间限并不全等于其周期的情况，没有简答的调度性测试。在这样的情况下，需要使用EDF算法生成一个时间表，来判断是不是在一个给定的时间区间内所有的时间限都被满足。在这种情况下EDF的一个可调度性测试如下：定义u=2匕®/Pi),dmax=£卷{4}以及P=lcm(Pl，…&)(这里的“1cm”表达最小公倍L数)o定义g(t)是任务集T中所有满足其时间限的绝对值小鱼t的任务执行时间之和。一个由n个任务构成的集合不是可行的EDF的充足必要条件是：u>1或存在某个t<min{P+d,-^-max{P-4}}使得九7⑴>tprintf("%maxfd",FS[i][0]);if(FSIi][11==-1)(printf("0");printf("\n");}e1se(printf("％d\n”，FS皿]]);)i++；Slcep(100000);（其中n为任务集中任务的数量;6为任务£的执行时间;R为周期任务的周期；山为任务7；•的相对时间限;八丁（£）为在绝对时间不迟于t的任务集合T中，所有反复的任务执行时间和。）三、实验仪器硬件:PC机;软件：Windows7,Visua1Studio2023集成开发环境四、实验环节1）理解EDF调度算法的原理并通过实例用EDF算法判断多任务的调度顺序。2）新建EDF.h头文献，在其中定义变量，结构体，函数。3）新建input.c文献,用input函数从键盘获取多个任务的名称、执行时间、周期和释放时间,将任务提成一个个时间片存在数组中，并输出数组和各时间片属性。4）新建edf.c文献,JIJEDF函数将数组中的时间片根据截止时间的大小从小到大进行排序，输出它们的截止时间排序，再判断是否可调度，若是不可调度输出“不可调度！”，若是可调度输出调度顺序。5）新建main.c文献，在其中调用input函数和EDF函数。6）运营程序，输入多个任务调试程序至结果无误。7）对实验进行分析、反思,与同学讨论。五、实险结果程序完毕后,输入了多种情况进行验证，运营结果对的，符合按照最早截止期优先算法得出的结果。1）不可调度Bnane.Execution(•Exocution9n«ne,Execution2nAne9Executionsnane»ExecutIon当五个任务的执行时间和周期都为1时，是不可调度的。（由EDF算法的测试可知）Bnane.Executiontine.Period<-Deadline>•ReleAcetin©：l110(•Exocutiontino*Period<-Deadline>rRole«cettine：2110tiiw：：9n«ne,Execution2irw!,P<rlodC«I>iiA<!lifi«>rR«l«*««t311Htine411ine«Pci*iod<*Dcadline>Releaset：nAne9ExecutionsFHtine5110nane»ExecutIonine,Period<•Deadline>,Release2）可调度当五个任务的执行时间和周期分别为1、3,2、12,1、6,1、4,3、20,释放时间分别为0,1,0,1,0时，是可调度的。结果如下：：Prosn****'snane.Executiontine»Period<-Dead1ine>rReleasetinerPertinel1故至时间排序如下:Progi"，snanc.Executionnow*iod<«-1><:adline>,Releasetine.Period<-tine：22ProsrM'sExecutionDeadline>•Releasetine.Period<-Dead1tino：31Progium'snone.Executionine>»Releasetine^Pcriod<-Deadlinc>,Retine：41ProgTAfi'anane.Exccutionleasetine：531213