14 Advanced Synchronization

14.1 Avoiding Locks

第五章中一些无锁实现的算法：

• count_stat
• count_stat_eventual

最好是将无锁技术隐藏在良好定义的API之中，如inc_count（），memblock_alloc（），rcu_read_lock（），等等。其原因是，随意使用无锁技术，它是创建大BUG的良好途径。 许多无锁技术的关键部分是内存屏障，这将在随后的章节中介绍。

14.2 Memory Barriers

14.2.1 Memory Ordering and Memory Barriers

编译器和同步原语（如锁和RCU）有责任通过对内存屏障（例如，在Linux内核中的smp_mb（））的使用来维护这种用户在执行顺序方面的直觉。

14.2.2 If B Follows A, and C Follows B, Why Doesn’t C Follow A?

一个典型的用例：

#define barrier() __asm__ __volatile__("": : :"memory")
thread0(void)
{
    A = 1;
    smp_wmb();
    B = 1;
}
thread1(void)
{
    while (B != 1)
    continue;
    barrier();
    C = 1;
}

thread2(void)
{
    while (C != 1)
    continue;
    barrier();
    assert(A != 0);
}

如果在真实世界的弱序硬件（一个1.5GHz 16-CPU POWER 5系统）上运行这个代码超过10M次的话，将导致断言被触发16次。显然，任何想编写内存屏障代码的人，需要做一些极限测试。
当然，在x86中不会触发断言，

修改方法：

#define barrier() __asm__ __volatile__("": : :"memory")
thread0(void)
{
    A = 1;
    smp_wmb();
    B = 1;
}
thread1(void)
{
    while (B != 1)
    continue;
    smp_mb();
    C = 1;
}

thread2(void)
{
    while (C != 1)
    continue;
    smp_mb();
    assert(A != 0);
}

14.2.3 Variables Can Have More Than One Value

state.variable = mycpu;
lasttb = oldtb = firsttb = gettb();
while (state.variable == mycpu) {
    /* 记录变量将时间计数器赋予本CPU的时间长度 */
    lasttb = oldtb;
    oldtb = gettb();
    if (lasttb - firsttb > 1000)
        break;
}

小问题14.3：是什么假定条件使得上面的代码片断在实际的硬件中不再正确？

答案：代码假设，某个指定的CPU只要看不到自己的值，它将立即看到最后的新值。在实际的硬件中，某些CPU可能在收敛到最终的值以前，会看到几个中间的结果。
关键在于每个CPU看到的state.variable是不一样的。通过以上代码可以统计在每个CPU中看到的state.variable的值及其对应的时间。

每一个水平条表示一个特定CPU观察到变量的时间，左边的黑色区域表示相应的CPU第一次计数的时间。

14.2.4 What Can You Trust?

最基本的内存屏障语义：所有 CPU架构都遵从如下规则

1. All accesses by a given CPU will appear to that CPU to have occurred in program order.
   一个特定CPU的所有访问操作都与该CPU上的编程顺序一致。

2. All CPUs’ accesses to a single variable will be consistent with some global ordering of stores to that variable.
   所有CPU对单个变量的访问都与存储这个变量的全局顺序多少有一些一致性。

3. Memory barriers will operate in a pair-wise fashion.
   内存屏障以成对的形式进行操作。

4. Operations will be provided from which exclusive locking primitives may be constructed.
   内布屏障操作能够由互斥锁原语所构建的语义提供。

14.2.4.1 Self-References Are Ordered

一个特定CPU将以“编程顺序”那样看到它对内存的访问操作。

14.2.4.2 Single-Variable Memory Consistency

对于单个变量来说，终将会对其值序列达成一致。如图14.5所示。
与之相对的，如果有多个变量，就目前所见的商业计算机系统来说，则需要内存屏障，以使CPU达成顺序一致。

14.2.4.3 Pair-Wise Memory Barriers

CPU 1       CPU 2
access(A);  access(B);
smp_mb();   smp_mb();
access(B);  access(A);

基本内存模型如上所示，其中A和B的初值为0，access可能是load或store，因此有16种可能，如下表所示：

ears => 多次加载
mouth => 多次存储

14.2.4.4 Pair-Wise Memory Barriers: Portable Combinations

• pairing 1

  CPU 1       CPU 2
  A=1;        Y=B;
  smp_mb();   smp_mb();
  B=1;        X=A;
  

在CPU1中执行一对被内存屏障分隔开的store指令，在CPU2中执行一对被内存屏障分隔开的load指令，在该语境下，有if (Y == 1) assert(X == 1)。

• pairing 2

CPU 1       CPU 2
X=A;        Y=B;
smp_mb();   smp_mb();
B=1;        A=1;

对应结果如下所示：

if (X == 1) assert(Y == 0)
if (Y == 1) assert(X == 0)

• pairing 3

CPU 1        CPU 2
X=A;         B=2;
smp_mb();    smp_mb();
B=1;         A=1;

对应结果如下所示：

if (X == 1) assert(B == 1); // CPU1对B的存储将重置CPU2对B的存储
if (X == 0) // B可能为1，也可能为2。

14.2.4.5 Pair-Wise Memory Barriers: Semi-Portable Combinations

21stcentury hardware would guarantee that at least one of the loads saw the value stored by the corresponding store (or some later value for that same variable).

至少有一个加载将看到相应存储的值。

• Ears to Mouths:

  CPU 0        CPU 1
  A=1;         B=1;
  smp_mb();    smp_mb();
  r1=B;        r2=A;
  

对应结果如下所示：

if (r1 == 0) assert(r2 == 1);
if (r2 == 0) assert(r1 == 1);

至少r1和r2中的某一个必然不是0，这意味着至少有一个加载将看到相应存储的值。

• Stores “Pass in the Night”

  CPU 1        CPU 2
  A=1;         B=2;
  smp_mb();    smp_mb();
  B=1;         A=2;
  

  假设CPU1持有B的cacheline，CPU2持有A的cacheline，可能会出现B==1 && A==2同时出现的情况。
  详见附录C中的表述。

14.2.4.6 Pair-Wise Memory Barriers: Dubious Combinations

• Ears to Ears 如果我们知道CPU 2对B的加载，返回一个更新的值，该值比CPU 1对B的加载值更新，那么我们将知道，CPU 2对A的加载，其返回值要么与CPU 1对A的加载值相同，要么是其更新的值。

• Mouth to Mouth, Ear to Ear

Because it is not possible for one load to see the results of the other, it is not possible to detect the conditional ordering provided by the memory barrier. If additional load from B is executed after both CPUs 1 and 2 complete, and if it turns out that CPU 2’s store to B happened last, then we know that CPU 2’s load from A returned either the same value as CPU 1’s load from A or some later value.

• Only One Store

在这种情况中，没有办法检测到由内存屏障提供的某种条件的顺序。

对于表14.1中的组合1，CPU 1对A的加载返回CPU 2对A的存储的值。那么我们知道CPU 1对B的加载，要么返回CPU 2对A的加载的值，要么返回其更新的值。

对于组合2，如果CPU 1对B的load看到CPU 2对B的存储之前的值，那么我们知道CPU 2对A的load将返回CPU 1对A的load相同的值，或者随后的值。

对于组合4，如果CPU 2对于B的load看到CPU 1对B的存储，那么我们知道CPU 2对A的load将返回CPU 1对A的load相同的值，或者随后的值。

对于组合8，如果CPU 2对于A的load看到CPU 1对于A的存储，那么我们知道CPU 1对于B的加载将返回CPU 2对A的加载同样的值，或者随后的值。

14.2.4.7 Semantics Sufficient to Implement Locking

锁的语义：

1．每一个CPU和硬件线程按编程顺序看到它自己的store和load操作。

a = 1;
b = 1 + a;
assert(b == 2);

在这种语义下，上述代码的断言不会被触发。

2．申请、释放锁操作，必须看起来是以单一全局顺序被执行。

spin_lock(&mylock);
if (p == NULL)
    p = kmalloc(sizeof(*p), GFP_KERNEL);
spin_unlock(&mylock);

如果该语义不成立，上述代码可能造成内存泄露。

3．如果一个特定变量在正在执行的临界区中，还没有被存储，那么随后在临界区中执行的加载操作，必须看到在最后一次临界区中，对它的存储。
也就是说在临界区实际包含了通用内存屏障的语义。

14.2.5 Review of Locking Implementations

void spin_lock(spinlock_t *lck)
{
    /* 如果当前的old_value==1，说明锁被其他线程占用
     * 那么循环读取锁的状态，直到其空闲。
     */
    while (atomic_xchg(&lck->a, 1) != 0)
        while (atomic_read(&lck->a) != 0)
            continue;
}
void spin_unlock(spinlock_t lck)
{
    smp_mb();
    atomic_set(&lck->a, 0);
}

以上逻辑的执行时序示例见上图所示。

下面继续解释14.2.4.7中锁的语义3：

这种情况下，成对的内存屏障足以恰当的维护两个临界区。CPU 2的atomic_xchg(&lck->a, 1)已经看到CPU 1 lck->a=0，因此CPU 2临界区的任何地方都必然看到CPU 1在之前临界区中所做的任何事情。

14.2.6 A Few Simple Rules

对内存屏障规则的一些简单的概括：

1．每一个 CPU按顺序看到它自己的内存访问。

2．如果一个单一共享变量被不同CPU加载、保存，那么被一个特定CPU看到的值的序列将与其他CPU看到的序列是一致的。并且，至少存在一个这样的序列：它包含了向这个变量存储的所有值，而每个CPU序列将与这个序列一致。

我的小问题：对这一点不是太理解， 例子见14.5。

以下3个概括的更多内容参照内存屏障成对使用的16种组合。

3．如果一个CPU按顺序存储变量A和B并且如果第二个CPU按顺序loadB和A，那么，如果第二个CPU对B的load得到了第一个CPU对它存储的值，那么第二个CPU对A的load也必然得到第一个CPU对它存储的值。

4．如果一个CPU在对B进行存储前，对A执行一个加载操作，并且，如果第二个CPU在对A进行存储前，执行一个对B的load，并且，如果第二个CPU对B的加载操作得到了第一个CPU对它的存储结果，那么第一个CPU对A的加载操作必然不会得到第二个CPU对它的存储。

5．如果一个CPU在对B进行存储前，进行一个对A的加载操作，并且，如果第二个CPU在对A进行存储前，对B进行存储，并且，如果第一个CPU对A的加载得到第二个CPU对它的存储结果，那么第一个CPU对B的存储必然发生在第二个CPU对B的存储之后，因此被第一个CPU保存的值被保留下来。

14.2.7 Abstract Memory Access Model

针对这个抽象模型，举两个例子不带屏障的例子，阐述输出结果的可能性

14.2.8 Device Operations

在设备操作中，假设一个有一些内部寄存器的以太网卡，它通过一个地址端口寄存器（A）和一个数据端口寄存器（D）访问。要读取内部寄存器5，可能会使用以下代码。

*A = 5;
x = *D;

可能会按照以下两种顺序之一来执行。

STORE *A = 5, x = LOAD *D
x = LOAD *D, STORE *A = 5

第二种情况几乎可以确定会出现故障，因为它在试图读取寄存器后才设置地址。

14.2.9 Guarantees

可以保证的行为

1. 在一个给定的CPU上，有依赖的内存访问将按序运行
2. 在特定CPU中，交叉的加载存储操作将在CPU内按顺序运行
3. 对单个变量的存储序列将向所有CPU呈现出一个单一的序列，虽然这个序列可能不能被代码所看见，实际上，在多次运行时，其顺序可能发生变化。

不能保证的行为

1. It must not be assumed that independent loads and stores will be issued in the order given.
2. It must be assumed that overlapping memory accesses may be merged or discarded.

14.2.10 What Are Memory Barriers?

14.2.10.1 Explicit Memory Barriers

1. Write (or store) memory barriers

一个写内存屏障提供这样的保证，从系统中的其他组件的角度来说，在屏障之前的写操作看起来将在屏障后的写操作之前发生

2. Data dependency barriers

数据依赖屏障是一种弱的读屏障形式。当两个load操作中，第二个依赖于第一个的结果时（如，第一个load得到第二个load所指向的地址），需要一个数据依赖屏障，以确保第二个load的目标地址将在第一个地址load之后被更新。

数据依赖屏障仅仅对相互依赖的加载进行排序。它对任何存储都没有效果，对相互独立的加载或者交叉加载也没有效果。

3. Read (or load) memory barriers

读屏障是一个数据依赖屏障，并加上如下保证，对于系统中其他组件的角度来说，所有在屏障之前的加载操作将在屏障之后的加载操作之前发生。

读内存屏障隐含数据依赖屏障，因此可以替代它。

4. General memory barriers

通用内存屏障保证，对于系统中其他组件的角度来说，屏障之前的加载、存储操作都将在屏障之后的加载、存储操作之前发生。

14.2.10.2 Implicit Memory Barriers

LOCK operations
一个LOCK操作充当了一个单方面屏障的角色。

它确保：对于系统中其他组件的角度来说，所有锁操作后面的内存操作看起来发生在锁操作之后。

LOCK操作之前的内存操作可能发生在它完成之后。

我的小问题:对这一点不太理解，在它完成之后是一个什么概念？难道说锁操作之前的内存操作可以塞到临界区里面吗?

LOCK操作几乎总是与 UNLOCK 操作配对。

UNLOCK Operations
UNLOCK 操作，UNLOCK 操作也充当了一个单方面屏障的角色。

确保对于系统中其他组件的角度来说，在UNLOCK操作之前的所有内存操作看起来发生在UNLOCK之前。

LOCK 和 UNLOCK 操作确保相互之间严格按顺序执行。

LOCK 和 UNLOCK 操作的用法通常可以避免再使用其他类型的内存屏障。

14.2.10.3 What May Not Be Assumed About Memory Barriers?

1．不能保证在内存屏障之前的内存访问将在内存屏障指令完成时完成；屏障仅仅用来在CPU的访问队列中做一个标记，表示相应类型的访问不能被穿越。

2．不能保证在一个CPU中执行一个内存屏障将直接影响另外一个CPU或者影响系统中其他硬件。其间接效果是第二个CPU所看到第一个CPU的内存访问顺序，但是请参照下一点。

3．不能保证一个CPU将看到第二个CPU的访问操作的正确顺序，即使第二个CPU使用一个内存屏障也是这样，除非第一个CPU也使用一个配对的内存屏障（参见14.2.10.6节“SMP 屏障对”）。

4．不能保证某些CPU片外硬件不会重排对内存的访问。CPU 缓存一致性机制将在CPU之间传播内存屏障的间接影响，但是可能不会按顺序执行这项操作。

14.2.10.4 Data Dependency Barriers

例1 初始状态：{A = 1, B = 2, C = 3,P = &A, Q = &C}:

执行序：

CPU 1            CPU 2
B = 4;
<write barrier>
P = &B;
                 Q = P;
                 D = *Q;

从直觉来看，结果有如下可能：

(Q == &A) implies (D == 1)
(Q == &B) implies (D == 4)

例如，预期的过程如下：

(Q == &B) -> B == 4 \
                     >
          -> D == B -> D == 4

实际可能出现：

(Q == &B) implies (D == 2)

Paul的解释如下：

注意这种极端违反直觉的情形在分离缓存机器中非常容易出现。例如，一个缓存带处理偶数编号的缓存行，另一个缓存带处理奇数编号的缓存行。指针P可能存储在奇数编号的缓存行，变量B存储在偶数编号的缓存行。那么，如果在读操作所在的CPU的缓存中，其偶数编号的缓存带异常繁忙，而奇数编号的缓存带空闲，就可以出现指针P的新值被看到（＆B），而变量B的旧值被看到（2）。

个人理解：CPU2中的两个load操作可能被打乱顺序，此时D = *P不成立。
所以也可能出现这种情况:

(Q == &B) implies (D == 3)

此时有：

(Q == &B) -> B == 4 
          -> D == *Q == C == 3

修改方法：

CPU 1            CPU 2
B = 4;
<write barrier>
P = &B;
                 Q = P;
                 <data dependency barrier>
                 D = *Q;

在CPU2的两个load操作之间添加数据依赖屏障，此时可以解决此问题。

例2 初始值{M[0] = 1, M[1] = 2, M[3] = 3, P = 0, Q = 3}:

CPU 1           CPU 2
M[1] = 4;
<write barrier>
P = 1;
                Q = P;
                <data dependency barrier>
                D = M[Q];

A number is read from memory and then used to calculate the index for an array access.

例3 数据依赖屏障对于Linux内核的RCU系统来说非常重要。

include/linux/rcupdateh中的rcu_dereference函数，允许RCU指针的当前目标被替换成一个新值，而不会使得要替换的目标看起来没有被全部初始化。

14.2.10.5 Control Dependencies

控制依赖需要一个完整的读内存屏障，而不是简单的数据依赖屏障来使它正常运行,如下所示：

q = &a;
if (p)
    q = &b;
<data dependency barrier>
x = *q;

这不会达到期望的效果，因为这实际上不是数据依赖，而是一个控制依赖。在该控制中，CPU在实际执行时，可能通过试图预取结果的方法来走捷径。这种情况下，实际需要如下代码。

q = &a;
if (p)
    q = &b;
<read barrier>
x = *q;

14.2.10.6 SMP Barrier Pairing

一个写屏障应当总是与数据依赖屏障或者读屏障配对，虽然通用屏障也是可以的。类似的，一个读屏障或者数据依赖屏障总是应当与至少一个写屏障配对使用，虽然，通用屏障也是可以的。 如下两种基本使用范例：

加入屏障后的数据更新流图如下所示：

14.2.10.7 Examples of Memory Barrier Pairings

本节使用的示意图值得学习。

例1

STORE A = 1
STORE B = 2
STORE C = 3
<write barrier>
STORE D = 4
STORE E = 5

对应时序说明图如下所示：

例2 初始条件：{B = 7, X = 9, Y = 8, C = &Y}:

CPU 1            CPU 2
A = 1;
B = 2;
<write barrier>
C = &B;          LOAD X
D = 4;           LOAD C (gets &B)
                 LOAD *C (reads B)

对应说明图如下所示：

此处存在load的乱序执行，可见此时的执行序是LOAD C; LOAD *C; LOAD X;。 由于缺乏data barrier在LOAD *C即LOAD B时读到的是old value。 所以在这个例子中，CPU2感知到的*C == 7。

为了解决这个问题，做如下修改：

CPU 1            CPU 2
A = 1;
B = 2;
<write barrier>
C = &B;          LOAD X
D = 4;           LOAD C (gets &B)
                 <data dependency barrier>
                 LOAD *C (reads B)

此时CPU的执行序如下所示：

可以看出，尽管此时在<data dependency barrier>之前的两条LOAD指令仍然被乱序执行，但是影响关键功能的LOAD B操作被放到了LOAD X以及LOAD C之后执行，这样就保证了在CPU1中存在写屏障的前提下，读到的B是新值2。

例3

读屏障仅仅对LOAD有效。
例如以下的CPU执行序：

CPU 1           CPU 2
A = 1;
<write barrier>
B = 2;
                LOAD B
                LOAD A

这个模型比较简单，做以下修改之后就可以使其按预期工作。

CPU 1           CPU 2
A = 1;
<write barrier>
B = 2;
                LOAD B
                <read barrier>
                LOAD A

14.2.10.8 Read Memory Barriers vs Load Speculation

举以下的例子来说明CPU的Load Speculation

CPU 1       CPU 2
            LOAD B
            DIVIDE
            DIVIDE
            LOAD A

如上图所示，CPU可能在执行DIVIDE操作完成之前执行LOAD A，这时候LOAD得到的值可能是old value。

所以，添加读屏障或数据屏障，如下所示：

CPU 1       CPU 2
            LOAD B
            DIVIDE
            DIVIDE
            <read barrier>
            LOAD A

此时CPU执行序可能如下所示：

这时冒险内存点没有变化，冒险获得的值将被使用。

而如果其他CPU对A进行了更新或者使它无效，那么冒险过程将被中止，A的值将被重新load，如下图所示：

14.2.11 Locking Constraints

此节内容与14.2.10.2有些许重复，不过在这里阐述的更详细。

锁原语包含了隐含的内存屏障。这些隐含的屏障提供了如下保障。

1．LOCK 操作保证

● LOCK之后的内存操作将在LOCK操作完成之后完成。

● LOCK操作之前的内存操作可能在LOCK操作完成之后完成。

我的小问题：这是否会带来问题？

2．UNLOCK 操作保证

● UNLOCK之前的内存操作将在UNLOCK 操作完成前完成。

● UNLOCK之后的操作可能在UNLOCK 操作完成前完成。

3．LOCK vs LOCK 保证

● All LOCK operations issued before another LOCK operation will be completed before that LOCK operation.

4．LOCK vs UNLOCK 保证

● All LOCK operations issued before an UNLOCK operation will be completed before the UNLOCK operation.

● All UNLOCK operations issued before a LOCK operation will be completed before the LOCK operation.

5．Failed conditional LOCK guarantee

几种 LOCK 变体操作可能失败，可能是由于不能立即获得锁，也可能是由于在等待锁可用时，接收到一个非阻塞信号或者发生异常。
失败的锁并不隐含任何类型的屏障。

14.2.12 Memory-Barrier Examples

14.2.12.1 Locking Examples

LOCK Followed by UNLOCK

如下例所示：*A和*B的赋值顺序无法保证，因为LOCK操作之前的内存操作可能在LOCK操作完成之后完成，UNLOCK之后的操作可能在UNLOCK 操作完成前完成。

*A = a;
LOCK
UNLOCK
*B = b;

实际操作执行序可能按如下顺序执行。

LOCK
*B = b;
*A = a;
UNLOCK

小问题14.13：什么样的LOCK-UNLOCK操作序列才能是一个全内存屏障？

答案：两个连续的LOCK-UNLOCK操作序列，或者（稍微有违常规），一个UNLOCK操作后面跟随一个LOCK操作。 如下所示：

*A = a;
UNLOCK
LOCK
*B = b;

下面给出证明： ● UNLOCK之前的内存操作将在UNLOCK 操作完成前完成。
所以保证了*A = a在UNLOCK前完成。
● LOCK之后的内存操作将在LOCK操作完成之后完成。
所以保证了*B = b在LOCK后完成。
● All UNLOCK operations issued before a LOCK operation will be completed before the LOCK operation.
所以保证了UNLOCK在LOCK之前完成
综上，*A = a在*B = b之前完成。

在Intel Itanium处理器中，会使用这些semi-permeable locking primitives来实现内存屏障的功能。

LOCK-Based Critical Sections 考虑下面的例子：

*A = a;
*B = b;
┏┳┓┏┳┓┏┳┓ LOCK ┏┳┓┏┳┓┏┳┓
*C = c;
*D = d;
┗┻┛┗┻┛┗┻┛ UNLOCK ┗┻┛┗┻┛┗┻┛
*E = e;
*F = f;

在实际执行中可能按照下列时序执行：

┏┳┓┏┳┓┏┳┓ LOCK ┏┳┓┏┳┓┏┳┓
*A = a; *F = f;
*E = e;
*C = c; *D = d;
*B = b;
┗┻┛┗┻┛┗┻┛ UNLOCK ┗┻┛┗┻┛┗┻┛

小问题14.15：假设大括号中的操作并发执行，表14.2中哪些行对变量“A”到“F”的赋值和LOCK/UNLOCK操作进行乱序是合法的。为什么是，为什么不是？

Ordering with Multiple Locks

包含多个锁的代码仍然看到包含这些锁的顺序约束，但是必须小心的一点是，记下哪一个约束来自于哪一个锁。

如下所示：

CPU 1       CPU 2
A = a;      E = e;
LOCK M;     LOCK Q;
B = b;      F = f;
C = c;      G = g;
UNLOCK M;   UNLOCK Q;
D = d;      H = h;

对于以上代码：
如14.2.11 Locking Constraints中所述，所有CPU必然看到以下的顺序约束。

1．LOCK M在 B、C和D之前。

2．UNLOCK M 在A、B和 C之后。

3．LOCK Q 在F、G和H之前。

4．UNLOCK Q在E、F和G之后。

Ordering with Multiple CPUs on One Lock

CPU 1       CPU 2
A = a;      E = e;
LOCK M;     LOCK M;
B = b;      F = f;
C = c;      G = g;
UNLOCK M;   UNLOCK M;
D = d;      H = h;

在这种情况下，要么CPU 1在CPU 2前申请到M，要么相反。在第一种情况下，对A、B、C的赋值，必然在对F、G、H的赋值之前。另一方面，如果CPU2先申请到锁，那么对E、F、G的赋值必然在对B、C、D的赋值之前。

这个例子说明了14.2.11锁的约束中的第4点。

All LOCK operations issued before an UNLOCK operation will be completed before the UNLOCK operation.

14.2.13 The Effects of the CPU Cache

内存屏障可以被认为起到图14.17中垂直线的作用，它确保CPU按适当的顺序向内存展示其值，就像确保它按适当顺序看到其他CPU所做的变化一样。

14.2.13.1 Cache Coherency

虽然缓存一致性协议保证特定CPU按顺序看到自己对内存的访问，并且所有CPU对包含在单个缓存行的单个变量的修改顺序会达成一致，但是不保证对不同变量的修改能够按照相同顺序被其他所有CPU看到，虽然某些计算机系统做出了这样的保证，但是可移植软件不能依赖它们。

以下的分离cache模型在理解一些违背直觉的场景下很有益。

要明白为什么乱序可能发生，考虑如图14.18所示的2-CPU系统，在这样的系统中，每一个CPU拥有一个分离的缓存，这个系统有以下属性。

1．奇数编号的缓存行可能在缓存A、C中，在内存中，或者兼而有之。

2．偶数编号的缓存行可能在缓存B、D中，在内存中，或者兼而有之。

3．当CPU核正在向它的缓存获取数据，它的其他缓存不必处于静止状态。其他缓存可以响应“使无效”请求，回写脏缓存行，处理CPU内存访问队列中的元素，或者其他。

4．每一个缓存都有各自的操作队列，它些队列被缓存用来维护所请求的一致性和顺序属性。

5．这些队列不一定在这些队列元素所影响的缓存行元素进行load和存储操作时进行刷新。
比如Invalidate Queues，与store buffer不同，CPU无法在load操作时扫描Invalidate Queues。

简而言之，如果缓存A忙，但是缓存行B空闲，那么与CPU 2向偶数行store相比，CPU1向奇数编号的缓存行store会被延迟。在不那么极端的情况下，CPU 2就可以看到CPU1的乱序操作。

14.2.14 Where Are Memory Barriers Needed?

仅仅在两个CPU之间或者CPU与设备之间存在需要交互的可能性时，才需要内存屏障。任何代码只要能够保证没有这样的交互，这样代码就不必使用内存屏障。

注意，这是最小的保证。正如附录C所讨论的那样，不同体系结构给出了更多保证。但是，不能将代码设计来只运行在特定的体系中。

像锁原语、原子数据结构维护原语以及遍历这些，实现原子操作的原语通常在它们的定义中包含了必要的内存屏障。

但是，有一些例外，例如在Linux内核中的atomic_inc（）。因此请确保查阅了文档，并且，如果可能的话，查阅它在软件环境中实际的实现。

最后一个忠告，使用原始的内存屏障原语应当是不得已的选择。使用已经处理了内存屏障的已有原语，几乎总是更好的选择。

14.3 Non-Blocking Synchronization 14.3.1 Simple NBS 14.3.2 NBS Discussion