重入锁

可重入锁是一种进程可以多次声明锁而不阻塞自身的锁.在不容易跟踪您是否已经拿到锁的情况下，它很有用.如果一个锁是不可重入的，你可以抓住这个锁，然后在你再次抓住它时阻塞，有效地死锁你自己的进程.

A reentrant lock is one where a process can claim the lock multiple times without blocking on itself. It's useful in situations where it's not easy to keep track of whether you've already grabbed a lock. If a lock is non re-entrant you could grab the lock, then block when you go to grab it again, effectively deadlocking your own process.

一般而言，可重入性是代码的一种属性，它没有中间可变状态，如果在执行时调用代码，则可能会损坏该状态.这样的调用可以由另一个线程进行，也可以由源自代码本身的执行路径递归进行.

Reentrancy in general is a property of code where it has no central mutable state that could be corrupted if the code was called while it is executing. Such a call could be made by another thread, or it could be made recursively by an execution path originating from within the code itself.

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

If the code relies on shared state that could be updated in the middle of its execution it is not re-entrant, at least not if that update could break it.

重入锁的用例

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

A (somewhat generic and contrived) example of an application for a re-entrant lock might be:

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

• You have some computation involving an algorithm that traverses a graph (perhaps with cycles in it). A traversal may visit the same node more than once due to the cycles or due to multiple paths to the same node.

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

The data structure is subject to concurrent access and could be updated for some reason, perhaps by another thread. You need to be able to lock individual nodes to deal with potential data corruption due to race conditions. For some reason (perhaps performance) you don't want to globally lock the whole data structure.

您的计算无法保留有关您访问过哪些节点的完整信息，或者您使用的数据结构不允许快速回答我以前来过这里"问题.

这种情况的一个例子是 Dijkstra 算法的简单实现，其中优先级队列实现为二进制堆，或使用简单链表作为队列的广度优先搜索.在这些情况下，扫描队列以查找现有插入是 O(N) 并且您可能不想在每次迭代时都这样做.

Your computation can't retain complete information on what nodes you've visited, or you're using a data structure that doesn't allow 'have I been here before' questions to be answered quickly.

An example of this situation would be a simple implementation of Dijkstra's algorithm with a priority queue implemented as a binary heap or a breadth-first search using a simple linked list as a queue. In these cases, scanning the queue for existing insertions is O(N) and you may not want to do it on every iteration.

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

In this situation, keeping track of what locks you've already acquired is expensive. Assuming you want to do the locking at the node level a re-entrant locking mechanism alleviates the need to tell whether you've visited a node before. You can just blindly lock the node, perhaps unlocking it after you pop it off the queue.

重入互斥锁

一个简单的互斥体是不可重入的，因为在给定的时间只能有一个线程在临界区.如果您获取互斥锁然后尝试再次获取它，一个简单的互斥锁没有足够的信息来判断之前谁持有它.要以递归方式执行此操作，您需要一种机制，其中每个线程都有一个令牌，以便您可以判断谁获取了互斥锁.这使得互斥机制的开销更大一些，因此您可能不想在所有情况下都这样做.

A simple mutex is not re-entrant as only one thread can be in the critical section at a given time. If you grab the mutex and then try to grab it again a simple mutex doesn't have enough information to tell who was holding it previously. To do this recursively you need a mechanism where each thread had a token so you could tell who had grabbed the mutex. This makes the mutex mechanism somewhat more expensive so you may not want to do it in all situations.

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

IIRC the POSIX threads API does offer the option of re-entrant and non re-entrant mutexes.