并发控制相关
对锁的理解
- 资源的并发保护
- 保证临界区的顺序(内存屏障/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 刷新的开销会小点,因为没有工作需要进行重新填充它。
参考文档
- 名不符实的读写锁
- Read-Copy Update,向无锁编程进发!
- liburcu,一个用户态的RCU实现
- HBase – 并发控制机制解析
- Herb Sutter谈论C++无锁编程
- 并发编程系列之一:锁的意义
- 从LONGADDER看更高效的无锁实现
- 7个示例科普CPU CACHE
- 内存屏障(Memory Barriers)
- 无锁HASHMAP的原理与实现
- Intel Haswell的事务内存分析
- 深入探索并发编程系列(一)-锁不慢;锁竞争慢
- 深入探索并发编程系列(二)-总是使用轻量级锁
- 深入探索并发编程系列(五)-将内存乱序逮个正着
- 深入探索并发编程系列(六)-编译期间内存乱序
- 深入探索并发编程系列(七)-内存屏障:资源控制操作
- 深入探索并发编程系列(八)-Acquire与Release语义
- 深入探索并发编程系列(九)-弱/强内存模型
- High Performance Dynamic Lock-Free Hash Tables
and List-Based Sets