念头。遇见不同想法 NIANTOU.NET

在别人的文字里,遇见自己的念头。

独立书写 · 自由阅读

土法炼钢

按发表时间排列
45 篇

RCU:宽限期的保证、读侧的三种实现与代价的去向

从宽限期保证的形式陈述出发,对照 liburcu 0.15.7 与 Linux v6.12 源码,说明读侧省掉的 StoreLoad 栅栏由谁补上、'读侧零开销'在哪些配置下成立;实测读侧开销、宽限期延迟、membarrier IPI 转嫁给读者的代价和一个缺栅栏的变异体。

并发跳表:标记删除、乐观加锁与 ConcurrentSkipListMap

跳表插删要改多个指针,靠标记删除或乐观加锁把它们变成一次线性化操作。对照 Pugh、Harris、Fraser、HLLS 与 JDK 21、LevelDB、RocksDB 源码,并用 TSan 与对拍验证实现,实测独占 CPU 与超额订阅两种情形下的吞吐。

无锁队列:Michael-Scott 算法与 ABA 问题

按 PODC 1996 原文复原 Michael-Scott 无锁队列:线性化点、计数指针防 ABA、计数器为何不解决内存回收、每条 CAS 的 C11 内存序,并用 TSan 与线性化检查器实测。

Cuckoo Hashing:用两个位置换取最坏情况常数查找

从 Pagh–Rodler 的两表插入与 cuckoo 图出发,用可复现实验核对失败概率、stash、d-ary 与分桶的负载阈值和两种插入搜索的代价,再对照 MemC3、libcuckoo、DPDK、OVS 源码说明并发读写怎样避免假未命中。

无锁栈:Treiber 栈、ABA、指数退避与消除退避

Treiber 栈只靠一次 CAS,却要分别处理 ABA、内存回收和争用三件事。本文用确定性复现、守恒测试和 sanitizer 区分前两者,在 4 个逻辑 CPU 上实测指数退避与消除数组,并对照 Linux llist、Windows SList、Boost.Lockfree 的取舍。

读到这里,留一点时间给自己的念头。