操作系统中的进程调度算法：多处理器调度（Multiprocessor Scheduling）详解 在多处理器系统（如多核CPU）中，多个进程可以真正并行执行，这带来了新的调度挑战。多处理器调度不仅要考虑如何选择进程运行，还要考虑如何将进程分配到合适的处理器上，以优化系统性能（如吞吐量、响应时间）和资源利用率（如负载均衡、缓存亲和性）。 1. 多处理器调度的主要挑战 与单处理器调度相比，多处理器调度面临以下独特问题： 负载均衡（Load Balancing） ：确保所有处理器的工作负载大致相当，避免某些处理器空闲而其他处理器过载。 缓存亲和性（Cache Affinity） ：进程在某个处理器上运行时，其数据会被缓存到该处理器的缓存中。若进程能被调度到同一处理器上，可减少缓存失效，提升性能。 同步开销（Synchronization Overhead） ：多个进程并行访问共享资源时，需通过锁等机制同步，这可能引发竞争和等待。 处理器异构性（Heterogeneity） ：处理器可能性能不同（如大小核架构），需根据进程需求合理分配。 2. 多处理器调度的方法分类 根据处理器的同构性，调度方法可分为两类： 对称多处理器调度（Symmetric Multiprocessing Scheduling, SMP Scheduling） ：所有处理器功能相同，操作系统可统一管理所有处理器和进程队列。 非对称多处理器调度（Asymmetric Multiprocessing Scheduling, AMP Scheduling） ：指定一个主处理器（如Master）处理系统任务（如I/O、调度），其他处理器（Workers）只执行用户进程。这种方式简单但主处理器可能成为瓶颈。 现代操作系统主要采用SMP调度，以下重点讲解其常见策略。 3. SMP调度的常见策略 策略1：全局队列（Global Queue） 描述 ：系统维护一个全局就绪队列，所有处理器从一个共享队列中选取进程执行。 工作流程 ： 任何新就绪的进程都被放入全局队列。 当处理器空闲时，它从全局队列中选取一个进程（根据特定算法，如优先级、时间片轮转）。 选取时需加锁以保证队列操作的原子性。 优点 ：自动实现负载均衡，因为空闲处理器总会从队列中取进程。 缺点 ： 锁竞争可能成为瓶颈（尤其在处理器多时）。 可能破坏缓存亲和性，因为进程可能被调度到不同处理器上。 策略2：局部队列（Per-Processor Queue） 描述 ：每个处理器维护自己的就绪队列，进程被固定分配到某个处理器的队列中。 工作流程 ： 进程创建时，根据某种策略（如轮询、随机）分配到某个处理器的队列。 处理器只从自己的队列中选取进程执行。 若某个处理器的队列为空，而其他队列有进程，需通过负载均衡机制迁移进程。 优点 ： 减少锁竞争（每个队列独立）。 增强缓存亲和性（进程倾向于在同一处理器运行）。 缺点 ：可能负载不均衡，需额外机制实现负载均衡。 4. 负载均衡机制 在局部队列策略中，负载均衡是关键，常见方法包括： 推送式负载均衡（Push Migration） ：一个监控线程（如周期性运行的负载均衡器）检测各处理器负载，若发现不均衡，主动将进程从过载处理器的队列迁移到空闲队列。 拉取式负载均衡（Pull Migration） ：当某个处理器空闲时，它主动从其他处理器的队列中“偷取”进程执行（称为Work Stealing）。 5. 实际系统中的多处理器调度 Linux CFS（Completely Fair Scheduler） ：采用局部队列策略，每个CPU有一个运行队列（runqueue）。通过周期性的负载均衡（如每1ms检查）和Work Stealing机制实现均衡。同时，CFS会考虑缓存亲和性，优先将进程调度到上次运行的CPU。 Windows调度器 ：支持全局队列和局部队列的混合策略。初始分配基于处理器组，但允许跨组迁移以平衡负载。 6. 调度示例：局部队列与负载均衡 假设双核系统（CPU0、CPU1），每个CPU有一个就绪队列： 初始状态：CPU0队列有进程P1、P2；CPU1队列有进程P3。 CPU1先完成P3的执行，队列为空。 负载均衡机制触发（如Work Stealing）：CPU1从CPU0的队列中偷取P2。 结果：CPU0运行P1，CPU1运行P2，实现负载均衡。 总结 多处理器调度通过全局队列或局部队列策略，结合负载均衡机制，在并行性和缓存效率之间权衡。理解这些机制有助于设计高效的多线程应用（如避免虚假共享、优化数据局部性）。实际系统中，调度器会动态调整策略以适应负载变化。