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

RM和EDF算法原论文翻译RM和EDF——硬实时环境下多线程的调度算法摘要：单处理器的多线程调度问题的研究范围已经从它本身的特征拓展到程序运行的可靠性。

研究表明最佳固定优先级调度在大型任务序列集的情况下的最大调度利用率仅为70%。

此外，根据当前任务序列截止期动态分配优先级可以使调度率利用率等于1。

本文还讨论了将两种调度方法结合起来的算法。

1 引言近年来，运用计算机来控制和监测工业生产过程已得到广泛应用和不断扩展，并且在未来很可能得到更大的拓展。

此类应用的多数情况下，计算机由一定数目的时限监控程序和一批非时限任务流所共用。

然而，在其他的应用中，非时限作业不存在且计算机的有效利用只能通过谨慎调度时限监测程序来达到。

后者被称为“纯过程控制”且为本文呈现的组合调度分析提供了理论背景。

本文研究了此类程序设计中的两种调度算法，这两种均为可抢断优先级驱动算法，这意味着正在处理的任务可被任何高优先级任务中断。

第一个算法用一个固定优先级分配能使处理器利用率到达约70%甚至更大。

第二个算法通过动态分配优先级可以达到处理器的全利用。

此外，本文还讨论了两个算法的结合。

2 背景一个程序控制计算机执行一个或更多的监控程序。

追踪航天器运行轨迹的天线尖端就是此类监控程序的一个例子。

每个程序与一系列任务序列集相联且共同被执行。

此类任务中的一些任务是为了响应计算机监控的设备所发生的事件。

这些任务不能先于事件执行。

每个任务都必须在事件按要求释放后的固定时间内执行完毕。

在此时间段内的服务都需确保稳定性。

将运行环境分类为“硬实时”[1]是为了在可接受的响应时间统计分布上与“软实时”相对应。

多数现有多程序设计文献是针对商业分时系统的统计数据分析（文献[2]包含了详细的参考书目）。

也有文献针对更有意思的方面，比如调度批量处理设备或是混合批量分时设备，这些调度通常是在如文献[3]-[8]中多处理器配置环境下。

仅有少数论文直接讨论如何攻克“硬实时”程序设计的难关。

浅析RM与EDF实时调度算法1 引言与非实时系统相比，嵌入式实时系统因其所控制物理过程的动态性，要求运行于其中的单个任务必须满足其时限要求，以确保整个系统的正确性和安全性[1]。

在航空航天、电信、制造、国防等领域，对实时系统有着强烈的应用需求。

实时处理和实时系统的研究和应用工作已经有了相当长的历史，在实时任务调度理论、实时操作系统、实时通信等方面取得了大量成果。

实时任务调度理论是实时处理技术的核心和关键[2]。

这是因为，实时任务具有时限要求，在一个或多个处理器之间调度实时任务，需要判断是否每个任务的执行都能在其截止期限内完成。

如果每个任务的执行都能在其截止期限内完成，则称该调度是可行。

可调度性判定就是判定给定的n个实时任务在应用某种调度算法的前提下能否产生一个可行的调度。

调度算法的设计要尽可能满足任务可调度性的要求[3]。

2 实时调度分类由于实时系统的侧重点不同，实时调度亦有多种分类方式。

常见的分类有，根据任务实时性要求的重要程度，分为硬实时调度和软实时调度——在硬实时调度中任务必须在其截止期限内执行完毕，否则将产生严重后果。

而对于软实时任务，当系统负载过重的时候，允许发生错过截止期限的情况，根据任务是在一个或多个处理器上运行，分为单处理器实时调度和多处理器实时调度，多处理器实时调度又可分为集中式调度和分布式调度；根据调度算法和可调度性判定是在任务运行之前还是运行期间进行的，分为静态调度、动态调度和混合调度；根据被调度的任务是否可以互相抢占，分为抢占式调度和非抢占式调度；根据任务请求到达的情况不同。

分为周期性任务调度和非周期性任务调度。

不同调度方式具有各自的优缺点，适用于不同类型的实时系统。

3 RM与EDF调度算法简介1973年，Liu 和Layland 提出了一种适用于可抢占的硬实时周期性任务调度的静态优先级调度算法——速率单调（Rate Monotonic ，简称RM ）调度算法，并对其可调度性判定问题进行了研究。

一种基于EDF的运行时模型研究的开题报告一、研究背景随着嵌入式系统的广泛应用，对实时性的要求不断提高，而实时性保证问题是嵌入式系统中一个十分重要的问题。

在实时系统中，任务调度算法是实现实时性保证的关键。

EDF（Earliest Deadline First）调度算法是一种比较有效的实时系统调度算法，它通过选择剩余执行时间最少的任务进行调度，以尽可能避免任务的失约。

在现有研究中，针对EDF调度算法的研究多集中在其理论分析和仿真实验上，缺乏对于真实硬件环境下的实验验证和性能研究，因此需要进一步探究基于EDF的运行时模型。

二、研究目标本研究旨在基于EDF调度算法，构建一个包含硬件平台和软件任务的综合实验平台，开展运行时模型研究，探索EDF调度算法在真实硬件环境下的实验验证和性能评估。

三、研究方法1. 构建实验平台：采用ARM Cortex-M4处理器作为硬件平台，开发基于FreeRTOS操作系统的软件任务，构建一个包含硬件平台和软件任务的综合实验平台。

2. 设计实验方案：根据EDF调度算法的机制和特点，设计一组实验方案，包括任务的执行时间和优先级，以及不同负载下的实验条件设置。

3. 进行实验验证：在实验平台上执行设计好的实验方案，统计实验数据，并运用相关数据分析方法进行实验结果评估。

四、研究意义通过构建基于EDF调度算法的综合实验平台，能够真实、直观地反映EDF调度算法在嵌入式系统中的实际应用效果，对于深入研究EDF调度算法的机制和特点，提升实时系统的实时性能有一定的意义。

同时，本研究所构建的实验平台对于其他实时任务调度算法的研究，也具有一定的参考价值。

一、实验目的1. 理解操作系统调度算法的基本原理和概念。

2. 掌握几种常见调度算法的原理和实现方法。

3. 分析不同调度算法的性能特点，为实际应用提供参考。

二、实验内容本次实验主要涉及以下几种调度算法：先来先服务（FCFS）、最短作业优先（SJF）、优先级调度（Priority Scheduling）、最高响应比优先（HRRN）和时间片轮转（Round Robin）。

1. 先来先服务（FCFS）调度算法FCFS调度算法按照进程到达就绪队列的顺序进行调度，先到达的进程先执行。

该算法简单易实现，但可能导致长作业等待时间过长，从而降低系统吞吐量。

2. 最短作业优先（SJF）调度算法SJF调度算法优先选择执行时间最短的进程进行调度。

该算法可以最大程度地减少平均等待时间和平均周转时间，但可能导致长作业等待时间过长。

3. 优先级调度（Priority Scheduling）算法优先级调度算法为每个进程设置一个优先级，优先选择优先级高的进程进行调度。

该算法可以满足高优先级作业的需求，但可能导致低优先级作业长时间等待。

4. 最高响应比优先（HRRN）调度算法HRRN调度算法为每个进程设置一个响应比，优先选择响应比高的进程进行调度。

响应比是作业的等待时间与作业所需时间的比值。

该算法综合考虑了作业的等待时间和所需时间，是一种较为公平的调度算法。

5. 时间片轮转（Round Robin）调度算法时间片轮转调度算法将CPU时间划分为固定的时间片，按照进程到达就绪队列的顺序，每次只允许一个进程运行一个时间片。

如果进程在一个时间片内无法完成，则将其放入就绪队列的末尾，等待下一次调度。

该算法可以平衡各个进程的执行时间，但可能导致进程响应时间较长。

三、实验步骤1. 编写一个进程调度程序，实现上述五种调度算法。

2. 生成一个包含多个进程的作业队列，每个进程具有到达时间、所需运行时间和优先级等信息。

3. 分别采用五种调度算法对作业队列进行调度，并记录每个进程的执行情况。

一种基于EDF的实时任务调度算法浅析摘要实时系统的高可靠性、计算准确性及输出结果的实时性使得其在各领域的应用越来越广泛。

而实时调度算法是实时系统中的关键技术。

本文在EDF 算法的基础上提出了一种新的实时调度算法，该算法通过任务的可推迟执行时间逐次逼近，能够快速准确的计算出每个任务的最大可挪用时间。

关键词实时性；实时调度算法；单调速率优先；最早截止期优先；计算时间前言实时系统是指能够及时响应外部发生的随机事件，并在规定时间内完成对事件处理的计算机系统。

实时系统具有高可靠性、实时性、少人工干预、专用性等特征，广泛应用于航天控制、工业控制、机器人智能控制、云计算、多处理器下多媒体流调度以及嵌入式智能设备等各个重要领域。

实时系统不仅应用广泛，而且要求严格。

对实时调度算法的研究，是实时领域的一个重要的研究课题[1]。

1 实时调度算法实时调度算法可以分为两类：静态调度算法和动态调度算法。

RM 和EDF 调度算法分别是经典的静态和动态实时高度算法，在实时调度领域占有重要地位。

EDF调度算法按照实时任务截止期的远近来分配优先级，截止期越近的任务优先级越高，任何时刻总是运行优先级最高的任务，即总是优先运行最紧迫的任务。

因为在不同时刻，两个周期任务截止期的远近关系可能会改变，所以EDF 调度算法是一种动态优先级调度算法。

EDF算法不仅对于硬实时周期任务调度，而且对于硬实时非周期任务的调度来说都是最优的动态优先级调度算法本文在EDF算法的基础上提出了一种新的实时调度算法，该算法通过任务的可推迟执行时间逐次逼近，能够快速准确的计算出每个任务的最大可挪用时间[2]。

2 任务模型本文使用以下概念来描述实时系统。

定义1（超周期，hyperperiod）：硬实时周期任务集中的所有任务周期的最小公倍数，记为H，H=LCM（T1，T2，…，Tn），其中LCM是最小公倍数函数。

定义2（周期任务的负载）：一个周期任务平均对处理器的占用率，记为u，u=C/T，C为周期任务每次的执行时间，T为周期任务的周期，即每次释放的时间间隔。

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

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

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

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

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

在批处理系统中的调度算法包括先来先服务（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完成。

ＯＣＣＵＰＡＴＩＯＮ912012 10案例C ASES抢占式动态优先级实时调度算法董晓明摘　要：在嵌入式系统中，任务调度器的好坏很大程度上决定了系统的性能。

该文分析了实时系统中具有代表性的静态和动态调度算法，结合剩余时间和ＥＤＦ算法以及中断时抢占策略，结合各自的优点，提出一种新的动态调度算法——抢占式剩余时间算法。

关键词：截止期限　ＥＤＦ　周期任务　实时调度一、基于优先级的实时调度算法在实时任务调度中，大量研究都集中于对调度策略的应用。

基于优先级的实时调度算法是一种常见的调度算法，这类算法主要包括速率单调算法(Rate．Monotonic，RM)、最早截止期优先算法(Earliest Deadline First，EDF)。

RM算法具有简单的实现机制和较低的调度开销，被广泛应用于实时调度领域。

然而仅以任务的周期作为优先级的判定条件，忽视了某些对于用户来说比较重要而周期长的任务，对一些周期负载较重的情况是不合适的。

最早截止期限优先算法(EDF)，是一种动态调度算法。

该算法的优先级根据他们的截止期限(Deadline)确定，具有最近的截止期限的任务具有最高的优先级。

如参考文献[3]中提到了一种RM改进的动态调度剩余时间算法，在每一次任务调度前，计算每一个等待任务的剩余时间，并按照各任务的剩余时间的长短为每一个任务分配或重新分配一个优先级，剩余时间越短，优先级越高。

二、抢占式剩余时间算法1.算法描述该算法对剩余时间算法的剩余时间计算方式做出改进，按照改进后的剩余时间为每一个任务分配或重新分配优先级，根据新的优先级采用抢占式任务调度策略。

其中剩余时间T s =T d -T w ，T d 为任务截止期限，T w 为任务等待时间。

该算法按以下几种情况讨论。

（1）按任务的剩余时间大小对任务的优先级进行设定，剩余时间越短优先级越高。

（2）如果当前优先级队列中优先级最高的任务的剩余时间大于该任务需要运行的时问，则该任务被调用执行，否则不予执行。

实验报告
姓
名：
学号：日期：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算法结果：。

实验报告实验名称：最早期限优先调度算法（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.设计进程控制块PCB的结构，通常应包括如下信息：进程名、进程优先数（或轮转时间片数）、进程已占用的CPU时间、进程到完成还需要的时间、进程的状态、当前队列指针等。

2.编写优先级调度算法程序3.按要求输出结果。

四、实验要求每个进程可有三种状态；执行状态（RUN）、就绪状态（READY,包括等待状态）和完成状态（FINISH），并假定初始状态为就绪状态。

（一）进程控制块结构如下：NAME——进程标示符PRIO/ROUND——进程优先数NEEDTIME——进程到完成还需要的时间片数STATE——进程状态NEXT——链指针注：1.为了便于处理，程序中进程的的运行时间以时间片为单位进行计算；2.各进程的优先数或，以及进程运行时间片数的初值，均由用户在程序运行时给定。

（二）进程的就绪态和等待态均为链表结构，共有四个指针如下：RUN——当前运行进程指针READY——就需队列头指针TAIL——就需队列尾指针FINISH——完成队列头指针五、实验结果：六、实验总结：首先这次实验的难度不小，它必须在熟悉掌握数据结构的链表和队列的前提下才能完成，这次实验中用了三个队列，就绪队列，执行队列和完成队列，就绪队列中的优先级数是有序插入的，当进行进程调度的时候，需要先把就绪队列的队首节点（优先级数最大的节点）移入执行队列中，当执行进程结束后，判断该进程是否已经完成，如果已经完成则移入完成队列，如果没有完成，重新有序插入就绪队列中，这就是这次实验算法的思想。

附录（算法代码）：#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct node{char name[20]; /*进程的名字*/int prio; /*进程的优先级*///int cputime; /*CPU执行时间*/int needtime; /*进程执行所需要的时间*/char state; /*进程的状态，W--就绪态，R--执行态，F--完成态*/struct node *next; /*链表指针*/}PCB;PCB *ready=NULL,*run=NULL,*finish=NULL; /*定义三个队列，就绪队列，执行队列和完成队列*/int num;void GetFirst(); /*从就绪队列取得第一个节点*/void Output(); /*输出队列信息*/void InsertPrio(PCB *in); /*创建优先级队列，规定优先数越小，优先级越高*/ void InsertTime(PCB *in); /*时间片队列*/void InsertFinish(PCB *in); /*时间片队列*/void PrioCreate(); /*优先级输入函数*///void TimeCreate(); /*时间片输入函数*/void Priority(); /*按照优先级调度*///void RoundRun(); /*时间片轮转调度*/void main(){printf("优先数调度算法\n");printf("请输入要创建的进程数目：");scanf("%d",&num);PrioCreate();Priority();Output();}void GetFirst() /*取得第一个就绪队列节点*/{run = ready;if(ready!=NULL){run ->state = 'R';ready = ready ->next;run ->next = NULL;}}void Output() /*输出队列信息*/{PCB *p;p = ready;printf("进程名\t优先级\t需要时间\t进程状态\n");while(p!=NULL){printf("%s\t%d\t%d\t\t%c\t\n",p->name,p->prio,p->needtime,p->state);p = p->next;}p = finish;while(p!=NULL){printf("%s\t%d\t%d\t\t%c\t\n",p->name,p->prio,p->needtime,p->state);p = p->next;}p = run;while(p!=NULL){printf("%s\t%d\t%d\t\t%c\t\n",p->name,p->prio,p->needtime,p->state);p = p->next;}}void InsertPrio(PCB *in) /*创建优先级队列，规定优先数越小，优先级越低*/ {PCB *fst,*nxt;fst = nxt = ready;if(ready == NULL) /*如果队列为空，则为第一个元素*/{in->next = ready;ready = in;}else /*查到合适的位置进行插入*/{if(in ->prio >= fst ->prio) /*比第一个还要大，则插入到队头*/{in->next = ready;ready = in;}else{while(fst->next != NULL) /*移动指针查找第一个别它小的元素的位置进行插入*/{nxt = fst;fst = fst->next;}if(fst ->next == NULL) /*已经搜索到队尾，则其优先级数最小，将其插入到队尾即可*/{in ->next = fst ->next;fst ->next = in;}else /*插入到队列中*/{nxt = in;in ->next = fst;}}}}void InsertFinish(PCB *in) /*将进程插入到完成队列尾部*/{PCB *fst;fst = finish;if(finish == NULL){in->next = finish;finish = in;}else{while(fst->next != NULL){fst = fst->next;}in ->next = fst ->next;fst ->next = in;}}void PrioCreate() /*优先级调度输入函数*/{PCB *tmp;int i;printf("输入进程名字,进程所需时间和优先级数：\n");for(i = 0;i < num; i++){if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL){perror("malloc");exit(1);}scanf("%s",tmp->name);getchar(); /*吸收回车符号*/scanf("%d",&(tmp->needtime));getchar();scanf("%d",&(tmp->prio));// tmp ->cputime = 0;tmp ->state ='W';//tmp ->prio = 20 - tmp->needtime; /*设置其优先级，需要的时间越多，优先级越低*/InsertPrio(tmp); /*按照优先级从高到低，插入到就绪队列*/}}void Priority() /*按照优先级调度，每次执行一个时间片*/{int flag = 1;GetFirst();while(run != NULL) /*当就绪队列不为空时，则调度进程如执行队列执行*/ {Output(); /*输出每次调度过程中各个节点的状态*/while(flag){run->prio -= 3; /*优先级减去三*///run->cputime++; /*CPU时间片加一*/run->needtime--;/*进程执行完成的剩余时间减一*/if(run->needtime == 0)/*如果进程执行完毕，将进程状态置为F，将其插入到完成队列*/{run ->state = 'F';// run->count++; /*进程执行的次数加一*/InsertFinish(run);flag = 0;}else /*将进程状态置为W，入就绪队列*/{run->state = 'W';//run->count++; /*进程执行的次数加一*///InsertTime(run);//再次插入就绪队列尾部InsertPrio(run);flag = 0;}}flag = 1;GetFirst(); /*继续取就绪队列队头进程进入执行队列*/ }。

edf算法在linux内核中的实践研究EDF（Earliest Deadline First）算法是一种实时调度算法，用于根据任务的截止时间进行调度。

在 Linux 内核中，EDF 调度算法主要应用于实时任务的调度。

Linux 内核中的实时调度器主要有两种：CFS（Completely Fair Scheduler）和SCHED_DEADLINE。

其中，SCHED_DEADLINE 是实时调度器的一种扩展，提供了对实时任务的支持，包括使用EDF 调度算法对实时任务进行调度。

SCHED_DEADLINE 调度策略下的任务可以通过设置参数来指定任务的截止时间和期限。

在这种调度策略下，Linux 内核使用EDF 调度算法将任务按照截止时间的先后顺序进行调度，确保截止时间更早的任务优先被执行。

对于周期性任务，Linux 内核提供了 sched_setscheduler() 系统调用来设置任务的调度策略和相关参数。

在调用该系统调用时，可以指定任务的调度策略为 SCHED_DEADLINE，然后设置相关的截止时间和期限等参数。

Linux 内核会根据设置的参数使用 EDF 调度算法进行实时任务的调度。

通过使用 EDF 调度算法，Linux 内核能够更好地保证实时任务的截止时间得到满足，并提高实时任务的响应能力和可靠性。

这对于一些对响应时间要求较高的应用场景非常重要，比如嵌入式系统、工控系统等。

总之，EDF 算法在 Linux 内核中通过 SCHED_DEADLINE 调度策略的实现，提供了对实时任务的支持，并根据任务的截止时间进行调度。

它在提高实时任务的响应能力和可靠性方面具有重要的实践研究意义。

最早截止期优先调度算法（EDF）的特点及实现1 引言随着计算机的发展，多道程序处理的出现需要强大的调度算法来对多任务进行调度，以确定多任务环境下任务的执行顺序以及占有CPU时间。

相对于静态、不可抢占的调度方法，EDF的出现使之凭借灵活性高、CPU占有率高很快成为最优的单处理器调度算法。

2 任务调度的基本概念在计算机发展的初期，需要使用计算机时，通常要集中在计算机所在的地方，人为的以作业的方式把工作内容一件一件的交给计算机处理，也就不存在调度的概念。

随后，出现了计算机的批处理方式，计算机把作业按照先来先服务的方式进行处理，体现了一种非常简单的调度概念。

随着多道程序处理方式的出现，调度逐渐变得重要和复杂起来。

在多任务的实时操作系统中，调度是一个非常重要的功能，用来确定多任务环境下任务执行的顺序和获得CPU资源后能够执行的时间长度。

操作系统通过一个调度程序看来实现调度功能，调度程序以函数的形式存在，用来实现操作系统的调度算法。

调度程序是影响系统性能（如吞吐率、延迟时间等）的重要部分。

在设计调度程序时，通常要综合考虑如下因素：CPU的使用率、输入、输出设备的吞吐率、响应时间、公平性和截止时间。

这些因素之间有一定的冲突性，在设计调度程序时需要优先考虑最重要的需求，然后再各种因素之间进行折中处理。

3 调度方法的分类对于大量的实时调度方法来说，主要存在以下几种划分方法：1、离线（off-line）和在线（on-line）调度根据获得调度信息的时机，调度算法可以分为离线调度和在线调度两类。

对于离线调度算法，运行过程中使用的调度信息在系统运行之前就确定了，如时间驱动的调度。

离线调度算法具有确定性，但缺乏灵活性，适用于特征能够预先确定，且不容易发生变化的应用。

在线调度算法的调度信息则在系统运行过程中动态获得，如优先级驱动的调度（如EDF,RMS等）。

在线调度算法在形成最佳调度决策上具有较大的灵活性。

2、抢占（preemptive）和非抢占（non-preemptive）调度根据任务在运行过程中能否被打断的处理情况。

吉林⼤学操作系统上机（实验⼆：处理机调度——实时调度算法EDF和RMS）每做⼀个实验都不禁感叹奇妙⾮常，以下仅为学习记录，不⾜出错欢迎指出实验⼆处理机调度——实时调度算法EDF和RMS实验⽬的深⼊理解处理机调度算法，了解硬实时概念，掌握周期性实时任务调度算法EDF(Earliest Deadline First)和RMS(Rate Monotonic Scheduling)的可调度条件，并能在可调度情况下给出具体调度结果。

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

给定⼀组实时任务，按照EDF算法和RMS算法分别判断是否可调度，在可调度的情况下，创建⼀组⽤户级线程，分别代表各个实时任务，并按算法确定的调度次序安排各个线程运⾏，运⾏时在终端上画出其Gantt图。

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

实验准备EDF算法和RMS算法的可调度条件及调度原则。

在Linux环境中创建⽤户级线程的函数。

EDF算法和RMS的可调度条件及调度原则EDF(Earliest Deadline First)为可抢先式调度算法，其调度条件为sum(Ci/Ti)≤1；该算法是根据任务的开始截⽌时间来确定任务的优先级。

截⽌时间愈早，其优先级愈⾼。

该算法要求在系统中保持⼀个实时任务就绪队列，具有最早截⽌时间的任务排在队列的最前⾯。

调度程序在选择任务时，总是选择就绪队列中的第⼀个任务，为之分配处理机，使之投⼊运⾏。

最早截⽌时间优先算法既可⽤于抢占式调度，也可⽤于⾮抢占式调度⽅式中。

RMS算法为不可抢先调度算法，其调度条件为sum(Ci/Ti)≤n(exp(ln(2)/n)-1)。

任务按单调速率优先级分配（RMPA）的调度算法，称为单调速率调度（RMS）。

RMPA是指任务的优先级按任务周期T来分配。

它根据任务的执⾏周期的长短来决定调度优先级，那些具有⼩的执⾏周期的任务具有较⾼的优先级，周期长的任务优先级低。