MCS 锁实现的问题

Question

我正在尝试使用原子在 C++ 中实现 MCS 锁。但不幸的是，线程陷入了死锁。一个线程在 acquire 方法中等待标志变为 false，而第二个线程在 release 方法中卡在 do while 循环中。所以问题肯定在storing/loading下一个节点原子。任何想法如何调试这个或我做错了什么？

这是我目前拥有的：

#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);
    }

MCS 锁实现的问题

Problems with MCS lock implementation

c++

multithreading

locking

openmp