静态优先级调度算法

❶ 静态抢占式优先级调度算法是如何进行的

按照优先级值的大小进行调度，选择优先级值大的作业优先调度。抢占式是指如果进入的作业的优先级数大于当前正在执行的作业的优先级数，就执行进入的作业，抢占了当前正在执行的作业的资源。
按照到达时间将作业放入就绪队列，当前作业执行过程中有作业进入，根据作业的优先级值进行判断，如果进入的作业的优先级值小于或等于当前执行的作业的优先级值，继续执行当前作业；如果进入的作业的优先级值大于当前执行的作业的优先级值，将资源给进入的作业，当前的作业就放入就绪队列队尾，此时还需要的服务时间为原服务时间-进入的作业的到达时间。之后，每到达一个作业就与当前执行的作业进行优先级值比较，优先级值大的优先执行。当当前执行的作业执行结束后，比较就绪队列中的作业的优先级值，优先级值大的优先执行。如此执行，直到就绪队列为空，结束调度。

❷ 进程调度的实时系统

最简单最直观的进程调度策略是基于优先级的调度，多数实时系统采用基于优先级的调度，每个进程根据它重要程度的不同被赋予不同的优先级，调度器在每次调度时，总选择优先级最高的进程开始执行.
首先要考虑的问题是如何分配优先级，对于进程优先级的分配可以采用静态和动态两种方式，静态优先级调度算法：这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级.静态优先级的分配可以根据应用的属性来进行，比如进程的周期，用户优先级，或者其它的预先确定的策略.单调率算法(RM)调度算法是一种典型的静态优先级调度算法，它根据进程的执行周期的长短来决定调度优先级，那些具有小的执行周期的进程具有较高的优先级.动态优先级调度算法：这种调度算法根据进程的资源需求来动态地分配进程的优先级，其目的就是在资源分配和调度时有更大的灵活性.在实时系统中，最早期限优先算法(EDF)算法是使用最多的一种动态优先级调度算法，该算法给就绪队列中的各个进程根据它们的截止期限(Deadline)来分配优先级，具有最近的截止期限的进程具有最高的优先级.
分配好优先级之后下一个要考虑的问题是何时让高优先级进程掌握CPU的使用权，这取决于操作系统的内核，有不可抢占式和可抢占式两种.
不可抢占式内核要求每个进程自我放弃CPU的所有权，各个进程彼此合作共享一个CPU.异步事件还是由中断服务来处理.中断服务可以使一个高优先级的进程由挂起状态变为就绪状态.但中断服务以后控制权还是回到原来被中断了的那个进程，直到该进程主动放弃CPU的使用权时，那个高优先级的进程才能获得CPU的使用权.这就出现了响应时间的问题，高优先级的进程已经进入了就绪状态但不能执行，这样进程的响应时间变得不再确定这与实时系统的要求不符，因此一般的实时操作系统都要求是可抢占式的内核，当一个运行着的进程使一个比它优先级高的进程进入了就绪态，当前进程的CPU使用权就被剥夺了，或者说被挂起了，那个高优先级的进程立刻得到了CPU的控制权，如果是中断服务子程序使一个高优先级的进程进入就绪态，中断完成时，中断了的进程被挂起，优先级高的那个进程开始运行.在这种内核设置下，多个进程可能处于并发的状态，这就出现了多个进程共享资源的情况，因此我们需要设置信号量来保证临界资源的正确使用，任何一个想使用临界资源的进程在进入临界区之前必须拥有使用临界资源的信号量，否则不可以执行临界区代码.
这样基于优先级的可抢占式进程调度策略就基本架构完成，但此时仍然有系统崩溃的危险，假设系统中有3个进程，分别为p1，p2和p3. p1的优先权高于p2，而p2的优先权高于p3.恰在此时p1和p2 因某种原因被阻塞，这时候系统调度p3执行.p3执行一段时间后，p1被唤醒.由于采取的是PBP的调度策略，因此p1抢占 p3的CPU， p1执行.p1执行一段时间后要进入临界区，但此时p3占有此临界资源的信号量.因此p1被阻塞，处于等待状态，等待p3 释放此信号量.经过这么一段时间后，p2此时此刻处于就绪状态.因此系统调度p2执行.如果p3在p2的执行期间一直没有能够被调度执行的话，那p1和p3将一直等到p2执行完后才能执行，p1更要等到p3释放它所把持的信号量才能执行；而这段时间完全有可能超出p1的Deadline，使得p1崩溃.我们看到在这个过程中，由于临界资源的使用问题使得优先级低的进程先于优先级高的进程先执行，这就出现了优先级反转的问题，从而造成了系统崩溃，对于这个问题可以采用优先级继承的办法来进行解决.在优先级继承方案中，当高优先级进程在等待低优先级的进程占有的信号量时，让低优先级进程继承高优先级进程的优先级，即把低优先级进程的优先权提高到高优先级进程的优先级；当低优先级进程释放高优先级进程等待的信号量时，立即把其优先权降低到原来的优先权.采用这种方法可以有效地解决上面所述的优先权反转的问题.当高优先级进程p1想要进入临界区时，由于低优先级进程p3占有这个临界资源的信号量，导致p1被阻塞.这时候，系统把p3的优先权升到p1的优先权，此时优先权处于p1和p3之间的进程p2，即使处于就绪状态也不可以被调度执行，因为此时p3的优先权已经高于p2，所以p3此时被调度执行.当p3释放p1需要的信号量时，系统立即把p3的优先权降到原来的高度，来保证p1和p2正常有序执行，有许多实时系统是采用这种方法来防止优先级反转的，如VXWORKS. 对于那些具有稳定，已知输入的简单系统，可以使用时间驱动的调度算法，它能够为数据处理提供很好的预测性.这种调度算法本质上是一种设计时就确定下来的离线的静态调度方法.在系统的设计阶段，在明确系统中所有的处理情况下，对于各个进程的开始，切换，以及结束时间等就事先做出明确的安排和设计.这种调度算法适合于那些很小的嵌入式系统，自控系统，传感器等应用环境.这种调度算法的优点是进程的执行有很好的可预测性，但最大的缺点是缺乏灵活性，并且会出现有进程需要被执行而 CPU 却保持空闲的情况.
对于不同要求下的实时系统可以采用不同的进程调度策略来进行设计，也可以将这些方法进行综合之后得到更适合的调度策略.

❸ 作业调度算法的优先级法

优先级算法（Priority Scheling）是多级队列算法的改进，平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢先式和非抢先式。 作业调度中的静态优先级大多按以下原则确定：
由用户自己根据作业的紧急程度输入一个适当的优先级。
由系统或操作员根据作业类型指定优先级。
系统根据作业要求资源情况确定优先级。
进程的静态优先级的确定原则：
按进程的类型给予不同的优先级。
将作业的情态优先级作为它所属进程的优先级。 进程的动态优先级一般根据以下原则确定：
根据进程占用有CPU时间的长短来决定。
根据就绪进程等待CPU的时间长短来决定。

❹ linux环境下的进程调度算法有哪些

第一部分： 实时调度算法介绍

对于什么是实时系统，POSIX 1003.b作了这样的定义：指系统能够在限定的响应时间内提供所需水平的服务。而一个由Donald Gillies提出的更加为大家接受的定义是：一个实时系统是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错。

实时系统根据其对于实时性要求的不同，可以分为软实时和硬实时两种类型。硬实时系统指系统要有确保的最坏情况下的服务时间，即对于事件的响应时间的截止期限是无论如何都必须得到满足。比如航天中的宇宙飞船的控制等就是现实中这样的系统。其他的所有有实时特性的系统都可以称之为软实时系统。如果明确地来说，软实时系统就是那些从统计的角度来说，一个任务（在下面的论述中，我们将对任务和进程不作区分）能够得到有确保的处理时间，到达系统的事件也能够在截止期限到来之前得到处理，但违反截止期限并不会带来致命的错误，像实时多媒体系统就是一种软实时系统。

一个计算机系统为了提供对于实时性的支持，它的操作系统必须对于CPU和其他资源进行有效的调度和管理。在多任务实时系统中，资源的调度和管理更加复杂。本文下面将先从分类的角度对各种实时任务调度算法进行讨论，然后研究普通的 Linux操作系统的进程调度以及各种实时Linux系统为了支持实时特性对普通Linux系统所做的改进。最后分析了将Linux操作系统应用于实时领域中时所出现的一些问题，并总结了各种实时Linux是如何解决这些问题的。

1. 实时CPU调度算法分类

各种实时操作系统的实时调度算法可以分为如下三种类别[Wang99][Gopalan01]：基于优先级的调度算法（Priority-driven scheling-PD）、基于CPU使用比例的共享式的调度算法（Share-driven scheling-SD）、以及基于时间的进程调度算法（Time-driven scheling-TD），下面对这三种调度算法逐一进行介绍。

1.1. 基于优先级的调度算法

基于优先级的调度算法给每个进程分配一个优先级，在每次进程调度时，调度器总是调度那个具有最高优先级的任务来执行。根据不同的优先级分配方法，基于优先级的调度算法可以分为如下两种类型[Krishna01][Wang99]：

静态优先级调度算法：

这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级。静态优先级的分配可以根据应用的属性来进行，比如任务的周期，用户优先级，或者其它的预先确定的策略。RM（Rate-Monotonic）调度算法是一种典型的静态优先级调度算法，它根据任务的执行周期的长短来决定调度优先级，那些具有小的执行周期的任务具有较高的优先级。

动态优先级调度算法：

这种调度算法根据任务的资源需求来动态地分配任务的优先级，其目的就是在资源分配和调度时有更大的灵活性。非实时系统中就有很多这种调度算法，比如短作业优先的调度算法。在实时调度算法中， EDF算法是使用最多的一种动态优先级调度算法，该算法给就绪队列中的各个任务根据它们的截止期限（Deadline）来分配优先级，具有最近的截止期限的任务具有最高的优先级。

1.2. 基于比例共享调度算法

虽然基于优先级的调度算法简单而有效，但这种调度算法提供的是一种硬实时的调度，在很多情况下并不适合使用这种调度算法：比如象实时多媒体会议系统这样的软实时应用。对于这种软实时应用，使用一种比例共享式的资源调度算法（SD算法）更为适合。

比例共享调度算法指基于CPU使用比例的共享式的调度算法，其基本思想就是按照一定的权重（比例）对一组需要调度的任务进行调度，让它们的执行时间与它们的权重完全成正比。

我们可以通过两种方法来实现比例共享调度算法[Nieh01]：第一种方法是调节各个就绪进程出现在调度队列队首的频率，并调度队首的进程执行；第二种做法就是逐次调度就绪队列中的各个进程投入运行，但根据分配的权重调节分配个每个进程的运行时间片。

比例共享调度算法可以分为以下几个类别：轮转法、公平共享、公平队列、彩票调度法（Lottery）等。

比例共享调度算法的一个问题就是它没有定义任何优先级的概念；所有的任务都根据它们申请的比例共享CPU资源，当系统处于过载状态时，所有的任务的执行都会按比例地变慢。所以为了保证系统中实时进程能够获得一定的CPU处理时间，一般采用一种动态调节进程权重的方法。

1.3. 基于时间的进程调度算法

对于那些具有稳定、已知输入的简单系统，可以使用时间驱动（Time-driven:TD）的调度算法，它能够为数据处理提供很好的预测性。这种调度算法本质上是一种设计时就确定下来的离线的静态调度方法。在系统的设计阶段，在明确系统中所有的处理情况下，对于各个任务的开始、切换、以及结束时间等就事先做出明确的安排和设计。这种调度算法适合于那些很小的嵌入式系统、自控系统、传感器等应用环境。

这种调度算法的优点是任务的执行有很好的可预测性，但最大的缺点是缺乏灵活性，并且会出现有任务需要被执行而CPU却保持空闲的情况。

2. 通用Linux系统中的CPU调度

通用Linux系统支持实时和非实时两种进程，实时进程相对于普通进程具有绝对的优先级。对应地，实时进程采用SCHED_FIFO或者SCHED_RR调度策略，普通的进程采用SCHED_OTHER调度策略。

在调度算法的实现上，Linux中的每个任务有四个与调度相关的参数，它们是rt_priority、policy、priority（nice）、counter。调度程序根据这四个参数进行进程调度。

在SCHED_OTHER 调度策略中，调度器总是选择那个priority+counter值最大的进程来调度执行。从逻辑上分析，SCHED_OTHER调度策略存在着调度周期（epoch），在每一个调度周期中，一个进程的priority和counter值的大小影响了当前时刻应该调度哪一个进程来执行，其中 priority是一个固定不变的值，在进程创建时就已经确定，它代表了该进程的优先级，也代表这该进程在每一个调度周期中能够得到的时间片的多少； counter是一个动态变化的值，它反映了一个进程在当前的调度周期中还剩下的时间片。在每一个调度周期的开始，priority的值被赋给 counter，然后每次该进程被调度执行时，counter值都减少。当counter值为零时，该进程用完自己在本调度周期中的时间片，不再参与本调度周期的进程调度。当所有进程的时间片都用完时，一个调度周期结束，然后周而复始。另外可以看出Linux系统中的调度周期不是静态的，它是一个动态变化的量，比如处于可运行状态的进程的多少和它们priority值都可以影响一个epoch的长短。值得注意的一点是，在2.4以上的内核中， priority被nice所取代，但二者作用类似。

可见SCHED_OTHER调度策略本质上是一种比例共享的调度策略，它的这种设计方法能够保证进程调度时的公平性--一个低优先级的进程在每一个epoch中也会得到自己应得的那些CPU执行时间，另外它也提供了不同进程的优先级区分，具有高priority值的进程能够获得更多的执行时间。

对于实时进程来说，它们使用的是基于实时优先级rt_priority的优先级调度策略，但根据不同的调度策略，同一实时优先级的进程之间的调度方法有所不同：

SCHED_FIFO：不同的进程根据静态优先级进行排队，然后在同一优先级的队列中，谁先准备好运行就先调度谁，并且正在运行的进程不会被终止直到以下情况发生：1.被有更高优先级的进程所强占CPU；2.自己因为资源请求而阻塞；3.自己主动放弃CPU（调用sched_yield）；

SCHED_RR：这种调度策略跟上面的SCHED_FIFO一模一样，除了它给每个进程分配一个时间片，时间片到了正在执行的进程就放弃执行；时间片的长度可以通过sched_rr_get_interval调用得到；

由于Linux系统本身是一个面向桌面的系统，所以将它应用于实时应用中时存在如下的一些问题：

Linux系统中的调度单位为10ms，所以它不能够提供精确的定时；

当一个进程调用系统调用进入内核态运行时，它是不可被抢占的；

Linux内核实现中使用了大量的封中断操作会造成中断的丢失；

由于使用虚拟内存技术，当发生页出错时，需要从硬盘中读取交换数据，但硬盘读写由于存储位置的随机性会导致随机的读写时间，这在某些情况下会影响一些实时任务的截止期限；

虽然Linux进程调度也支持实时优先级，但缺乏有效的实时任务的调度机制和调度算法；它的网络子系统的协议处理和其它设备的中断处理都没有与它对应的进程的调度关联起来，并且它们自身也没有明确的调度机制；

3. 各种实时Linux系统

3.1. RT-Linux和RTAI

RT -Linux是新墨西哥科技大学（New Mexico Institute of Technology）的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是，为了在Linux系统中提供对于硬实时的支持，它实现了一个微内核的小的实时操作系统（我们也称之为RT-Linux的实时子系统），而将普通Linux系统作为一个该操作系统中的一个低优先级的任务来运行。另外普通Linux系统中的任务可以通过FIFO和实时任务进行通信。RT-Linux的框架如图 1所示：

图 1 RT-Linux结构

RT -Linux的关键技术是通过软件来模拟硬件的中断控制器。当Linux系统要封锁CPU的中断时时，RT-Linux中的实时子系统会截取到这个请求，把它记录下来，而实际上并不真正封锁硬件中断，这样就避免了由于封中断所造成的系统在一段时间没有响应的情况，从而提高了实时性。当有硬件中断到来时， RT-Linux截取该中断，并判断是否有实时子系统中的中断例程来处理还是传递给普通的Linux内核进行处理。另外，普通Linux系统中的最小定时精度由系统中的实时时钟的频率决定，一般Linux系统将该时钟设置为每秒来100个时钟中断，所以Linux系统中一般的定时精度为 10ms，即时钟周期是10ms，而RT-Linux通过将系统的实时时钟设置为单次触发状态，可以提供十几个微秒级的调度粒度。

RT-Linux实时子系统中的任务调度可以采用RM、EDF等优先级驱动的算法，也可以采用其他调度算法。

RT -Linux对于那些在重负荷下工作的专有系统来说，确实是一个不错的选择，但他仅仅提供了对于CPU资源的调度；并且实时系统和普通Linux系统关系不是十分密切，这样的话，开发人员不能充分利用Linux系统中已经实现的功能，如协议栈等。所以RT-Linux适合与工业控制等实时任务功能简单，并且有硬实时要求的环境中，但如果要应用与多媒体处理中还需要做大量的工作。

意大利的RTAI( Real-Time Application Interface )源于RT-Linux，它在设计思想上和RT-Linux完全相同。它当初设计目的是为了解决RT-Linux难于在不同Linux版本之间难于移植的问题，为此，RTAI在 Linux 上定义了一个实时硬件抽象层，实时任务通过这个抽象层提供的接口和Linux系统进行交互，这样在给Linux内核中增加实时支持时可以尽可能少地修改 Linux的内核源代码。

3.2. Kurt-Linux

Kurt -Linux由Kansas大学开发，它可以提供微秒级的实时精度[KurtWeb] [Srinivasan]。不同于RT-Linux单独实现一个实时内核的做法，Kurt -Linux是在通用Linux系统的基础上实现的，它也是第一个可以使用普通Linux系统调用的基于Linux的实时系统。

Kurt-Linux将系统分为三种状态：正常态、实时态和混合态，在正常态时它采用普通的Linux的调度策略，在实时态只运行实时任务，在混合态实时和非实时任务都可以执行；实时态可以用于对于实时性要求比较严格的情况。

为了提高Linux系统的实时特性，必须提高系统所支持的时钟精度。但如果仅仅简单地提高时钟频率，会引起调度负载的增加，从而严重降低系统的性能。为了解决这个矛盾， Kurt-Linux采用UTIME所使用的提高Linux系统中的时钟精度的方法[UTIMEWeb]：它将时钟芯片设置为单次触发状态（One shot mode），即每次给时钟芯片设置一个超时时间，然后到该超时事件发生时在时钟中断处理程序中再次根据需要给时钟芯片设置一个超时时间。它的基本思想是一个精确的定时意味着我们需要时钟中断在我们需要的一个比较精确的时间发生，但并非一定需要系统时钟频率达到此精度。它利用CPU的时钟计数器TSC (Time Stamp Counter)来提供精度可达CPU主频的时间精度。

对于实时任务的调度，Kurt-Linux采用基于时间（TD）的静态的实时CPU调度算法。实时任务在设计阶段就需要明确地说明它们实时事件要发生的时间。这种调度算法对于那些循环执行的任务能够取得较好的调度效果。

Kurt -Linux相对于RT-Linux的一个优点就是可以使用Linux系统自身的系统调用，它本来被设计用于提供对硬实时的支持，但由于它在实现上只是简单的将Linux调度器用一个简单的时间驱动的调度器所取代，所以它的实时进程的调度很容易受到其它非实时任务的影响，从而在有的情况下会发生实时任务的截止期限不能满足的情况，所以也被称作严格实时系统（Firm Real-time）。目前基于Kurt-Linux的应用有：ARTS（ATM Reference Traffic System）、多媒体播放软件等。另外Kurt-Linux所采用的这种方法需要频繁地对时钟芯片进行编程设置。

3.3. RED-Linux

RED -Linux是加州大学Irvine分校开发的实时Linux系统[REDWeb][ Wang99]，它将对实时调度的支持和Linux很好地实现在同一个操作系统内核中。它同时支持三种类型的调度算法，即：Time-Driven、 Priority-Dirven、Share-Driven。

为了提高系统的调度粒度，RED-Linux从RT-Linux那儿借鉴了软件模拟中断管理器的机制，并且提高了时钟中断频率。当有硬件中断到来时，RED-Linux的中断模拟程序仅仅是简单地将到来的中断放到一个队列中进行排队，并不执行真正的中断处理程序。

另外为了解决Linux进程在内核态不能被抢占的问题， RED-Linux在Linux内核的很多函数中插入了抢占点原语，使得进程在内核态时，也可以在一定程度上被抢占。通过这种方法提高了内核的实时特性。

RED-Linux的设计目标就是提供一个可以支持各种调度算法的通用的调度框架，该系统给每个任务增加了如下几项属性，并将它们作为进程调度的依据：

Priority：作业的优先级；

Start-Time：作业的开始时间；

Finish-Time：作业的结束时间；

Budget：作业在运行期间所要使用的资源的多少；

通过调整这些属性的取值及调度程序按照什么样的优先顺序来使用这些属性值，几乎可以实现所有的调度算法。这样的话，可以将三种不同的调度算法无缝、统一地结合到了一起。

❺ 什么是静态调度算法

静态调度算法是调度之前制定好调度策略，调度过程庆源缺中按照预先制定的策略进行调度，调度过程中不考虑当前各服务器、网关或链路的实际负载情况及可负载的能力。由于调度不随着当前的负载情况改变而改变，因此称为静态调度算法。算法特点是誉辩实现简单、调度快捷。静态调度算法主要代表有：轮转调度算法、加权轮转调度算法、随机调度算法、加权随机调度算法、基于源地址哈希调度算法、基于目的地址哈希调度算法、裂举基于源地址端口哈希调度算法。

❻ 什么rm调度算法

一个任务的响应时间(response time)是指一个任务请求, 这个任务实际完成的时间跨度. 在静态调度中, 任务的临界时刻(critical instant)这个概念被首先提出来. 它被定义为一个特定的时刻, 如果在这个时刻有这个任务的请求, 那么这个任务就会需要最大的响应时间. 由此得出 定理1: 一个任务的临界时间就是比这个任务优先级高的所有任务同时发出请求的时刻. 定理1的价值在于它找到了一个证明一个调度算法能否调度任一任务集充分必要条件, 那就是所有任务同时请求执行的时的情况下每个任务仍能满足各自的期限, 那么这个任务集就可以被这个调度算法调度. 有了这个推论, 我们就可以证明RM调度的最优性了. 定理2: 如果一个任务集能够被静态调度, 那么RMS算法就能够调度这个任务集. 从这个意义上说, RMS是最优的静态调度算法. 这个定理的证明方法就是有名的交换法. 证明思路如下: 假设一个任务集S采用其他静态优先级算法可以调度,那么总有这样两个优先级相邻的任务i和j, 有Ti>Tj,而Pi≤Pj.把Ti和Tj的优先级Pi和Pj互换,明显可以看出这时S仍然可以调度, 因为在所有任务同时请求的情况下, 交换这两个任务不会影响其它任务的完成时间, 同时这两个任务都可以在各自期限内完成. 按照这样的方法,其他任何静态优先级调度最终都可以转换成RM调度. RMS已被证明是静态最优调度算法, 开销小, 灵活性好, 是实时调度的基础性理论。即使系统瞬时过载, 也完全可预测哪些任务丢失时限。缺点是处理机利用率较低, 最坏的情况下，当n→∞时, 不超过ln2 (≈ 70%)。另外, RMS是充分但非必要条件。而在一般情况下，对于随机的任务集大约只有88%. 70%或者88%的处理器利用率对于许多实时应用来说是一个严重的限制，动态调度算法如最早截止期最先（earliest deadline first，EDF）或者最少空闲时间最先（least laxity first，LLF）已经被证明是最优的，并且能够实现100% 的处理器利用率. 具有资源同步约束的RMS调度 当实时任务间共享资源时, 可能出现低优先级任务不可预测地阻塞高优先级任务执行的情况, 叫优先级倒置。这时RMS 算法不能保证任务集的调度, 必须使用有关协议控制优先级的倒置时间。常用的协议有优先级顶级协议和堆资源协议, 使用这些协议可使优先级的倒置时间最多为一个资源临界段的执行时间, 并且不会发生死锁。 基于RMS 的非周期任务的调度 实时系统中的非周期任务可采用延迟服务器算法或随机服务器算法进行调度。它们的最大特点是可在周期任务的实时调度环境下处理随机请求。两者的基本思想是将非周期任务转化成周期任务, 再利用RMS算法进行调度。前者用一个或几个专用的周期任务执行所有非周期任务, 这种周期任务叫非周期任务服务器。根据周期大小,服务器有固定优先级, 服务器的执行时间被称为预算, 它在每个服务器周期Ts 的起点补充。只要服务器有充足的预算, 就可在其周期内为非周期任务服务。该算法实现简单, 但可调度性分析较难, 有时会出现抖动, 可能发生一个非周期任务在相邻两个服务器周期中连续执行2倍预算的现象, 与RMS理论不符, 需要适当修改RMS算法。随机服务器算法与延迟服务器算法相似, 但预算不是在每个周期起点补充, 而是在预算消耗Ts时间之后再补充。该算法与RMS分析算法一致, 但实现复杂。 EDF最早截止时间优先算法（EDF）也称为截止时间驱动调度算法（DDS），是一种动态调度算法。EDF指在调度时，任务的优先级更具任务的截止时间动态分配。截止时间越短，优先级越高。EDF有如下定理： 定理2：如果一个任务集按EDF算法调度，当且仅当U<=1。 EDF的特点(1) 任务模型: 与RMS 调度相同。 (2) 优先级分配方法: 动态分配, 距要求时限所剩时间越短优先级越高。 理论上，EDF和LLF算法都是单处理器下的最优调度算法。但是由于EDF和LLF在每个调度时刻都要计算任务的deadline或者空闲时间，并根据计算结果改变任务优先级，因此开销大、不易实现，其应用受到一定限制。多处理器实时调度