Dekker 算法

beyes

初步设想是这样的：
定义全局布尔变量 turn ，其值 0, 1 分别表示 P0 和 P1 进程占有了临界区。

对于 P0 进程：

[C++] 纯文本查看 复制代码

bool turn;
/* 对于 P0 进程 */
while (turn != 0)
;   /*什么都不做,忙等待*/

/*********************/
/*  临界区代码    */
/*********************/

turn = 1;

对于 P1 进程：

[C++] 纯文本查看 复制代码

bool turn;
/* 对于 P0 进程 */
while (turn != 1)
;   /*什么都不做,忙等待*/

/*********************/
/*  临界区代码    */
/*********************/

turn = 0;

从上面的设计中，可以看到存在两个问题：
1. 当 turn = 0 时，P1 是需要一直忙等待 turn = 1 时方可进入临界区。如果 P0 在 turn = 0 时一直没有进入临界区，那么 P1 的等待就是白等！
2. 如果任何一个进程在自己的临界区代码里失败(如死循环)或在临界代码外失败了，那么另外一个进程将永远无法进入自己的临界区！

下面对上面的设计进行改进：
使用全局共享数组 flag 标志临界区的状态：
当 flag[0] 或 flag[1] 为 ture 时，表示 P0 或 P1 在使用临界区；
当 flag[0] 或 flag[1] 为 false 时，表示 P0 或 P1 不使用临界区。

此时对于 P0 进程：
[code=css]bool flag[2];
while (flag[1])
;  /*什么都不做,忙等待*/

flag[0]=1;
/*********************/
/*  临界区代码    */
/*********************/
flag[0]=0;[/mw_shl_code]

此时对于 P1 进程：
[code=css]bool flag[2];
while (flag[0])
;  /*什么都不做,忙等待*/

flag[1]=1;
/*********************/
/*  临界区代码    */
/*********************/
flag[1]=0;[/mw_shl_code]

从上面的设计中可以看到，如果 P0 在临界区里死了，P1 仍然会忙等待无法进入临界区代码。但如果假设 P0 永不会死在临界区中，那么就不会出现像第一种情况里有一个进程进行“无辜”等待的情况。也就是说，P0 或 P1 是看对方的情况来访问临界区的，而不是看第三者(第一种情况中的 turn 变量)的脸色访问临界区的。但是这里，仍然存在一个问题，如果 flag[0] == flag[1] == false 时会出现什么情况？这时候，P0 和 P1 都有可能进入临界区。假设某时刻，CPU 将时间片分给了 P0，于是 P0 在 while 中判断 flag[0] 为 false 而往下走，这时 CPU 刚好又将时间片分给了 P1，于是 P1 也能顺利的进入临界区。这种情况违背了互斥和忙则等待的原则。

针对上面的改进再做修正：
由于上面有可能同时检测到 flag[0]=flag[1]=0 而两个进程同时进入临界区的情况。所以在此考虑将“先检测临界区状态(检查flag[0]或flag[1]标志)改为”先设置标志位“，也就是说，P0 和 P1 谁要是想访问临界区，谁就先举手声明一下自己这一意愿。这种做法，用代码表示如下：


对于 P0 进程：

[C++] 纯文本查看 复制代码

bool flag[2];
flag[0] = true;  /* 我要访问临界区，先告知大家一下*/
while (flag[1])  /* 看看 P1 有没有在临界区中，有的话我就等等 */
;
/*********************/
/*  临界区代码    */
/*********************/
flag[0] = false;          /*访问完了*/

对于 P1 进程：

[C++] 纯文本查看 复制代码

bool flag[2];
flag[1] = true;  /* 我要访问临界区，先告知大家一下*/
while (flag[0])  /* 看看 P0 有没有在临界区中，有的话我就等等 */
;
/*********************/
/*  临界区代码    */
/*********************/
flag[1] = false;          /*访问完了*/

但是这么一来，又有个问题了。比如当 P0 声明完自己要访问临界区后(flag[0] = true)，时间片轮转到 P1，这时 P1 也进行了声明，然后到 P0 运行时，发现 P1 已经用了临界区，自己就进行忙等待，同理 P1 也会因此进入忙等待。在这种情况下，发生了死锁，结果是两人都无法进入临界区。

---

综合上面所出的问题，进行最终的改进，得到了成功的 Dekker 算法，以 P0 的执行流程为例，得到流程图如下：

使用代码描述：

[C++] 纯文本查看 复制代码

        bool flag[2];
        flag[0] = false;
        flag[1] = false;


        bool turn = 0;


        flag[0] = true;
        while (flag[1]) {
                if (turn) {
                        flag[0] = false;
                        while (turn);
                        flag[0] = true;
                }
        }
        /* critical section code */
        ...
        
        turn = 1;
        flag[0] = false;


        /* remainder section */

代码说明：

第 9 行，P0 宣称自己要进入临界区了。
第 10 行，虽然 P0 已经宣布自己要进入临界区，但这还不够，因为 P1 可能也已经宣布。
第 11 行，两人都宣布要进入临界区，那要看谁已经进入。不管谁先进入临界区了它都要对 turn  进行相应设置，P0 退出临界区时使 turn=1 以表明 P1 对临界区可用了； P1 退出临界区时使 turn=0 以表明 P0 对临界区可用了。
第 12 行，发现 P1 进入，P0 就暂时宣布自己不想进入临界区。
第 13 行，一直在侦测 P1 是不是从临界区出来了，如果没出来，那么 P0 就忙等待。
第 14 行，P1 已经从临界区出来，P0 可以再次宣称自己要进入临界区。注意，这里仍然要返回到第 10 行的循环再次判断一下 P1 是否又宣称自己进入临界区且又占据了临界区资源。如果 P1 已经完全退出的话，那 P0 就安心的进入临界区。
第 20 行，P0 从临界区出来后，要标志一下 trun，以表明自己从临界区出来了。
第 21 行，表明自己暂时不想再进去临界区。
第 24 行，做其余的代码功能。


P1 的代码和 P0 是同理的，P1 进程代码如下：

[C++] 纯文本查看 复制代码

          flag[1] = true;
        while (flag[0]) {
                if (turn != 1) {
                        flag[1] = false;
                        while (turn != 1);
                        flag[1] = true;
                }
        }
        /* critical section code */
        ...
        
        turn = 0;
        flag[1] = false;


        /* remainder section */