3

ReentrantLock allows a thread to acquire the same lock recursively, so that a lock count is incremented and decremented on successive lock/unlock. Whereas the lock count has to be decremented to zero before it is released to other threads.

Why or under what circumstances would I write code to acquire a lock recursively?

The only point I can see in having the feature is to make it convenient for us to write recursive code, where a method (which in the course of its execution acquires a lock) is called recursively.

Are there any other situations where recursive/repeated acquisition of a lock by a thread may be useful ?

Clarification of the question:

  • Please ignore the lock being reentrant. Just so happens that recursivity is provided by reentrant lock.
  • I am referring to the recursive feature of a lock
  • Please do not answer with why use reentrant lock.
  • Please do not answer with "recursivity is not the main feature of reentrant lock"
  • I want to know what situations require the recursive acquisition of a lock, regardless if the lock is reentrant or not.
Community
  • 1
  • 1
Blessed Geek
  • 21,058
  • 23
  • 106
  • 176

1 Answers1

1

Might as well search better: this should be helpful

A use case for re-entrant locking:

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

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

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

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

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

Community
  • 1
  • 1
Muli Yulzary
  • 2,559
  • 3
  • 21
  • 39
  • Apologies for editing your answer, because I needed to refer to the items by their number. – Blessed Geek Oct 24 '14 at 07:07
  • Item 1: Wouldn't it be better to lock the whole tree/graph with a single lock if the traversal has to be atomic? Wouldn't atomically traversing a tree by individually locking nodes run a highly horrendous risk of dead-locking? – Blessed Geek Oct 24 '14 at 07:10
  • Item 2: When I need to acquire three nodes to complete an atomic operation, I would first acquire those nodes. If I failed to acquire the complete set of nodes, I would bail out and release all of them. If it reaches a situation whereby I lose track of the nodes I need to acquire atomically, such that I may acquire it twice due to the complexity of algorithm - that algorithm should be banned unless it is written by superman, ultraman or captain america. – Blessed Geek Oct 24 '14 at 07:17
  • Item 4: Does Dijkstra's algorithm require locking? – Blessed Geek Oct 24 '14 at 07:24
  • My recent project, we had the graph designed with granularity, such that we could lock a graph by regions. We just lock the whole region of a graph. So that at the most we locked three regions, with no risk of acquiring the same lock twice. It is safer to properly design a graph than to haphazardly use an elegantly deadlock-prone locking algorithm. – Blessed Geek Oct 24 '14 at 07:33
  • For every single statement: it depends what you are trying to implement. synchronization is a simple idea but complex to implement. It depends what you are trying to achieve in you particular case. – Muli Yulzary Oct 24 '14 at 09:16