第8章 处理器管理

第2版周苏机械工业出版社·2023操作系统原理第8章

处理器管理Chapter8:Processormanagement第8章处理器管理在多道程序设计系统的运行过程中，内存中有多个进程，每个进程或者正在处理器上运行，或者正在等待某些事件的发生（比如I/O完成）。处理器（或处理器组）通过执行某个进程而保持忙状态，此时其他进程处于等待状态。多道程序设计的关键是调度，比较典型的调度有四种类型（见表8-1）。我们来分析三种类型的处理器调度，并给出它们之间的关联性。第8章处理器管理表8-1调度的类型长程调度和中程调度主要是由与系统并发度相关的性能来驱动的，系统并发度是指处于等待处理器执行的进程的个数。我们先考虑在单处理器系统中的调度情况，这是由于多处理器的使用增加了额外的复杂性，而从单处理器着眼可以更清楚地看到调度算法之间的区别。目录/Contents01020304处理器调度的类型调度算法多处理器调度实时调度01处理器调度的类型Thetypeofprocessorscheduling8.1处理器调度的类型处理器调度的目标是以满足系统目标（如响应时间、吞吐率、处理器效率）的方式，把进程分配到一个或多个处理器中执行。在许多系统中，这个调度活动被分成三个独立的功能：长程、中程和短程调度，以表明在执行这些功能时的相对时间比例。8.1处理器调度的类型图8-1将调度功能结合到进程状态转换图中。创建新进程时，执行长程调度，它决定是否把进程添加到当前活跃的进程集合中。中程调度是交换功能的一部分，它决定是否把进程添加到那些至少部分在内存中并且可以被执行的进程集合中。短程调度真正决定下一次执行哪一个就绪进程。图8-1调度和进程状态转换8.1处理器调度的类型右图重新组织了进程状态转换图，用于表示调度功能的嵌套。

图8-2调度的层次8.1处理器调度的类型由于调度决定了哪个进程必须等待、哪个进程可以继续运行，因此它影响着系统的性能。这一点可以在图8-3中看出，该图给出了在一个进程状态转换过程中所涉及的队列。为简单起见，图8-3中给出一个新进程直接到达就绪态的情况，而图8-1和图8-2给出了到达就绪态和就绪/挂起态这两种不同情况。从根本上说，调度属于队列管理方面的问题，用来在排队环境中减少延迟和优化性能。图8-3调度的队列图长程调度程序控制着系统的并发度，一旦允许进入，一个作业或用户程序就成为一个进程，并被添加到供短程调度程序使用的队列中等待调度。中程调度是交换功能的一部分。典型情况下换入决定取决于管理系统并发度的需求。短程调度程序也称为分派程序，它执行得最频繁，并且精确地决定下一次执行哪一个进程。长程调度短程调度中程调度8.1处理器调度的类型8.1.1长程调度长程调度程序控制着系统的并发度，一旦允许进入，一个作业或用户程序就成为一个进程，并被添加到供短程调度程序使用的队列中等待调度。在某些系统中，一个新创建的进程开始处于被换出状态，被添加到供中程调度程序使用的队列中等待调度。在批处理系统或者操作系统的批处理部分中，新提交的作业被发送到磁盘，并保存在一个批处理队列中。在长程调度程序运行的时候，从队列中创建相应的进程。这里涉及两个决策，调度程序必须决定什么时候操作系统能够接纳一个进程或者多个进程；同时，调度程序必须决定接受哪个作业或哪些作业，并将其转变成进程。8.1.1长程调度关于何时创建一个新进程的决策通常由要求的系统并发度来驱动。创建的进程越多，每个进程可以执行的时间所占百分比就越小（即更多进程竞争同样数量的处理器时间）。因此，为了给当前的进程集提供满意的服务，长程调度程序可能限制系统并发度。每当一个作业终止时，调度程序可决定增加一个或多个新作业。此外，如果处理器的空闲时间片超过了一定的阈值，也可能会启动长程调度程序。8.1.1长程调度关于下一次允许哪一个作业进入的决策可以基于简单的先来先服务（FCFS）原则，或者基于管理系统性能工具，其使用的原则可以基于优先级、期待执行时间和I/O需求。例如，如果信息是可以得到的，则调度程序可以试图混合处理器密集型和I/O密集型的进程。如果一个进程主要担负计算工作，偶尔才会用到I/O设备，则该进程被视为处理器密集型；如果一个进程执行所使用的时间主要取决于等待I/O操作，则把它视为I/O密集型。同样，可以根据请求的I/O资源来做出决策，以达到I/O使用的平衡。8.1.1长程调度对于分时系统中的交互程序，用户试图连接到系统的动作可能产生一个进程创建的请求。分时用户并不是仅仅排队等待直到系统接受它们。相反，操作系统将接受所有的授权用户，直到系统饱和为止。这时，连接请求将会得到指示系统已经饱和要求用户重新尝试的消息。8.1.2中程调度中程调度是交换功能的一部分。典型情况下换入决定取决于管理系统并发度的需求。在不使用虚存存储的系统中，存储管理也是一个问题。因此，换入决策将考虑换出进程的存储需求。8.1.3短程调度从执行的频繁程度考虑，长程调度程序执行的频率相对较低，并且仅仅是粗略地决定是否接受新进程及接受哪一个。为进行交换决定，中程调度程序执行得略微频繁一些。短程调度程序也称为分派程序，它执行得最频繁，并且精确地决定下一次执行哪一个进程。当可能导致当前进程阻塞或可能抢占当前运行进程的事件发生时，调用短程调度程序。这类事件包括时钟中断、操作系统调用、I/O中断和信号（如信号量）。02调度算法Schedulingalgorithm8.2调度算法调度算法是指根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法，例如，在批处理系统中，为了照顾为数众多的段作业，应采用短作业优先的调度算法；又如在分时系统中，为了保证系统具有合理的响应时间，应当采用轮转法进行调度。在多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度；但也有些调度算法既可以用于作业调度，也可以用于进程调度。8.2调度算法短程调度的主要目标是按照优化系统一个或多个方面行为的方式来分配处理器时间。短程调度准则短程调度准则优先级的使用选择调度策略公平共享调度在系统中每个进程被指定一个优先级，调度程序总是优先选择具有较高优先级的进程。优先级的使用确定在就绪进程中选择哪一个进程在下一次执行。选择调度策略用户关心构成应用程序的一组进程如何执行。因此，基于进程组的调度策略是非常具有吸引力的。公平共享调度短程调度调度策略优先级公平共享8.2.1短程调度准则短程调度的主要目标是按照优化系统一个或多个方面行为的方式来分配处理器时间，需要对可能被评估的各种调度策略建立一系列规则。通常使用的调度准则可以按两维来分类。首先可以按面向用户和面向系统的准则来区分。面向用户的准则与单个用户或进程感知到的系统行为相关，例如交互式系统中的响应时间。响应时间是指从提交一条请求到输出响应所经历的时间间隔，这个时间量对用户是可见的，自然也是用户关心的，我们希望调度策略能给各种用户提供“好”的服务。对于响应时间，可以定义一个阈值，如2秒。那么调度机制的目标是使平均响应时间为2秒或小于2秒的用户数目达到最大。8.2.1短程调度准则另一个准则是面向系统的，即其重点是处理器使用的效果和效率。例如吞吐量，也就是进程完成的速度。吞吐量是关于系统性能的一个非常有意义的度量，我们总希望系统的吞吐量能达到最大。但是，该准则侧重于系统的性能，而不是提供给用户的服务。因此吞吐量是系统管理员所关注的。面向用户的准则在所有系统中都是非常重要的，而面向系统的准则在单用户系统中的重要性就低一些。在单用户系统中，实现处理器高利用率或高吞吐量可能并不重要，只要系统对用户应用程序的响应时间是可以接受的。8.2.1短程调度准则另一种划分的根据是这些准则是否与性能直接相关。与性能直接相关的准则是定量的，通常可以很容易地度量，例如响应时间和吞吐量。与性能无关的准则或者在本质上是定性的，或者不容易测量和分析，例如可预测性。我们希望提供给用户的服务能够随着时间的流逝展现给用户一贯相同的特性，而与系统执行的其他工作无关。在某种程度上，该准则可以通过计算负载函数的变化量来度量，但是这并不像度量吞吐率或响应时间关于工作量的函数那么直接。8.2.1短程调度准则表8-2总结了几种重要的调度准则，它们是互相依赖的，不可能同时都达到最优。例如，提供较好的响应时间可能需要调度算法在进程间频繁地切换，这就增加了系统开销，降低了吞吐量。因此，设计一个调度策略涉及在互相竞争的各种要求之间进行折中，根据系统的本质和使用情况，给各种要求设定相应的权值。在大多数交互式操作系统中，不论是单用户还是分时系统，适当的响应时间是关键需求。8.2.1短程调度准则表8-2调度准则8.2.2优先级的使用在许多系统中，每个进程都被指定一个优先级，调度程序总是优先选择具有较高优先级的进程。图8-4说明了优先级的使用。为了清楚起见，队列图被简化了，忽略了多个阻塞队列和挂起态的存在。不是提供一个就绪队列，而是提供了一组队列，按优先级递减的顺序排列：RQ0，RQ1，…，RQn。当进行一次调度选择时，调度程序从优先级最高的队列（RQ0）开始。如果该队列中有一个或多个进程，则使用某种调度策略选择其中一个；如果RQ0为空，则检查RQ1，接下来的处理类似。图8-4优先级排队8.2.2优先级的使用纯粹的优先级调度方案会出现的一个问题是，低优先级的进程可能会长时间处于饥饿状态。如果不希望这样，则一个进程的优先级应该随着它的时间或执行历史而变化。一般情况下，优先级数值越大，表示的进程优先级就越低。8.2.3选择调度策略表8-3给出了各种调度策略的一些简要信息。其中，选择函数确定在就绪进程中选择哪一个进程在下一次执行，这个函数可以基于优先级、资源需求或者该进程的执行特性。8.2.3选择调度策略表8-3各种调度策略的特点8.2.3选择调度策略对于最后一种情况，下面的三个量是非常重要的：w：到现在为止，在系统中停留的时间。e：到现在为止，花费的执行时间。s：进程所需要的总服务时间，包括e；通常，该数量必须进行估计或由用户提供。例如，选择函数max[w]表示先来先服务（FCFS）的原则。8.2.3选择调度策略决策模式说明选择函数在被执行的瞬间的处理方式，通常可分为以下两类：（1）非抢占：在这种情况下，一旦进程处于运行状态，它就不断执行直到终止，或者因为等待I/O，或者因为请求某些操作系统服务而阻塞自己。（2）抢占：当前正在运行的进程可能被操作系统中断，并转移到就绪态。关于抢占的决策可能是在一个新进程到达时，或者在一个中断发生后，把一个被阻塞的进程置为就绪态时，或者出现基于周期性的时间中断时。8.2.3选择调度策略与非抢占策略相比，抢占策略可能会导致较大的开销，但是可能会对所有进程提供较好的服务，因为它们避免了任何一个进程独占处理器太长的时间。此外，通过使用有效的进程切换机制（尽可能地获得硬件的帮助），以及提供比较大的内存，使得大部分程序都在内存中，可使抢占的代价相对比较低。8.2.3选择调度策略在描述各种调度策略时，使用下表中的进程集作为运行实例。可以把它们想象成批处理作业，服务时间是所需要的整个执行时间。另外也可以把这些视为正在进行的进程，需要以重复的方式轮流使用处理器和I/O。对后一种情况，服务时间表示一个周期所需要的处理器时间。在任何一种情况下，根据排队模型，该数值对应于服务时间。表8-4进程调度示例8.2.3选择调度策略对于表8-4的例子，图8-5显示了一个周期内每种策略的执行模式。由于每个进程的结束时间是确定的，根据这一点，可以确定周转时间。根据排队模型，周转时间就是驻留时间Tr，或这一项在系统中花费的总时间（等待时间+服务时间）。一个更有用的数字是归一化周转时间，它是周转时间与服务时间的比率，该值表示一个进程的相对延迟。在典型情况下，进程的执行时间越长，可以容忍的延迟时间就越长。该比率可能的最小值为1.0，值的增加对应于服务级别的减少。8.2.3选择调度策略

图8-5调度策略的比较8.2.3选择调度策略1.先来先服务最简单的策略是先来先服务（FCFS），也称为先进先出（FIFO）或严格排队方案。当每个进程就绪后加入就绪队列，当前正在运行的进程停止执行时，选择在就绪队列中存在时间最长的进程运行。FCFS执行长进程比执行短进程更好。使用FCFS的一个缺点是，它更有利于处理器密集型的进程。考虑有一组进程，其中有一个进程大多数时候都使用处理器（处理器密集型），还有许多进程大多数时候进行I/O操作（I/O密集型）。8.2.3选择调度策略如果一个处理器密集型的进程正在运行，则所有I/O密集型的进程都必须等待。有一些进程可能在I/O队列中（阻塞态），但是当处理器密集型的进程正在执行时，它们可能移回就绪队列。这时，大多数或所有I/O设备都可能是空闲的，即使它们可能还有工作要做。在当前正在运行的进程离开运行状态时，就绪的I/O密集型的进程迅速地通过运行态，又阻塞在I/O事件上。如果处理器密集型的进程也被阻塞了，则处理器空闲。因此，FCFS可能导致处理器和I/O设备都未得到充分利用。FCFS自身对于单处理器系统并不是很有吸引力的选择。但是，它通常与优先级策略相结合，以提供一种更有效的调度方法。因此，调度程序可以维护许多队列，每个优先级一个队列，每个队列中的调度基于先来先服务原则。在后面讨论反馈调度时，可以看到这类系统的一个例子。8.2.3选择调度策略2.轮转为了减少在FCFS策略下短作业的不利情况，一种简单的方法是采用使用基于时钟的抢占策略，这类方法中，最简单的是轮转（RR）算法。以一个周期性间隔产生时钟中断，当中断发生时，当前正在运行的进程被置于就绪队列中，然后基于FCFS策略选择下一个就绪作业运行。这种技术也称为时间片，因为每个进程在被抢占前都给定一片时间。8.2.3选择调度策略对于轮转法，最主要的设计问题是使用的时间段（片）的长度。如果这个长度非常短，则短作业会相对比较快地通过系统。另一方面，处理时钟中断、执行调度和分派函数都需要处理器开销。因此应该避免使用过短的时间片。一个有用的思想是时间片最好略大于一次典型的交互所需要的时间。如果小于这个时间，大多数进程都需要至少两个时间片。当一个时间片比运行时间最长的进程还要长时，轮转法就退化成FCFS。8.2.3选择调度策略轮转法在通用的分时系统或事务处理系统中都特别有效。但对于依赖处理器密集型的进程和I/O密集型的进程有所不同。通常，I/O密集型的进程比处理器密集型的进程使用处理器的时间（花费在I/O操作之间的执行时间）短。如果既有处理器密集型的进程又有I/O密集型的进程，就有可能发生如下情况：一个I/O密集型的进程只使用处理器很短的一段时间，然后因为I/O而被阻塞，等待I/O操作的完成，然后加入就绪队列；另一方面，一个处理器密集型的进程在执行过程中通常使用一个完整的时间片并立即返回到就绪队列中。因此，处理器密集型的进程不公平地使用了大部分处理器时间，从而导致I/O密集型的进程性能降低，I/O设备使用低效，响应时间变化大。8.2.3选择调度策略一种称为虚拟轮转法（VRR）的改进了的轮转法可以避免这种不公平性。新进程到达并加入就绪队列，是基于FCFS管理的。当一个正在运行进程的时间片用完后，它返回就绪队列。当一个进程为I/O而被阻塞时，它加入一个I/O队列。至此为止，一切都没有什么不同之处。它的新特点是解除了I/O阻塞的进程都被转移到一个FCFS辅助队列中。当进行一次调度决策时，辅助队列中的进程优先于就绪队列中的进程。当一个进程从辅助队列中调度时，它的运行时间不会长于基本时间段减去它上一次在就绪队列中被选择运行的总时间。性能研究表明，这种方法在公平性方面确实优于轮转法。8.2.3选择调度策略3.最短进程优先减少FCFS固有的对长进程的偏向的另一种方法是最短进程优先（SPN）策略。这是一个非抢占的策略，其原则是下一次选择预计处理时间最短的进程。因此，短进程将会越过长作业，跳到队列头。这样，短进程接受服务比在FCFS策略下要早。如果关注响应时间，整体性能也有显著的提高。但是，响应时间的波动也增加了，特别是对长进程的情况。因此可预测性降低了。8.2.3选择调度策略SPN策略的难点在于需要知道或至少需要估计每个进程所需要的处理时间。对于批处理作业，系统要求程序员估计该值，并提供给操作系统。如果程序员的估计远低于实际运行时间，系统就可能终止该作业。在生产环境中，相同的作业频繁地运行，可以收集关于它们的统计值。对交互进程，操作系统可以为每个进程保留一个运行平均值。SPN的风险在于只要持续不断地提供更短的进程，长进程就有可能饥饿。另一方面，尽管SPN减少了对长作业的偏向，但是由于缺少抢占机制，它在分时系统或事务处理环境下仍然不理想。8.2.3选择调度策略4.最短剩余时间最短剩余时间（SRT）是针对SPN增加了抢占机制的版本。在这种情况下，调度程序总是选择预期剩余时间最短的进程。当一个新进程加入就绪队列时，它可能比当前运行的进程有更短的剩余时间，因此，只要新进程就绪，调度程序就可能抢占当前正在运行的进程。和SPN一样，调度程序在执行选择函数时必须有关于处理时间的估计，并且存在长进程饥饿的危险。SRT不像FCFS那样偏向长进程，也不像轮转那样会产生额外的中断，从而减少了开销。另一方面，它必须记录过去的服务时间，从而增加了开销。从周转时间来看，SRT比SPN有更好的性能，因为相对于一个正在运行的长作业，短作业可以立即被选择运行。8.2.3选择调度策略5.最高响应比优先周转时间和实际服务时间的比率称为归一化周转时间，它可用于度量性能。对每个单独的进程，我们都希望该值最小，并且希望所有进程的平均值也最小。一般而言，我们事先并不知道服务时间是多少，但可以基于过去的历史或用户和配置管理员的某些输入值近似地估计它。和SRT、SPN一样，使用最高响应比（HRRN）策略需要估计预计的服务时间。8.2.3选择调度策略6.反馈法如果没有关于各个进程相对长度的任何信息，则SPN、SRT和HRRN都不能使用。另一种导致偏向短作业的方法是处罚运行时间较长的作业（FB），换句话说，如果不能获得剩余的执行时间，那就关注已经执行了的时间。8.2.3选择调度策略方法如下：调度基于抢占原则（按时间片）并且使用动态优先级机制。当一个进程第一次进入系统中时，它被放置在RQ0，如图8-4所示。当它第一次被抢占后并返回就绪状态时，它被放置在RQ1。在随后的时间里，每当它被抢占时，它被降级到下一个低优先级队列中。一个短进程很快会执行完，不会在就绪队列中降很多级。一个长进程会逐级下降。因此，新到的进程和短进程优先于老进程和长进程。在每个队列中，除了在优先级最低的队列中之外，都使用简单的FCFS机制。一旦一个进程处于优先级最低的队列中，它就不可能再降低，但是会重复地返回该队列，直到运行结束。因此，该队列可按照轮转方式调度。8.2.3选择调度策略这个方案有许多变体。一个简单的版本是使用和轮转法相同的方式——按照周期性的时间间隔执行抢占。存在问题是，长进程的周转时间可能惊人地增加。事实上，如果频繁地有新作业进入系统，就有可能出现饥饿的情况。为补偿这一点，可以按照队列改变抢占次数：从RQ0中调度的进程允许执行一个时间单位，然后被抢占；从RQ1中调度的进程允许执行两个时间单位，然后抢占：等等。一般而言，从RQi中调度的进程允许执行2i的时间，然后才被抢占。即使给较低的优先级分配较长的时间，长进程仍然有可能饥饿。一种可能的补救方法是当一个进程在它的当前队列中等待服务的时间超过一定的时间量后，把它提升到一个优先级较高的队列中。8.2.4公平共享调度前面的所有调度算法都是把就绪进程集合视为单一的进程池，从这个进程池中选择下一个要运行的进程。虽然该池可以按优先级划分成几个，但它们都是同构的。8.2.4公平共享调度但是，在多用户系统中，如果单个用户的应用程序或作业可以组成多个进程（或线程），就会出现传统的调度程序不认识的进程集合结构。从用户的角度看，他所关心的不是某个特定的进程如何执行，而是构成应用程序的一组进程如何执行。因此，基于进程组的调度策略是非常具有吸引力的，该方法通常称为公平共享调度。此外，即使每个用户用一个进程表示，这个概念也可以扩展到用户组。例如，在分时系统中，可能希望把某个部门的所有用户视为同一个组中的成员，然后进行调度决策，并给每个组中的用户提供相同的服务。因此，如果同一个部门中的大量用户登录到系统，则希望响应时间效果的降低主要影响到该部门的成员，而不会影响其他部门的用户。8.2.4公平共享调度“公平共享”表明了这类调度程序的基本原则。每个用户被指定了某种类型的权值，该权值定义了该用户对系统资源的共享，而且是作为在所有使用的资源中所占的比例来体现的。特别地，每个用户被分配了处理器的共享。这种方案或多或少以线性的方式操作，如果用户A的权值是用户B的两倍，那么从长期运行的结果来看，用户A可以完成的工作应该是用户B的两倍。公平共享调度程序的目标是监视使用情况，对那些相对于公平共享的用户占有较多资源的用户，调度程序分配以较少的资源，相对于公平共享的用户占有较少资源的用户，调度程序分配以较多的资源。03多处理器调度Multiprocessorscheduling8.3多处理器调度当一个计算机系统包含多个处理器时，在设计调度功能时就会产生一些新问题。本节首先给出关于多处理器的简单概述，然后分析设计进程级调度和线程级调度时的不同考虑。多处理器系统可以分为以下几类：（1）松耦合、分布式多处理器、集群：由一系列相对自治的系统组成，每个处理器有自己的内存和I/O通道。（2）专门功能的处理器：I/O处理器就是一个典型的例子。在这种情况下，有一个通用的主处理器，专用处理器受主处理器的控制，并给主处理器提供服务。（3）紧耦合多处理：由一系列共享同一内存并在操作系统控制下的处理器组成。在这里，我们主要关注的是最后一类系统，特别是与调度有关的问题。粒度可以根据粒度的不同来区分5类并行度。设计问题所采用的方法通常取决于应用程序的粒度等级和可用处理器的数目。进程调度有多条基于优先级的队列。在任何情况下，都可把系统视为多服务器排队结构。线程调度一个应用程序可以作为一组线程来实现，可以在同一个地址空间中协作和并发地执行。01020304调度8.3多处理器调度8.3.1粒度一种描述多处理器并把它和其他结构放置在一个上下文环境中的较好方法是，考虑系统中进程之间的同步粒度，或者说同步频率。我们可以根据粒度的不同来区分5类并行度。表8-5同步粒度和进程8.3.1粒度（1）无约束并行性。指进程间没有显式的同步，每个进程都代表独立的应用或作业。这类并行性的一个典型应用是分时系统。每个用户都执行一个特定的应用，如字处理或电子表格。多处理器和多道程序单处理器一样提供相同的服务。由于有多个处理器可用，因而用户的平均响应时间非常短。无约束并行有可能达到这样的性能，每个用户都如同在使用个人计算机或工作站。如果任何一个文件或信息被共享，则单个系统必须连接在一个有网络支持的分布式系统中。另一方面，在许多实例中，多处理器共享系统比分布式系统的成本效益更高，它允许节约使用磁盘和其他外围设备。8.3.1粒度（2）粗粒度和非常粗粒度并行性。粗粒度和非常粗粒度的并行，是指在进程之间存在着同步，但在一个比较或非常粗的级别上。这种情况可以简单地处理成一组运行在多道程序单处理器上的并发进程，在多处理器上对用户软件进行很少的改动或者不进行改动就可以提供支持。一般而言，使用多处理器体系结构，对所有需要通信或同步的并发进程集合都有好处。当进程间的交互不是很频繁时，分布式系统可以提供较好的支持。但是，当交互更加频繁时，分布式系统中的网络通信开销会抵消一部分潜在的加速比，在这种情况下，多处理器组织能提供最有效的支持。8.3.1粒度（3）中等粒度并行性。应用程序可以通过进程中的一组线程被有效地实现，在这种情况下，必须由程序员显式地指定应用程序潜在的并行性。典型情况下，为了达到中等粒度并行性的同步，在应用程序的线程之间，需要更高程度的合作与交互。尽管多处理器和多道程序单处理器都支持独立、非常粗和粗粒度的并行度，并基本不会对调度功能产生影响，但在处理线程调度时，仍然需要重新分析调度。由于应用程序中各个线程间的交互非常频繁，导致系统对一个线程的调度决策可能会影响整个应用的性能。（4）细粒度的并行性。代表比线程中的并行更加复杂的使用情况。迄今为止，这仍然是一个特殊的、被分割的领域，有许多不同的方法。8.3.2设计问题多处理器中的调度涉及三个相互关联的问题：（1）把进程分配到处理器。（2）在单个处理器上使用多道程序设计。（3）一个进程的实际分派。在讨论这三个问题时，必须牢记所采用的方法通常取决于应用程序的粒度等级和可用处理器的数目。8.3.2设计问题1.把进程分配到处理器假设多处理器的结构是统一的，即没有哪个处理器在访问内存和I/O设备时具有特别的物理优势，那么最简单的调度方法是把处理器视为一个资源池，并按照要求把进程分配到相应的处理器。随之而来的问题是，分配应该是静态的还是动态的？如果一个进程从被激活到完成，一直被分配给同一个处理器，那么就需要为每个处理器维护一个专门的短程队列。这个方法的优点是调度的开销比较小，因为对所有进程，关于处理器的分配只进行一次。同时，使用专用处理器允许一种称为组调度的策略。8.3.2设计问题静态分配的缺点是一个处理器可能处于空闲状态，这时它的队列为空，而另一个处理器却积压了许多工作。为防止这种情况发生，需要使用一个公共队列。所有进程都进入一个全局队列，然后调度到任何一个可用的处理器中。这样，在一个进程的生命周期中，它可以在不同的时间于不同的处理器上执行。在紧密耦合的共享存储器结构中，所有处理器都可以得到所有进程的上下文环境信息，因此，调度进程的开销与它被调度到哪个处理器无关。另一种分配策略是动态负载平衡，在该策略中，线程可以在不同处理器所对应的队列之间转移。Linux采用的就是这种动态分配策略。8.3.2设计问题不论是否给进程分配专用的处理器，都需要通过某种方法把进程分配给处理器。可以使用两种方法：主从式和对等式。在主从式结构中，操作系统的主要核心功能总是在某个特定的处理器上运行，其他处理器可能仅仅用于执行用户程序。主处理器负责调度作业。当一个进程被激活时，如果从处理器需要服务（例如一次I/O调用），它必须给主处理器发送一个请求，然后等待服务的执行。这种方法非常简单，几乎不需要对单处理器多道程序操作系统进行增强。由于处理器拥有对所有存储器和I/O资源的控制，因而可以简化冲突解决方案。这种方法有两个缺点：①主处理器的失败导致整个系统失败，②主处理器可能成为性能瓶颈。8.3.2设计问题在对等式结构中，操作系统可以在任何一个处理器中执行。每个处理器从可用进程池中进行自调度。这种方法增加了操作系统的复杂性，操作系统必须确保两个处理器不会选择同一个进程，进程也不会从队列中丢失，因此必须采用某些技术来解决和同步对资源的竞争请求。当然，在这两个极端之间还存在着许多方法。可以提供一个处理器子集，以专门用于内核处理而不是只用一个处理器。另一种方法是，基于优先级和执行历史来简单地管理内核进程和其他进程之间的需求差异。8.3.2设计问题2.在单个处理器上使用多道程序设计如果每个进程在其生命周期中都被静态地分配给一个处理器，就应该考虑一个新问题：该处理器支持多道程序吗，读者的第一反应可能是很奇怪为什么需要问这样的问题。这是因为如果把单个进程与处理器绑定，而该进程因为等待I/O或者因为考虑到并发/同步而频繁地被阻塞时，会产生处理器资源的浪费。8.3.2设计问题传统的多处理器处理的粗粒度或无约束同步粒度见表8-5，显然，单个处理器能够在许多进程间切换，以达到较高的利用率和更好的性能。但是，对于运行在多处理器系统中的中等粒度应用程序，当多个处理器可用时，要求每个处理器尽可能地忙就不再那么重要了。相反，我们更加关注如何能为应用提供最好的平均性能。由许多线程组成的一个应用程序的运行情况会很差，除非所有的线程都同时运行。8.3.2设计问题3.进程分派与多处理器调度相关的最后一个设计问题是选择哪一个进程运行。我们已经知道，在多道程序单处理器上，与简单的先来先服务策略相比较，使用优先级或者使用基于历史的高级调度算法可以提高性能。考虑多处理器时，这些复杂性可能是不必要的，还有可能起到相反的效果，相对比较简单的方法可能会更有效，而且开销也比较低。对于线程调度的情况，会出现比优先级和执行历史更重要的新问题。8.3.3进程调度在大多数传统的多处理器系统中，进程并不是被指定到一个专门处理器的。不是所有处理器只有一个队列，或者使用某种类型的优先级方案，而是有多条基于优先级的队列，并且都送进相同的处理器池中。在任何情况下，都可以把系统视为多服务器排队结构。8.3.3进程调度考虑一个双处理器系统，每个处理器的处理速率为单处理器系统中处理器处理速率的一半。一项研究关注进程服务时间，给出了FCFS调度、轮转法和最短剩余时间法的比较。进程服务时间可以用来度量整个作业所需要的处理器时间总量，或者该进程每次准备使用处理器时所需要的时间总量。对于轮转法而言，假设时间片的长度比上下文环境切换的开销大，而比平均服务时间短，其结果取决于服务时间的变化。该研究在各种情况下重复分析关于多道程序设计的程度的假设、I/O密集型和CPU密集型的进程和使用优先级，得出的一般结论是，对于双处理器，调度原则的选择没有在单处理器中显得重要。显然，当处理器的数目增加时，这个结论会更加确定。因此，在多处理器系统中使用简单的FCFS原则或者在静态优先级方案中使用FCFS就足够了。8.3.4线程调度线程执行的概念与进程中的定义是不同的。一个应用程序可以作为一组线程来实现，这些线程可以在同一个地址空间中协作和并发地执行。在单处理器中，线程可以用做辅助构造程序，并在处理过程中重叠执行I/O。由于进行线程切换的系统开销远远小于进程切换的系统开销，因此可以用很少的代价实现这些优点。在多处理器系统中，线程的全部能力得到了更好展现。在这个环境中，线程可以用于开发应用程序中真正的并行性。如果一个应用程序的各个线程同时在各个独立的处理器中执行，其性能就会得到显著提高。但是，对于需要在线程间交互的应用程序（中等粒度的并行度），线程管理和调度中很小的变化就会对性能产生重大的影响。8.3.4线程调度在多处理器线程调度和处理器分配的各种方案中，有4种比较突出的方法，即负载分配、组调度、专用处理器分配和动态调度。1.负载分配进程不是分配到一个特定处理器的。系统维护一个就绪线程的全局队列，每个处理器只要空闲就从队列中选择一个线程。这里使用术语负载分配来区分这种策略和负载平衡方案，负载平衡是基于一种比较永久的分配方案分配工作的。8.3.4线程调度这可能是最简单的方法，也是可以从单处理器环境中直接移用的方法。它有以下优点：·负载均匀地分布在各个处理器上，确保当有工作可做时，没有处理器是空闲的。·不需要集中调度器。当一个处理器可用时，操作系统调度例程就会在该处理器上运行，以选择下一个线程。·可以使用任何一种方案组织和访问全局队列，包括基于优先级的方案和考虑了执行历史或预计处理请求的方案。8.3.4线程调度对三种不同的负载分配方案分析如下：（1）先来先服务（FCFS）：当一个作业到达时，它的所有线程都被连续地放置在共享队列末尾。当一个处理器变得空闲时，它选择下一个就绪线程执行，直到完成或被阻塞。（2）最少线程数优先：共享就绪队列被组织成一个优先级队列，如果一个作业包含的未调度线程的数目最少，则给它指定最高的优先级。具有相同优先级的队列按作业到达的顺序排队。和FCFS一样，被调度的线程一直运行到完成或阻塞。（3）可抢占的最少线程数优先：最高的优先级给予包含的未被调度的线程数目最少的作业。对于刚到达的作业，如果包含的线程数目少于正在执行的作业，它将抢占属于这个被调度作业的线程。8.3.4线程调度通过使用模拟模型说明，对于很多种作业，FCFS优于上面列出的另两种策略。此外，还发现某些组调度通常优于加载共享。负载分配有以下缺点：·中心队列占据了必须互斥访问的存储器区域。因此，如果有许多处理器同时进行查找工作，就有可能成为瓶颈。当只有很少的几个处理器时，这不是什么大问题；但是，当多处理器系统包含了几十个甚至几百个处理器时，就可能真正出现瓶颈。·被抢占的线程可能不在同一个处理器上恢复执行。如果每个处理器都配备一个本地cache，缓存的效率会很低。8.3.4线程调度·如果所有线程被视为一个公共的线程池，则一个程序的所有线程不可能都同时获得对处理器的访问。如果一个程序的线程间需要高度的合作，所涉及的进程切换就会严重影响性能。8.3.4线程调度尽管可能存在许多缺点，负载分配仍然是当前多处理机系统中使用得最多的一种方案。Mach操作系统中使用了一种改进后的负载分配技术。操作系统为每个处理器维护一个本地运行队列和一个共享的全局运行队列。本地运行队列供临时绑定在某个特定处理器上的进程使用。处理器首先检查本地运行队列，使得绑定的线程绝对优先于未绑定的线程。关于使用绑定线程的一个例子是，用一个或多个处理器专门运行属于操作系统一部分的进程。另一个例子是，特定应用程序的线程可以分布在许多处理器上，通过附加适当的软件，可以提供对组调度的支持。8.3.4线程调度2.组调度一组相关的线程基于一对一的原则，同时调度到一组处理器上运行。这个概念早先就用在进程调度上，称为成组分配，它包括以下优点：·如果紧密相关的进程并行执行，同步阻塞可能会减少，而且可能只需要很少的进程切换，性能会提高。·调度开销可能会减少，因为一个决策可以同时影响许多处理器和进程。在多处理器中使用了协同调度这个术语。协同调度基于调度一组相关任务（称为特别任务）的概念。特别任务中的元素特别小，接近于后来线程的概念。8.3.4线程调度“组调度”已经应用于同时调度组成一个进程的一组线程。对于中等粒度到细粒度的并行应用程序，组调度是非常必要的，因为如果这种应用程序的一部分准备运行，而另一部分却还没有运行时，它的性能会严重地下降。它还对全体并行应用程序都有好处，即使那些对性能要求没有这么灵敏的应用程序也是如此。组调度的需要得到了广泛的认识，并且在许多多处理器操作系统中都得到了实现。8.3.4线程调度组调度提高应用程序性能的一个显著方式是使进程切换的开销最小。假设进程的一个线程正在执行，并且到达一点，必须与该进程的另一个线程在该处同步。如果这个线程未运行，但是在就绪队列中，则第一个线程被挂起，直到在其他处理器上进行了进程切换并得到了需要的线程。对于线程间需要紧密合作的应用程序，这种切换会严重地降低性能。合作线程的同时调度还可以节省资源分配的时间。例如，多个组调度的线程可以访问一个文件，而不需要在执行定位、读、写操作时进行锁定的额外开销。组调度的使用引发了对处理器分配的要求。一种可能的情况如下：假设有N个处理器和M个应用程序，每个应用程序有N个或少于N个线程。那么，使用时间片，每个应用程序将被给予M个处理器中可用时间的l/M。这个策略的效率可能很低。8.3.4线程调度3.专用处理器分配这种方法正好与负载分配的方法相反，它通过把线程指定到处理器来定义隐式的调度。每个程序在其执行过程中，被分配给一组处理器，处理器的数目与程序中线程的数目相等。当程序终止时，处理器返回到总的处理器池中，可供分配给另一个程序。给出组调度的一种极端形式，在一个应用程序执行期间，把一组处理器专门分配给这个应用程序。也就是说，当一个应用程序被调度时，它的每一个线程都被分配给一个处理器，这个处理器专门用于处理这个线程，直到应用程序运行结束。8.3.4线程调度这个方法看上去极端浪费处理器时间，如果应用程序的一个线程被阻塞，等待I/O或与其他线程的同步，则该线程的处理器一直处于空闲：处理器没有多道程序设计。以下两点可以在一定程度上解释使用这种策略的原因：（1）在一个高度并行的系统中，有数十个或数百个处理器，每个处理器只占系统总代价的一小部分，处理器利用率不再是衡量有效性或性能的一个重要因素。（2）在一个程序的生命周期中避免进程切换会加快程序的速度。8.3.4线程调度研究推断，比较有效的策略是将活跃线程的数目限制为不超过系统中处理器的数目。例如，大多数应用程序或者只有一个线程，或者可以使用任务队列结构，这种策略将提供对处理器资源更有效、更合理的使用。8.3.4线程调度专用处理器分配和组调度，在解决处理器分配问题时都对调度问题进行了抨击。可以看出，多处理器系统中的处理器分配问题更加类似于单处理器中的存储器分配问题，而不是单处理器中的调度问题。在某一给定的时刻，给一个程序分配多少个处理器，这个问题类似于在某一给定时刻，给一个进程分配多少页框。考虑一个类似于虚存中工作集的术语——活动工作集。活动工作集指的是，为了保证应用程序以可以接受的速度继续进行，在处理器上必须同时调度的最少数目的活动（线程）。8.3.4线程调度和存储器管理方案一样，调度活动工作集中所有元素失败时可能导致处理器抖动。当调度需要服务的线程，导致那些服务即将被用到的线程被取消调度时，就会发生这种情况。类似地，处理器碎片指当一些处理器剩余而其他处理器已被分配时，剩余的处理器无论是从数量上还是从适合程度上都难以支持正在等待的应用程序的需要。组调度和专用处理器分配的目的是避免这些问题。8.3.4线程调度4.动态调度在执行期间，进程中线程的数目可以改变。某些应用程序可能提供了语言和系统工具，允许动态地改变进程中的线程数目，这就使得操作系统可以通过调整负载情况来提高利用率。8.3.4线程调度一项相关研究提出了一种方法，使得操作系统和应用程序能够共同进行调度决策。操作系统负责把处理器分配给作业，每个作业通过把它的一部分可运行任务映射到线程，使用当前划分给它的处理器执行这些任务。关于运行哪个子集以及当该进程被抢占时应该挂起哪个线程之类的决策留给单个的应用程序（可能通过一组运行时库例程）。这种方法并不适合于所有的应用程序。某些应用程序可能会默认使用一个线程，而其他应用程序可以设计为引用操作系统的这种功能。8.3.4线程调度在这种方法中，操作系统的调度责任主要局限于处理器分配，并根据以下策略继续进行。当一个作业请求一个或多个处理器时（或者是因为作业第一次到达，或者是因为它的请求发生了变化）：（1）如果有空闲的处理器，则用它们满足请求。（2）否则，如果发请求的作业是新到达的，则从当前已分配了多个处理器的作业中分出一个处理器给这个作业。（3）如果这个请求的任何分配都不能得到满足，则它保持未完成状态，直到一个处理器变成可用，或者该作业废除了它的请求（例如，如果不再需要额外的处理器）。8.3.4线程调度当释放了一个或多个处理器（包括作业离开）时：（4）为这些处理器扫描当前未得到满足的请求队列。给表中每个当前还没有处理器的作业（也就是说，给所有处于等待的新到达的作业）分配一个处理器。然后再次扫描这个表，按FCFS原则分配剩下的处理器。研究中的分析表明，对可以采用动态调度的应用程序，这种方法优于组调度和专用处理器分配。但是，该方法的开销可能会抵消它的一部分性能优势。为证明动态调度的价值，需要在实际系统中不断体验。04实时调度Real-timescheduling8.4实时调度实时计算正在成为越来越重要的原则。操作系统，特别是调度器，可能是实时系统中最重要的组件。目前实时系统应用的例子包括实验控制、过程控制设备、机器人、空中交通管制、电信、军事指挥与控制系统，下一代系统还将包括自动驾驶汽车、具有弹性关节的机器人控制器、智能化生产中的系统查找、空间站和海底勘探等。8.4实时调度实时计算可以定义成这样的一类计算，即系统的正确性不仅取决于计算的逻辑结果，而且还依赖于产生结果的时间。我们可以通过定义实时进程或实时任务来定义实时系统。一般来说，在实时系统中，某些任务是实时任务，它们具有一定的紧急程度。这类任务试图控制外部世界发生的事件，或者对这些事件做出反应。由于这些事件是“实时”发生的，因而实时任务必须能够跟得上它所关注的事件。因此，通常给一个特定的任务制定一个最后期限，最后期限指定开始时间或结束时间。8.4实时调度这类任务可以分成硬实时任务或软实时任务两类。硬实时任务指必须满足最后期限的限制，否则会给系统带来不可接受的破坏或者致命的错误。软实时任务也有一个与之关联的最后期限，并希望能满足这个期限的要求，但这并不是强制的，即使超过了最后期限，调度和完成这个任务仍然是有意义的。实时任务的另一个特征是它们是周期的还是非周期的。非周期任务有一个必须结束或开始的最后期限，或者有一个关于开始时间和结束时间的约束。而对于周期任务，这个要求描述成“每隔周期T一次”或者“每隔T个单位”。特点特征实时限时单调优先实时操作系统的特征设计实时系统调度器时，最重要的是所有硬实时任务都在它们的最后期限内完成。限时调度大多数实时操作系统的设计目标是，尽可能快速地启动实时任务，因此强调快速中断处理和任务分派。优先级反转当系统环境迫使一个较高优先级的任务去等待一个较低优先级的任务时，优先级反转就会发生。实时操作系统的特点实时操作系统要具备5个方面的要求，即可确定性、可响应性、用户控制、可靠性和故障弱化操作。实时调度实时调度是计算机科学中最活跃的研究领域之一。速率单调调度为周期性任务解决多任务调度冲突的一种非常好的方法是速率单调调度，这种方案基于任务的周期指定优先级。8.3实时调度8.4.1实时操作系统的特点实时操作系统要具备5个方面的要求，即可确定性、可响应性、用户控制、可靠性和故障弱化操作。8.4.1实时操作系统的特点1.可确定性一个操作系统是可确定性的，在某种程度上是指它可以按照固定的、预先确定的时间或时间间隔执行操作。当多个进程竞争使用资源和处理器时间时，没有哪个系统是完全可确定的。在实时操作系统中，进程请求服务是用外部事件和时间安排来描述的。操作系统可以确定性地满足请求的程度首先取决于它响应中断的速度，其次取决于系统是否具有足够的能力在要求的时间内处理所有的请求。关于操作系统可确定性能力的一个非常有用的度量是，从高优先级设备中断到达到开始服务之间的延迟。在非实时操作系统中，这个延迟可以是几十到几百毫秒，而在实时操作系统中，这个延迟的上限可以从几微秒到l毫秒。8.4.1实时操作系统的特点2.可响应性一个相关但截然不同的特点是可响应性。确定性关注的是操作系统获知有一个中断之前的延迟，可响应性关注的是在知道中断之后操作系统为中断提供服务的时间。可响应性包括以下几方面：（1）最初处理中断并开始执行中断服务例程（ISR）所需要的时间总量。如果ISR的执行需要一次进程切换，那么需要的延迟将比在当前进程上下文环境中执行ISR的延迟长。（2）执行ISR所需要的时间总量，通常与硬件平台有关。（3）中断嵌套的影响。如果一个ISR可被另一个中断的到达中断，服务将被延迟。8.4.1实时操作系统的特点确定性和响应性共同组成了对外部事件的响应时间。对实时系统来说，响应时间的要求是非常重要的，因为这类系统必须满足系统外部的个体、设备和数据流所强加的时间要求。8.4.1实时操作系统的特点3.用户控制用户控制在实时操作系统中通常比在普通操作系统中更广泛。在典型的非实时操作系统中，用户要么对操作系统的调度功能没有任何控制，要么仅提供了概括性的指导，诸如把用户分成多个优先级组。但在实时系统中，允许用户细粒度地控制任务优先级是必不可少的。用户应该能够区分硬实时任务和软实时任务，并且在每一类中确定相对优先级。实时系统还允许用户指定一些特性，例如是使用页面调度还是使用进程交换、哪一个进程必须常驻内存、使用何种磁盘传输算法、不同优先级的进程各有哪些权限等。8.4.1实时操作系统的特点4.可靠性可靠性在实时系统中比在非实时系统中更重要。非实时系统中的暂时故障可以简单地通过重新启动系统来解决，多处理器非实时系统中的处理器失败可能导致服务级别降低，直到发生故障的处理器被修复或替换。但是实时系统是实时地响应和控制事件，性能的损失或降低可能产生灾难性的后果，例如从资金损失到毁坏主要设备甚至危及生命。8.4.1实时操作系统的特点5.故障弱化操作和其他领域一样，实时和非实时操作系统的区别只是一个程度问题，即使实时系统也必须设计成响应各种故障的模式。故障弱化操作指系统在故障时尽可能多地保存其性能和数据的能力。例如一个典型的传统UNIX系统，当它检测到内核中的数据错误时，给系统控制台产生一个故障信息，并为了以后分析故障，把内存中的内容转储到磁盘，然后终止系统的执行。与之相反，实时系统将尝试改正这个问题或者最小化它的影响并继续执行。一般来说，系统会通知用户或用户进程，它试图进行校正，并且可能在降低了的服务级别上继续运行。当需要关机时，必须维护文件和数据的一致性。8.4.1实时操作系统的特点故障弱化运行的一个重要特征称为稳定性。我们说一个实时系统是稳定的，是指如果当它不可能满足所有任务的最后期限时，即使总是不能满足一些不太重要任务的最后期限，系统也将首先满足最重要、优先级最高的任务的最后期限。8.4.2实时操作系统的特征为满足前面的要求，当前的实时操作系统典型地包括以下特征：（1）快速的进程或线程切换。（2）体积小（只具备最小限度的功能）。（3）迅速响应外部中断的能力。（4）通过诸如信号量、信号和事件之类的进程间通信工具，实现多任务处理。（5）使用特殊的顺序文件，可以快速存储数据。（6）基于优先级的抢占式调度。（7）最小化禁止中断的时间间隔。（8）用于使任务延迟一段固定的时间或暂停/恢复任务的原语。（9）特别的警报和超时设定。8.4.2实时操作系统的特征实时系统的核心是短程任务调度器。在设计这种调度器时，公平性和最小平均响应时间并不是最重要的，最重要的是所有硬实时任务都在它们的最后期限内完成（或开始），尽可能多的软实时任务也可以在它们的最后期限内完成（或开始）。大多数当代实时操作系统都不能直接处理最后期限，它们设计成尽可能地对实时任务做出响应，使得当临近最后期限时，一个任务能够迅速地被调度。从这一点看，实时应用程序在许多条件下都要求确定性的响应时间在几毫秒到小于l毫秒的范围内。前沿应用程序，如军用飞机模拟器，通常要求响应时间在10~100μs的范围内。8.4.2实时操作系统的特征图8-6显示了许多种可能性。在使用简单轮转调度的抢占式调度器中，实时任务将被加入就绪队列，等待它的下一个时间片，如图8-6（a）所示。在这种情况下，调度时间通常是实时应用程序难以接受的。

图8-6实时进程调度8.4.2实时操作系统的特征在非抢占式调度器中，可以使用优先级调度机制，给实时任务更高的优先级。在这种情况下，只要当前的进程阻塞或运行结束，就可以调度这个就绪的实时任务，如图8-6（b）所示。如果在临界时间中，一个比较慢的低优先级任务正在执行，就会导致几秒的延迟，同样，这种方法也是难以接受的：一种比较折中的方法是把优先级和基于时钟的中断结合起来。可抢占点按规则的间隔出现。当出现一个可抢占点时，如果有更高优先级的任务正在等待，则当前运行的任务被抢占。这就有可能抢占操作系统内核的部分任务。这类延迟大约为几毫秒，如图8-6（c）所示。8.4.2实时操作系统的特征尽管最后一种方法对某些实时应用程序已经足够了，但是对一些要求更苛刻的应用程序仍是不够的，这时常常采用一种称为立即抢占的方法。在这种情况下，操作系统几乎立即响应一个中断，除非系统处于临界代码保护区中。关于实时任务的调度延迟可以降低到100μs或更少。8.4.3实时调度实时调度是计算机科学中最活跃的研究领域之一。本节将给出各种实时调度方法的概述，并查看两类流行的调度算法。在考察实时调度算法时，可以观察到各种调度方法取决于：（1）一个系统是否执行可调度性分析；（2）如果执行，它是静态的还是动态的；（3）分析结果自身是否根据在运行时分派的任务产生一个调度或计划。8.4.3实时调度基于这些考虑，分以下几类算法进行说明：（1）静态表法：执行关于可行调度的静态分析。分析的结果是一个调度，它用于确定在运行时一个任务何时必须开始执行。（2）静态优先级抢占法：执行一个静态分析，但是没有制定调度，而是通过给任务指定优先级，使得可以使用传统的基于优先级的抢占式调度程序。（3）基于动态规划调度法：在运行时动态地确定可行性，而不是在开始运行前离线地确定（静态）。一个到达的任务，只有当能够满足它的时间约束时，才可以被接受执行。可行性分析的结果是一个调度或规划，可用于确定何时分派这个任务。（4）动态尽力调度法：不执行可行性分析。系统试图满足所有的最后期限，并终止任何已经开始运行但错过最后期限的进程。8.4.3实时调度静态表调度适用于周期性的任务。该分析的输入为周期性的到达时间、执行时间、周期性的最后结束期限和每个任务的相对优先级。调度器试图开发一种调度，使得能够满足所有周期性任务的要求。这是一种可预测的方法，但是不够灵活，因为任何任务需求的任何变化都需要重做调度。最早最后期限优先或其他周期性的最后期限技术都属于这类调度算法。8.4.3实时调度静态优先级抢占调度与大多数非实时多道程序系统中的基于优先级的抢占式调度所用的机制相同。在非实时系统中，各种因素都可能用于确定优先级。例如，在分时系统中，进程优先级的变化取决于它是处理器密集型的还是I/O密集型的。在实时系统中，优先级的分配与每个任务的时间约束相关。这种方法的一个例子是速率单调算法，它基于周期的长度给任务指定静态优先级。基于动态规划调度，在一个任务已到达但未执行时，试图创建一个包含前面被调度任务和新到达任务的调度。如果新到达的任务可以按这种方式调度：满足它的最后期限，而且之前被调度的任务也不会错过它的最后期限，则修改这个调度以适应新任务。8.4.3实时调度动态尽力调度是当前许多商用实时系统所使用的方法。当一个任务到达时，该系统根据任务的特性给它指定一个优先级，并通常使用某种形式的时限调度，如最早最后期限调度。一般来说，这些任务是非周期性的，因此不可能进行静态调度分析。而对于这类调度，直到到达最后期限或者直到任务完成，我们都不知道是否满足时间约束，这是这类调度的一个主要缺点，它的优点是易于实现。8.4.4限期调度大多数当代实时操作系统的设计目标是，尽可能快速地启动实时任务，因此强调快速中断处理和任务分派。事实上，在评估实时操作系统时，并没有一个特别有用的度量。尽管存在动态资源请求和冲突、处理过载和软硬件故障，实时应用程序通常并不关注绝对速度，它关注的是在最有价值的时间完成（或启动）任务，既不要太早，也不要太晚。它按照优先级提