다중 스레드에서 연결 목록 대기열 사용

Question

C++에서 OpenMP 병렬 처리 라이브러리를 배우고 있습니다. 기본적인 개념을 가지고 있고 링크 된 목록 큐를 구현하여 지식을 테스트하려고했습니다. 여러 스레드에서 큐를 소비하려고했습니다.

여기서 도전은 동일한 노드를 두 번 사용하지 않는 것입니다. 그래서 스레드간에 큐를 공유하는 것을 고려하고 있었지만 한 번에 하나의 스레드 만 업데이트 (큐의 다음 노드로 이동) 할 수있었습니다. 이 목적을 위해 나는 치명적이거나 잠금을 사용할 수 있습니다. 그러나, 그들을 사용하지 않고; 어쨌든, 그것은 완벽하게 작동하는 것 같습니다. 경쟁 조건이 발생하지 않았습니다.

#include <iostream> 
#include <omp.h> 
#include <zconf.h> 


struct Node { 
    int data; 
    struct Node* next = NULL; 
    Node() {} 
    Node(int data) { 
     this->data = data; 
    } 
    Node(int data, Node* node) { 
     this->data = data; 
     this->next = node; 
    } 
}; 

void processNode(Node *pNode); 

struct Queue { 
    Node *head = NULL, *tail = NULL; 

    Queue& add(int data) { 
     add(new Node(data)); 
     return *this; 
    } 

    void add(Node *node) { 
     if (head == NULL) { 
      head = node; 
      tail = node; 
     } else { 
      tail->next = node; 
      tail = node; 
     } 
    } 

    Node* remove() { 
     Node *node; 
      node = head; 
     if (head != NULL) 
      head = head->next; 

     return node; 
    } 

}; 

int main() { 
    srand(12); 
    Queue queue; 
    for (int i = 0; i < 6; ++i) { 
     queue.add(i); 
    } 

    double timer_started = omp_get_wtime(); 
    omp_set_num_threads(3); 
    #pragma omp parallel 
    { 
     Node *n; 
     while ((n = queue.remove()) != NULL) { 
      double started = omp_get_wtime(); 
      processNode(n); 
      double elapsed = omp_get_wtime() - started; 
      printf("Thread id: %d data: %d, took: %f \n", omp_get_thread_num(), n->data, elapsed); 
     } 
    } 
    double elapsed = omp_get_wtime() - timer_started; 

    std::cout << "end. took " << elapsed << " in total " << std::endl; 
    return 0; 
} 

void processNode(Node *node) { 
    int r = rand() % 3 + 1; // between 1 and 3 
    sleep(r); 
} 

출력은 다음과 같습니다 : I 스레드 여러 번 다른 번호로이를 실행했습니다

Thread id: 0 data: 0, took: 1.000136 
Thread id: 2 data: 2, took: 1.000127 
Thread id: 2 data: 4, took: 1.000208 
Thread id: 1 data: 1, took: 3.001371 
Thread id: 0 data: 3, took: 2.001041 
Thread id: 2 data: 5, took: 2.004960 
end. took 4.00583 in total 

. 그러나 나는 어떤 경쟁 조건이나 잘못된 것을 얻을 수 없었다. 두 개의 다른 스레드가 '제거'를 호출하고 단일 노드를 두 번 처리하는 것이 가능하다고 생각했습니다. 그러나 그것은 일어나지 않았다. 왜?

https://github.com/muatik/openmp-examples/blob/master/linkedlist/main.cpp

Answer 1

가장 먼저, 당신은 테스트을 통해 올바른으로 멀티 스레드 코드를 증명할 수 없다. 귀하의 직감, 잠금/중요 섹션이 필요합니다 맞습니다.

테스트는 특히 대기열에서 쉽습니다. 빨리 다음 휴식 대기열 :

Thread 1 processed 11133 nodes. 
Thread 0 processed 9039 nodes. 

그러나이 테스트 코드 제대로 만 번을 실행 큐를 만든 경우 다시, '아무튼 다음 흥미로운 결과 예를 들어

for (int i = 0; i < 10000; ++i) { 
    queue.add(i); 
} 

double timer_started = omp_get_wtime(); 
#pragma omp parallel 
{ 
    size_t counter = 0; 
    Node *n; 
    while ((n = queue.remove()) != NULL) { 
     processNode(n); 
     counter++; 
    } 

    #pragma omp critical 
    std::cout << "Thread " << omp_get_thread_num() << " processed " << counter << " nodes." << std::endl; 
} 

void processNode(Node *node) {} 

보기 t는 큐가 올바르게 구현되었음을 의미합니다.

특히, remove을 보호하는 것만으로는 충분하지 않습니다. 큐의 모든 읽기 및 쓰기를 올바르게 보호해야합니다. 이 권리를 얻는 데 어려움이 있는지 알아 보려면 excellent talk by Herb Sutter을 보시기 바랍니다.

일반적으로 기존 병렬 데이터 구조를 사용하는 것이 좋습니다 (예 : Boost.Lockfree).

그러나 불행히도 OpenMP 및 C++11 lock/atomic primitives don't officially play well together. 엄밀히 말하자면 OpenMP를 사용한다면 OpenMP 동기화 프리미티브 또는이를 사용하는 라이브러리에 집중해야합니다.