concurrent - thawk/wiki GitHub Wiki
顺序一致性模型由 Lamport 于 1979 年提出。顺序一致性模型最好理解但代价太大,原文指出:
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.
该模型指出:如果在共享存储系统中多机并行执行的结果等于把每一个处理器所执行的指令流按照某种方式顺序地交织在一起在单机上执行的结果,则该共享存储系统是顺序一致性的。
顺序一致性不仅在共享存储系统上适用,在多处理器和多线程环境下也同样适用。而在多处理器和多线程环境下理解顺序一致性包括两个方面,
-
从多个线程平行角度来看,程序最终的执行结果相当于多个线程某种交织执行的结果
-
从单个线程内部执行顺序来看,该线程中的指令是按照程序事先已规定的顺序执行的(即不考虑运行时 CPU 乱序执行和 Memory Reorder)
处理器一致性(Processor Consistency)模型比顺序一致性模型弱,因此对于某些在顺序一致性模型下能够正确执行的程序在处理器一致性条件下执行时可能会导致错误的结果,处理器一致性模型对访存事件发生次序施加的限制是:
-
在任意读操作(Load)被允许执行之前,所有在同一处理器中先于这一 Load 的读操作都已完成;
-
在任意写操作(Store)被允许执行之前,所有在同一处理器中先于这一 Store 的访存操作(包括 Load 和 Store操作)都已完成。
上述条件允许 Store 之后的 Load 越过 Store 操作而有限执行。
弱一致性(Weak Consistency)模型的主要思想是将同步操作和普通的访存操作区分开来,程序员必须用硬件可识别的同步操作把对可写共享单元的访存保护起来,以保证多个处理器对可写单元的访问是互斥的。
弱一致性对访存事件发生次序的限制如下:
-
同步操作的执行满足顺序一致性条件;
-
在任一普通访存操作被允许执行之前,所有在同一处理器中先于这一访存操作的同步操作都已完成;
-
在任一同步操作被允许执行之前,所有在同一处理器中先于这一同步操作的普通操作都已完成。
上述条件允许在同步操作之间的普通访存操作执行时不用考虑进程之间的相关,虽然弱一致性增加了程序员的负担,但是它能有效地提高系统的性能。
释放一致性(Release Consistency)模型是对弱一致性(Weak Consistency)模型的改进,它把同步操作进一步分成了获取操作(Acquire)和释放操作(Release)。Acquire 用于获取对某些共享变量的独占访问权,而 Release 则用于释放这种访问权,释放一致性(Release Consistency)模型访存事件发生次序的限制如下:
-
同步操作的执行满足顺序一致性条件;
-
在任一普通访存操作被允许执行之前,所有在同一处理器中先于这一访存操作的 Acquire 操作都已完成;
-
在任一 Release 操作被允许执行之前,所有在同一处理器中先于这一 Release 操作的普通操作都已完成。
在硬件实现的释放一致性模型中,对共享单元的访存是及时进行的,并在执行获取操作(Acquire)和释放操作(Release)时对齐。在共享虚拟存储系统或者在由软件维护的数据一致性的共享存储系统中,由于通信和数据交换的开销很大,有必要减少通信和数据交换的次数。为此,人们在释放一致性(Release Consistency)模型的基础上提出了急切更新释放一致性模型(Eager Release Consistency)和懒惰更新释放一致性模型(Lazy Release Consistency)。
在急切更新释放一致性模型中,在临界区内的多个存数操作对共享内存的更新不是及时进行的,而是在执行 Release 操作之前(即退出临界区之前)集中进行,把多个存数操作合并在一起统一执行,从而减少了通信次数。
-
happens-before
-
sequenced-before(线程内)
在同一个线程内,操作A先于操作B
-
inter-thread happens-before
-
dependency-ordered before(线程间)
-
线程1的操作A对变量M执行“release”写,线程2的操作B对变量M执行“consume”读,并且操作B读取到的值源于操作A之后的“release”写序列中的任何一个(包括操作A本身)
-
线程1的操作A 与线程2的操作X之间存在dependency-ordered before关系,同时线程2的操作B“depends on”操作X(所谓B“depends on”A,这里就不给出精确的定义,举个直观的例子:B=M[A])
-
-
synchronizes-with(线程间)
线程1的操作A对变量M执行“release”写,线程2的操作B对变量M执行“acquire”读,并且操作B读取到的值源于操作A之后的“release”写序列中的任何一个(包括操作A本身)
-
synchronizes-with && sequenced-before
-
sequenced-before && inter-thread happens-before
-
inter-thread happens-before && inter-thread happens-before
-
-