0

我正在使用多线程程序中的共享链表。我没有使用锁存器（互斥体），而是依靠 CAS 操作来确保插入和删除的正确性。所有插入和删除都发生在链表（LIFO）的头部。该程序没有按预期工作，它随机导致分段错误并退出。有什么想法吗？这是我的程序的简化版本。大约 1% 的时间它会中断四个线程。

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

我发现了问题。当两个并发线程试图删除头部的同一个节点时。他们都抓住了链表的头部（n = head）。其中一个被挂起，而另一个设法从链表中删除该节点，对其进行处理并删除它。当其他线程试图删除该节点时，它会执行 CAS 操作。CAS 操作的第三个参数 (n->next) 尝试取消引用已被另一个线程删除的指针。我有一个解决这个问题的方法，但是这里太复杂了，无法在这里讨论。

于 2013-03-13T02:08:16.860 回答