Программирование без блокировки: переупорядочение и семантика порядка памяти

Question

Я пытаюсь найти свои ноги в программировании без блокировки. Прочитав различные объяснения семантики упорядочения памяти, я хотел бы выяснить, что может произойти переупорядочение. Насколько я понял, инструкции могут быть переупорядочены компилятором (из-за оптимизации во время компиляции программы) и ЦП (во время выполнения?).

Для упрощенной семантики ссылка cpp предоставляет следующий пример:

// Thread 1:
r1 = y.load(memory_order_relaxed); // A
x.store(r1, memory_order_relaxed); // B
// Thread 2:
r2 = x.load(memory_order_relaxed); // C 
y.store(42, memory_order_relaxed); // D

Говорят, что при x и y, изначально равных нулю, коду разрешено создавать r1 == r2 == 42, потому что, хотя A секвенируется до B в потоке 1, а C чередуется до D в потоке 2, ничто не мешает D появиться до A в порядке модификации y, и B от появления перед C в порядке изменения x. Как это могло случиться? Означает ли это, что C и D переупорядочиваются, поэтому порядок выполнения будет DABC? Можно ли изменить порядок A и B?

Для семантики acqu-release есть следующий пример кода:

std::atomic<std::string*> ptr;
int data;

void producer()
{
    std::string* p  = new std::string("Hello");
    data = 42;
    ptr.store(p, std::memory_order_release);
}

void consumer()
{
    std::string* p2;
    while (!(p2 = ptr.load(std::memory_order_acquire)))
        ;
    assert(*p2 == "Hello"); // never fires
    assert(data == 42); // never fires
}

Мне интересно, что если бы мы использовали расслабленный порядок памяти вместо приобретения? Я думаю, значение data можно прочитать раньше p2 = ptr.load(std::memory_order_relaxed), но что насчет p2?

Наконец, почему в этом случае хорошо использовать смягченный порядок памяти?

template<typename T>
class stack
{
    std::atomic<node<T>*> head;
 public:
    void push(const T& data)
    {
      node<T>* new_node = new node<T>(data);

      // put the current value of head into new_node->next
      new_node->next = head.load(std::memory_order_relaxed);

      // now make new_node the new head, but if the head
      // is no longer what's stored in new_node->next
      // (some other thread must have inserted a node just now)
      // then put that new head into new_node->next and try again
      while(!head.compare_exchange_weak(new_node->next, new_node,
                                        std::memory_order_release,
                                        std::memory_order_relaxed))
          ; // the body of the loop is empty
    }
};

Я имею в виду оба head.load(std::memory_order_relaxed) а также head.compare_exchange_weak(new_node->next, new_node, std::memory_order_release, std::memory_order_relaxed),

Подводя итог всему вышесказанному, мой вопрос в основном, когда мне нужно заботиться о возможном переупорядочении, а когда нет?

Answer 1

Для #1 компилятор может выдать хранилище для y до загрузки из x (нет никаких зависимостей), и даже если это не так, загрузка из x может быть отложена на уровне процессора / памяти.

Для #2 p2 будет отличным от нуля, но ни *p2, ни данные не обязательно будут иметь значащее значение.

Для #3 существует только один акт публикации неатомарных магазинов, созданных этой веткой, и это релиз

Вы должны всегда заботиться о переупорядочении, или, лучше, не принимать никакого порядка: ни C++, ни аппаратное обеспечение не выполняют код сверху вниз, они только уважают зависимости.