进程调度

基本概念

导言

• 对于单处理器系统，同一时间只有一个进程可以运行。其他进程都应等待、直到CPU空闲并可调度为止。多道程序的目标是始终允许某个进程运行以最大化CPU利用率。这种想法比较简单，一个进程执行直到他应等待为止，通常等待某个i/o请求的完成。对于简单的计算机系统，CPU就处于闲置状态。所有这些等待时间就会浪费，没有完成任何有用工作。
• 采用多道程序我们试图有效利用这个时间。多个进程同时处于内存，一个进程等待时，操作系统就从该进程接管CPU控制，并将CPU交给另一进程，这种方式不断重复，当一个进程必须等待时，另一进程接管CPU使用权。这种调度是操作系统的基本功能，几乎所有计算机资源都在使用前都要调度。当然CPU是最重要的计算机资源之一，因此CPU调度是操作系统设计的重要部分。

CPU-I/O执行周期burst

• CPU的调度成功取决于如下观察到的进程属性：进程执行包括周期进行CPU执行和io等待。进程在这2个状态之间不断交替，进程执行从CPU执行开始，之后io执行：接着另一个CPU执行，接着另一个io执行等等，最终，最后的CPU执行通过系统请求结束，以便中止执行。
• CPU执行时间频率曲线通常为指数或超指数的形式，具有大量短CPU执行和少量超CPU执行。Io密集型程序通常具有大量短CPU执行，CPU密集型程序可能只有少量长CPU执行。

CPU调度程序

• 每当CPU空闲时，操作系统就应从就绪队列中选择一个进程来执行。进程选择采用短期调度程序或CPU调度程序。调度程序从内存中选择一个能够执行的进程，并为其分配CPU。
• 注意：就绪队列不必是先进先出队列。在概念上，就绪队列内的所有进程都要排队，以便等待在CPU上去运行。队列内的记录通常为进程控制块PCB

抢占调度

• 需要进行CPU调度的情况可分为以下4种：

• • 当一个进程从运行状态切换到等待状态，例如I/O请求，或wait调用以便等待一个子进程的终止
  • 当一个进程从运行状态切换到就绪状态时，例如当出现中断时
  • 当一个进程从等待状态切换到就绪队列时，例如i/o完成
  • 当一个进程终止时
  • 对于第一种和第4种情况除了调度没有选择。

• 如果一个调度只能发生在第一种和第4种情况下，则调度方案称为非抢占的或协作的：否则调度方案称为抢占的。在非抢占调度下，一旦某个进程分配到CPU，该进程就会一直使用CPU，直到它终止或切换到等待状态。

• 不过当多个进程共享数据时，抢占调度可能导致竞争情况。假设2个进程共享数据，当第一个进程正在更新数据时，他被抢占以便第2个进程能够运行。然后，第2个进程可能试图读数据，但是这时该数据处于不一致的状态。这就会造成混乱。

调度程序

• 与CPU调度功能有关的另一个组件是调度程序dispatcher。调度程序是一个模块，用来将CPU控制交给由短期调度程序选择的进程。这个功能包括：

• • 切换上下文
  • 切换到用户模式
  • 跳转到用户程序的合适位置，以便重新启动程序

• 调度程序应尽可能快，因为在每次进程切换时都要使用。调度程序停止一个进程而启动另一个进程所需要的时间称为调度延迟dispatch latency

调度准则

• 为了比较CPU调度算法，可以采用许多比较准则。选择哪些特征来比较，对于确定哪种算法是最好的有本质上的区别就。这些准则包括：

• • CPU使用率：应使CPU尽可能的忙碌。从概念上讲，CPU使用率从零到100%，对于一个实际系统，它的范围应从40%（轻负荷系统）到90%（重负荷系统）。
  • 吞吐量：如果CPU忙于执行进程，那么工作就在完成。一种测量工作的方法称为吞吐量throughput，它是在一个时间单元内进程完成的数量，对于长进程，吞吐量可能为每小时一个进程；对于短进程，吞吐量可能为每秒10个进程。
  • 周转时间：从一个特定进程的角度来看一个重要准则是运行这个进程需要多长时间。从进程提交到进程完成的时间段称为周转时间turnaround time，周转时间为所有时间段之和，包括等待进入内存、在就绪队列中等待、在CPU上执行和i/o执行。
  • 等待时间：CPU调度算法并不影响进程运行和执行i/o的时间，它只影响进程在就绪队列中因等待所需的时间。等待时间为在就绪队列中等待所花的时间之和。
  • 响应时间：对于交互系统，周转时间不是最佳选择。通常进程可以相当早的产生输出，并且继续计算新的结果同时输出以前的结果给用户。因此另一时间是从提交请求到产生第一响应的时间。这种时间称为响应时间，是开始响应所需的时间，而非输出响应所需的时间。周转时间通常受输出设备速度的限制。

• 最大化CPU使用率和吞吐量，并且最小化周转时间、等待时间和响应时间，就是可取的。在大多数情况下，优化的是平均值。然而，在有些情况下，优化的是最小值或最大值，而不是平均值。例如为了保证所有用户都能得到好的服务，可能要使最大响应时间最小。

调度算法

先到先服务调度

（等待时间长）

• 最简单的CPU调度算法是先到先服务FCFS调度算法。采用这种方案，先请求CPU的进程首先分配到CPU。FCFS策略可以通过FIFO队列容易的实现。当一个进程进入就绪队列时，它的PCB会被链接到队列尾部。当CPU空闲时，它会分配给位于队列头部的进程，并且这个运行进程从队列中移去。
• FCFS策略的缺点是，平均等待时间往往很长。由于所有其他进程都等待一个大进程释放CPU，称这种情况护航效果convoy effect，与让较短进程先进行相比，这会导致CPU和设备的使用率降低。
• 也要注意FCFS调度算法是非抢占的。一旦CPU分别分配给了一个进程，该进程就会使用CPU直到释放CPU为止，即程序终止或是请求i/o。FCFS算法对于分时系统（每个用户需要定时得到一定的CPU时间），是特别麻烦的，允许一个进程使用CPU过长将是个严重错误。

最短作业优先调度

（等待时间短，但是存在饥饿）

• 另一个不同的CPU调度方法是最短作业优先shortest-job-first,SJF调度算法。这个算法将每个进程与其下次CPU执行的长度关联起来。当CPU变为空闲时，他会被赋给具有最短CPU执行的进程。如果2个进程具有同样长度的CPU执行，那么可以由FCFS来处理。注意一个更为恰当的表示是最短下次CPU执行算法shortest-next-CPU-burst，这是因为调度取决于进程的下次CPU执行的长度，而不是其总的长度。
• 可以证明SJF调度算法是最优的。这是因为对于给定的一组进程，SJF算法的平均等待时间最小。通常将短进程移到长进程之前，短进程的等待时间减少大于长进程的等待时间增加。因而，平均等待时间减少。
• SJF算法的真正困难是如何知道下次CPU执行的长度。对于批处理系统的长期（作业）调度，可以将用户提交作业时指定的进程时限作为长度，在这种情况下，用户有意精确估计进程时间，就是因为低值可能意味着更快的响应（过小的值会引起实现超出错误进而需要重新提交）。SJF调度经常用于长期调度。
• 虽然SJF算法是最优的，但是它不能在短期CPU调度级别上加以实现，因为没有办法知道下次CPU执行的长度。一种方法是试图进SJF算法。虽然不知道下一个CPU执行的长度，但是可以预测它。可以认为下一个CPU执行的长度与以前的相似，因此通过计算下一个CPU执行程度的近似值，可以选择具有预测最短CPU执行的进程来运行。

• SJF算法可以是抢占的或非抢占的。当一个新进程到达就绪队列而以前进程正在执行，就需要选择了。新进程的下次CPU执行，与当前运行进程的尚未完成的CPU执行相比，可能还要小。抢占SJF算法就会抢占当前运行进程，而非抢占SJF算法会允许当前运行进程可以先完成CPU执行，抢占SJF调度有时称为最短剩余时间优先shortest-remaining-time-first调度。

优先级调度

• SJF算法是通用优先级调度算法的一个特例。每个进程都有一个优先级与其关联，而只有最高优先级的进程会分配到CPU。相同优先级的进程按FCFS顺序调度。SJF算法是一个简单的优先级算法，其优先级为下次预测的CPU执行时间的倒数。CPU执行越长，则优先级越小。
• 优先级通常为固定区间0-7,0-4095等的数字。不过对于零表示最高还是最低的优先级没有定论。
• 优先级的定义可分为内部的和外部的。内部的定义对优先级采用一些测量数据来进行计算进程优先级。例如时限、内存要求、打开文件数量和平均io执行时间与平均CPU执行时间等，都可以用于计算优先级。外部定义的优先级采用操作系统之外的准则，如进程重要性、用于支付使用计算机的费用类型和数量，赞助部门、其他因素等。
• 优先级调度算法的一个主要问题是无穷阻塞indefinite blocking或饥饿starvation。就绪运行但是等待CPU的进程可以认为是阻塞的，优先级调度算法可以让某个低优先级进程无穷等待CPU。对于一个超载的计算机系统，稳定的更高优先级的进程流可以阻止低优先级的进程获得CPU。一般会有两种情况发生，要么进程最终会运行，要么系统最终崩溃并失去所有未完成的低优先级进程。
• 无穷等待问题的解决方案之一是老化aging。老化逐渐增加在系统中等待很长时间的进程的优先级。可以选择每隔多长时间提升等待进程的优先级。

轮转调度（响应快，周转长）

• 轮转调度算法是专门为分时系统设计的。它类似于FCFS调度，但是增加了抢占以切换进程。将一个较小时间单元定义为时间量time quantum或时间片time slice。时间片的大小通常为10到100毫秒。就绪队列作为循环队列。CPU调度程序循环整个就绪队列，为每个进程分配不超过一个时间片的CPU。
• 为了实现RR调度，我们再次将就绪队列视为进程的FIFO队列，新进程添加到就绪队列的尾部，CPU调度程序从就绪队列中选择第一个进程，将定时器设置在一个时间片后中断，最后分派这个进程。
• 接下来有两种情况发生，进程可能只需要少于时间片的CPU执行。对于这个情况，进程本身会自动释放CPU。调度程序接着处理就是队列的下一个进程，否则如果当前运行进程的CPU执行大于一个时间片，那么定时器会中断，进而中断操作系统，然后进行上下文切换，它将进程加到就绪队列的尾部，接着CPU调度程序会选择就是队列的下一个进程。
• 在RR调度算法中，没有进程被连续分配超过一个时间片的CPU（除非他是唯一一个可运行的进程），如果进程的CPU执行超过一个时间片，那么该进程就会被抢占，并被放回到就绪队列中，因此，RR调度算法是抢占的。
• 如果就绪队列有n个进程，并且时间片为q，那么每个进程就会得到1/n的CPU时间，而且每次分得的时间不超过q个时间单元，每个进程等待获得下一个CPU时间片的时间不会超过（n-1）q个时间单元。
• RR算法的性能很大程度上取决于时间片的大小。在一种极端情况下，如果时间片很大，那么RR算法就与FCFS算法一样，如果时间片很小，那么RR算法可能导致大量的上下文切换。
• 因此，我们希望时间片远远大于上下文切换时间。如果上下文切换时间约为时间片的10%，那么10%的CPU时间会浪费在上下文切换上，在实践中，大多数现代操作系统的时间片为10 -100 ms，上下文切换的时间一般少于10ms，因此，上下文切换时间只是时间片的一小部分。
• 周转时间也依赖于时间片大小

多级队列调度

• 在进程容易分成不同组的情况下，可以有另一类调度算法，例如，进程通常分为前台进程（或交互进程）和后台进程（或批处理进程）。这两种类型的进程具有不同的响应时间要求，进而也有不同的调度需要。另外，与后台进程相比，前台进程可能需要更高的优先级（外部定义）。
• 多级队列调度算法（multilevel queue）将就绪队列分成多个单独队列，根据进程属性，如内存大小，进程优先级，进程类型等，一个进程永久的分配到一个队列，每个队列都有自己的调度算法，例如可以前台队列使用RR轮转调度，后台进程使用FCFS算法
• 此外队列之间应有调度，通常采用固定优先级抢占调度，例如，前台队列可以比后台队列具有绝对的优先。
• 另一种可能是，在队列之间划分时间片，每个队列都有一定比例的CPU时间，可用于调度队列内的进程，但是不同的队列，时间比例不同；

多级反馈队列调度

• 通常在使用多级队列调度算法时，进程进入系统时被永久的分配到某个队列，进程不能在队列间移动，这样虽然调度开销低，但是不够灵活。

• 多级反馈队列（multilevel feedback queue）调度算法允许进程在队列间迁移，根据不同CPU执行的特点来区分进程，如果使用过多的CPU时间，那么他会被移到更低的优先级队列，这种方案将I/O密集型和交互进程放在更高优先级队列上，此外，在较低优先级队列中等待过长的进程会被移到更高优先级队列，这种形式的老化阻止饥饿的发生。

• 通常，多级反馈队列调度程序可由下列参数定义：

• • 队列数量
  • 每个队列的调度算法
  • 用以确定何时升级到更高优先级队列的算法
  • 用以确定何时降级到更低优先级队列的算法
  • 用以确定进程在需要服务时将会进入那个队列的方法

• 多级反馈队列调度程序的定义使其成为最通用的CPU调度算法。通过配置，他能适用所设计的特定系统，遗憾的是，由于需要一些方法来选择参数一定义最佳的调度选择，所以她也是最复杂的算法。

多处理器调度

多处理器调度的方法

• 在一个多处理器中，CPU 调度的一种方法是让一个处理器(主服务器)处理所有的调度决定、IO 处理以及其他系统活动，其他的处理器只执行用户代码。这种非对称多处理( asymmetric multiprocessing)方法更为简单，因为只有一个处理器访问系统数据结构，减轻了数据共享的需要。
• 另一种方法是使用对称多处理(symmetric multiprocessing，SMP）方法，即每个处理器自我调度。所有进程可能处于一个共同的就绪队列中，或每个处理器都有它自己的私有就绪进程队列。无论如何，调度通过每个处理器检查共同就绪队列并选择一个进程来执行。如果多个处理器试图访问和更新一个共同数据结构，那么每个处理器必须仔细编程:必须确保两个处理器不能选择同一进程，且进程不会从队列中丢失。事实上，许多现代操作系统，包括 Windows XP、Windows 2000、Solaris、Linux和Mac OS x，它们都支持SMP。

处理器亲和性

• 由于使缓存无效或重新构建的代价高,绝大多数SMP系统试图避免将进程从一个处理器移至另一个处理器，而是努力使一个进程在同一个处理器上运行，这被称为处理器亲和性，即一个进程需有一种对其运行所在的处理器的亲和性。
• 处理器亲和性有几种形式。当一个操作系统具有设法让一个进程保持在同一个处理器上运行的策略，但不能做任何保证时，则会出现软亲和性(soft affinity)。此时，进程可能在处理器之间移动。有些系统，如Linux，还提供一个支持硬亲和性(hard affinity)的系统调用，从而允许进程指定它不允许移至其他处理器上。
• 系统的内存架构可以影响处理器的亲和性，采用非统一内存访问的一种架构，其中一个CPU访问内存的某些部份会比其他部分更快。通常情况下，这类系统包括组合CPU和内存的板卡。每个板的CPU访问本板内存快于访问其他板的内存。如果操作系统的CPU调度和内存分配算法一起工作，那么当一个进程分配到一个特定的亲核处理器时，他应分配到同板上的内存。

负载平衡

• 对于SMP系统，重要的是保持所有处理器的负载平衡，以便充分利用多处理器的优点。否则一个或多个处理器会空闲，而其他处理器会处于高负载状态，且有一系列进程处于等待状态。负载平衡load balance设法将负载平均分配到SMP系统的所有处理器。重要的是，要注意对于有些系统，他们的处理器具有私有的可执行的进程的队列，负载平衡是必须的；而对于具有公共队列的系统，负载平衡通常没有必要，因为一旦处理器空闲的话，他立刻从公共队列中取走一个可执行进程。同样重要的是，要注意对于大多数支持SMB的现代操作系统，每个处理器都有一个可执行进程的私有队列。
• 负载平衡通常有两种方法：推迁移Push migration和拉迁移pull migration。对于推迁移，一个特定的任务周期性会检查每个处理器的负载，如果发现不平衡，那么通过将进程从超载处理器推到空闲或不太忙的处理器，从而平均分配负载。当空闲处理器从一个忙的处理器上拉一个等待任务时，发生拉迁移。推迁移和拉迁移不必互相排斥，事实上，在负载平衡系统中它们常常被并行实现。有趣的是，负载平衡往往会抵消处理器亲和性的好处。也就是说，保持一个进程运行在同一处理器上的好处是进程可以利用他在该处理器缓存内的数据。无论是从一个处理器向另一个处理器推或拉进程，都会失去这个好处。

线程调度

导言

• 在支持线程的操作系统上，内核级线程（而不是进程）才是操作系统所调度的。用户级线程是由线程库来管理的，而内核并不知道她们，用户级线程为了运行在CPU上，最终应映射到相关的内核级线程，但是这种映射可能不是直接的，可能采用轻量级进程（LWP）。

竞争范围

• 用户级和内核级线程之间的一个区别在于他们是如何调度的，对于实现多对一和多对多模型的系统线程库会调度用户级线程，以便在可用LWP上运行，这种方案称为进程竞争范围（process-contention scope， PCS），因为竞争CPU是发生在统一进程的线程之间（当我们说线程库将用户线程调度到可用LWP时，并不意味着线程真实运行在一个CPU上，这回需要操作系统调度内核线程到物理CPU）；
• 为了决定哪一个内核级线程调度到一个处理器上，内核采用系统竞争范围（system-contention scope，SCS），采用SCS调度来竞争CPU，发生在系统内的所有线程之间。采用一对一模型的系统，只采用SCS调度。
• 通常情况下，PCS采用优先级调度，且是抢占的，调度程序选择运行具有最高优先级的，可运行的线程执行。

操作系统实例

Solaris调度

• Solaris采用基于优先级的线程调度，根据优先级不同，他有四类调度，分别是：

• • 实时，系统，分时，交互

• 每个类型内有不同的优先级和调度算法。

• 进程默认的调度类型是分时。分时调度方法采用多级反馈队列，动态地调整优先级和赋予不同长度的时间片。默认地，在优先级和时间片之间有反比关系：优先级越高，时间片越小;优先级越低，时间片越大。交互进程通常有更高的优先级，CPU约束进程有更低的优先级。这种调度策略对交互进程有好的响应时间，对CPU约束进程有好的吞吐量。交互类型与分时类型使用同样的调度策略，但是它能给窗口应用程序更高的优先级以提高性能。

• 系统类用来运行内核进程，如调度程序或换页服务，一旦创建，系统进程的优先级就不改变；实时类型的线程具有最高优先级，允许实时进程保证在给定时间内响应；

• 通常分配表包含以下字段：

• • ·优先级:分时和交互类型的依赖类型的优先级。数值越高，优先级越大。
  • ·时间片:优先级相关的时间片。这表明优先级与时间片之间相反的关系:最低优先级（优先级为0）具有最长的时间片(200 ms)，最高优先级（优先级为59）具有最短的时间片(20 ms)。
  • ·时间片到期:用完了其全部时间片而未堵塞的线程的新的优先级。这种线程被认为是CPU密集的。如图5.11中所示，这些线程会被降低优先级。
  • ·从睡眠中返回:从睡眠中返回的线程的优先级（如等待IO)。如表中所示，当一个等待线程有IO可用的时候，它的优先级被提高到50~59，以支持给交互进程提供好的响应时间的调度策略。

Windows XP调度

• 基于优先级、抢占调度算法来调度线程，保证最高优先级的线程总是运行，直到被更高优先级的进程所抢占，或终止，或时间片到期，或调用了阻塞系统调用。这种抢占使得实时线程在需要使用CPU时能优先得到使用。
• 调度程序使用32优先级方案以确定线程执行的顺序，优先级分为两大类：可变类型包括优先级0-15的线程；实时类型包括优先级从16-31的线程；还有一个线程运行在优先级0，用于内存管理。调度程序为每个调度优先级使用一个队列，从高到低检查队列，直到它发现一个线程可以执行。如果没有找到就绪线程，那么调度程序会执行一个称为空闲线程（idle thread）的特别线程。

Linux调度

• Linux调度程序是抢占的、基于优先级的算法，具有两个独立的优先级范围:从0~99的real-time范围和从100～140的nice范围。这两个范围映射到全局优先级，其中数值越低表明优先级越高。
• 与包括Solaris和 Windows XP在内的其他许多系统的调度程序不同，Linux 给较高的优先级分配较长的时间片，给较低的优先级分配较短的时间片。

算法评估

导言

• 如何选择CPU调度算法以用于特定系统?调度算法有许多，且各有自己的参数。因此，选择算法可能会比较困难。

• 第一个问题是定义用于选择算法的准则。准则通常是通过CPU使用率、响应时间或吞吐量来定义的。为了选择算法，首先必须定义这些参数的相对重要性。准则可包括如下参数，

• • ·最大化CPU使用率，同时要求最大响应时间为1s。
  • ·最大化吞吐量，例如，要求（平均）周转时间与总的执行时间成正比。

• 一旦定义了选择准则，需要评估所考虑的各种算法。

确定模型（简单快速）

• 一种主要类型的评估方法称为分析评估法( analytic evaluation)。分析评估法使用给定算法和系统负荷，产生一个公式或数字，以评估对于该负荷算法的性能。
• 一种类型的分析评估是确定模型法(deterministic modeling)。这种方法采用特殊预先确定的负荷，计算在给定负荷下每个算法的性能。
• 最突出的例子就是利用甘特图分析，计算各种算法的平均等待时间，周转时间等等；

排队模型

• 计算机系统可描述为服务器网络。每个服务器都有一个等待进程队列。CPU是具有就绪队列的服务器，而I/O系统是具有设备队列的服务器。知道了到达率和服务率，可计算使用率、平均队列长度、平均等待时间等。这种研究称为排队网络分析（queueing-networkanalysis）。

• 作为一个例子，设n为平均队列长度（不包括正在服务的进程)，W为队列的平均等待时间，λ 为新进程到达队列的平均到达率（如每秒三个进程)。那么，在进程等待的W时间内，则有 λ xW个新进程到达队列。如果系统处于稳定状态，那么离开队列的进程的数量必须等于到达进程的数量。因此，

• • n= λ ×w

• 这一公式称为Little公式。Little公式特别有用，因为它适用于任何调度算法和到达分布。

模拟（精确）

• 模拟涉及对计算机系统进行建模，
• 驱动模拟的数据可由许多方法产生。最为普通的方法使用随机数生成器，以根据概率分布生成进程、CPU区间时间、到达时间、离开时间等。分布可以数学地（统一的、指数的、泊松的）或经验地加以定义。如果经验定义分布，那么要对所研究的真实系统进行测量。其结果可用来定义真实系统事件的真实分布，该分布再用来驱动模拟。
• 然而，由于真实系统前后事件之间有关系，分布驱动模拟可能不够精确。频率分布只表示每个事件发生了多少次，它并不能表示事件的发生顺序。可以采用跟踪磁带来解决这个问题。通过监视真实的系统，记录下事件发生的顺序来建立跟踪磁带（见图5.15)，然后使用这个顺序来驱动模拟。跟踪磁带提供了基于真实输入来比较两种算法的很好的方法。这种方法针对给定输入产生了精确的结果。

• 然而模拟通常需要数小时的计算时间，所以是昂贵的。为了提供更精确的结果，需要更细致的模拟，但是也需要更多的计算时间。而且跟踪磁带需要大量的存储空间。最后，模拟程序的设计、编码、调试是其主要的工作。

实现（最精确）

• 即使是模拟，精确度也是有限的。针对评估调度算法，唯一完全精确的方法是对它进行编程，将它放在操作系统内，并观测它如何工作。这一方法将真实算法放入操作系统，然后在真实操作系统内进行评估。
• 该方法的主要困难是其高昂的代价。所引起的代价不但包括对算法进行编程、修改操作系统以支持该算法（以及相关的数据结构)，而且包括用户对不断改变操作系统的反应。绝大多数用户并不关心创建更好的操作系统，而只需要能执行程序并使用其结果。经常性地改变操作系统并不能帮助用户得到他们所想要的。
• 另一个困难是算法所使用的环境会发生改变。