EDF调度算法

最早截止期优先实时调度算法研究ResearchontheEarliestDeadlineFirstReal-TimeSchedulingAlgorithmPage2一、引入1、背景、目的及意义2、国内外研究概况二、实时系统模型和EDF算法1、实时系统模型2、EDF实时调度算法3、EDF调度算法的最优性4、硬实时周期任务集的可调度性判定三、最大可挪用时间1、问题描述2、最大可挪用时间的性质3、可延迟时间逼近算法4、仿真实验内容要点Page3内容要点四、硬实时周期任务和偶发任务混合调度1、空闲时间分布2、可挪用时间3、空闲挪用时间判定算法4、仿真实验五、资源访问控制1、访问控制协议2、可调度判定条件3、对比实验六、总结Page4一、引入1、背景、目的及意义在实时系统的理论研究中，按对计算完成时间的约束要求将实时任务分为硬实时任务和软实时任务。硬实时任务：规定时限内必须完成，否则会产生严重后果。e.g汽车的刹车制动系统任务、核反应堆的冷却系统任务；软实时任务：不强制性要求在规定时限内完成，但若错过其截止时期会导致系统性能下降。e.g银行业务、电话网交换机；实时任务还可分为周期任务和非周期任务（亦称偶发任务）。Page5一、引入1、背景、目的及意义从实时系统理论的发展来看，主要有以下几个方面：硬实时周期任务的调度：主要在单处理器且只存在多个独立硬实时周期任务的条件下给出一种调度算法；在保证硬实时周期任务的时限要求前提下，考虑偶发任务、软实时任务的混合调度：对软实时任务的调度目标：对软实时非周期任务，提高它们的响应时间；对软实时周期任务，针对当错过截止期的软实时任务数达到一定比例后也是不能接受的情况，提出了保证一个软实时周期任务在任意连续m次任务中，至少有n次任务在截止期限内完成的调度要求，并将能满足这种调度要求的实时系统称为弱硬实时系统（e.g实时网络传输）。对偶发任务的调度目标：因为偶发任务也是硬实时任务，故需满足它们的时限要求并给出可调度性判定条件。Page6一、引入1、背景、目的及意义从实时系统理论的发展来看，主要有以下几个方面：有资源互斥的硬实时任务调度：提出几种资源互斥协议来防止优先级反转和死锁问题，并给出相应的可调度判定条件。多处理器实时任务调度，前面的研究都是假定系统中只有一个处理器，忽略实际复杂的因素，将注意力集中到调度算法、资源访问控制和可调度性分析判定的基本原理上。这部分将这些理论应用于包含多个处理器的实时系统中，并处理在单处理器系统中未出现的问题。Page7一、引入1、背景、目的及意义目前业界公认的已经成为工业标准的实时调度算法有两个：最优固定优先级调度算法：单调速率调度算法RM最优动态优先级调度算法：最早截止期优先调度算法EDFEDF不仅可调度硬实时周期任务，还可调度硬实时非周期任务（偶发任务），且调度硬实时周期任务集时，周期任务集总负载最大可达100%。这篇论文主要就是分析该调度算法的性质，特别是最大可挪用时间的性质和计算，及其在硬实时周期任务、偶发任务、软实时任务的混合调度，资源访问控制等领域的应用。通过改进混合调度算法和可调度性判定条件，来提高处理器利用率。Page8一、引入2、国内外研究概况实时调度算法在非实时系统中，经常采用时间片轮转算法等来对各任务进行调度，很显然这并不适合对时限有严格要求的实时系统。实时系统的调度算法按决策产生的时机可分为脱机调度（offline）和联机调度（online）。脱机调度：要求事先知道所有任务的运行参数才能做出最优的决策，需要整个系统的确定性是其最大缺点联机调度：在系统运行时根据已释放的任务来决策，目前使用最广泛的优先级驱动调度就是联机调度。Page9一、引入2、国内外研究概况优先级驱动调度可分为可抢占式和不可抢占式。因已经证明：所有非抢占的优先级驱动调度都不是最优的，只有可抢占的调度算法才可能达到最优的调度，故下面讨论的都是可抢占的优先级驱动调度。优先级驱动调度又可分为固定优先级和动态优先级。e.g单调速率调度算法RM根据周期任务的释放频率，即周期的长短来分配任务的优先级，周期越短的任务优先级越高。其可调度性判定的充要条件：周期任务集的负载U≤)12(nn,其中n为周期任务数，当n很大时，该右式趋近于0.693。Page10一、引入2、国内外研究概况当然，RM是基于这样一种比较理想的硬实时周期任务模型：i.所有的任务都是周期任务ii.所有的任务都是不相关的，即它们没有共享资源iii.所有任务都有一个固定的执行时间或最大执行时间iv.所有任务的相对截止时间都等于它们的周期v.所有任务都是可抢占的vi.系统只有一个处理器注：若iv不成立，则RM不是最优的固定优先级调度算法。这事可采用另一种算法：时限单调(deadlinemonotonic)调度算法DM，其按任务的相对时限来分配优先级：相对时限越短，优先级越高。Page11一、引入2、国内外研究概况在同样的系统模型下，也存在动态优先级的调度算法：Earliestdeadlinefirst,EDFEDF按实时任务截止期的远近来分配优先级，任何时刻总是总是运行优先级最高的任务，即总是优先运行最紧迫的任务。EDF对于硬实时周期任务或硬实时非周期任务的调度来说都是最优的动态优先级调度算法。Page12一、引入2、国内外研究概况还有其他的动态优先级调度算法，e.g最小空闲时间优先（LeastSlackTimeFirst,LST）算法。一个任务在t时刻的空闲时间等于：截止时刻－t－该任务的剩余执行时间虽然LST也是具有最优性，但需随时监视所有就绪任务，运行时的开销较大，且如果两个任务的空闲时间接近，很容易产生调度的颠簸现象，所以实际使用中一般不适用。Page13一、引入2、国内外研究概况软实时任务和偶发任务的调度因为软实时任务允许运行时间错过截止期，所以其调度目标是在保证满足硬实时周期任务的时限前提下，提高软实时任务的响应时间。目前主要的调度算法有：ii.轮询服务器法iii.挪用法i.后台运行法Page14一、引入2、国内外研究概况i.后台运行法：在没有硬实时任务运行时轮流运行软实时任务，即把软实时任务当作优先级最低的后台任务运行，实现简单，但响应时间十分不理想。ii.轮询服务器法：增加一个用来执行软实时任务的周期任务，根据采用的某种硬实时周期任务调度算法，确保把这个周期任务加入到已有的硬实时周期任务集中仍然满足可调度条件。这个周期任务作为一个轮询的服务器程序（pollingserver），它将按先来先服务的方式来运行软实时任务，当这个服务程序的执行时间耗尽时就必须让出处理器直到下一轮再运行。Page15一、引入2、国内外研究概况当该服务程序在某处轮询中发现没有软实时任务，如果简单的放弃执行，挂起自己直到下一个周期，那么如果有马上到来的软实时任务就会被延迟执行，而如果保留轮询程序的执行时间预算，并在这段时间内有软实时任务到来时允许利用保留的带宽运行，就可能缩短软实时任务的响应时间。另外，关于如何保留这些未用完的带宽又可有可延期服务器（deferableserver,DS）和间发服务器（sporadicserver,SS）等算法。其中SS算法已经成为POXIC实时系统标准的一部分(POXIC_SCHED_SPORADIC）。采用带宽保留的轮询服务器法比后台运行法的响应时间更好，但已被证明：即使再复杂的带宽保留算法也无法达到最优的软实时任务的响应时间。Page16一、引入2、国内外研究概况iii.挪用法：又称空闲时间偷取法（slackstealingalgorithm）基本思想是在保证已有的硬实时周期任务的时限要求前提下，尽量推迟硬实时周期任务的运行，将推迟的这部分处理器空闲时间挪用出来运行非周期任务。挪用法的策略就是尽可能多尽可能早地偷取时间来执行软实时任务，从而可以达到最优的软实时任务响应时间。挪用法需要解决的关键问题是计算任意时刻可以挪用的时间，特别是任意时刻的最大可挪用时间。Page17一、引入2、国内外研究概况因为调度硬实时周期任务采用的调度算法的不同，可挪用时间及其计算方法都不同，所以挪用法又可分为基于固定优先级和基于动态优先级。e.g由Lehoczky等人提出的OFP：通过计算在一个超周期(hyperperiod)中每个任务的延迟时间来得到最大的可挪用时间；基于固定优先级：由何军等人提出的ODD等。但是这类算法由于采用固定优先级调度算法，硬实时周期任务集的最大允许负载较低，从而也延迟了软实时任务的响应时间。而使用动态优先级调度算法时，负载最高可达100%，所以在相同的系统负载下基于动态优先级调度的可挪用时间较大。Page18一、引入2、国内外研究概况基于动态优先级：ISA算法，由涂刚等人提出的一种基于EDF的算法，并证明了采用该算法可以达到软实时任务的最优响应时间。然而，使用动态优先级调度时，周期任务集的最大可挪用时间计算比较复杂，现有的算法多是近似计算，如Buttazzo的TB(N)算法、Ripoll的EESS算法。对于偶发任务的调度虽然也可采用上述的软实时任务的调度算法，但是它们都不保证满足偶发任务的时限要求，而且也没给出关键的可调度性判定条件。Page19一、引入2、国内外研究概况资源访问控制上述研究中的系统模型都假定各个实时任务之间是完全不相关的，但是在实际的系统中有许多的公共资源，比如消息队列、网络缓冲区和硬件设备，这些资源可以提供给多个任务访问，但不能被多个任务同时访问。在实时系统中考虑多个相关的实时任务调度并引入锁的机制会导致优先级反转现象：假如根据优先级驱动的调度算法安排一个高优先级的任务运行，当这个任务访问一个互斥资源时，如果这个资源已被另一个低优先级任务占用，那么这个高优先级的任务将阻塞，而这个低优先级任务将运行，这显然违背了调度算法本来的安排。Page20一、引入2、国内外研究概况失控的优先级反转：在上述的情况下，如果这时再出现一个优先级介于这两个任务之间的实时任务，那么这个实时任务就会抢占低优先级的任务运行，这也间接阻塞了前面所提到的那个高优先级任务，即使这个任务与那个高优先级任务之间是没有资源相关的，但如果频繁出现这种优先级介于低优先级和高优先级之间的实时任务，那么这个阻塞时间将一直延长，且其长短是无法预测的，这种情况被认为是失控的优先级反转。优先级反转及其失控情况可能导致本来满足可调度性判定条件的任务集出现错过截止期的情况。另外，引入锁的机制还可能出现死锁的情况，不过其可以通过规定必须按顺序给资源加锁来解决。Page21一、引入2、国内外研究概况资源访问控制协议：为了克服上述问题而提出。资源访问控制协议并不能消除优先级反转引起的阻塞，它只是使得高优先级任务被阻塞的时间是可预测的，而不是失控的。NPCS(NonPreemitiveCriticalProtocol)协议：不可抢占临界区协议，即当一个任务拥有某个互斥资源，那么它的优先级比所有任务的优先级都高。故也防止了死锁。但一个明显的缺点是，所有任务都会被其他请求某互斥资源的较低优先级的作业所阻塞，即使它们之间不存在资源冲突。当所有任务的资源需求都已知时，令拥有资源的任务以所有请求该资源的任务的最高优先级执行，便可以改进该协议（同样防止了死锁）。这就是Ada95的实时系统支持的最高限度优先级协议（ceilingpriorityprotocol)实际的工作方式。Page22一、引入2、国内外研究概况PIP(priorityinheritanceprotocol)：即优先级继承协议，是另一种简单的资源访问控制协议，用于可抢占式的优先级驱动调度算法。规则：当一个高优先级的任务因为加锁而被另一个低优先级任务阻塞时，这个低优先级的任务将继承这个高优先级任务的优先级别并运行，直到它解开这个锁才恢复之前的优先级。这个方法就避免了出现优先级反转导致的间接阻塞和失控现象，可以保证高优先级任务被阻塞的时间不会大于最外层临界区的持续时间。PIP与NPCS类似，不需要预先知道任何任务对资源的需求