Skip to content
#C++

阻塞与非阻塞算法 & 数据结构

约 1674 个字 25 行代码 预计阅读时间 9 分钟

  • 阻塞的算法和数据结构使用 mutex、条件变量、期值来同步数据，但非阻塞不等价于 lock-free，比如自旋锁没有使用任何阻塞函数的调用，是非阻塞的，但并非 lock-free
  • 非阻塞数据结构由松到严可分为三个等级：
  • obstruction-free（无障碍）：如果其他线程都暂停了，任何一个给定的线程都会在有限步数内完成操作。上例就是这种情况，但这种情况很少见，所以满足这个条件只能算一个失败的 lock-free 实现。
  • lock-free（无锁）：如果多线程在同一个数据结构上操作，其中一个将在有限步数内完成操作。满足 lock-free 必定满足 obstruction-free。
  • wait-free（无等待）：如果多线程在同一个数据结构上操作，每个线程都会在有限步数内完成操作。满足 wait-free 必定满足 lock-free，但 wait-free 很难实现，因为要保证有限步数内完成操作，就要保证操作一次通过，并且执行到某一步不能导致其他线程操作失败。
  • lock-free 数据结构必须允许多线程并发访问，但它们不能做相同操作，比如一个 lock-free 的 queue 允许一个线程 push、另一个线程 pop，但不允许两个线程同时 push。此外，如果一个访问 lock-free 数据结构的线程被中途挂起，其他线程必须能完成操作而不需要等待挂起的线程。

lock-free thread-safe stack

  • pop 返回值应该返回智能指针。
  • 如果直接返回值，返回前一定会先移除元素，如果拷贝返回值时抛出异常，移除的元素就丢失了。
  • 如果传引用，其他线程移除了节点，被移除的节点不能被解引用，当前线程就无法安全地拷贝数据。

Safety Memory Garbage Collection

在有锁的数据结构中，内存回收很简单：当一个节点被从数据结构中移除时，我们可以立即 delete 它，因为持有锁的线程是唯一能访问这个节点的线程。

但在无锁数据结构中，情况完全不同：

  1. 线程 A 想要从栈中 pop 一个节点（比如 Node* old_top）。
  2. 在线程 A 真正 delete old_top 之前，它的时间片用完了，被挂起。
  3. 线程 B 此时可能仍然持有一个指向 old_top 的指针，因为它在线程 A pop 操作开始时也正在访问栈顶。
  4. 如果线程 A 在恢复执行后立即 delete old_top，线程 B 就会访问一个已经被释放的内存（悬挂指针），导致程序崩溃。

所以我们释放内存当且仅当没有任何线程正在访问它时。

Hazard Pointers

code implement

每个线程都有自己的“风险指针列表”

C++
// 全局风险指针数组，存储每个线程的风险指针
static std::atomic<void *> g_hazard_pointers[MAX_THREADS];
// 全局标志，记录哪个槽被哪个线程占用
static std::atomic_flag g_hp_owner_flags[MAX_THREADS];
  • 系统为每一个参与无锁操作的线程分配一个（或多个）风险指针 (Hazard Pointer)。
  • 这些风险指针通常存储在一个全局的、所有线程都可以读取的列表中。
  • 一个风险指针就是一个 void 或 Node，它指向一个内存地址。

“宣告风险”的操作流程

当一个线程（比如线程 A）要访问一个可能被其他线程删除的共享节点（比如 node_p）时，它必须遵循以下流程：

  1. 获取节点指针: 线程 A 首先以某种方式获取了 node_p 的指针（例如，通过原子地读取 stack.top）。
  2. 设置风险指针 (Set Hazard Pointer): 在真正解引用 node_p 之前，线程 A 必须“宣告”它将要访问这个节点。它会把 node_p 的地址写入到它自己的风险指针中。
  3. 验证 (Validation): 这是至关重要的一步，用于解决 ABA 问题。设置完风险指针后，线程 A 必须再次检查它想要访问的节点是否还是原来的那个。如果验证通过，线程 A 就可以安全地访问 node_p 了，因为它已经确保了在它宣告风险之后，这个节点没有被其他线程移除。
C++
// 再次读取栈顶，看它是否已经变了
if (stack.top.load() != node_p) {
  // 如果变了，说明在我宣告风险的瞬间，节点已经被 pop 了。
  // 我宣告的风险无效，必须从头再来。
  thread_local_hazard_pointer.store(nullptr); // 清除风险宣告
  goto retry_loop;
}
  1. 执行操作: 线程 A 现在可以安全地解引用 node_p 并进行操作（例如，读取它的 value 和 next 指针）。
  2. 清除风险指针 (Clear Hazard Pointer): 当线程 A 不再需要访问 node_p 时，它必须清除自己的风险指针，告诉大家它已经用完了。

安全删除节点的流程

当一个线程（比如线程 C）成功地从数据结构中移除了一个节点（比如 removed_node）后，它不能立即 delete 这个节点。
它需要做的是：

  1. (Retire List)”: 线程 C 将 removed_node 的指针添加到一个属于它自己的、私有的“待删除列表”中。
C++
static thread_local std::vector<Node *> retired_list_;
  1. 定期扫描和清理 (Scan and Reclaim): 线程 C 会在某个时刻（比如，当它的待删除列表达到一定大小时）触发一次清理操作。
  • 获取所有风险指针: 它会遍历全局的风险指针列表，收集所有线程当前宣告的所有风险指针，并将它们放入一个集合中。
    C++
    // 全局函数：扫描所有风险指针，返回一个包含所有受保护指针的集合
std::vector<void *> get_all_hazard_pointers() {
  std::vector<void *> pointers;
  for (unsigned i = 0; i < MAX_THREADS; ++i) {
      void *p =
          HazardPointer::g_hazard_pointers[i].load(std::memory_order_acquire);
      if (p) {
          pointers.push_back(p);
      }
  }
  return pointers;
}
  • 检查并删除: 然后，它遍历自己的“待删除列表”。对于列表中的每一个 node_to_delete，它检查这个 node_to_delete 是否存在于刚刚收集的风险指针集合中：
    1. 如果不存在，说明当前没有任何线程正在访问这个节点，可以安全地 delete 它。
    2. 如果存在，说明有其他线程正在访问它，不能删除。这个节点会被保留在待删除列表中，等待下一次清理。

Reference Count

为每个节点增加一个原子引用计数 (Atomic Reference Counter): std::shared_ptr 的操作是原子的，但要检查是否 lock-free

  • 获取指针时增加计数: 当一个线程要访问一个节点时，它会原子地增加该节点的引用计数。
  • 使用完毕后减少计数: 当线程不再需要访问该节点时，它会原子地减少该节点的引用计数。
  • 删除时检查计数: 当一个节点从数据结构中被逻辑上移除（例如，从栈顶 pop 出来）后，执行移除操作的线程会减少其引用计数。如果此时引用计数变为 0，则说明没有任何线程（包括它自己）在引用这个节点，此时可以安全地 delete 它。