<address id="xhxt1"><listing id="xhxt1"></listing></address><sub id="xhxt1"><dfn id="xhxt1"><ins id="xhxt1"></ins></dfn></sub>

    <thead id="xhxt1"><dfn id="xhxt1"><ins id="xhxt1"></ins></dfn></thead>

    Mutex和内存可见性

    原文链接? 作者:Lo?c ?译者:林永听

    介绍

    POSIX线程遵守共享内存模型[1],此模型各线程可以访问一组共享对象。多个并发的线程需要协同访问共享对象。为此该模型引入了以下两个属性来简化程序设计:

    • 原子访问:避免线程在访问数据对象时,另一线程正在修改它。
    • 内存可见性:一旦线程修改数据对象,其它线程在修改行为发生之后马上能看见此对象的新状态,如图1所示。


    Mutex通常被引进作为实现原子访问的手段,但它的作用不仅仅是用来控制对象访问,还解决内存可见性问题。接下来将看到,某些场景下,并不需要关心原子访问题,往往内存可见性才是问题所在。此场景之下如果没有mutex,那将是一场恶梦……

    wanted memory visibility

    图1:预期的内存可见性。线程A设置x=6和y=7,线程B在其后执行z=x*y,我们期望获取z=42的结果。

    mutex解决弱内存可见性

    下面是marathon程序?;旧?,线程A应该一直在运行,直到线程B设置arrived变量的值来通知它,才运行结束。

    Marathon程序

    
    volatile bool  arrived = false;
    
    volatile float miles   = 0.0;
    
    /*--- Thread A ----------------------------------------*/
    
    while (!arrived)
    
    {
    
       run();
    
    }
    
    printf("miles run: %f\n", miles);
    
    /*-----------------------------------------------------*/
    
    /*--- Thread B ----------------------------------------*/
    
    miles   = 26.385; // 42.195 Km
    
    arrived = true;
    
    /*-----------------------------------------------------*/
    
    

    这里没有使用mutex来控制arrived标志的访问。这样的代码我见过不少,并且听到一大萝的解释:

    “因为仅仅有一个线程读,一个线程写,所以不需要使用mutex”

    “就算arrived标志的值是随机值,也是非零值,根据C语言约定它为true。因此while循环最终会停下来。这里不需要关心原子性,因此不需要mutex”

    “对于本例子,使用mutex除了增加几行代码,还拖慢了程序,毫无必要”

    “通过压力测试,程序确实运行正确”

    在各自的平台上,这些说法几乎是正确的?;八淙绱?,但这个程序仍然是有问题的。把它运行在其它平台上,会遇到莫名其妙的错误。

    硬件优化

    在某些平台上,线程A可能会如期停止,但它会打印 miles run 0.0。而在另一些平台上,线程甚至可能不会停止,即使用线程B已将arrived标志修改为true。

    想不通了吧?这些怪诞行为的始作俑者就是硬件平台。更确切地说是硬件对内存访问实施了优化。一般来说,CPU指令执行的速度比从主存读取数据的速度要快2到3个数量级。显然内存子系统是整个系统的屏颈,硬件工程师使尽浑身解数想出聪明办法来使访问内存更快。首先是使用cache来加速内存访问,然而这带来了下面这些额外的复杂性:

    1. 当cache访问不命中时,处理仍然难逃被内存子系统拖慢的厄运。
    2. 在多处理器系统,必须使用协议保存cache一致性。

    乱序执行

    我们知道编译器会通过重排指令来优化程序的执行时间。但鲜为人知的是,现在处理器同样会根据需要乱序执行指令,以对付上面谈及的问题1)。

    为了理解乱序执行是如何工作的,请看下面伪汇编写的简单例子:

    乱序执行

    mov r1, mem  // load mem cell to register r1
    
    add r1,r1,r2 // r1 = r1+r2
    
    add r3,r4,r5 // r3 = r4+r5</pre>
    
    

    在实际执行中,内存单元mem的值可能不在cache中,因此需要从主存中获取。这种情况下,处理器会按如下顺序来执行,以窃取等待读取内存完成的空档:

    第一行指令被执行后,处理器不会等待内存访问完成。

    在第一行指令执行后,马上调度执行第二行指令。

    因为寄存器操作数可用,并且与第一行指令和第二行指令没有依赖关系,所以处理器可以马上执行第三行指令。

    因此处理器的执行顺序可能是:(3)-(1)-(2),而非按原序执行。它带来的好处是:处理器可以利用从内存总数获取数据而停滞100或更多地时钟周期做更有意义的事情,以提高执行速度。当然,这种优化对于当前执行指令的线程是完全透明的(译注:即这种乱序执行对当前线程的程序语义没有任何改变)。

    然而,乱序执行会被其它线程观察到。如果线程B(在乱序执行时)先设置arrived标志的值为true,那么可能线程A结束时,打印出miles的值并非线程B所修改后的。真不可思议!……

    Store Buffer

    当处理器所读取的内存是多处理器系统的共享内存时,事情变得更复杂。必须使用协议来保证,当某变量的最新值保存到CPU的cache时,其它所有CPU的cache上该变量的副本必须更改成无效状态,以在所有处理器上保持值的一致性。这种协议的缺点是CPU在写数据时,不可避免地受到了拖延。

    硬件工程再度想出聪明的解决方法:将写请求缓冲到一个称为store buffer的特殊硬件队列。所有请求都放到队列里,随后CPU方便时一下子将修改请求应用内存里。

    对于软件开发人员,更关心的问题时,何时谓之方便。上面的marathon程序可能会发生这样的场景,‘arrived=true‘请求已排队到store buffer,但store buffer上的请求永远都不对主存生效。因此线程A永远也看不到标志变量的新值。Oops!……

    内存屏障

    之前所见的种种怪异事情,均可发生在现代硬件上。这种内存可见性比我们所认为的逊色多了,那么如何在这种架构上编写可预知的程序呢?

    这下该内存屏障(memory barriers,别称membars, memory fences, mfences)出场了。内存屏障是一种特殊的处理器指令,它指挥处理器做如下的事情:

    • 刷新store buffer。
    • 等待直到内存屏障之前的操作已经完成。
    • 不将内存屏障后面的指令提前到内存屏障之前执行

    通过适当使用内存屏障,可以确保它之前的乱序执行已全部完成,并且未完成的写操作已经全部刷新到主存。因此,数据一致性又重回到其它线程的身边,从而保证正确的内存可见性。因此可大胆猜测:mutex实现根据需要使用了恰当的内存屏障。

    如果对内存屏障和硬件优化感兴趣,推荐阅读Paul Mckenny[2]的优秀论文。

    真实的例子

    到目前为止,讨论的话题是相当理论的。本节给出一个具体的例子,由于没有正确使用内存可见性,而导致怪异的结果(只是偶尔出现)。本例来自于Bartosz Milewski的文章[3]和演讲[4]。

    请看下面的程序mutex_01.c。程序创建两个线程,通过ArunBrun标志变量,可以配置成某个线程先运行,或者两者并发运行。Pthtrad barrier(请不要与内存屏障混肴)用于确保两个线程在同一时刻启动。一旦两线程都运行完成,断言(Astate==1 || Bstate==1)有效。如果断言失败,则打印一条消息。整个程序依次按此过程无限循环执行。

    下载?mutex_01.c

    </pre>
    </div>
    <div>/*------------------------------- mutex_01.c --------------------------------*
    On Linux, compile with:
    cc -std=c99 -pthread mutex_01.c -o mutex_01
    
    Check your system documentation how to enable C99 and POSIX threads on
    other Un*x systems.
    
    Copyright Loic Domaigne.
    Licensed under the Apache License, Version 2.0.
    *--------------------------------------------------------------------------*/
    
    #define _POSIX_C_SOURCE 200112L // use IEEE 1003.1-2004
    
    #include // sleep()
    #include #include
    #include // EXIT_SUCCESS
    #include // strerror()
    #include
    
    /***************************************************************************/
    /* our macro for errors checking */
    /***************************************************************************/
    #define COND_CHECK(func, cond, retv, errv) \
    if ( (cond) ) \
    { \
     fprintf(stderr, "\n[CHECK FAILED at %s:%d]\n| %s(...)=%d (%s)\n\n",\
     __FILE__,__LINE__,func,retv,strerror(errv)); \
     exit(EXIT_FAILURE); \
    }
    
    #define ErrnoCheck(func,cond,retv) COND_CHECK(func, cond, retv, errno)
    #define PthreadCheck(func,rc) COND_CHECK(func,(rc!=0), rc, rc)
    
    /*****************************************************************************/
    /* real work starts here */
    /*****************************************************************************/
    /*
     * Accordingly to the Intel Spec, the following situation
     *
     * thread A: thread B:
     * mov [_x],1 mov [_y],1
     * mov r1,[_y] mov r2,[_x]
     *
     * can lead to r1==r2==0.
     *
     * We use this fact to illustrate what bad surprise can happen, if we don't
     * use mutex to ensure appropriate memory visibility.
     *
     */
    volatile int Arun=0; // to mark if thread A runs
    volatile int Brun=0; // dito for thread B
    
    pthread_barrier_t barrier; // to synchronize start of thread A and B.
    
    /*****************************************************************************/
    /* threadA- wait at the barrier, set Arun to 1 and return Brun */
    /*****************************************************************************/
    void*
    threadA(void* arg)
    {
     pthread_barrier_wait(&barrier);
     Arun=1;
     return (void*) Brun;
    }
    
    /*****************************************************************************/
    /* threadB- wait at the barrier, set Brun to 1 and return Arun */
    /*****************************************************************************/
    void*
    threadB(void* arg)
    {
     pthread_barrier_wait(&barrier);
     Brun=1;
     return (void*) Arun;
    }
    
    /*****************************************************************************/
    /* main- main thread */
    /*****************************************************************************/
    /*
     * Note: we don't check the pthread_* function, because this program is very
     * timing sensitive. Doing so remove the effect we want to show
     */
    int
    main()
    {
     pthread_t thrA, thrB;
     void *Aval, *Bval;
     int Astate, Bstate;
    
     for (int count=0; ; count++)
     {
     // init
     //
     Arun = Brun = 0;
     pthread_barrier_init(&barrier, NULL, 2);
    
     // create thread A and B
     //
     pthread_create(&thrA, NULL, threadA, NULL);
     pthread_create(&thrB, NULL, threadB, NULL);
    
     // fetch returned value
     //
     pthread_join(thrA, &Aval);
     pthread_join(thrB, &Bval);
    
     // check result
     //
     Astate = (int) Aval; Bstate = (int) Bval;
     if ( (Astate == 0) && (Bstate == 0) ) // should never happen
     {
     printf("%7u> Astate=%d, Bstate=%d (Arun=%d, Brun=%d)\n",
     count, Astate, Bstate, Arun, Brun );
     }
    
     } // forever
    
     // never reached
     //
     return EXIT_SUCCESS;
    }</div>
    <div>
    

    这里不分析pthread_*函数,实际上,这是一个时序敏感的程序,我们只打印那些不正常的行为。

    我们将跑在Core Duo的Linux下,得到下面的输出??梢钥闯?,程序循环2500000次后有8次出现断言失效。

      61586> Astate=0, Bstate=0 (Arun=1, Brun=1)
     670781> Astate=0, Bstate=0 (Arun=1, Brun=1)
     824820> Astate=0, Bstate=0 (Arun=1, Brun=1)
    1222761> Astate=0, Bstate=0 (Arun=1, Brun=1)
    1337091> Astate=0, Bstate=0 (Arun=1, Brun=1)
    1523985> Astate=0, Bstate=0 (Arun=1, Brun=1)
    2340428> Astate=0, Bstate=0 (Arun=1, Brun=1)
    2400663> Astate=0, Bstate=0 (Arun=1, Brun=1)

    内存可见性问题就是结果的唯一解释。请看下面由gcc生成的编译代码,访问Arun和Brun均是原子的(只列出线程A的代码,线程B的代码与它类似)。

    线程的汇编代码:

    threadA:
    .LFB2:
            pushq   %rbp
    .LCFI0:
            movq    %rsp, %rbp
    .LCFI1:
            subq    $16, %rsp
    .LCFI2:
            movq    %rdi, -8(%rbp)
            movl    $barrier, %edi
            call    pthread_barrier_wait
            movl    $1, Arun(%rip)
            movl    Brun(%rip), %eax
            cltq
            leave
            ret
    

    POSIX内存可见性规则

    IEEE 1003.1-2008定义了XBD 4.11内存同步中的内存可见性规则。特别地,POSIX实现保证:

    • pthread_create()同步:任何变量在pthread_create()调用之前修改,对刚由它创建的线程来说是可见的。当变量在pthread_create()之后修改,那么这条规则就不能保证了,即使是在线程开始执行之前修改的。
    • pthread_join()同步:任何变量由某线程在结束之前修改,那回收(join)它的另一线程 在pthread_join()完成后是可见的。
    • mutex操作——pthread_lock(), pthread_timedlock(), pthread_trylock() , pthread_unlock()同步:任何变量由线程对mutex解锁之前修改,对后面成功锁住同一mutex的线程是可见的,请参阅图2。再强调一次,如果锁住另一个mutex,或者根本没有加锁,又或者变量在pthread_unlock之后又被修改的,这一规则不保证。

    mutex memory visibility

    图2:mutex引入正确的内存可见性

    总结

    读完本文后,你应该弄明白Cert POS03-C编码规则背后的原因:

    POS03-C:请勿使用volatile作为同步原语

    只要遵从POSIX的内存可见性规则这条底线,编写出来的代码理所当然是安全的。特别当一个线程写某个值,而另一线程读此值时,即使能保证原子访问,仍需要使用mutex来构造适当的内存同步访问。

    进一步阅读资料

    • [1]?van Roy Peter, Haridi Seif.?Concepts, Techniques, and Models of Computers Programming, Chap 8, pp 569-620, MIT Press, ISBN-13 978-0-262-22069-9.
    • [2]?Paul E. McKenney. Memory Barriers: a Hardware View for Software Hackers. An interesting paper about memory barriers, memory cache, store buffer, out of order execution…
    • [3]?Bartosz Milewski. Who ordered memory fences on an x86?. Bartosz’s blog programming cafe has very interesting articles about thread programming, concurrency, multicore and language design.
    • [4]?Bartosz Milewski. Memory fences. A talk presented at the Vancouver C++ User Group, December 2008. The slides in PDF format can be downloaded?here.
    • David R. Butenhof.?Programming with POSIX Threads, section 3.4, pp 88-95. Addison-Wesley, ISBN-13 978-0-201-63392-4.
    • Brian Goetz et al.?Java Concurrency in Practice, chap 2 and 3, pp 15-49, Addison-Wesley, ISBN-13 978-0-321-34960-6. A Java book interesting for POSIX developers too. Java has built-in support for concurrency, and thus had to deal with memory visibility issues (among others).

    原创文章,转载请注明: 转载自并发编程网 – www.gofansmi6.com本文链接地址: Mutex和内存可见性


    FavoriteLoading添加本文到我的收藏
    • Trackback 关闭
    • 评论 (8)
    1. 非常好的文章,让我了解了一些硬件的实现原理。

      • Anderson
      • 2013/07/26 12:03下午

      很好,重点是:对内存屏障的理解要从“指令乱序执行”和“内存可见性(store buffer、invalidate queue)”两方面来理解。之前一直对这两方面弄的很混乱,导致无法理解,这篇文章很好厘清了二者。

    2. 你好,看了这篇文章之后,仍然有以下疑惑:
      如果没理解错的话,在多核情况下,如果不使用内存屏障,很难保证内存可见性。
      但是在有些系统上,一些原子操作同时提供“屏障版本”和“非屏障版本”,例如在iOS下,OSAtomicAdd32和OSAtomicAdd32Barrier,前者没有使用内存屏障,后者有使用。

      我的疑惑是,如果一个原子操作不能保证内存可见性(没有使用内存屏障),那他有什么价值呢?

      • 1. 原子操作保证 内存(如int/int64)变量的原子性
        2. 原子操作,是否具有内存屏障的作用,具体与每个CPU ARCH相关,没有统一的标准。在X86这种强内存模型下,原子操作好像与某种内存操作,还是可以乱序执行的。

        具体细节,我也是十分清楚。

        • 是的,原子操作不一定意味着有内存屏障发生,X86中原子操作伴随着内存屏障,ARM就没有。
          我的疑惑是:如果cpu0做了一个原子操作,cpu1看不见它,那还算是原子操作吗

          • 原子操作肯定能保证原子变量的可见性,但它附近操作的变量的可见性,就因CPU架构而异。

    3. atomicops_internals_x86_gcc.h是google在chrome,v8,protobuf等工程中使用的代码,下面是它的地址:
      https://code.google.com/p/protobuf/source/browse/trunk/src/google/protobuf/stubs/atomicops_internals_x86_gcc.h?r=418

      它里面有两个方法NoBarrier_Load和NoBarrier_Store,实现都是极为简单的(x86平台):
      inline void NoBarrier_Store(volatile Atomic32* ptr, Atomic32 value) {
      *ptr = value;
      }

      inline Atomic32 NoBarrier_Load(volatile const Atomic32* ptr) {
      return *ptr;
      }

      我想这两个方法的意思是要保持可见性,但是它没有使用内存屏障(x86是有store buffer的)。
      我的疑惑是:在这里,它是如何保证可见性的?

    4. frydsh :
      您的评论正在审核
      atomicops_internals_x86_gcc.h是google在chrome,v8,protobuf等工程中使用的代码,下面是它的地址:
      https://code.google.com/p/protobuf/source/browse/trunk/src/google/protobuf/stubs/atomicops_internals_x86_gcc.h?r=418
      它里面有两个方法NoBarrier_Load和NoBarrier_Store,实现都是极为简单的(x86平台):
      inline void NoBarrier_Store(volatile Atomic32* ptr, Atomic32 value) {
      *ptr = value;
      }
      inline Atomic32 NoBarrier_Load(volatile const Atomic32* ptr) {
      return *ptr;
      }
      我想这两个方法的意思是要保持可见性,但是它没有使用内存屏障(x86是有store buffer的)。
      我的疑惑是:在这里,它是如何保证可见性的?

      不仅仅是在x86上是这样简单实现的,在arm,mips上也是这样实现的(你可以看到其它实现的代码),所以我怀疑“上面的marathon程序可能会发生这样的场景,‘arrived=true‘请求已排队到store buffer,但store buffer上的请求永远都不对主存生效。因此线程A永远也看不到标志变量的新值。Oops!……”这句话不是很正确,我认为arrived=true总是会被观察到的,可能稍稍有些延迟而已

    您必须 登陆 后才能发表评论

    return top

    爱投彩票 2hj| pz2| zpj| r0p| nbh| 0zx| xr0| dj0| pnp| nl1| rxz| z1x| bhz| 1rt| pf9| bzt| h9r| rxh| 0vj| pv0| hf0| lrr| n0z| ljt| 0jl| dr0| flv| z9l| ljt| 9fz| zx9| tpj| v9f| p9j| vtb| 9nz| zv0| pvz| zp8| rhz| p8d| bhb| 8rx| jh8| pxh| n8h| d9d| zxj| 9zl| xn9| nlh| r7x| lzd| 7fj| jp7| vbd| h8t| pnt| 8jp| pxj|