Concurrency, Synchronization & Deadlock Questions
Correctness of shared-state coordination between concurrent threads and tasks. Covers mutexes (futex-based and spin-then-sleep), semaphores, condition variables, spinlocks, reader-writer locks, and the producer-consumer pattern; atomic operations, compare-and-swap, lock-free and wait-free structures with the ABA problem and safe memory reclamation; memory ordering, barriers and acquire/release semantics; race conditions, data races, critical sections, time-of-check to time-of-use gaps and read-modify-write hazards; deadlock (the Coffman conditions, lock ordering, prevention and detection), livelock and starvation; priority inversion as a locking hazard and the priority-inheritance fix; designing thread-safe structures such as bounded queues, caches, rate limiters, event buses and work-stealing schedulers, with coarse versus fine-grained and per-key locking; alternatives to locking such as thread confinement, message passing, actors and transactional memory; and diagnosing and testing concurrency bugs (heisenbugs, race detectors, stress and replay, reviewing concurrent code). Excludes a specific language's threading API and memory model, concurrency for throughput and pool tuning, distributed locks and consensus, database isolation levels, RTOS ceiling protocols and schedulability, and interrupt masking between ISRs and main code.
Build a thread-safe rate limiter that allows bursts but caps the long-run rate. Explain your data structures and your synchronization, and how you keep the hot path fast under many concurrent callers.
Sample Answer
Direct answer
Use a token bucket in its single-word form (the Generic Cell Rate Algorithm, GCRA): each limiter keeps one 64-bit atomic, the theoretical arrival time (TAT, the earliest time the next request would be on schedule). A caller computes a new TAT from the current time and either rejects (no write) or installs it with one compare-and-swap (CAS), an atomic "write this only if the value is still what I read" instruction. There is no lock, state is one word per key, bursts up to burst are allowed, and the long-run rate can never exceed rate.
Why one word instead of the textbook bucket
The textbook bucket holds up to capacity tokens and spends one per request; it stores tokens (how many are left) and last_refill (when tokens were last topped up), and on each request it first adds (now - last_refill) * rate tokens, capped at capacity, then spends one if any remain. Those two fields must change together, so a naive version needs a mutex (or a double-width CAS). GCRA folds both into the single value TAT, so one CAS updates the whole state.
Let T = 1/rate be the emission interval and B = burst * T the burst tolerance. For a request at time now:
start = max(TAT, now)
new_TAT = start + T
allow iff new_TAT - now <= B
Why one number is enough: max(TAT - now, 0) is how far the schedule is ahead of the clock, which is the burst allowance already used, so the tokens left are floor((B - max(TAT - now, 0)) / T). A request is allowed exactly when at least one token is left, which is the same test as new_TAT - now <= B. Time passing lowers TAT - now by itself, so refilling needs no stored last_refill.
Hand trace with rate = 10/s, burst = 5 (so T = 100 ms, B = 500 ms), TAT starting at 0 and times in milliseconds. Requests at now = 0: TAT goes 100, 200, 300, 400, 500 (five allowed, tokens left 4, 3, 2, 1, 0); the sixth would give new_TAT = 600, and 600 - 0 = 600 > 500, so it is rejected with no write. At now = 300 tokens left are (500 - 200) / 100 = 3: three requests move TAT to 600, 700, 800 and a fourth is rejected. The equivalent textbook bucket (capacity 5) goes 5, 4, 3, 2, 1, 0 tokens, refills 3 tokens in 300 ms, and spends them, matching the program output below.
If allowed, CAS TAT from the value you read to new_TAT. If the CAS fails another caller moved TAT; reload and recompute. The time until a rejected caller may retry is TAT + T - B - now, usable for a Retry-After value (the HTTP response header that tells a client how long to wait, given either as a number of seconds or as a date).
Implementation, run under ThreadSanitizer
#include <atomic>
#include <cstdint>
#include <cstdio>
#include <thread>
#include <vector>
// Token bucket in "virtual scheduling" form (GCRA): one atomic word, the
// theoretical arrival time (TAT) in nanoseconds. Time is injected so the test is deterministic.
class RateLimiter {
public:
RateLimiter(std::uint64_t rate_per_sec, std::uint64_t burst)
: interval_ns_(1'000'000'000ull / rate_per_sec),
burst_ns_(burst * interval_ns_), tat_(0) {}
bool try_acquire(std::uint64_t now_ns) {
std::uint64_t tat = tat_.load(std::memory_order_relaxed);
for (;;) {
std::uint64_t start = tat > now_ns ? tat : now_ns;
std::uint64_t new_tat = start + interval_ns_;
if (new_tat - now_ns > burst_ns_) return false; // bucket empty: reject, no write
if (tat_.compare_exchange_weak(tat, new_tat,
std::memory_order_relaxed,
std::memory_order_relaxed))
return true; // on failure tat is reloaded; retry
}
}
private:
const std::uint64_t interval_ns_, burst_ns_;
alignas(64) std::atomic<std::uint64_t> tat_; // own cache line
};
// Releases all threads at the same instant (a spin gate), so their first calls really overlap.
static long hammer(RateLimiter& rl, std::uint64_t now_ns, int threads, int tries) {
std::atomic<long> granted{0};
std::atomic<bool> go{false};
std::vector<std::thread> ts;
for (int i = 0; i < threads; ++i)
ts.emplace_back([&] {
while (!go.load()) {}
for (int k = 0; k < tries; ++k)
if (rl.try_acquire(now_ns)) granted.fetch_add(1, std::memory_order_relaxed);
});
go.store(true);
for (auto& t : ts) t.join();
return granted.load();
}
int main() {
const std::uint64_t t0 = 5'000'000'000ull; // arbitrary start: 5 s on the injected clock
RateLimiter rl(10, 5); // 10 per second, burst of 5
// Contention check: 2000 rounds, each a fresh limiter and 8 gated threads at one frozen instant.
// Only the first 5 admissions write, so a single round gives the race a tiny window; many rounds do not.
int wrong_rounds = 0;
for (int r = 0; r < 2000; ++r) {
RateLimiter fresh(10, 5);
if (hammer(fresh, t0, 8, 50) != 5) ++wrong_rounds;
}
std::printf("2000 gated rounds: %d granted something other than 5 (expect 0)\n", wrong_rounds);
std::printf("burst at t=0: granted %ld (expect 5)\n", hammer(rl, t0, 8, 1000));
std::printf("after +300 ms: granted %ld (expect 3)\n", hammer(rl, t0 + 300'000'000ull, 8, 1000));
std::printf("after +10 s idle: granted %ld (expect 5, bucket does not bank more than burst)\n",
hammer(rl, t0 + 10'300'000'000ull, 8, 1000));
// Long-run rate: one request every 10 ms for 20 s of injected time (2000 attempts).
RateLimiter rl2(10, 5);
long ok = 0;
for (std::uint64_t i = 0; i < 2000; ++i) ok += rl2.try_acquire(t0 + i * 10'000'000ull);
std::printf("20 s at 100 req/s offered: granted %ld (5 + floor(10 * 19.99) = 204)\n", ok);
}
g++ -std=c++17 -O2 -Wall -Wextra -fsanitize=thread rate_limiter.cpp -o rate_limiter -pthread && ./rate_limiter
Output (GCC 14, Linux container, TSan reported nothing; the run takes on the order of half a minute under TSan and about a second without it, depending on the machine):
2000 gated rounds: 0 granted something other than 5 (expect 0)
burst at t=0: granted 5 (expect 5)
after +300 ms: granted 3 (expect 3)
after +10 s idle: granted 5 (expect 5, bucket does not bank more than burst)
20 s at 100 req/s offered: granted 204 (5 + floor(10 * 19.99) = 204)
The clock is passed in so the decisions are deterministic for a given instant. In each of the 2,000 gated rounds a fresh limiter faces eight threads released together by a spin gate at one frozen instant, and exactly the burst (5) gets through every time. The gate and the repetition matter: only the first five admissions write, so a single ungated run gives the race a tiny window (threads started one after another can finish their calls before the next one exists). To confirm the check can fail, replace the compare-and-swap with a plain store, a lost-update bug: the 2,000 gated rounds then report many rounds wrong and the burst line often grants more than 5 (some runs still print 5 on that line). The exact numbers differ from run to run and machine to machine, so only the direction of the rounds line is stable. The remaining lines are single frozen-instant checks: after 300 ms at 10 per second exactly 3 more pass (T = 100 ms), and an idle period never banks more than the burst. The last line checks the long-run cap: 2,000 attempts spread over 19.99 s admit 5 + 199 = 204 requests.
Synchronization choices
- Memory order is relaxed.
memory_order_relaxedasks only for atomicity of the operation, with no ordering guarantees about other memory. The limiter publishes no other data: the decision is the value itself. Acquire/release would add cost for nothing. (If an allowed request also hands over data through the limiter, that changes.) - No write on rejection. Under an abusive flood most calls hit the early
return false, which is a read of a cache line that stays shared. Only admitted requests write. - A failed compare-exchange is cheap, and the system still makes progress. A failed CAS normally means another caller changed the word (hardware that implements CAS with load-linked/store-conditional can also fail spuriously, which the loop absorbs), so the system as a whole keeps progressing: lock-free (some caller always finishes), not wait-free (every caller finishing in a bounded number of steps), because one unlucky caller can retry repeatedly. Load-linked/store-conditional is a pair of instructions where the store succeeds only if nothing disturbed the location since the load.
- Clock source. Use a monotonic clock (
steady_clock), never wall time that can jump. Threads read the clock slightly out of order;max(TAT, now)tolerates a stalenowbecause TAT never moves backwards. - Cache line. A cache line is the fixed-size block in which cores exchange memory (64 bytes on x86-64 and most Arm cores; some chips, such as Apple's M-series, use 128);
alignas(64)places the word at a 64-byte boundary (use 128 where the line is 128 bytes) so it keeps the hot word off lines holding other data, avoiding false sharing (unrelated variables on one cache line forcing the cores to trade ownership).
Keeping the hot path fast with many callers
Per-key limiters live in a map. Look the key up with a read-mostly structure (a hash map split into shards, each with a reader-writer lock that lets many readers in at once and one writer alone, or an immutable snapshot: a read-only copy of the map that is replaced wholesale on update) and create the limiter object once. Then the hot path is one atomic load, arithmetic, and at most one CAS.
When one key is so hot that its single CAS word becomes the bottleneck (every core hammering one cache line), the options and their costs are:
| Option | What you gain | What you give up |
|---|---|---|
Split into k sub-buckets, each with rate/k and burst/k, picked by thread or hash | k independent cache lines | Precision: one sub-bucket can reject while another has room. Burst must be at least k |
| Each thread takes a batch of tokens (say 16) from the shared word and spends locally | Shared writes drop by the batch size | Up to (threads x batch) tokens held idle, so the cap is looser in the short term |
| Mutex around a classic bucket | Simplest to reason about | Callers queue on the lock; a descheduled holder stalls everyone |
I would ship the single-word CAS version and only move to batching when profiling shows that line contended.
Sliding window state under concurrency
A sliding-window log (for example login attempts) stores one timestamp per recent attempt: memory is O(limit) per key and appending and pruning the deque needs a lock or a more complex structure. A sliding-window counter keeps two fixed-window counts and weights them, which is O(1) and atomic-friendly but approximate. A plain fixed window is cheapest but can admit about twice the limit across a window boundary. The token bucket keeps O(1) state, allows the burst the question asks for, and has no boundary effect; its cost is that it cannot express "exactly N in any rolling minute".
Pitfalls
- Using wall-clock time (jumps break the cap).
- Charging cost
cper request: usenew_TAT = start + c*T; a request costing more thanburstcan never pass, so reject it up front. - Integer overflow in the time arithmetic: 64-bit nanoseconds last for centuries; 32-bit milliseconds do not.
- A limiter per key that is never evicted leaks memory under key-spraying attacks.
Describe the purpose of a mutex, a semaphore, a condition variable and a barrier. For each, give one realistic use and one situation where it is the wrong tool.
Sample Answer
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
| Primitive | Purpose | Realistic use | Wrong tool when |
|---|---|---|---|
| Mutex | Exclusive access to shared data, with an owner: the thread that locks must be the one that unlocks (std::mutex::unlock from another thread is undefined behaviour: the program has no guaranteed meaning and may crash or corrupt data) | Protect an in-memory account table so a transfer updates both balances together | You need to signal "an event happened" between threads (nothing to hold), or you would hold it across a slow network call, blocking everyone else |
| Semaphore | A count of permits; no owner, so any thread can signal | Limit 3 concurrent downloads; an interrupt handler signalling a task | You need to protect a data structure and want ownership and priority inheritance: a semaphore has no owner, so the system cannot boost the holder |
| Condition variable | Sleep until a condition on shared state holds; the mutex guards that state | A consumer waiting until a queue is non-empty | Used alone as a flag or event: it keeps no state, so a notification sent before the waiter arrives is lost |
| Barrier | All N threads must arrive before any continues; reusable per phase | A simulation step: every thread finishes computing step k before any starts k+1 | The participants are not all guaranteed to arrive (one exits early or throws): the rest wait forever. Also wrong when threads do not actually need lockstep, because everyone then runs at the speed of the slowest |
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
waitsleeps 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 onwhile (!pred()) wait(lock), which also protects against spurious wakeups (a waiting thread returning although no thread notified it; the C++ reference noteswaitcan 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 (
noexceptpromises it will not throw).arrive_and_waitmeans "I have arrived; block until all N threads have". Every thread sees the callback's result afterwards.std::barrierfixes its participant count at construction; a thread that must leave early callsarrive_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_INHERITon 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.
What is a counting semaphore? Describe wait and signal, how it differs from a binary semaphore, and a realistic use such as limiting concurrent access to a scarce resource. What goes wrong with fairness or misuse?
Sample Answer
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:
| Step | Count | Effect |
|---|---|---|
| Thread 1 waits | 3 to 2 | proceeds |
| Thread 2 waits | 2 to 1 | proceeds |
| Thread 3 waits | 1 to 0 | proceeds |
| Thread 4 waits | 0 | blocks |
| Thread 1 signals | 0 to 1, then thread 4 takes it | thread 4 proceeds |
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
| Counting | Binary | |
|---|---|---|
| Range | 0 to N | 0 or 1 |
| Typical use | Pool of N identical resources; counting events so none is lost | One-shot signal between two threads; mutual exclusion in the simplest case |
| Signalling twice before anyone waits | Count becomes 2: both events remembered | The second signal is not remembered as a second event, so one event is remembered. What the API does with the extra signal depends on the platform: std::binary_semaphore makes a release beyond its maximum a precondition violation (undefined behaviour, so never rely on it), FreeRTOS's give call returns a failure code, and POSIX has no binary semaphore type, so sem_post would simply count up to 2 |
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.
Design a thread-safe LRU cache with concurrent get and put. Describe your data structures, locking strategy and eviction, and explain how you avoid one global lock becoming a bottleneck.
Sample Answer
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:
LinkedHashMapin access order (Java), which keeps a hash table and a doubly linked list internally.getandputboth move the entry to the "most recent" end. OverridingremoveEldestEntryto returnsize() > capacityevicts the least recently used entry automatically on insert. All operations are O(1). - Shard selection: spread the hash (
h ^ (h >>> 16)) and mask withshards - 1(shard count a power of two). Per-shard capacity = ceiling of total / shards. Masking withshards - 1keeps only the low bits of the number, which is a fast way to computeh mod shardsfor 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
getandputserializes, and a thread holding the lock while the OS preempts it stalls everybody. - Sharded locks: each shard has a
ReentrantLock.gettakes its shard's lock because it reorders the list. Withnshards, two random operations collide with probability about1/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
ReentrantLockorsynchronizedper shard, because the critical sections are short and never suspend. Use a coroutineMutexonly 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.
Compare lock-free algorithms against ordinary locking for a high-throughput service. Address contention behaviour, progress guarantees, memory reclamation and the risk of subtle bugs. When is lock-free actually faster?
Sample Answer
Recommendation
Default to ordinary locks (a mutex, a sharded mutex, or a reader-writer lock). Use lock-free structures only when a measurement shows the lock is the bottleneck, or when a hard constraint forbids blocking (a signal handler, a real-time thread, a path where a lock holder being descheduled would break a latency target). Even then, take a tested implementation instead of writing your own. A lock-free structure is not automatically faster; the measurement below shows a case where it is slower.
Progress guarantees, in plain terms
A blocking algorithm can be stuck forever if one thread (say, a lock holder) is descheduled or dies. The non-blocking levels are:
- Obstruction-free: a thread running alone finishes in a bounded number of steps. Example: an update that backs out and retries when it detects another thread interfering; two threads can keep backing each other out, but one running alone completes.
- Lock-free: when the program runs long enough, at least one thread makes progress (the system is never stuck, but an individual thread can retry indefinitely). Example: a CAS retry loop.
- Wait-free: every operation finishes in a bounded number of steps (no individual thread starves). Example: the single hardware atomic add mentioned below, which has no retry loop.
(These match the definitions in the Wikipedia article "Non-blocking algorithm".) A compare-and-swap (CAS) loop (read a value, compute a new one, store it only if nobody changed it, otherwise retry) is lock-free: a failed CAS means another thread's CAS succeeded, but one thread can keep losing. A single hardware atomic add (fetch_add) has no retry loop on CPUs that implement it directly.
What lock-free costs
- Memory reclamation: when a node is unlinked, other threads may still hold a pointer to it, so freeing it is dangerous. You need hazard pointers (each thread publishes "I am using this node" in a slot, and nobody frees a node that appears in a slot), epochs (a global counter; a node is freed only after every thread has moved past the epoch in which it was unlinked) or RCU (read-copy-update, a scheme where deleters wait until readers are done), which add code and per-thread state.
- The ABA problem: a CAS sees the same value A, but in between it changed to B and back to A (for example, a node freed and its address reused). The CAS succeeds when it should not. Concrete values (illustrative addresses): thread 1 reads head = node A at 0x100 whose next is B, and is paused. Thread 2 pops A, pops B, frees both, then pushes a new node that the allocator places at 0x100 again, whose next is C. Thread 1 resumes and runs CAS(head, A, B): head is 0x100, so it succeeds and sets head to B, which was freed (and is no longer in the stack), so the stack is now corrupt.
- Memory ordering: you must choose the weakest correct order for each atomic. Wrong choices often work on x86 and fail on Arm.
- Composability: an atomic operation changes one word. Updating two fields consistently needs a different design.
- Retry cost under contention: failed CAS attempts are wasted work and cache-line traffic.
Measured contention behaviour
A deliberately simple case: all threads increment one shared counter, using a mutex, an atomic fetch_add, and a CAS loop. The numbers are total throughput in millions of operations per second (Mops/s, summed over all threads, higher is better) from the program below, built with g++ -std=c++20 -O2 -pthread and run in a Docker Linux VM (aarch64, 14 vCPUs) on a Mac that was also running other jobs. checks: 1 means true: the three counters all ended equal to the expected total, so no increment was lost. One sample run:
threads mutex fetch_add cas_loop (Mops/s total)
1 209 542 541
2 28 238 304
4 57 151 91
8 59 37 16
checks: 1
Repeated runs of the same program varied a lot (the two-thread and eight-thread rows most of all, and a column order seen in one run was sometimes reversed in another), so the table is one sample, not a result. What recurred across many re-runs is the broad shape: with one thread the atomics are well ahead of the mutex; with two threads the atomics are ahead and the mutex is much lower; with four threads the three are closer together and the CAS loop can drop to the mutex's level; with eight threads the atomics lose their lead and the mutex is usually, but not always, on top. The shape matters more than the digits. Reading it (the explanations below are ESTIMATES, not measured):
- One thread, no contention: the atomic versions are typically about two to three times faster than the mutex (about 2.6 times in the sample), because a mutex does extra work to lock and unlock.
- Two to four threads: the atomics are ahead of the mutex (for example 238 and 304 against 28 at two threads in the sample), but the gap shrinks quickly and the spread is wide; at four threads the CAS loop can fall to the mutex's level. The mutex drop in the sample, from 209 to 28 once a second thread appears, is plausibly because a contended mutex makes waiting threads sleep and be woken, which costs far more than the uncontended lock and unlock.
- Eight threads on one hot counter: the atomic versions lose their lead: in most runs the mutex is ahead of both the CAS loop and
fetch_add, though not in every run (in the sample, 59 against 37 forfetch_addand 16 for CAS). A plausible explanation: every operation needs exclusive ownership of the same cache line, failed CAS attempts add wasted work, and under a mutex blocked threads sleep instead of all fighting for the line. Do not treat these numbers as general; they come from one shared VM, one trivial critical section, and say nothing about tail latency (the time taken by the slowest few percent of operations, which is what a user notices).
The better fix for a hot counter is neither: keep one counter per thread and add them up when read.
The program that produced the table:
#include <atomic>
#include <chrono>
#include <iostream>
#include <mutex>
#include <thread>
#include <vector>
using namespace std::chrono;
template <class F>
double run(int threads, long per_thread, F body) { // million ops per second
std::vector<std::thread> ts;
auto t0 = steady_clock::now();
for (int i = 0; i < threads; ++i) ts.emplace_back([&] { for (long k = 0; k < per_thread; ++k) body(); });
for (auto& t : ts) t.join();
double s = duration<double>(steady_clock::now() - t0).count();
return threads * per_thread / s / 1e6;
}
int main() {
const long N = 2'000'000;
std::mutex m; long locked = 0;
std::atomic<long> faa{0}, cas{0};
std::cout << "threads mutex fetch_add cas_loop (Mops/s total)\n";
for (int t : {1, 2, 4, 8}) {
double a = run(t, N, [&] { std::lock_guard<std::mutex> g(m); ++locked; });
double b = run(t, N, [&] { faa.fetch_add(1, std::memory_order_relaxed); });
double c = run(t, N, [&] {
long v = cas.load(std::memory_order_relaxed);
while (!cas.compare_exchange_weak(v, v + 1, std::memory_order_relaxed)) {}
});
std::cout << t << " " << (long)a << " " << (long)b << " " << (long)c << "\n";
}
const long expected = N * (1 + 2 + 4 + 8); // every thread count adds threads * N increments
std::cout << "checks: " << (locked == expected && faa.load() == expected && cas.load() == expected) << "\n";
}
When lock-free is actually faster
- Low contention per memory location, many cores, short operations: as in the one and two thread rows.
- Readers that write no shared, contended memory (RCU-style reads write nothing; hazard-pointer reads write only to a per-thread slot): reads scale while a lock's reader count would bounce a cache line.
- A lock holder can be descheduled (more runnable threads than cores): with a lock, everyone waits for the sleeping holder; with lock-free, others proceed. This helps tail latency, which the benchmark above does not measure.
- Places that cannot take a lock at all: signal handlers, interrupt handlers sharing data with threads, real-time threads where taking a lock invites priority inversion (a high-priority thread waiting on a low-priority lock holder).
It is slower or no better when one word is hammered by many threads (the eight-thread row), when the critical section is large (the lock-free version just copies more), or when the team cannot maintain the subtle code. Verify any lock-free code with ThreadSanitizer and stress tests, and test on a weakly ordered CPU such as Arm as well as x86.
Unlock Full Question Bank
Get access to all 32 Concurrency, Synchronization & Deadlock interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.