1
// CAS 语义：原子地比较并交换
2
// 如果 *addr == expected，则 *addr = desired，返回 true
3
// 否则返回 false，*addr 不变
4
bool cas(int* addr, int expected, int desired);
5

6
// x86 实现：LOCK CMPXCHG 指令
7
inline bool cas(volatile int* addr, int expected, int desired) {
8
    int result;
9
    __asm__ __volatile__ (
10
        "lock cmpxchgl %3, %1\n\t"
11
        "sete %0"
12
        : "=r" (result), "+m" (*addr)
13
        : "a" (expected), "r" (desired)
14
        : "cc", "memory"
15
    );
16
    return result;
17
}

1
// FAA 语义：原子地增加并返回旧值
2
// old = *addr; *addr += value; return old;
3
int faa(int* addr, int value);
4

5
// x86 实现：LOCK XADD 指令
6
inline int faa(volatile int* addr, int value) {
7
    __asm__ __volatile__ (
8
        "lock xaddl %0, %1"
9
        : "+r" (value), "+m" (*addr)
10
        :
11
        : "cc", "memory"
12
    );
13
    return value;  // 返回旧值
14
}

1
// ARM64: 原子 CAS 的 LL/SC 实现
2
// LDXR: 独占加载，标记地址
3
// STXR: 独占存储，返回 0 表示成功
4
cas:
5
    ldxr    w0, [x1]           // 独占加载 *addr → w0
6
    cmp     w0, w2             // 比较 w0 == expected?
7
    b.ne    fail
8
    stxr    w3, w4, [x1]       // 独占存储 desired → *addr
9
    cbnz    w3, cas            // 如果失败（被其他核心修改），重试
10
fail:
11
    ret

1
#include <atomic>
2

3
std::atomic<int> counter{0};
4

5
// 原子递增
6
counter.fetch_add(1, std::memory_order_relaxed);
7

8
// 原子读取
9
int val = counter.load(std::memory_order_acquire);
10

11
// 原子写入
12
counter.store(42, std::memory_order_release);
13

14
// CAS 操作
15
int expected = 42;
16
bool success = counter.compare_exchange_strong(
17
    expected, 100,
18
    std::memory_order_acq_rel,
19
    std::memory_order_acquire
20
);

1
// 经典的 acquire-release 模式
2
std::atomic<bool> ready{false};
3
int data = 0;
4

5
// 生产者线程
6
void producer() {
7
    data = 42;  // 写数据
8
    ready.store(true, std::memory_order_release);  // 释放：保证上面的写可见
9
}
10

11
// 消费者线程
12
void consumer() {
13
    while (!ready.load(std::memory_order_acquire)) {}  // 获取：保证看到 release 之前的写
14
    assert(data == 42);  // 一定成立！
15
}

1
// 伪共享：两个计数器在同一缓存行
2
struct BadCounters {
3
    std::atomic<int> a;  // 线程 1 频繁更新
4
    std::atomic<int> b;  // 线程 2 频繁更新
5
    // a 和 b 可能在同一 64 字节缓存行
6
    // 线程 1 更新 a → 使线程 2 的缓存行失效
7
    // 线程 2 更新 b → 使线程 1 的缓存行失效
8
    // 反复弹跳，性能下降 10-50x
9
};
10

11
// 缓存行对齐：消除伪共享
12
struct GoodCounters {
13
    alignas(64) std::atomic<int> a;  // 独占缓存行
14
    alignas(64) std::atomic<int> b;  // 独占缓存行
15
};

1
# 使用 perf 检测缓存行弹跳
2
perf stat -e cache-misses,cycles,L1-dcache-load-misses \
3
    ./counter_benchmark
4

5
# 使用 perf c2c 检测伪共享
6
perf c2c record ./counter_benchmark
7
perf c2c report
8
# 输出会显示哪些缓存行被多个线程修改

1
// CAS 失败时的指数退避
2
void atomic_add(std::atomic<int>& counter, int value) {
3
    int backoff = 1;
4
    int old = counter.load(std::memory_order_relaxed);
5
    while (!counter.compare_exchange_weak(
6
        old, old + value,
7
        std::memory_order_relaxed)) {
8
        // 退避：减少缓存行争用
9
        for (int i = 0; i < backoff; i++) {
10
            _mm_pause();  // x86 PAUSE 指令，约 40 ns
11
        }
12
        backoff = std::min(backoff * 2, 64);  // 上限 64
13
    }
14
}

1
// Go: 无锁计数器
2
type AtomicCounter struct {
3
    value int64
4
}
5

6
func (c *AtomicCounter) Increment() {
7
    atomic.AddInt64(&c.value, 1)
8
}
9

10
func (c *AtomicCounter) Get() int64 {
11
    return atomic.LoadInt64(&c.value)
12
}
13

14
// Per-CPU 计数器：消除缓存行争用
15
type PerCPUCounter struct {
16
    counters []int64  // 每个 CPU 一个计数器，缓存行对齐
17
    padding  [64]byte // 防止伪共享
18
}
19

20
func (c *PerCPUCounter) Increment() {
21
    cpu := runtime.GetCPU()  // 获取当前 CPU ID
22
    atomic.AddInt64(&c.counters[cpu], 1)
23
}
24

25
func (c *PerCPUCounter) Get() int64 {
26
    var total int64
27
    for i := range c.counters {
28
        total += atomic.LoadInt64(&c.counters[i])
29
    }
30
    return total
31
}

1
// Michael-Scott 无锁队列（简化版）
2
template<typename T>
3
class LockFreeQueue {
4
    struct Node {
5
        T data;
6
        std::atomic<Node*> next{nullptr};
7
    };
8

9
    std::atomic<Node*> head;
10
    std::atomic<Node*> tail;
11

12
public:
13
    LockFreeQueue() {
14
        Node* sentinel = new Node{};
15
        head.store(sentinel);
16
        tail.store(sentinel);
17
    }
18

19
    void enqueue(T value) {
20
        Node* node = new Node{value};
21
        Node* old_tail = tail.load(std::memory_order_acquire);
22

23
        while (true) {
24
            Node* next = old_tail->next.load(std::memory_order_acquire);
25
            if (next == nullptr) {
26
                // 尝试链接新节点
27
                Node* null = nullptr;
28
                if (old_tail->next.compare_exchange_strong(
29
                    null, node,
30
                    std::memory_order_release,
31
                    std::memory_order_relaxed)) {
32
                    // 成功，尝试推进 tail
33
                    tail.compare_exchange_strong(
34
                        old_tail, node,
35
                        std::memory_order_release,
36
                        std::memory_order_relaxed);
37
                    return;
38
                }
39
            } else {
40
                // tail 落后了，帮助推进
41
                tail.compare_exchange_strong(
42
                    old_tail, next,
43
                    std::memory_order_release,
44
                    std::memory_order_relaxed);
45
            }
46
            old_tail = tail.load(std::memory_order_acquire);
47
        }
48
    }
49
};

1
// Treiber 无锁栈（简化版）
2
template<typename T>
3
class LockFreeStack {
4
    struct Node {
5
        T data;
6
        Node* next;
7
    };
8

9
    std::atomic<Node*> head{nullptr};
10

11
public:
12
    void push(T value) {
13
        Node* node = new Node{value, head.load()};
14
        while (!head.compare_exchange_strong(node->next, node,
15
            std::memory_order_release, std::memory_order_relaxed)) {
16
            // CAS 失败：head 已被其他线程修改，重试
17
        }
18
    }
19

20
    bool pop(T& result) {
21
        Node* old_head = head.load(std::memory_order_acquire);
22
        while (old_head && !head.compare_exchange_strong(
23
            old_head, old_head->next,
24
            std::memory_order_acquire, std::memory_order_relaxed)) {
25
            // CAS 失败：head 已被其他线程修改
26
        }
27
        if (!old_head) return false;  // 栈空
28
        result = old_head->data;
29
        //  这里存在 ABA 问题：old_head 可能已被其他线程 pop 后又 push 回来
30
        delete old_head;  // 需要 Hazard Pointer 或版本号保护
31
        return true;
32
    }
33
};

1
// ABA 问题：CAS 无法区分值的变化历史
2
// 1. 线程 1 读取 *addr = A
3
// 2. 线程 2 将 *addr 从 A 改为 B
4
// 3. 线程 2 将 *addr 从 B 改回 A
5
// 4. 线程 1 执行 CAS(A, C) → 成功！但数据已被修改过
6

7
// 解决方案 1：版本号
8
struct TaggedPointer {
9
    void* ptr;
10
    uint64_t tag;  // 每次修改递增
11
};
12

13
// 解决方案 2：Hazard Pointer
14
// 在访问共享节点前，先注册 hazard pointer
15
// 其他线程在释放节点前检查是否有 hazard pointer 指向它
16

17
// 解决方案 3：RCU（Read-Copy-Update）
18
// 读者无锁访问旧版本
19
// 写者创建新版本，通过 RCU 机制等待所有读者切换

1
// Linux 内核 RCU 使用
2
// 读者：无锁访问
3
rcu_read_lock();
4
struct data* d = rcu_dereference(global_ptr);
5
// 使用 d...
6
rcu_read_unlock();
7

8
// 写者：创建新版本并替换
9
struct data* new_data = kmalloc(sizeof(*new_data), GFP_KERNEL);
10
*new_data = *old_data;
11
new_data->field = new_value;
12
rcu_assign_pointer(global_ptr, new_data);
13
synchronize_rcu();  // 等待宽限期
14
kfree(old_data);

1
// Hazard Pointer 示意（简化版）
2
// 每个线程拥有 MAX_HAZARD 个危险指针槽位
3
constexpr int MAX_HAZARD = 2;
4
std::atomic<void*> hazard_ptrs[MAX_THREADS][MAX_HAZARD];
5

6
// 读者：注册 hazard pointer
7
void* node = head.load();
8
hazard_ptrs[my_thread][0].store(node);  // 声明"我正在用 node"
9
// ... 使用 node ...
10
hazard_ptrs[my_thread][0].store(nullptr);  // 用完了，释放声明
11

12
// 写者：删除节点前检查
13
void retire_node(void* node) {
14
    retired_list.push(node);
15
    if (retired_list.size() > threshold) {
16
        scan_retired();  // 遍历所有线程的 hazard pointer
17
        // 只释放没有任何 hazard pointer 指向的节点
18
    }
19
}

1
// 定义 Per-CPU 变量
2
DEFINE_PER_CPU(int, my_counter);  // 每个 CPU 一个 int 副本
3

4
// 更新：只访问本 CPU 的副本，无需原子操作
5
this_cpu_inc(my_counter);  // 等价于 my_counter[cpu]++，无缓存行弹跳
6

7
// 读取全局值：需要遍历所有 CPU 的副本
8
int total = 0;
9
for_each_possible_cpu(cpu) {
10
    total += per_cpu(my_counter, cpu);
11
}

1
#include <urcu.h>
2
#include <urcu-pointer.h>
3

4
struct data* global_ptr;
5

6
// 读者
7
void reader() {
8
    rcu_read_lock();
9
    struct data* d = rcu_dereference(global_ptr);
10
    // 使用 d... 无锁，零开销
11
    rcu_read_unlock();
12
}
13

14
// 写者
15
void writer(struct data* new_data) {
16
    struct data* old = rcu_xchg_pointer(&global_ptr, new_data);
17
    synchronize_rcu();  // 等待所有读者退出
18
    free(old);
19
}