Concurrency, Synchronization & Deadlock Questions

Direct answer

Two threads deadlock when each takes one lock and then asks for the lock the other already holds. The fix is to make every thread take the locks in the same order (or let std::scoped_lock take both without deadlock), or to use try_lock with a randomized back-off. To find it in a live system, take a thread dump (a snapshot listing every thread and the call stack it is currently stuck in) and look for two threads each blocked on a lock the other holds; to reproduce it, widen the timing window and run lock-order checking (ThreadSanitizer or the kernel's lockdep) in test builds.

The deadlock, in code

Each worker takes its first lock, sleeps 100 ms so the other thread can take its first lock, then asks for the second one. The sleep is only there to make the unlucky timing certain; in production the same interleaving happens rarely and under load, which is why these bugs are intermittent.

#include <chrono>
#include <cstdio>
#include <cstring>
#include <mutex>
#include <random>
#include <thread>

using namespace std::chrono_literals;

std::mutex lock_a, lock_b;

// Each worker takes its first lock, pauses so the other thread can take its own
// first lock, then asks for the second one.
void worker_opposite(std::mutex& first, std::mutex& second, const char* name) {
    std::lock_guard<std::mutex> g1(first);
    std::printf("%s holds its first lock\n", name);
    std::this_thread::sleep_for(100ms);
    std::lock_guard<std::mutex> g2(second);   // never returns in "bad" mode
    std::printf("%s got both\n", name);
}

// Fix 1: take both locks through std::scoped_lock, which avoids deadlock whatever order the arguments are listed in.
void worker_scoped(const char* name) {
    std::scoped_lock both(lock_a, lock_b);
    std::printf("%s got both\n", name);
}

// Fix 2: try-lock with randomized backoff. Releases what it holds on failure.
void worker_trylock(std::mutex& first, std::mutex& second, const char* name, unsigned seed) {
    std::mt19937 rng(seed);
    for (;;) {
        std::unique_lock<std::mutex> g1(first);
        std::this_thread::sleep_for(100ms);
        if (second.try_lock()) {
            std::lock_guard<std::mutex> g2(second, std::adopt_lock);
            std::printf("%s got both\n", name);
            return;
        }
        g1.unlock();                                   // give up the first lock
        std::this_thread::sleep_for(std::chrono::milliseconds(1 + rng() % 50));
    }
}

int main(int argc, char** argv) {
    std::setvbuf(stdout, nullptr, _IOLBF, 0);   // flush each line even when piped
    const char* mode = argc > 1 ? argv[1] : "bad";
    std::thread t1, t2;
    if (!std::strcmp(mode, "bad")) {
        t1 = std::thread(worker_opposite, std::ref(lock_a), std::ref(lock_b), "T1");
        t2 = std::thread(worker_opposite, std::ref(lock_b), std::ref(lock_a), "T2");
    } else if (!std::strcmp(mode, "sequential")) {
        // Opposite orders, but one after the other: cannot hang, yet a lock-order
        // checker still sees both orders and flags the potential deadlock.
        std::thread(worker_opposite, std::ref(lock_a), std::ref(lock_b), "T1").join();
        std::thread(worker_opposite, std::ref(lock_b), std::ref(lock_a), "T2").join();
        std::puts("finished");
        return 0;
    } else if (!std::strcmp(mode, "scoped")) {
        t1 = std::thread(worker_scoped, "T1");
        t2 = std::thread(worker_scoped, "T2");
    } else {
        t1 = std::thread(worker_trylock, std::ref(lock_a), std::ref(lock_b), "T1", 1u);
        t2 = std::thread(worker_trylock, std::ref(lock_b), std::ref(lock_a), "T2", 2u);
    }
    t1.join();
    t2.join();
    std::puts("finished");
}

Reading guide for the trylock worker: std::unique_lock is a lock holder that, unlike lock_guard, can be released early with unlock(); second.try_lock() attempts to take the second lock and returns false at once instead of waiting; std::lock_guard<std::mutex> g2(second, std::adopt_lock) takes over a lock that is already held so it is released automatically at the end of the scope; std::mt19937 rng(seed) is a random-number generator, given a different seed per thread so the two threads pick different delays; and std::ref passes a mutex by reference to std::thread, which would otherwise try to copy it.

Built and run in a Linux container with GCC 14 (g++ -std=c++20 -O2 -Wall -Wextra -pthread deadlock.cpp -o dl), each mode under timeout 5:

$ timeout 5 ./dl bad ; echo exit=$?
T1 holds its first lock
T2 holds its first lock
exit=124
$ timeout 5 ./dl scoped
T1 got both
T2 got both
finished
$ timeout 5 ./dl trylock
T2 got both
T1 got both
finished

In bad mode neither "got both" line ever appears, and exit code 124 is timeout killing a process that did not finish: that is the deadlock. Two lines of output followed by silence, with zero CPU use, is the classic signature (a livelock, by contrast, burns CPU while making no progress). In scoped and trylock modes the order of the two "got both" lines can differ between runs; the point is that both always appear and the program finishes.

Fixes

1. One global lock order. If every code path that needs both locks takes lock_a then lock_b, the cycle cannot form. std::scoped_lock both(lock_a, lock_b) is the library way to take both without deadlock: the C++ reference says that with several mutexes it uses a deadlock-avoidance algorithm as if by std::lock. It does not impose a rank on your locks (a common implementation tries one lock, try-locks the rest and backs off), so it protects only the code that takes all the locks through it together; a path that locks them one at a time in the opposite order can still deadlock, which is why a written global order stays the rule that covers every path. For locks chosen at run time, order by a stable key (an id or, within one process, the address).
2. try_lock with randomized back-off (trylock mode above). Take the first lock, try_lock the second, and if that fails release the first, sleep a random few milliseconds and start again. Livelock risk: if both threads back off for the same fixed time they can collide again forever, each repeatedly taking its first lock and failing on the second. The random delay (different seed per thread) breaks the symmetry. It does not guarantee progress in every execution, only that repeated collision becomes unlikely. Prefer fix 1 when you can order the locks.

Detecting it in a live system (in order)

1. Confirm the symptom. Some requests hang, the process is alive, and CPU use for those threads is near zero. High CPU with no progress points to livelock instead.
2. Capture all thread stacks. For a native process, attach gdb and run thread apply all bt (bt is short for backtrace, the list of function calls that led to where a thread is stopped; the GDB manual: thread apply all command runs the command on every thread). A deadlock shows as two or more threads parked inside pthread_mutex_lock, where each one's lock is the one the other holds. In a Java service, ThreadMXBean.findDeadlockedThreads() returns the IDs of platform threads in a cycle over monitors (Java's built-in synchronized locks) and ownable synchronizers (lock objects such as ReentrantLock) (its Javadoc warns it can be expensive, so call it from a diagnostic endpoint, not in a hot loop; it does not report cycles that include virtual threads, which are lightweight threads scheduled by the JVM rather than one-to-one by the operating system). A core file is a saved snapshot of a process's memory taken when it is killed or crashes, which gdb can open afterwards to run the same thread apply all bt.
3. Name the two locks and the two code paths, then check which one violates the order your design says it should follow.
4. Instrument for next time. Log lock acquisition with the holder when a try_lock_for (timed lock) times out, so a stuck wait becomes a log line with both thread names instead of a silent hang.

Reproducing it under load

• Widen the window. Add a short sleep or yield between acquiring the first and second lock in a test build (exactly what the sleep_for(100ms) above does), then run many threads against the same locks.
• Run a lock-order checker so the deadlock need not happen. ThreadSanitizer (TSan) builds a graph of which lock was taken while holding which, and reports a cycle as lock-order-inversion (potential deadlock). In the sequential mode, T1 finishes before T2 starts, so no hang is possible, yet it still reports (the full report also prints stack frames, trimmed here):

$ g++ -std=c++20 -O1 -g -fsanitize=thread -pthread deadlock.cpp -o dlt && ./dlt sequential
T1 holds its first lock
T1 got both
T2 holds its first lock
==================
WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock) (pid=14)
  Cycle in lock order graph: M0 (0x000000420150) => M1 (0x000000420120) => M0

  Mutex M1 acquired here while holding mutex M0 in thread T1:
    ...  worker_opposite(std::mutex&, std::mutex&, char const*) /w/deadlock.cpp:18
  Mutex M0 acquired here while holding mutex M1 in thread T2:
    ...  worker_opposite(std::mutex&, std::mutex&, char const*) /w/deadlock.cpp:18
SUMMARY: ThreadSanitizer: lock-order-inversion (potential deadlock) ...
T2 got both
finished

Reading the report: M0 and M1 are TSan's names for the two mutexes (here lock_a and lock_b, shown with their addresses); Cycle in lock order graph: M0 => M1 => M0 says some thread took M1 while holding M0 and another took M0 while holding M1, which is the circular wait; each Mutex Mx acquired here while holding mutex My in thread Tn block gives the thread and the source line of one half of the cycle.

Run on the same TSan build, ./dlt bad prints no report: TSan checks when the second lock is acquired, and in bad mode that acquisition never completes. Test with the non-overlapping sequential mode, or on code paths that sometimes run alone, and do not expect the report from a build that already hangs. The Clang documentation gives a typical slowdown of 5x-15x and memory overhead of 5x-10x, so this belongs in test and staging builds, not production.

• In kernel code the lockdep validator (the Linux kernel's built-in lock-order checker) tracks lock classes and proves from lock sequences that occurred at least once that no timing of them can deadlock, so a bad ordering is reported without the hang ever happening.

Pitfalls

• Fixing only the two code paths you found: add the rule (a comment next to the lock declarations, plus a test) so a third path does not reintroduce the inversion.
• Back-off without randomness, or without releasing the first lock, which turns a deadlock into a livelock or does nothing at all.
• Holding a lock while calling a callback, which hides the second acquisition from anyone reading the call site.

Direct answer

The Michael-Scott queue (a multi-producer multi-consumer, MPMC, queue) is a singly linked list with a permanent dummy node (a placeholder node holding no real item, so head and tail are never null), a head that points at the dummy and a tail that points at (or one node behind) the last node. Enqueue links a new node after the last node with a CAS (compare-and-swap, an atomic "write only if still equal to what I read") on that node's next, then tries to swing tail. Dequeue reads the node after the dummy and CASes head forward so that node becomes the new dummy. The operations help each other: whoever notices tail lagging behind a linked node moves it forward before doing its own work, so no thread ever waits for another to finish. The linearization point (the single instant at which the operation appears to take effect) is the successful link CAS for enqueue and the successful head CAS for a non-empty dequeue. ABA (a CAS succeeds because the value looks unchanged although it was changed and changed back) and memory reclamation (when it is safe to free a removed node) are solved either by version-counted links over a recycled pool (shown below), by hazard pointers or epochs, or by a garbage collector (GC).

How it works

1. Invariants. head always points at the dummy. tail is either the last node or exactly one node behind it. Nodes are only ever added at the end and removed at the front.
2. Enqueue. Read tail and tail->next. If next is null, CAS tail->next from null to the new node (linearization point). Then CAS tail to the new node; if that fails, someone already helped. If next is not null, tail is lagging: CAS tail to next (helping) and retry.
3. Dequeue. Read head, tail and head->next. If head == tail and next is null, the queue is empty (it linearizes at the read of next that returned null; the re-check that head is unchanged, made right after that read, confirms the read saw the current dummy). If head == tail and next is not null, help move tail. Otherwise read the value from next before the CAS (afterwards the node may be recycled), then CAS head from the old dummy to next (linearization point); the old dummy is released.
4. Why helping matters. Without it, a thread stalled between its link CAS and its tail swing would block every other enqueuer: that is lock-based behaviour in disguise. With it the algorithm stays lock-free: a failed CAS means somebody else's CAS succeeded.

A traced example: helping with a lagging tail

Start with an empty queue: one dummy node D, head -> D, tail -> D, D.next = null.

1. Enqueuer E1 wants to add item A. It reads tail = D and D.next = null, then CASes D.next from null to A. This succeeded: A is now in the queue (the linearization point), even though tail still points at D. Now E1 is descheduled before it swings tail.
2. Enqueuer E2 wants to add B. It reads tail = D and D.next = A, which is not null, so it knows tail is lagging. It does not wait for E1: it CASes tail from D to A (helping), then loops.
3. E2 reads tail = A, A.next = null, CASes A.next from null to B (E2's linearization point), then CASes tail from A to B.
4. E1 wakes up and tries to CAS tail from D to A. It fails because tail is already B, which is fine: E1 treats a failed swing as "someone helped" and returns. The list is D -> A -> B and the order A then B is the order of the link CASes.
5. A dequeuer reads head = D, D.next = A, reads A's value, then CASes head from D to A. A is now the dummy and the caller gets A's value (that CAS is the dequeue's linearization point).

Empty-queue case: a dequeuer reads head = D, then D.next, and gets null; it then checks that head is still D. Since head is unchanged, D was still the dummy when D.next was read, and a null next at that moment means no item sat after the dummy, so the queue was empty at exactly that read. That read is the linearization point of the failed dequeue. If head had changed in between, the read may describe a stale dummy and the loop retries.

Worked example: a tested C++ implementation

Nodes live in a fixed pool of 4,096. A link is (tag << 32) | node index (a counted link: the index plus a version number); every successful CAS on a link bumps its tag, so a link that came back to the same index is still told apart. Released nodes go to a tagged free list (itself a lock-free stack), so memory is never returned to the allocator while a stale thread may read it. Reading guide: pack/idx_of/tag_of build and split a link; release_node/acquire_node push and pop the free list; enqueue is step 2 of the algorithm above (the else branch is helping, the line after the loop is the optional tail swing); dequeue is step 3 (its first branch handles empty or lagging, its second reads the value then CASes head); main runs the producers and consumers and checks the results. Two producers each enqueue 200,000 numbers tagged with their producer id; two consumers dequeue them; the checks are no loss, no duplicates, and that each consumer sees each producer's numbers in increasing order (per-producer first-in first-out, FIFO, order).

// Michael-Scott queue over a fixed node pool with counted (tagged) links.
// A link is (tag << 32) | node index. Nodes are recycled through a tagged free list,
// so no node is ever returned to the allocator while a stale thread may still read it.
#include <atomic>
#include <cstdint>
#include <cstdio>
#include <thread>
#include <vector>

constexpr uint32_t NIL = 0xFFFFFFFFu;
constexpr uint32_t POOL = 4096;
static uint64_t pack(uint32_t tag, uint32_t idx) { return (uint64_t(tag) << 32) | idx; }
static uint32_t idx_of(uint64_t l) { return uint32_t(l); }
static uint32_t tag_of(uint64_t l) { return uint32_t(l >> 32); }

struct Node {
    std::atomic<uint32_t> value{0};
    std::atomic<uint64_t> next{pack(0, NIL)};
    std::atomic<uint32_t> free_next{NIL};
};

class MSQueue {
    Node nodes_[POOL];
    std::atomic<uint64_t> head_, tail_, free_{pack(0, NIL)};

    void release_node(uint32_t n) {                       // push onto the tagged free list
        uint64_t f = free_.load();
        do { nodes_[n].free_next.store(idx_of(f)); }
        while (!free_.compare_exchange_weak(f, pack(tag_of(f) + 1, n)));
    }
    uint32_t acquire_node() {                             // pop from the tagged free list
        uint64_t f = free_.load();
        for (;;) {
            if (idx_of(f) == NIL) return NIL;
            uint32_t nx = nodes_[idx_of(f)].free_next.load();
            if (free_.compare_exchange_weak(f, pack(tag_of(f) + 1, nx))) return idx_of(f);
        }
    }
public:
    MSQueue() {
        for (uint32_t i = 1; i < POOL; ++i) release_node(i);
        head_ = tail_ = pack(0, 0);                        // node 0 is the dummy
    }
    bool enqueue(uint32_t v) {
        uint32_t n = acquire_node();
        if (n == NIL) return false;                        // pool exhausted
        nodes_[n].value.store(v);
        nodes_[n].next.store(pack(tag_of(nodes_[n].next.load()), NIL));
        uint64_t tail;
        for (;;) {
            tail = tail_.load();
            uint64_t next = nodes_[idx_of(tail)].next.load();
            if (tail != tail_.load()) continue;            // snapshot changed, retry
            if (idx_of(next) == NIL) {
                // LINEARIZATION POINT of enqueue: this CAS links the new node after the last node.
                if (nodes_[idx_of(tail)].next.compare_exchange_weak(next, pack(tag_of(next) + 1, n))) break;
            } else {
                // Tail is lagging: HELP the enqueuer that linked a node but has not swung Tail yet.
                tail_.compare_exchange_weak(tail, pack(tag_of(tail) + 1, idx_of(next)));
            }
        }
        tail_.compare_exchange_strong(tail, pack(tag_of(tail) + 1, n));  // optional swing; others may do it
        return true;
    }
    bool dequeue(uint32_t& out) {
        for (;;) {
            uint64_t head = head_.load(), tail = tail_.load();
            uint64_t next = nodes_[idx_of(head)].next.load();
            if (head != head_.load()) continue;
            if (idx_of(head) == idx_of(tail)) {
                if (idx_of(next) == NIL) return false;     // empty (linearizes at the load of next above)
                tail_.compare_exchange_weak(tail, pack(tag_of(tail) + 1, idx_of(next)));  // HELP
            } else {
                uint32_t v = nodes_[idx_of(next)].value.load();   // read BEFORE the CAS: node may be recycled after it
                // LINEARIZATION POINT of a non-empty dequeue: Head moves past the old dummy.
                if (head_.compare_exchange_weak(head, pack(tag_of(head) + 1, idx_of(next)))) {
                    release_node(idx_of(head));            // old dummy goes back to the pool
                    out = v;
                    return true;
                }
            }
        }
    }
};

int main() {
    constexpr int P = 2, C = 2, PER = 200000;
    static MSQueue q;
    std::atomic<long> consumed{0};
    std::vector<std::vector<uint32_t>> got(C);
    std::vector<std::thread> th;
    for (int p = 0; p < P; ++p)
        th.emplace_back([&, p] {
            for (uint32_t i = 0; i < PER; ++i)
                while (!q.enqueue(uint32_t(p) << 24 | i)) std::this_thread::yield();
        });
    for (int c = 0; c < C; ++c)
        th.emplace_back([&, c] {
            uint32_t v;
            while (consumed.load() < long(P) * PER)
                if (q.dequeue(v)) { got[c].push_back(v); consumed.fetch_add(1); }
        });
    for (auto& t : th) t.join();
    // Checks: every item exactly once, and each consumer sees each producer's items in increasing order.
    std::vector<std::vector<char>> seen(P, std::vector<char>(PER, 0));
    long total = 0; bool order_ok = true, dup = false;
    for (int c = 0; c < C; ++c) {
        uint32_t last[P]; for (auto& l : last) l = 0xFFFFFFFFu;
        for (uint32_t v : got[c]) {
            uint32_t p = v >> 24, i = v & 0xFFFFFF;
            if (last[p] != 0xFFFFFFFFu && i <= last[p]) order_ok = false;
            last[p] = i;
            if (seen[p][i]++) dup = true;
            ++total;
        }
    }
    printf("dequeued %ld of %d, duplicates=%d, per-producer FIFO order kept=%d\n", total, P * PER, dup, order_ok);
}

g++ -std=c++20 -O1 -g -Wall -Wextra -fsanitize=thread msqueue.cpp -o m && ./m (g++ 14.4.0; TSan, the data race detector, reported nothing) and the same program at -O2 run twice without TSan all printed:

dequeued 400000 of 400000, duplicates=0, per-producer FIFO order kept=1

All atomics use the default sequentially consistent order (every thread sees one agreed order of all these operations) to keep the proof obligation small; relaxing to acquire/release on the link CASes and loads is possible but should be done only with a model-checked argument (a tool that explores every interleaving of a small model of the algorithm, rather than trusting a hand proof). Not executed: counter wraparound (see the test plan).

ABA and memory reclamation: the options

For a pointer-passing queue I would take hazard pointers when threads can be preempted for long periods (bounded garbage matters) and epochs when threads are short-lived and the per-operation cost dominates.

The Java version

ConcurrentLinkedQueue in the JDK is documented as based on the Michael and Scott non-blocking algorithm. The same algorithm in plain AtomicReference form needs no tag and no free list: the collector guarantees a node is not reused while referenced, which removes the reclamation half of ABA. AtomicStampedReference (it succeeds only if both the reference and an integer stamp match) is needed only if you recycle node objects yourself. A four-thread run, each thread pushing and enqueuing 100,000 numbers, checked the item count and the sum:

import java.util.concurrent.atomic.AtomicReference;

public class GcLockFree {
    // Treiber stack: nodes are plain garbage-collected objects, never reused by this code.
    static final class TStack<T> {
        private static final class Node<T> { final T item; Node<T> next; Node(T i) { item = i; } }
        private final AtomicReference<Node<T>> head = new AtomicReference<>();
        void push(T item) {
            Node<T> n = new Node<>(item);
            Node<T> h;
            do { h = head.get(); n.next = h; } while (!head.compareAndSet(h, n));
        }
        T pop() {
            Node<T> h;
            do { h = head.get(); if (h == null) return null; } while (!head.compareAndSet(h, h.next));
            return h.item;
        }
    }

    // Michael-Scott queue: same algorithm, no tags, no free list.
    static final class MSQueue<T> {
        private static final class Node<T> { final T item; final AtomicReference<Node<T>> next = new AtomicReference<>(); Node(T i) { item = i; } }
        private final AtomicReference<Node<T>> head, tail;
        MSQueue() { Node<T> d = new Node<>(null); head = new AtomicReference<>(d); tail = new AtomicReference<>(d); }
        void enqueue(T item) {
            Node<T> n = new Node<>(item);
            for (;;) {
                Node<T> t = tail.get(), nx = t.next.get();
                if (t != tail.get()) continue;
                if (nx == null) {
                    if (t.next.compareAndSet(null, n)) { tail.compareAndSet(t, n); return; }  // linearization point
                } else tail.compareAndSet(t, nx);                                              // help
            }
        }
        T dequeue() {
            for (;;) {
                Node<T> h = head.get(), t = tail.get(), nx = h.next.get();
                if (h != head.get()) continue;
                if (h == t) { if (nx == null) return null; tail.compareAndSet(t, nx); }
                else { T v = nx.item; if (head.compareAndSet(h, nx)) return v; }               // linearization point
            }
        }
    }

    public static void main(String[] a) throws Exception {
        final int THREADS = 4, PER = 100_000;
        TStack<Integer> s = new TStack<>();
        MSQueue<Integer> q = new MSQueue<>();
        Thread[] ts = new Thread[THREADS];
        for (int t = 0; t < THREADS; t++) { ts[t] = new Thread(() -> {
            for (int i = 0; i < PER; i++) { s.push(i); q.enqueue(i); } }); ts[t].start(); }
        for (Thread t : ts) t.join();
        long sumS = 0, nS = 0, sumQ = 0, nQ = 0; Integer v;
        while ((v = s.pop()) != null) { sumS += v; nS++; }
        while ((v = q.dequeue()) != null) { sumQ += v; nQ++; }
        long expect = (long) THREADS * ((long) (PER - 1) * PER / 2);
        System.out.println("stack: " + nS + " items, sum " + sumS + "; queue: " + nQ + " items, sum " + sumQ + "; expected " + (THREADS * PER) + " items, sum " + expect);
    }
}

java GcLockFree.java (JDK 21) printed:

stack: 400000 items, sum 19999800000; queue: 400000 items, sum 19999800000; expected 400000 items, sum 19999800000

Related queue designs and where they fit

• Bounded array queue (for example a logging pipeline that must not allocate): each slot carries a sequence number (a counter stored with the slot that tells producers and consumers whose turn it is) saying whether it is ready for a producer or a consumer; a full ring makes enqueue fail or the caller drop or block, and there is no reclamation problem at all.
• Lock-free linked list with deletion: removing a node in the middle needs a "logically deleted" mark in the node's next pointer, set by CAS before the node is physically unlinked, so that no one links a new node after a node being removed.
• Network I/O or mobile (Java/Kotlin) producers: the shape above, with the GC doing the reclamation.
• Use from interrupt and thread context across cores: no GC and no allocator in an interrupt service routine, so use the pooled design with version-tagged CAS; every thread and ISR needs the ordering the CASes provide, and reclamation is the pool plus tag.

Test plan for a lock-free MPMC queue

1. A tiny pool (a few nodes) so recycling happens constantly: the use-after-free and reclamation-lag bugs only show then.
2. A sanitizer build (TSan, and AddressSanitizer for the pointer version) in CI.
3. Invariants checked after the run: every item exactly once, per-producer order, and queue empty at the end.
4. Wraparound: start the tag counters near 0xFFFFFFFF so the wrap happens in the test.
5. Empty and one-element transitions with one enqueuer racing one dequeuer, plus long runs with many yields to vary the interleaving.

Pitfalls

Reading the value after the head CAS; forgetting to help; assuming tail is always the last node; and using a tag too short for the update rate.

Direct answer

Each of the four coordinates a different thing. A mutex (mutual exclusion lock) lets one thread at a time touch shared data. A semaphore is a counter that limits how many threads may use something, or signals that something happened. A condition variable lets a thread sleep until a condition on shared data becomes true, always used together with a mutex. A barrier makes a group of threads all arrive at a point before any continues. The wrong tool is usually the one that does not match whether you are protecting data, counting capacity, waiting for a state, or synchronizing a phase.

The four, with a use and a wrong use

Executed demonstration: a condition variable used as a bare signal, and a barrier working as designed

#include <barrier>
#include <chrono>
#include <condition_variable>
#include <cstdio>
#include <mutex>
#include <thread>
#include <vector>

using namespace std::chrono_literals;

std::mutex m;
std::condition_variable cv;
bool ready = false;

int main() {
    // Condition variable used as a bare signal: the notification fires before anyone waits.
    {
        std::unique_lock<std::mutex> lk(m);
        ready = true;
    }
    cv.notify_one();                                   // nobody is waiting: this wakeup is gone

    {
        std::unique_lock<std::mutex> lk(m);
        bool woke = cv.wait_for(lk, 300ms) != std::cv_status::timeout;   // no predicate
        std::printf("bare wait after early notify: woke = %s\n", woke ? "yes" : "no (waits forever without the timeout)");
    }
    {
        std::unique_lock<std::mutex> lk(m);
        bool ok = cv.wait_for(lk, 300ms, [] { return ready; });          // predicate checks the state
        std::printf("wait with predicate: proceeds = %s\n", ok ? "yes" : "no");
    }

    // Barrier: every participant must arrive before any continues.
    constexpr int N = 3;
    int phase1_done = 0;                               // written under the barrier's completion step
    std::barrier sync(N, [&]() noexcept { phase1_done = N; });
    std::vector<std::thread> ts;
    std::vector<int> saw(N, -1);
    for (int i = 0; i < N; i++)
        ts.emplace_back([&, i] {
            std::this_thread::sleep_for(std::chrono::milliseconds(10 * i));   // uneven phase 1
            sync.arrive_and_wait();
            saw[i] = phase1_done;                      // all see the completed phase 1
        });
    for (auto& t : ts) t.join();
    std::printf("barrier: every thread saw phase1_done = %d %d %d\n", saw[0], saw[1], saw[2]);
}

Compiled with g++ -std=c++20 -O2 -Wall -Wextra -pthread prims.cpp (and with -fsanitize=thread, same output, no reports) in a GCC 14 container:

bare wait after early notify: woke = no (waits forever without the timeout)
wait with predicate: proceeds = yes
barrier: every thread saw phase1_done = 3 3 3

• The notify happened while nobody was waiting, so a bare wait sleeps until it times out; a wait with a predicate checks the state (ready) first and proceeds. The program uses a 300 ms timeout only so the demonstration cannot hang. Waiting with a predicate is equivalent to looping on while (!pred()) wait(lock), which also protects against spurious wakeups (a waiting thread returning although no thread notified it; the C++ reference notes wait can return without any notification).
• The barrier's completion function is a callback the barrier runs once per phase, after the last thread arrives and before any thread is released (noexcept promises it will not throw). arrive_and_wait means "I have arrived; block until all N threads have". Every thread sees the callback's result afterwards. std::barrier fixes its participant count at construction; a thread that must leave early calls arrive_and_drop, which reduces the count for later phases.

Where a message queue fits, and ISR-to-task signalling

• A message queue (a thread-safe FIFO that hands data from one thread to another) fits when threads should exchange data instead of sharing it: the queue does the locking and the waiting, and each item has one owner at a time. It is the wrong tool when many threads must update one large structure in place (copying it through a queue is expensive), or when you need the latest value only (a shared variable under a mutex is simpler).
• ISR-to-task signalling. An interrupt service routine (ISR) cannot block, so it should signal rather than lock: a semaphore for a pure event, or a queue when the event carries data (a received byte). Do not lock a mutex from an ISR: the ISR cannot block, and the mutex ownership model assumes a thread that can wait and later unlock.
• Ownership and priority awareness. Because a mutex has an owner, it can support priority inheritance (the lock holder temporarily runs at the priority of the highest-priority waiter, so a medium-priority thread cannot keep a low-priority holder from finishing). POSIX defines this as PTHREAD_PRIO_INHERIT on a mutex attribute. A semaphore, with no owner, cannot do this. Choose the primitive whose ownership matches the job: mutex for data (owner exists), semaphore or queue for events and capacity (no owner).

Recommendation and pitfalls

For shared data, default to a mutex; add a condition variable only when a thread must wait for a state; use a semaphore for a count of identical resources or a pure signal; use a barrier only for lockstep phases with a fixed set of participants; and use a queue when the design is "workers pass messages". Pitfalls: waiting on a condition variable without a predicate loop, signalling a condition variable without changing the state under the mutex, using a binary semaphore as a lock, and a barrier with a participant that can fail before reaching it.

Direct answer

A counting semaphore is a counter plus a wait queue, managed by two operations. Wait (also called P, down or acquire) blocks until the counter is above zero, then decrements it. Signal (V, up, release or post) increments the counter and wakes a waiter if there is one. The counter's initial value is the number of "permits" you have. A binary semaphore is the same thing limited to 0 or 1. Unlike a mutex, a semaphore has no owner: any thread may signal it. Typical use: limit concurrent access to a scarce resource, such as at most 3 simultaneous database connections.

How it behaves

With initial count 3:

The C++ reference says exactly this about std::counting_semaphore: acquire decrements the counter or blocks until it can, release increments it and unblocks acquirers, and unlike std::mutex it is not tied to threads of execution, so acquiring and releasing can happen on different threads.

Counting vs binary

std::binary_semaphore is just std::counting_semaphore<1>.

A realistic use: limiting concurrent access

#include <atomic>
#include <chrono>
#include <cstdio>
#include <semaphore>
#include <thread>
#include <vector>

using namespace std::chrono_literals;

std::counting_semaphore<8> slots(3);      // at most 3 threads may use the scarce resource
std::atomic<int> inside{0}, max_inside{0};

void use_resource(bool fail_early_bug) {
    slots.acquire();                                  // wait (P): count 3 -> 2 -> 1 -> 0, then block
    int now = ++inside;
    int seen = max_inside.load();
    while (now > seen && !max_inside.compare_exchange_weak(seen, now)) {}
    std::this_thread::sleep_for(20ms);
    --inside;
    if (fail_early_bug) return;                       // BUG: returns without giving the permit back
    slots.release();                                  // signal (V): count + 1, wakes one waiter
}

int main() {
    std::vector<std::thread> ts;
    for (int i = 0; i < 10; i++) ts.emplace_back(use_resource, false);
    for (auto& t : ts) t.join();
    std::printf("10 threads, 3 permits: max concurrent = %d\n", max_inside.load());

    // Misuse: three callers hit an error path that skips release(). The pool is now empty.
    std::vector<std::thread> bad;
    for (int i = 0; i < 3; i++) bad.emplace_back(use_resource, true);
    for (auto& t : bad) t.join();
    bool got = slots.try_acquire_for(200ms);
    std::printf("after 3 leaked permits, a new acquire succeeds = %s\n", got ? "yes" : "no (timed out)");

    // Binary semaphore: a one-shot signal between threads, released by a different thread.
    std::binary_semaphore ready(0);
    std::thread producer([&] { std::this_thread::sleep_for(10ms); ready.release(); });
    ready.acquire();
    producer.join();
    std::printf("binary semaphore signalled by another thread: ok\n");
}

Compiled with g++ -std=c++20 -O2 -Wall -Wextra -pthread sem.cpp (and again with -fsanitize=thread, same output, no reports) in a GCC 14 container:

10 threads, 3 permits: max concurrent = 3
after 3 leaked permits, a new acquire succeeds = no (timed out)
binary semaphore signalled by another thread: ok

Ten threads compete for three permits and never more than three are inside at once. The second line shows the classic misuse: three callers hit an early-return path that skips release, and the permits are gone for good, so every later caller waits until it times out.

ISR-to-task signalling vs resource-pool counting

An ISR (interrupt service routine: code the hardware runs when an interrupt fires) must never block, so it cannot take a lock. It can signal a semaphore, and a task blocked on that semaphore wakes to do the longer processing. The POSIX specification makes sem_post async-signal-safe, meaning it may be called from a signal handler (the user-space cousin of an interrupt handler), which is what makes signalling from such a context legitimate; on an RTOS (real-time operating system) use the ISR-specific give call the RTOS documents.

• Binary semaphore (initial 0): "an event happened". If two interrupts fire before the task runs, the second signal is not counted, so the task handles one event. That is fine when the task re-reads the device state anyway.
• Counting semaphore (initial 0): each interrupt adds one, so the task runs once per event and none is lost, provided the count cannot overflow its maximum.
• Resource pool (initial N): tasks wait to claim one of N buffers and signal to return it. Here the count means "free items".

Fairness and misuse

• Who wakes up. POSIX says sem_post, under a real-time scheduling policy (the POSIX real-time scheduling policies SCHED_FIFO, where a thread runs until it blocks or yields, and SCHED_RR, which adds a fixed time slice among threads of equal priority; SCHED_SPORADIC, where supported, follows the SCHED_FIFO rule), unblocks the highest-priority waiter, and the one that has waited longest among equals; under other policies POSIX leaves the choice to the implementation. The C++ reference documents no wake-up order at all, so do not rely on first-come-first-served. A waiter can in principle be passed over repeatedly (starvation); if you need strict arrival order, queue tickets explicitly (each waiter takes a number and is served in number order).
• Leaking a permit (shown above): release in a scope guard (a small object whose destructor gives the permit back on every exit path), not by hand on each path.
• Signalling without waiting inflates the count above the real number of resources, so more users get in than exist.
• A semaphore as a mutex. With no owner, the system does not know whom to boost to avoid priority inversion (a high-priority thread stuck behind a low-priority lock holder that a medium-priority thread keeps preempting), and any thread can release it by mistake.
• Waiting while holding another resource can deadlock: a thread holding permit A waits for permit B while another does the reverse.

Direct answer

Use a hash map for O(1) lookup plus a doubly linked list that orders entries from least to most recently used; evict from the least-recent end when the cache exceeds capacity. The catch is that a get changes the recency order, so even reads are writes and a read-write lock does not help. To stop one lock from being a bottleneck, split the cache into shards (independent sub-caches chosen by key hash), each with its own lock and its own LRU list, so threads touching different shards never contend. The price: eviction becomes approximate (least-recently-used within a shard, not globally). I would start with 16 shards of a lock-guarded LinkedHashMap and measure before anything fancier.

Data structures and eviction

• Per shard: LinkedHashMap in access order (Java), which keeps a hash table and a doubly linked list internally. get and put both move the entry to the "most recent" end. Overriding removeEldestEntry to return size() > capacity evicts the least recently used entry automatically on insert. All operations are O(1).
• Shard selection: spread the hash (h ^ (h >>> 16)) and mask with shards - 1 (shard count a power of two). Per-shard capacity = ceiling of total / shards. Masking with shards - 1 keeps only the low bits of the number, which is a fast way to compute h mod shards for a power of two. Spreading first mixes the high 16 bits into the low ones, because many hash codes differ only in their high bits. Worked example with 4 shards (mask 3) and integer keys, whose hash code is the number itself: keys 65536, 131072 and 196608 all have low two bits 00, so masking alone sends all three to shard 0. With spreading they become 65536^1 = 65537, 131072^2 = 131074 and 196608^3 = 196611, which land in shards 1, 2 and 3.
• LRU order trace (capacity 2): put(1), put(2) gives order 1 then 2 (2 most recent). get(1) moves 1 to the recent end: order 2 then 1. put(3) overflows, so the least recent end (2) is evicted: order 1 then 3.

Locking strategy

• One baseline: a single lock around the whole map is simple and correct, and for a modest request rate it is fine. Its cost is contention: every get and put serializes, and a thread holding the lock while the OS preempts it stalls everybody.
• Sharded locks: each shard has a ReentrantLock. get takes its shard's lock because it reorders the list. With n shards, two random operations collide with probability about 1/n.
• Never call the value loader (a database or network call on a cache miss) while holding a shard lock: it serializes every key in that shard behind one slow call and can deadlock if the loader calls the cache. Load first, then put; guard against duplicate loads of the same key ("cache stampede") with a per-key future map if it matters.

Working code (Java 21, compiled and run)

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.ReentrantLock;

public class ShardedLru<K, V> {
    private static final class Shard<K, V> {
        final ReentrantLock lock = new ReentrantLock();
        final LinkedHashMap<K, V> map;
        Shard(int capacity) {
            // accessOrder = true: get() moves the entry to the "most recent" end, so get() mutates
            map = new LinkedHashMap<>(16, 0.75f, true) {
                @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                    return size() > capacity;      // evict the least recently used entry of this shard
                }
            };
        }
    }

    private final Shard<K, V>[] shards;
    private final int mask;

    @SuppressWarnings("unchecked")
    public ShardedLru(int totalCapacity, int shardCount) {      // shardCount must be a power of two
        shards = new Shard[shardCount];
        int per = (totalCapacity + shardCount - 1) / shardCount;
        for (int i = 0; i < shardCount; i++) shards[i] = new Shard<>(per);
        mask = shardCount - 1;
    }

    private Shard<K, V> shardFor(K key) {
        int h = key.hashCode();
        return shards[(h ^ (h >>> 16)) & mask];
    }

    public V get(K key) {
        Shard<K, V> s = shardFor(key);
        s.lock.lock();                 // get() reorders the list, so even reads need the lock
        try { return s.map.get(key); } finally { s.lock.unlock(); }
    }

    public void put(K key, V value) {
        Shard<K, V> s = shardFor(key);
        s.lock.lock();
        try { s.map.put(key, value); } finally { s.lock.unlock(); }
    }

    public int size() {
        int n = 0;
        for (Shard<K, V> s : shards) { s.lock.lock(); try { n += s.map.size(); } finally { s.lock.unlock(); } }
        return n;
    }

    public static void main(String[] args) throws Exception {
        // 1. Single shard behaves as an exact LRU.
        ShardedLru<Integer, String> c = new ShardedLru<>(2, 1);
        c.put(1, "a"); c.put(2, "b"); c.get(1); c.put(3, "c");   // touching 1 makes 2 the eldest
        System.out.println("after put(3): get(1)=" + c.get(1) + " get(2)=" + c.get(2) + " get(3)=" + c.get(3));

        // 2. Concurrent stress: 8 threads, 200,000 operations each, 1,000 distinct keys, capacity 256.
        ShardedLru<Integer, Integer> big = new ShardedLru<>(256, 16);
        AtomicLong wrong = new AtomicLong();
        ExecutorService pool = Executors.newFixedThreadPool(8);
        List<Future<?>> fs = new ArrayList<>();
        for (int t = 0; t < 8; t++) {
            final int seed = t;
            fs.add(pool.submit(() -> {
                Random r = new Random(seed);
                for (int i = 0; i < 200_000; i++) {
                    int k = r.nextInt(1000);
                    if (r.nextInt(4) == 0) big.put(k, k * 31);
                    else { Integer v = big.get(k); if (v != null && v != k * 31) wrong.incrementAndGet(); }
                }
            }));
        }
        for (Future<?> f : fs) f.get();
        pool.shutdown();
        System.out.println("wrong values = " + wrong.get() + ", size <= 256: " + (big.size() <= 256));
    }
}

java ShardedLru.java in a Linux container (Eclipse Temurin 21) printed:

after put(3): get(1)=a get(2)=null get(3)=c
wrong values = 0, size <= 256: true

The first line is the exact-LRU check with one shard of capacity 2: after get(1), key 2 is the least recently used, so inserting 3 evicts 2. The second line comes from 8 threads each doing 200,000 operations (about 25% puts) over 1,000 keys into a 256-entry, 16-shard cache: no thread ever read a value that did not belong to its key, and the cache never exceeded 256 entries. This stress run checks safety (no corruption, no growth past capacity); it does not prove hit-rate quality or that locking is fair.

Trade-offs and what would change my choice

• Approximate global LRU: with 16 shards of 16 entries, a shard that happens to hold hot keys evicts them while another shard has stale entries. Uneven hash distribution and hot keys worsen it. For an exact LRU, use one lock.
• Very high read throughput (many more reads than writes, where shard locks still show contention): avoid taking a lock for the recency update on every hit. Either use a sampled or batched recency update (record the access in a buffer and apply the batch under the lock later), or a CLOCK approximation (a reference bit per entry that readers set without the lock, and eviction scans for an unset bit). Both give up strict ordering for read scalability. A tuned library cache such as Caffeine on the JVM is usually the better choice than a hand-built one in production, so know these techniques as the reasons such libraries exist.
• Kotlin: the same structure works with ReentrantLock or synchronized per shard, because the critical sections are short and never suspend. Use a coroutine Mutex only when the code inside the lock must suspend, and do not hold a thread lock across a suspension point.
• The size() method in the code above locks one shard at a time and adds the counts, so it returns a sum of per-shard snapshots taken at slightly different moments: safe (no unlocked reads, and the sum can never exceed the number of shards times the per-shard capacity), but not a number that was true at one instant. That bound equals the requested total only when the total divides evenly: because per-shard capacity is rounded up, a cache built for 10 entries over 4 shards holds up to 4 x 3 = 12 (a 1,000-key fill of that configuration reported size 12 when run). A strictly consistent size needs every shard lock held at once, acquired in a fixed order to avoid deadlock; reading each shard without a lock is worse, because it can see a half-updated map.
• Choose the shard count as a power of two a few times the number of threads that call the cache in parallel, then measure; too many shards waste capacity on rounding and fragment the LRU.

Pitfalls

Using ConcurrentHashMap plus a separate list lets the map and list disagree under races; a read lock around get on an access-ordered LinkedHashMap corrupts the list; a poor hashCode sends most keys to one shard and silently recreates the global lock.