并发编程 临界区和互斥

1. 临界区

什么是临界区？导致竞态条件发生的代码区称作临界区。在临界区中使用适当的同步就可以避免竞态条件。

我们再来看这个例子：一个文件中保存了一个数字 n，进程 A 和进程 B 都想要去读取这个文件的数字，并把这个数字加 1 后，保存回文件。假设 n 的初始值是 0，在我们理想的情况下，进程 A 和进程 B 运行后，文件中 n 的值应该为 2，但实际上可能会发生 n 的值为 1。我们可以考量一下，每个进程做这件事时，需要经过什么步骤：

• 1) 读取文件里 n 的值；
• 2) 令 n = n + 1；
• 3) 把新的 n 值保存回文件。

假设进程 A 在运行完步骤 1 和 2，但还没开始运行步骤 3 时，发生了一个时钟中断，这个时候操作系统通过调度，让进程 B 开始运行，进程 B 运行步骤 1 时，发现 n 的值为 0，于是它运行步骤 2 和 3，最终会把 n = 1 保存到文件中。之后进程 A 继续运行时，由于它并不知道在它运行步骤 3 之前，进程 B 已经修改了文件里的值，所以进程 A 也会把 n = 1 写回到文件中。

直接按照步骤 1~3 运行，就会导致竞态条件。我们可以把步骤 1 - 3 这段程序片段定义为临界区，临界区意味着这个区域是敏感的，因为一旦进程运行到这个区域，那么意味着会对公共数据区域或者文件进行操作，也意味着有可能有其它进程也正运行到了临界区。

2. 互斥

如何避免竞态条件呢？我们需要采取以某种手段，确保当一个进程在使用一个共享变量或者文件时，其它的进程不能做同样的操作，换言之，我们需要 “互斥”。

在以上的例子中，唯一能让 n = 2 的方法，只能期望进程 A 和进程 B 按顺序分别完整地运行完所有步骤。如果能够采用适当的方式，使得这两个进程不会同时处于临界区，那么就能避免竞态条件。也就是，我们需要想想怎么样做到 “互斥”。

所以，互斥的本质就是阻止多个进程同时进入临界区。

3. 互斥的解决方案

1) 屏蔽中断

我们前面提到的例子中，进程 B 之所以能够进入临界区，是因为进程 A 在临界区中受到了中断。如果我们让进程 A 在进入临界区后，立即对所有中断进行屏蔽，离开临界区后，才响应中断，那么即使发生中断，那么 CPU 也不会切换到其它进程，因此此时进程 A 可以放心地修改文件内容，不用担心其它的进程会干扰它的工作。

然而，这个设想是美好，实际上它并不可行。第一个，如果有多个CPU，那么进程 A 无法对其它 CPU 屏蔽中断，它只能屏蔽正在调度它的 CPU，因此由其它 CPU 调度的进程，依然可以进入临界区；第二，关于权力的问题，是否可以把屏蔽中断的权力交给用户进程？如果这个进程屏蔽中断后再也不响应中断了， 那么一个进程有可能挂住整个操作系统。

2) 锁变量

也许可以通过设置一个锁标志位，将其初始值设置为 0 ，当一个进程想进入临界区时，先检查锁的值是否为 0，如果为 0，则设置为 1，然后进入临界区，退出临界区后把锁的值改为0；若检查时锁的值已经为1，那么代表其他进程已经在临界区中了，于是进程进行循环等待，并不断检测锁的值，直到它变为0。

但这种方式本身就存在着竞态条件，原因是，当一个进程读出锁的值为0时，在它将其值设置为1之前，另一个进程被调度起来，它也读到锁的值为0，这样就出现了两个进程同时都在临界区的情况。

3) 严格轮换法

锁变量之所以出问题，其实是因为将锁变量由0改为1这个动作，是由想要获取锁的进程去执行的。如果我们把这个动作改为由已经获得锁的进程去执行，那么就不存在竞态条件了。

先设置一个变量 turn，代表当前允许谁获得锁，假设有两个进程，进程 A 的逻辑如下所示：

    while (turn != 0){
        // 如果还没轮到自己获取锁，则进入循环等待
    }
    do_critical_region();// 执行临界区的程序
    turn = 1;// 由获得锁的一方将锁变量修改为其它值，允许其它进程获得锁
    do_non_critical_region();// 执行非临界区的程序

进程 B 的逻辑如下所示：

    while (turn != 1) {
        // 如果还没轮到自己获取锁，则进入循环等待
    }
    do_critical_region();// 执行临界区的程序
    turn = 0;// 由获得锁的一方将锁变量修改为其它值，允许其它进程获得锁
    do_non_critical_region();// 执行非临界区的程序

但这里需要考虑到一个事情，假设进程 A 的 do_non_critical_region() 需要执行很长时间，即进程 A 的非临界区的逻辑需要执行较长时间，而进程 B 的非临界区的逻辑很快就执行完，显然，进程 A 进入临界区的频率会比进程 B 小一点，理想的情况下，进程 B 应该多进入临界区几次。但是由于进程 B 在执行非临界区逻辑前会把 turn 设置为 0，等它很快地把非临界区的逻辑执行完后，回来检查 turn 的值时，发现 turn 的值一直都不是 1，turn 的值需要进程 A 把它设置为 1，而进程 A 此时却正在进行着漫长的非临界区逻辑代码，所以导致进程 B 无法进入临界区。

这就说明，在一个进程比另一个进程慢很多的情况下，严格轮换法并不是一个好办法。

4) Peterson 算法

严格轮换法的问题就出在严格两个字上，即多个进程之间是轮流进入临界区的，根本原因是想要获得锁的进程需要依赖其它进程对于锁变量的修改，而其它进程都要先经过非临界区逻辑的执行才会去修改锁变量。

严格轮换法中的 turn 变量不仅用来表示当前该轮到谁获取锁，而且它的值未改变之前，都意味着它依然阻止了其它进程进入临界区，恰恰好，一个进程总是要经过非临界区的逻辑后才会去改变turn的值。

因此，我们可以用两个变量来表示，一个变量表示当前应该轮到谁获得锁，另一个变量表示当前进程已经离开了临界区，这种方法实际上叫做 Peterson 算法，是由荷兰数学家 T.Dekker 提出来的。

    static final int N = 2;
    int turn = 0;
    boolean[] interested = new boolean[N];

    void enter_region(int process) {
        int other = 1 - process;
        interested[process] = true;
        turn = process;
        while(turn == process && !interested[other]) {
        }
    }

    void exit_region(int process) {
        interested[process] = false;
    }

进程在需要进入临界区时，先调用 enter_region，离开临界区后，调用 exit_region。Peterson 算法使得进程在离开临界区后，立马消除了自己对于临界区的“兴趣”，因此其它进程完全可以根据 turn 的值，来判断自己是否可以合法进入临界区。