Concurrency and Multithreading

1The mental model (what this really is)#

Start with the one distinction people fumble in the first 30 seconds.

Concurrency is about structure. Parallelism is about execution.

• Concurrency: your program is organized as multiple independent tasks that can make progress in overlapping time windows.
• Parallelism: two of those tasks literally run at the same instant on two cores.
• You can have concurrency on a single core: the CPU interleaves tasks on time slices, often around 10ms each.
• You can have parallelism without much concurrency: a parallel-for that splits one array across 8 cores.
• Rob Pike said it best: concurrency is dealing with a lot of things at once, parallelism is doing a lot of things at once. Say that line and you have already set yourself apart.

Process versus thread.

• A process has its own memory space. Threads live inside a process and share that memory.
• That sharing is the whole point and the whole problem: fast to communicate through (no copying, no serialization), terrifying to get right (everyone can scribble on everyone else's data).
• A thread switch costs roughly 1 to 5 microseconds.
• A full process context switch is heavier, because the OS also swaps the page tables and flushes the TLB.
• That cost is why thread pools exist: pay to create a thread once, then reuse it.

The thing to internalize: no coordination means undefined.

• When two threads touch the same memory and at least one writes, with no coordination, the outcome is undefined. Not "usually fine." Undefined.
• The CPU reorders instructions. The compiler reorders instructions.
• Per-core caches mean thread A's write may sit in a store buffer and stay invisible to thread B for a while. (L1 hit is about 1ns, a trip to main memory is about 100ns.)
• A race condition is not just two threads clobbering a value. It is the absence of a happens-before relationship that guarantees one thing is visible to another.

2Why it matters / core idea#

The core idea you are being tested on: correctness under nondeterminism.

• A single-threaded program runs the same way every time.
• A multithreaded one can run a huge number of interleavings. For two threads of n steps each, the count of valid interleavings blows up combinatorially, and your code has to be correct in all of them.
• Interviewers love this because it maps directly to production.

Why this maps to real pain.

• Concurrency bugs pass every test, pass code review, run fine for six months, then take down checkout on Black Friday and never reproduce on your laptop.
• The classic one: Therac-25, a radiation machine whose race condition gave patients lethal overdoses in the 1980s.
• These bugs are not academic.

So what the interviewer is actually asking.

• When they bring up threads, the real question is: do you reason about the bad interleaving, or do you only think about the happy path?
• Your job is to show you instinctively ask "what if a context switch happens right here?"
• Narrate it out loud. The interviewer is grading your reasoning, not just your final code.

3The template (how it works, with pseudocode)#

Most concurrency problems reduce to a few primitives. Know these cold.

Mutex (lock). Mutual exclusion: only one thread holds it at a time. Wrap the shared state.

lock.acquire()
try:
 # critical section: touch shared state here
 balance = balance - amount
finally:
 lock.release() # ALWAYS release, even on exception

• Keep the critical section as small as possible. Lock too much and you kill parallelism. Lock too little and you have a race.
• An uncontended mutex is cheap: tens of nanoseconds, often just an atomic flip in user space.
• A contended one is expensive: losers get parked by the OS and woken later, which is a syscall plus a context switch.

Semaphore. A counter that allows up to N threads through.

sem = Semaphore(10)
sem.acquire() # blocks if 10 already in flight
try:
 call_downstream()
finally:
 sem.release()

• A mutex is basically a semaphore with N = 1, plus ownership, so only the holder can release it.
• Use it to limit concurrency, like a connection pool of 10.

Condition variable. Lets a thread sleep until some predicate becomes true, without busy-waiting (no burning a core in a spin loop).

lock.acquire()
while queue.is_empty():
 condition.wait(lock) # releases lock, sleeps, reacquires on wake
item = queue.pop()
lock.release()

• Always wait in a while loop, never an if. Two reasons: spurious wakeups are real, and another thread may have changed the state back before you reacquire the lock.

Atomics. Hardware-level operations that are indivisible, like compare-and-swap (CAS).

• CAS(addr, expected, new) sets the value to new only if it currently equals expected, and reports whether it worked.
• On x86 this compiles to a single LOCK CMPXCHG instruction.
• This is the building block for lock-free code.

The toolbox in one line each.

• Mutex: exclusive access.
• Semaphore: N-at-a-time.
• Condition variable: "wait until."
• Atomics: fine-grained lock-free updates.
• If you can name when to reach for each, you sound like you have used them, not read about them.

4A worked example (walk through one problem step by step)#

Classic question: "Two threads each increment a shared counter a million times. Final value?"

• Naive answer: two million. Wrong, and that is the trap.

Why counter++ is not one operation.

• It is three: read counter into a register, add one, write it back.
• Now picture the bad interleaving:
• Thread A reads 5. Context switch.
• Thread B reads 5, adds one, writes 6. Context switch back.
• Thread A still has 5 in its register, adds one, writes 6.
• Two increments happened, counter went up by one. We lost an update.
• This is a read-modify-write race. Over two million operations you land somewhere unpredictable: anywhere between about 1,000,001 and 2,000,000, and it changes every run.

How I fix it: three options, and I would mention all three to show range.

1. Mutex around the increment. Correct and simple, but every one of the 2 million increments takes a lock. Under heavy contention the threads spend their time fighting over the lock (parking and waking), not working. Throughput can drop below single-threaded.
2. Atomic increment. Use atomic.fetch_add(1). The hardware guarantees the read-modify-write is indivisible. Faster than a mutex here because there is no blocking, just a CAS retry loop under the hood. Still, both cores touch the same cache line, so it serializes on the cache coherence protocol (MESI) and does not scale linearly.
3. Shard it. Give each thread its own private counter on its own cache line, sum the two at the end. Zero contention during the hot loop. This is the senior answer, because it shows you know the fastest lock is the one you never take. Java's LongAdder is exactly this idea productized.

Close with the visibility point.

• Even the final read needs to happen-after both threads finish (a join or a memory barrier), or you might read a stale cached value from a store buffer that never flushed.
• Saying that unprompted signals you actually understand memory models, not just locks.

The fastest lock is the one you never take.

5Variations and gotchas#

The interviewer will throw these at you one by one. Have a crisp one-liner and a fix for each.

Deadlock. The famous one.

• Two threads, two locks, each holds one and waits for the other. Forever.
• Know Coffman's four conditions by heart, because interviewers ask: mutual exclusion, hold-and-wait, no preemption, circular wait.
• All four must hold at once, so breaking any one makes deadlock impossible.
• Practical fix, almost always: lock ordering. Every thread acquires locks in the same global order (say, always lower address first), which kills the circular-wait condition.
• Say "I enforce a consistent lock acquisition order" and you have answered the follow-up before it is asked.
• Backups if they push: lock timeouts with retry, or tryLock with backoff.

Livelock.

• Threads are not blocked, they keep reacting to each other and making no progress.
• Two people stepping side to side in a hallway, both polite, both stuck.
• Harder to spot than deadlock, because CPU usage looks busy, not frozen.

Starvation.

• A thread never gets the resource because others keep jumping the queue.
• Common with reader-writer locks, where a steady stream of readers starves a waiting writer.
• Fixed with fair locks or aging (bump a waiter's priority the longer it waits).

Priority inversion.

• A low-priority thread holds a lock a high-priority thread needs, and a medium-priority thread preempts the low one, so the high one waits on the medium one indirectly.
• This almost killed the 1997 Mars Pathfinder mission: the rover kept resetting until JPL patched it remotely.
• Fix: priority inheritance (the lock holder temporarily inherits the waiter's priority).

The ABA problem.

• In lock-free CAS code, a value goes A, then B, then back to A.
• Your CAS sees A and thinks nothing changed, but the world moved underneath you (the memory may have been freed and reallocated).
• Fixed with version-tagged pointers (a counter bumped on every change) or hazard pointers.
• If you can explain ABA, you look like you have written real lock-free code.

False sharing.

• Two unrelated variables land on the same 64-byte cache line.
• Two cores updating them separately still thrash the cache line back and forth over the coherence bus, as if they were the same variable.
• You can lose a 2x or more speedup for no logical reason.
• Pad your data to separate cache lines (Java has @Contended).
• This is a performance gotcha, not a correctness one, and naming it impresses systems-focused interviewers.

6Trade-offs#

Every concurrency decision is a trade between safety, throughput, and latency, plus complexity.

Locking granularity.

• Coarse-grained (one big lock over the whole structure): easy to reason about and correct, but it serializes everything, so throughput tanks past a couple of threads.
• Fine-grained (many small locks, one per bucket or node): gives you parallelism but multiplies deadlock risk and cognitive load.
• Lock-free structures: best throughput under contention, worst debuggability. Reach for them rarely and only with good reason, because getting the memory ordering right by hand is where careers go to die.

Blocking versus non-blocking.

• Blocking (mutexes, condition variables): simple, and the OS parks idle threads so they burn no CPU, but each park/wake is a syscall costing microseconds.
• Non-blocking (spinlocks, CAS loops): avoids the context-switch cost, great when the critical section is nanoseconds and the lock is held briefly, terrible when it is long, because you burn a whole core spinning on nothing.

The honest meta-trade: the cheapest concurrency is less shared state.

• Immutable data, message passing (Go channels, the actor model, Erlang), and per-thread ownership sidestep entire classes of bugs.
• When I can design the race away instead of locking around it, I do.
• That instinct, "don't share, or share immutable," is what makes code maintainable and is a strong thing to say out loud.

7Mistakes that cost people the round#

• Confusing concurrency and parallelism. First question, first impression. Nail it in one sentence.
• Thinking volatile means atomic. volatile (in Java/C#) gives you visibility and ordering, not atomicity. A volatile counter increment is still a read-modify-write race. People mix these up constantly, and it is an instant tell.
• Checking a condition with if instead of while around a condition variable wait. Spurious wakeups are real, and the predicate can change before you reacquire the lock.
• Holding a lock while doing I/O or calling external code. A network call can block for seconds under a lock you grabbed for a microsecond of work, and a callback can try to reacquire the same lock and deadlock you.
• Only describing the happy path. If you never say "context switch here" or "bad interleaving," the interviewer assumes you do not see the race.
• Reaching for lock-free immediately. It signals the opposite of maturity. Start simple, measure, then optimize. Senior engineers default to the clearest correct solution and only go lock-free when a profiler says the lock is the bottleneck.
• Forgetting to release the lock on an exception path. Use RAII (C++ lock_guard), Java try-with-resources, or try/finally. A leaked lock is a frozen service and a 3am page.

8Your practice path (study order)#

Go in this order. Each builds on the last.

1. Thread-safe counter, three ways: mutex, atomic, sharded. Reason about why each is correct and benchmark the three under 8 threads so you feel the contention difference.
2. Bounded blocking queue (producer/consumer). The canonical condition-variable problem. You need two conditions, not-full and not-empty. If you can code this cleanly, you understand coordination.
3. Reader-writer lock. Many readers or one writer. Forces you to think about fairness and writer starvation, and when it even pays off (reads must vastly outnumber writes).
4. Dining philosophers. The deadlock teaching problem. Solve it with lock ordering, then with a limiting semaphore (allow at most 4 of 5 philosophers to sit). Explain both.
5. Print in order / FizzBuzz with N threads. Common LeetCode-style "concurrency" tags (LeetCode 1114, 1116, 1195). Pure coordination practice with semaphores or condition variables.
6. A simple thread pool. Submit tasks, a fixed set of worker threads pull from a shared blocking queue. Ties everything together and is a frequent "build this" prompt in senior loops.
7. A lock-free stack with CAS, if you are targeting systems roles. Hit the ABA problem on purpose so you can talk about it fluently.

One habit that matters more than any single problem: do them by hand, then reason out loud about the worst interleaving for each. That out-loud habit is exactly what you need in the room.

9Where this shows up#

Concurrency surfaces in a few predictable places.

• Big tech systems rounds and low-level coding rounds (Google, Meta, Amazon, Microsoft): the thread-safe-structure and deadlock questions.
• Infrastructure, database, and trading firms (HFT shops like Jane Street and Citadel, plus Oracle and cloud teams): deep into memory models, lock-free, and false sharing. They push until you break, because in a trading engine a microsecond of lock contention is real money.
• Backend and senior/staff interviews: folded into system design, as connection pools, rate limiters, idempotency keys, and "what happens under concurrent requests."
• Mobile and frontend roles: a lighter version through async/await and the main-thread rule (never block the UI thread).

The pattern underneath all of it.

• The deepest versions live at companies writing their own runtimes, databases, or exchanges.
• The lighter versions are everywhere, because every service handling more than one request at a time is a concurrency problem, whether the interviewer calls it that or not.

Want to see which rounds at which companies lean hardest on this? Check the company guides to map these patterns to the interviews you are actually taking.