操作系统中的进程同步：Peterson算法

描述
Peterson算法是一种经典的软件解决方案，用于解决两个进程（或线程）在并发环境下的临界区（Critical Section）问题。该算法确保两个进程不会同时进入临界区，从而避免数据竞争和不一致性。它仅使用共享内存，无需硬件同步指令（如原子操作），适用于单处理器或多处理器系统。Peterson算法的核心思想是通过两个共享变量（一个标志数组和一个轮转变量）来实现互斥。

知识点结构

1. 临界区问题回顾：多个进程需要互斥地访问共享资源，临界区代码必须满足互斥、进步和有限等待三个条件。
2. Peterson算法的共享变量：
   • flag[2]：布尔数组，flag[i]表示进程i是否想进入临界区。
   • turn：整型变量，表示当前允许进入临界区的进程编号。
3. 算法步骤：每个进程在进入临界区前执行特定代码，退出时重置标志。
4. 正确性分析：证明算法如何满足互斥、进步和有限等待条件。
5. 局限性：仅适用于两个进程，且可能受内存重排序影响。

循序渐进讲解

第一步：临界区问题与算法目标

• 问题背景：假设有两个进程P0和P1，它们共享一个变量（如计数器），需要修改该变量的代码称为临界区。若不加同步，两个进程可能同时修改数据，导致结果错误。
• 目标：设计一种协议，使得：
  1. 互斥：任一时刻最多一个进程在临界区内。
  2. 进步：若无进程在临界区内，则某个想进入的进程最终能进入。
  3. 有限等待：进程不会无限期等待进入临界区。

第二步：Peterson算法的变量定义
算法使用两个共享变量：

• flag[0]和flag[1]：初始均为false。当进程i想进入临界区时，设置flag[i] = true。
• turn：取值为0或1，表示若两个进程同时想进入，则turn决定优先权（类似“谦让”机制）。
  变量需存储在共享内存中，确保进程均可访问。

第三步：算法代码与执行流程
以进程P0的视角（P1对称）：

// 进程P0的代码
flag[0] = true;           // 步骤1：P0表示想进入临界区
turn = 1;                 // 步骤2：将优先权让给P1
while (flag[1] == true && turn == 1) { 
    // 忙等待：如果P1想进入且当前轮次是P1，则P0循环等待
}
// 临界区代码：执行共享资源操作
flag[0] = false;          // 退出临界区：重置标志

• 步骤解释：
  1. flag[0]=true：P0声明意图。
  2. turn=1：主动将优先权交给P1（体现“谦让”）。
  3. 循环条件：若P1也想进入（flag[1]==true）且轮次是P1（turn==1），则P0等待；否则P0进入临界区。
  4. 退出时设置flag[0]=false，表示不再需要进入。

第四步：正确性分析（为什么能保证互斥？）

• 互斥证明：假设P0和P1同时进入临界区，则双方都必须通过循环条件。
  • 若P0进入，则必有flag[1]==false或turn==0。
  • 若P1进入，则必有flag[0]==false或turn==1。
  • 但双方同时设置flag为true后，turn只能有一个值（最后写入的进程生效）。
  • 若turn=0，则P1会因turn==0而等待（P1的循环条件为flag[0]==true && turn==0）；若turn=1，则P0等待。矛盾！故互斥成立。

第五步：进步与有限等待的满足

• 进步：若P0在临界区外，则P1进入时只需判断flag[0]和turn。若P0不想进入（flag[0]=false），P1可直接进入；若P0想进入，但turn=1，则P1进入。不会出现双方互相阻塞。
• 有限等待：进程P0退出临界区时重置flag[0]=false，若P1在等待，则P1立即进入。下一次P0想进入时，会设置turn=1，保证P1优先，避免饥饿。

第六步：局限性讨论

• 仅限两个进程：算法设计针对两个进程，多进程需扩展（如Filter算法）。
• 内存可见性问题：在现代多核处理器中，编译器和硬件可能重排序指令（如先执行turn=1再执行flag[0]=true），导致错误。解决方案需添加内存屏障（Memory Barrier）或使用原子操作。
• 忙等待缺点：等待进程占用CPU，不适用于单处理器高负载场景（可结合调度优化）。

总结
Peterson算法以简洁的代码实现了临界区互斥，是理解软件同步的经典案例。尽管实际应用中多采用硬件支持的原子操作（如互斥锁），但该算法揭示了同步问题的本质：通过共享变量协调进程意图与轮次，实现公平互斥。