经过测试的实施彼得森锁的算法？ [英] A tested implementation of Peterson Lock algorithm?

问题描述

有谁知道一个良好的/正确的实现用C Peterson的锁算法的？我似乎无法找到。谢谢你。

Does anyone know of a good/correct implementation of Peterson's Lock algorithm in C? I can't seem to find this. Thanks.

推荐答案

我不会做出有关如何实施好或改正任何断言，但它是测试（简述）。这是在维基百科中描述的算法的直接翻译。

I won't make any assertions about how good or correct the implementation is, but it was tested (briefly). This is a straight translation of the algorithm described on wikipedia.

struct petersonslock_t {
    volatile unsigned flag[2];
    volatile unsigned turn;
};
typedef struct petersonslock_t petersonslock_t;

petersonslock_t petersonslock () {
    petersonslock_t l = { { 0U, 0U }, ~0U };
    return l;
}

void petersonslock_lock (petersonslock_t *l, int p) {
    assert(p == 0 || p == 1);
    l->flag[p] = 1;
    l->turn = !p;
    while (l->flag[!p] && (l->turn == !p)) {}
};

void petersonslock_unlock (petersonslock_t *l, int p) {
    assert(p == 0 || p == 1);
    l->flag[p] = 0;
};

格雷格指出与略微宽松存储器一致性（例如x86）在SMP结构，虽然负载到同一存储器位置是在顺序，负载在一个处理器上的不同位置，可能会出现不按顺序的其他处理器

Greg points out that on an SMP architecture with slightly relaxed memory coherency (such as x86), although the loads to the same memory location are in order, loads to different locations on one processor may appear out of order to the other processor.

延Gustedt和ninjalj建议修改原始算法使用 atomic_flag 键入。这意味着，设置标志和转弯会使用 atomic_flag_test_and_set 和清除它们会使用 atomic_flag_clear 从C11。另外，内存屏障可更新之间被征收人标志。

Jens Gustedt and ninjalj recommend modifying the original algorithm to use the atomic_flag type. This means setting the flags and turns would use the atomic_flag_test_and_set and clearing them would use atomic_flag_clear from C11. Alternatively, a memory barrier could be imposed between updates to flag.

编辑：我本来试图通过写入同一个存储单元的所有状态，以纠正这一点。 ninjalj指出，位操作打开的状态的操作成RMW而不是原来的算法的负荷和商店。因此，需要原子位操作。 C11提供了这样的运营商，如内置插件确实GCC。下面的算法使用GCC内置插件，但包裹在宏，以便它可以容易地被改变，以某些其它的实现。然而，上述修改原来的算法是preferred解决方案。

I originally attempted to correct for this by writing to the same memory location for all the states. ninjalj pointed out that the bitwise operations turned the state operations into RMW rather than load and stores of the original algorithm. So, atomic bitwise operations are required. C11 provides such operators, as does GCC with built-ins. The algorithm below uses GCC built-ins, but wrapped in macros so that it can easily be changed to some other implementation. However, modifying the original algorithm above is the preferred solution.

struct petersonslock_t {
    volatile unsigned state;
};
typedef struct petersonslock_t petersonslock_t;

#define ATOMIC_OR(x,v)   __sync_or_and_fetch(&x, v)
#define ATOMIC_AND(x,v)  __sync_and_and_fetch(&x, v)

petersonslock_t petersonslock () {
    petersonslock_t l = { 0x000000U };
    return l;
}

void petersonslock_lock (petersonslock_t *l, int p) {
    assert(p == 0 || p == 1);
    unsigned mask = (p == 0) ? 0xFF0000 : 0x00FF00;
    ATOMIC_OR(l->state, (p == 0) ? 0x000100 : 0x010000);
    (p == 0) ? ATOMIC_OR(l->state, 0x000001) : ATOMIC_AND(l->state, 0xFFFF00);
    while ((l->state & mask) && (l->state & 0x0000FF) == !p) {}
};

void petersonslock_unlock (petersonslock_t *l, int p) {
    assert(p == 0 || p == 1);
    ATOMIC_AND(l->state, (p == 0) ? 0xFF00FF : 0x00FFFF);
};

这篇关于经过测试的实施彼得森锁的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！