0

マルチスレッド プログラムで共有リンク リストを使用しています。ラッチ (ミューテックス) を使用する代わりに、挿入と削除の正確性を確保するために CAS 操作に依存しています。すべての挿入と削除は、リンクされたリスト (LIFO) の先頭で行われます。プログラムが期待通りに動作せず、ランダムにセグメンテーション違反を引き起こし、終了します。何かご意見は？これが私のプログラムの簡略化されたバージョンです。約 1% の確率で 4 つのスレッドで中断します。

struct Node {
  unsigned long num;
  Node* next;
};

Node* head = NULL;

#define NUM_THREADS 4L
#define Rounds 10000L
#define Iterations 100L
#define SumPerRound ((Iterations-1)*Iterations/2)
#define SumPerThread (SumPerRound * Rounds)
#define ExpectedSum (SumPerThread * NUM_THREADS)

unsigned long totalSum = 0;
void* Worker(void*) {
  for (unsigned int r = 0; r < Rounds; r++) {
    for (unsigned int i = 0; i < Iterations; i++) {
      Node* n = new Node();
      n-> num = i;
      do {
        n->next = head;
      } while (!__sync_bool_compare_and_swap(&head, n->next, n));
    }

    for (unsigned int i = 0; i < Iterations; i++) {
      Node* n;
      do {
        n = head;
        assert(n);
      } while (!__sync_bool_compare_and_swap(&head, n, n->next));
      __sync_fetch_and_add(&totalSum, n->num);
      delete n;
    }
  }
  return NULL;
}
4

1 に答える 1

0

問題が見つかりました。2 つの同時スレッドが先頭で同じノードを削除しようとした場合。どちらも連結リストの先頭 (n = 先頭) を取得します。それらの 1 つが一時停止され、もう 1 つがこのノードをリンクされたリストから削除し、処理して削除します。他のスレッドがそのノードを削除しようとすると、CAS 操作が実行されます。CAS 操作 (n->next) の 3 番目の引数は、他のスレッドによって削除されたポインターを逆参照しようとします。この問題の解決策はありますが、ここで説明するには複雑すぎます。

于 2013-03-13T02:08:16.860 に答える