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

1. 问题背景：临界区问题
在多进程/多线程环境中，当多个执行流需要访问共享资源（如变量、数据结构等）时，可能会因为交替执行导致数据不一致，这就是临界区问题。我们需要一种机制确保：

• 互斥：同一时刻只有一个进程能进入临界区。
• 进展：如果没有进程在临界区内，那么需要进入临界区的进程能够进入。
• 有限等待：进程从申请进入临界区到获准进入的等待时间是有限的。

2. Peterson算法的基本思想
Peterson算法是一种经典的软件解决方案，用于两个进程/线程之间的同步。它不需要特殊的硬件指令（如Test-and-Set），仅通过共享变量来实现互斥。其核心思想是"礼貌谦让"：

• 每个进程都先表达自己想进入临界区的意愿。
• 然后指定另一个进程为"优先者"。
• 只有当对方不想进入，或者对方指定我为优先时，我才能进入。

3. 算法所需的共享变量

• int turn; // 表示当前轮到哪个进程进入（0或1）
• bool flag[2]; // 表示进程是否想进入临界区（flag[0]对应进程0，flag[1]对应进程1）

4. 算法的详细步骤
假设有两个进程P0和P1（其ID分别为0和1）。

进程Pi（i为0或1）的代码：

while (true) {
    // 1. 表达进入意愿
    flag[i] = true;
    
    // 2. 指定对方为优先者
    turn = j;  // j是另一个进程的ID（1-i）
    
    // 3. 谦让检查：只有当对方不想进入，或者对方指定我优先时，我才能进入
    while (flag[j] == true && turn == j) {
        // 忙等待（busy-waiting）
    }
    
    // 4. 进入临界区
    // ... 访问共享资源 ...
    
    // 5. 离开临界区
    flag[i] = false;
    
    // 6. 剩余区代码
    // ...
}

进程Pj（j=1-i）的代码对称。

5. 逐步解析算法逻辑

• 步骤1（flag[i]=true）：进程Pi明确表示"我想进入临界区"。
• 步骤2（turn=j）：Pi礼貌地说"你先请"，将优先权让给Pj。
• 步骤3（while条件检查）：
  • 如果Pj不想进入（flag[j]==false），Pi直接进入临界区。
  • 如果Pj也想进入（flag[j]==true），则检查turn的值：
    • 如果turn==j（确实轮到Pj），Pi循环等待。
    • 如果turn==i（实际上轮到Pi），Pi进入临界区。

6. 为什么能保证互斥？
假设P0和P1同时试图进入临界区：

• 它们都会设置自己的flag为true。
• 最后执行turn=语句的进程将决定turn的最终值。
• 由于turn只能是0或1，只有一个进程能通过while条件检查：
  • 如果turn最终为0，P0看到turn==0（自己）而通过检查，P1看到turn==0（对方）而等待。
  • 如果turn最终为1，P1通过检查，P0等待。

7. 为什么能保证进展和有限等待？

• 进展：如果没有进程在临界区，想进入的进程不会被阻止。
• 有限等待：当进程Pi离开临界区时，它会设置flag[i]=false，这会立即释放Pj的等待（如果Pj在等待）。如果Pj在Pi之后表达意愿，turn的值会确保其中一个进程能进入。

8. 算法的局限性

• 仅适用于两个进程：Peterson算法不能直接扩展到多个进程。
• 忙等待：等待的进程会持续检查条件，浪费CPU资源。
• 内存屏障问题：在现代多核处理器上，需要内存屏障确保flag和turn的修改对其他核心立即可见。

9. 实际应用
虽然Peterson算法本身很少直接用于生产环境（因有更高效的硬件指令如CAS），但它：

• 是理解同步问题的经典教学案例。
• 展示了如何用纯软件实现互斥。
• 为更复杂的同步机制提供了理论基础。

通过这个逐步分析，你应该能理解Peterson算法如何巧妙地利用两个共享变量，在不需要硬件支持的情况下解决两个进程的临界区问题。