无锁数据结构中需要多少个 ABA 标记位？
How many ABA tag bits are needed in lock-free data structures?
无锁数据结构中 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 位指针 space .
无锁数据结构中的 ABA 标签需要多少位？
根据论文
http://web.cecs.pdx.edu/~walpole/class/cs510/papers/11.pdf
危险指针：无锁对象的安全内存回收（IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS，第 15 卷，第 6 期，2004 年 6 月，第 491 页），作者：PhD Maged M. Michael
标签位的大小应该使环绕在真正的无锁场景中不可能（我可以读这个好像你可能有 N 个线程 运行 并且每个都可以访问该结构，你应该有 N+1 个不同的状态至少对于标签）：
6.1.1 IBM ABA-Prevention Tags
The earliest and simplest lock-free method for node reuse is
the tag (update counter) method introduced with the
documentation of CAS on the IBM System 370 [11]. It
requires associating a tag with each location that is the
target of ABA-prone comparison operations. By incrementing
the tag when the value of the associated location is
written, comparison operations (e.g., CAS) can determine if
the location was written since it was last accessed by the
same thread, thus preventing the ABA problem.
The method requires that the tag contains enough bits to make
full wraparound impossible during the execution of any
single lock-free attempt. This method is very efficient and
allows the immediate reuse of retired nodes.
可以根据抢占时间和指针修改频率来估计实际安全的标记位数量。
提醒一下，ABA 问题发生在线程读取它想要通过比较和交换更改的值时，被抢占，并且当它恢复时指针的实际值恰好等于线程的值以前读过。因此，尽管在抢占时间内其他线程可能修改了数据结构，但比较和交换操作可能会成功。
添加单调递增标签的想法是使指针的每次修改都是唯一的。为了成功，增量必须在修改线程可能被抢占期间产生唯一的标记值；即为了保证正确性，标签在整个抢占时间内可能不会回绕。
让我们假设抢占持续单个 OS 调度时间片，通常为数十到数百毫秒。 CAS 在现代系统上的延迟是几十到几百纳秒。如此粗略的最坏情况估计是，当一个线程被抢占时，可能会有数百万次指针修改，因此标记中应该有 20 多位才能使其不回绕。
在实践中，可以根据已知的 CAS 操作频率对特定的实际用例做出更好的估计。还需要更准确地估计最坏情况下的抢占时间；例如，被高优先级作业抢占的低优先级线程可能会以更长的抢占时间告终。
根据您的数据结构，您可以从指针中窃取一些额外的位。例如，如果对象是 64 字节并且始终在 64 字节边界上对齐，则每个指针的低 6 位可用于标记（但这可能是您已经为新计划建议的）。
另一种选择是在对象中使用索引而不是指针。
在连续对象的情况下，当然只是数组或向量的索引。对于在堆上分配对象的列表或树，您可以使用自定义分配器并在分配的块中使用索引。
比如说 17M 的对象，你只需要 24 位，剩下 40 位给标签。
这将需要一些（小而快的）额外计算来获得地址，但如果对齐是 2 的幂，则只需要移位和加法。
无锁数据结构中 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 位指针 space .
无锁数据结构中的 ABA 标签需要多少位？
根据论文
http://web.cecs.pdx.edu/~walpole/class/cs510/papers/11.pdf 危险指针：无锁对象的安全内存回收（IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS，第 15 卷，第 6 期，2004 年 6 月，第 491 页），作者：PhD Maged M. Michael
标签位的大小应该使环绕在真正的无锁场景中不可能（我可以读这个好像你可能有 N 个线程 运行 并且每个都可以访问该结构，你应该有 N+1 个不同的状态至少对于标签）：
6.1.1 IBM ABA-Prevention Tags
The earliest and simplest lock-free method for node reuse is the tag (update counter) method introduced with the documentation of CAS on the IBM System 370 [11]. It requires associating a tag with each location that is the target of ABA-prone comparison operations. By incrementing the tag when the value of the associated location is written, comparison operations (e.g., CAS) can determine if the location was written since it was last accessed by the same thread, thus preventing the ABA problem. The method requires that the tag contains enough bits to make full wraparound impossible during the execution of any single lock-free attempt. This method is very efficient and allows the immediate reuse of retired nodes.
可以根据抢占时间和指针修改频率来估计实际安全的标记位数量。
提醒一下，ABA 问题发生在线程读取它想要通过比较和交换更改的值时，被抢占，并且当它恢复时指针的实际值恰好等于线程的值以前读过。因此，尽管在抢占时间内其他线程可能修改了数据结构，但比较和交换操作可能会成功。
添加单调递增标签的想法是使指针的每次修改都是唯一的。为了成功，增量必须在修改线程可能被抢占期间产生唯一的标记值；即为了保证正确性，标签在整个抢占时间内可能不会回绕。
让我们假设抢占持续单个 OS 调度时间片，通常为数十到数百毫秒。 CAS 在现代系统上的延迟是几十到几百纳秒。如此粗略的最坏情况估计是，当一个线程被抢占时，可能会有数百万次指针修改，因此标记中应该有 20 多位才能使其不回绕。
在实践中，可以根据已知的 CAS 操作频率对特定的实际用例做出更好的估计。还需要更准确地估计最坏情况下的抢占时间；例如，被高优先级作业抢占的低优先级线程可能会以更长的抢占时间告终。
根据您的数据结构，您可以从指针中窃取一些额外的位。例如，如果对象是 64 字节并且始终在 64 字节边界上对齐，则每个指针的低 6 位可用于标记（但这可能是您已经为新计划建议的）。
另一种选择是在对象中使用索引而不是指针。
在连续对象的情况下，当然只是数组或向量的索引。对于在堆上分配对象的列表或树，您可以使用自定义分配器并在分配的块中使用索引。
比如说 17M 的对象，你只需要 24 位，剩下 40 位给标签。
这将需要一些（小而快的）额外计算来获得地址，但如果对齐是 2 的幂，则只需要移位和加法。