原子操作、写回策略、缓存一致性问题、内存序详解

什么是原子操作

多线程环境下确保共享变量的操作在执行时不会被干扰，从而避免竞态

什么是原子变量

原子变量是多线程编程中用于实现无锁并发操作的重要工具，它可以保证对变量的操作是原子性的，即在同一时刻只有一个线程能够对其进行操作，避免了多线程环境下的数据竞争和不一致问题。

原子变量的基本操作

• 读操作 : load

  load() 用于从原子变量中读取值，它是原子性的，不会被其他线程的操作打断。

std::atomic<int> i(10);
int value = i.load(); // 原子读取操作

• 写入操作： store

  store() 方法或直接赋值来写入原子变量的值。

std::atomic<int> j(0);
j.store(42); //j赋值为42
j = 42;//也可以直接赋值

• 比较并交换操作（Compare-And-Swap CAS）
  CAS允许在不使用传统锁（如std::mutex）的情况下，对共享数据进行线程安全的更新。
  原子变量值和目标值相等，则将原子变量的值更新为新值，并返回true。
  原子变量值和目标值不相等，则不进行更新操作，直接返回false。

std::atomic<int> atomicValue(10);//原子变量值

void CAS_Example() {
    int expected = 10;//期望值
    int newVal = 20;  //原子变量和期望值相等后更新的值
    bool success = atomicValue.compare_exchange_strong(expected, newVal);
    if (success) {
        std::cout << "Value was updated successfully." << std::endl;
    } else {
        std::cout << "Value was not updated. Expected value was: " << expected << std::endl;
    }
}

C++里CAS有两个函数
compare_exchange_weak 和 compare_exchange_strong

区别：compare_exchange_weak 可能会在原子变量的当前值等于期望值时仍然返回 false，即出现伪失败。这是因为在某些硬件平台上，实现 CAS 操作可能会受到一些干扰，例如缓存一致性问题。由于可能出现伪失败，compare_exchange_weak 在某些平台上的性能可能更好，尤其是在循环中使用时，因为它可以避免一些额外的开销。

原子性

原子性是指一个操作在执行过程中不可被中断，要么这个操作完全执行完毕，要么完全不执行，不会出现执行到一半被其他线程干扰的情况。从其他线程的视角来看，这个操作是 “瞬间完成” 的，不存在中间状态。

怎么保证原子性

保证操作指令不被打断

• 单处理器单核环境下
  1、屏蔽中断
  2、硬件层自旋锁保障

• 多处理器或多核环境下
  1、跟单处理器一样保证操作指令不被打断
  2、避免其他核心操作相关内存空间：lock指令，阻止其他核心对相关内存的访问

缓存命中

缓存命中是指在计算机系统中，当处理器或其他组件需要访问数据时，所需的数据恰好已经存在于缓存中，从而可以直接从缓存中快速获取数据，而无需从速度相对较慢的主存储器或其他外部存储设备中读取。这大大提高了数据访问的速度和系统的整体性能。

为什么要有缓存

减少 I/O 操作、为了解决CPU运算速度于内存访问速度的不匹配问题

写回（write-back）策略

写

读

缓存一致性问题

解决缓存一致性问题

写传播 总线嗅探机制

通过总线嗅探策略将读写请求通过总线广播给所有核心，核心根据本地状态进行响应

照成的问题

大量无关数据在总线上传播，带来总线带宽压力

解决 ： MESI一致性协议

缓存里的数据都在这四个状态里进行转移和切换

写后锁住M和E状态，避免其他核心访问相关内存

• Modified （已修改）
  表示某数据块已修改但是没有同步到主存里
  • 当处理器需要将修改后的数据写回主存时，会发起一个 “写回（Write - Back）” 操作，将数据写回到主存中。之后，根据是否有其他处理器请求该缓存行数据，状态会发生不同变化。如果没有其他处理器请求，缓存行状态变为独占（Exclusive）；如果有其他处理器请求，状态变为共享（Shared）。
  • 其他处理器读操作
    当收到其他处理器对该缓存行的读请求时，本处理器会先将修改后的数据写回主存，然后将数据提供给请求的处理器，同时将自己的缓存行状态从修改变为共享（Shared）。
  • 其他处理器写操作
    如果收到其他处理器对该缓存行的写操作请求，本处理器会先将修改后的数据写回主存，然后将自己的缓存行状态变为无效（Invalid），因为其他处理器将对该数据进行修改。
• Exclusive（独占）
  表示某数据只在某一个核心里，且此时该数据在主存和缓存里的数据一致
  • 本处理器写操作
    当处理器对处于独占状态的缓存行进行写操作时，缓存行状态会从独占变为修改（Modified），因为此时数据被修改，与主存中的数据不一致。
  • 其他处理器读操作
    如果其他处理器发起对该缓存行的读请求，本处理器会将数据提供给其他处理器，同时将自己的缓存行状态从独占变为共享（Shared），因为此时多个处理器都拥有了该缓存行的副本。
• Shared（共享）
  表示某数据在多个核心里加载，且此时该数据在主存和缓存里的数据一致
  • 当处理器想要对处于共享状态的缓存行进行写操作时，它会向总线发送一个使无效(Invalidate消息，通知其他拥有该缓存行副本的处理器将其对应的缓存行状态变为无效。一旦收到所有其他处理器的确认消息，该处理器会将自己的缓存行状态从共享变为修改（Modified），然后执行写操作。
  • 其他处理器写操作
    如果收到其他处理器对该缓存行的写操作广播（通常是其他处理器发送的 “使无效” 消息），本处理器会将自己缓存中对应的缓存行状态变为无效（Invalid）。
  • 其他处理器读操作
    当收到其他处理器对该缓存行的读操作时，本处理器的缓存行状态保持共享（Shared）不变，因为多个处理器可以同时共享相同的数据副本。
• Invalid（已失效）
  某数据在核心里已经失效，不是最新数据
  • 当处理器需要访问处于无效状态的缓存行中的数据时，会发起一个读请求。如果其他处理器的缓存中没有该数据（即主存数据是最新的），则从主存中读取数据到该处理器的缓存行，并将其状态设置为独占（Exclusive）。
    若其他处理器的缓存中有该数据且处于共享状态，该处理器会从主存或其他缓存中获取数据，然后将该缓存行状态设置为共享（Shared）。
  • 收到写操作广播
    当处于无效状态的缓存行收到其他处理器对同一缓存行的写操作广播时，它会继续保持无效（Invalid)状态，因为本身数据就是无效的，无需做额外处理。

事件状态机

内存序

内存序规定了处理器对内存操作（读和写）的执行顺序以及这些操作在不同处理器或线程之间的可见性顺序。在单线程程序中，通常按照代码的顺序来执行内存操作，但在多线程环境下，由于处理器的优化、缓存机制等因素，内存操作的实际执行顺序和可见性可能会与代码顺序不同，内存序就是用来控制和规范这种行为的。

int i;
int j;
i = 0;
j = 0;
//在编译器看来i = 0和j = 0;的赋值是毫不相关的两句，
//所以某些情况下两句的顺序可能会被由于编译器的优化而导致被交换
//而在程序员眼里有时候可能有要先初始化i = 0以后才能去进行 j = 0的需求

为什么有内存序

• 保证数据一致性：在多线程环境中，多个线程可能同时访问和修改共享数据。通过合理地设置内存序，可以确保每个线程都能看到正确的数据状态，避免出现数据不一致的情况。
• 避免竞态条件：竞态条件是指多个线程访问共享资源时，由于执行顺序的不确定性导致程序出现不可预测的结果。内存序可以通过规定操作的执行顺序和可见性，减少竞态条件的发生，使程序的行为更加可预测。
• 提高程序性能：虽然内存序主要是为了保证正确性，但在某些情况下，也可以通过合理地选择内存序来提高程序的性能。例如，在一些不需要严格顺序一致性的场景下，使用较宽松的内存序模型可以允许处理器进行更多的优化，提高程序的执行效率。

六种内存序

• memory_order_relaxed
  1：没有同步性，读到的可能不是一个最新的值
  2：不干预编译器或CPU的优化
  3：既可以用到读操作，也可以用于写操作

这里x是一个原子操作，在写入x操作后的 读出b 操作可能会被优化到前面，在写入x操作前的写入c操作也可能被优化到后面

• memory_order_release
  1：有同步性
  2：指导优化，当前线程的任何前面的读写操作都不能优化到该原子操作后面
  说明该原子操作基于前面的步骤，所以前面的操作不能放到后面去
  3：只用于写操作

• memory_order_acqurie
  1：只用于写操作
  2：当前线程的任何后面的读写操作都不能优化到该原子操作前面
  说明该原子操作后面的步骤基于该原子操作，所以前后面的操作不能放到前面去
  3：有同步性
  

• memory_order_acq_rel
  1：即涉及读又涉及写
  2：不可优化，前面步骤不可优化到后面，后面步骤也不可优化到前面

• memory_order_seq_cst
  1：同步性
  2：不可优化，前面步骤不可优化到后面，后面步骤也不可优化到前面