Используя эти атомарные операции с упорядоченным порядком памяти и rel / acq, как показано, работает ли этот фрагмент кода C ++? - PullRequest
Новая
       52

Используя эти атомарные операции с упорядоченным порядком памяти и rel / acq, как показано, работает ли этот фрагмент кода C ++?

1 голос
/ 05 мая 2019

Написано в псевдокоде cppmem: 

int main()                                                                                                                                                                                   
{                                                                                                                                                                                            
  atomic_int n = -1;                                                                                                                                                                         
  atomic_int n2 = 0;                                                                                                                                                                         

  {{{                                                                                                                                                                                        
      {                                                                                                                                                                                      
        n2.store(1, mo_relaxed);                                                                                                                                                             
        if (n.load(mo_relaxed) != -1)                                                                                                                                                        
          n.store(1, mo_release);                                                                                                                                                            
      }                                                                                                                                                                                      
  |||                                                                                                                                                                                        
      {                                                                                                                                                                                      
        n.store(0, mo_release);                                                                                                                                                              
        int expected = 0;                                                                                                                                                                    
        do                                                                                                                                                                                   
        {                                                                                                                                                                                    
          desired = n2.load(mo_relaxed);                                                                                                                                                     
        }                                                                                                                                                                                    
        while (!n.compare_exchange_strong(&expected, desired, mo_acquire));                                                                                                                  
      }                                                                                                                                                                                      
  }}}                                                                                                                                                                                        

  assert(n == 1);                                                                                                                                                                            
}

Словом, две атомные переменные инициализируются как n = -1 и n2 = 0;

Поток 1 сначала записывает 1 в n2, а затем в n, при условии, что n не было (все еще) -1.

Поток 2 сначала записывает 0 в n, затем загружает n2 и назначает n = n2 до тех пор, пока n не изменилось с момента последнего чтения n (или когда n по-прежнему равно 0).

После объединения обоих потоков n должно равняться 1 в каждом возможном выполнении.

Этот код является частью моего проекта с открытым исходным кодом и связан со сбросом реализации streambuf к началу буфера без блокировки, в то время как два потока одновременно читают и записывают в него. Эта конкретная часть связана с «синхронизацией» (или очисткой записанного вывода).

Я разработал это, и оно работает, когда каждая операция последовательно согласована (это было проверено методом грубой силы), но я не могу обернуться вокруг требований к порядку памяти: /.

Ответы [ 2 ]

1 голос
/ 05 мая 2019

Это утверждение может сработать, если инструкции (и обновления кэша) выполняются в следующем порядке:

  • Первые потоки выполняют все свои инструкции.Так что просто измените значение n2 с 0 на 1.
  • Затем потоки 2 запустятся.Сначала он меняет значение n с -1 на 0.
  • Затем потоки 2 загружают n2 (в n2.load(mo_relaxed)).На данный момент синхронизации нет, поэтому можно загрузить любое значение, ранее сохраненное в n2 (включая значение инициализации, см. [intro.race] / 1 ).Допустим, он загружает 0.
  • Таким образом, значения переменных потоков 2 равны n==0 (последнее в порядке изменения n), n2==0, expected==0, desired==0 передсравнить инструкцию по обмену.Затем обмен сравнениями завершается успешно и сохраняет 0 в n.

В конце выполнения двух потоков вы получаете n==0 и n2==1.

При последовательной согласованности то, что я описал, не может произойти, потому что если поток 1 видел n2==1 && n==-1, поток 2 не мог видеть n2==0 && n==0.

С этим алгоритмом я уверен, что невозможно использовать любой другой порядок памятичем последовательная последовательность.

0 голосов
/ 06 мая 2019

Используя инструмент, который я нашел на https://plv.mpi -sws.org / rcmc / Я смог экспериментально обнаружить, что самые непринужденные требования:

Резьба1: 

n2.store(1, std::memory_order_seq_cst);
if (n.load(std::memory_order_seq_cst) != -1)
  n.store(1, std::memory_order_release);

Резьба2: 

n.store(0, std::memory_order_seq_cst);
int expected = 0;
int desired;
do
{
    desired = n2.load(std::memory_order_seq_cst);
}
while (!n.compare_exchange_strong(expected, desired,
    std::memory_order_acquire, std::memory_order_relaxed));

EDIT:

Более поздний инструмент тех же авторов (что также, конечно, лучше) теперь можно загрузить с https://github.com/MPI-SWS/genmc

Этот инструмент оказывается чрезвычайно быстрым и полезным, даже для тестирования реальных алгоритмов, которые используют слабо упорядоченные атомы, как, например, я здесь делаю: genmc_buffer_reset_test.c

# include в данной строке - это сгенерированные файлы C, извлеченные из моего кода C ++ и преобразованные в C с помощью сценариев awk, поскольку мне кажется, что genmc может (к сожалению) использоваться только для кода C (?).

...