MCS 锁定实现的问题

Question

我正在尝试在C++与原子学实现MCS锁。但不幸的是，线程陷入了僵局。一个线程正在等待 catch 方法中的标志变为 false，而第二个线程则停在释放方法中的 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);
}