Reentrant mutex

In computer science, the reentrant mutex (also known as a recursive mutex or recursive lock) is a synchronization primitive that may be locked multiple times by the same thread without causing a deadlock.

While a thread that attempts to lock a standard (non-reentrant) mutex that it already holds would block indefinitely, this operation succeeds on a reentrant mutex. This is achieved by associating the mutex with the thread that owns it and maintaining a lock count. The owning thread can acquire the lock multiple times, incrementing the count each time. The lock is only released for other threads to acquire once the owning thread has unlocked it the same number of times it was acquired, bringing the count to zero.

Motivation

A reentrant mutex solves deadlocks that can occur when a function needs to acquire a lock that is already held by the same thread. This often happens in recursive code or when one function that acquires a lock calls another function that must acquire the same lock.

Recursive mutexes solve the problem of non-reentrancy with regular mutexes: if a function that takes a lock and executes a callback is itself called by the callback, deadlock ensues. In pseudocode, that is the following situation:

Consider the following scenario in pseudocode:

var m : Mutex  // A standard, non-reentrant mutex, initially unlocked.

function lock_and_call(i : Integer)
    m.lock()
    callback(i)
    m.unlock()

function callback(i : Integer)
    if i > 0
        lock_and_call(i - 1)

lock_and_call(1)  // Invoking the function

When lock_and_call(1) is executed with a standard mutex, it results in a deadlock:

1. The initial call to lock_and_call(1) successfully acquires the lock m.
2. It then calls callback(1).
3. Inside callback(1), because i > 0, it calls lock_and_call(0).
4. This second call to lock_and_call attempts to acquire the lock m again.
5. Deadlock: Because the mutex m is already locked, the thread stops and waits for the lock to be released. However, it is the thread itself that holds the lock, so it is waiting for itself to complete an action it can never take.

Using a reentrant mutex for m prevents this deadlock. When the second call to lock_and_call(0) attempts to lock the mutex, the operation succeeds because the thread attempting to acquire the lock is already the owner. The mutex's internal count is incremented. The lock is only fully released when both calls to lock_and_call have completed and performed their corresponding m.unlock() operations.

Practical use

W. Richard Stevens notes that recursive locks are "tricky" to use correctly, and recommends their use for adapting single-threaded code without changing APIs, but "only when no other solution is possible".

The Java language's native synchronization mechanism, monitor, uses recursive locks. 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.

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:

• A "control" condition using a regular lock
• Owner identifier, unique to each thread (defaulting to empty / not set)
• Acquisition count (defaulting to zero)

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.