CPU Cache and Memory Ordering——并发程序设计入门

7月 13th, 2013

CPU Cache and Memory Ordering

内容简介

本PPT,为本人学习CPU架构以及并发程序设计的一些心得与收获。主要内容包括:

 

  •   简单介绍CPU的架构,部分主要模块及其功能(Cache Structure, Cache Line , Set-Way);
  •   Cache Coherence算法 (MESI, MOESI);
  •  CPU Memory Ordering模型 (Atomic,Reorder,Memory Barrier (Compiler, CPU),Lock Instruction,Load Acquire/Store Release);
  •  并发程序设计 (实现一个Spinlock,纠正一个Lock-Free Algorithm,Data Race (False-Sharing, Per-Processor Data));

 

分享地址

新浪微盘

  • PPT格式下载地址:点我
  • PDF格式下载地址:点我

 

说明:推荐下载PPT格式,每页PPT的备注中,都有对应的参考资料,可进行深入的学习。而PDF格式,所有的参考资料,均在最后给出。

 

SlideShare


 

 

 

  1. 銀座 tory burch
    9月 5th, 201311:30

    セールtory burch カチューシャ

  2. hydra
    11月 27th, 201317:34

    感谢你的分享.收获非常多。

  3. frydsh
    12月 24th, 201317:38

    你好,看了你的这篇文章之后,还是有一个疑惑,不知道下面的说法是否正确:
    缓存一致性会保证所有的CPU看到一致的数据,当然由于Store Buffer等机制的原因,某些CPU可能迟一些看到数据的改变,但是最终都会看到(即使不使用memory barrier)。

    share variable:
    bool run = true;

    thread 1:
    void foo()
    {
    while(run)
    {
    // do something
    }
    }

    thread 2:
    void bar()
    {
    run = false;
    }

    这里应该可以正常运行的吧(不使用memory barrier),当thread 2运行了bar之后,thread 1应该可以从foo中返回,因为这里对顺序没有要求,只要求可以看到run变量的最新值,对吗?

    但是一些文章说thread 1可能永远也看不到run变为了false,为什么?

    期待你的解惑

    • hedengcheng
      12月 24th, 201318:46

      有可能看得到,有可能会永远看不到,在于编译器的优化。
      如果编译器优化的很彻底,发现thread 1中永远不会改变run的取值,认为run一直是true,进而把while(run)改写为while(true),那么就永远看不到run的改变了。
      因为C/C++语言设计之初,未考虑多线程,因此编译器有可能会有这种优化。

      • frydsh
        12月 24th, 201321:02

        也就是说,如果看不到,并不是因为store buffer的原因,而是因为编译器优化;如果禁止编译器优化,那么应该没事。

        另外再问一个问题:如果对run变量采取pthread_mutex保护的话,问题是否能得到解决呢?还是要采用volatile关键字才行?

        • hedengcheng
          12月 25th, 201312:08

          都有可能,既有可能是编译器,也有可能是CPU的store buffer。

          用pthread_mutex就没问题了,mutex的语义,跟spinlock一致,可以参考我最新的博文:锁的意义。

          • frydsh
            12月 25th, 201315:05

            我看了“锁的意义”这篇文章,但还是觉得要用volatile才行,否则编译器还是可能优化它(将while(run)改写为while(true)),还是说pthread_mutex会阻止编译器做这个优化(将while(run)改写为while(true))?
            “锁的意义”这篇文章只说到阻止编译器做顺序上的优化,没有说阻止这类优化(将while(run)改写为while(true))。

            另外我觉得这里只需要用volatile就可以了(对单一变量赋值应该可以保证可见性,不管有没有store buffer的存在),不需要用锁,不知道对不对?

  4. 郜小农
    1月 27th, 201415:13

    没看出frydsh的这个例子中的问题和store buffer有什么关系,能不能举例说明一下?
    我觉得用了volatile就可以了,阻止编译器优化不仅仅是阻止它顺序优化。
    另外he博士,在PPT中,关于纠错的那个person算法。 这个算法好像是很久之前提出来的,应该是基于单CPU多线程。 如果这个前提上,应该是没有问题的吧。

    • hedengcheng
      1月 28th, 201417:43

      我又考虑了一下。frydsh的例子,还是在于编译器的优化,跟store buffer应该无关。

      关于peterson算法,哪怕在单核多线程下,也不能够保证正确性。因为乱序有两种情况,一种是编译器导致的,一种是cpu执行时导致的。无论是否单核,编译器都有可以调换两个不相关的内存操作的顺序,进而导致哪怕在单核下执行,peterson算法也有可能是错的,编译器做了不该做的优化。至于单核下,cpu是否仍旧会执行乱序,我个人觉得不可能。

  5. bearxiong
    2月 17th, 201422:03

    Hi
    向你请教一个问题,我在看你CPU Cache and Memory Ordering——并发程序设计入门这个pdf一直有个问题想不明白,在你simplest spinlock的例子里面,spin_lock() [all memory operations] spin_unlock()[intel平台],比如thread 1(cpu 0)首先获取到了这个锁更新了全局变量a=1,之后释放这个锁,thread 2(cpu 1)获取到了这个锁,然后去读取这个变量a,那会不会出现这种情况,thread 1在更新 a的时候只把a=1 写到了store buffer,还没有刷新到cache,thread 2去读取a的时候读取到的值可能就是old value而不是thread 1更新的值?

    Thanks

    • hedengcheng
      2月 18th, 201410:49

      不会。锁的一个性质,就是unlock至lock间有一个happens-before语义。你可以这么认为,unlock的时候,会把store buffer中所有的写操作,按顺序刷出到内存,保证写出对其他lock操作的线程可见。

      • bearxiong
        2月 18th, 201410:56

        但是你例子里面的spin_unlock的代码是这样子的barrier();*lock=0,这个能保证store buffer刷新到cache吗?
        我想应该需要一个store barrier指令才行吧,比如sfence。

        Thanks

        • hedengcheng
          2月 18th, 201413:50

          我指的是你可以形象的这么理解。实际上的细节是,unlock是一个release语义,保证unlock前的内存操作在unlock操作之前完成。其他线程能够lock成功,说明其他线程已经读到了unlock的数据,那么就一定能够读到unlock之前的内存操作。而且,在intel x86体系下,storestore是不会乱序的。unlock对应的写操作,在store buffer中一定在lock保护下的内存操作之后,因此unlock能看到,说明store buffer之前的内存操作已经被写出了。

          • bearxiong
            2月 18th, 201414:30

            谢谢你的解答。

          • 阳凌
            4月 2nd, 201514:11

            还是同样的问题,x86 oostore 体系,按照wiki上http://en.wikipedia.org/wiki/Memory_ordering#cite_note-table-8 给的图标,显示应该是 storestore的。但是一直查不到相关x86 oostore的资料。能讲解一下吗?

          • 阳凌
            4月 2nd, 201514:13

            同时在内核中看到 ticket spinlock 的代码
            static inline void __raw_spin_unlock(raw_spinlock_t *lock)
            {
            __asm__ __volatile__(
            UNLOCK_LOCK_PREFIX “incb %0″
            :”+m” (lock->slock)
            :
            :”memory”, “cc”);
            }

            a.在 IA32 体系结构下,如果使用 PPro SMP 系统或者启用了 X86_OOSTORE,则 UNLOCK_LOCK_PREFIX 被定义为“lock”前缀;否则被定义为空。 也看到了X86_OOSTORE的东西,

          • hedengcheng
            4月 2nd, 201515:19

            按照这个说法,intel有两种cpu,一种是x86体系,例如:nehalem,sandybridge;还有一种是安腾cpu,这个cpu是内存弱一致模型的,oostore应该是指安腾cpu,弱一致模型。

  6. 阳凌
    4月 2nd, 201517:18

    hedengcheng :
    按照这个说法,intel有两种cpu,一种是x86体系,例如:nehalem,sandybridge;还有一种是安腾cpu,这个cpu是内存弱一致模型的,oostore应该是指安腾cpu,弱一致模型。

    我也看你给的下面,是截取自Wiki上的一幅图,列举了不同CPU架构,可能存在的指令乱序。wiki上的一个图。
    里面提到了 x86 oostore 和X86 还有IA64单独分开的。,应该是不同的架构,从wiki给的资料来看,似乎IA64和oostore的乱法是一样的乱法。应该不是你说的 安腾 不是安腾一般是IA64这样的说法,而且WIKI也单独列举了IA64

  7. 林间晓风
    7月 31st, 201615:42

    文章不错,想知道您对 storebuffer 有了解么。知道具体写入过程是怎样的么,是否可能存在这种场景:
    CPU1 把X写入 store buffer1
    CPU2 紧接着把X写入 store buffer2

    那最终MEM内存里面的数据是后面的CPU2的么,怎么保证时序的?