Reentrant mutex

In computer science, a reentrant mutex is a mutual exclusion, recursive lock mechanism. In a reentrant mutex, the same thread can acquire the lock multiple times. However, the lock must be released the same number of times or else other threads will be unable to acquire the lock. It has some similarities to a counting semaphore.

Recursive locks (also called recursive thread mutex) are those that allow a thread to recursively acquire the same lock that it is holding. Note that this behavior is different from a normal lock. In the normal case if a thread that is already holding a normal lock attempts to acquire the same lock again, then it will deadlock. Recursive locks behave exactly like normal locks when another thread tries to acquire a lock that is already being held. Note that the recursive lock is said to be released if and only if the number of times it has been acquired matches the number of times it has been released by the owner thread. Many operating systems do not provide these recursive locks natively. Hence, it is necessary to emulate the behavior using primitive non-recursive mutexes (locks).

A big form of criticism on recursive mutexes is that when used in combination with condition variables, the semantics are not clearly defined. For example, if a condition variable could not recursively unlock the mutex, then the system could run into a deadlock. On the other hand, if the mutex was recursively unlocked, it would unlock all critical sections, even though simple inspection of code wouldn't reveal this. Therefore, several implementations, such as the mutexes and condition variables used inside the FreeBSD kernel, don't allow waiting on a condition variable if the calling process has acquired more than one lock.

The Java language's native synchronization mechanisms have used recursive locks since Java's inception. Syntactically, a lock is a block of code with the 'synchronized' keyword preceding it and any Object reference in parentheses that will be used as the mutex. Inside the synchronized block, the given object can be used as a condition variable by doing a wait(), notify(), or notifyAll() on it. Thus all Objects are both recursive mutexes and condition variables. The newer Java versions provide additional primitives in the form of AtomicIntegers and AtomicBooleans and so on, which are lower-level and faster, and which can be used to construct spin-lock types of structures that allow multi-core programming, where mutexes and condition variables fail.

Example

  1. Thread A calls function F which acquires a reentrant lock for itself before proceeding
  2. Thread B calls function F which attempts to acquire a reentrant lock for itself but cannot due to one already outstanding, resulting in either a block (it waits), or a timeout if requested
  3. Thread A's F calls itself recursively. It already owns the lock, so it will not block itself (no deadlock). This is the central idea of a reentrant mutex, and is what makes it different from a regular lock.
  4. Thread B's F is still waiting, or has caught the timeout and worked around it
  5. Thread A's F finishes and releases its lock(s)
  6. Thread B's F can now acquire a reentrant lock and proceed if it was still waiting

Software emulation

Software emulation can be accomplished using the following structure:

Acquisition

  1. Acquire the control condition.
  2. If the owner is set and not the current thread, wait for the control condition to be notified (this also releases the condition).
  3. Set the owner to the current thread. The owner identifier should have already been cleared at this point unless the acquirer is already the owner.
  4. Increment the acquisition count (should always result in 1 for new owners).
  5. Release the control condition.

Release

  1. Acquire the control condition, asserting that the owner is the releaser.
  2. Decrement the acquisition count, asserting that the count is greater than or equal to zero.
  3. If the acquisition count is zero, clear the owner information and notify the control condition.
  4. Release the control condition.