MCS锁实现中的问题

Question

我正试图用atomics在C++中实现MCS锁。但不幸的是，线程陷入了死锁。一个线程正在等待获取方法中的标志变为false，而第二个线程被卡在release中的do while循环中。因此，问题必须是以原子方式存储/加载下一个节点。有什么想法来调试这个或者我做错了什么吗？

到目前为止，这就是我所拥有的：

#include <atomic>
#include <iostream>
#include <omp.h>

struct qnode {
  std::atomic<qnode *> next;
  std::atomic<bool> wait;
};

class mcs_lock {
  std::atomic<qnode *> tail;

public:
  void acquire(qnode *p) {
    p->next.store(nullptr);
    p->wait.store(true);

    qnode *prev = tail.exchange(p, std::memory_order_acq_rel);

    if (prev) {
      prev->next.store(p, std::memory_order_release);

      /* spin */
      while (p->wait.load(std::memory_order_acquire))
        ;
    }
  }

  void release(qnode *p) {
    qnode *succ = p->next.load(std::memory_order_acquire);

    if (!succ) {
      if (tail.compare_exchange_strong(p, nullptr, std::memory_order_acq_rel))
        return;

      do {
        succ = p->next.load(std::memory_order_acquire);
      } while (succ == nullptr);
    }

    succ->wait.store(false, std::memory_order_release);
  }
};

int main() {
  mcs_lock lock;
  qnode p;
  int counter = 0;

#pragma omp parallel for default(none) private(p) shared(lock, counter)
  for (int i = 0; i < 100000; i++) {
    lock.acquire(&p);
    ++counter;
    lock.release(&p);
  }

  std::cout << "counter=" << counter << "\n";

  return 0;
}

Answer 1

问题在于发布实现中的问题：

    if (!succ) {
      // if this compare-exchange fails, it loads the new value of tail
      // and stores it in p
      if (tail.compare_exchange_strong(p, nullptr, std::memory_order_acq_rel))
        return;

      do {
        succ = p->next.load(std::memory_order_acquire);
      } while (succ == nullptr);
    }

如注释所示，失败的比较-交换覆盖p中的值。当然，这就是为什么下面的循环没有像预期的那样终止的原因。修复非常简单：

    if (!succ) {
      auto expected = p;
      if (tail.compare_exchange_strong(expected, nullptr, std::memory_order_acq_rel))
        return;

      do {
        succ = p->next.load(std::memory_order_acquire);
      } while (succ == nullptr);
    }