CPU调度

在多道程序设计的操作系统中，多个进程同时存在于内存中，它们竞争有限的CPU资源。CPU调度是操作系统的核心功能之一，它负责从就绪队列中选择下一个要执行的进程，并将CPU控制权分配给该进程。调度决策直接影响系统的性能指标，包括CPU利用率、吞吐量、响应时间和公平性。

CPU调度器根据预定义的调度算法和策略，综合考虑进程的优先级、执行时间、资源需求等多种因素，动态决定进程的执行顺序。这一机制确保了系统资源的高效利用，同时满足不同应用场景对响应性和公平性的需求。

为什么需要CPU调度

在早期的单道批处理系统中，一次只能运行一个程序。当程序执行I/O操作时，CPU处于空闲状态，造成计算资源的严重浪费。这种设计导致CPU利用率极低，系统整体效率低下。

现代操作系统采用多道程序设计（multiprogramming）技术，允许多个进程同时驻留在内存中。当某个进程因I/O操作而阻塞时，操作系统立即进行上下文切换，将CPU分配给另一个处于就绪状态的进程。这种机制显著提高了CPU利用率，使得系统能够在等待I/O的同时继续执行计算任务。

CPU-I/O突发周期

理解CPU调度的关键在于认识进程的执行模式。每个进程的执行可以抽象为一个CPU突发（CPU burst）和I/O突发（I/O burst）的交替循环。

以文字处理应用为例，当用户输入文字时，进程在CPU上执行计算任务，这构成了CPU突发阶段。随后，进程需要将数据写入磁盘，此时进程进入I/O突发阶段，等待I/O操作完成。I/O操作完成后，进程再次进入CPU突发阶段，继续执行计算任务。

不同类型的进程表现出不同的CPU-I/O突发模式。I/O密集型进程（如文字处理器、网页浏览器）通常具有大量短时间的CPU突发，进程频繁地在CPU执行和I/O等待之间切换。相比之下，CPU密集型进程（如视频编码、科学计算）则表现出少量长时间的CPU突发，进程大部分时间都在执行计算任务。

CPU调度器的工作原理

CPU调度器是操作系统的核心组件，负责从就绪队列（ready queue）中选择下一个要执行的进程。就绪队列是一个数据结构，包含了所有处于就绪状态但尚未获得CPU的进程。调度器根据预定义的调度算法，从就绪队列中选择合适的进程，并将其分配给CPU执行。

就绪队列的实现方式取决于所采用的调度算法。它可能是一个简单的先进先出（FIFO）队列，也可能是一个按优先级排序的优先队列，或者是一个基于红黑树等高效数据结构的有序集合。无论采用何种数据结构，其核心功能都是维护就绪进程的有序集合，以便调度器能够快速选择下一个要执行的进程。

抢占式与非抢占式调度

CPU调度决策可能发生在以下四种情况下：

• 进程从运行状态转换到等待状态（如等待I/O操作完成）
• 进程从运行状态转换到就绪状态（如时间片用完或被抢占）
• 进程从等待状态转换到就绪状态（如I/O操作完成）
• 进程终止

前两种情况（进程等待I/O或进程终止）属于强制性调度，系统必须选择新的进程来执行。对于后两种情况，操作系统具有调度决策的自由度。

当调度只在进程主动放弃CPU时发生，我们称之为非抢占式调度（nonpreemptive scheduling）。在这种模式下，一旦进程获得CPU，它将一直执行直到完成、阻塞或主动让出CPU。非抢占式调度的优点是实现简单、上下文切换开销小，但可能导致高优先级进程长时间等待。

现代操作系统普遍采用抢占式调度（preemptive scheduling），这意味着操作系统可以在任何时候中断正在运行的进程，将CPU分配给更高优先级的进程。抢占式调度提高了系统的响应性和公平性，使得高优先级任务能够及时获得CPU资源。

分派器

分派器是CPU调度功能中的另一个重要组件，它负责将CPU控制权交给被调度器选中的程序。分派器的工作包括上下文切换、切换到用户模式，以及跳转到用户程序中正确的位置继续执行。

分派器需要尽可能高效地完成这些操作，因为它每次上下文切换时都会被调用。从停止一个进程到启动另一个进程所需的时间称为分派延迟（dispatch latency）。分派延迟包括保存和恢复进程上下文、更新进程控制块（PCB）、切换内存管理单元（MMU）状态等操作的时间开销。

在现代系统中，上下文切换的频率相当高。通过Linux系统的vmstat命令可以观察到，系统每秒可能发生数百次甚至数千次上下文切换。这些切换包括自愿切换（voluntary context switch，进程主动放弃CPU）和非自愿切换（involuntary context switch，进程被强制中断）。

调度标准

评价CPU调度算法的优劣需要从多个维度进行综合衡量。不同的应用场景对调度标准有不同的要求，因此需要根据系统类型和工作负载特征来选择合适的调度算法。

CPU利用率

CPU利用率（CPU utilization）衡量的是CPU处于忙碌状态的时间比例。理想情况下，我们希望CPU始终保持忙碌状态，避免空闲等待。在真实系统中，CPU利用率通常在40%（轻负载系统）到90%（重负载系统）之间。过高的CPU利用率可能导致系统响应性下降，而过低的利用率则表明计算资源未被充分利用。

吞吐量

吞吐量（throughput）表示单位时间内完成的进程数量。对于长时间运行的批处理作业，吞吐量可能是每秒几个进程；对于短时间的交互式事务处理，吞吐量可能是每秒数十个甚至数百个进程。吞吐量是衡量系统整体效率的重要指标。

周转时间

周转时间（turnaround time）是从进程提交到完成的总时间。它包括进程在就绪队列中等待的时间、在CPU上执行的时间，以及进行I/O操作的时间。周转时间越短，意味着进程能够更快地完成，这对于批处理系统尤为重要。

等待时间

等待时间（waiting time）特指进程在就绪队列中等待的时间。CPU调度算法只影响等待时间，不影响进程的实际执行时间（CPU burst time）或I/O时间。等待时间是评价调度算法公平性的重要指标。

响应时间

在交互式系统中，响应时间（response time）比周转时间更重要。响应时间是从提交请求到产生第一个响应的时间间隔。对于交互式应用（如文本编辑器、图形界面），用户更关心系统对输入操作的响应速度，而不是整个任务完成所需的时间。

经典调度算法

先来先服务调度

先来先服务（First-Come, First-Served, FCFS）是最简单的调度算法，也称为先进先出（FIFO）调度。进程按照到达就绪队列的顺序获得CPU，先到达的进程先执行。FCFS算法实现简单，不需要维护复杂的优先级信息。

假设有三个进程P1、P2、P3，它们的CPU突发时间分别是24、3、3毫秒。如果按照P1、P2、P3的顺序到达，那么P1的等待时间是0毫秒，P2的等待时间是24毫秒，P3的等待时间是27毫秒，平均等待时间是17毫秒。

但如果按照P2、P3、P1的顺序到达，平均等待时间就变成了3毫秒。这说明FCFS算法对进程的到达顺序很敏感，其性能在很大程度上取决于工作负载的特征。当短进程先到达时，平均等待时间显著降低。

FCFS算法的主要问题是可能导致"护航效应"（convoy effect）。当一个长时间运行的进程占用CPU时，其他短时间进程必须等待，即使它们的执行时间很短。这会导致CPU和I/O设备的利用率下降，因为短进程在等待长进程完成时，I/O设备可能处于空闲状态。

最短作业优先调度

最短作业优先（Shortest-Job-First, SJF）算法总是选择CPU突发时间最短的进程执行。SJF算法可以是非抢占式的，也可以是抢占式的（称为最短剩余时间优先，SRT）。

对于上面的例子，SJF算法会选择P4（3毫秒）、P1（6毫秒）、P3（7毫秒）、P2（8毫秒）的顺序执行，平均等待时间是7毫秒，比FCFS的10.25毫秒要好。

SJF算法在理论上是最优的，能够提供最短的平均等待时间。这一结论可以通过数学证明：对于给定的进程集合，按照CPU突发时间递增的顺序执行，能够最小化平均等待时间。

但是，SJF算法有一个根本性问题：我们无法预知进程的下一个CPU突发时间。在实际系统中，进程的CPU突发时间通常是未知的，这限制了SJF算法的直接应用。

为了解决这个问题，我们可以尝试预测下一个CPU突发时间。常用的方法是使用指数平均法（exponential averaging）：

其中，$\tau_{n+1}$是下一次CPU突发的预测值，$t_n$是第n次CPU突发的实际值，$\tau_n$是第n次CPU突发的预测值，α是平滑因子（0 ≤ α ≤ 1）。α越接近0，预测值更多地依赖历史数据；α越接近1，预测值更多地依赖最近的实际值。通常α取0.5，在历史趋势和最新变化之间取得平衡。

SJF算法的抢占式版本称为最短剩余时间优先（Shortest-Remaining-Time-First, SRT）。当新进程到达时，如果其剩余CPU突发时间小于当前运行进程的剩余时间，则抢占当前进程。SRT算法能够进一步优化平均等待时间，但需要更频繁的上下文切换。

时间片轮转调度

时间片轮转（Round-Robin, RR）算法为每个进程分配一个固定的时间片（time quantum或time slice）。当时间片用完时，进程被抢占并放到就绪队列末尾，下一个进程获得CPU。RR算法特别适合交互式系统，因为它能够保证所有进程都能定期获得CPU时间。

对于上面的例子，使用4毫秒的时间片，P1需要6个时间片完成，P2和P3各需要1个时间片。平均等待时间是5.66毫秒。

时间片的大小对RR算法的性能有重要影响。如果时间片太大，RR算法就退化为FCFS算法，失去了时间片轮转的优势；如果时间片太小，会产生过多的上下文切换开销，导致系统效率下降。

时间片的选择需要在响应性和效率之间取得平衡。理想情况下，时间片应该设置得比大多数进程的CPU突发时间稍长一些，使得大部分短进程能够在一个时间片内完成，从而减少等待时间。同时，时间片不能太短，以避免上下文切换开销超过实际计算时间。通常，时间片设置在10到100毫秒之间，具体值取决于系统的响应性要求和上下文切换开销。

优先级调度

优先级调度（Priority Scheduling）为每个进程分配一个优先级，CPU总是分配给优先级最高的进程。优先级可以通过内部因素（如时间限制、内存需求、I/O与CPU比率）或外部因素（如重要性、用户类型、付费情况）来确定。优先级可以是静态的（在进程创建时确定，运行期间不变）或动态的（根据进程行为动态调整）。

优先级调度的一个严重问题是"饥饿"（starvation）现象。低优先级进程可能永远得不到执行机会，如果持续有高优先级进程到达，低优先级进程将无限期等待。这违反了调度的公平性原则。

解决饥饿问题的方法是"老化"（aging）：逐渐提高长时间等待进程的优先级。随着等待时间的增加，进程的优先级逐渐提升，最终能够获得执行机会。老化机制确保了所有进程最终都能获得CPU时间，避免了无限期等待的问题。

多级队列调度

多级队列调度（Multilevel Queue Scheduling）将进程分成不同的队列，每个队列有自己的调度算法。进程根据其类型（如实时进程、系统进程、交互进程、批处理进程）被分配到相应的队列。这种设计允许系统为不同类型的进程采用不同的调度策略，以满足各自的特点和需求。

队列之间的调度通常采用固定优先级抢占式调度。实时队列具有绝对优先级，只有当高优先级队列为空时，低优先级队列才能获得CPU。这种设计确保了关键任务能够及时响应。

另一种方法是时间片分配（time slicing）：每个队列获得CPU时间的一定比例。例如，交互队列获得80%的CPU时间，批处理队列获得20%的CPU时间。这种方法在保证高优先级队列性能的同时，也为低优先级队列提供了执行机会。

多级反馈队列调度

多级反馈队列调度（Multilevel Feedback Queue Scheduling）允许进程在不同队列间移动，这是多级队列调度的改进版本。如果进程使用过多CPU时间（时间片用完），会被移到低优先级队列；如果进程等待时间过长，会被移到高优先级队列。这种反馈机制能够根据进程的实际行为动态调整其优先级，既照顾了I/O密集型进程（短CPU突发），也避免了CPU密集型进程（长CPU突发）长期占用CPU。

多级反馈队列调度器需要定义以下参数：队列数量、每个队列的调度算法、队列间的时间片分配、进程在不同队列间移动的规则（升级和降级策略），以及新进程的初始队列分配。

这种算法是最通用的CPU调度算法，可以配置为适应特定系统的需求。通过合理设置参数，多级反馈队列调度能够同时满足交互式应用对响应时间的要求和批处理应用对吞吐量的要求。但它也是最复杂的算法，因为需要为所有参数选择最佳值，这通常需要根据实际工作负载进行调优。

调度算法可视化

线程调度

在现代操作系统中，真正被调度的是线程（thread）而不是进程（process）。线程是CPU调度的基本单位，而进程是资源分配的基本单位。用户级线程（User-Level Thread, ULT）由线程库管理，内核级线程（Kernel-Level Thread, KLT）由操作系统内核调度。多线程进程中的多个线程共享进程的地址空间和资源，但每个线程有自己独立的栈和寄存器状态。

竞争范围

线程调度有两种竞争范围（contention scope）：进程竞争范围（Process Contention Scope, PCS）和系统竞争范围（System Contention Scope, SCS）。

在进程竞争范围（PCS）中，只有同一进程内的线程相互竞争CPU。线程库从该进程的线程中选择一个优先级高的线程，将其映射到一个轻量级进程（Lightweight Process, LWP）上执行。用户级线程通常采用PCS，线程调度由用户空间的线程库完成，操作系统只看到LWP，不知道进程内部有多少线程。

在系统竞争范围（SCS）中，系统中的所有线程（来自不同进程）一起竞争CPU。操作系统内核直接调度线程，根据线程的优先级决定哪个线程获得CPU。内核级线程采用SCS，线程调度由操作系统内核完成，线程的创建、销毁和调度都需要系统调用。

POSIX线程调度

POSIX标准提供了丰富的线程调度API，允许程序员控制线程的调度策略。主要的调度策略包括：

• SCHED_FIFO（先进先出）
• SCHED_RR（轮转）
• SCHED_OTHER（系统默认）

#include <pthread.h>
#include <stdio.h>
 
int main() {
    pthread_attr_t attr;
    int policy;
    
    // 获取默认属性
    pthread_attr_init(&attr);
    
    // 获取当前调度策略
    pthread_attr_getschedpolicy(&attr, &policy);
    
    // 设置调度策略为FIFO
    pthread_attr_setschedpolicy(&attr, SCHED_FIFO);
    
    // 创建线程...
    
    return 0;
}

SCHED_FIFO策略按照先进先出的顺序调度线程，没有时间片限制。高优先级线程会一直运行直到完成、阻塞或主动让出CPU。相同优先级的线程按照FIFO顺序执行。SCHED_RR策略在相同优先级的线程间进行轮转调度，每个线程获得一个时间片，时间片用完后被放到队列末尾。SCHED_OTHER是系统默认的调度策略，通常采用时间片轮转或完全公平调度。

多处理器调度

在多处理器系统中，CPU调度面临新的挑战：如何将任务分配到不同的处理器核心上，如何确保每个核心都能充分利用，如何防止某些核心过载而其他核心空闲。多处理器调度需要考虑负载均衡、处理器亲和性、缓存一致性等因素，以实现系统整体性能的最优化。

多处理器架构

现代多处理器系统包括多种架构：多核CPU、多线程核心、NUMA系统和异构多处理。每种架构都有其独特的调度挑战。

调度策略

多处理器调度有两种主要策略：非对称多处理（Asymmetric Multiprocessing, AMP）和对称多处理（Symmetric Multiprocessing, SMP）。

在非对称多处理（AMP）中，一个处理器作为主服务器（master）处理所有调度决策，其他处理器（slaves）只执行用户代码。这种方法的优点是实现简单，调度逻辑集中，易于维护。缺点是主服务器可能成为性能瓶颈，且主服务器故障会导致整个系统无法调度。

在对称多处理（SMP）中，每个处理器都是自调度的（self-scheduling）。每个处理器都有自己的调度器，独立检查就绪队列并选择线程运行。这种方法的优点是负载分散，没有单点故障，可扩展性好。缺点是需要处理多处理器间的同步问题，实现复杂度较高。现代操作系统普遍采用SMP架构。

就绪队列组织

多处理器系统有两种组织就绪队列的方式：公共就绪队列（shared ready queue）和每处理器私有队列（per-processor private queue）。

在公共就绪队列中，所有线程都在一个共享队列中，任何处理器都可以从中选择线程。这种方法的优点是实现简单，负载自动均衡。缺点是需要同步机制（如锁）来避免竞争条件，多处理器同时访问队列时会产生竞争，可能成为性能瓶颈。

在每处理器私有队列中，每个处理器有自己的就绪队列。这种方法的优点是避免了同步开销，减少了竞争，提高了效率。缺点是需要额外的负载均衡机制，以防止某些处理器的队列为空而其他处理器的队列过长。

负载均衡

负载均衡（load balancing）确保所有处理器的工作负载均匀分布，避免某些处理器过载而其他处理器空闲。负载均衡对于多处理器系统的性能至关重要，不均衡的负载会导致系统整体性能下降。

负载均衡有两种方法：推送迁移（push migration）和拉取迁移（pull migration）。在推送迁移中，特定的负载均衡任务定期检查每个处理器的负载，如果发现负载不平衡，就将线程从过载处理器移动到空闲或负载较轻的处理器。在拉取迁移中，空闲处理器主动从繁忙处理器的队列中拉取等待的线程。现代操作系统通常结合使用两种方法，以实现更好的负载均衡效果。

处理器亲和性

处理器亲和性（processor affinity）是指让线程尽量在同一个处理器上执行，避免频繁的处理器迁移。处理器亲和性对于系统性能有重要影响，主要原因是缓存局部性（cache locality）。

当线程在同一个处理器上执行时，该处理器的缓存（L1、L2、L3缓存）中会存储线程常用的数据和指令，访问速度很快。如果线程被迁移到另一个处理器，新处理器的缓存是空的，需要从内存重新加载数据和指令，这会导致缓存未命中（cache miss）和性能下降。频繁的处理器迁移会破坏缓存局部性，增加内存访问延迟，降低系统整体性能。

处理器亲和性有软亲和性（soft affinity）和硬亲和性（hard affinity）两种形式。在软亲和性中，操作系统尝试让进程在同一个处理器上运行，但不保证，当负载不均衡时仍可能进行迁移。在硬亲和性中，进程可以指定只能在特定的处理器子集上运行，操作系统保证不会将进程迁移到其他处理器。硬亲和性提供了更强的控制，但可能影响负载均衡的效果。

实时CPU调度

在实时系统中，时间约束是系统设计的核心要求。实时调度算法的任务是确保每个实时任务都能在其截止时间（deadline）前完成。超过截止时间的服务在实时系统中被视为无效，甚至可能导致系统故障。实时调度算法必须能够进行可调度性分析（schedulability analysis），判断给定的任务集合是否能够在所有截止时间前完成。

实时系统分类

实时系统分为软实时系统和硬实时系统。软实时系统不保证关键实时进程何时被调度，只保证它们比非关键进程有优先权。硬实时系统有更严格的要求，任务必须在截止时间前完成，超过截止时间的服务等同于没有服务。

延迟最小化

实时系统的关键性能指标是延迟（latency）。事件延迟（event latency）是从事件发生到被服务的时间间隔。实时系统要求延迟尽可能小且可预测，以满足实时任务的截止时间要求。

延迟可以分为两个部分：中断延迟（interrupt latency）和分派延迟（dispatch latency）。中断延迟是从硬件中断发生到中断处理程序开始执行的时间。分派延迟是从中断处理程序完成到实时任务开始执行的时间，包括上下文切换、调度决策等操作的时间开销。实时系统通过优化中断处理、使用快速上下文切换机制、减少内核关键路径长度等方式来最小化延迟。

基于优先级的调度

实时操作系统普遍采用基于优先级的抢占式调度。高优先级任务可以随时抢占低优先级任务，确保关键任务能够及时响应。实时调度算法通过合理的优先级分配和抢占机制，保证所有实时任务都能在其截止时间前完成。

速率单调调度

速率单调调度（Rate-Monotonic Scheduling, RMS）是一种静态优先级调度算法，适用于周期性实时任务。RMS算法的优先级分配规则是：任务周期越短，优先级越高。周期为$T_i$的任务的优先级高于周期为$T_j$的任务，当且仅当$T_i < T_j$。这种优先级分配策略基于一个重要的观察：周期短的任务通常有更紧的截止时间要求。

速率单调调度在理论上是最优的静态优先级调度算法，但CPU利用率有上限。对于N个进程，最坏情况下的CPU利用率是 $N(2^{1/N} - 1)$。当N趋近于无穷大时，利用率趋近于约69%（$\ln 2 \approx 0.693$）。这意味着即使所有任务的周期和计算时间都满足可调度性条件，CPU利用率也可能无法达到100%。RMS算法要求所有任务都是周期性的，且周期等于截止时间。

最早截止时间优先调度

最早截止时间优先（Earliest-Deadline-First, EDF）调度是一种动态优先级调度算法。EDF算法根据任务的截止时间动态分配优先级：截止时间越早，优先级越高。当新任务到达或当前任务的截止时间改变时，优先级会重新计算。EDF算法适用于周期性和非周期性实时任务。

EDF调度在理论上是最优的动态优先级调度算法，对于单处理器系统，理论上可以达到100%的CPU利用率。只要任务集合的总利用率不超过100%，EDF算法就能保证所有任务在其截止时间前完成。但实际中由于上下文切换、中断处理、缓存失效等开销，无法达到理论上的100%利用率。EDF算法的主要缺点是优先级动态变化，实现复杂度较高。

比例共享调度

比例共享调度（Proportional Share Scheduling）也称为公平份额调度（Fair-Share Scheduling），将CPU时间按照预定义的份额（share）分配给不同的进程或用户。每个进程获得与其份额成比例的CPU时间。例如，如果进程A的份额是50，进程B的份额是25，那么进程A应该获得约66.7%的CPU时间，进程B应该获得约33.3%的CPU时间。比例共享调度确保了资源分配的公平性和可预测性。

比例共享调度器必须与准入控制（admission control）策略配合工作，确保应用程序获得其分配的时间份额。准入控制器在进程创建时检查系统是否有足够的可用份额，如果新进程请求的份额超过了可用份额，准入控制器会拒绝该进程进入系统。准入控制保证了系统不会过载，确保已接受的任务能够获得承诺的资源份额。

CPU调度实验室

操作系统实例

不同的操作系统采用了不同的CPU调度策略和实现方式，这些设计反映了各自的设计哲学和应用场景。下面我们分析几个主流操作系统的调度器实现。

Linux调度器

Linux的调度器经历了多次重大改进。从早期的传统UNIX调度器，到2.5版本的O(1)调度器，再到2.6.23版本引入的完全公平调度器（CFS），Linux的调度技术不断演进。 CFS调度器的核心思想是为每个任务分配CPU处理时间的比例，而不是固定的时间片。这种比例基于任务的nice值计算，nice值范围从-20到+19，数值越小表示相对优先级越高。

CFS使用虚拟运行时间（vruntime）来记录每个任务的运行情况。对于正常优先级的任务，虚拟运行时间等于实际物理运行时间。对于低优先级任务，虚拟运行时间增长更快；对于高优先级任务，虚拟运行时间增长更慢。

CFS使用红黑树来组织可运行任务，以vruntime作为键值。调度器总是选择vruntime最小的任务运行，这确保了公平性。红黑树的平衡特性使得查找最小vruntime的任务只需要O(log N)的时间复杂度。

Linux还支持实时调度，使用POSIX标准。实时任务有更高的优先级，范围从0到99，而普通任务的优先级范围从100到139。这种设计确保了实时任务能够及时响应。

Windows调度器

Windows使用基于优先级的抢占式调度算法。调度器确保最高优先级的线程总是运行。 Windows的调度器称为分派器，它使用32级优先级方案来确定线程的执行顺序。优先级分为两个类别：变量类别（优先级1-15）和实时类别（优先级16-31）。

Windows API提供了六个优先级类别（priority class），每个类别对应一个优先级范围：

• IDLE_PRIORITY_CLASS（空闲优先级类别）：优先级最低，只有在系统空闲时才执行，适用于后台任务和低优先级服务。
• BELOW_NORMAL_PRIORITY_CLASS（低于正常优先级类别）：优先级低于正常类别，适用于不需要立即响应的后台任务。
• NORMAL_PRIORITY_CLASS（正常优先级类别）：大多数应用程序的默认优先级类别，提供标准的调度行为。
• ABOVE_NORMAL_PRIORITY_CLASS（高于正常优先级类别）：优先级高于正常类别，适用于需要更快响应的应用程序。
• HIGH_PRIORITY_CLASS（高优先级类别）：高优先级类别，可以抢占大多数其他线程，但应谨慎使用，避免影响系统响应性。
• REALTIME_PRIORITY_CLASS（实时优先级类别）：最高优先级类别，用于实时任务，可以抢占所有其他线程，包括系统线程。

通过这些优先级类别，Windows可以灵活地控制线程的调度优先级，确保关键任务能够及时响应，同时避免低优先级任务被完全饿死。Windows还支持用户模式调度（User-Mode Scheduling, UMS），允许应用程序在用户空间创建和管理线程，减少内核调度的开销，这对于创建大量线程的应用程序（如数据库服务器）来说更加高效。

Solaris调度器

Solaris使用基于优先级的线程调度，每个线程属于六个调度类之一：时间共享（TS）、交互（IA）、实时（RT）、系统（SYS）、公平共享（FSS）和固定优先级（FP）。

时间共享类是默认的调度类，使用多级反馈队列算法。优先级和时间片成反比关系：优先级越高，时间片越短。交互类使用相同的调度策略，但为窗口应用程序提供更高的优先级。 实时类中的线程具有最高优先级，可以抢占其他所有类别的线程。系统类用于运行内核线程，如调度器和分页守护进程。

Solaris将类特定的优先级转换为全局优先级，并选择全局优先级最高的线程运行。内核还维护十个中断服务线程，它们不属于任何调度类，以最高优先级（160-169）执行。

算法评估

选择合适的CPU调度算法需要根据系统类型、工作负载特征和性能要求进行综合考虑。不同的调度算法在不同的场景下表现出不同的性能特征，没有一种算法在所有情况下都是最优的。

例如，考虑五个进程P1、P2、P3、P4、P5，它们的CPU突发时间分别是10、29、3、7、12毫秒。我们可以计算FCFS、SJF和RR（时间片=10毫秒）算法的平均等待时间。

FCFS算法的平均等待时间是28毫秒，SJF算法的平均等待时间是13毫秒，RR算法的平均等待时间是23毫秒。从这个例子可以看出，SJF算法在这个特定工作负载下表现最好，因为它优先执行短进程，最小化了平均等待时间。但需要注意的是，SJF算法需要预知进程的CPU突发时间，这在实际情况中往往不可行。

队列模型

队列模型（queueing model）基于排队论（queueing theory），将计算机系统抽象为服务器网络。每个服务器（如CPU、I/O设备）都有自己的等待队列，进程在队列中等待服务。通过数学分析，可以预测系统的性能指标，如平均队列长度、平均等待时间、系统利用率等。

利特尔公式（Little's Law）是队列分析中的基本公式：$n = λ × W$，其中n是平均队列长度，λ是平均到达率（arrival rate），W是平均等待时间。这个公式适用于任何调度算法和到达分布，是队列理论的基础。通过利特尔公式，我们可以从已知的到达率和等待时间计算出队列长度，或者从队列长度和到达率计算出等待时间。

队列模型的局限性在于只能处理相对简单的算法和分布。复杂的调度算法（如多级反馈队列）和实际的分布模式（如长尾分布）往往难以用数学公式准确描述，需要采用其他评估方法。

模拟

模拟（simulation）是评估CPU调度算法最常用和最直观的方法。模拟器通过编程实现计算机系统的模型，使用数据结构表示系统的主要组件（如CPU、内存、I/O设备、进程队列等）。模拟器维护一个时钟变量，随着模拟时间的推进，模拟器修改系统状态以反映设备、进程和调度器的活动。

模拟数据可以通过几种方式生成。最常见的方法是使用随机数生成器，根据概率分布生成进程到达时间、CPU突发时间、I/O突发时间等事件。分布可以是数学定义的（如均匀分布、指数分布、泊松分布）或基于实际系统测量的经验分布。

另一种方法是使用跟踪文件（trace file）。通过监控真实系统并记录实际事件的序列（如进程创建、CPU突发、I/O操作）来创建跟踪文件，然后使用这个序列来驱动模拟。跟踪文件提供了比较不同算法在完全相同输入下性能的绝佳方式，消除了随机性对结果的影响，使得算法比较更加公平和可靠。

小结

CPU调度是操作系统的核心功能之一，负责从就绪队列中选择下一个要执行的进程，并将CPU控制权分配给该进程。调度决策直接影响系统的性能指标，包括CPU利用率、吞吐量、响应时间、周转时间和公平性。

我们从最简单的先来先服务（FCFS）算法开始，讨论了最短作业优先（SJF）、时间片轮转（RR）、优先级调度、多级队列调度和多级反馈队列调度等经典算法。每种算法都有其适用场景和优缺点，没有一种算法在所有情况下都是最优的。

现代操作系统往往结合多种调度策略，以适应不同的应用场景。多处理器系统引入了负载均衡和处理器亲和性等新的挑战。实时系统对时间约束有严格要求，需要专门的实时调度算法（如RMS、EDF）来保证任务在其截止时间前完成。

小练习

1. FCFS调度算法

假设有5个进程P1、P2、P3、P4、P5，它们的到达时间和CPU突发时间（单位：毫秒）如下表所示：

使用先来先服务（FCFS）调度算法，请计算：

1. 每个进程的完成时间
2. 每个进程的周转时间（完成时间 - 到达时间）
3. 每个进程的等待时间（周转时间 - CPU突发时间）
4. 平均周转时间
5. 平均等待时间

时间轴: 0----10----39----42----49----61
进程:   P1        P2         P3    P4    P5

2. SJF调度算法

使用相同的进程数据，但这次使用最短作业优先（SJF）调度算法（非抢占式），请计算：

1. 调度顺序
2. 每个进程的完成时间、周转时间和等待时间
3. 平均周转时间和平均等待时间

时间轴: 0----10----13----20----32----61
进程:   P1    P3    P4    P5    P2

3. 时间片轮转（RR）调度算法

使用相同的进程数据，采用时间片轮转（RR）调度算法，时间片大小为10毫秒。请计算：

1. 调度顺序和时间轴
2. 每个进程的完成时间、周转时间和等待时间
3. 平均周转时间和平均等待时间

时间轴: 0-10  10-20  20-23  23-30  30-40  40-50  50-60  60-61  61-70
进程:   P1     P2     P3     P4     P5     P2     P5     P2

4. 实时调度可调度性分析

考虑两个周期性实时任务：

• 任务T1：周期P1 = 50ms，执行时间C1 = 20ms
• 任务T2：周期P2 = 100ms，执行时间C2 = 30ms

使用速率单调调度（RMS）算法，请：

1. 确定每个任务的优先级
2. 计算CPU利用率
3. 判断任务集合是否可调度（使用RMS可调度性条件）