Bakery Lock when used inside a struct doesn't work

Question

I'm new at multi-threaded programming and I tried to code the Bakery Lock Algorithm in C.

Here is the code:

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

Then I run the following example. I run 100 threads and each thread runs the following code:

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

After all threads have been executed, the result of the shared counter is 10 * 100 = 1000 which is the expected value. I executed my program multiple times and the result was always 1000. So it seems that the implementation of the lock is correct. That seemed weird based on a previous question I had because I didn't use any memory barriers/fences. Was I just lucky?

Then I wanted to create a multi-threaded program that will use many different locks. So I created this (full code can be found here):

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

and the code changes to:

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

Now when executing my program, sometimes I get 997, sometimes 998, sometimes 1000. So the lock algorithm isn't correct.

What am I doing wrong? What can I do in order to fix it?

Is it perhaps a problem now that I'm reading arrays number and choosing from a struct and that's not atomic or something?

Should I use memory fences and if so at which points (I tried using asm("mfence") in various points of my code, but it didn't help)?

Answer 1

With pthreads, the standard states that accessing a varable in one thread while another thread is, or might be, modifying it is undefined behavior. Your code does this all over the place. For example:

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

This code accesses choosing[j] over and over while waiting for another thread to modify it. The compiler is entirely free to modify this code as follows:

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

Why? Because the standard is clear that another thread may not modify the variable while this thread may be accessing it, so the value can be assumed to stay the same. But clearly, that won't work.

It can also do this:

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

Same logic. It is perfectly legal for the compiler to write back a variable whether it has been modified or not, so long as it does so at a time when the code could be accessing the variable. (Because, at that time, it's not legal for another thread to modify it, so the value must be the same and the write is harmless. In some cases, the write really is an optimization and real-world code has been broken by such writebacks.)

If you want to write your own synchronization functions, you have to build them with primitive functions that have the appropriate atomicity and memory visibility semantics. You must follow the rules or your code will fail, and fail horribly and unpredictably.