如何更好理解 Peterson 算法？

发表于 更新于 分类于 阅读次数： 15 本文字数： 1.9k 阅读时长 ≈ 2 分钟

1 Peterson 算法提出的背景

在我们讲述 Peterson 算法之间，我们先了解一下 Peterson 算法提出前的背景（即：在这个算法提出之前，前人们都做了哪些工作）这对于我们之后理解 Peterson 算法有很大的裨益。

Peterson 算法是基于双线程互斥访问的 LockOne 与 LockTwo 算法而来。LockOne 算法使用一个 flag 布尔数组，LockTwo 使用一个 turn 的整型量，都实现了互斥，但是都存在死锁的可能。Peterson 算法把这两种算法结合起来，完美地用软件实现了双线程互斥问题。

2 Peterson 算法

首先，我们来看看下面这两段代码：

1
2
3
4
5
6
Pi进程：                                  
flag[i] = True;
while(flag[j]);
critical section;
flag[i] = False;
remainder section;

1
2
3
4
5
6
Pj进程：                                
flag[j] = True;
while(flag[i]);
critical section;
flag[j] = False;
remainder section;

以上是用来实现两个进程互斥访问临界区的两端代码，我们可以这样来理解这两段代码，其中 flag[i] 表示进程 Pi 表示想要进入临界区，while(flag[j]) 可以理解为 Pi 在自己进临界区之前，先问问 Pj 是否想要进入临界区，如果 Pj 想进的话它就等待（Pi 品德高尚）；类似的，Pj 也是同样的。双方互相谦让的结果是，最终两个进程谁也进不了临界区。（可以想象这样一个生活场景，两个人同时想进屋，结果在门口谦让了了半天，过了很久都没进去）

Peterson 算法就是在上面代码的基础之上，又引入了一个变量 turn，打破了这种因为谦让而导致 “饥饿” 的现象。下面我们先来看看 Peterson 算法的代码：

1
2
3
4
5
6
7
Pi进程：                                  
flag[i] = True;
turn = j;
while(flag[j] && turn == j);
critical section;
flag[i] = False;
remainder section;
1
2
3
4
5
6
7
Pj进程：                                  
flag[j] = True;
turn = i;
while(flag[i] && turn == i);
critical section;
flag[j] = False;
remainder section;

怎么理解变量 turn 呢？可以将 turn 变量理解成轮到谁进入临界区了。举个例子：turn = i，表示轮到 Pi 进入临界区。那么上面这个代码就可以理解为：首先，Pi 想进入临界区（flag[i] = True），然后，还是和前面的代码一样，Pi 会先把进入临界区的机会让给 Pj（turn = j），同样地，当 Pj 想进入临界区时，也会将进入临界区的权利先让给 Pi。紧接着，变量 turn 的作用就显现出来了，当 Pj 把进入临界区的机会又让给 Pi 的时候（注意：这是发生在 Pi 将进入临界区的优先权让给 Pj 之后），Pi 这次就会直接进入临界区。就不会再次出现一直互相谦让，最终导致均无法进入临界区的情况了。

关于为什么当进入临界区的权利（即 turn = i）又回到 Pi 手里时，Pi 会直接进入临界区的分析？我们可以分析一下 Pi 能够成功进入临界区的条件（即：while (flag [j] && turn == j) 语句）：

总的分为以下两种情况：

  1. Pj 不想进入临界区（flag [j] = False）

    当 Pj 不想进入临界区时，自然也就不存在 Pi 和 Pj 冲突的情况，Pi 当然就直接进入临界区。

  2. Pj 想进入临界区（flag [j] = True）

    当 Pj 想进入临界区，又分为以下两种情况：

  • 当 turn = i

    turn = i 说明当前轮到 i 进入临界区了 ，这个时候 i 就直接进入临界区了，不再谦让。（其实这个挺合理的，根据 Peterson 算法的代码我们不难发现因为 turn 的值是根据先后想要进入临界区的顺序排列的）

  • 当 turn != i

    turn != i 说明当前轮到 i 进入临界区了没有轮到 Pi 进入临界区，Pi 自然需要等待。

仅过上面的分析，我们就不难理解，当 Pi 和 Pj 经过一轮谦让之后，就会直接根据 turn 的值（即：该轮到谁进临界区了）来直接决定谁该进入临界区。现在回过头回顾整个算法，其实我们会发现，Peterson 算法的思想会更贴近于生活中的真实情况，大家一般都是略微谦让一下，然后直奔主题，难道不是吗？哈哈

3 参考资料

[1] 维基百科编者. Peterson 算法 [G/OL]. 维基百科，2021 (20210501)[2021-05-01]. https://zh.wikipedia.org/w/index.php?title=Peterson%E7%AE%97%E6%B3%95&oldid=65429794.