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

实验报告实验名称:最初期限优先调度算法(EDF)实验一、实险目的1) 了解实时调度，了解最早截止期优先算法(EDF算法)；2)使用C语言实现最早截止期优先算法(EDF算法)：3)计算多个任务的调度顺序。二、实验原理最早截止期优先算法(EDF),也称为最早死限调度算法(DDS),是种采用动态调度的 优先级调度算法，任务的优先级根据任务的截止时间来拟定。任务的截止时间越近，任务 的优先级越高;任务的截止时间越远，任务额优先级越低。当有新的任务处在就绪状态时， 任务的优先级就有也许需要进行调整。EDF算法的测试假如所有的任务都是周期性的,并且相应的时间限等于它们的周期,对任务集的调度性 的测试是非常简朴的：假如任务集的总运用率不大于1 ,那么任务集就可以由EDF算法在 一个单解决器上进行合理的调度。对于那些任务的时间限并不全等于其周期的情况，没有简 答的调度性测试。在这样的情况下，需要使用EDF算法生成一个时间表，来判断是不是在 一个给定的时间区间内所有的时间限都被满足。在这种情况下EDF的一个可调度性测试如 下：定义u = 2匕L®/Pi),dmax = £卷4以及P = lcm(Pl，&)(这里的“1cm”表达最小 公倍数)o定义g(t)是任务集T中所有满足其时间限的绝对值小鱼t的任务执行时间之 和。一个由n个任务构成的集合不是可行的EDF的充足必要条件是：u > 1 或存在某个t < minP + dmax,- maxPf - 4使得九7 > tp r 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调度算法的原理并通过实例用EDF算法判断多任务的调度顺序。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）对实验进行分析、反思,与同学讨论。五、实险结果程序完毕后,输入了多种情况进行验证，运营结果对的，符合按照最早截止期优先算法 得出的结果。1）不可调度当五个任务的执行时间和周期都为1时，是不可调度的。（由EDF算法的测试可知）b nane.Execut ion ( Exocut ion9 n«ne,Execut ion 2 nAne 9 Execut ion s nane»Execut Ionb nane.Execut ion ( Exocut ion9 n«ne,Execut ion 2 nAne 9 Execut ion s nane»Execut Iontine.Period<-Deadline>ReleAce tino*Period<-Deadline>rRole«ce t irw!,P<rlodC«I>iiA<!lifi«>rR«l«*«« t ine«Pci*iod<*Dcadline>FRe lease t ine,Period<Deadline>,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 ProsrM's Progium's ProgTAfi' anane. Execut ion nanc.Execut ion now* Execution none.Execut ion nane.Exccutiont ine»Period<-Dead 1 ine >r Re lease t ine r Per iod< «-1><: ad line >, Re lease t ine. Period<-Deadline> Re lease t i ne. Per iod<-Dead 1 ine >» Re lease t inePcriod<-Deadlinc>,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）编程前要理解清楚算法。对算法理解不清就编写代码实现，那么写出来的程序与计算出来的结果会不一致、运营不对的。重新理解算法，调试程序，会导致不必要的时间浪 费。2）实验前一定要做好实验设计。如变量设立，功能语句设计等。否则在编写程序的过 程中容易出现思维逻辑不清楚，无法继续实现必需功能的问题。这样仍然会导致不必要的时间浪费。附：源代码/ED F.h#include < s tdio.h>int name:#includewindows. h>int 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) 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 e"EDF. h"void 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;i<5； i+) / * i 是任务个数* /printf("Progr am' s n ame, Execu t i o 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(k<5)/* 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(stdin) ; /*清空缓冲区*/k+；)p r int f ("n");p rint f ("What you in p ut is: n ");fo r ( i =0;i<n 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核心算法v oid ED F() struct Prog r am m;i n t i,int sum;i n t fl a g;排序for ( i = 0;i<numbe r ： i +)(k= i ;for (j = i ； j < number;j+)/e d f.c#in c 1 ude'EDF.h"void copy(str u c t Progra m * b,structProgram* a) b-> n ame = a->name;b ->run = a->run;b->pcriod = a->per i od;b-> r e I e ase=a>re 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 );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;i<numbe r ; i +)j=Ai.release:whiie(j< n umber)i f(FS j 1! =-l )e 1 se (i f(FS j 0 =-l)F S j 0=Ai . name；if(j=Ai.r e lease+ A i. pe r iod I | j >A 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