Peterson锁算法的测试实现？ [英] 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.

推荐答案

我不会对执行的好坏进行任何断言， 。这是wikipedia上描述的算法的直译。

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;
};

Greg指出，在具有轻微内存一致性（例如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.

Jens Gustedt和ninjalj建议修改原始算法使用 atomic_flag 类型。这意味着设置标志和转弯将使用 atomic_flag_test_and_set ，并清除它们将使用C11中的 atomic_flag_clear 。或者，可以在标志的更新之间施加存储器屏障。

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内置函数，但是包装在宏中，以便它可以很容易地更改为一些其他实现。但是，修改上面的原始算法是首选的解决方案。

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);
};

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