最早期限优先调度算法(EDF)实验报告

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

2、常简单的：如果任务集的总利用率不大于1，那么任务集就可以由EDF算法在一个单处理器上进行合理的调度。对于那些任务的时间限并不全等于其周期的情况，没有简答的调度性测试。在这样的情况下，需要使用EDF算法生成一个时间表，来判断是不是在一个给定的时间区间内所有的时间限都被满足。在这种情况下EDF的一个可调度性测试如下：定义u=i=1n(ei/Pi)，dmax=max1indi以及P=lcm(P1,Pn)（这里的“lcm”表示最小公倍数）。定义hT(t)是任务集T中所有满足其时间限的绝对值小鱼t的任务执行时间之和。一个由n个任务构成的集合不是可行的EDF的充分必要条件是：u>1或存在某个t<

3、;minP+dmax,u1-umax1inPi-di 使得hTt>t（其中n为任务集中任务的数量；ei为任务Ti的执行时间；Pi为周期任务的周期；di为任务Ti的相对时间限；hTt为在绝对时间不迟于t的任务集合T中，所有重复的任务执行时间和。）三、 实验仪器硬件：PC机；软件：Windows7，Visual Studio 2010集成开发环境四、 实验步骤1） 理解EDF调度算法的原理并通过实例用EDF算法判断多任务的调度顺序。2） 新建EDF.h 头文件，在其中定义变量，结构体，函数。3） 新建input.c文件，用input函数从键盘获取多个任务的名称、执行时间、周期和释放时间，将任

4、务分成一个个时间片存在数组中，并输出数组和各时间片属性。4） 新建edf.c文件，用EDF函数将数组中的时间片根据截止时间的大小从小到大进行排序，输出它们的截止时间排序，再判断是否可调度，若是不可调度输出“不可调度！”，若是可调度输出调度顺序。5） 新建main.c文件，在其中调用input函数和EDF函数。6） 编译运行程序，输入多个任务调试程序至结果无误。7） 对实验进行分析、反思，与同学讨论。五、 实验结果程序完成后，输入了多种情况进行验证，运行结果正确，符合按照最早截止期优先算法得出的结果。1） 不可调度当五个任务的执行时间和周期都为1时，是不可调度的。（由EDF算法的测试可知）2）可

5、调度当五个任务的执行时间和周期分别为1、3，2、12，1、6，1、4，3、20，释放时间分别为0,1,0,1,0时，是可调度的。结果如下：六、 实验分析与讨论1）编程前要理解清楚算法。对算法理解不清就编写代码实现，那么写出来的程序与计算出来的结果会不一致、运行不正确。重新理解算法，调试程序，会造成不必要的时间浪费。2）实验前一定要做好实验设计。如变量设置，功能语句设计等。否则在编写程序的过程中容易出现思维逻辑不清晰，无法继续实现必需功能的问题。这样仍然会造成不必要的时间浪费。附：源代码/EDF.h#include <stdio.h>#include <windows.h>

6、;#define n 5int number;int schedule10002;int FS10002;struct Programint name;int run;int period;int release;A1000;void Input();void EDF();/input.c/*输入*/#include"EDF.h"void Input()/ program An;char s;int i,j,k;int name,run,period,release;number=0;for(i=0;i<5;i+)/*i是任务个数*/   

7、;             printf( "Program's name,Execution time,Period(=Deadline),Release time:" );                scanf( "%d %d %d %d",&n

8、ame,&run,&period,&release);                k=0;                 while(k<5)/*k是周期数*/       

9、                                          for(j=0;j<run;j+)     

10、60;                                                 

11、60;                        A=name;                      

12、60;                         Anumber.run=1;                      &

13、#160;                         Anumber.period=period;                    

14、60;                           Anumber.release=release+k*period;                 

15、                               number+;                 

16、0;                                              fflush(stdin); /*清空缓冲区

17、*/                                k+;                printf(

18、"n");printf("What you input is:n");for(i=0;i<number;i+)                 printf( "%dt%dt%dt%dn",A,Ai.run,Ai.period,Ai.release);printf("n"); /main.c/*EDF 算法实现-C 语言，结构体*

19、/#include "EDF.h"void Input();int main()Input();EDF();return 0;/edf.c#include"EDF.h"void copy(struct Program* b,struct Program* a)     b->name = a->name;    b->run = a->run;    b->period = a->period;   

20、 b->release=a->release;    return;/EDF 核心算法void EDF()       struct Program m;     int i,j,k,l;    int sum;      int flag;    /排序    for(i = 0;i<number;

21、i+)                                    k = i;        for(j = i;j < number;j+) 

22、0;                  if(Aj.period+Aj.release < Ak.period+Ak.release)                         

23、                                       k = j;          

24、                                                  

25、    copy(&m,&Ak);                                copy(&Ak,&Ai);       

26、;                         copy(&Ai,&m);                     &#

27、160;          printf( "截至时间排序如下n" );                 for(i = 0;i < number;i+)             &#

28、160;                                  printf( "%dt%dt%dt%dn",A,Ai.run,Ai.period,Ai.release);   

29、0;                            printf( "*n" );    /判断              

30、;  sum = 0;                flag=0;                 for(i=0;i<number+1;i+)         

31、                                       FSi0=-1;         

32、0;                      FSi1=-1;                          &#

33、160;      for(i=0;i<number;i+)                                        &#

34、160;       j=Ai.release;                                 while(j<number)     

35、                                                  

36、                          if(FSj1!=-1)                       

37、;                                                  

38、;                                                  

39、;                                                  

40、;                                    else              

41、                                                  

42、                                                 if(FSj0=-1)

43、                                                  

44、                                                  

45、                                            FSj0=A;    

46、;                                                  

47、;                           if(j=Ai.release+Ai.period|j>Ai.release+Ai.period)               

48、                                                  

49、                                                  

50、                                                  

51、           flag=1;                                      

52、;                                                  

53、;                                                  

54、;                       break;                          

55、0;                                                 

56、0;                                                 

57、0;  else if (FSj0=A)                                             

58、;                                                  

59、;                                                  

60、;                                                  

61、;                                                  

62、;                            else                      

63、                                                  

64、                                                  

65、                      FSj1=A;                          

66、;                                                  

67、;     if(j=Ai.release+Ai.period|j>Ai.release+Ai.period)                                     

68、                                                  

69、                                                  

70、                                       flag=1;          

71、;                                                  

72、;                                                  

73、;                                                  

74、; break;                                                

75、0;                                                 

76、0;                                                 

77、0;           j+;                                      &

78、#160;                          if(flag=1)                      &#

79、160;                         printf( "不可调度！n" );                   

80、60;             else                        printf( "调度顺序如下n" );        

81、60;                       i=0;                          

82、;       while(i<Anumber-1.period+Anumber-1.release)                                    

83、                                             if(FSi0=-1)    

84、                                                  

85、          printf( "0 ");                                    

86、             else                                     &

87、#160;                                                 &

88、#160;                        printf( "%d ", FSi0);                    

89、                                                  

90、                           if(FSi1=-1)