与AI纸上谈兵-CAS的ABA问题

CAS

CAS即Compare And Swap的缩写，翻译成中文就是 比较并交换 ，其作用是让CPU比较内存中某个值是否和预期的值相同，如果相同则将这个值更新为新值，不相同则不做更新，也就是CAS是原子性的操作(读和写两者同时具有原子性)，其实现方式是通过借助C/C++调用CPU指令完成的，所以效率很高。

用CAS来实现一个无锁栈

设想我们实现了一个无锁栈，用链表节点表示栈中的元素，其中top指针指向栈顶元素。为了实现高效和线程安全的出栈操作，我们使用CAS更新top指针。一个典型的出栈伪代码可能是以下形式：

function pop() {  
    do {  
        oldTop = top  // 获取当前栈顶节点  
        if (oldTop == null) {  
            return null  // 栈为空  
        }  
        newTop = oldTop.next  // 栈顶将被移除，新的栈顶是下一个  
    } while (!compare_and_swap(top, oldTop, newTop))  // CAS操作，尝试更新栈顶  
    return oldTop.value  // 返回栈顶的值  
}

ABA问题-在无锁栈中

假设以下线程和操作按顺序发生：

1. 线程A：调用pop，读取oldTop，其值是节点A。
2. 线程B：调用两次pop，依次移除了节点A和节点B，并随后将节点A重新压回栈（通过push操作），此时栈的top再次指向节点A。
3. 线程A：继续执行刚才的CAS操作，发现top的值仍然是节点A（因为线程B又将节点A压回栈），CAS 操作通过。

看似 CAS 成功了，但线程A并不知道，栈的结构已经在它检查oldTop和执行CAS之间发生了改变。此时返回的节点A可能已经不再安全使用，因为它的状态已经被修改，或者栈本身的数据结构可能已经遭到破坏。

ABA问题-在“生活”中

小明在提款机，提取了50元，因为提款机问题，有两个线程，同时把余额从100变为50

线程1（提款机）：获取当前值100，期望更新为50，

线程2（提款机）：获取当前值100，期望更新为50，

线程1成功执行，线程2某种原因block了，这时，某人给小明汇款50

线程3（默认）：获取当前值50，期望更新为100，

这时候线程3成功执行，余额变为100，

线程2从Block中恢复，获取到的也是100，compare之后，继续更新余额为50！！！

此时可以看到，实际余额应该为100（100-50+50），但是实际上变为了50（100-50+50-50）这就是ABA问题带来的成功提交。

ABA问题的解决

在变量前面加上版本号，每次变量更新的时候变量的 版本号都 +1，即A->B->A就变成了1A->2B->3A。

class Node<T> {  
    T value;  
    Node<T> next;  
    long version; // 添加版本号字段  
}  

class VersionedReference<T> {  
    Node<T> reference;  
    long version;  
  
    VersionedReference(Node<T> ref, long ver) {  
        reference = ref;  
        version = ver;  
    }  
}  

function pop() {  
    VersionedReference<T> oldTop;  
    Node<T> newTop;  
  
    do {  
        oldTop = top.get(); // 获取当前的引用和版本号  
        if (oldTop.reference == null) {  
            return null; // 栈为空  
        }  
        newTop = oldTop.reference.next; // 新的栈顶是下一个节点  
      
        // CAS操作会同时比较引用和版本号  
    } while (!top.compareAndSet(  
        oldTop,  // 期望的旧值(包含引用和版本号)  
        new VersionedReference(newTop, oldTop.version + 1)  // 新值(更新引用和版本号)  
    ));  
  
    return oldTop.reference.value;  
}  

什么是原语？

计算机是一门人造科学，因此真正意义上的“原语”是不存在的。操作系统层面上的“原语”（比如 write 之类的系统调用）对程序员来讲的确是不可分割的最小单位，但是这写系统调用本身还是用好几句汇编语句组成的（对于 Linux 来说是 C 语言）。可能有人要说到了机器代码这一级就不能再分了，但事实上一条机器指令也是由好几个组合逻辑信号构成的。同样的道理，控制信号也不过是无数电子在器件内部漂移的结果。

因此定义“原语”的前提是观察者所处的位置。一旦规定了观察者的位置和观察的角度，比如就在操作系统的这层上，read，wirte，wait这些个系统调用自然就是最“原始”的词汇，这也是为什么“原语”会在操作系统中频繁出现的缘故。

参考

什么是“原语”

CAS原理分析及ABA问题详解

Claude 3.5 sonnet