c++ - 我们需要多少个内存屏障来实现彼得森锁？

Question

我想弄清楚我们需要多少内存栅栏才能实现 Peterson 锁。显然，我们至少需要一个。

https://bartoszmilewski.com/2008/11/05/who-ordered-memory-fences-on-an-x86/

在实践中，基于在不同架构中执行的大量测试，似乎一个就足够了。但是，理论上，我们是否需要额外的？

我试过下面的代码

my peterson_lock failed in this situation

通过标记 B 更改标记 A 之间的顺序，它起作用了!但是，内存栅栏并没有捕捉到标记 A 和标记 B 之间的顺序。那么，这是否意味着程序仍然不正确？

#include <pthread.h>

typedef struct {
    volatile bool flag[2];
    volatile int victim;
} peterson_lock_t;

void peterson_lock_init(peterson_lock_t &lock) {
    lock.flag[0] = lock.flag[1] = false;
    lock.victim = 0;
}

void peterson_lock(peterson_lock_t &lock, int id) {
    lock.victim = id; // Mark as A
    lock.flag[id] = true; // Mark as B
    asm volatile ("mfence" : : : "memory");
    while (lock.flag[1 - id] && lock.victim == id);
}

void peterson_unlock(peterson_lock_t &lock, int id) {
    lock.flag[id] = false;
    lock.victim = id;
}

替换“标记为 A”和“标记为 B”行的顺序后，我希望程序几乎总是正确运行，因为它现在与维基百科关于彼得森锁的条目一致。

https://en.wikipedia.org/wiki/Peterson%27s_algorithm

但是，内存栅栏并没有保护标记A和标记B之间的顺序，因此，程序是否仍然有可能不正确？如果是，如何解决？

Answer 1

没有人在主流平台上使用 Peterson 锁，因为互斥锁可用。但是假设您不能使用这些并且您正在为旧的 X86 平台编写代码而无法访问现代原语(没有内存模型，没有互斥锁，没有原子 RMW 操作)，则可以考虑使用此算法。

您对 Peterson 锁的实现不正确(在交换行“标记为 A”和“标记为 B”之后)。
如果将维基百科伪代码翻译成 C++，则正确的实现变为:

typedef struct {
    volatile bool flag[2];
    volatile int victim;
} peterson_lock_t;

void peterson_lock(peterson_lock_t &lock, int id) {
    lock.flag[id] = true;
    lock.victim = 1-id;
    asm volatile ("mfence" ::: "memory"); // CPU #StoreLoad barrier
    while (lock.flag[1-id] && lock.victim == 1-id);
}

void peterson_unlock(peterson_lock_t &lock, int id) {
    asm volatile("" ::: "memory"); // compiler barrier
    lock.flag[id] = false;
}

除了在 lock 变量上使用 volatile 外，mfence 指令(在 peterson_lock 中)有必要防止#StoreLoad 重新排序。这显示了算法需要顺序一致性的罕见情况；即，对 lock 变量的操作必须在单个总顺序中进行。

volatile 的使用基于 gcc/X86 上的不可移植(但“几乎”正确)的属性。“‘几乎’正确”因为即使 X86 上的 volatile 存储是 CPU 级别的释放操作，编译器仍然可以对 volatile 上的操作重新排序> 和非 volatile 数据。
出于这个原因，我在 peterson_unlock 中重置 lock.flag[id] 之前添加了一个编译器屏障。

但使用此算法对线程之间共享的所有数据使用 volatile 可能是个好主意，因为编译器仍然可以仅对 CPU 寄存器中的非 volatile 数据执行存储和加载操作。

请注意，通过对共享数据使用 volatile，peterson_unlock 中的编译器屏障变得多余。