Maged M. Michael的Hazard Pointer能否防范ABA问题?代码逻辑解惑
关于Hazard Pointer入队操作中ABA问题的疑问
更新说明:
我认为“其他线程可能在第4行到第4b行之间移除并重新插入节点”指的是,在第4行到第4b行期间,某个节点可能被移除、修改并重新插入到同一位置,且在被其他线程完全回收前,会引发潜在的ABA问题——即节点地址不变但内容已更改。
我正在研读Maged M. Michael介绍Hazard Pointer的论文,文中给出了一个使用Hazard Pointer的入队(Enqueue)函数:
//FIFO queue algorithm, stripped of memory management code structure NodeType { Data:DataType; Next:*NodeType; } //Shared variables Head,Tail:*NodeType; //Initially both Head and Tail point to a dummy node //hp0 is private ptr to 2 of the thread's hazard ptrs Enqueue(data: DataType) { 1. node <- NewNode(); 2. node.Data <- data; 3. node.Next <- null; while true { 4. t <- Tail; 4a: *hp0 <- t; 4b: if (Tail ≠ t) continue; 5. next <- t.Next 6. if (Tail ≠ t) continue; 7. if (next ≠ null) {CAS(&Tail, t, next); continue;} 8. if CAS(&t.next, null, node) break; } 9. CAS(&Tail, t, node); }
若缺少第4a和4b行,第5行访问节点时可能出现访问风险(访问风险:线程尝试访问已被释放的节点)。
作者称第4a和4b行可保证安全内存回收与ABA防范。我理解其安全内存回收的逻辑,但不清楚如何防范ABA问题。
作者提到其他线程可能在第4行到第4b行之间移除并重新插入节点,但表示这可接受,因为未违反3.3节的条件。
换句话说,作者承认可能出现ABA问题(节点移除并重新插入),但只要满足3.3节的特定条件,就是可行的。
3.3节条件(翻译):
因此,关联算法必须满足的条件是:当线程持有某个节点的危险引用时,该线程的至少一个危险指针必须从该节点对线程绝对安全的时刻起,持续持有该引用。请注意,这个条件意味着,当节点被标记为待回收(retired)时,没有线程能够创建指向该节点的新危险引用。
我不理解该条件与第4a、4b行防范ABA问题的关联。
内容的提问来源于stack exchange,提问作者Anderson Chris
相关产品推荐
相关产品推荐

