Synchronization primitives

Standard Library Lock Primitives

The standard library provides:

• Mutex: A basic mutual exclusion primitive that guards data and allows safe concurrent access.
• RwLock: A lock that allows multiple readers or one writer.
• Condvar: A condition variable for signaling between threads.

These are part of std::sync and are built on OS-level primitives like futexes (on Linux) or critical sections (on Windows). Key features:

• Cross-platform: They work consistently across all platforms supported by Rust.
• Blocking behavior: These locks block the current thread when contention occurs, which means they are not optimized for asynchronous programming.
• Heavyweight: They are reliable but can be slower for high-contention or lightweight workloads due to their reliance on OS synchronization mechanisms.

Parking Lot Primitives

The Parking Lot library (e.g., parking_lot::Mutex) provides:

• Mutex and RwLock replacements: Faster and more efficient than the standard library equivalents.
• Condvar: A condition variable similar to std::sync::Condvar.

Key differences compared to std:

• Lightweight locking: Parking Lot uses spinlocks initially before falling back to OS synchronization primitives. This reduces overhead for uncontended locks.
• Smaller memory footprint: Parking Lot locks are slimmer than their std counterparts, which makes them more cache-friendly.
• Fairer wake-ups: Implements a queue-based approach to wake up threads in the order they were parked.
• No Arc requirement: Parking Lot primitives don’t require the data to be wrapped in Arc (standard std::sync::Mutex does if shared between threads).
• Blocking: Like std, Parking Lot locks block threads, so they are not suitable for async tasks.

Spinlocks

Spinlocks are a type of mutual exclusion (mutex) mechanism used to protect shared resources in multi-threaded programming. Unlike traditional mutexes, spinlocks do not block threads when contention occurs. Instead, a thread attempting to acquire the lock will “spin” in a loop, repeatedly checking if the lock becomes available.

A spinlock is implemented using a shared atomic variable, often a single bit or integer. The variable’s state indicates whether the lock is acquired (locked) or available (unlocked). Threads attempt to acquire the lock using an atomic compare-and-swap operation (CAS) or similar atomic instructions.

1. Lock acquisition:

   • If the lock is free, the thread atomically sets the lock variable to “locked” and proceeds.
   • If the lock is already held by another thread, the thread spins in a loop, repeatedly checking the lock variable until it is released.

2. Lock release:

   • The thread holding the lock sets the lock variable back to “unlocked,” allowing other threads to acquire it.

Example in Rust (pseudo-code for illustration):

use std::sync::atomic::{AtomicBool, Ordering};
use std::hint;
 
struct Spinlock {
    lock: AtomicBool,
}
 
impl Spinlock {
    fn new() -> Self {
        Self {
            lock: AtomicBool::new(false),
        }
    }
 
    fn lock(&self) {
        while self
            .lock
            .compare_exchange(false, true, Ordering::Acquire, Ordering::Relaxed)
            .is_err()
        {
            hint::spin_loop(); // Hint to the CPU to optimize the spin loop
        }
    }
 
    fn unlock(&self) {
        self.lock.store(false, Ordering::Release);
    }
}
 
fn main() {
    let spinlock = Spinlock::new();
    spinlock.lock();
    // Critical section
    spinlock.unlock();
}

Disadvantages of Spinlocks

• CPU wastage: A spinning thread consumes CPU cycles while waiting, which can degrade overall system performance if the lock is held for a long time.
• Fairness issues: Spinlocks may lead to starvation, as they do not guarantee fair access to the lock.
• Unsuitability for long waits: If the critical section takes time, a blocking mutex is often a better choice.

---

When to Use Spinlocks

• Short critical sections: Spinlocks are ideal when the lock is expected to be held for a very short duration.
• Low contention: They perform well in scenarios where lock contention is rare.
• Non-blocking environments: Useful in real-time systems or interrupt handlers where blocking is unacceptable.

---

Practical Example of Spinlocks in Action

Optimized Spinlocks with Yielding:

Modern implementations of spinlocks often include optimizations such as yielding the CPU after spinning for a while, or backoff strategies to reduce contention.

Example with exponential backoff:

fn lock_with_backoff(&self) {
    let mut attempts = 0;
    while self
        .lock
        .compare_exchange(false, true, Ordering::Acquire, Ordering::Relaxed)
        .is_err()
    {
        if attempts < 10 {
            hint::spin_loop(); // Spin actively for a few iterations
        } else {
            std::thread::yield_now(); // Yield the CPU to prevent resource hogging
        }
        attempts += 1;
    }
}

---

Spinlocks are heavily used in low-level systems programming, particularly in kernel code, real-time systems, or lock-free data structures, where traditional mutexes might introduce unacceptable latency. However, for most general-purpose applications, higher-level synchronization primitives are preferred.

---

Tokio Lock Primitives

Tokio provides lock primitives specifically designed for asynchronous programming:

• tokio::sync::Mutex: An async version of Mutex.
• tokio::sync::RwLock: An async version of RwLock.
• tokio::sync::Semaphore: A counting semaphore to control access to a fixed number of resources.

Key differences compared to std and Parking Lot:

• Non-blocking: Instead of blocking threads, these locks use await to yield control when contention occurs, allowing other tasks to run. This avoids blocking the executor’s threads.
• Designed for async runtimes: These primitives integrate seamlessly with the Tokio runtime. They are not suitable for use outside async contexts.
• Fairness: Tokio’s locks provide fairness guarantees, ensuring that tasks acquire locks in the order they request them.

Example:

A tokio::sync::Mutex will return control to the runtime if a task attempts to acquire a locked resource. Other tasks on the same thread can continue to execute. In contrast, a std::sync::Mutex or parking_lot::Mutex would block the thread, potentially stalling the runtime.

---