Mutex (Mutual Exclusion)

The lock operation, also called acquire, is the mechanism by which a thread gains exclusive ownership of a mutex. If the mutex is already held by another thread, the calling thread will block (enter a waiting state) until the mutex becomes available. This operation is the entry point to a critical section.

• Blocking Behavior: The thread is suspended by the operating system scheduler, freeing the CPU core for other work.
• Implementation: Typically involves an atomic test-and-set or compare-and-swap instruction at the hardware level to check and claim the lock in a single, uninterruptible step.

The unlock operation, or release, relinquishes a thread's ownership of a mutex, making it available for acquisition by other waiting threads. This operation marks the exit from a critical section. Failing to unlock a held mutex results in a deadlock, permanently blocking all other threads waiting for that resource.

• Scheduler Wake-up: The unlock operation typically signals the OS scheduler to wake up one or all threads waiting on the mutex.
• Memory Barrier: A full memory fence is often implied, ensuring all writes within the critical section are visible to the next thread that acquires the lock.

Try-lock is a non-blocking variant of the lock operation. It attempts to acquire the mutex and returns immediately with a success or failure status, allowing the thread to perform alternative work instead of waiting. This is crucial for building responsive systems and avoiding deadlocks in complex locking hierarchies.

• Use Case: Useful in scenarios where a thread must acquire multiple locks; if one is unavailable, it can release any already held and retry later, following a deadlock-avoidance protocol.
• Return Value: Returns true if the lock was acquired successfully, false if it was already held.

A recursive mutex allows the same thread that currently holds the lock to acquire it multiple times without causing a self-deadlock. The mutex maintains a lock count and is only released for other threads when a matching number of unlock operations have been performed. This is essential when a public function protected by a mutex calls another function that requires the same lock.

• Lock Count: Internally tracks the number of successful acquires by the owning thread.
• Overhead: Slightly more overhead than a standard mutex due to the need to track ownership and count.
• Caution: Can mask poor software design where locking boundaries are unclear.

Mutexes can be configured with various attributes that define their runtime behavior, impacting performance and correctness.

• Pthread Mutex Types:
  • NORMAL: No error checking, may cause deadlock if relocked by the same thread.
  • ERRORCHECK: Provides error detection for relocks and unlocks by non-owners.
  • RECURSIVE: Allows recursive locking as described.
  • DEFAULT: Implementation-defined, often maps to NORMAL or RECURSIVE.
• Priority Inheritance: A protocol to prevent priority inversion, where a low-priority thread holds a lock needed by a high-priority thread. The mutex temporarily boosts the holder's priority.

While both are synchronization primitives, they serve distinct purposes. A mutex is a locking mechanism used to protect a shared resource, providing mutual exclusion with ownership semantics (only the locker can unlock). A binary semaphore (initialized to 1) can be used similarly but lacks ownership; any thread can signal (unlock) it.

• Mutex: For mutual exclusion (1 thread in a critical section). Has a concept of an owner.
• Counting Semaphore: For resource counting (N threads can access a pool of resources). No owner concept.
• Key Difference: A mutex is typically used for thread synchronization within a process, while semaphores are often used for inter-process communication (IPC). Misusing a semaphore as a mutex can lead to subtle bugs.

A deadlock is a state where two or more threads are permanently blocked, each waiting for a mutex held by the other. It's a critical failure of liveness.

Common Causes:

• Circular Wait: Thread A holds Lock 1 and waits for Lock 2, while Thread B holds Lock 2 and waits for Lock 1.
• Nested Locking: Acquiring multiple locks in an inconsistent order across threads.

Best Practices:

• Lock Ordering: Establish and strictly follow a global hierarchy for acquiring multiple locks.
• Lock Timeout: Use try_lock_for or try_lock_until to avoid indefinite blocking.
• Lock Guards: Prefer RAII wrappers like std::lock_guard or std::scoped_lock (C++17) which can acquire multiple locks atomically and safely.

Priority inversion occurs when a low-priority thread holds a mutex needed by a high-priority thread, but the low-priority thread cannot run because a medium-priority thread is preempting it. This causes the high-priority thread to wait indefinitely for a lower-priority task.

Mitigation Strategies:

• Priority Inheritance: The mutex protocol temporarily boosts the priority of the lock-holding thread to that of the highest-priority waiter. This is often a configurable attribute of real-time OS mutexes.
• Priority Ceiling: Assigns a static, high priority to the mutex itself; any thread that acquires it runs at that priority until release.
• Design: Minimize the duration of critical sections and avoid locking in high-priority threads where possible.

Lock contention arises when multiple threads frequently attempt to acquire the same mutex, leading to serialized execution and CPU cycles wasted on spinning or context switching.

Symptoms: High CPU usage with low throughput, poor scaling with added cores.

Optimization Techniques:

• Fine-Grained Locking: Protect smaller, independent data structures with separate mutexes instead of one global lock.
• Lock-Free Data Structures: Use atomic operations and CAS-based algorithms for high-contention counters or queues.
• Sharding: Partition data so each thread operates on a distinct subset, eliminating shared state.
• Critical Section Minimization: Hold the lock only for the minimal time necessary—compute outside the lock if possible.

The Resource Acquisition Is Initialization (RAII) pattern is the cornerstone of exception-safe mutex management. It guarantees that a held mutex is released when the guard object goes out of scope, regardless of how the scope is exited (return, exception, etc.).

Standard Implementations:

• std::lock_guard: Simple scoped ownership. Acquires on construction, releases on destruction.
• std::unique_lock: More flexible. Supports deferred locking, timeouts, and transfer of ownership.
• std::scoped_lock (C++17): Designed for acquiring multiple mutexes simultaneously without deadlock risk.

Example:

cppCopy
{
    std::scoped_lock lock(my_mutex); // Lock acquired here
    shared_vector.push_back(value);
} // Lock automatically released here, even if push_back throws

Double-checked locking is a broken optimization attempt for lazy initialization where a lock is avoided after the first initialization. In its naive form, it is unsafe due to instruction reordering in weak memory models.

The Broken Pattern:

cppCopy
if (ptr == nullptr) {          // First check (unsafe without sync)
    std::lock_guard lock(mtx);
    if (ptr == nullptr) {      // Second check
        ptr = new Resource();
    }
}
return ptr;

The write to ptr may become visible to other threads before the Resource constructor completes.

Correct Solutions:

• Use local static variables (C++11 guarantees thread-safe initialization).
• Use std::call_once with a std::once_flag.
• Use atomic operations with std::memory_order_acquire and std::memory_order_release for hand-crafted solutions.

A mutex is not always the optimal synchronization primitive. Selecting the right tool is a key design decision.

Decision Guide:

• Use a Mutex (std::mutex): For exclusive access to a shared resource or critical section. The default choice for mutual exclusion.
• Use a Reader-Writer Lock (std::shared_mutex): When data is read frequently but written rarely. Allows concurrent reads but exclusive writes.
• Use a Semaphore (std::counting_semaphore): To control access to a pool of identical resources (e.g., connection pools) or for producer-consumer signaling.
• Use a Condition Variable (std::condition_variable): To allow threads to wait for a specific state change, always paired with a mutex.
• Use Atomics (std::atomic): For simple counters, flags, or pointers where lock-free operations are sufficient.
• Use a Spinlock: Only for very short critical sections on bare-metal or when thread descheduling overhead is prohibitive; otherwise, prefer a mutex.

A semaphore is a synchronization variable that controls access to a common resource by multiple threads, using an internal counter. Unlike a mutex, which is binary (locked/unlocked), a semaphore can permit a specified number of concurrent accesses.

• Counting Semaphore: Manages access to a pool of identical resources (e.g., database connections).
• Binary Semaphore: Can be used similarly to a mutex but lacks the concept of ownership, meaning any thread can release it.
• Key Operation: wait() (or P) decrements the count; signal() (or V) increments it. A thread blocks if wait() is called when the count is zero.

Atomic operations are indivisible read-modify-write instructions (e.g., fetch-and-add, compare-and-swap) that complete without interruption from other threads. They are the foundation for lock-free and wait-free algorithms.

• Hardware Support: Implemented via CPU instructions (like LOCK prefix on x86) to ensure cache-line exclusivity.
• Use Case: Ideal for simple updates to shared counters or flags, avoiding the overhead of a full mutex lock.
• Limitation: Only guarantees atomicity for the specific operation; complex multi-step logic still requires higher-level synchronization.

A condition variable enables threads to wait for a specific program state (a condition) to become true. It is always used in conjunction with a mutex to protect the shared data that defines the condition.

• Typical Pattern: A thread acquires a mutex, checks a condition (e.g., queue.empty()), and if false, waits on the condition variable, which atomically releases the mutex. Upon notification, it re-acquires the mutex.
• Signaling: notify_one() wakes one waiting thread; notify_all() wakes all.
• Crucial for: Implementing producer-consumer queues, thread pools, and any scenario where a thread must wait for an event.

A spinlock is a busy-wait mutex where a thread repeatedly checks (spins) on a flag in a loop until it becomes available. It is a low-level locking primitive often used in kernel development or for very short critical sections.

• Advantage: Extremely low latency when lock contention is minimal, as it avoids the cost of a context switch.
• Disadvantage: Wastes CPU cycles if the lock is held for a long time, reducing system throughput.
• Adaptive Spinlocks: Hybrid approaches that spin for a short duration before yielding the CPU or sleeping.

A reader-writer lock (or shared-exclusive lock) allows concurrent read access to a shared resource by multiple threads, but requires exclusive access for write operations. This optimizes for read-heavy workloads.

• Modes: Shared (read) lock, Exclusive (write) lock.
• Policies: Manages fairness between readers and writers (e.g., writer-preference prevents reader starvation).
• Implementation: Typically built using a mutex and condition variables, or via atomic operations for more advanced versions.

A memory barrier or fence is a low-level instruction that enforces ordering constraints on memory operations issued before and after the barrier. It is essential for correct synchronization on processors with weak memory consistency models.

• Problem Solved: Compilers and CPUs can reorder memory operations for performance. Without barriers, a thread might see writes from another thread in an unexpected order, breaking lock logic.
• Types: Acquire (prevents subsequent reads/writes from being moved before the barrier), Release (prevents prior reads/writes from being moved after it). Mutex lock/unlock operations imply these barriers.