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

by

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

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

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.

More Related Contents:

  1. Difference between -pthread and -lpthread while compiling
  2. Recursive Lock (Mutex) vs Non-Recursive Lock (Mutex)
  3. What is a deadlock?
  4. How efficient is locking an unlocked mutex? What is the cost of a mutex?
  5. Can x86 reorder a narrow store with a wider load that fully contains it?
  6. How efficient is locking and unlocked mutex? What is the cost of a mutex?
  7. Is Pthread library actually a user thread solution?
  8. Which is more efficient, basic mutex lock or atomic integer?
  9. Is there an advantage to use a Synchronized Method instead of a Synchronized Block?
  10. Volatile vs. Interlocked vs. lock
  11. what is the correct way to implement a QThread… (example please…)
  12. std::lock_guard or std::scoped_lock?
  13. How would you implement your own reader/writer lock in C++11?
  14. What is thread contention?
  15. Does a locked object stay locked if an exception occurs inside it?
  16. Does an x86 CPU reorder instructions?
  17. How to set the stacksize with C++11 std::thread
  18. What is a “thread” (really)?
  19. Difference between the TPL & async/await (Thread handling)
  20. How, if at all, do Erlang Processes map to Kernel Threads?
  21. How to detect and debug multi-threading problems?
  22. Thread references require static lifetime?
  23. Does multithreading make sense for IO-bound operations?
  24. How do you query a pthread to see if it is still running?
  25. Spring @Async limit number of threads
  26. Does an asynchronous call always create/call a new thread?
  27. Is it better to use TThread’s “Synchronize” or use Window Messages for IPC between main and child thread?
  28. What happens when different CPU cores write to the same RAM address without synchronization?
  29. If a synchronized method calls another non-synchronized method, is there a lock on the non-synchronized method
  30. Simple Deadlock Examples

Leave a Comment