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;
…
资料显示这种方法会违背空闲则入的原则,请问是为什么?
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;
…
资料显示这种方法会违背空闲则入的原则,请问是为什么?
收起
引自免费微信小程序:皆我百晓生
在Dekker算法中,两个进程(P0和P1)通过共享变量flag[0]
和flag[1]
以及一个循环结构来实现对临界区的访问控制。尽管该算法旨在确保同一时刻只有一个进程能进入临界区,但其设计确实存在违背“空闲则入”原则的情况。下面详细解释这一现象及其原因。
“空闲则入”原则: “空闲则入”是进程同步互斥算法应遵循的基本原则之一,它要求当临界区处于空闲状态且有进程请求进入时,该进程应当被立即允许进入,不应无故阻塞。即如果有多个进程竞争临界区,且当前无人占用,那么应该让等待队列中的下一个进程顺利进入。
Dekker算法存在的问题:
考虑以下场景:
flag[0] = false, flag[1] = false
,表明两个进程均未申请进入临界区。while(flag[1])
),检测到flag[1]
为false
,因此不阻塞,继续执行。while(flag[0])
),同样检测到flag[0]
为false
,因此也不阻塞,继续执行。flag[0]
设置为true
(表示申请进入临界区),然后准备进入临界区。
flag[1]
设置为true
,同样准备进入临界区。此时,尽管临界区实际上是空闲的(因为之前没有进程在里面),但由于P0和P1几乎同时进行了申请操作,导致双方都看到对方尚未申请(即各自的循环检查条件在另一方申请前已通过),进而都试图进入临界区。这构成了所谓的“竞态条件”,违反了“空闲则入”的原则,因为实际上只有一个进程可以真正进入临界区,另一个进程会被无谓地阻塞在外。
要解决这个问题,通常需要引入额外的同步机制,如更复杂的标志交换、使用硬件提供的原子指令(如test-and-set、compare-and-swap等),或者采用更高层次的同步原语如信号量、互斥锁等。这些方法能确保即使在并发环境下,进程间的同步也能符合“空闲则入”原则,不会出现上述无效阻塞的情况。
综上所述,Dekker算法由于缺乏足够的同步保证,在特定并发情况下会导致违背“空闲则入”原则,使得临界区在实际空闲时仍可能阻止某个符合条件的进程进入。为实现有效的进程同步互斥,需采用更为健壮的同步算法或原语。
报告相同问题?