如何用无锁算法计算栈大小？CAS实现无锁栈的栈长计算方法

嘿，这两个关于无锁栈计数的问题我刚好有经验，来给你详细拆解一下～

无锁环境下，普通全局变量计数肯定行不通——多线程竞争时会出现竞态条件，导致计数和实际栈元素数量不符。核心思路是用原子变量配合CAS（Compare-And-Swap）操作维护线程安全的计数器，具体步骤如下：

• 给栈新增一个原子类型的计数器（比如C里的_Atomic size_t，C++里的std::atomic<size_t>），初始值设为0。
• 入栈（push）操作：只有当通过CAS成功将新节点设为栈顶后，再原子地递增计数器（比如调用fetch_add(1)）。必须保证栈的CAS操作成功后才更新计数器，否则会出现“计数加了但节点没入栈”的不一致情况。
• 出栈（pop）操作：同理，只有当CAS成功移除栈顶节点后，再原子地递减计数器（比如fetch_sub(1)）。
• 如果你的编程语言/环境不支持原子加减指令，也可以用CAS手动实现计数器增减：比如递增时，先读取当前计数，然后尝试CAS将其更新为当前值+1，直到CAS成功为止。

首先纠正你代码里的小笔误：return t-val;应该是return t->val;，不然编译都通不过😂。

要给这个无锁栈加上长度计数，我们需要新增一个原子计数器，然后修改pop和对应的push操作，确保计数和栈操作同步：

第一步：新增原子计数器 #

// C语言示例，用原子类型定义计数器，初始为0
_Atomic size_t StackSize = 0;
// 如果是C++，用std::atomic<size_t> StackSize = 0;

第二步：修改pop操作，同步更新计数器 #

只有当CAS成功修改栈顶（也就是出栈操作真正完成）时，我们才递减计数器：

data_t pop() { 
    Node *t, *x; 
    do{ 
        t = Top; 
        if(t == NULL) return EMPTY; 
        x = t->next; 
    } while(!CAS(&Top, t, x)); 
    // CAS成功，出栈完成，原子递减计数器
    StackSize.fetch_sub(1);
    return t->val; 
}

第三步：同步修改push操作（必须配套） #

对应的push操作也要在CAS成功入栈后递增计数器，不然计数会和实际元素数不符：

void push(data_t val) {
    Node *new_node = malloc(sizeof(Node));
    if (!new_node) {
        // 处理内存分配失败的情况，比如返回错误码
        return;
    }
    new_node->val = val;
    Node *t;
    do {
        t = Top;
        new_node->next = t;
    } while(!CAS(&Top, t, new_node));
    // CAS成功，入栈完成，原子递增计数器
    StackSize.fetch_add(1);
}

关于CAS手动实现计数增减的备选方案 #

如果你的环境不支持fetch_add/fetch_sub这类原子加减指令，也可以用CAS手动循环实现：
比如递减计数器的部分可以改成：

size_t current_count;
do {
    current_count = StackSize;
    // 栈不为空才递减，这里已经确保出栈成功，所以current_count至少为1
} while(!CAS(&StackSize, current_count, current_count - 1));

不过硬件原生支持的原子加减指令比手动CAS循环更高效，优先用前者。

注意事项 #

• 必须保证栈操作的CAS成功和计数器更新是绑定的：不能先更新计数器再做栈的CAS，否则如果CAS失败，计数器就会和实际栈元素数不一致。
• 当栈为空时，pop返回EMPTY，这时候不能修改计数器，否则会出现负数计数。

内容的提问来源于stack exchange，提问作者Eraboti Aledor