今天终于考完了试。打算补一下博客之类的，想起来复习操作系统的时候，在选择一个进程进入临界区的时候有个算法叫Peterson算法，感觉理解起来非常好玩，于是打算在这里介绍一下我的理解。

问题说明

首先必须要说清的是问题到底是什么。

在操作系统中，协作的进程会共享一些公共区域。而对这个区域的操作结果取决于操作进行的时序。于是就需要一点手段来阻止多个进程同时访问该共享区域。把要访问共享区域的代码称为临界区，就能把这个问题称作“临界区问题”。

这个问题要满足下面四个条件：

  1. 任何两个进程不能同时处于临界区
  2. 不得使进程无限期等待进入临界区
  3. 临界区外的进程不能阻塞其他进程
  4. 不应对CPU的速度和数量做假设

这样就相当于有了一点前情提要了。这里没有涉及硬件支持的手段和系统提供的信号量之类的东西，只是在忙等待的情况下所使用的方案。

最开始的方案是严格轮换法：也就是在一个进程进入临界区的时候，其他进程都在死循环中；直到一个进程退出，才由进程之中的另一个进入关键区。

为了简化起见：我们在介绍算法的时候、都是以两个进程的情况为例。

Dekker 算法

Dekker算法和Peterson算法是差不多的想法：也就是进程自己以一定的规则约束自己，最终达到有序进入关键区的目的。

Dekker算法和Peterson算法有一些相同的全局变量：用来表明每个进程是否需要进入关键区的interested数组、以及一个表示当前轮到谁进入关键区的turn变量。

每个进程又有两个变量id和other，用于标示自己和另一个进程的序号。

Dekker算法的主要循环如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
while(true) {
    interested[id] = true;
    while(interested[other]) {
        if (turn == other) {
            interested[id] = false;
            while (turn == other) ;
            interested[id] =  true;
        }
    }
    enter();
    turn = other;
    interested[id] = false;
}

如果用通俗的语言解释一下，那么一个想进入关键区的进程的动作是这样的：

一个进程想进入关键区，那么他首先要表明自己的态度：我要进入关键区了，把手举得高高的。 interested[id] = true

然后他环顾四周，看看有没有别人想进入关键区。如果没有当然就直接自己进去了。 while 判断

如果有的话，他就会看看现在轮到的是谁：如果是自己、他还是会毫不犹豫地自己进入。 if 判断

但是如果现在轮到的人不是自己怎么办？这是他也许就会长叹一声”时不我予”，然后放下手interested[id] = false，等对面该做的做完了 while (turn == other) ;，再举起手interested[id] = true，再等待下一次机会会不会轮到自己。

在自己做完了自己想做的事情之后、立即再把机会让给别人turn = other，同时心里也就没有了执念 interested[id]=false

Dekker算法的完整代码在这里。Java实现。

Peterson算法

Peterson算法我感觉是比Dekker算法更好玩一些。而且有两种不同的解释:

一个进程想进入关键区，表明自己的态度、举手示意。interested[id] = true。然后开始争夺、希望让自己获得进入关键区的权力turn = id。

这时他观察周围，发现对方也有意要进入关键区，而现在却是自己拿到了权力、这说明自己是从他们手中拿到了权力：于是什么都不做、先等待对方进入关键区。

while (interested[other] && turn == id) ;

直到对方出来为止、然后自己才进入关键区。出关键区之后，放弃对这个关键区的兴趣不表。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
while (true) {
    // Attempt to enter the critical region
    interested[id] = true;
    turn = id; // 让自己获得进入关键区的权力

    if (interested[other] // 发现对方也有意进入关键区
        && turn == id) { // 而且自己抢了对面的权力
        System.out.print("进程" + id + "正在等待");
        // 什么都不做、等待对方先进
    }
    enter();
    interested[id] = false; // 不再感兴趣
}

还有一种解释就更有趣了：

一个进程想进入关键区，表明自己的态度、举手示意。interested[id] = true。然后开始推荐对方，让对方先进入关键区turn = other。

直到后来大局已定再进行观察的时候，如果权力在自己那就自己进去、如果权力在对方就让对方进去。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
while (true) {
    // Attempt to enter the critical region
    interested[id] = true;
    turn = other; // 让对方获得进入关键区的权力

    if (interested[other] // 发现对方有意进入关键区
        && turn == other) { // 而且对方当权
        System.out.print("进程" + id + "正在等待");
        // 什么都不做、等待对方先进
    }
    enter(); // 自己进入关键区
    interested[id] = false; // 不再感兴趣
}

完整的代码在这里。

结语

当时看操作系统的时候看到这里心里不由就飘远了。如果是为了获得某样东西而不想与别人起冲突，我们平常的行事大概就像Dekker算法描述的那样吧。而Peterson算法的第一种解释好像就给了一种更好的方案：让拥有权力的人去等待没有权力的人、为没有权力的人服务。至于Peterson算法的第二种解释，好像更是像传说一样的世界：每个人举荐别人，而最后又坦然接受得失。

这个算法是本来就这样玄奥吗？恐怕也是完全取决于世人以一个怎么样的角度去看它了。