Есть ли гонка данных?

Question

class Test { 
    struct hazard_pointer { 
     std::atomic<void*> hp; 
     std::atomic<std::thread::id> id; 
    }; 

    hazard_pointer hazard_pointers[max_hazard_pointers]; 

    std::atomic<void*>& get_hazard_pointer_for_current_thread(){ 
     std::thread::id id = std::this_thread::get_id(); 
     for(int i =0; i < max_hazard_pointers; i++){ 
      if(hazard_pointers[i].id.load() == id){ 
       hazard_pointers[i].id.store(id); 
       return hazard_pointers[i].hp; 
      } 
     } 
    std::atomic<nullptr> ptr; 
    return ptr; 
    } 
}; 

int main() { 
Test* t =new Test(); 
std::thread t1([&t](){ while(1) t->get_hazard_pointer_for_current_thread();}); 
     std::thread t2([&t](){ while(1) t->get_hazard_pointer_for_current_thread();}); 
t1.join(); 
t2.join(); 
return 0; 
} 

Функция get_hazard_pointer_for_current_thread может выполняться параллельно. Есть data race? На моем глазе нет data race из-за атомной операции, но я не уверен.

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

Предположим, что элементы массива hazard_pointers инициализированы.

Answer 1

Я не думаю, что у вас есть C++ UB от параллельного доступа к неатомным данным, но похоже, что у вас есть the normal kind of race condition в вашем коде.

if (x==a) x = b почти всегда должен быть атомарным чтение-модификация-запись (вместо отдельных атомных нагрузок и атомных магазинов) в алгоритмах безблокировочного, если нет какой-то причине, почему это нормально по-прежнему хранить b если x изменено на что-то другое чем a между чеком и магазином.

(В этом случае единственное, что может быть сохранено, это значение, которое уже было там, как указывает @MargaretBloom. Таким образом, нет «ошибки», просто куча бесполезных магазинов, если это единственный код что касается массива. Я предполагаю, что вы на самом деле не намерены писать бесполезный пример, поэтому я рассматриваю это ошибку.)

---

программирования безблокировочного не так просто, даже если вы сделайте это низкопроизводительным способом со значением по умолчанию std::memory_order_seq_cst для всех магазинов, поэтому компилятор должен MFENCE всюду. Создание всего atomic позволяет избежать C++ UB; вам все равно придется тщательно разрабатывать логику вашего алгоритма, чтобы убедиться, что она правильная, даже если несколько магазинов/загрузок из других потоков (потоков) становятся видимыми между каждой вашей собственной операцией и т. д. (например, см. Preshing's lock-free hash table.) .)

Необходимо быть свободным от UB (по крайней мере теоретически), но определенно недостаточно для правильного/безопасного кода. Быть без гонок означает отсутствие (проблематичных) рас даже между атомными доступами. Это более сильная, но все же недостаточная часть отсутствия ошибок.

Я говорю «в теории», потому что на практике много кода с UB происходит, чтобы скомпилировать то, что мы ожидаем, и будем укусить вас только на других платформах или с будущими компиляторами или с другим окружающим кодом, который предоставляет UB во время оптимизации.

Тестирование не может легко обнаружить все ошибки, особенно. если вы только тестируете на сильно упорядоченном оборудовании x86, но простая ошибка, подобная этому, должна быть легко обнаружима при тестировании.

---

Проблема с кодом, более подробно:

Вы делаете неатомарные сравнения-обмен, с атомной нагрузкой и отдельным атомным магазином:

 if(hazard_pointers[i].id.load() == id){ 
      // a store from another thread can become visible here 
      hazard_pointers[i].id.store(id); 
      return hazard_pointers[i].hp; 
     } 

.store() должен быть std::compare_exchange_strong, поэтому значение не изменяется, если хранилище из другого потока изменило значение между вашей загрузкой и вашим магазином. (Помещение внутри if на расслабленную или приобретаемую нагрузку по-прежнему является хорошей идеей, я думаю, что ветка, чтобы избежать lock cmpxchg, является хорошей идеей, если вы ожидаете, что значение не будет соответствовать большую часть времени. Это должно позволить оставаться в кеш-строках Shared, когда нить не находит совпадение по этим элементам.)

Answer 2

Есть несколько ошибок в коде:

1. get_hazard_pointer_for_current_thread может не возвращать никакого значения - неопределенное поведение.
2. hazard_pointers Элементы массива не инициализируются.
3. if(hazard_pointers[i].id.load() == id) hazard_pointers[i].id.store(id); не имеет никакого смысла.

---

И да, есть гонки данных. Между заявлением if(hazard_pointers[i].id.load() == id) и hazard_pointers[i].id.store(id); другой поток может измениться hazard_pointers[i].id. Вероятно, вам нужно использовать команду сравнения и замены.