Блокировка пекарни при использовании внутри структуры не работает - PullRequest
Новая
       12

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

1 голос
/ 11 февраля 2012

Я новичок в многопоточном программировании, и я пытался закодировать Алгоритм блокировки хлебобулочных изделий в 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);                                              
    }

После того, как все потоки были выполнены, результатом общего counter будет 10 * 100 = 1000, который является ожидаемым значением. Я выполнил свою программу несколько раз, и результат всегда был 1000. Таким образом, кажется, что реализация блокировки является правильной. Это казалось странным из-за предыдущего вопроса , который у меня был, потому что я не использовал никаких барьеров / ограждений памяти. Мне просто повезло ?

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

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") в разных точках моего кода, но это не помогло)?

1 Ответ

1 голос
/ 11 февраля 2012

При pthreads стандарт гласит, что доступ к varable в одном потоке, в то время как другой поток изменяет или может изменить его, является неопределенным поведением.Ваш код делает это повсюду.Например: 

  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.)

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

...