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

时限调度算法给出的调度顺序时限调度算法是一种常用的任务调度算法，它主要用于在有限的时间内，合理地安排多个任务的执行顺序，以提高系统的效率和性能。

本文将介绍时限调度算法的基本原理和常见的调度顺序。

一、先来了先服务（FCFS）调度顺序先来了先服务（First-Come-First-Served）调度顺序是最简单的一种调度算法，它按照任务到达的先后顺序进行调度。

当一个任务到达后，系统就立即执行它，直到任务结束或发生阻塞。

这种调度顺序的优点是简单易实现，但缺点是无法根据任务的重要程度和紧急程度进行优先级调度，容易导致低优先级任务长时间等待。

二、最短作业优先（SJF）调度顺序最短作业优先（Shortest-Job-First）调度顺序是根据任务的执行时间长度进行调度的算法。

当多个任务同时到达时，系统会选择执行时间最短的任务先执行。

这种调度顺序的优点是能够最大程度地减少平均等待时间，提高系统的响应速度。

然而，它也存在着一定的缺点，即可能导致长任务的饥饿问题，即长任务可能一直等待短任务执行完毕而得不到执行。

三、优先级调度顺序优先级调度顺序是根据任务的重要程度和紧急程度进行调度的一种算法。

每个任务都有一个优先级，优先级越高的任务越先执行。

这种调度顺序能够根据任务的紧急程度进行调度，保证重要任务得到及时处理。

然而，它也存在着可能导致低优先级任务长时间等待的问题，因此需要合理设置任务的优先级。

四、时间片轮转（RR）调度顺序时间片轮转（Round-Robin）调度顺序是一种基于时间片的调度算法，它将每个任务分配一个固定长度的时间片，当一个任务的时间片用完后，系统会将其放入等待队列，并执行下一个任务。

这种调度顺序能够公平地分配系统资源，避免某个任务长时间占用资源，但也可能导致任务的响应时间较长。

五、最早截止时间优先（EDF）调度顺序最早截止时间优先（Earliest-Deadline-First）调度顺序是根据任务的截止时间进行调度的一种算法。

实验报告实验名称：最早期限优先调度算法（EDF）实验一、实验目的1）了解实时调度，了解最早截止期优先算法（EDF算法）；2）使用C语言实现最早截止期优先算法（EDF算法）；3）计算多个任务的调度顺序。

二、实验原理最早截止期优先算法（EDF），也称为最早死限调度算法（DDS），是一种采用动态调度的优先级调度算法，任务的优先级根据任务的截止时间来确定。

任务的截止时间越近，任务的优先级越高；任务的截止时间越远，任务额优先级越低。

当有新的任务处于就绪状态时，任务的优先级就有可能需要进行调整。

EDF算法的测试如果所有的任务都是周期性的，并且对应的时间限等于它们的周期，对任务集的调度性的测试是非常简单的：如果任务集的总利用率不大于1，那么任务集就可以由EDF算法在一个单处理器上进行合理的调度。

对于那些任务的时间限并不全等于其周期的情况，没有简答的调度性测试。

在这样的情况下，需要使用EDF算法生成一个时间表，来判断是不是在一个给定的时间区间内所有的时间限都被满足。

在这种情况下EDF的一个可调度性测试如下：定义，以及（这里的“lcm”表示最小公倍数）。

定义是任务集T中所有满足其时间限的绝对值小鱼t的任务执行时间之和。

一个由n个任务构成的集合不是可行的EDF的充分必要条件是：或存在某个使得（其中n为任务集中任务的数量；为任务的执行时间；为周期任务的周期；为任务的相对时间限；为在绝对时间不迟于t的任务集合T中，所有重复的任务执行时间和。

）三、实验仪器硬件：PC机；软件：Windows7，Visual Studio 2010集成开发环境四、实验步骤1）理解EDF调度算法的原理并通过实例用EDF算法判断多任务的调度顺序。

2）新建EDF.h 头文件，在其中定义变量，结构体，函数。

3）新建input.c文件，用input函数从键盘获取多个任务的名称、执行时间、周期和释放时间，将任务分成一个个时间片存在数组中，并输出数组和各时间片属性。

1.1先来先服务算法(FCFS)先来先服务(FCFS-First Com e First Serve)算法，是一种随即服务算法，它不仅仅没有对寻找楼层进行优化，也没有实时性的特征，它是一种最简单的电梯调度算法。

它根据乘客请求乘坐电梯的先后次序进行调度。

此算法的优点是公平、简单，且每个乘客的请求都能依次地得到处理，不会出现某一乘客的请求长期得不到满足的情况[12]。

这种方法在载荷较轻松的环境下，性能尚可接受，但是在载荷较大的情况下，这种算法的性能就会严重下降，甚至恶化。

人们之所以研究这种在载荷较大的情况下几乎不可用的算法，有两个原因：(1)任何调度算法在请求队列长度为1时，请求速率极低或相邻请求的间隔为无穷大时使用先来先服务算法既对调度效率不会产生影响，而且实现这种算法极其简单。

(2)先来先服务算法可以作为衡量其他算法的标准。

1.2最短寻找楼层时间优先算法(SSTF)最短寻找楼层时间优先(SSTF-Shortest Seek Time First) [14]算法，它注重电梯寻找楼层的优化。

最短寻找楼层时间优先算法选择下一个服务对象的原则是最短寻找楼层的时间。

这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。

在重载荷的情况下，最短寻找楼层时间优先算法的平均响应时间较短，但响应时间的方差较大，原因是队列中的某些请求可能长时间得不到响应，出现所谓的“饿死”现象。

1.3扫描算法(SCAN)扫描算法(SCAN)是一种按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。

它进行寻找楼层的优化，效率比较高，但它是一个非实时算法。

扫描算法较好地解决了电梯移动的问题，在这个算法中，每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的，所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成，免去了电梯频繁的来回移动[2]。

操作系统中的调度算法分析操作系统是计算机系统中最为重要的组成部分之一，它负责管理计算机系统的资源，包括硬件和软件资源，并且为其它应用程序提供支持和服务。

在操作系统中，调度算法是其中非常重要的一部分，对于它的优化和改进有着非常重要的意义。

本文将按照类别对操作系统中的调度算法进行详细分析，包括批处理系统中的调度算法、交互式系统中的调度算法、实时系统中的调度算法，以及多处理器系统中的调度算法。

一、批处理系统中的调度算法批处理系统是指能够自动地运行一批作业的操作系统，它是在没有任何人的干预下完成作业的自动化系统。

在批处理系统中的调度算法，其主要目的是使各作业的吞吐率最大，并且减少响应时间和等待时间。

在批处理系统中的调度算法包括先来先服务（FCFS）算法、短进程优先（SJF）算法、最高响应比优先（HRRN）算法等。

1、先来先服务（FCFS）算法先来先服务算法，也称为先到先服务算法，是最简单的一种调度算法。

它的作用是按照进程的到达时间的先后顺序进行服务，先到达的进程先得到服务，后到达的进程则必须等待前面进程的服务结束才能够被执行。

优点是公平、简单，缺点是会导致长作业等待时间长，短作业等待时间短。

2、短进程优先（SJF）算法短进程优先算法，是按照进程的执行时间长度来排序，执行时间越短的进程优先得到服务，它可以使得等待时间总和最小，从而提高系统的吞吐率。

但是，如果遇到长作业，则会导致短作业等待时间过长。

3、最高响应比优先（HRRN）算法最高响应比优先算法，则是综合考虑前两种算法的优点而得到的一种调度算法，它会计算出每个进程的响应比，并且选择响应比最高的进程进行执行。

响应比的计算公式是：响应比 = (等待时间 + 执行时间) / 执行时间该算法可以最大限度地减少等待时间，并且适用于长作业与短作业的服务。

二、交互式系统中的调度算法相比于批处理系统，交互式系统强调用户体验，需要快速响应用户的指令请求。

因此，交互式系统中的调度算法，其主要目的是降低响应时间，尽可能快地处理用户的请求。

先来先服务,时间片调度,优先级调度算法实验报告先来先服务、时间片调度、优先级调度算法实验报告1. 引言本次实验旨在研究和比较先来先服务（FCFS）、时间片调度（RR）和优先级调度（Priority Scheduling）三种常见的进程调度算法。

进程调度是操作系统中的重要概念之一，合理的进程调度算法可以提高系统效率，优化资源利用。

2. 先来先服务算法•先来先服务算法是一种简单的调度算法，按照进程到达的顺序进行调度。

•优点：简单易实现，适用于长作业。

•缺点：容易造成短作业等待时间过长，无法满足实时性要求。

3. 时间片调度算法•时间片调度算法将CPU时间划分为一段一段的时间片，每个进程在一个时间片内执行。

•若进程未完成，会被放入就绪队列的末尾，等待下一个时间片。

•优点：公平，适用于短作业，能满足实时性要求。

•缺点：时间片过长，会导致长作业等待时间过长。

4. 优先级调度算法•优先级调度算法根据进程的优先级来确定调度顺序，拥有最高优先级的进程先执行。

•静态优先级可在创建进程时确定，动态优先级可根据进程执行情况进行调整。

•优点：适用于实时任务和长作业，可根据需求调整优先级。

•缺点：可能导致低优先级任务等待时间过长，存在优先级反转问题。

5. 实验结果与分析通过对三种调度算法的实验测试，得出以下结论：•FCFS算法在长作业的情况下表现较好，但对于短作业不友好，容易造成长时间等待；•RR算法适用于短作业，能保证公平性，但时间片过长可能导致长作业等待时间过长；•优先级调度算法较为灵活，能满足实时性要求，但可能导致低优先级任务长时间等待。

综上所述，不同的调度算法适用于不同的场景，根据需求选择合适的算法可提高系统效率。

6. 总结本次实验对先来先服务、时间片调度和优先级调度算法进行了研究和比较。

通过对三种算法的分析，我们可以根据任务特点和需求选择合适的调度算法，以提高系统的效率和资源利用率。

同时，在实际应用中也需要考虑进程的实时性要求，避免长时间等待等问题的出现。

操作系统课程报告学号 1315212033 姓名滕健伟班级 13 电子2 华侨大学电子工程系一、最早截止时间优先（EDF）算法的基本原理1. 最早截止时间优先EDF（Earliest DeadlineFirst）算法是非常著名的实时调度算法之一。

在每一个新的就绪状态，调度器都是从那些已就绪但还没有完全处理完毕的任务中选择最早截止时间的任务，并将执行该任务所需的资源分配给它。

在有新任务到来时，调度器必须立即计算EDF，排出新的定序，即正在运行的任务被剥夺，并且按照新任务的截止时间决定是否调度该新任务。

如果新任务的最后期限早于被中断的当前任务，就立即处理新任务。

按照EDF算法，被中断任务的处理将在稍后继续进行。

2. 该算法的思想是从两个任务中选择截至时间最早的任务,把它暂作为当前处理任务,再判断该任务是否在当前周期内,若不在当前周期内,就让另一任务暂作当前处理任务,若该任务也不在当前周期内,就让CPU空跑到最靠近的下一个截至时间的开始,若有任务在该周期内,就判断该任务的剩余时间是否小于当前截至时间与当前时间的差,若小于,则让该任务运行到结束.否则,就让该任务运行到该周期的截止时间,就立即抢回处理器,再判断紧接着的最早截至时间,并把处理器给它,做法同上,如此反复执行.本实验用C语言对最早截止时间优先算法进行了模拟。

二、程序流程图三、程序及注释本程序模拟两个任务同时到来时，进程依据最早截止时间优先算法的分配情况。

定义了如下变量：Int T，模拟时间，T<=100；Float m,判断所要处理的任务是否满足单机处理限制条件；Int cycA,cycB,任务A，B的周期时间，是需要用户输入的信息；Int serveA,serveB,任务A，B的处理时间,是需要用户输入的信息；Int a,b,任务A，B的下标，即标记任务A,B是第几次到来，第几次执行，第几次结束；Int numa,numb,标记任务Ai,Bi的累计执行时间，当numa=serveA时，任务A完成，当numb=serveB时，任务B完成。

操作系统实验四设计先来先服务进程调度模拟算法实验提示：进程个数至少5个以上（动态），也可让用户动态输入，每个进程由一个进程控制块来标识，进程控制块的内容根据情况自己设计，但至少要有进程名、进程状态、到达时间、估计运行时间信息；设计一个先进先出队列和系统时间，调度时，总是选择队列头部（到达时间最早）的进程；当进程到达时间小于系统时间时，进程执行，当在当前时间没有到达的进程时，可安排延时来模拟闲逛进程。

由于本实验为模拟实验，所以被选中调度进程并不实际启动运行，而仅执行按估计运行时间延时，并输出进程的开始和结束运行信息模拟进程的运行，而且省去进程的现场保护和现场恢复工作。

在所设计的程序中应有显示或打印语句，能显示或打印就绪队列中的进程、正运行进程的进程名、开始运行时间、结束运行时间等，给出各进程的周转时间和平均周转时间。

实验要求：实验报告中要给出流程图和源程序，源程序中要附有详细的注释，给出程序运行时的输入值和运行结果总结收获或对该题的改进意见和见解。

流程图：源程序：输入值：ID 进程名到达时间服务时间1 A2 32 B3 43 C4 5运行结果：总结收获：通过本次实验，我了解到如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在就绪队列的后面，那么先来先服务总是把当前处于就绪队列之首的那个进程调度到运行状态。

也就说，它只考虑进程进入就绪队列的先后，而不考虑它的下一个CPU周期的长短及其他因素。

FCFS算法简单易行，是一种非抢占式策略，但性能却不大好。

先来先服务的调度算法：最简单的调度算法，既可以用于作业调度，也可以用于程序调度，当作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，优先从后备队列中，选择一个或多个位于队列头部的作业，把他们调入内存，分配所需资源、创建进程，然后放入“就绪队列”,直到该进程运行到完成或发生某事件堵塞后，进程调度程序才将处理机分配给其他进程。

有利于长作业（进程）而不利于短作业（进程）和CPU繁忙型作业（进程）而不利于I/O繁忙型作业（进程）。

实验报告
姓
名：
学号：日期：2011-1-10 实验
题
目：
实验二：处理机调度---实时调度算法EDF和RMS
实验目的：
深入理解处理机调度算法，了解硬实时概念，掌握周期性实时任务调度算法EDF(Earliest Deadline First)和RMS(Rate-Monotonic Scheduling)的可调度条件，并能在可调度的情况下给出具体调度结果。

实验内容：
在Linux环境中采用用户级线程模拟实现EDF和RMS两种实时调度算法。

给定一组实时任务，按照EDF算法和RMS算法分别判断是否可调度。

在可调度的情况下，创建一组用户级线程，分别代表各个实时任务，并按算法所确定的调度次序安排各个线程运行，运行时在终端上画出其Gantt图。

为避免图形绘制冲淡算法，Gantt图可用字符表示。

实验步骤：1.启动虚拟机，在Linux系统终端中找到代码
2.仔细阅读教材相关内容和实验指导书中实验准备；
3.将代码在Linux系统上编译并运行。

4.根据实验结果分析。

5.结束实验，退出保存。

实验结果：实验结果如实验指导书上所示。

EDF算法结果：
RMS算法结果：。