c - Bakery Lock 在结构内部使用时不起作用

Question

我是多线程编程的新手，我尝试编写 Bakery Lock Algorithm在 C 中。

代码如下:

int number[N];  // N is the number of threads                                                          
int choosing[N];                

void lock(int id)  {                                                                       
  choosing[id] = 1;                                                         
  number[id] = max(number, N) + 1;                                       
  choosing[id] = 0;                                                         

  for (int j = 0; j < N; j++)                                                   
    {                                                                       
      if (j == id)                                                          
        continue;                                                           

      while (1)                                                             
          if (choosing[j] == 0)                                             
            break;                                                          

      while (1)                                                             
        {                                                                   
          if (number[j] == 0)                                               
            break;                                                          
          if (number[j] > number[id]                                        
              || (number[j] == number[id] && j > id))                       
            break;                                                          
        }                         
    }
}

void unlock(int id)  {
   number[id] = 0;
}

然后我运行以下示例。我运行 100 个线程，每个线程运行以下代码:

  for (i = 0; i < 10; ++i)  {      
      lock(id);                                                                   
      counter++;
      unlock(id);                                              
    }                                                                       

所有线程执行完毕后，共享计数器的结果是10 * 100 = 1000，这是预期值。我多次执行我的程序，结果总是 1000。所以看来锁的实现是正确的。基于 previous question 这似乎很奇怪我有，因为我没有使用任何内存障碍/栅栏。 我只是运气好吗？

然后我想创建一个将使用许多不同锁的多线程程序。所以我创建了这个(完整代码可以在 here 中找到):

typedef struct {                                                            
  int number[N];                                                            
  int choosing[N];                                                          
} LOCK;      

并且代码更改为:

void lock(LOCK l, int id)                                                        
{                                                                           
  l.choosing[id] = 1;                                                                                                          
  l.number[id] = max(l.number, N) + 1;                                                                                            
  l.choosing[id] = 0;                 
...

现在在执行我的程序时，有时我会得到 997，有时会得到 998，有时会得到 1000。所以锁定算法不正确。

我做错了什么？我该怎么做才能修复它？

现在我从 struct 中读取数组 number 和 choosing 可能是个问题吗那不是原子的还是什么？

我应该使用内存栅栏吗？如果是，应该在哪些点使用(我尝试在我的代码的不同点使用 asm("mfence")，但没有帮助)？

Answer 1

对于 pthreads，标准声明在一个线程中访问一个变量而另一个线程正在或可能正在修改它是未定义的行为。您的代码到处都是这样做的。例如:

  while (1)                                                             
      if (choosing[j] == 0)                                             
        break;

这段代码一遍又一遍地访问choosing[j]，同时等待另一个线程修改它。编译器可以完全自由地修改这段代码，如下所示:

int cj=choosing[j];
while(1)
    if(cj == 0)
       break;

为什么？因为标准很明确，当这个线程可能正在访问它时，另一个线程可能不会修改变量，所以可以假定该值保持不变。但显然，这行不通。

它还可以这样做:

while(1)
{
   int cj=choosing[j];
   if(cj==0) break;
   choosing[j]=cj;
}

同样的逻辑。编译器写回一个变量是完全合法的，无论它是否被修改，只要它在代码可以访问该变量的时候这样做。 (因为在那个时候，另一个线程修改它是不合法的，所以值必须相同并且写入是无害的。在某些情况下，写入确实是一种优化，现实世界的代码已经被这样破坏了回写。)

如果您想编写自己的同步函数，则必须使用具有适当原子性和内存可见性语义的原始函数来构建它们。您必须遵守规则，否则您的代码将失败，并且失败得可怕且不可预测。