c - 用 C 语言调试 Lamport 烘焙算法的简化版本

Question

我正在尝试用 C 语言实现 Lamport 烘焙算法的简化版本，然后再尝试使用它来解决更复杂的问题。*我所做的简化是锁仅由两个线程共享，而不是由两个线程共享。 N.

我设置了两个线程(通过 OpenMP 以保持简单)，它们循环，尝试增加其关键部分内的共享计数器。如果一切按计划进行，那么最终的计数器值应该等于迭代次数。但是，这里有一些示例输出:

count: 9371470 (expected: 10000000)

哦!有些东西坏了，但是什么？我的实现非常像教科书( for reference )，所以也许我滥用了内存屏障？我是否忘记将某些内容标记为 volatile ？

我的代码:

#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <omp.h>

typedef struct
{
    volatile bool entering[2];
    volatile uint32_t number[2];
} SimpleBakeryLock_t;

inline void mb() { __sync_synchronize(); }

inline void lock(SimpleBakeryLock_t* l, int id)
{
    int i = id, j = !id;
    uint32_t ni, nj;

    l->entering[i] = true;
    mb();

    ni = 1 + l->number[j];
    l->number[i] = ni;
    mb();

    l->entering[i] = false;
    mb();

    while (l->entering[j]) {
        mb();
    }

    nj = l->number[j];
    mb();
    while ((nj != 0) && (nj < ni || (nj == ni && j < i)))
    {
        nj = l->number[j];   // re-read
        mb();
    }
}

inline void unlock(SimpleBakeryLock_t* l, int id)
{
    l->number[id] = 0;
    mb();
}

SimpleBakeryLock_t x;

int main(void)
{
    const uint32_t iterations = 10000000;
    uint32_t count = 0;

    bool once = false;
    int i;

    memset((void*)&x, 0, sizeof(x));
    mb();

    // set OMP_NUM_THREADS=2 in your environment!
    #pragma omp parallel for schedule(static, 1) private(once, i)
    for(uint32_t dummy = 0; dummy < iterations; ++dummy)
    {
        if (!once)
        {
            i = omp_get_thread_num();
            once = true;
        }

        lock(&x, i);
        {

            count = count + 1;
            mb();
        }
        unlock(&x, i);
    }

    printf("count: %u (expected: %u)\n", count, iterations);

    return 0;
}

要编译并运行(在 Linux 上)，请执行以下操作:

$ gcc -O3 -fopenmp bakery.c
$ export OMP_NUM_THREADS=2
$ ./a.out

• 我打算将简单的 Bakery 锁链接成二叉树(锦标赛风格)，以实现 N 个线程之间的互斥。

Answer 1

我找到了两个问题，代码现在可以工作了。问题:

1. __sync_synchronize() 未在我的平台(Apple 的 GCC 4.2.1)上生成 mfence 指令。用显式 mfence 替换 __sync_synchronize() 可以解决此问题。
2. 我对 OpenMP 私有(private)变量做了一些错误(仍然不确定是什么......)。有时，两个线程以相同的身份进入锁(例如，都可能说它们是线程 0)。在每次迭代中用“omp_get_thread_num”重新计算“i”似乎可以解决问题。

为了完整性，以下是更正后的代码:

#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <omp.h>

#define cpu_relax() asm volatile ("pause":::"memory")
#define mb() asm volatile ("mfence":::"memory")

/* Simple Lamport bakery lock for two threads. */
typedef struct
{
    volatile uint32_t entering[2];
    volatile uint32_t number[2];
} SimpleBakeryLock_t;

void lock(SimpleBakeryLock_t* l, int id)
{
    int i = id, j = !id;
    uint32_t ni, nj;

    l->entering[i] = 1;
    mb();

    ni = 1 + l->number[j];
    l->number[i] = ni;
    mb();

    l->entering[i] = 0;
    mb();

    while (l->entering[j]) {
        cpu_relax();
    }

    do {
        nj = l->number[j];
    } while ((nj != 0) && (nj < ni || (nj == ni && j < i)));
}

void unlock(SimpleBakeryLock_t* l, int id)
{
    mb();  /* prevent critical section writes from leaking out over unlock */
    l->number[id] = 0;
    mb();
}

SimpleBakeryLock_t x;

int main(void)
{
    const int32_t iterations = 10000000;
    int32_t dummy;
    uint32_t count = 0;

    memset((void*)&x, 0, sizeof(x));
    mb();

    // set OMP_NUM_THREADS=2 in your environment!
    #pragma omp parallel for schedule(static, 1)
    for(dummy = 0; dummy < iterations; ++dummy)
    {
        int i = omp_get_thread_num();
        lock(&x, i);
        count = count + 1;
        unlock(&x, i);
    }

    printf("count: %u (expected: %u)\n", count, iterations);

    return 0;
}