iis7 asp网站运行缓慢,网站后台首页模板,关于征求网站建设,phpcms 手机网站后台文章目录 无锁队列中的ABA问题ABA问题解决方案 ABA问题#xff1a;CAS在操作的时候会检查变量的值是否被更改过#xff0c;如果没有则更新值#xff0c;但是带来一个问题#xff0c;最开始的值是A#xff0c;接着变成B#xff0c;最后又变成了A。经过检查这个值确实没有修… 文章目录 无锁队列中的ABA问题ABA问题解决方案 ABA问题CAS在操作的时候会检查变量的值是否被更改过如果没有则更新值但是带来一个问题最开始的值是A接着变成B最后又变成了A。经过检查这个值确实没有修改过因为最后的值还是A但是实际上这个值确实已经被修改过了。
听起来似乎没有什么严重的问题举几个实际的例子看下。
无锁队列中的ABA问题
/* Naive lock-free stack which suffers from ABA problem.*/
class Stack {std::atomicObj* top_ptr;//// Pops the top object and returns a pointer to it.//Obj* Pop() {while (1) {Obj* ret_ptr top_ptr;if (ret_ptr nullptr) return nullptr;// For simplicity, suppose that we can ensure that this dereference is safe// (i.e., that no other thread has popped the stack in the meantime).Obj* next_ptr ret_ptr-next;// If the top node is still ret, then assume no one has changed the stack.// (That statement is not always true because of the ABA problem)// Atomically replace top with next.if (top_ptr.compare_exchange_weak(ret_ptr, next_ptr)) {return ret_ptr;}// The stack has changed, start over.}}//// Pushes the object specified by obj_ptr to stack.//void Push(Obj* obj_ptr) {while (1) {Obj* next_ptr top_ptr;obj_ptr-next next_ptr;// If the top node is still next, then assume no one has changed the stack.// (That statement is not always true because of the ABA problem)// Atomically replace top with obj.if (top_ptr.compare_exchange_weak(next_ptr, obj_ptr)) {return;}// The stack has changed, start over.}}
};考虑有两个线程并发的访问该队列。
初始时栈顶元素是 AA 指向 BB 指向 C。
top -- A -- B -- CThread 1 执行 pop 操作将栈顶元素 A 弹出取出了top_ptr, 和 next_ptr后被中断。
Obj* ret_ptr top_ptr;
if (ret_ptr nullptr) return nullptr;// For simplicity, suppose that we can ensure that this dereference is safe// (i.e., that no other thread has popped the stack in the meantime).Obj* next_ptr ret_ptr-next;此刻Thread 1里看到的是top_ptr等于A next_ptr 等于B问题其实就在这里了保证top_ptr等于A时并不能保证next_ptr等于B。
Thread 2 执行 pop 操作将栈顶元素从 A 改为 B。
top -- B -- CThread 2 再次执行 pop 操作将栈顶元素从 B 改为 C。
top -- CThread 2 执行 push 操作将元素 A 推回到栈顶。
top -- A -- CThread 1 继续执行执行 compare_exchange_weak(A, B)由于 top ret操作成功栈顶元素变为了 B。 此刻
top -- B(already delete)Thread 1 访问栈顶元素但是 B 已经被删除这导致了 ABA 问题。
当从列表中删除一个项目并释放其内存后如果再次分配一个新项目并将其添加到列表中由于最近最常使用MRU的内存分配策略新分配的对象通常会位于被删除对象的相同位置。
或者是在启用缓存机制时重新分配的对象也有极大的概率是之前释放的对象。ABA问题解决方案
在原有的内容上添加额外的“标签”或“戳记”位。例如使用比较和交换compare and swap操作指针的算法可以使用地址的低位来表示指针成功修改的次数。因此即使地址相同下一次比较和交换操作也会失败因为标签位不匹配。这种情况有时被称为ABAʹ因为第二个A与第一个略有不同。这种带标签的状态引用也被用于事务内存transactional memory中。
在实现中可以使用带标签的指针来解决ABA问题其中指针的低位用于存储标签信息。然而如果支持双宽比较和交换double-width CAS更常见的做法是使用单独的标签字段。
通过使用标签位每次对共享数据进行操作时都会更新标签即使地址相同标签的变化也能够反映出对象的修改历史。这样在进行比较和交换操作时除了比较地址外还需要比较标签位从而更可靠地检测到对象的变化。
如果“标签”字段发生了环绕wraparound那么对抗ABA问题的保证就不再有效。然而根据观察在当前存在的CPU上并且使用60位标签只要程序的生命周期即在不重新启动程序的情况下限制在10年内就不会发生环绕此外有人认为为了实际目的通常只需拥有40-48位的标签来确保不会发生环绕。由于现代CPU特别是所有现代x64 CPU倾向于支持128位的CAS比较和交换操作这可以提供对抗ABA问题的可靠保证。
当使用128位CAS操作时除了存储指针地址外还可以存储一个更大的标签值。因为标签位数更多所以即使在长时间运行的程序中标签的环绕概率也非常低几乎可以忽略不计。
通过使用128位CAS操作并保留足够长度的标签位可以提供对抗ABA问题的坚实保证。这意味着在多线程或并发环境中即使对象的地址没有改变只要标签发生变化CAS操作也会失败从而可以正确检测到对象的变化。这种方法在实践中被广泛采用以确保数据的一致性和并发操作的正确性。
所谓的版本号、标记基本都是采用这个原理。
