Memory Consistency Model for Shared-Memory Multiprocessors学习笔记(一)

        最近纠结与linux kernel中关于memory barrier的语义和使用方法。遂进行深入阅读研究,所思所得记录如下。


一,Sequential Consistency Model

        对于程序员来说,在SMP系统中编程,最直观的内存一致性模型就是Sequential Consistency (SC,其实内存一致性模式可以扩展为分布式系统中的一致性模型)。因为它跟UP系统中的顺序模型最接近。Lamport对SC给出如下定义:

                A multiprocessor is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

        此定义分为两部分:1)从任一处理器的角度看,整个系统中所有处理器发送(inssue)的所有内存操作(memory operations)都是以同一个顺序次序(sequential order)依次完成(complete)。2)在整个顺序次序中,任一单个处理器发送的操作都是以该处理器运行的代码所指定的次序(program order)依次完成。事实上,此定义规定了SC模型必须维持的原子性(atomicity)和代码顺序(program order)两个要求。下面我们以代码说明此模型,其中大写字母为系统共享内存中的变量,小写字母为单个处理器中的私有变量,所有变量在未特别说明时都初始化为0。

                       P1                         P2

                  a1:   A = 1;           a2:   u = B;

                  b1:   B = 2;           b2:   v = A;

                                代码1

         假设代码1在某次运行(execution)后发现u == 2,那么我们会“想当然”的认为v == 1。因为我们直觉地认为,在这次运行中,如果u == 2,说明读操作a2完成于写操作b1之后,由此断定读操作b2一定完成于写操作a1之后,这样可得结果v == A == 1。因此,可以推断系统可能以(a1,b1,a2,b2)的次序完成所有操作。这就是SC模型。也是最简单,最直观,最严格(strict)的模型。

        前面对代码1运行的推断基于SC模型的第二条性质——代码次序,即要求所有操作以代码指定的次序完成。不幸的是,几乎所有的真实系统,由于采用了各种硬件或编译器优化技术,并不”直接“满足此模型。这些优化技术可能使系统违背SC定义中的任何一条——原子性或者代码顺序。我们来看一个违背了原子性的模型。由Lamport定义的第一条可知,原子性是指从任一处理器的角度看,对同一地址的写操作都是以同一次序完成。

                             P1                      P2                        P3                       P4

                        a1: A = 1;         a2:   u = A;           a3:   w = A;          a4:   A = 2;

                                                b2:   v = A;           b3:   x = A;

                                                         代码2

        假设运行代码2的系统采用了Cache,而且P2与P3各自拥有A的拷贝。这样,开始运行后,P1会发送A的更新值1分别到P2与P3。同样,P4会发送A的更新值2分别到P2与P3。由于系统的各种延迟,更新消息可能以不同次序到达P2与P3。比如,从P2角度看,P1的更新值1先于P4的更新值到达,从P3角度看,P4的更新值先于P1的更新值到达。这样会产生(u,v,w,x)==(1,2,2,1)这样的结果,显然该结果不符合SC模型,它违背了SC模型的原子性。后面介绍的模型都是以SC模型为参考进行变形(Relaxation)。


二,Relaxing the Write to Read Program Order

         W-R Relaxation模型为SC模型的一个变种,IBM-370是该模型的一个具体实现。该模型允许前面的某个写操作与其后面的某个读操作,在两个操作地址不同的情况下,能够乱序完成(W-R Reordering)。示例如下:

                       P1                           P2

                a1:   A = 1;             a2:   B = 1;    

                b1:   u = B;             b2:   v = A;

                                代码3

          在SC模型中,代码3只可能产生(u,v)==(1,1),(1,0),(0,1)三种结果,而不可能产生(0,0)的结果。可是此结果在W-R Relaxation模型中是可能的。比如,该代码在此模型中可能以(b1,a2,b2,a1)次序完成,即读操作b1被允许在写操作a1完成前完成。

          需要注意的是,此类模型中,要求对同一地址的W-R操作不能乱序完成,即如果W-R操作的两个地址相同,那么这两个操作必须按代码次序完成。更广泛的讲,竞争操作(competing operations),即对同一地址的的多个操作中存在至少一个写操作,必须维持这些操作的代码次序。


三, Relaxing the Write to Write Program Order

        与W-R Relaxation模型类似,W-W Relaxation模型除了允许W-R乱序外,还允许W-W乱序,即两个写操作,在两个操作地址不同的情况下,能够乱序完成(W-W Reordering)。示例如下:

                         P1                                     P2

                  a1:   A = 1;                      a2:   while (Flag == 0);

                  b1:   B = 1;                      b2:   u = A;

                  c1:   Flag = 1;                  c2:   v = B;

                                         代码4

        在SC模型,甚至W-R Relaxation模型中,代码4只有(u,v)==(1,1)一个合理结果。可在W-W Relaxation模型中,(1,0),(0,1),(0,0)都是合理结果。比如,该代码在此模型中可能以(a1,c1,a2,b2,c2,b1)的次序完成,即写操作c1被允许在写操作b1前完成。

        同样需要注意的是,此类模型中,要求维持对同一地址的W-W操作的代码次序。


四, Relaxing the Read to Read and Read to Write Order

         此模型相比前面的模型更加宽松,它允许R-R操作和R-W操作乱序完成。与前面的模型类似,此模型要求维持竞争操作的代码次序。


参考资料:

《Memory Consistency Model for Shared-Memory Multiprocessors》 by Kourosh Gharachorloo

《Memory Barriers: a Hardware View for Software Hackers》 by Paul E. McKenney

### 回答1: 《a primer on memory consistency pdf》是本关于内存致性的入门指南。内存致性是指在多线程编程中,对共享变量的访问操作的执行顺序保持致的问题。在多核处理器上运行的并发程序中,由于缓存、指令重排等因素的存在,不同核之间读写共享变量的顺序可能不同,从而导致程序产生错误的结果。 这本《a primer on memory consistency pdf》通过深入浅出的方式介绍了多线程编程中的内存致性问题及其解决方案。首先,它解释了为什么多线程程序需要关注内存致性,并对内存模型进行了详细的介绍。然后,它介绍了在不同内存模型下,程序的执行顺序可能发生的变化,并举例说明了这些变化可能带来的问题。 接着,书中详细介绍了些常见的内存致性模型,如顺序致性、弱致性、松散致性等,并解释了它们之间的区别和适用场景。同时,还介绍了如何使用同步原语(如锁、原子操作)来保证多线程程序的正确性,以及编译器和处理器级别的优化技术对内存致性的影响。 此外,《a primer on memory consistency pdf》还对些实际应用中的内存致性问题进行了讨论,如并发数据结构、并行算法等。通过这些案例,读者可以更好地理解内存致性问题的实际应用和解决方法。 总之,《a primer on memory consistency pdf》是本很好的入门指南,通过简明扼要地介绍内存致性问题及其解决方案,读者可以对多线程编程中的内存致性有个较为全面的了解,并且可以在实际应用中进行正确的处理。 ### 回答2: 《内存致性基础中文版PDF》是本介绍内存致性的基础知识的文档。内存致性是指对于多个并发执行的进程或线程,它们观察到操作内存的结果是致的。在多核处理器系统中,每个处理器都有自己的缓存,如果缓存数据不致,就会导致内存不致性的问题。 这份文档首先介绍了内存致性的背景和重要性。在多核处理器和并发编程的背景下,内存致性变得尤为重要。接着,文档详细介绍了不同的内存致性模型,包括顺序致性、弱致性和松散致性等。每种模型都有自己的特点和适用场景,了解这些模型能够帮助程序员编写高效且正确的并发程序。 文档还介绍了些实现内存致性的技术,如缓存致性协议和内存屏障等。了解这些技术可以帮助开发者更好地理解内存致性的原理和实现机制。此外,文档还提供了些实际应用的示例和案例,让读者更好地理解内存致性在实际开发中的应用和挑战。 《内存致性基础中文版PDF》是份权威且易懂的资料,适合对内存致性感兴趣的学生、程序员和系统工程师阅读。它可以帮助读者建立起对内存致性概念的全面和深入的理解,为他们编写高效且正确的并发程序提供指导和帮助。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值