进程同步互斥算法中违背空闲则如的问题

Question

Dekker算法的初步设想是这样的：

/*PROCESS 0*/
…
while(flag[1]);/*判断P1是否申请进入临界区*/①
flag[0]=true;/*P0申请进入临界区*/
临界区
flag[0]=false;/*进入完成，撤回申请*/
…
/*PROCESS 1*/
…
while(flag[0]);
flag[1]=true;
临界区
flag[1]=false;
…

资料显示这种方法会违背空闲则入的原则，请问是为什么？

Answer 1

引自免费微信小程序：皆我百晓生

在Dekker算法中，两个进程（P0和P1）通过共享变量flag[0]和flag[1]以及一个循环结构来实现对临界区的访问控制。尽管该算法旨在确保同一时刻只有一个进程能进入临界区，但其设计确实存在违背“空闲则入”原则的情况。下面详细解释这一现象及其原因。

“空闲则入”原则： “空闲则入”是进程同步互斥算法应遵循的基本原则之一，它要求当临界区处于空闲状态且有进程请求进入时，该进程应当被立即允许进入，不应无故阻塞。即如果有多个进程竞争临界区，且当前无人占用，那么应该让等待队列中的下一个进程顺利进入。

Dekker算法存在的问题：

考虑以下场景：

1. 初始状态： flag[0] = false, flag[1] = false，表明两个进程均未申请进入临界区。
2. 并发执行： P0和P1几乎同时开始执行，并尝试进入临界区。
   • P0执行到第①行（while(flag[1])），检测到flag[1]为false，因此不阻塞，继续执行。
   • 同时，P1也执行到相似的检查（while(flag[0])），同样检测到flag[0]为false，因此也不阻塞，继续执行。
3. 冲突发生： 紧接着，P0将flag[0]设置为true（表示申请进入临界区），然后准备进入临界区。
   • 同时，P1也将flag[1]设置为true，同样准备进入临界区。

此时，尽管临界区实际上是空闲的（因为之前没有进程在里面），但由于P0和P1几乎同时进行了申请操作，导致双方都看到对方尚未申请（即各自的循环检查条件在另一方申请前已通过），进而都试图进入临界区。这构成了所谓的“竞态条件”，违反了“空闲则入”的原则，因为实际上只有一个进程可以真正进入临界区，另一个进程会被无谓地阻塞在外。

要解决这个问题，通常需要引入额外的同步机制，如更复杂的标志交换、使用硬件提供的原子指令（如test-and-set、compare-and-swap等），或者采用更高层次的同步原语如信号量、互斥锁等。这些方法能确保即使在并发环境下，进程间的同步也能符合“空闲则入”原则，不会出现上述无效阻塞的情况。

综上所述，Dekker算法由于缺乏足够的同步保证，在特定并发情况下会导致违背“空闲则入”原则，使得临界区在实际空闲时仍可能阻止某个符合条件的进程进入。为实现有效的进程同步互斥，需采用更为健壮的同步算法或原语。