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

Question

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

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

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

我试过下面的代码

通过标记 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;
}

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

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

但是内存栅栏并没有保护Mark A和Mark B之间的顺序，所以程序是否还有可能出错？如果是，如何解决？

Answer 1

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

您对 Peterson 锁的实现不正确（在交换行 'Mark as A' 和 'Mark as 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 的使用基于 non-portable（但 'almost' 正确）gcc/X86 的属性。 “'almost' 正确”因为即使 X86 上的 volatile 存储是 CPU 级别的释放操作，编译器仍然可以对 volatile 和非-volatile数据。
出于这个原因，我在 peterson_unlock.

中重置 lock.flag[id] 之前添加了一个编译器屏障

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

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

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

How many memory barriers do we need to implement a Peterson lock?

c++

x86

mutex

memory-barriers