Concurrent Data Structures (Thread-Safe Queue & Doubly Linked List)

A classic beginner mistake when designing concurrent data structures is taking std::queue<T> and simply wrapping every member function in a mutex:

// BROKEN THREAD-SAFE QUEUE ATTEMPT:
class NaiveQueue {
    std::mutex mtx;
    std::queue<int> q;
public:
    bool empty() { std::lock_guard<std::mutex> lk(mtx); return q.empty(); }
    int front()  { std::lock_guard<std::mutex> lk(mtx); return q.front(); }
    void pop()   { std::lock_guard<std::mutex> lk(mtx); q.pop(); }
};

The Anatomy of the Race Condition

Consider two consumer threads executing the standard idiom on a queue with exactly 1 item remaining:

if (!q.empty()) {
    int val = q.front();
    q.pop();
    process(val);
}

1. Thread 1 calls q.empty(). It acquires mtx, sees q.empty() == false, releases mtx, and enters the if block.
2. Before Thread 1 can execute q.front(), Thread 2 intervenes! Thread 2 calls q.empty() (returns false), calls q.front() (reads the element), and calls q.pop() (removes the element).
3. Thread 1 resumes and calls q.front(). The queue is now empty! Calling front() on an empty std::queue is undefined behavior, causing an immediate crash or segmentation fault!

Even if the queue contains 2 elements, two threads calling front() independently will read the same element twice, and then calling pop() twice will skip an element entirely! Wrapping individual methods in locks does not make an interface thread-safe.

To eliminate the interface race, a concurrent queue must combine reading the element and removing it into a single locked operation. In C++, there are three canonical signatures for race-free pop operations:

1. bool try_pop(T& value)

Acquires the lock, checks if the queue is empty. If empty, releases the lock and returns false. If non-empty, moves the front element into value, pops from the queue, releases the lock, and returns true. (Exception safety note: moving into caller's reference ensures that if the move constructor throws, the item remains safely in the queue).

2. std::optional<T> try_pop()

Modern C++17/23 idiomatic non-blocking pop. Returns std::nullopt if empty, or std::optional<T>(std::move(front)) if an item was present.

3. std::optional<T> wait_and_pop()

Blocking pop for consumer threads. Puts the thread to sleep on a std::condition_variable until an item is pushed or the queue is stopped, eliminating CPU-burning polling loops.

When synchronizing linked data structures (linked lists, skip lists, search trees), developers have two fundamental locking choices:

Coarse-Grained Locking

A single std::mutex guards the entire data structure. Every traversal, insertion, and deletion acquires the master lock.

• Pros: Simple, zero deadlock risk, easy exception safety, low memory overhead (1 mutex total).
• Cons: High contention under heavy multithreaded loads; all threads serialize regardless of which nodes they touch.

Fine-Grained Locking (Hand-Over-Hand / Lock Coupling)

Each individual node in the linked structure contains its own std::mutex. When traversing the list, a thread locks Node i+1 before releasing the lock on Node i (like swinging hand-over-hand across monkey bars).

• Pros: Multiple threads can traverse different sections of the list concurrently.
• Cons: Severe performance overhead (locking/unlocking dozens of mutexes per traversal incurs high bus-lock costs), complex deadlock avoidance, and elevated memory footprint (40 bytes per node for std::mutex). In production C++, sharded locking or lock-free designs are overwhelmingly preferred over hand-over-hand locking.

When interviewers ask candidates to optimize an in-memory Cache for high-read, low-write workloads, candidates frequently suggest std::shared_mutex: "We will use std::shared_lock (read lock) for get(), and std::unique_lock (write lock) for put()!"

The Fatal Flaw in LRU Caches

In a standard key-value map, get(key) is a read-only operation. However, in an LRU (Least Recently Used) Cache, calling get(key) mutates the underlying Doubly Linked List! Specifically, the accessed node must be moved to the front of the list (Most Recently Used position) by updating four pointers:

• node->prev->next = node->next
• node->next->prev = node->prev
• node->next = head->next
• head->next = node

If two threads execute cache.get() concurrently under a std::shared_lock, both threads attempt to rewrite these four node pointers at the exact same time! This causes a catastrophic data race, dangling pointers, circular linked lists, and memory corruption. In an LRU Cache, get() is a write operation and requires an exclusive lock (or a decoupled promotion queue).

Because a single coarse mutex serializes all accesses to an LRU Cache, high-throughput systems (such as Memcached, Redis clusters, or database buffer pools) use Lock Striping (Sharding).

Instead of protecting the entire cache with one lock, the cache is partitioned into S independent shards (typically a power of 2, e.g., 16, 32, or 64). Each shard contains its own independent mutex, hash map, and doubly linked list. When a thread accesses key K, it hashes the key to select a shard:

$$shardIndex = hash(K) \pmod S$$

Because different keys map to different shards, operations on unrelated keys proceed in 100% parallel execution without lock contention! Cross-shard operations are rare, and cache eviction is localized to the individual shard with zero inter-thread interference.