如何更好理解Peterson算法?

发表于 更新于 分类于 阅读次数： 本文字数： 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.