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

What is the Re-entrant lock and concept in general?

提问by vehomzzz

I always get confused. Would someone explain what Reentrantmeans in different contexts? And why would you want to use reentrant vs. non-reentrant?

我总是很困惑。有人会解释Reentrant在不同上下文中的含义吗？为什么要使用可重入与不可重入？

Say pthread (posix) locking primitives, are they re-entrant or not? What pitfalls should be avoided when using them?

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

Is mutex re-entrant?

互斥量是可重入的吗？

回答by ConcernedOfTunbridgeWells

Re-entrant locking

重入锁

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 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 use case for re-entrant locking

可重入锁定的用例

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.

• You 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.

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

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

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

In this situation, keeping track of what locks you've already acquired is expensive. Assuming you want 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.

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

Re-entrant mutexes

可重入互斥体

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 the POSIX threads API does offer the option of re-entrant and non re-entrant mutexes.

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

回答by Henk Holterman

A re-entrant lock lets you write a method Mthat puts a lock on resource Aand then call Mrecursively or from code that already holds a lock on A.

可重入锁使您可以编写一个方法M，该方法将锁定资源A，然后M递归调用或从已经持有锁定的代码调用A。

With a non re-entrant lock, you would need 2 versions of M, one that locks and one that doesn't, and additional logic to call the right one.

使用不可重入锁，您将需要 2 个版本M，一个锁定，一个不锁定，以及调用正确的附加逻辑。

回答by Ratna Beresford

Reentrant lock is very well described in this tutorial.

重入锁在本教程中有很好的描述。

The example in the tutorial is far less contrived than in the answer about traversing a graph. A reentrant lock is useful in very simple cases.

本教程中的示例远没有关于遍历图的答案那么做作。重入锁在非常简单的情况下很有用。

回答by Rick

The what and why of recursive mutexshould not be such a complicated thing described in the accepted answer.

递归互斥锁的内容和原因不应该是已接受的答案中描述的如此复杂的事情。

I would like to write down my understanding after some digging around the net.

我想在网上挖掘一番后写下我的理解。

---

---

First, you should realize that when talking about mutex, multi thread concepts is definitely involved too. (mutex is used for synchronization. I don't need mutex if I only have 1 thread in my program)

首先，您应该意识到在谈论mutex 时，肯定也涉及多线程概念。（互斥锁用于同步。如果我的程序中只有 1 个线程，我不需要互斥锁）

---

---

Secondly, you should know the difference bewteen a normal mutexand a recursive mutex.

其次，您应该知道普通互斥锁和递归互斥锁之间的区别。

Quoted from APUE:

引用自APUE：

(A recursive mutex is a) A mutex type that allows the same threadto lock it multiple times without first unlocking it.

（递归互斥是 a）一种互斥类型，它允许同一线程在不先解锁的情况下多次锁定它。

The key difference is that within the same thread, relock a recursive lock does not lead to deadlock, neither block the thread.

关键区别在于，在同一个线程内，relock一个递归锁不会导致死锁，也不会阻塞线程。

Does this mean that recusive lock never causes deadlock?
No, it can still cause deadlock as normal mutex if you have locked it in one thread without unlocking it, and try to lock it in other threads.

这是否意味着递归锁永远不会导致死锁？
不，如果您将它锁定在一个线程中而不解锁它，它仍然会像普通互斥锁一样导致死锁，并尝试将它锁定在其他线程中。

Let's see some code as proof.

让我们看一些代码作为证明。

1. normal mutex with deadlock

1. 带死锁的普通互斥锁

#include <pthread.h>
#include <stdio.h>

pthread_mutex_t lock;


void * func1(void *arg){
    printf("thread1\n");
    pthread_mutex_lock(&lock);
    printf("thread1 hey hey\n");

}


void * func2(void *arg){
    printf("thread2\n");
    pthread_mutex_lock(&lock);
    printf("thread2 hey hey\n");
}

int main(){
    pthread_mutexattr_t lock_attr;
    int error;
//    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_DEFAULT);
    if(error){
        perror(NULL);
    }

    pthread_mutex_init(&lock, &lock_attr);

    pthread_t t1, t2;

    pthread_create(&t1, NULL, func1, NULL);
    pthread_create(&t2, NULL, func2, NULL);

    pthread_join(t2, NULL);

}

output:

输出：

thread1
thread1 hey hey
thread2

common deadlock example, no problem.

常见的死锁例子，没问题。

1. recursive mutex with deadlock

2. 带有死锁的递归互斥锁

Just uncomment this line
error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
and comment out the other one.

只需取消注释这一行
error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
并注释掉另一行。

output:

输出：

thread1
thread1 hey hey
thread2

Yes, recursive mutex can also cause deadlock.

是的，递归互斥锁也会导致死锁。

1. normal mutex, relock in the same thread

3. 普通互斥锁，在同一个线程中重新锁定

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

pthread_mutex_t lock;


void func3(){
    printf("func3\n");
    pthread_mutex_lock(&lock);
    printf("func3 hey hey\n");
}

void * func1(void *arg){
    printf("thread1\n");
    pthread_mutex_lock(&lock);
    func3();
    printf("thread1 hey hey\n");

}


void * func2(void *arg){
    printf("thread2\n");
    pthread_mutex_lock(&lock);
    printf("thread2 hey hey\n");
}

int main(){
    pthread_mutexattr_t lock_attr;
    int error;
//    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_DEFAULT);
    if(error){
        perror(NULL);
    }

    pthread_mutex_init(&lock, &lock_attr);

    pthread_t t1, t2;

    pthread_create(&t1, NULL, func1, NULL);
    sleep(2); 
    pthread_create(&t2, NULL, func2, NULL);

    pthread_join(t2, NULL);

}

output:

输出：

thread1
func3
thread2

Deadlock in thread t1, in func3.
(I use sleep(2)to make it easier to see that the deadlock is firstly caused by relocking in func3)

陷入僵局thread t1，在func3。
（我用来sleep(2)更容易看出死锁首先是由重新锁定引起的func3）

1. recursive mutex, relock in the same thread

4. 递归互斥锁，在同一个线程中重新锁定

Again, uncomment the recursive mutex line and comment out the other line.

再次，取消对递归互斥体行的注释并注释掉另一行。

output:

输出：

thread1
func3
func3 hey hey
thread1 hey hey
thread2

Deadlock in thread t2, in func2. See? func3finishes and exits, relocking does not block the thread or lead to deadlock.

陷入僵局thread t2，在func2。看？func3完成并退出，重新锁定不会阻塞线程或导致死锁。

---

---

So, last question, why do we need it ?

那么，最后一个问题，我们为什么需要它？

For recursive function (called in multi-threaded programs and you want to protect some resource/data).

对于递归函数（在多线程程序中调用并且您想保护一些资源/数据）。

E.g. You have a multi thread program, and call a recursive function in thread A. You have some data that you want to protect in that recursive function, so you use the mutex mechanism. The execution of that function is sequential in thread A, so you would definitely relock the mutex in recursion. Use normal mutex causes deadlocks. And resursive mutexis invented to solve this.

例如，您有一个多线程程序，并在线程 A 中调用了一个递归函数。您有一些要在该递归函数中保护的数据，因此您使用了互斥机制。该函数的执行在线程 A 中是顺序的，因此您肯定会在递归中重新锁定互斥锁。使用普通互斥锁会导致死锁。而递归互斥体就是为了解决这个问题而发明的。

See an example from the accepted answer When to use recursive mutex?.

请参阅已接受答案中的示例 何时使用递归互斥锁？.

The Wikipedia explains the recursive mutex very well. Definitely worth for a read. Wikipedia: Reentrant_mutex

维基百科很好地解释了递归互斥锁。绝对值得一读。维基百科：Reentrant_mutex