マルチスレッドでリンクリストキューを消費する

Question

C++でOpenMP並列処理ライブラリを学習しています。私は基本的な概念を持っていると感じ、リンクリストキューを実装して自分の知識をテストしようとしました。私は、複数のスレッドからキューを消費したかったのです。

ここでの課題は、同じノードを2回消費しないことです。だから私はスレッド間でキューを共有することを検討していましたが、一度に1つのスレッドのみを更新して（キュー内の次のノードに移動する）ことができます。この目的のために、私はクリティカルまたはロックを使用することができます。しかし、それらを使用せずに。どういうわけか、それは完全に働いているようです。競合状態は発生していません。

#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); 
} 

出力は次のようになります。

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 

私はスレッドと、多くの異なる回数でこれを実行しようとしました。しかし、私は競争状態や何か間違ったものを得ることができませんでした。私は2つの異なるスレッドが「削除」を呼び出し、単一のノードを2回処理することが可能であると考えていました。しかし、それは起こらなかった。どうして？

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

Answer 1

まず第一に、あなたはテストを通して正しいことが、マルチスレッドコードを証明することはできません。ロック/クリティカルセクションが必要なあなたの勘は正しいです。

あなたのテストは特にキューで簡単です。すぐに、次の休憩あなたのキュー：

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

しかし、あなたは、このテストコードを正しく万回を実行キューを作った場合は、再度、」doesnの次の興味深い結果例えば

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同期プリミティブまたはそれらを使用するライブラリに固執する必要があります。