Bakery блокировки при использовании внутри структуры не работает

Question

Я новичок в многопоточном программировании, и я пытался кодировать Bakery Lock Algorithm в C.

Вот код:

Тогда Я приведу следующий пример. Я бегу 100 потоков и каждый поток работает следующий код:

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

После того как все нити были выполнены, результат общего counter является 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. Поэтому алгоритм блокировки неверен.

Что я делаю неправильно? Что я могу сделать, чтобы исправить это?

Это, возможно, проблема теперь, когда я читаю массивы number и choosing из struct и это не атомная или что-то?

Должен ли я использовать заграждения памяти, и если да, то в каких точках (я пытался использовать 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; 
} 

Та же логика. Для компилятора совершенно законно записывать переменную, была ли она изменена или нет, если это происходит в то время, когда код мог получить доступ к переменной.(Потому что в то время для другого потока не разрешено изменять его, поэтому значение должно быть одинаковым, а запись безвредна. В некоторых случаях написание действительно представляет собой оптимизацию, и код реального мира был нарушен такими writebacks.)

Если вы хотите написать свои собственные функции синхронизации, вы должны создать их с помощью примитивных функций, которые имеют соответствующую семантику атомарности и памяти. Вы должны следовать правилам или ваш код будет сбой и неудачный и непредсказуемый.