进程同步的Dekker算法初版改进为什么违背忙则等待和空闲则入？

Question

Dekker 算法经过很多版本的改进才是最终的样子，它的初版是这样的

/*PROCESS 0*/
…
while(flag[1]); flag[0]=true;
临界区
flag[0]=false;
…
/*PROCESS 1*/
…
while(flag[0]);
flag[1]=true; 
临界区
flag[1]=false;
…

上述算法实现了忙则等待：当P0在临界区中时，turn值为0，只有P0出临界区后，将turn值修改为1，P1才能进入自己的临界区。但违背了空闲则入：若P0停在while判断之前的位置，而此时turn值又为0，则P1不能进入临界区。这就意味着，如果一个进程运行失败，另一个进程也将永久被阻止。
改进如下

/*PROCESS 0*/
…
while(flag[1]); 
flag[0]=true;
临界区
flag[0]=false;
…
/*PROCESS 1*/
…
while(flag[0]);
flag[1]=true; 
临界区
flag[1]=false;
…

资料上说违背忙则等待：flag[0]和flag[1]都为false时，两进程都可以进入临界区。但是1在进入临界区前已经把fala[0]置为true了啊；是按照while(flag[1]); while(flag[0]);flag[0]=true;flag[1]=true;的顺序执行时会违背忙则等待吗？
还有违背空闲则入：flag[0]和flag[1]初值都为true时，两进程都不能进入临界区。也是按照while(flag[1]); while(flag[0]);的顺序执行？

Answer 1

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

您的问题涉及对Dekker算法初版及其改进的理解与分析，以及它们是否遵循“忙则等待”和“空闲则入”的原则。针对您提供的代码片段和疑问，我会进行详细的解答。

首先，我们明确一下“忙则等待”（Bounded Waiting）和“空闲则入”（Mutual Exclusion）的概念：

• 忙则等待：一个进程试图进入临界区时，如果其他进程已经在临界区内，它最多等待有限次就能进入临界区。
• 空闲则入：当临界区处于空闲状态时，任何请求进入临界区的进程都能立即获得访问权限。

接着，我们分别分析Dekker算法初版及改进版：

Dekker算法初版

/* PROCESS 0 */
...
while (flag[1]);   // 原文中的这段代码似乎重复，已删除重复部分
flag[0] = true;
临界区
flag[0] = false;
...

/* PROCESS 1 */
...
while (flag[0]);
flag[1] = true;
临界区
flag[1] = false;
...

在这个初版中，确实存在您指出的问题：

1. 违背空闲则入：如果进程P0因故停留在while(flag[1])判断语句之前（例如，P0被中断），而此时flag[0]仍为初始值false。这时，即使临界区空闲（即P1也未进入临界区），P1也会因为while(flag[0])条件满足而阻塞在入口处，导致两个进程都无法进入临界区，违反了“空闲则入”。

2. 违背忙则等待：当两个进程同时到达各自的入口，且flag[0]和flag[1]均为false时，由于没有额外的协调机制，两个进程可能同时进入临界区，破坏了“忙则等待”。这是因为两个进程可能会同时通过各自的while循环检查，然后各自设置自己的标志位为true，进而同时进入临界区。

综上所述，Dekker算法初版确实违背了“忙则等待”和“空闲则入”。

接下来，关于您提到的“改进”，其内容实际上与初版相同，并未进行实质性的改变。因此，基于上述分析，这个“改进”版本依然存在同样的问题，即违背“忙则等待”和“空闲则入”。

对于您后续的疑问，描述的似乎是Dekker算法的一个理想化执行流程，而非实际存在的问题。在实际情况中，没有额外的同步机制确保两个进程严格按照特定顺序执行操作。即便按照理想的顺序执行，也不能解决初版算法中存在的问题。

总结来说，Dekker算法初版及其所谓的“改进”版本均未能有效实现“忙则等待”和“空闲则入”原则。正确的改进应引入适当的同步机制，如增加一个“turn”变量或其他更复杂的逻辑，以确保两个进程有序地、互斥地进入临界区。如果您需要了解修正后的Dekker算法或相关改进版本，请提供具体代码或详细描述，我将为您进一步分析。