第11章 多处理机操作系统

多处理机系统概述

多处理机系统是由多个CPU（或多个核）通过互连网络连接组成的系统，具有共享或分布的内存结构和I/O设备。

多处理机系统分类

按内存结构分类

• 共享内存多处理机（SMP）：

  • 所有CPU共享同一主存空间
  • CPU间通信通过共享内存
  • 扩展性受限于内存带宽和缓存一致性

• 分布式内存多处理机：

  • 每个CPU有自己的本地内存
  • CPU间通信通过消息传递
  • 可扩展性好，但编程复杂

按CPU类型分类

• 同构多处理机：所有CPU相同
• 异构多处理机：CPU类型不同（如CPU+GPU）

多处理机调度

调度分类

• 集中式调度：由一个调度器负责所有CPU的调度
• 分布式调度：每个CPU有自己的调度器
• 层次式调度：结合集中式和分布式的优点

调度算法

• 负载均衡：将工作负载均匀分配到各个CPU
• 亲和性调度：尽量让进程在同一CPU上运行
• 工作组调度：将相关进程调度到同一CPU组

缓存一致性

缓存一致性问题

在共享内存多处理机系统中，多个CPU的缓存可能包含同一内存地址的副本，需要保证所有CPU看到一致的数据。

缓存一致性协议

• MESI协议：

  • Modified（M）：数据被修改，只在一个缓存中
  • Exclusive（E）：数据未修改，只在一个缓存中
  • Shared（S）：数据未修改，在多个缓存中
  • Invalid（I）：数据无效

• MOESI协议：在MESI基础上增加Owner状态

同步机制

原子操作

• 测试并设置（Test-and-Set）：原子地设置值并返回旧值
• 比较并交换（Compare-and-Swap）：原子地比较并交换值
• 加载链接/条件存储（LL/SC）：成对的原子操作

锁机制

• 自旋锁：忙等待获得锁
• 排队锁：按FIFO顺序分配锁
• 读-写锁：允许多个读者或一个写者

屏障（Barrier）

• 全局屏障：所有进程必须到达屏障点
• 本地屏障：进程组内所有进程到达屏障点

多处理机性能优化

负载均衡

• 静态负载均衡：在编译时分配负载
• 动态负载均衡：运行时根据CPU负载动态调整

缓存优化

• 数据局部性：提高时间和空间局部性
• 伪共享避免：确保相关数据在同一缓存行

内存层次结构优化

• NUMA优化：优先访问本地内存
• 预取技术：提前加载可能需要的数据

多处理机操作系统类型

主机操作系统（Master-Slave）

• 一台主计算机管理所有资源
• 其他计算机作为从机执行计算任务
• 优点：实现简单
• 缺点：主计算机成为瓶颈

对称多处理机（SMP）

• 所有CPU地位平等，共同管理资源
• 优点：没有单点故障，可扩展性好
• 缺点：同步开销大

分布式操作系统

• 多个独立的操作系统协同工作
• 优点：可靠性高，容错能力强
• 缺点：实现复杂，通信开销大

并行程序设计

并行编程模型

• 共享内存模型：使用锁、信号量等同步机制
• 消息传递模型：使用MPI等消息传递库
• 数据并行模型：对数据集合进行并行操作

并行性能指标

• 加速比：并行执行时间与串行执行时间的比值
• 效率：加速比与处理器数量的比值
• 可扩展性：性能随处理器数量增长的保持能力