- Paper: [Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation](https://sysweb.cs.toronto.edu/publication_files/0000/0165/ipdps06.pdf)
# Memory Reclaimtion Schemes
- Blocking schemes：
- QSBR
- EBR
- Non-blocking scemes：
- HPBR
- LFRC
## QSBR：Quiescent-State-Based Reclamation
- Grace period `[a, b]`:
- 在时间b之后，所有在时间 a 之前删除的node，都可以被安全地删除；
- Quiescent state：
- QSBR使用 quiescent state来检测 grace period；
- 线程T没有引用共享的nodes；
- QSBR的 grace period就是所有的线程都经历过了一个 quiescent state；
- Quiescent state 的定义是应用独立的，例如linux定义为 voluntary context switch等；
- 例如 `[t1, t3]` 或者 `[t3, t5]` 都是一个 grace period；
- 并不需要跟踪最小的 grace period，任何包含了 `[t1, t3]` 和 `[t3, t5]` 的时间段都是 grace period；
- QSBR天生就是blocking的：
- 
## EBR：Epoch-Based Reclamation
- 使用 epoch 取代 QSBR 的 quiescent state；
```c
/// EBR concurrently-readable search
int search (struct list *l, long key)
{
node_t *cur;
critical_enter();
for (cur = l->list_head;
cur != NULL; cur = cur->next) {
if (cur->key >= key) {
critical_exit();
return (cur->key == key);
}
}
critical_exit();
return (0);
}
```
- 与 QSBR 对比：
• 好处：跟踪流程可以对上层应用隐藏，易于使用；
• 坏处：开销更大些， QSBR不需要记录 epoch，
## HPBR：Hazard-Pointer-Based Reclamation
- 每个线程在操作时保存 K 个 hazard pointers，用来阻止其他线程进行回收；
- Queue 和 linked list 需要 K = 2 Hazard pointer，Stack只需要 K = 1；
- 删除一个node后，线程把它放在一个私有的list中，
- 当list的大小到达一个预定的阈值R后，线程开始回收没有非harzad pointer的node；
----
# Memory Consistency
- HPBR、EBR 和 LFRC 需要 per-operation fences；
- HPBR 和 LFRC 还需要 per node fence；
- per node fence 意味着对迭代遍历不友好（需要访问很多nodes）；
- 即访问节点多的场景下，性能差；