10.4　如何避免竞态条件

对程序使用者来说，抢占式多任务模式十分方便，但对于程序设计者来讲会出现其他问题。在不知道何时被喝令终止并交替的前提下，要编写一个能稳妥执行的程序是非常困难的。

我们来看下面这段反映银行交易的伪代码，看看有可能发生哪些问题。

如果存款余额高于10 000元 {
存款余额减去10 000元、
取出10 000元的钞票
}

单看这段程序似乎没有任何问题。问题会发生在当存款余额这个变量被共有，并且这个程序在多处同时执行时。在检查了“如果存款余额高于 10 000 元”之后，有可能不凑巧刚好又交替到别的程序的执行上。这时会出现以下情况：存款余额只有 15 000 元时却取出来 20 000 元钞票的严重问题。

（假设存款余额有15 000元。首先程序A执行）
A：存款余额高于10 000元吗？→Yes
（这里又交替到程序B的执行上）
B：存款余额高于10 000元吗？→ Yes
B：存款余额减去10 000元、取出10 000元的钞票
（这里存款余额变为5，000元。然后再交替回程序A）
A：存款余额减去10 000元、取出10 000元的钞票
（存款余额仅有5000元却取出了1万元！）

这种局面被称为竞态条件（race condition），或者说这个程序是非线程安全的。

竞态条件成立的三个条件

竞态条件在什么时候成立呢？并行执行的两个处理之间出现竞态条件必须同时满足以下三个条件。

a 两个处理共享变量

b 至少一个处理会对变量进行修改

c 一个处理未完成之前另一个处理有可能介入进来

反之，只要三个条件中有一个不具备，就可以编写适于并发处理的安全的程序 4。

4这三个条件是参考了 Java Concurrency in Practice 一书（Brain Goetz，Joshua Bloch，Doug Lea 著，中文版为《Java 并发编程实战》，机械工业出版社 2012 年 2 月出版，童云兰译）关于修复问题程序的三种方法的表述总结出的。

为了说明a和b，我们考虑一下两个人看一台电视的场景。如果有一方随意地换台，另一方就有可能抱怨。这相当于满足了“a变量被共享”和“b有一方可能修改”的条件。如果另外买一台电视一人一台的话，无论什么时候换台都不至于招致另一方的抱怨，因为没有了a中共享的情况。或者，不去换台两个人一直看，也不会引起任何问题，因为没有了b中一方修改的可能。

没有共享——进程和 actor 模型

如果最初就没有共享任何数据，条件a就不可能发生，也就没有必要在意竞态条件了。

在进程中没有内存共享

相信很多人都知道 UNIX 将执行的程序叫做进程（process）。不同的进程不会共享内存，所以在多个程序之间不会在内存上出现竞态条件。只需要注意与数据库连接或文件读写时共享数据的情形就够了。

但是进程这个词直译就是“处理”，是一个非常通用的概念。它在 UNIX 诞生以前就已经被使用。当时的进程和现在 UNIX 中的进程不一样，它有时会共享内存，有时会进行排他控制，更像是现在我们所称的线程之类。

1969 年问世的操作系统 Multics 中，进程也是共享内存的 5。但是 Multics 项目加入了太多的功能而变得过度复杂，因此后来大家又发起了简化运动。最终，在 1970 年操作系统 UNICS 被设计出来，它就是后来的 UNIX。

5Multics 是基于 PL/I 和汇编语言编写的。1964 年出现的 PL/I 程序设计语言是第一个引入了类似于今天的线程概念的编程语言。

UNIX 采用了一种机制，它能保证每个进程所需要的内存空间，不同进程之间不会共享内存 6。

6想了解更多细节的读者可以搜索关键字 Virtual Address Space。

没有共享的方式成功了吗

UNIX 的机制是一个进程中可以并行执行的处理只有一个。也就是说，如果要想多个处理并行执行就需要启动多个进程。不同的进程不共享内存，即并行执行的处理之间不共享内存。那么这种方式后来成功了么？

没有。在 UNIX 发布大约 10 年后，人们设计出了“轻量级进程”。它是一种共享内存、具有 UNIX 出现以前风格的进程。后来，这个被称为线程。

笔者执笔本书时 UNIX 已走过了近 40 年。在这 40 年的时间里，没有共享的方式中始终有解决不了的问题。即使现在使用线程，对于共享内存的处理仍然让人头疼，但没办法，还得继续编写程序。

actor 模型

在不共享内存的设计方针下，还有一个流派——actor 模型。它发布于 1973 年，是为实现并发处理而出现的一种模型。

它认为可以通过不共享内存而是传递消息的方法 7 来在并发处理时进行信息交互。

7同期于 1971 年诞生的 Smalltalk-71 是一种通过发送消息实现信息交互的语言。THE EARLY HISTORY OF SMALLTALK, http://gagne.homedns.org/~tgagne/contrib/EarlyHistoryST.html。

我们以行政文员、资料和公文格为例来说明。甲打开桌上的资料进行处理时，如果乙走过来希望甲处理其他资料，这就影响了甲正在进行中的工作，这就是共享内存的问题所在。一方面，在甲的工作告一段落之前，即使乙在旁边一直等候也是浪费时间。这就是后面要讲到的死锁的问题。如果不这样，乙在往甲的公文格中放入新的资料后马上回去处理自己的工作，这就变成 actor 模型。

这种模型中处理是非同步的。乙不知道甲何时会处理完公文格中的资料。不管何时处理完，如果在资料中写明“处理完毕请送回乙处”等信息，一旦乙在自己的公文格中看到了甲的回复，也就知道了这些资料已经处理完毕。

这种机制适宜的处理场景中，必须提一下消息交互的场景。如 Twitter 和 Facebook 这样面向大量用户的信息交互服务，应该有很多适合 actor 模型发挥作用的处理。这些处理在实现中使用了那些采用了 Erlang8、Scala 等 actor 模型的语言。

8Erlang 语言在 1987 年问世，并于 1998 年成为开源的程序设计语言。2007 年，因为 Twitter 等应用的出现备受关注，是一种能让消息发送和接收变得更轻松的设计语言。

不修改——const、val、Immutable

有一种方法是通过规避条件b，即使共享内存，只要不作修改也不会有任何问题。

Haskell 语言就是一种大力提倡这种方针的语言，它的所有变量都不可修改。

但是更多的语言采用了更加现实的折衷策略——使一部分变更无法作修改。比如在 C++ 语言中，使用 const 声明变量时，这个变量就是无法修改的。再如在 Scala 语言中，有 var 和 val 两种声明变量的方法，val 声明的变量就无法作修改。

Java 语言经常使用到 Mark Grand 提出的设计模式 9 之一的 Immutable 模式。这种模式下，类中定义了 private 字段，同时定义了读取这些字段的 getter 方法，但不定义对这些字段作修改的 setter 方法。因为没有准备用于修改的方法，所以实现了只能读取但不能改写的效果。

9想了解更多细节的读者可以参照 Patterns in Java: a catalog of reusable design patterns illustrated with UML（Mark Grand 著）一书。——译者注。

不介入

如果要消除竞态条件成立的第c个条件——一个处理未完成之前另一个处理有可能介入进来，这时该如何做呢？在处理期间如何杜绝别的作业介入进来？

线程的协调——fibre、coroutine、green thread

其中有一类方法，如 fibre、coroutine、green thread 处理介入的原因是抢占式线程，那么使用协调模式的线程就可以解决了。Ruby 语言中的 Fibre 类，以及 Python 语言和 JavaScript 语言中的 generator 都是这种情况 10。

10Ruby 语言中的 Fibre 是在 1.9 版本中增加的，而 JavaScript 语言中的 generator 是在 1.7 版本中增加的。Python 语言和 JavaScript 语言都在 generator 中使用了 yield 一词，但 Ruby 语言由于历史原因将 yield 用于了别的目的，所以具有不一样的含义。此处不应该混淆。

毫无疑问，由于是协作式多任务模式，如果有某个线程独占 CPU，其他处理就只能停止。说到底，这种方法的前提是各个线程能保证合理的执行时间在合适的时候做出让步。

表示不便介入的标志——锁、mutex、semaphore

另有一类方法，共享一种表示不便介入的标志。比如做一种约定，如果某内存上的值不为 0 时，这意味着其他线程如果介入将带来麻烦。那么各个线程在执行那些介入后可能带来问题的处理时，事先会去检查这块内存上的值。如果为 0 则继续执行，如果不为 0 则等待其变回 0 后再做处理。

这和试衣间中的门帘或单人浴室包间的状态牌类似。门帘关闭时表示这时试衣间正被占用，现在进去的话不方便。想使用试衣间的人只能在外面一直等到门帘打开为止。

这类方法有多种称法，如锁、mutex 和 semaphore，但它们的核心概念和浴室的状态牌是一样的 11。锁这个名字很容易让人误解为只要上了锁其他人就进不来了，然而实际上它只是一个表示“使用中”的状态牌。如果有线程不去检查状态牌的状态，那它也就变得没有意义了。

11本书统称为锁。

这一机制是艾兹格·迪科斯彻（Edsger Wybe Dijkstra）于 1965 年发明的。1974 年霍尔（Hoare）发明了更加方便的改良版本，即 Concurrent Pascal 中采用的 monitor 的概念。1974 年时 C 语言已经问世 3 年了，直到 20 年后问世的 Java 语言采用了 monitor 的概念，它才得以广泛使用。

在进入之前先检查是否挂有“使用中”的状态牌，如果有则等待，如果没有挂则挂上“使用中”的状态牌再进入。要实现这一系列约定的动作是件比较麻烦的事情。比如使用 if 语句时，在“做值的检查”和“判断为 0 则改为 1”时，有可能有其他处理介入进来。这样一来检查就毫无意义了。为了不让其他处理在中间介入进来，就有必要使用一种能将值的检查和修改同时执行的命令。因为 Java 语言处理器实现了这一功能，所以 Java 语言用户无需烦恼，只要直接使用 synchronized lock 就可以轻松地使用锁的功能。