Fair Lock and Recursive Lock Hybrid Design

In concurrent programming, locks are fundamental tools for protecting shared resources. However, standard locks have two common problems:

1. Recursion issue: The same thread acquiring a non-recursive lock multiple times causes deadlock
2. Fairness issue: Non-fair locks may cause thread starvation

How to solve these problems while ensuring thread safety? This article provides an in-depth analysis of fair lock and recursive lock hybrid design in industrial-grade code, with a clean-room reconstruction in Rust.

The Problem: Lock Dilemma

Recursive Lock Dilemma

// Non-recursive lock: same thread acquiring multiple times causes deadlock
std::mutex m;
m.lock();
m.lock(); // Deadlock!

Fair Lock Dilemma

// Non-fair lock: new requests may cut in line
// Thread A acquires lock
// Thread B, C wait
// Thread A releases, B acquires
// Thread A acquires again quickly (fast release/acquire)
// B never gets lock -> Starvation

Industrial Solution: Recursive + Fair

The original code uses TRecursiveFairLock:

class TRecursiveFairLock {
public:
    void Acquire() noexcept;
    bool TryAcquire() noexcept;
    void Release() noexcept;
    
    bool IsFree() noexcept;
    bool IsOwnedByMe() noexcept;
    
private:
    class TImpl;
    THolder<TImpl> Impl;
};

The core ideas of this design:

• Recursion support: Maintain recursion_count, same thread can re-enter
• Fair queue: FIFO order, prevents thread starvation
• Pimpl pattern: Hide implementation details, keep header clean

Trade-off Analysis

Advantages

1. Avoid deadlock: Recursion allows same thread to acquire lock multiple times
2. Prevent starvation: Fair queue ensures waiting threads acquire in order
3. Clean interface: Pimpl hides complex implementation

Costs

1. Implementation complexity: Recursion + fairness increases lock complexity
2. Performance overhead: Fair queue maintenance has extra cost
3. Memory usage: Impl pointer increases memory usage

Rust Clean-Room Demonstration

struct FairRecursiveLock {
    inner: Mutex<FairRecursiveLockInner>,
}

struct FairRecursiveLockInner {
    owner_thread_id: Option<ThreadId>,
    recursion_count: usize,
    wait_queue: Vec<WaitNode>,
}

impl FairRecursiveLock {
    fn lock(&self) {
        let current_thread = thread::current().id();
        let mut inner = self.inner.lock().unwrap();
        
        // Case 1: Lock is free
        if inner.owner_thread_id.is_none() {
            inner.owner_thread_id = Some(current_thread);
            inner.recursion_count = 1;
            return;
        }
        
        // Case 2: Same thread re-entry
        if inner.owner_thread_id == Some(current_thread) {
            inner.recursion_count += 1;
            return;
        }
        
        // Case 3: Need to wait...
    }
}

fn main() {
    let lock = Arc::new(FairRecursiveLock::new());
    
    // Test recursive acquisition
    lock.lock();
    lock.lock();
    lock.unlock();
    lock.unlock();
}

Summary

This article provides an in-depth analysis of fair lock and recursive lock hybrid design, exploring the following core trade-offs:

1. Recursive vs Non-recursive: Trade extra counter for re-entry capability
2. Fair vs Non-fair: Trade throughput for determinism
3. Complexity vs Maintainability: Use Pimpl to hide implementation details

This design pattern is very common in systems requiring high concurrency and determinism. Understanding the trade-offs behind it is crucial for designing reliable concurrent systems.