并发编程 临界区和互斥

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 的值,来判断自己是否可以合法进入临界区。

我们前面提供了一种避免竞态条件的方案:锁变量。通过设置一个锁标志位,将其初始值设置为 0 ,当一个进程想进入临界区时,先检查锁的值是否为 0,如果为 0,则设置为 1,然后进入临界区,退出临界区后把锁的值改为0 ...