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

实验报告实验名称：最早期限优先调度算法（EDF）实验一、 实验目的1） 了解实时调度，了解最早截止期优先算法（EDF 算法）；2） 使用 C 语言实现最早截止期优先算法（EDF 算法）；3） 计算多个任务的调度顺序二、 实验原理最早截止期优先算法（EDF），也称为最早死限调度算法（DDS），是一种采用动态调度的优先级调度算法，任务的优先级根据任务的截止时间来确定任务的截止时间越近，任务的优先级越高；任务的截止时间越远，任务额优先级越低当有新的任务处于就绪状态时，任务的优先级就有可能需要进行调整EDF 算法的测试如果所有的任务都是周期性的，并且对应的时间限等于它们的周期，对任务集的调度性的测试是非常简单的：如果任务集的总利用率不大于 1，那么任务集就可以由 EDF 算法在一个单处理器上进行合理的调度对于那些任务的时间限并不全等于其周期的情况，没有简答的调度性测试在这样的情况下，需要使用 EDF 算法生成一个时间表，来判断是不是在一个给定的时间区间内所有的时间限都被满足在这种情况下 EDF 的一个可调度性测试如下：定义 ， 以及 （这里的“lcm”表示𝑢=∑𝑛𝑖=1(𝑒𝑖/𝑃𝑖) 𝑑𝑚𝑎𝑥=max1≤𝑖≤𝑛{𝑑𝑖} 𝑃=𝑙𝑐𝑚(𝑃1,…𝑃𝑛)最小公倍数）。

定义 是任务集 T 中所有满足其时间限的绝对值小鱼 t 的任务执行时间ℎ𝑇(𝑡)之和一个由 n 个任务构成的集合不是可行的 EDF 的充分必要条件是：或存在某个 使得𝑢>1𝑡𝑡（其中 n 为任务集中任务的数量； 为任务 的执行时间； 为周期任务的周期； 为𝑒𝑖 𝑇𝑖 𝑃𝑖 𝑑𝑖任务 的相对时间限； 为在绝对时间不迟于 t 的任务集合 T 中，所有重复的任务执行𝑇𝑖 ℎ𝑇(𝑡)时间和三、 实验仪器硬件：PC 机；软件：Windows7，Visual Studio 2010 集成开发环境四、 实验步骤1） 理解 EDF 调度算法的原理并通过实例用 EDF 算法判断多任务的调度顺序2） 新建 EDF.h 头文件，在其中定义变量，结构体，函数3） 新建 input.c 文件，用 input 函数从键盘获取多个任务的名称、执行时间、周期和释放时间，将任务分成一个个时间片存在数组中，并输出数组和各时间片属性4） 新建 edf.c 文件，用 EDF 函数将数组中的时间片根据截止时间的大小从小到大进行排序，输出它们的截止时间排序，再判断是否可调度，若是不可调度输出“不可调度！”，若是可调度输出调度顺序。

5） 新建 main.c 文件，在其中调用 input 函数和 EDF 函数6） 编译运行程序，输入多个任务调试程序至结果无误7） 对实验进行分析、反思，与同学讨论五、 实验结果程序完成后，输入了多种情况进行验证，运行结果正确，符合按照最早截止期优先算法得出的结果1）不可调度当五个任务的执行时间和周期都为 1 时，是不可调度的由 EDF 算法的测试可知）2）可调度当五个任务的执行时间和周期分别为 1、3，2、12，1、6，1、4，3、20，释放时间分别为 0,1,0,1,0 时，是可调度的结果如下：六、 实验分析与讨论1）编程前要理解清楚算法对算法理解不清就编写代码实现，那么写出来的程序与计算出来的结果会不一致、运行不正确重新理解算法，调试程序，会造成不必要的时间浪费2）实验前一定要做好实验设计如变量设置，功能语句设计等否则在编写程序的过程中容易出现思维逻辑不清晰，无法继续实现必需功能的问题这样仍然会造成不必要的时间浪费附：源代码//EDF.h#include #include #define n 5int number;int schedule[1000][2];int FS[1000][2];struct Program{int name;int run;int period;int release;}A[1000];void Input();void EDF();//input.c/*************输入*************/#include"EDF.h"void Input(){// program A[n];char s;int i,j,k;int name,run,period,release;number=0;for(i=0;iname = a->name;b->run = a->run;b->period = a->period;b->release=a->release;return;}//EDF 核心算法void EDF() {struct Program m;int i,j,k,l;int sum;int flag;//排序for(i = 0;iA[i].release+A[i].period){flag=1;}break;}else if (FS[j][0]==A[i].name) {;}else{FS[j][1]=A[i].name;if(j==A[i].release+A[i].period||j>A[i].release+A[i].period){flag=1;}break;}}j++;}}if(flag==1){printf( "不可调度！\n" );}else{printf( "调度顺序如下\n" );i=0;while(i