multithreading - 可重入锁和一般概念是什么？

Question

我总是感到困惑。有人可以解释一下什么Reentrant在不同的上下文中意味着什么？为什么要使用可重入与不可重入？

假设 pthread (posix) 锁定原语，它们是否是可重入的？使用时应避免哪些陷阱？

互斥体是可重入的吗？

Answer 1

可重入锁定

可重入锁是一种进程可以多次声明锁而不会阻塞自身的锁。在不容易跟踪您是否已经获取锁的情况下，它非常有用。如果锁是不可重入的，您可以抓取该锁，然后在再次抓取它时阻塞，从而有效地使您自己的进程陷入死锁。

重入性通常是代码的一个属性，它没有中央可变状态，如果代码在执行时被调用，则该状态可能会被破坏。这样的调用可以由另一个线程进行，也可以通过源自代码本身的执行路径递归地进行。

如果代码依赖于可以在执行过程中更新的共享状态，则它是不可重入的，至少在更新可能会破坏它的情况下是不可重入的。

可重入锁定的用例

可重入锁应用程序的(有点通用和人为的)示例可能是:

• 您有一些涉及遍历图(可能其中有循环)的算法的计算。由于循环或由于到同一节点的多个路径，遍历可能会多次访问同一节点。

• 数据结构受到并发访问的影响，并且可能由于某种原因(可能由另一个线程)进行更新。您需要能够锁定各个节点以处理由于竞争条件而导致的潜在数据损坏。由于某种原因(也许是性能)，您不想全局锁定整个数据结构。

• 您的计算无法保留有关您访问过的节点的完整信息，或者您使用的数据结构不允许快速回答“我以前来过这里吗”问题。
  
  这种情况的一个例子是 Dijkstra 算法的简单实现，其中优先级队列实现为二叉堆，或者使用简单链表作为队列进行广度优先搜索。在这些情况下，扫描队列中现有插入的时间复杂度为 O(N)，您可能不想在每次迭代时都执行此操作。

在这种情况下，跟踪您已经获取的锁的成本很高。假设您想在节点级别进行锁定，可重入锁定机制可以减轻判断您之前是否访问过节点的需要。您可以盲目锁定节点，也许在将其从队列中弹出后解锁它。

可重入互斥体

简单的互斥体是不可重入的，因为在给定时间只有一个线程可以位于临界区中。如果您获取互斥锁，然后尝试再次获取它，则简单的互斥锁没有足够的信息来判断谁先前持有它。要递归地执行此操作，您需要一种机制，其中每个线程都有一个 token ，以便您可以知道谁获取了互斥体。这使得互斥机制更加昂贵，因此您可能不想在所有情况下都这样做。

IIRC POSIX 线程 API 确实提供了可重入和不可重入互斥体的选项。