一.应用场景展示——多线程计数
1.全局原子操作计数的数据流图
核心问题就是不同CPU如何在同一时刻看到同样的全局变量值。
2.每线程自增计数的数据流图
二.cache原理和实现
1. cache geometry
size : 包含的cache line个数
way ：每set相连way数
2. cache核心是一个硬件hash表
举例说明一下：
该cache是一个2路(2 ways)16组(16 sets)相连，大小为16 * 2 = 32 cache line的cache。
对应的硬件hash表如下：
三.数据同步电信号是什么？
MESI —— 内存缓存一致性性协议
注意，MESI协议只能保证并发编程中的可见性，并未解决原子性和有序性的问题，所以只靠MESI协议是无法完全解决多线程中的所有问题。
1. cache line的四种状态
M : "modified"E : "exclusive"S : "shared"I : "invalid"
MESI 存在“modified”，“exclusive”，“shared”和“invalid”四种状态，协议可以在一个指定的缓存行中应用这四种状态。因此，协议在每一个缓存行中维护一个两位的状态标记，这个标记附着在缓存行的物理地址和数据后面。
（1）modify状态
（2）exclusive状态
（3）shared状态
（4）invalid状态
2. MESI的消息类型
MESI的六种消息大致分为两类：请求消息和响应消息
cpu接收响应消息的顺序决定了->其他cpu感知到的当前线程的执行顺序
（1）read：（请求消息）
cpu发送read消息请求需要读取数据的物理地址。
（2）read response：（响应消息）
"read response"消息包含先前“read”消息请求的数据。此“read response”消息可能由内存或其他缓存之一提供。
（3）invalidate：（请求消息）
“invalidate”消息包含要作废的缓存行的物理地址。所有其他缓存都必须从其缓存中删除相应的数据并进行响应。
（4）invalidate acknowledge：（响应消息）
接收到“invalidate”消息的CPU必须在从其缓存中删除指定的数据后以“invalidate acknowledge”消息响应。
（5）read invalidate：（请求消息）
“read invalidate”消息包含要读取的缓存行的物理地址，同时指示其他缓存删除数据。“read invalidate”消息需要“read response”和一组“invalidate acknowledge”消息作为应答。
（6）writeback
“writeback”消息包含要写回内存的地址和数据（也可能是沿途“窥探”到其他cpu的缓存中）。此消息允许缓存根据需要弹出处于“修改”状态的行，以便为其他数据腾出空间。
3. cache line在四种状态之间的转换
(1) M和E状态转换
Transition (a)：缓存行被写回到物理内存，但是CPU仍然将它保留在缓存中，并在以后修改它。这个转换需要一个“写回”消息。Transition (b)：CPU将数据写到缓存行，该缓存行目前处于排它访问。不需要发送或者接收任何消息。(2) M和I状态转换
Transition (c)：CPU收到一个“读使无效”消息，相应的缓存行已经被修改。CPU必须使无效本地副本，然后响应“读响应”和 “使无效应答”消息，同时发送数据给请求的CPU(注意，这个数据是M状态的cache数据)，并标示它的本地副本不再有效(本地副本已经通过读响应发送给请求的CPU了)。Transition (d)：CPU进行一个原子读—修改—写操作，相应的数据没有在它的缓存中。它发送一个“读使无效”消息，通过“读响应”消息接收数据。一旦它接收到一个完整的“使无效应答”响应集合，CPU就完成此转换。(3) M和S状态转换
Transition (e)：CPU进行一个原子读—修改—写操作，相应的数据在缓存中是只读的。它必须发送一个“使无效”消息，并等待“使无效应答”响应集合以完成此转换。Transition (f)：其他某些CPU读取缓存行，其数据由本CPU提供，本CPU包含一个只读副本。数据只读的原因，可能是由于数据已经回写到内存中。这个转换开始于接收到一个“读”消息，最终本CPU响应了一个“读响应” 消息。(4) E和S状态转换
Transition (g)：其他CPU读取数据，并且数据是从本CPU的缓存或者物理内存中提供的。无论哪种情况，本CPU都会保留一个只读副本。这个事务开始于接收到一个“读”消息，最终本CPU响应一个“读响应”消息。Transition (h)：当前CPU很快将要写入一些数据到缓存行，于是发送一个“使无效”消息。直到它接收到所有“使无效应答”消息后，CPU才完成转换。可选的，所有其他CPU通过“写回”消息将缓存行的数据换出（可能是为其他缓存行腾出空间）。这样，当前CPU就是最后一个缓存该数据的CPU。(5) E和I状态转换
Transition (i)：其他某些CPU进行了一个原子读—修改—写操作，相应的缓存行仅仅被本CPU持有。本CPU将缓存行变成无效状态。这个转换开始于接收到“读使无效”消息，最终本CPU响应一个“读响应”消息以及一个“使无效应答”消息。Transition (j)：本CPU保存一个数据到缓存行，但是数据还没有在它的缓存行中。因此发送一个“读使无效”消息。直到它接收到“读响应”消息以及所有“使无效应答”消息后，才完成事务。缓存行可能会很快转换到“修改”状态，这是在存储完成后由Transition (b)完成的。(6) S和I状态转换
Transition (k)：本CPU装载一个数据，但是数据还没有在缓存行中。CPU发送一个“读”消息，当它接收到相应的“读响应”消息后完成转换。Transition (l)：其他CPU存储一个数据到缓存行，但是该缓存行处于只读状态（因为其他CPU也持有该缓存行）。这个转换开始于接收到一个“使无效”消息，当前CPU最终响应一个“使无效应答”消息。4. 一个简单示例
（1）.MESI协议只对汇编指令中执行加锁操作的变量有效，表现到C/C++中为使用voliate关键字定义变量或使用加锁操作
（2）.对于汇编指令中执行加锁操作的变量，MESI协议在以下两种情况中也会失效：
a、CPU不支持缓存一致性协议。
b、该变量超过一个缓存行的大小，缓存一致性协议是针对单个缓存行进行加锁，此时，缓存一致性协议无法再对该变量进行加锁，只能改用总线加锁的方式。
MESI工作原理实例展示：
（1）、CPU1从内存中将变量a加载到缓存中，并将变量a的状态改为E（独享），并通过总线嗅探机制对内存中变量a的操作进行嗅探
（2）、此时，CPU2读取变量a，总线嗅探机制会将CPU1中的变量a的状态置为S（共享），并将变量a加载到CPU2的缓存中，状态为S
(3)、CPU1对变量a进行修改操作，此时CPU1中的变量a会被置为M（修改）状态，而CPU2中的变量a会被通知，改为I（无效）状态，此时CPU2中的变量a做的任何修改都不会被写回内存中（高并发情况下可能出现两个CPU同时修改变量a，并同时向总线发出将各自的缓存行更改为M状态的情况，此时总线会采用相应的裁决机制进行裁决，将其中一个置为M状态，另一个置为I状态，且I状态的缓存行修改无效）
(4)、CPU1将修改后的数据写回内存，并将变量a置为E（独占）状态
(5)、此时，CPU2通过总线嗅探机制得知变量a已被修改，会重新去内存中加载变量a，同时CPU1和CPU2中的变量a都改为S状态
在上述过程第3步中，CPU2的变量a被置为I（无效）状态后，只是保证变量a的修改不会被写回内存，但CPU2有可能会在CPU1将变量a置为E（独占）状态之前重新读取内存中的变量a，这个取决于汇编指令是否要求CPU2重新加载内存。
