Reentrant mutex

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.[1] In pseudocode, that is the following situation:

var m : Mutex  // A non-recursive 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

Given these definitions, the function call lock_and_call(1) will cause the following sequence of events:

• m.lock() — mutex locked
• callback(1)
• lock_and_call(0) — because i > 0
• m.lock() — deadlock, because m is already locked, so the executing thread will block, waiting for itself.

Replacing the mutex with a recursive one solves the problem, because the final m.lock() will succeed without blocking.

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".[2]

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

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