lock_free concurrent data structure

阻塞的算法和数据结构使用 mutex、条件变量、期值来同步数据,但非阻塞不等价于 lock-free,比如自旋锁没有使用任何阻塞函数的调用,是非阻塞的,但并非 lock-free

非阻塞数据结构由松到严可分为三个等级:obstruction-free、lock-free、wait-free

  • obstruction-free(无障碍):如果其他线程都暂停了,任何一个给定的线程都会在有限步数内完成操作。
  • lock-free(无锁):如果多线程在同一个数据结构上操作,其中一个将在有限步数内完成操作。(其他线程等待)
  • wait-free(无等待):如果多线程在同一个数据结构上操作,每个线程都会在有限步数内完成操作。

lock-free 数据结构必须允许多线程并发访问,但它们不能做相同操作,比如一个 lock-free 的 queue 允许一个线程 push、另一个线程 pop,但不允许两个线程同时 push。

此外,如果一个访问 lock-free 数据结构的线程被中途挂起,其他线程必须能完成操作而不需要等待挂起的线程

使用 lock-free 数据结构主要是为了最大化并发访问,不需要阻塞。

第二个原因是鲁棒性,如果线程在持有锁时死掉就会导致数据结构被永久破坏,而对 lock-free 数据结构来说,除了死掉的线程里的数据,其他的数据都不会丢失。lock-free 没有任何锁,所以一定不会出现死锁

但 lock-free 可能造成更大开销,用于 lock-free 的原子操作比非原子操作慢得多,且 lock-free 数据结构中的原子操作一般比 lock-based 中的多, 此外,硬件必须访问同一个原子变量以在线程间同步数据。

无论 lock-free 还是 lock-based,性能方面的检查(最坏情况等待时间、平均等待时间、总体执行时间)都是非常重要的

lock-free thread-safe stack

  • 最简单的 stack 实现方式是包含头节点指针的链表。push 的过程很简单,创建一个新节点,然后让新节点的 next 指针指向当前 head,最后 head 设为新节点
  • 这里的 race condition 在于,如果两个线程同时 push,让各自的新节点的 next 指针指向当前 head,这样必然导致 head 最终设为二者之一的新节点,而另一个被丢弃
  • 解决方法是,在最后设置 head 时先进行判断,只有当前 head 与新节点的 next 相等,才将 head 设为新节点,如果不等则让 next 指向当前 head 并重新判断。而这个操作必须是原子的,因此就需要使用 compare_exchange_weak,不需要使用 compare_exchange_strong,因为 compare_exchange_weak 在相等时可能替换失败,但替换失败也会返回 false,放在循环里带来的效果是一样的,而 compare_exchange_weak 在一些机器架构上可以产生比 compare_exchange_strong 更优化的代码
#include <atomic>

template <typename T>
class LockFreeStack {
 public:
  void push(const T& x) {
    Node* t = new Node(x);
    t->next = head_.load();
    while (!head_.compare_exchange_weak(t->next, t)) {
    }
  }

 private:
  struct Node {
    T v;
    Node* next = nullptr;
    Node(const T& x) : v(x) {}
  };

 private:
  std::atomic<Node*> head_;
};
  • pop 的过程很简单,先存储当前头节点指针,再将头节点设为下一节点,最后返回存储的头节点并删除指针。这里的 race condition 在于,如果两个线程同时 pop,如果一个已经删除了头节点,另一个线程读取头节点的下一节点就访问了空悬指针
  • 先绕开删除指针这一步,考虑前几步的实现
template <typename T>
void LockFreeStack<T>::pop(T& res) {
  Node* t = head_.load();  // 未考虑头节点为空指针的情况
  while (!head_.compare_exchange_weak(t, t->next)) {
  }
  res = t->v;
}
  • 但传引用的问题是,如果其他线程移除了节点,被移除的节点不能被解引用,当前线程就无法安全地拷贝数据。因此,如果想安全地返回值,应该返回智能指针
#include <atomic>
#include <memory>

template <typename T>
class LockFreeStack {
 public:
  void push(const T& x) {
    Node* t = new Node(x);
    t->next = head_.load();
    while (!head_.compare_exchange_weak(t->next, t)) {
    }
  }

  std::shared_ptr<T> pop() {  // 还未考虑释放原来的头节点指针
    Node* t = head_.load();
    while (t && !head_.compare_exchange_weak(t, t->next)) {
    }
    return t ? t->v : nullptr;
  }

 private:
  struct Node {
    std::shared_ptr<T> v;
    Node* next = nullptr;
    Node(const T& x) : v(std::make_shared<T>(x)) {}
  };

 private:
  std::atomic<Node*> head_;
};
  • 释放被移除的节点的难点在于,一个线程在释放内存时,无法得知其他线程是否持有要释放的指针
  • 只要没有其他线程调用 pop,就能安全释放,因此可以用一个计数器来记录调用 pop 的线程数,计数不为 1 时,先把节点添加到待删除节点列表中,计数为 1 则安全释放
#include <atomic>
#include <memory>

template <typename T>
class LockFreeStack {
 public:
  void push(const T& x) {
    Node* t = new Node(x);
    t->next = head_.load();
    while (!head_.compare_exchange_weak(t->next, t)) {
    }
  }

  std::shared_ptr<T> pop() {
    ++pop_cnt_;
    Node* t = head_.load();
    while (t && !head_.compare_exchange_weak(t, t->next)) {
    }
    std::shared_ptr<T> res;
    if (t) {
      res.swap(t->v);
    }
    try_delete(t);
    return res;
  }

 private:
  struct Node {
    std::shared_ptr<T> v;
    Node* next = nullptr;
    Node(const T& x) : v(std::make_shared<T>(x)) {}
  };

 private:
  static void delete_list(Node* head) {
    while (head) {
      Node* t = head->next;
      delete head;
      head = t;
    }
  }

  void append_to_delete_list(Node* first, Node* last) {
    last->next = to_delete_list_;
    // 确保 last->next 为 to_delete_list_,再设置 first 为新的头节点
    while (!to_delete_list_.compare_exchange_weak(last->next, first)) {
    }
  }

  void append_to_delete_list(Node* head) {
    Node* last = head;
    while (Node* t = last->next) {
      last = t;
    }
    append_to_delete_list(head, last);
  }

  void try_delete(Node* head) {
    if (pop_cnt_ == 0) {
      return;
    }
    if (pop_cnt_ > 1) {
      append_to_delete_list(head, head);
      --pop_cnt_;
      return;
    }
    Node* t = to_delete_list_.exchange(nullptr);
    if (--pop_cnt_ == 0) {
      delete_list(t);
    } else if (t) {
      append_to_delete_list(t);
    }
    delete head;
  }

 private:
  std::atomic<Node*> head_;
  std::atomic<std::size_t> pop_cnt_;
  std::atomic<Node*> to_delete_list_;
};

如果要释放所有节点,必须有一个时刻计数器为 0。在高负载的情况下,往往不会存在这样的时刻,从而导致待删除节点的列表无限增长

Hazard Pointer(风险指针)

  • 另一个释放的思路是,在线程访问节点时,设置一个保存了线程 ID 和该节点的风险指针。用一个全局数组保存所有线程的风险指针,释放节点时,如果数组中不存在包含该节点的风险指针,则可以直接释放,否则将节点添加到待删除列表中。风险指针实现如下
  • 风险指针实现简单并达到了安全释放的目的,但每次删除节点前后都要遍历数组并原子访问内部指针来检查,增加了很多开销
  • 无锁内存回收技术领域十分活跃,大公司都会申请自己的专利,风险指针包含在 IBM 提交的专利申请中,在 GPL 协议下允许免费使用

引用计数

  • 另一个方案是使用引用计数记录访问每个节点的线程数量,std::shared_ptr 的操作是原子的,但要检查是否 lock-free
  • C++20 支持 std::atomicstd::shared_ptr
  • 更通用的方法是手动管理引用计数,为每个节点设置内外部两个引用计数,两者之和就是节点的引用计数,外部计数默认为 1,访问对象时递增外部计数并递减内部计数,访问结束后则不再需要外部计数,将外部计数减 2 并加到内部计数上
  • 不指定内存序则默认使用开销最大的 std::memory_order_seq_cst,下面根据操作间的依赖关系优化为最小内存序

原文链接: https://www.cnblogs.com/lygin/p/17134476.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

    lock_free concurrent data structure

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/319124

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年2月24日 下午3:10
下一篇 2023年2月24日 下午3:11

相关推荐