并发控制相关

对锁的理解

  • 资源的并发保护
  • 保证临界区的顺序（内存屏障/CPU屏障）
  • 当锁持有时间占比在90%以上时，不如让单线程去访问这个资源

并发控制的方法

  • 互斥锁
  • 读写锁
  • CAS
  • 原子量
  • RCU
  • 多版本控制
  • 行锁

读写锁

读写锁适合资源写少读多（多线程并发读比例高）的场景，而且linux的读写锁实现效率不高（单个写线程，20个读线程的情况下，如果没有很重的读开销，则使用读写锁反而比使用mutex要慢，当然如果读操作很耗时，则使用读写锁会更划算）。

linux下的pthread mutex实现，如果没有碰到竞争是不会陷入内核的。

RCU

RCU在内核中应用比较多，实现了读写的并行，在Writer端增加一定负担，使得Reader端几乎可以Zero-overhead，特别适用用读操作远远大与写操作的场景，或者写的优先级不如读高的场景。

MVCC

MVCC让读不影响写，但读会读到旧数据。

场景决定应用，我们需要根据资源的读写比例来选择合适的并发控制方法。

CAS

对无锁的理解

  • 基本上一两次自旋尝试就能成功的情况下使用CAS效率比锁的效率高
  • 使用一般锁会线程切换，如果极短时间就能拿锁，则线程切换的成本太高，反之亦然
  • 通过减少阻塞和等待，来改进并发性和可扩展性
  • 锁与锁之间的任务比较简单的时候，无锁编程更可行
  • CAS会增加竞争性，这点会影响性能，因此需要测试来确认
  • 当临界区较短或者一个core上只有一个线程时，和mutex相比，使用spin lock性能较佳，因为避免了上下文切换。
  • 事务内存这种新技术扩展了CAS的应用范围
  • 使用无锁编程后，编译器乱序和指令乱序都遵循原则：内存执行顺序的基本原则–绝不修改单程序的行为，在多核情况下，则需要注意到乱序的存在。

行锁

行锁是解决一个大数据下的场景问题：总数据量很大，但同一时刻并发操作的数据量相对是很少的，这种情况下，通过行锁的机制可以解决这种场景的需求。

举个例子，数据量有10亿，但同时刻并发量只有10w，则相当于10亿个数据共用了10w把锁，如果是普通锁机制，则需要10亿把锁。

原子量

  • 对原子量的 ‘读出-计算-写入’ 操作序列是原子的，在以上动作完成之前，任何其它处理器和线程均无法访问该原子量。
  • 对原子量的 ‘读出-计算-写入’ 操作序列是原子的，在以上动作完成之前，任何其它处理器和线程均无法访问该原子量。
  • 性能方面的代价可以看内存屏障相关的内容
  • 在X86体系结构下，对于64位架构，只要同时满足以下两个条件，那么对该基础内置数据类型变量（int、bool、指针等）的普通读写都是原子的：
    • 条件1:该变量按cache line对齐
    • 条件2:该变量sizeof值不超过64

内存屏障等

疑问TODO

在x86平台写无锁代码，是不是只要保证编译不乱序就可以？cache一致性如何处理，具体如何判断，如何操作

内存模型

软件内存模型

C11与C++11编程语言是一种弱的软件内存模型。如果你正在用x86/64等强类型处理器家族，当在这些语言中使用底层的原子操作时并不会受到影响注3。我之前说过，只要是为了阻止编译器乱序，你必须要指定正确的内存执行顺序限制.

硬件内存模型

强内存模型意味着每个机器指令都能隐式的包含Acquire与Release语义。结果是，当一个CPU核执行一系列的写操作时，其它的每一个CPU核看见的都是那些值都以它们被写入时的顺序在改变。

顺序一致性

在C++11中,当在原子数据类型执行操作的时候，可以使用默认的顺序约束，也就是memory_order_seq_cst。如果这么做了，工具链会限制编译器乱序并发出CPU特定的指令来充当合适的memory barrier。在这种方式下，尽管是在弱内存模型的多核设备上,也会模拟出顺序一致性的内存模型。

cpu cache相关

  • 程序的运行存在时间和空间上的局部性
    • 比如C语言中应该尽量减少静态变量的引用:静态变量存储在全局数据段，在一个被反复调用的函数体内，引用该变量需要对缓存多次换入换出，而如果是分配在堆栈上的局部变量，函数每次调用CPU只要从缓存中就能找到它了，因为堆栈的重复利用率高。
    • 循环体内的代码要尽量精简:代码是放在指令缓存里的，而指令缓存都是一级缓存，只有几K字节大小，如果对某段代码需要多次读取，而这段代码又跨越一个L1缓存大小，那么缓存优势将荡然无存。
  • CPU的流水线(pipeline)并发性

内存屏障

  • store barrier，在x86 上是”sfence”指令，强迫所有的、在屏障指令之前的 存储指令在屏障以前发生，并且让 store buffers 刷新到发布这个指令的 CPU cache。这将使程序状态对其他 CPU 可见，这样，如果需要它们可以对它做出响应。
  • load barrier: 加载屏障，在x86 上是”lfence”指令，强迫所有的、加载指令之后的指令在屏障之后发生，然后等待那个 CPU 的 load buffer 排空。
  • Full Barrier，在x86 上是”mfence”指令，在 CPU 上是加载和内存屏障的组合。

原子指令和软件锁

原子指令，如x86里的 “lock …” 指令，是高效的 full barrier，它们锁住存储子系统来执行操作，有受保证的全序关系（total order），即使跨 CPU。软件锁通常使用内存屏障，或原子指令来达到可视性和保留程序顺序。

Java 存储模型

在Java 存储模型里，volatile 字段在写入后插入一个内存屏障，在读取前插入加载屏障。类里面修饰为 final 的字段在它们被初始化后插入一个存储指令，以确这些字段在构造函数完成、有可用引用到这个对象时是可见的。

内存屏障对性能的影响

内存屏障阻止了 CPU 执行很多隐藏内存延迟的技术，因此有它们有显著的性能开销，必须考虑。为了达到最大性能，最好对问题建模，这样处理器可以做工作单元，然后让所有必须的内存屏障在工作单元的边界上发生。采用这种方法允许处理器不受限制地优化工作单元。把必须的内存屏障分组是有益的，那样，在第一个之后的 buffer 刷新的开销会小点，因为没有工作需要进行重新填充它。

参考文档