能否仅使用turn变量实现Peterson算法？flag数组是否冗余？

课堂展示的Peterson算法代码 #

// P0:
do {
  flag[0] = TRUE; turn = 1;
  while(flag[1] && turn == 1);

  // Critical section
  flag[0] = FALSE;
  // remainder section
} while(1)


// P1:
do {
  flag[1] = TRUE; turn = 0;
  while(flag[0] && turn == 0);
  
  // critical section
  flag[1] = FALSE;
  // remainder section
} while(1)

问题 #

请问是否可以仅使用turn这一个变量实现Peterson算法？仅依靠turn变量是否已能满足临界区的相关要求？此处的flag[]数组是否属于冗余设计？

解答 #

核心结论 #

不能仅用turn变量实现Peterson算法，仅靠turn无法满足临界区全部要求，flag数组绝非冗余设计

1. 仅用turn变量无法实现Peterson算法的核心逻辑 #

如果移除flag数组，仅保留turn变量，假设修改后的逻辑如下：

// P0
do {
  turn = 1;
  while(turn == 1);
  // 临界区
  turn = 0;
  // 剩余区
} while(1);

// P1
do {
  turn = 0;
  while(turn == 0);
  // 临界区
  turn = 1;
  // 剩余区
} while(1);

这种情况下会出现致命问题：比如P0先执行turn=1，随即进入循环等待；此时P1执行turn=0，也进入循环等待——两个进程会互相死锁，永远无法进入临界区，直接违背了算法的核心目标。

2. 仅靠turn变量无法满足临界区的全部要求 #

临界区同步必须满足三个核心准则：

• 互斥性：同一时间只能有一个进程进入临界区
• 前进性：当无进程在临界区时，必须允许等待的进程进入
• 有限等待：任何进程等待进入临界区的时间必须有限

仅使用turn变量时：

• 互斥性勉强可以保证，但前进性完全失效，如上述死锁案例，两个进程会无限等待；
• 有限等待也无法满足，进程可能永远卡在循环中无法推进。

3. flag数组是Peterson算法的核心，绝非冗余 #

flag数组的核心作用是让进程主动声明进入临界区的意图：

• 进程设置flag[i]=TRUE，相当于向其他进程发出“我要进入临界区”的信号；
• 结合turn变量的“谦让”逻辑（比如P0设置turn=1，把进入权优先让给P1），可以避免无意义的死等：如果P0声明要进入，但P1并没有进入意图（flag[1]=FALSE），P0可以直接进入临界区，无需等待；
• 简言之，flag负责“告知意图”，turn负责“冲突时的优先级判定”，两者结合才能同时满足互斥性、前进性和有限等待三大准则，缺一不可。

内容的提问来源于stack exchange，提问作者Done