分割和同步设计
并发编程中的设计模式
分割联系
哲学家的就餐问题
阻止饥饿
Dijkstra解决方法
- 使用一个全局信号量
- 假设通信延迟忽略不计的话
最新的解决办法：
- 给叉子编号
- 先拿盘子周围编号最小的叉子
- 然后再拿编号最高的叉子
- 至少有一位肯定可以拿到两把叉子，则开始就餐
为资源编号并按照编号顺序获取资源的通用技术在防止死锁上经常使用
这类问题，都是这对资源争用，因此也可以称之为
- 水平并行化
- 数据并行化
双端队列
如果基于锁，要达到在双端队列两端进行并发操作是比较困难的。
右手锁和左手锁
左手锁
- 控制左手端入列操作
右手锁
- 控制右手端入列操作
4个以内的数据，重叠
- 需要两个锁同时起作用
复合双端队列
用两个单独的双端队列串联在一起
- 每个队列用自己的锁保护
- 需要控制加锁层次的顺序一致
- 避免死锁
需要重新平衡两个队列的元素，带来额外的性能开销
哈希永远是分割一个数据结构的最简单和最有效的方法。、
可以根据元素在队列中的位置为每个元素分配一个序号，然后以此对双端队列进行哈希。
为了避免死锁，只在获取链表锁之前获取下标锁，每种类型的锁（下标或者链表）每次从不获取超过一个
讨论
复合式在某种程度上比哈希式实现要复杂，但效果可能会好一些。
- 没有考虑复杂的重新平衡机制
不过，这种机制最多也就获得了两倍的扩展能力
- 最多只能有两个线程并发的持有出列的锁
- 关键点在于从共享队列中入列或者出列的巨大开销
分割问题的讨论
水平并行化/数据并行化
- 同步开销小（接近0）
垂直并行化/管道
- 双端队列
- 数据可以从一个线程转移到另一个线程
- 需要密切的合作
- 需要更多的工作来获得某种程度的效率
设计准则
并发编程的目标：
- 性能
- 生产率
- 通用性
设计模式
- 这些准则被认为是设计中的阻力
- 对这些阻力进行恰当权衡
设计准则：
- 加速
- 顺序执行 / 并行执行
- 竞争
- 不是越多CPU越好
- 资源竞争
- 锁竞争
- 内存竞争
- 开销
- 工作-同步比率
- 消耗在同步原语上的时间都是不必要的开销
- 缓存缺失
- 消息延迟
- 加解锁原语
- 原子指令
- 内存屏障
- 同步开销与临界区代码的开销衡量
- 更大的临界区能容忍更大的同步开销
- 读写比率
- 对不同操作采用不同的同步原语来保护
- 复杂性
- 需要维护更多状态
- 还必须考虑
- 同步原语
- 消息传递
- 锁的设计
- 临界区识别
- 死锁
- 更高的开发/维护代价
- 顺序执行还有优化的空间
- 并行化只是众多优化中的一种，并不是唯一的
- 主要应用于CPU瓶颈的优化
建议：
- 程序在临界区上所花的时间越少，潜在加速就越大
- Amdahl定律
- 一个时刻只有一个CPU进入临界区
- 程序在某个互斥的临界区上所耗费的时间必须大大小于CPU数的倒数
- 这样增加CPU数目才能达到加速
- 竞争效应所浪费的多余CPU和 / 本来该是加速的理想时间，应该少于可用CPU的数目
- 差距越大，CPU的效率越低
- 如果可用的同步原语相较它们保护的临界区来说开销太大
- 加速程序运行的最佳办法是减少调用这些原语的次数
- 分批进入临界区
- 数据所有权
- RCU
- 使用粒度更粗的设计
- 代码锁
- 加速程序运行的最佳办法是减少调用这些原语的次数
- 如果临界区相较守护这块临界区的原语来说开销太大
- 加速程序运行的最佳办法是增加程序的并行化程度
- 读写锁
- 数据锁
- RCU
- 数据所有权
- 加速程序运行的最佳办法是增加程序的并行化程度
- 如果临界区相较守护这块临界区的原语来说开销太大，并且被守护的数据结构读多于写
- 那么加速程序运行的最佳办法是增加程序的并行化程序
- 读写锁
- RCU
- 那么加速程序运行的最佳办法是增加程序的并行化程序
- 各种增加SMP性能的改动，减少锁竞争程度，能改善响应时间
- 多核处理器
同步粒度
-
串行程序
-
代码锁
- 硬性的同步语句，加锁
- 容易引起锁竞争
-
数据锁
- 在数据结构中，分割一个锁结构
- 每个数据都带有一把自己的锁
- 避免全局锁的争用
- 想要降低锁竞争，并且同步开销不是主要瓶颈时，适用
-
数据所有权
- 按照线程或者CPU的个数分割数据结构
- 每个线程/CPU都可以不需要任何同步开销的情况下访问属于它的子集
- 数据/资源隔离
- 需要考虑数据分割的平均
- 避免分配不均，导致热点
- 对于重要数据只读可以通过复制来让每一个线程/CPU拥有数据
MIPS(Million Instructions Per Second)：单字长定点指令平均执行速度 Million Instructions Per Second的缩写，每秒处理的百万级的机器语言指令数
在数据结构的锁已经被获取时，防止数据结构被释放的几种解决办法：
- 适用静态分配的锁
- 变相的全局锁
- 导致高度的锁冲突
- 降低性能和扩展性
- 使用静态分配的锁数组，将数据结构的地址进行哈希，以选择要获取的锁
- 哈希函数要足够的高效
- 扩展性的瓶颈点
- 只读时，锁请求的开销降低性能
- 哈希函数要足够的高效
- 使用垃圾回收器
- 在数据结构还有被引用时，不会被释放
- 消除了存在性保证性的负担
- 加重了垃圾回收的负担
- 作为垃圾回收机制的特例，使用一个全局的引用计数，或者一个全局的引用计数数组
- 使用冒险指针，它可以被视为一种inside-out引用计数
- 基于冒险指针的算法，维护一个每线程的指针列表
- 列表中的特定指针就是相应结构的引用
- 有点类似智能指针
- 基于冒险指针的算法，维护一个每线程的指针列表
- 使用事务内存（TM）
- 每一次对数据结构的引用和修改都被自动执行
- 使用RCU（Read-Copy Update）
- 一种极其轻量级的，类似垃圾回收器的东西
- 写者不允许释放那些仍然被读者所引用的数据结构
- 对于那些大量用于读取的数据结构来说，RCU被大量使用
并行快速路径
细粒度的设计一般要比粗粒度的设计复杂。
- 许多情况下，绝大部分开销只由一小部分代码产生
- 不只是算法需要并行化，算法所属的工作负载也要并行化
并行快速路径的设计模式
- 读写锁
- RCU
- 分层多级锁
- 分配器缓存（Allocator caches）
读写锁
如果同步开销可以忽略不计（比如程序使用了粗粒度的并行化），并且只有一小段临界区修改数据，那么让多个读者并行处理可以显著地增加可扩展性
层级锁
需要严格注意加锁顺序，防止死锁
额外的加解锁动作，会带来开销
可以考虑，不同的重量级别的锁，自旋，读写，互斥
如：jdk 6 中的 4层锁结构， 自旋->轻量->重量->互斥
资源分配器缓存
并行，为每一个cpu分配一个独享的资源池。
分级，独享的小空间（资源池）；一个较大的共享资源池，实用代码锁保护。
典型例子：
- CPU的多级缓存
- JVM中的多级GC空间
防止随便，多个空间可以连续使用。
- 分配器常规套路
- jvm也有类似的设计
其他难点：
- 弹性的空间管理
- 实际中，还需要处理各种不同的资源大小
- 最大允许的空间阈值
- 不同用途的空间，使用不同的管理策略
- 不同级别的内存块组合
- 页
- 如jvm中分配的空间单位，分成不同大小块的空间（资源池）
- 这些不同大小的空间，可用于不同大小的Object空间分配
- 更好的解决对齐
- 不同级别的内存块组合
| 等级 | 锁类型 | 目的 |
|---|---|---|
| 每线程资源池 | 数据所有权 | 高速分配 |
| 全局内存块资源池 | 数据锁 | 将内存块放在各个线程中 |
| 组合 | 数据锁 | 将内存块放在页中 |
| 系统内存 | 代码锁 | 获取、释放系统内存 |
