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

《2023年最早期限优先调度算法EDF实验报告.docx》由会员分享，可在线阅读，更多相关《2023年最早期限优先调度算法EDF实验报告.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验报告实验名称:最初期限优先调度算法(EDF)实验一、实险目的1) 了解实时调度，了解最早截止期优先算法(EDF算法)；2)使用C语言实现最早截止期优先算法(EDF算法)：3)计算多个任务的调度顺序。二、实验原理最早截止期优先算法(EDF),也称为最早死限调度算法(DDS),是种采用动态调度的 优先级调度算法，任务的优先级根据任务的截止时间来拟定。任务的截止时间越近，任务 的优先级越高;任务的截止时间越远，任务额优先级越低。当有新的任务处在就绪状态时， 任务的优先级就有也许需要进行调整。EDF算法的测试假如所有的任务都是周期性的,并且相应的时间限等于它们的周期,对任务集的调度性 的测试是非常

2、简朴的：假如任务集的总运用率不大于1 ,那么任务集就可以由EDF算法在 一个单解决器上进行合理的调度。对于那些任务的时间限并不全等于其周期的情况，没有简 答的调度性测试。在这样的情况下，需要使用EDF算法生成一个时间表，来判断是不是在 一个给定的时间区间内所有的时间限都被满足。在这种情况下EDF的一个可调度性测试如 下：定义u = 2匕L/Pi),dmax = 卷4以及P = lcm(Pl，&)(这里的“1cm”表达最小 公倍数)o定义g(t)是任务集T中所有满足其时间限的绝对值小鱼t的任务执行时间之 和。一个由n个任务构成的集合不是可行的EDF的充足必要条件是：u 1 或存在某个t tp r

3、 i n t f( % d , FS i 0);i f (FSI i 11 = =-1)(pr i nt f ( 0);p rintf ( n);e 1 se(pr i n t f( dn”，FS 皿);)i+；Slcep(100 0 00);（其中n为任务集中任务的数量;6为任务的执行时间;R为周期任务的周期；山为任 务7；的相对时间限;八丁（）为在绝对时间不迟于t的任务集合T中，所有反复的任务执行时 间和。）三、实验仪器硬件:PC机;软件：W ind o w s 7, V i s u a 1 Studio 2 0 2 3 集成开发环境四、实验环节1）理解ED F调度算法的原理并通过实例用E

4、DF算法判断多任务的调度顺序。2）新建EDF. h头文献，在其中定义变量，结构体，函数。3）新建inpu t . c文献,用i n p u t函数从键盘获取多个任务的名称、执行时间、周期 和释放时间,将任务提成一个个时间片存在数组中，并输出数组和各时间片属性。4）新建ed f . c文献,JIJ EDF函数将数组中的时间片根据截止时间的大小从小到大进行排 序，输出它们的截止时间排序，再判断是否可调度，若是不可调度输出“不可调度！”，若 是可调度输出调度顺序。5）新建main. c文献，在其中调用inp u t函数和EDF函数。6）编译运营程序，输入多个任务调试程序至结果无误。7）对实验进行分析

5、、反思,与同学讨论。五、实险结果程序完毕后,输入了多种情况进行验证，运营结果对的，符合按照最早截止期优先算法 得出的结果。1）不可调度当五个任务的执行时间和周期都为1时，是不可调度的。（由EDF算法的测试可知）b nane.Execut ion ( Exocut ion9 nne,Execut ion 2 nAne 9 Execut ion s naneExecut Ionb nane.Execut ion ( Exocut ion9 nne,Execut ion 2 nAne 9 Execut ion s naneExecut Iontine.PeriodReleAce tino*Perio

6、drRolece t irw!,PiiArRl* t inePci*iodFRe lease t ine,Period,Releasetin：l 110 tine：2 110 tiiw：3 1 1 H tine：4 1 1 H tine：5 1102 ）可调度当五个任务的执行时间和周期分别为1、3,2、12, 1、6,1、4, 3、20,释放时间分别为0, 1,0, 1,0时，是可调度的。结果如下：Prosn* s Progi，s ProsrMs Progiums ProgTAfi anane. Execut ion nanc.Execut ion now* Execution none.Ex

7、ecut ion nane.Exccutiont inePeriodr Re lease t ine r Per iod, Re lease t ine. Period Re lease t i ne. Per iod Re lease t inePcriod,Re leasetine：l 1 tine：2 2 tino：3 1 tine：4 1 tine：5 3故至时间排序如下:2。202。12121213121718131324调度顺序如下: 1 3 4 22 51 55 04 01 3 b 0W 01 4 b 0B 01 34 22 0。0 a 04 03 0 0 R实脸分析与讨论1）编

8、程前要理解清楚算法。对算法理解不清就编写代码实现，那么写出来的程序与计算出来的结果会不一致、运营不对的。重新理解算法，调试程序，会导致不必要的时间浪 费。2）实验前一定要做好实验设计。如变量设立，功能语句设计等。否则在编写程序的过 程中容易出现思维逻辑不清楚，无法继续实现必需功能的问题。这样仍然会导致不必要的时间浪费。附：源代码/ED F.h#include int name:#includewindows. hint run;# def i ne n 5i nl per i od;i n t num b er；i n t r eleas e ;in t sc h c iule| 10 0 0

9、) 2 :A 1 000;i n t FS 10 0 0 2 ;v o id Input ();s t ru c t Pro gram vo i d EDF();/ inp u t. c/* * * * * * *输入* * */#i n clu d eEDF. hvoid Input()(/ pro g r am AnJ;char s ;int i.j.k;in t n a mc,run, pc r i o d,r e lea s e;numb e r=0;for( i =0;i5； i+) / * i 是任务个数* /printf(Progr am s n ame, Execu t i o

10、 n t im e ,Peri o d(=D e adline).Rel e ase time：);s canf (%d %d % d % d , &name,&run, & p eriod.& r elease);k=0;while(k5)/* k 是周期数*/(f or( j = 0 j r u n ； j +)(A|n u mber . n ame=nam e ;A(n u mb e r.run=l;A num b cr.pc r iod= period;A numbe r . release=re! e as e +k * period;n u mbe r +;If f 1 ush(s

11、tdin) ; /*清空缓冲区*/k+；)p r int f (n);p rint f (What you in p ut is: n );fo r ( i =0;in u mb e r ;i+ + ) p r intf( %dt%dt%dt% d . n am e ,A(i. ru n ,Ai .period, A( i .rele a se); pri n tf( n )：/main.c/*E D F算法实现-C语言，结构体*/include EDF.h v o id Inpul();i n t m a i n ()(I n p u t ()：EDF ();return 0 ;)/EDF核

12、心算法v oid ED F() struct Prog r am m;i n t i,int sum;i n t fl a g;排序for ( i = 0;inumbe r ： i +)(k= i ;for (j = i ； j n ame = a-name;b -run = a-run;b-pcriod = a-per i od;b- r e I e ase=are 1 e ase：ret u r n;if(A| j J. p eri o d+Aj. r e 1 ease Ak.p e rio d + A k . r eleas e )copy(&m,&A k);copy(&Ak ,&A i

13、 );copy)P r i n t f(截至时间排序如下n);for(i = 0; i number： i+)name, A i . r u n,A i .p e r iod. Aname, A i . r u n,A i .p e r iod. Aprint f (%dl%d t %d t%dn,A i.ij.rclc a s c)：)p rint f ( * * * * n-/ /判断s uni = 0 ；f lag=0;ibr(i=0;i n umb e r+1 ;i+)(FS i 0=-l;FSi (1= 1;)for(i=0;inumbe r ; i +)j=Ai.release:w

14、hiie(jA i . r el e ase+A i. p er i o d )(f lag=l;)b reak：)el s e i f (FSjO =A(i. n ame)elseFS| j J l=Ali.na me：if( j =Ai.release+A i j.perio d | I j A i .ease+A ij. period)flag=l：break;J +；i f (fl a g= 1 )(P rintf(不可调度！ n );)else(prin t f (调度顺序如下n);i =0 ：while(i A num be r - I . p eriod+Anumbe r -1 . r ele a s e)i f(FSi 0 =-1)P rint f ( 0 );else