并发编程之ABA问题

实习日记
830 words

ABA问题是并发编程中一个经典的问题，尤其在使用无锁数据结构时容易发生。它源于变量值经历了”A→B→A”的变化序列，导致程序逻辑误判状态未改变。以下是详细解析：

ABA问题的定义

当某个线程执行CAS（Compare-and-Swap）操作时：

  1. 线程1读取共享变量的值为A
  2. 线程2将值修改为B，随后又改回A
  3. 线程1再次检查时发现值仍是A，认为未被修改，继续执行操作

此时程序逻辑可能因中间状态变化而出现错误。

典型案例（链表删除场景）

假设一个无锁链表结构：

1
2
3
4
5
struct Node {
    int value;
    Node* next;
};
Node* head;  // 全局头指针

线程1操作：

  1. 读取当前头节点指针old_head = head（地址0x1000，值A）
  2. 准备将头指针更新为new_head = old_head->next

线程2操作：

  1. 删除头节点0x1000，释放内存
  2. 新建节点0x2000（值B），插入链表头部
  3. 再次删除0x2000，分配新节点0x1000（值C，但地址与旧节点相同）插入头部

结果：
线程1执行CAS(&head, old_head, new_head)时，发现head仍是0x1000，误以为链表未变化，实际上：

  • 原0x1000节点已被释放
  • 新0x1000节点的数据可能已不同

ABA的危害

危害类型 具体表现
数据损坏 操作已释放的内存，导致数据结构逻辑错误
内存泄漏 错误地重复释放同一块内存
程序崩溃 访问已被其他线程回收的内存区域
逻辑错误 状态机错误推进（如错误认为资源未被修改）

解决方案

带标签的指针（Tagged Pointer）

  • 原理：在指针的低位添加版本号标签（通常利用指针对齐的冗余位）
  • 实现：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    struct TaggedPtr {
        Node* ptr;
        uint64_t tag;  // 使用指针未使用的低位存储
    };

    bool CAS(TaggedPtr* dest, TaggedPtr old_val, TaggedPtr new_val) {
        // 同时比较指针和标签
        return __atomic_compare_exchange(dest, &old_val, &new_val, false, 
                                        __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE);
    }
  • 优势：硬件级原子操作支持（x86的CMPXCHG16B指令）

危险指针（Hazard Pointer）

  • 原理：线程声明正在使用的指针，延迟内存释放
  • 步骤：
    1. 线程访问指针时，将其注册到全局危险指针列表
    2. 释放内存前检查所有危险指针是否引用该内存
    3. 无引用时安全释放，否则加入待释放队列稍后处理

RCU（Read-Copy-Update）

  • 原理：通过写时复制和宽限期确保读操作安全
  • 流程：
    1. 写线程创建数据副本并修改
    2. 原子替换指针指向新副本
    3. 等待所有正在读旧数据的线程退出临界区后，释放旧数据

内存回收器（Epoch-Based Reclamation）

1
2
3
4
5
6
7
// 伪代码示例
void worker_thread() {
    enter_epoch();  // 进入当前epoch
    // 执行操作...
    leave_epoch();  // 退出epoch
    // 后台线程定期回收不再被任何epoch引用的内存
}

各方案性能对比

方案 内存开销 吞吐量 适用场景
标签指针 低 极高 x86-64平台，需要硬件支持
危险指针 中 高 通用无锁数据结构
RCU 高 中 读多写少，Linux内核常用
内存回收器 中 高 复杂无锁结构，如数据库索引
Comments