从百度的一道笔试题说线程安全

合租的室友在帮他的一同学做百度笔试题，并拉上我和另一室友一起做。第一题是关于线程安全的：

 

现代的处理器提供了compare-and-swap原子操作：

int compare_and_swap(int * pv, const int cv, const int nv);

即比较*pv与cv，如果相等，则把*pv值替换为nv并返回*pv原值，否则返回*pv的值。

请利用上述原子操作实现如下操作：

int inc_if_gt_zero(int * pv);

即如果*pv > 0，则把*pv加1并返回修改后的*pv，否则返回*pv。

结果要线程安全且不使用锁、信号灯、互斥量、临界区或类似机制。

 

由于看过一些java多线程方面的书籍，也比较熟悉，JDK5的AtomicXXX中incrementAndGet等操作的内部实现也用到compare-and-swap这一原子操作。 下面是我的代码：

int inc_if_gt_zero(int * pv) {
  while (true) {
    int c = *pv;
    if (c <= 0) return c;
    int v = compare_and_swap(pv, c, c+1);
    if (c == v) {
      return c+1;
    }
  }
}

 

主要思想是在对pv进行加1操作之前，看它的值有没有改变，没有改变就执行加1操作，否则重试。Doug Lea的经典著作《Concurrent Programming in Java》将这种方法称之为"乐观重试"，《Concurrent in Practice》书中则称之为"无等待算法"。对我来说这显而易见，但是我的两个室友却不同意。我的两个室友都是做C++的，都是我的同学，不妨称之为室友A和室友B。室友A直觉上感觉不靠谱，但是找不出原因，室友B则认为完全不对。我没能说服他们，我发现争议的焦点在于对线程安全的理解上，室友A做过多线程编程，他从锁机制的角度来考虑线程安全，因而才对"乐观重试"的方法感觉不靠谱，室友B则基本没有做过，认为对上题来说，输入为2时，必须输出就为3，对他来说，下面的单线程程序就是正确的：

int inc_if_gt_zero(int * pv) {
  int c = *pv;
  if (c <= 0) return c;
  *pv = ++c;
  return c;
}

 

 

当时我对线程安全的概念也一直没有好好梳理，也无法用语言清晰的表达出我的思想。经过一晚上的思考，思路终于有些清晰了。线程安全的一个重要规则是"as-if-serial"规则，也就是多个线程同时执行操作(在语义上是原子性的操作)，看起来就像在单个线程顺序执行这些操作一样。具体来说，以上面的例子为例，假设n个线程，分别表示为T1,T2,...和Tn，同时执行inc_if_gt_zero操作，pv的初始值为1，那么对于线程安全的程序来说它必须保证两个结果：

1. n个线程执行完毕后，它必须和单个线程中顺序执行n个inc_if_gt_zero操作之后的内存效果一样，也就是pv的值必须为n+1。
2. as-if-serial规则虽然保证多个操作看起来像在单线程中执行一样，但并不保证它们执行的顺序。对于该例子，执行的结果可能是按T1,T2,...Tn的顺序，也可能是按Tn,Tn-1,...T1的顺序，最多只可能为n!种顺序。如果按照T1,T2,...Tn的顺序的操作执行，T1,T2,...Tn的inc_if_gt_zero分别返回2,3,...n+1，如果按Tn,Tn-1,...T1的顺序，T1,T2,...Tn的inc_if_gt_zero分别返回n+1,n,...1。可以得知，线程T1,T2,...Tn的inc_if_gt_zero的返回结果必定是2,3,...,n+1的一个排列，但到底是哪个排列是不确定的。这里并不需要保证inc_if_gt_zero返回时pv的值和返回值相同。
   

对于该程序的单线程版本，它明显可能违背结果1，最终pv的值可能小于n+1，当然也违背结果2，多个线程执行的结果也可能出现重复的值。对于该程序的关键是保证判断c是否大于0的语句和将pv的值加1的语句之间不能被别的线程给打断，这可以通过锁机制来实现，也可以通过上面说的乐观重试机制来实现，这多少有些类似数据库中的悲观锁和乐观锁。

 

最后要注意的是，对于该程序的乐观锁版本，如果将最后一句"return c+1"，改成"return *pv"是有问题的，这在单线程程序中是正确的，在多线程中这时pv的值可能不再等于c+1了，这导致T1,T2, ...Tn的inc_if_gt_zero可能返回重复值。