竞态条件

在一般的操作系统中,不同的进程可能会分享一块公共的存储区域,例如内存或者是硬盘上的文件,这些进程都允许在这些区域上进行读写。 操作系统有一些职责,来协调这些使用公共区域的进程之间以正确的方式进行想要的操作。这些进程之间需要通信,需要互相沟通,有商有量,才能保证一个进程的动作不会影响到另外一个进程正常的动作,进而导致进程运行后得不到期望的结果。在操作系统概念中,通常用 IPC(Inter Process Communication,即进程间通信)这个名词来代表多个进程之间的通信。 为了解释什么是竞态条件(race condition),我们引入一个简单的例子来说明: 一个文件中保存了一个数字 n,进程 A 和进程 B 都想要去读取这个文件的数字,并把这个数字加 1 后,保存回文件。假设 n 的初始值是 0,在我们理想的情况下,进程 A 和进程 B 运行后,文件中 n 的值应该为 2,但实际上可能会发生 n 的值为 1。我们可以考量一下,每个进程做这件事时,需要经过什么步骤:

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

在进一步解释竞态条件之前,必须先回顾操作系统概念中的几个知识点:

  1. 进程是可以并发运行的,即使只有一个 CPU 的时候)
  2. 操作系统的时钟中断会引起进程运行的重新调度,
  3. 除了时钟中断,来自其它设备的中断也会引起进程运行的重新调度

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

唯一能让 n = 2 的方法,只能期望进程 A 和进程 B 按顺序分别完整地运行完所有步骤。 我们可以给竞态条件下一个定义了

两个或者多个进程读写某些共享数据,而最后的结果取决于进程运行的准确时序,称为竞态条件。

在上述的文字中,我们使用进程作为对象来讨论竞态条件,实际上对于线程也同样适用,这里的线程包含但不限于内核线程、用户线程。因为在操作系统中,进程其实是依靠线程来运行程序的。更甚至,在 Java 语言的线程安全中,竞态条件这个概念也同样适用。(参考《Java 并发编程实战》第二章)

互斥与临界区

如何避免 race condition,我们需要以某种手段,确保当一个进程在使用一个共享变量或者文件时,其它的进程不能做同样的操作,换言之,我们需要“互斥”。 以上述例子作为例子,我们可以把步骤 1 - 3 这段程序片段定义为临界区,临界区意味着这个区域是敏感的,因为一旦进程运行到这个区域,那么意味着会对公共数据区域或者文件进行操作,也意味着有可能有其它进程也正运行到了临界区。如果能够采用适当的方式,使得这两个进程不会同时处于临界区,那么就能避免竞态条件。 也就是,我们需要想想怎么样做到“互斥”。

互斥的方案

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

屏蔽中断

之前提到的例子中,进程 B 之所以能够进入临界区,是因为进程 A 在临界区中受到了中断。如果我们让进程 A 在进入临界区后,立即对所有中断进行屏蔽,离开临界区后,才响应中断,那么即使发生中断,那么 CPU 也不会切换到其它进程,因此此时进程 A 可以放心地修改文件内容,不用担心其它的进程会干扰它的工作。 然而,这个设想是美好,实际上它并不可行。第一个,如果有多个CPU,那么进程 A 无法对其它 CPU 屏蔽中断,它只能屏蔽正在调度它的 CPU,因此由其它 CPU 调度的进程,依然可以进入临界区;第二,关于权力的问题,是否可以把屏蔽中断的权力交给用户进程?如果这个进程屏蔽中断后再也不响应中断了, 那么一个进程有可能挂住整个操作系统。

锁变量

也许可以通过设置一个锁标志位,将其初始值设置为 0 ,当一个进程想进入临界区时,先检查锁的值是否为 0,如果为 0,则设置为 1,然后进入临界区,退出临界区后把锁的值改为0;若检查时锁的值已经为1,那么代表其他进程已经在临界区中了,于是进程进行循环等待,并不断检测锁的值,直到它变为0。 但这种方式也存在着竞态条件,原因是,当一个进程读出锁的值为0时,在它将其值设置为1之前,另一个进程被调度起来,它也读到锁的值为0,这样就出现了两个进程同时都在临界区的情况。

严格轮换法

锁变量之所以出问题,其实是因为将锁变量由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 无法进入临界区。 这就说明,在一个进程比另一个进程慢很多的情况下,严格轮换法并不是一个好办法。

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

TSL 指令

回顾一下我们之前提到的“锁变量”这种方法,它的一个致命的缺点是对状态变量进行改变的时候,如从 0 改为 1 或者从 1 改为 0 时,是可以被中断打断的,因此存在竞态条件。 之后我们在锁变量的基础上,提出如果锁变量的修改不是由想要获取进入临界区的进程来修改,而是由已经进入临界区后想要离开临界区的进程来修改,就可以避免竞态条件,继而引发出严格轮换法,以及从严格轮换法基础上改进的 Peterson 算法。这些方法都是从软件的方式去考虑的。实际上,可以在硬件 CPU 的支持下,保证锁变量的改变不被打断,使锁变量成为一种很好的解决进程互斥的方法。 目前大多数的计算机的 CPU,都支持 TSL 指令,其全称为 Test and Set Lock,它将一个内存的变量(字)读取寄存器 RX 中,然后再该内存地址上存一个非零值,读取操作和写入操作从硬件层面上保证是不可打断的,也就是说是原子性的。它采用的方式是在执行 TSL 指令时锁住内存总线,禁止其它 CPU 在 TSL 指令结束之前访问内存。这也是我们常说的 CAS (Compare And Set)。 当需要把锁变量从 0 改为 1 时,先把内存的值复制到寄存器,并将内存的值设置为 1,然后检查寄存器的值是否为 0,如果为 0,则操作成功,如果非 0 ,则重复检测,知道寄存器的值变为 0,如果寄存器的值变为 0 ,意味着另一个进程离开了临界区。进程离开临界区时,需要把内存中该变量的值设置为 0。

忙等待

上述提到的 Peterson 算法,以及 TSL 方法,实际上它们都有一个特点,那就是在等待进入临界区的时候,它们采用的是忙等待的方式,我们也常常称之为自旋。它的缺点是浪费 CPU 的时间片,并且会导致优先级反转的问题。

考虑一台计算机有两个进程, H 优先级较高,L 优先级较低。调度规则规定,只要 H 处于就绪状态,就可以运行。在某一时刻,L 处于临界区内,此时 H 处于就绪态,准备运行。但 H 需要进行忙等待,而 L 由于优先级低,没法得到调度,因此也无法离开临界区,所以 H 将会永远忙等待,而 L 总无法离开临界区。这种情况称之为优先级反转问题(priority inversion problem)

进程的阻塞与唤醒

操作系统提供了一些原语,sleep 和 wakeup。

内核提供给核外调用的过程或者函数成为原语(primitive),原语在执行过程中不允许中断。

sleep 是一个将调用进程阻塞的系统调用,直到另外一个进程调用 wakeup 方法,将被阻塞的进程作为参数,将其唤醒。阻塞与忙等待最大的区别在于,进程被阻塞后CPU将不会分配时间片给它,而忙等待则是一直在空转,消耗 CPU 的时间片。

信号量

首先需要明白的一点是,信号量的出现是为了解决什么问题,由于一个进程的阻塞和唤醒是在不同的进程中造成的,比如说进程 A 调用了 sleep() 会进入阻塞,而进程 B 调用 wakeup(A)会把进程 A 唤醒。因为是在不同的进程中进行的,所以也存在着被中断的问题。加入进程 A 根据逻辑,需要调用 sleep() 进入阻塞状态,然而,就在它调用 sleep 方法之前,由于时钟中断,进程 B 开始运行了,根据逻辑,它调用了 wakeup() 方法唤醒进程 A,可是由于进程 A 还未进入阻塞状态,因此这个 wakeup 信号就丢失了,等待进程 A 从之前中断的位置开始继续运行时并进入阻塞后,可能再也没有进程去唤醒它了。 因此,进程的阻塞和唤醒,应该需要额外引进一个变量来记录,这个变量记录了唤醒的次数,每次被唤醒,变量的值加1。有了这个变量,即使wakeup操作先于sleep操作,但wakeup操作会被记录到变量中,当进程进行sleep时,因为已经有其它进程唤醒过了,此时认为这个进程不需要进入阻塞状态。 这个变量,在操作系统概念中,则被称为信号量(semaphore),由 Dijkstra 在 1965 年提出的一种方法。 对信号量有两种操作, down 和 up。 down 操作实际上对应着 sleep,它会先检测信号量的值是否大于0,若大于0,则减1,进程此时无须阻塞,相当于消耗掉了一次 wakeup;若信号量为0,进程则会进入阻塞状态。 而 up 操作对应着 wakeup,进行 up 操作后,如果发现有进程阻塞在这个信号量上,那么系统会选择其中一个进程将其唤醒,此时信号量的值不需要变化,但被阻塞的进程已经少了一个;如果 up 操作时没有进程阻塞在信号量上,那么它会将信号量的值加1。 有些地方会把 down 和 up 操作称之为 PV 操作,这是因为在 Dijkstra 的论文中,使用的是 P 和 V 分别来代表 down 和 up。 信号量的 down 和 up 操作,是操作系统支持的原语,它们是具有原子性的操作,不会出现被中断的情况。

互斥量

互斥量(mutex)其实是信号量的一种特例,它的值只有 0 和 1,当我们不需要用到信号量的计数能力时,我们可以使用互斥量,实际上也意味着临界区值同一时间只允许一个进程进入,而信号量是允许多个进程同时进入临界区的。