无锁数据结构中需要多少个ABA标记位？

Question

无锁数据结构中ABA问题的一种流行解决方案是使用额外的单调递增标记来标记指针.

 struct aba {
      void *ptr;
      uint32_t tag;
 };

但是,这种方法存在问题.它真的很慢,并且存在巨大的缓存问题.如果我抛弃标签字段,我可以获得两倍的加速.但这不安全吗？

所以我下一次64位平台的尝试填充了ptr字段中的位.

struct aba {
    uintptr __ptr;
};
uint32_t get_tag(struct aba aba) { return aba.__ptr >> 48U; }

但有人告诉我,标签只有16位是不安全的.我的新计划是使用指针对齐缓存行来填充更多标记位,但我想知道它是否有效.

如果无法工作,我的下一个计划是使用Linux的MAP_32BIT mmap标志来分配数据,所以我只需要32位指针空间.

在无锁数据结构中,ABA标记需要多少位？

Answer 1

可以根据抢占时间和指针修改的频率来估计实际上安全的标签位数。

提醒一下，当线程读取它想要通过比较和交换更改的值并被抢占时，就会发生 ABA 问题，并且当它恢复时，指针的实际值恰好等于线程之前读取的值。因此，尽管其他线程在抢占期间可能进行数据结构修改，但比较和交换操作仍可能成功。

添加单调递增标签的想法是使指针的每次修改都是唯一的。为了使其成功，增量必须在修改线程可能被抢占的时间内产生唯一的标记值；即，为了保证正确性，标签在整个抢占时间内可能不会环绕。

我们假设抢占持续单个操作系统调度时间片，通常为数十到数百毫秒。现代系统上 CAS 的延迟为数十到数百纳秒。因此，粗略的最坏情况估计是，当线程被抢占时，可能会有数百万次指针修改，因此标记中应该有 20+ 位，以便它不会环绕。

在实践中，可以根据已知的 CAS 操作频率对特定的实际用例做出更好的估计。还需要更准确地估计最坏情况的抢占时间；例如，低优先级线程被高优先级作业抢占可能会导致抢占时间更长。