时间戳

首页 > 解决方案 > 我们需要多少内存屏障来实现一个 Peterson 锁？

c++ - 我们需要多少内存屏障来实现一个 Peterson 锁？

问题描述

我试图弄清楚我们需要多少内存栅栏来实现彼得森锁。显然，我们至少需要一个。

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

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

我试过下面的代码

我的 peterson_lock 在这种情况下失败了

将 Mark A 与 Mark B 之间的顺序更改为有效！但是，内存栅栏并没有捕捉到 Mark A 和 Mark 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”行的顺序后，我希望程序几乎总是正确运行，因为它现在与彼得森锁上的 Wikipedia 条目一致。

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

但是，内存栅栏并没有保护 Mark A 和 Mark B 之间的顺序。因此，还有可能是程序不正确吗？如果是这样，如何解决？

标签： c++x86mutexmemory-barriers

解决方案

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

您对彼得森锁的实现不正确（在交换“标记为 A”和“标记为 B”行之后）。
如果将 Wikipedia 伪代码翻译为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;
}

除了使用volatileon helock变量之外，mfence指令 (in peterson_lock) 是防止 #StoreLoad 重新排序所必需的。这显示了一种算法需要顺序一致性的罕见情况。即对lock变量的操作必须以单一的总顺序进行。

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

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

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

推荐阅读