目录

• 背景
• 问题
• 共享结构的无锁释放
• • 对比
  • ref-cnt
  • rcu
  • epoch-based reclam
  • hazard pointer: 冒险指针
  • • 结构
    • 原理
    • 正确性保证
    • 范例
• 参考

背景

多线程共享一个数据结构。
共享数据结构，可以做到节约内存。
但是多线程共享，可能会有问题，比如同步的问题。

问题

在并发编程中，当我们在操作共享的内存对象时，需要考虑到其他线程是否有可能也正在访问同一对象，如果要释放该内存对象时不考虑这个问题，会引发严重的后果（访问悬空指针）。

• 共享内存对象的回收问题
  lock-free的方法来解决共享内存对象的回收问题。

• ABA问题
  ABA问题和内存回收问题是相关的，都是内存的生命周期管理问题。

内存回收问题解的是共享内存什么时候能安全的回收，而ABA问题解的是共享内存什么时候能被安全的重新使用。

共享结构的无锁释放

对比

ref-cnt

rcu

epoch-based reclam

hazard pointer: 冒险指针

总结起来，当对象正在使用时，就不能回收内存。每一个“正在使用”都需要对应一个标记。引用计数使用的标记是计数数值一，对应的原子操作性能问题就成为它无法摆脱的原罪。而 Hazard Pointer 使用的标记更为轻巧，一般通过在链表中标记该对象的指针实现，回收时如果发现链表中有对应的指针就不进行内存回收，将标记的复杂度转移到回收部分，也就更适合读多写少的场景。

结构

• 数据结构
  需要为每个线程准备一些线程局部的内存，用来存储两部分内容：
  pointers: 用来存储这个线程当前正在访问的内存对象，正在访问的内存对象不能被任何线程释放；
  retire list（退休列表）: 有待被这个线程释放的内存对象，但还没有释放；

• 原理
  每个线程都将自己正在访问且不希望被任何线程释放的内存对象存放在线程局部的pointers中；
  当任何线程删除内存对象后，都需要先把该内存对象放入自己线程局部的retire list，但是不释放；
  当retire list中的内存对象数量超过一定限度时，扫描retire list，找到没有被任何线程使用的内存节点并将其安全的释放；

• 要点
  pointers是单写多读，而retire list是单写单读的；这个性质很重要，不然的话我们又需要另一种机制来保护hazard pointer了…

原理

每个线程在申请读取某个共享的指针对象时，将指针记录下来（通常在一个per-thread 的 list「对象链表」上），读取结束时将清除该记录；而发生更新时，将更新替换下来的旧指针加入退休列表里，退休列表积攒到一定程度时则检查哪些对象已经不在其他线程的对象链表中，不再使用的则可以执行删除。

Hazard Pointer 的高性能依赖于平台上线程本地存储（TLS： thread local strore）的性能。单纯使用 CAS 更新全局的对象链表和退休列表的性能太低，可以使用 TLS 做为缓冲层，这样大部分时间都是更新本线程的数据。

正确性保证

• 考虑这种情况：

1》线程A开始访问内存对象o，拿到了o的地址
2》线程B将内存对象o从数据结构中删除，加入retire list，并扫描所有线程的pointers，此时线程A还没有来得及将o放入到pointers中，因此3》B可以将o释放
4》线程A将o放入pointers中
5》线程A访问o，crash…

• 分析
  看上去很危险，但实际上这种情况在hazard pointer中并不会发生，因为hazard pointer的正确性证明要求线程在pointers中持有的内存对象都必须是“连续安全的”。
  简单来说，就是说从线程取到该内存对象的一刻开始到将其放入pointers的这段过程中这个内存对象不能被其他线程从数据结构中删除，也就是说其安全状态必须是“连续”的（安全指不会被释放，在数据结构中或是加入到pointers中的的内存对象都是安全的）。

于是流程变成了这样：
1>线程A开始访问内存对象o，拿到了o的地址
2>线程B将内存对象o从数据结构中删除，加入retire list，并扫描所有线程的pointers，此时线程A还没有来得及将o放入到pointers中，因此B可以将o释放
3>线程A将o放入pointers中
4>线程A对o执行double check，发现o已经不在数据结构中了（被删除），因此认为加入到pointers中的地址是无效的，撤销并失败退出

• 如何做到
  double check，代码如下：

范例

参考

http://blog.kongfy.com/2017/02/hazard-pointer/