《为什么程序员需要关心顺序一致性(Sequential Consistency)而不是Cache一致性(Cache Coherence?)》有43个想法

  1. 按照我的理解,作者的意思是SC是通过避免乱序优化保证程序的正确性,并且在C++中实现这个的手段是atomic operation.

    如果我的理解是正确的,那么我的疑问是:

    (1)乱序优化是编译器内部的一种实现手段,作为代码者,我完全没有必要知道这个.当然,如果我要了解这个也可以,但是让我在代码上保证这个就完全是”强人所难”.

    (2)就我的知识,atomic operation不是保证避免乱序优化,而是为了保证原子状态的读写操作,在很大程度上是为了避免从缓存读写内容,而是从代价比较昂贵的内存读写.说明atomic operation最好的例子是两个线程对一个int型的变量累加的操作,如果不使用类似于atomic operation的操作,那么最后的结果可能是变量只是累加1,而不是累加2(因为是两个线程).

    1. (1)确实这样给程序员造成了很大的困难,所以有一个简化的data race model被提出来,即只要保证acquire和release语义就能简化编程和编译器优化的难度,具体的你可以看看参考文献[6]。但是我想说,进入多核时代后不管是程序员还是compiler writer还是搞体系结构的都面临非常多的新挑战,现阶段不可能programmer什么都不需要做就可以免费的享受多核,阵痛是难免的。
      (2)我原文中对atomic operation只是一笔带过,近期会专门写一篇文章讲它,实际上atomic operation会有memory ordering的语义。

  2. 感谢博主的分享。Cache Coherence在动态生成二进制代码并执行的时候是需要关注的,例如Chunck技术。

  3. 另外,请教博主一个问题,乱序到底是指的哪种语义?
    1、CPU本身执行指令的时候是乱序执行的,但对于程序员来说其执行结果等价于按程序序依次执行指令的结果,从而对程序员透明。
    2、编译器编译优化的过程中根据CPU的流水线特征做了指令重排,在单个线程遵循程序序,但是由于不知道多线程运行环境,可能保证不了程序整体语义上的程序序,从而导致执行结果错误。

    麻烦解释下这个困惑我很久的问题,多谢。

    1. @ericliu
      就像你说的,乱序即有CPU造成的也有和编译器造成的。在传统的单线程语义下,CPU和编译器的乱序优化是不会影响程序语义的正确性的,所以对程序员来说就是透明的。但是在多线程环境下,因为CPU和编译器都缺少对多线程程序语义的“整体性”的了解,所以就可能造成违反多线程语义的错误的优化。说简单点,就是因为CPU和编译器还未能跟上多核时代的步伐。要保证正确性最简答的办法就是不做乱序优化,直接按照我文中所指的Sequential Consistency的方式顺序执行,可是这样对程序的性能影响太大,本质上CPU和编译器之所以要乱序执行就是为了提高性能。所以现在的折衷方案是由程序员来在适当的地方使用带有acquire和release的原语来“告诉”CPU和编译器你在这个地方不能给我做优化,其他的地方你可以做。Acquire和release语义的原语在内部会调用memory barrier来保证memory order。例如,VS2005开始所有volatile变量的读操作有acquire语义,写操作具有release语义。这个属性在C++标准里是没有的,属于VS自己的扩展。但是尽管如此,volatile在多线程里面还是非常难搞的一个概念,我会专门写一写它。

  4. 我不懂為什麼程序员会滿足于SC?上例Execution 1,Execution 2,Execution 3都滿足SC,但r1,r2结果都不一樣;有哪一個程序员会喜歡non-deterministic的结果?

    1. 恩 non deterministic是Multicore的固有通病 而且是很多concurrency bug的根源。现在一个研究热点就是deterministic并行。

      1. 所以你同意SC没有用? 要deterministic的结果就要加synchronization(wait, signal等),加了synchronization就定了execution order,SC就无用武之地了!?

    2. My point is: In order to get deterministic result, one has to put in synchronization, and once sync is put in, one fixes the order of execution – at least the order which SC tries to re-arrange – and SC is rendered irrelevant; using SC or not, reordering is not allowed; no one can benefit from reordering.
      Look at the exmple. If you want r1==0 and r2 == 1, then you can allow Exec 1 only, and you will write
      Thread 1 {
      x = 1;
      r1 = y;
      signal(sync)
      }
      Thread 2 {
      wait(sync)
      y = 1;
      r2 = x;
      }
      And yes, the compiler can still reorder (switch the order of) the 2 assignments in Thread 1, and the 2 assignments in Thread 2, though that’s not even allowed by SC. But the orders of execution in Exec 2 and 3, allowed under SC, are no longer permitted once synchronization is added to ensure deterministic result. Then what’s the use of SC? And why does a programmer need to care about the consistency model? Once synchronization is put in to ensure determinism, the execution order is pretty much fixed.

      1. Good point.
        我同意你的观点:从程序员的角度来讲,为了保证r1,r2的最终值是确定的,程序员会使用synchronization来使得程序按自己的意志来进行。其实这就是编写多线程程序时的一条关键准则:任何时候都不能假定你的程序会按照你所想的执行顺序去执行(因为execution order是不确定的),而是需要使用synchronization来确保程序会按你所想的方式去执行。

        至于SC,它之所以有用是因为JDK1.5和C++ 1x的多线程内存模型中就引入了SC for data race free这个模型。基于这个模型,在进行lock free编程的时候程序员就特别需要注意memory consistency相关的概念(因为这时体现在代码上的就不是经常用的lock,conditional variable等开销很大的同步机制,而是带有原子性和顺序性语义的atomic变量了)。希望我这个解释能让你满意:)

        1. 不满意:) “SC…有用是因为…进行lock free编程的时候程序员就特别需要注意memory consistency相关的概念” 我说过,你也同意,程序员会使用synchronization来确保determinism。那为何又会进行lock free编程呢?你有不用lock也可确保determinism、correctness的程序例子吗?“atomic变量”其实是不是一个syntactic sugar? 把一个变量declare為“atomic variable”其实不就是每一次access它的时候都加mutex lock? 在program中每一次access它的时候都加mutex lock太麻烦,所以便弄了“atomic”这个data type,为程序员save some trouble.

        2. “SC有用是因为SC for data race free这个模型” – SC 在 SC for data race free这个模型 出现前很久就有了。所以在 SC for data race free这个模型 出现前,SC是没用的?有人没事做,搞一个SC出来;十几/几十年后,搞SC for data race free模型的时候才发觉SC的用处???
          BTW, data race和data dependence分别在那?

          1. What I actually meant to ask is: Can data race be determined by data dependence?

          2. 呵呵,“SC有用是因为SC for data race free这个模型”这句话确实不严谨。我举个例子吧,在C++1x中,程序员可以对atomic类型的操作制定三种不同类型的memory ordering:sequential consistent ordering,acquire release ordering和relaxed ordering。atomic类型比mutex提供了更大的灵活性(例如可以用atomic类型实现lock free算法),两者不可同日而语。如果程序员对这三种ordering的特点不了解的话就不能很好的使用atomic类型,这直接证明了为什么程序员需要了解SC。

          3. 言下之意就是如果没有C++1x的memory ordering,就没有必要了解SC? 首先说“SC有用是因为SC for data race free这个模型”,现在又好像说SC有用是因为C++1x的memory ordering,究竟SC可不可以有自己的用处?

  5. 我想讲清楚我讲的deterministic是指final values of r1 and r2不是指execution order.

    1. 其实到处都有non-deterministic的现象啊,比如抢占式操作系统,你并不关心某个进程何时分到了多大的时间片;比如windows消息机制,你并不在乎程序一定的情况下消息是否按照某个顺序到达。SC是个基本的保证,即使加了同步语义,程序的结果是deterministic,仍然包含在SC的框架下了

  6. “其实到处都有non-deterministic的现象”- I agree, but that’s not my point. Programmers do not like non-deterministic output (i.e. final values), so they use synchronization to ensure determinism. “SC是个基本的保证” – 保证什么呢?保证determinism吗?文中已有例子说明SC不保证determinism!Synchronization才是保证determinism。我不知道你的“SC框架”是什么框架。有了Synchronization保证determinism,再搞一个“SC框架”不是多此一举吗?

    1. A consistency model limits the values of a variables from a read. In the example in the article, (r1,r2) can be at least (0,1),(1,0),(1,1),(0,0). But SC limits the set of possible values to be the first three pairs only. A relaxed model may allow all 4 possibilities. My point is: A programmer in 99% of the cases would like only one possibility; so he uses synchronization. Once synchronization is used, the consistency model is irrelevant. Then why care about what consistency model is used and what possibilities there are? And I think that’s why most parallel programming languages do not specify a consistency model. Now Java and C++ are trying to specify one – is it only because that they have these volatile and atomic variables? Then, if they don’t have these data types, does it mean a consistency model is not needed? And are these data types really needed? Or because there are emerging applications that permit non-determinism?

  7. 1)Synchronization本身的实现就是需要考虑SC的,换句话说,如果没有SC,Synchronization都根本实现不了,所以说操作系统编写人员在SC的基础上,实现了一整套Synchronization供应用程序开发人员调用;
    2)对于95%以上的程序员实际上都可以用Synchronization取代关键代码端SC的MB操作,但仍然有一些程序员在考虑性能终极优化的时候需要深入了解SC,比如一些核心服务器报文转发,如果收到报文就掉Synchronization,那整体性能会非常差,SC可以在这个层面保证吞吐量和最佳的性能。目前一些云计算的一些程序都再用SC取代Synchronization了。

  8. “用Synchronization取代关键代码端SC的Memory Barrier操作” — Synchronization的定義為何?SC的MB操作指何? Process (or thread) synchronization construct 很多都imply有 data synchronization (e.g. Memory Barrier)。 OpenMP的”end parallel” directive就imply memory barrier。那不是“取代”。

  9. 最近一直对memory barrier 非常疑惑,由于最近在写多线程服务器。我想问下我的理解是否正确
    1。Memory barrier是用来保证SC的而不是用来刷新CPU Cache到内存的
    2。一个核上的线程对某个内存的操作不需要显示调用MB等操作也能在其他核上运行的线程的读操作
    反应出来(这是通过文章中所说的CC协议所保证的,是对程序员透明的)
    3。如果有这样2个线程,
    bool continuerun = true;
    线程1
    while(continuerun)
    {
    …do something
    }
    线程2
    while(1)
    {
    if(如果用户输入exit)
    continuerun = false;
    }

    对于这样一个程序,如果用户输入exit以后,continuerun的变量改变会在另外一个线程中立即反应出来(由CPu的CC协议保证)
    是这样么

    1. 个人观点,仅供参考:
      1.Memory barrier是用来保证SC的而不是用来刷新CPU Cache到内存的。这一点肯定是对的。
      2.关于第二点和第三点显然不对。“一个核上的线程对某个内存的操作不需要显示调用MB等操作也能在其他核上运行的线程的读操作反应出来” — 那我们还要“锁”干嘛!
      3. “2个线程”的编码应该为:
      bool continuerun = true;
      pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
      pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
      线程1
      pthread_mutex_lock(&lock);
      while(continuerun)
      {
      …do something
      pthread_cond_wait(&cond, &lock);
      …do something
      }
      线程2
      while(1)
      {
      if(如果用户输入exit){
      pthread_mutex_lock(&lock);
      continuerun = false;
      pthread_cond_signal(&cond);
      pthread_mutex_unlock(&lock);
      }
      }

      1. 不好意思,看您回答说第二点肯定不对,但是从博主这篇文章中“
        。Cache Coherence(下文简称CC)是多核CPU在硬件中已经实现的一种机制,简单的说,它确保了对在多核CPU的Cache中一个地址的读操作一定会返回那个地址最新的(被写入)的值。

        感觉第二点也是对的啊,请博主也发表一下意见,谢谢

        1. digdeep说的一定要用mutex是对的。

          “Cache Coherence(下文简称CC)是多核CPU在硬件中已经实现的一种机制,简单的说,它确保了对在多核CPU的Cache中一个地址的读操作一定会返回那个地址最新的(被写入)的值。”,这句话没错,但是在程序中,continuerun这个被线程1写入的新值一定在线程2读到之前就“真正被写入到cache里”,而不是暂时缓存在cache buffer之类的地方,是需要用锁来保证的。两者是两个维度的问题。

          1. 博主,你好,你在回复中提到“continuerun这个被线程1写入的新值一定在线程2读到之前就“真正被写入到cache里”,而不是暂时缓存在cache buffer之类的地方,是需要用锁来保证的”,CACHE和CACHE BUFFER各指什么?难道他们不是CPU中的L2么?

    2. 在网上查到一片英文资料,刚好可以回答你的第2、3个问题:http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html
      Cache Coherence:
      Most authors treat cache coherence as being virtually synonymous with sequential consistency; it is perhaps surprising that it isn’t. Sequential consistency requires a globally (i.e. across all memory locations) consistent view of memory operations, cache coherence only requires a locally (i.e. per-location) consistent view. Here’s an example of a scenario that would be valid under cache coherence but not sequential consistency:
      P1: W(x)1 W(y)2
      ———————–
      P2: R(x)0 R(x)2 R(x)1 R(y)0 R(y)1
      ———————–
      P3: R(y)0 R(y)1 R(x)0 R(x)1
      ———————–
      P4: W(x)2 W(y)1
      这里有四个进程(线程)P1和P4对x,y进行写操作,而P2和P3对x,y进行读操作。我们可以看到:在P1和P4对x进行写操作之后,P2最先读到的x=0;在P1和P4对y进行写操作之后,P2和P3竟然从来没有读到y=2的情况。所以说:在程序员的头脑中最好忘掉“CC”,“CC”与我们程序员没有半毛钱的直接关系。
      注:这里P2和P3看到的“执行顺序”不一致,所以它违反了“SC”!

  10. NND,格式发生了变化,补充一下:
    P1: W(x)1 W(y)2
    ———————–———————–———————–———————–———————–
    P2: R(x)0 R(x)2 R(x)1 R(y)0 R(y)1
    ———————–———————–———————–———————–———————–
    P3: R(y)0 R(y)1 R(x)0 R(x)1
    ———————–———————–———————–———————–———————–
    P4: W(x)2 W(y)1

    1. 还是不行,“P2:”和“P3:”后面的三个空格被系统自动删除了。又不能发图片。还是参考原网站吧:http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html

  11. “在进入多核时代后编译器没跟上发展” 對於這句話我要發點聲。這根源應該在於語言要先訂出記憶體模型,而後編譯器才能依照語言規定進行優化。說编译器没跟上发展有點冤枉它了。:)

  12. 我最近在写多线程的程序时,对C++ 的关键字volatile 非常的不解,很多人说在多个线程共享的变量前都在加这个,但你又说不用去理会CC,我真是晕头了。

  13. 楼主,似乎 Cache Conherence (缓存一致性)应该是Cache Coherency?

    1. 哦,仅是一个笔误而已,无关大局,我反倒自己不看前面其实是正确的

电子邮件地址不会被公开。 必填项已用*标注