《程序员的自我修养》中关于加锁不能保证线程安全的一个错误

在《程序员的自我修养 — 链接装载与库》一书第28页“过度优化”这一节中,作者提到了编译器优化可能造成多线程bug的情况(我手中的是09年6月第二次印刷那版)。原文如下:

线程安全是一个非常烫手的山芋,因为即使合理的使用了锁,也不一定能保证线程安全,这是源于落后的编译器技术已经无法满足日益增长的并发需求。很多看似无错的代码在优化和并发前又产生了麻烦。最简单的例子,让我们看看如下代码:

x = 0;
Thread 1 Thread 2
lock(); lock();
x++; x++;
unlock(); unlock();

由于有lock和unlock的保护,x++的行为不会被并发所破坏,那么x的值似乎必然是2了。然后,如果编译器为了提高x的访问速度,把x放到了某个寄存器里,那么我们知道不同线程的寄存器是各自独立的,因此如果Thread 1先获得锁,则程序的执行可能会呈现如下的执行情况:

*1 Thread 1:读取x的值到某个寄存器R[1] (R[1]=0)
*2 Thread 1:R[1]++
*3 Thread 2:读取x的值到某个寄存器R[2] (R[2]=0)
*4 Thread 2:R[2]++
*5 Thread 2:将R[2]写回至x(x=1)
*6 Thread 1:(很久以后)将R[1]写回至x(x=1)

可见在这样的情况下即使正确的加锁,也不能保证多线程安全。

这个“加锁后仍不能保证线程安全”的结论其实是错误的。在对一段代码进行加锁操作之后,被锁保护起来的代码就形成了一个临界区,在任何时刻最多只能有一个线程运行这个临界区中的代码,而其他的线程必须等待(例如pthread_mutex_lock是阻塞型等待,pthread_spin_lock是忙等待)。给临界区加锁之后相当于给临界区内的代码添加了原子性的语义。

既然加锁之后临界区内的代码是原子操作的,那么就不可能出现《程》中描述的那种执行顺序,因为Thread 2必须要等到Thread 1执行完x++和unlock()之后才能获得锁并随即进行x++操作。即如下所述的执行顺序:

*1 Thread 1:lock()
*2 Thread 1:读取x的值到某个寄存器R[1] (R[1]=0)
*3 Thread 1:R[1]++
*4 Thread 1:将R[1]写回至x(x=1)
*5 Thread 1:unlock()
*6 Thread 2:lock() //得到锁
*7 Thread 2:读取x的值到某个寄存器R[2] (R[2]=1)
*8 Thread 2:R[2]++
*9 Thread 2:将R[2]写回至x(x=2)
*10 Thread 2:unlock()

其实,这里更值得讨论的一个问题是memory visibility(内存可见性)。例如,在Thread 1将R[1]的值写回至x的这一步中,如果Thread 1只是将值放到了这个CPU核的write buffer(write buffer是多核CPU中为于优化写性能的一种硬件)里,而未将最新值直接更新至内存,那么处在另一个CPU核上的Thread 2真的有可能在第7步时读到的是x的旧值0,这下该怎么办?这个问题其实就是共享变量的值何时能被其他线程可见的问题。

好在正是因为内存可见性在共享内存的并行编程中如此的重要,所以以pthread为代表的线程库早就规定好了自己的内存模型,其中就包括了memory visibility的定义:

Memory Visibility
– When will changes of shared data be visible to other threads?
– Pthreads standard guarantees basic memory visibility rules
» thread creation
• memory state before calling pthread_create(…) is visible to created thread
» mutex unlocking (also combined with condition variables)
• memory state before unlocking a mutex is visible to thread which locks same mutex
» thread termination (i.e. entering state “terminated”)
• memory state before termination is visible to thread which joins with terminated thread
» condition variables
• memory state before notifying waiting threads is visible to woke up threads

说简单点,Pthreads线程库帮程序员保证了pthread mutex(spin lock也一样)所保护的临界区内共享变量的可见性:即Thread 1一执行完unlock(),x的最新值1一定能被Thread 2看见。(为了实现这一点,Pthreads线程库在实现的时候都会根据相应的硬件平台调用相应的memory barrier来保证内存可见性,感兴趣的同学可以看看nptl的实现)

所以,只要正确的用锁保护好你的共享变量,你的程序就会是线程安全的。《程》中所给出的上述例子其实是错误的。

PS.《程》确实是本好书,作者作为我的同龄人功力还是令人钦佩的。但是这个例子也反映了一个现实:写书最怕的就是出现重大的原则性错误,而博客作为互联网上的公开资源,能更容易的吸收大家的修改意见,保证文章的正确性。

参考文献:
[1] Programming with POSIX Threads
[2] Mutex and Memory Visibility

《《程序员的自我修养》中关于加锁不能保证线程安全的一个错误》上有0条评论

  1. 我觉得您这里举的例子“内存可见性”不是很恰当。因为其实CPU cache有一致性的,你说的那种情况cache protocol就已经处理好了,所以只要一个thread更新了某个内存地址,虽然没有写回内存,另一个thread也不会读到old的数据。内存可见性的问题主要是CPU乱序执行造成的,memory fence主要也是为了控制乱序的scope。如果有其他手段能保证执行顺序,也可以不用锁(lock prefix or atomic instruction)。不知道我这种理解有没有问题。

    1. 按照我的理解,cache coherence只能保证thread 2“最终”一定能看见x的新值,但是具体什么时候能看见cache coherence并不能保证。《Computer Architecture A Quantitative Approach》第四版英文版P207页写的很清楚:“The issue of exactly when a written value must be seen by a reader is defined by a memory consistency model”,而memory consistency与cache conherence是两个问题。Memory barrier主要有两个作用:to complete all pending operations scheduled before the memory barrier(包括把write buffer中的数据更新到内存中去),以及to not re-order past the barrier。其实write bufffer也是造成reordering的可能原因之一,所以我觉得我的理解没有错:)

  2. 请问如果书中代码的lock()其实分别是两个锁,那的确有可能出现书中所说的执行顺序吧?

      1. 也不尽如此,如果锁本身有保证可见性作用的话,那么这里其实是等效于加了volatile关键字。例如Java中的synchronized对象锁本身就可以保证锁住对象的修改对其它线程的可见性。

  3. 谨慎的提下意见,感觉是博主理解错了,原文写的清楚,是由于寄存器优化导致的。就原文的例子来说,假设thread 1执行的是如下代码:
    x=0
    lock()
    x++;
    unlock;
    y = x;
    因为unlock之后还需要用到x的值,而且一些落后或者激进的编译器就会产生下面这样的汇编码:
    mov $0, x //x=0
    lock()
    mov x, %eax //将x值从内存读到eax
    add $1, %eax //eax++,结果并不写回内存
    unlock
    mov %eax, y //y = eax, 可以节省一次读内存操作
    mov %eax, x //这里才将x的值写回内存
    可以看出,thread 1在释放了锁之后才将x的值写回内存。这样就会出现原文中的执行序。
    这种错不是一种臆想的错误,这在早期的编译器,尤其是多线程刚出来的时候特别常见,直到现在一些编译器的高级优化选项还会犯类似(要复杂的多)的错误。

    1. 编译器确实可能做出违法多线程语义的优化。但是,unlock()操作本身是带有memory barrier的,这样意味着x的最新值肯定会被其他线程看得见,即thread 2肯定能在thread 1的unlock操作之后看到x的最新值,这就是我的依据。

      原文的执行顺序本身是不可能发生的,因为thread 2一定要等到thread 1 unlock()执行完之后才能获取锁,进而读取x的值啊。

      1. 关键很多编译器早先根本就没考虑多线程的问题,所以也不存在保证语义的说法。
        unlock的操作可以有很多中实现,比如我现在在做的系统里就有自己实现的spin_lock,没有考虑memory barrier的情况。。

        1. 恩,我明白你的意思。我文中特意拿Pthreads举例,是因为它的标准规定了unlock操作具有可见性的语义。所以Linux上的NPTL肯定能保证pthread_mutex_unlock()的可见性。至于编译器是否会把mov %eax, x 放到unlock之后执行我确实不太确定,可能确实有些编译选项会做这样的优化。但是,如果真的如此的话,那岂不是说使用lock来保证x++这样的操作的原子性都不能得到保证了么?

          1. 我2010年读到这一部分时也有点疑惑,因为如果这段代码都不能保证成功的话,那岂不是加锁根本就没有意义,那么现在世界上跑的大部分程序都会有问题?我没具体研究过编译器代码,但是感觉编译器优化也应该至少保证程序正确才对。否则没人敢用。

  4. 同意之前sponge的意见;问题的关键在于 pthread_mutex_lock/unlock的使用能否阻止编译器对X++进行寄存器优化;如果不能,那么编译器完全可能在unlock之后才把寄存器中当前X的值写入内存,甚至不写也有可能。

    1. 我觉得关键是内存模型,即x处在存储体系的那一层,如果是在CPU cache或者memory中,那么很安全,CPU硬件和pthread会保证一致性。如果在CPU寄存器中,那么显然书中说的问题就会出现。
      作为一个开发多线程的程序员,应该有内存模型的概念,文中的x变量,是否在声明的时候需要加上volatile呢?如果没有加上,那么我感觉书中的代码本身就是有问题的。编译器如果对多线程支持那么烂,那么早期的并发系统都不可能实现出来。

      1. 我觉的原文说的没错哦:“程序的执行可能会呈现如下的执行情况”,具体在啥时候可能呢?当然是在unlock不带路障时可能啦!原文并没有说一定使用了pthread。
        博主讲的内存可见性也没错哦,补充原文介绍另一种执行情况!

  5. 我觉得在一本很有市场的很底层的技术书籍中,出现如此严重的错误,实在不应该。很容易误导我这样的初学者。

  6. 我在做一些多核处理器的编程工作,不基于操作系统的。这款cpu采用了弱一致性模型。我想知道实际开发中c编码该如何组织。

  7. 确实是个错误啊,作者忽略了memory visibility,认为编译器在unlock之后仍然将值保存在寄存器中

  8. 没有错误,人家说的没错。
    x++;这行对应的汇编代码很可能是两行:从内存中加载x到寄存器、对这个寄存器进行+1操作,由于后面的代码很可能还会用到变量x,所以编译器在unlock();之前很可能并没有把x的值写回内存。这个时候如果线程1的时间片用完,调度了线程2,线程2执行同样的操作,最后两个线程写回x的值都将是1。

回复 Hesey 取消回复

您的电子邮箱地址不会被公开。