правильное использование compare_exchange_weak

Question

const int SIZE = 20; 
struct Node { Node* next; }; 

std::atomic<Node*> head (nullptr); 
void push (void* p) 
{ 
    Node* n = (Node*) p; 
    n->next = head.load(); 
    while (!head.compare_exchange_weak (n->next, n)); 
} 
void* pop() 
{ 
    Node* n = head.load(); 
    while (n && 
      !head.compare_exchange_weak (n, n->next)); 

    return n ? n : malloc (SIZE); 
} 

void thread_fn() 
{ 
    std::array<char*, 1000> pointers; 

    for (int i = 0; i < 1000; i++) pointers[i] = nullptr; 

    for (int i = 0; i < 10000000; i++) 
    { 
     int r = random() % 1000; 

     if (pointers[r] != nullptr) // allocated earlier 
     { 
      push (pointers[r]); 
      pointers[r] = nullptr; 
     } 
     else 
     { 
      pointers[r] = (char*) pop(); // allocate 

      // stamp the memory 
      for (int i = 0; i < SIZE; i++) 
       pointers[r][i] = 0xEF; 
     } 
    } 
} 


int main(int argc, char *argv[]) 
{ 
    int N = 8; 

    std::vector<std::thread*> threads; 
    threads.reserve (N); 

    for (int i = 0; i < N; i++) 
     threads.push_back (new std::thread (thread_fn)); 

    for (int i = 0; i < N; i++) 
     threads[i]->join(); 
} 

Что не так с этим использованием compare_exchange_weak? Вышеупомянутый код сбрасывается 1 раз в 5 раз с помощью clang ++ (MacOSX).

Глава.load() во время аварии будет иметь «0xEFEFEFEFEFEF». pop походит на malloc и push - это как бесплатный. Каждый поток (8 потоков) случайным образом распределить или освобождать память от head

Answer 1

Это может быть приятно замок свободной Распределитель, но ABA-problem возникают:

: Предположим, что некоторые thread1 выполняет pop(), который читает текущее значение head в n переменная, но сразу же после этого загружается нить и concurrentthread2 выполняет полный код pop(), то есть он читает одно и то же значение от head и осуществляет успешныйcompare_exchange_weak.

B: Теперь объект, называемый по n в thread1, не больше не принадлежал к списку, и может быть изменен thread2. Таким образом, n->next - это мусор вообще: чтение из него может вернуть любое значение. Например, это может быть 0xEFEFEFEFEF, где первые 5 байт марка (EF), ведьма была написана thread2, а последние 3 байта все еще 0 от nullptr. (Общее значение численно интерпретируется в little-endian способ). Кажется, что, поскольку head значение было изменено, thread1 провалит свое compare_exchange_weak вызов, но ...

: Одновременные thread2push() эс привел указатель обратно в список. Таким образом, thread1 видит начальную величину head и выполняет успешную команду compare_exchange_weak, в которой не указан значение head. Список поврежден.

Обратите внимание, что проблема - это больше, чем возможность, что другая нить может изменять содержимое n->next. Проблема в том, что значение n->nextбольше не связано со списком. Таким образом, даже он не изменяется одновременно, он становится недействительным (для замены head) в случае, например, когда другой поток (ы) pop() 2 элемента из списка, но push() назад только первый из них. (So ​​n->next будет указывать на второй элемент, который больше не принадлежит к списку.)