multithreading - 无锁数据结构中需要多少个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问题。因此，尽管在抢占时间内其他线程可能对数据结构进行了修改，但比较和交换操作仍可能成功。

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

假设抢占持续一个OS调度时间片，通常为数十到数百毫秒。在现代系统上，CAS的等待时间为数十至数百纳秒。如此粗略的最坏情况估计是，抢占线程时可能会有数百万个指针修改，因此标记中应该有20多个位，以使其不会回绕。

实际上，可以基于CAS操作的已知频率对特定的实际用例进行更好的估计。还需要更准确地估计最坏情况下的抢占时间；例如，被高优先级作业抢占的低优先级线程可能会以更长的抢占时间结束。