一、CPU缓存结构
1.1 CPU的多级缓存
因为CPU的计算速度非常快，但内存的访问速度相对较慢。因此，如果CPU每次都要从内存读取数据，会造成大量的等待时间，降低整体性能。
通过引入多级缓存，可以在CPU和内存之间建立数据缓存层，将最常用的数据暂时保存在靠近CPU的高速缓存（CPU Cache）中，以供CPU快速访问。不同级别的缓存容量和访问速度各不相同，一般来说，L1缓存最小、速度最快，L2缓存次之，L3缓存最大但速度相对较慢。并且 L1和L2 是 CPU 私有，L3 是所有 CPU 共享。
多级缓存的设计可以实现更高的命中率，即CPU能够更频繁地从高速缓存中获取需要的数据，减少对内存的访问次数，从而提高整体性能。
1.2 Cache Line
CPU 从内存中读取数据到 CPU Cache 的过程中，是一小块一小块来读取数据的。这样一小块一小块的数据，在 CPU Cache 里面，我们把它叫作缓存行(Cache Line)。即，Cache Line是CPU缓存中的最小可读写单元，用于存储从主存中读取的数据块。日常使用的 Intel 服务器或者 PC 里，Cache Line 的大小通常是 64 字节。
当CPU访问内存时，如果所需数据在缓存中已经存在于一个Cache Line中，那么CPU可以直接从缓存中读取数据，而无需访问主存，从而提高了数据传输的速度。
- 标志位（flag）：用于指示Cache Line当前是否有效。当一个Cache Line中存储的数据被更新或替换时，标志位会被清除，表示该Cache Line不再有效。（存MESI 的状态）
- 标记（tag）：用于标识数据区域中存储的数据块是来自哪个主存地址。当CPU需要读取或写入特定地址的数据时，它会将该地址的一部分作为标记，并与Cache Line中存储的标记进行比较，以确定是否命中缓存。
- 数据区域（data）：用于存储从主存中读取的数据块。
二、写回策略
写回策略（Write Back）是一种用于缓存管理的写入更新方式。当数据被修改时，写回策略将更新后的数据首先写入缓存，而不立即写入主内存。
具体来说，当缓存中的某个数据被修改时，写回策略将在修改时更新缓存中的对应数据，并将其标记为脏数据，表示该数据已经被修改过。然后，当需要替换这个被修改的数据时，才将更新后的数据写回主内存。
- 当请求是写请求时
1）若命中，直接将新数据写入缓存，并且标记为脏数据dirty（缓存中修改过但尚未写回到更高级别缓存或主内存中的数据）。注意此时不会写入内存。
2）若未命中，分配一个缓存块Cache Line，判断当前缓存块是不是脏数据。如果是，先将缓存块的数据写回内存中，再将新数据写入缓存块。如果不是脏数据，直接从内存中读到缓存块中（建立内存块与缓存块的索引关系），再将新数据写入缓存块，并标记为dirty。
- 当请求是读请求时
1）若命中，直接返回其数据；
2）若未命中时，分配一个缓存块，判断当前缓存块是不是脏数据。如果是，先将缓存块的数据写回下一级存储中，再从内存读取新数据到缓存块中。如果不是脏数据，直接从内存中读到缓存块中，修改dirty位为clean（未被修改）。最后返回数据。
这种策略的主要优势在于减少了向主内存写入数据的次数。相比于每次数据修改都直接写入主内存（写直达，Write Through），写回策略可以将多次对同一块数据的修改累积起来，一次性地写回主内存，减少了对主内存的访问，提高了效率。
三、缓存一致性问题及解决方案
3.1 缓存一致性问题
上面介绍的写回策略，延迟数据写入主内存的时机，可能会带来数据一致性的问题。因为CPU是多核的，在数据被修改后，尚未写回主内存之前，如果发生了缓存替换或其他操作，主内存上的数据可能是过期的。
比如在多处理器系统下，核心A和核心A共享一块主存。假如核心A从主存中读取到 x，并对其加 1 ，此时还没有写回主存。与此同时，核心B 也从主存中读取 x ，并加 1 。但是它们都不知道对方的存在，也不可以读取对方的缓存。若这时都将 x 写回主存，那此时 x 的值就少了 1 ，出现了数据不一致的问题。
3.2 解决方案
3.2.1 总线嗅探
当一个处理器执行一个写操作时，它会在总线上广播一个写请求，并在总线上传输要写入的数据。其他处理器的总线嗅探器会监听到该写请求，并检查请求中的地址。如果某个处理器的缓存中包含了该地址的数据块，总线嗅探器就会将该缓存块标记为“无效”，表示该数据已经过期，需要从主内存或其他缓存中重新获取最新的数据。
同样地，当一个处理器执行一个读操作时，总线嗅探器也会监听到该读请求，并检查请求中的地址。如果某个处理器的缓存中包含了该地址的数据块，总线嗅探器会检查该数据块是否为“脏”，即是否被修改过。如果是脏数据，则总线嗅探器负责将该数据写回到主内存或其他缓存中，以保证数据的一致性。
通过总线嗅探技术，处理器能够感知其他处理器对共享数据的读写操作，并及时更新自己的缓存，以确保所有处理器都能访问到最新的共享数据。
3.2.2 事务的串行化
举个例子，假设有两个事务 T1 和 T2，我们希望它们并发执行的过程如下：
T1：读取数据 A，修改数据 A（A = 10 ~> A = 20）
T2：读取数据 A，修改数据 A（A = 20 ~> A = 30）
但是如果这两个事务并发执行，并未经过任何的串行化控制，可能出现以下情况：
T1 先执行读取操作，读取到 A 的值为 10；
T2 在 T1 执行读取操作后执行读取操作，读取到 A 的值也为 10；
T1 执行修改操作，将 A 的值修改为 20；
T2 也执行修改操作，将 A 的值修改为 30；
在这种情况下，最终 A 的值是 30，而不是按照顺序执行时的 20。
然而，如果采用串行化控制，将 T1 和 T2 串行化执行，保证它们不会交叉执行，那么最终的结果将与串行执行的结果一致。具体的串行化执行过程如下：
T1 先执行读取操作，读取到 A 的值为 10；
T1 执行修改操作，将 A 的值修改为 20；
T2 在 T1 执行完毕后执行读取操作，读取到 A 的值为 20；
T2 执行修改操作，将 A 的值修改为 30；
采用串行化控制后，最终 A 的值为 30，与串行执行的结果一致。
可以通过对线程T1加锁，保证T1执行时候，T2不会产生干扰，达到串行效果。
3.2.3 MESI
通过事务的串行化，每当有核心修改数据，都需要广播给其他的核心。但是，并不是所有的核心都与这个数据相关。这样就会浪费带宽，代价比较大。接下来引入MESI来解决这个问题。
MESI是一种缓存一致性协议，用于解决多核处理器中的缓存一致性问题。CPU 中每个缓存行（caceh line）都使用MESI进行标记，MESI是四种状态的缩写，分别代表了缓存行的不同状态：修改（Modified）、独占（Exclusive）、共享（Shared）和无效（Invalid）。
1）修改（Modified）：当某个核心独占地拥有一块缓存行的数据时，如果该核心对缓存行进行了修改，那么该缓存行的状态为修改状态。同时，该核心对缓存行所做的修改还没有写回到主存中。
2）独占（Exclusive）：如果某个核心独占地拥有一块缓存行的数据，并且该数据未被修改，那么该缓存行的状态为独占状态。此时，其他核心不能缓存该缓存行中的数据。
3）共享（Shared）：当多个核心同时缓存同一块缓存行的数据时，该缓存行的状态为共享状态。多个核心可以同时读取该数据，但不能进行写操作。
4）无效（Invalid）：如果某个核心的缓存中的数据与主存中的数据不一致，或者某个核心将共享缓存行标记为无效状态，那么该缓存行的状态就会变为无效状态。此时，其他核心不能使用该缓存行中的数据，必须从主存中获取最新的数据。
四、原子操作
4.1 什么是原子操作
原子操作是指在执行过程中不会被中断的操作，要么全部执行成功，要么全部不执行，不会出现部分执行的情况。原子操作可以看作是不可分割的单元， 运行期间不会有任何的上下文切换。
1）在单核处理器上，原子操作可以通过禁止中断的方式来保证不被中断。当一个线程或进程执行原子操作时，可以通过禁用中断来确保原子性。在禁用中断期间，其他线程或进程无法打断当前线程或进程的执行，从而保证原子操作的完整性。
2）在多核处理器上，原子操作的实现需要使用一些特殊的硬件机制或同步原语来保证原子性。以下是两种常见的方法：
1、使用硬件原子指令：现代多核处理器通常支持硬件原子指令，例如CAS（Compare-And-Swap）指令。这样的指令允许对共享内存进行原子读取和写入操作。CAS指令会比较内存中的值与期望值，如果相等则执行写入操作，否则不执行。通过使用这样的原子指令，可以在多核处理器上实现原子操作。
2、使用锁和同步原语：多核处理器上的原子操作可以通过锁来实现互斥访问。以往0x86，是直接锁总线，避免所有内存的访问。现在是只需要锁住相关的内存，比较其他核心对这块内存的访问。
4.2 c++ 标准库的原子类型
4.2.1 atomic<T>
atomic<T> 是 C++ 中的原子类型模板，用于实现原子操作。它提供了一种线程安全的方式来对特定类型的数据进行读取和写入，以及执行其他常见的原子操作，如增加（增量）和交换等。
atomic<T> 提供了以下常用的成员函数和操作符：
1）加载和存储操作：通过 load() 和 store() 方法可以实现从原子对象中加载值或将值存储到原子对象中。
2）交换和比较交换操作：使用 exchange() 可以原子地将新值存储到原子对象中，并返回之前的值；使用 compare_exchange_strong() 或 compare_exchange_weak() 可以原子地比较并交换值。
3）增减操作：使用 fetch_add() 和 fetch_sub() 可以原子地增加或减少原子对象的值，并返回之前的值。
4）访问操作：除了上述操作，还可以使用 operator++、operator–、operator+=、operator-= 等操作符进行原子操作。
4.2.2 is_lock_free()
用于检查原子类型是否是无锁（lock-free）的。它返回一个布尔值，指示原子类型是否可以在特定硬件平台上以无锁方式进行操作。
bool is_lock_free() const noexcept;
如果 is_lock_free() 返回 true，表示该原子类型可以在特定硬件平台上以无锁方式进行操作；如果返回 false，则表示该原子类型无法以无锁方式进行操作，需要使用锁或其他同步机制。
4.2.3 load()
获取原子对象中的当前值，并返回该值。它会保证在多线程环境下对数据的读取是原子的，即不会受到其他线程同时修改的干扰，保证了数据的一致性。
load(memory_order order = memory_order_seq_cst) const noexcept;
参数 order 是一个可选参数，用于指定内存序（memory order）的类型，默认为 memory_order_seq_cst。内存序定义了原子操作的时序关系，决定了在多线程环境下对数据访问的可见性和有序性。
4.2.4 store()
用于原子地存储（写入）值到原子对象中。它可以将给定的值存储到原子对象中，并保证在多线程环境下的可见性和原子性。
void store(T value, memory_order order = memory_order_seq_cst) noexcept;
参数 value 是要存储到原子对象中的值，参数 order 是一个可选参数，用于指定内存序（memory order）的类型，默认为 memory_order_seq_cst。
4.2.5 exchange()
用于原子地交换原子对象中的值，并返回先前的值。它可以将给定的值与原子对象的当前值进行交换，并保证在多线程环境下的可见性和原子性。
exchange(T desired, memory_order order = memory_order_seq_cst) noexcept;
参数 desired 是要与原子对象进行交换的值，参数 order 是一个可选参数，用于指定内存序（memory order）的类型，默认为 memory_order_seq_cst。
4.2.6 compare_exchange_weak()
用于原子地比较并交换原子对象的值。它可以比较原子对象的当前值与期望值，并在匹配时将新值存储到原子对象中。
bool compare_exchange_weak(T& expected, T desired, memory_order success, memory_order failure) noexcept;
参数 expected 是对原子对象进行比较的期望值，并且在返回时被更新为原子对象的当前值。参数 desired 是要存储到原子对象中的新值。参数 success 和 failure 分别指定了成功和失败情况下的内存序（memory order）类型，默认为 memory_order_seq_cst。
返回值是一个 bool 类型，表示是否成功执行了比较和交换操作。如果比较的值与期望值相等，则交换成功，返回 true，否则交换失败，返回 false。
weak版本的CAS允许偶然出乎意料的返回（比如在字段值和期待值一样的时候却返回了false），不过在一些循环算法中，这是可以接受的。通常它比起strong有更高的性能。
举个例子
a.compare_exchange_weak(b,c)其中a是当前值，b期望值，c新值
a==b时：函数返回真，并把c赋值给a
a!=b时：函数返回假，并把a复制给b
#include <iostream> // std::cout #include <atomic> // std::atomic, std::atomic_flag, ATOMIC_FLAG_INIT int main() //相等案例 { std::atomic<int> a; a.store(10); int b=10; //a==b int c=20; std::cout<<"a:"<<a<<std::endl; while(!a.compare_exchange_weak(b,c)) { b=10; c=20; } std::cout<<"a true:"<<a.load()<<std::endl; std::cout<<"a:"<<a<<" b:"<<b<<" c:"<<c<<std::endl; return 0; } a:10 a true:20 a:20 b:10 c:20
int main() //不等案例 { std::atomic<int> a; a.store(10); int b=100; //a!=b int c=20; std::cout<<"a:"<<a<<std::endl; while( !a.compare_exchange_weak(b,c)) { b=100; c=20; } std::cout<<"a true:"<<a.load()<<std::endl; std::cout<<"a:"<<a<<" b:"<<b<<" c:"<<c<<std::endl; return 0; } a:10 a:10 b:10 c:20
4.2.7 compare_exchange_strong()
强化版的CAS，如果需要保证严格的原子性，则应该使用 compare_exchange_strong 函数。其他根weak版一样。
compare_exchange_strong ------------ 会阻塞cpu, 会慢一些
compare_exchange_weak --------------- 有可能失败，性能高, 可以加while直到它成功
