0

在尝试使用它解决更复杂的问题之前，我正在尝试在 C 中实现 Lamport's Bakery Algorithm 的简化版本。* 我所做的简化是锁仅由两个线程而不是 N 共享。

我设置了两个线程（通过 OpenMP 使事情变得简单），它们循环，试图在它们的关键部分增加一个共享计数器。如果一切都按计划进行，那么最终的计数器值应该等于迭代次数。但是，这里有一些示例输出：

count: 9371470 (expected: 10000000)

嗬！有些东西坏了，但是什么？我的实现是相当教科书（供参考），所以也许我在滥用内存屏障？我是否忘记将某些内容标记为易失性？

我的代码：

#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 个线程之间的互斥。
4

1 回答 1

1

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

  1. __sync_synchronize() 没有在我的平台（Apple 的 GCC 4.2.1）上生成 mfence 指令。用显式 mfence 替换 __sync_synchronize() 可以解决此问题。
  2. 我对 OpenMP 私有变量做错了什么（仍然不确定是什么......）。有时两个线程以相同的身份进入锁（例如，两者都可能说他们是线程 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;
}
于 2013-06-02T16:40:33.213 回答