为什么这段代码会导致死锁？

Question

我从 pstack 中看到这段代码导致了死锁，感到惊讶！但我不知道原因。

pthread_mutex_t lock;

_Cilk_for (int i = 0; i < N; ++i) {
  int ai = A[i];
  if (ai < pivot) {
    pthread_mutex_lock(&lock);
    A[ia++] = ai;
    pthread_mutex_unlock(&lock);
  }
  else if (ai > pivot) {
    pthread_mutex_lock(&lock);
    A[ib++] = ai;
    pthread_mutex_unlock(&lock);
  }
  else {
    pthread_mutex_lock(&lock);
    A[ic++] = ai;
    pthread_mutex_unlock(&lock);
  }
}

我只是使用互斥锁来确保对A的访问是原子化和串行化的。

• 这段代码有什么问题会导致死锁？
• 有没有更好的实现方法？

- Lazer

---

旁注：这似乎是一种可怕的实现并行快速排序的方式？ - Mysticial

你是否在 lock 上调用了 pthread_mutex_init 函数？ - Nemo

这段代码不会死锁。死锁需要至少在尝试获取另一个锁时持有一个锁。你从未这样做过。 - Keith Randall

但是，它却在我面前死锁了。 - Lazer

Answer 1

如果这段代码是在函数内部，那么你没有正确初始化互斥锁。你需要将它设置为PTHREAD_MUTEX_INITIALIZER（用于简单的默认互斥锁）或对其进行pthread_mutex_init()（用于更复杂的要求）。如果没有正确初始化，你就不知道互斥锁的初始状态 - 它可能处于锁定状态，只是因为在该位置的堆栈上发生的任何事情看起来像一个已锁定的互斥锁。

这就是为什么它总是需要以某种方式初始化，以确保没有关于初始状态的疑虑。

你可能还会遇到另一个潜在的问题：

int ai = A[i];

由于在更新变量时，另一个线程只完成了部分工作，因此您可能需要使用相同的互斥锁来保护该访问，否则可能会读取到“半状态”。

---

而且，我必须说，我不确定这里是否明智地使用了线程。使用互斥锁可能会使像A[ia++] = ai这样的语句被淹没，以至于绝大部分时间都花费在锁定和解锁互斥锁上。它们通常在处理锁定期间要处理的代码稍微复杂一些时更有用。

您可能会发现非线程化的变体会比这个更快（但是，当然，不要仅凭我的话 - 我的主要优化口号是“测量，不要猜测”）。

- paxdiablo

---

谢谢，这个可行，但我不明白，锁的值有什么影响？ - Lazer

@paxdiablo：不知道为什么缺少init()会导致死锁？我非常确定这是死锁。 - Lazer

@Lazer：是的，如果不按照pthread文档进行适当的初始化，您就无法知道初始状态。我们可能会发现它在锁定状态下启动，只是因为在分配它时堆栈上有这样的内容。请参见更新。 - paxdiablo

Answer 2

您的pthread_mutex_t lock未正确初始化，因此由于它是一个局部变量，可能包含垃圾，并且可能处于奇怪的锁定状态。您应该调用pthread_mutex_init或使用PTHREAD_MUTEX_INITIALIZER初始化您的lock

正如其他人所抱怨的那样，您没有明智地使用互斥锁。您代码的关键部分太小了。

- Basile Starynkevitch

Answer 3

在你修复或确认你确实正在初始化你的lock之后：

pstack可能知道由_Cilk_for引入的控制机制，这些机制会干扰本来合理的pthread代码。

快速搜索显示有用于Cilk的互斥解决方案 - 混合使用Cilk和pthread没有被提及。看起来Cilk是建立在pthread之上的一层 - 因此，如果Cilk选择在mutex周围放置一个包装器，他们很可能有充分的理由这样做。我建议继续使用Cilk API。

除此之外，你的算法存在更根本性的问题。在你的情况下，创建并行线程以及同步它们的开销可能远远超过执行for循环体中的代码的成本。很可能不并行化运行会更快。

- Richard Sitze

---

事实上，对于某些工作负载，这比串行版本慢了10倍。 - Lazer