Concurrency & threads

The four consistency points to know

• Sequential consistency: every operation appears in a global total order; each thread's order matches its program order. The mental model you wish was true. Almost no real hardware provides it for free.
• x86 (TSO): total store order. Stores are not reordered with stores; loads are not reordered with loads; stores can be delayed past later loads (store buffer). Strong-ish, but the store-buffer rule trips people up.
• ARM / POWER (weak): most reorderings allowed. Need explicit barriers (DMB, ISB).
• Happens-before: partial order across threads enforced by synchronization (lock acquire/release, atomic with appropriate ordering, thread join).

C++ memory orders (memorize)

1. Mutual exclusion — only one thread holds the resource.
2. Hold and wait — a thread holds one resource while waiting for another.
3. No preemption — resources can't be forcibly released.
4. Circular wait — a cycle exists in the resource-wait graph.

Practical deadlock-prevention recipes:

• Lock ordering: enforce a global order (e.g., always acquire account_a before account_b if id(a) < id(b)). Breaks circular wait.
• Try-lock with backoff: if you can't get all needed locks, release what you have and retry. Breaks hold-and-wait.
• Single coarse lock: when in doubt and not perf-critical, use one lock. Eliminates circular wait by construction.

Python — using queue.Queue

import threading, queue

q = queue.Queue(maxsize=10)   # thread-safe, blocking on full/empty

def producer():
    for i in range(100):
        q.put(i)               # blocks if full
        print(f"produced {i}")

def consumer():
    while True:
        item = q.get()         # blocks if empty
        print(f"consumed {item}")
        q.task_done()

threading.Thread(target=producer, daemon=True).start()
threading.Thread(target=consumer, daemon=True).start()
q.join()

C++ — explicit condition variables

#include <mutex>
#include <condition_variable>
#include <queue>

template<typename T>
class BoundedQueue {
    std::mutex m;
    std::condition_variable not_full, not_empty;
    std::queue<T> q;
    size_t cap;
public:
    BoundedQueue(size_t c) : cap(c) {}

    void put(T x) {
        std::unique_lock lk(m);
        not_full.wait(lk, [&]{ return q.size() < cap; });
        q.push(std::move(x));
        not_empty.notify_one();
    }

    T take() {
        std::unique_lock lk(m);
        not_empty.wait(lk, [&]{ return !q.empty(); });
        T x = std::move(q.front()); q.pop();
        not_full.notify_one();
        return x;
    }
};

What's atomic in Python?

Single bytecode ops are atomic (e.g., list.append, dict[k] = v). But x += 1 is not — it's load + add + store, three separate bytecodes. Two threads can both load, both add, both store — losing one increment.

The mental model

• Tasks wrap coroutines; scheduled on the loop.
• Futures are awaitables; resolved by external code.
• Event loop uses selectors (epoll on Linux, kqueue on macOS) under the hood for I/O readiness.
• Cancellation: task.cancel() raises CancelledError at the next await point.

import asyncio

async def fetch(url):
    print(f"start {url}")
    await asyncio.sleep(1)         # simulated I/O — yields control to loop
    print(f"done {url}")
    return url

async def main():
    results = await asyncio.gather(*(fetch(u) for u in urls))
    return results

asyncio.run(main())

from multiprocessing import shared_memory
import numpy as np

# Producer
shm = shared_memory.SharedMemory(create=True, size=4 * 1024 * 1024)
arr = np.ndarray((1024, 1024), dtype=np.float32, buffer=shm.buf)
arr[:] = np.random.randn(1024, 1024)
print(shm.name)   # pass to consumer

# Consumer (different process)
shm = shared_memory.SharedMemory(name="...")
arr = np.ndarray((1024, 1024), dtype=np.float32, buffer=shm.buf)
# zero-copy access; no pickle round-trip

CAS — the building block

CAS(addr, expected, new): atomically set *addr = new if *addr == expected. Returns success/failure. Hardware provides this via CMPXCHG (x86) or LDREX/STREX (ARM). Foundation of lock-free queues, hashmaps, ref counts.

The ABA problem

Thread T1 reads A, gets preempted. Thread T2 changes A → B → A. T1 resumes, runs CAS expecting A — it succeeds, but the world changed underneath. T1's logic may now be invalid (e.g., the node it pointed to was freed and the address reused).

Mitigations:

• Tagged pointers: pointer + version counter (e.g., 48-bit ptr + 16-bit version). CAS the whole 64-bit word.
• Hazard pointers: each thread publishes "I'm using ptr X." Memory not freed until no thread declares hazard.
• RCU: defer freeing until all readers active before the write are done.
• Garbage collection: in GC'd languages, the GC won't reuse addresses while references exist.

RCU (Read-Copy-Update)

Readers access shared data without locking. Writers create new copies and atomically swap pointers. Old copies freed only after all readers that started before the swap have finished (a "grace period"). Used heavily in the Linux kernel for read-heavy data (routing tables, file system mounts).

Hazard pointers

Per-thread pointers marking objects "in use." Memory reclamation defers freeing until no thread declares a hazard pointer to that object. Solves ABA and use-after-free in lock-free structures. More memory-efficient than RCU; more complex bookkeeping.

• LC 1114 Print in Order
• LC 1115 Print FooBar Alternately
• LC 1116 Print Zero Even Odd
• LC 1117 Building H2O
• LC 1188 Design Bounded Blocking Queue
• LC 1195 Fizz Buzz Multithreaded
• LC 1226 The Dining Philosophers
• LC 1242 Web Crawler Multithreaded

Concurrency quiz — readiness check

1. Implement a thread-safe LRU.
   Show answer

   Hashmap + doubly-linked list, single mutex around both. For higher concurrency: striped locks (per-bucket mutex). Java's old ConcurrentHashMap used this. Newer designs use lock-free with hazard pointers but they're production-grade complex.

2. What does Python's GIL block exactly?
   Show answer

   Bytecode execution. Released during I/O syscalls and in C extensions that explicitly release it (NumPy, PyTorch CUDA). Doesn't help CPU-bound pure Python — use multiprocessing or PEP 703 free-threaded Python (3.13t).

3. Diagnose a race in this code: counter += 1 from N threads.
   Show answer

   Not atomic — load + add + store. Two threads can both load N, both store N+1, lose one increment. Fix: lock around the increment, or use threading.Lock + with, or atomic counter (Python: itertools.count(); C++: std::atomic<int>).

4. Explain memory_order_acquire / release.
   Show answer

   Acquire load: prevents subsequent reads/writes from being reordered before this load. Release store: prevents prior reads/writes from being reordered after this store. Pair them to establish happens-before across threads (the SC-DRF model).

5. Producer-consumer with bounded buffer.
   Show answer

   Mutex + two condition variables (not_full, not_empty) + a queue + capacity. put: acquire mutex, wait on not_full while size==cap, push, signal not_empty. take: acquire mutex, wait on not_empty while empty, pop, signal not_full. Both predicate-tested via while loop (spurious wakeups).

6. What's the ABA problem?
   Show answer

   Thread reads value A; preempted; another thread changes A→B→A; first thread's CAS succeeds (sees A) but the world changed. Fix: tagged pointers (pointer + version counter), hazard pointers, RCU, garbage collection.

7. Why striped lock instead of single mutex on a hashmap?
   Show answer

   Lock per bucket → reduces contention. Threads operating on different keys touch different mutexes, parallelize. Tradeoff: more memory, more complex resize. Java's old ConcurrentHashMap used 16 stripes by default.

8. Implement a multithreaded web crawler.
   Show answer

   Thread pool of N workers. Shared thread-safe URL queue (deque + lock OR queue.Queue). Shared visited set (with lock). Per-host rate limiter. Termination: "no more URLs and no in-flight tasks." Use concurrent.futures.ThreadPoolExecutor in Python.

9. asyncio vs threading vs multiprocessing — pick one and explain.
   Show answer

   asyncio: many concurrent I/O operations, single thread, cooperative scheduling. Threading: I/O-bound or C-extension-heavy work where GIL is released. Multiprocessing: pure-CPU parallelism in Python. Free-threaded Python (3.13t) blurs the line.

10. Why does a single sync call kill an asyncio event loop?
    Show answer

    The loop is single-threaded; while it executes a sync function, no other coroutine runs. time.sleep(1), sync DB query, requests.get() — all freeze the loop. Use await asyncio.sleep, async DB drivers, aiohttp; or wrap blocking calls in asyncio.to_thread().

11. Coffman's four conditions — name them.
    Show answer

    (1) Mutual exclusion. (2) Hold and wait. (3) No preemption. (4) Circular wait. Break any one to prevent deadlock. Most common practical fix: lock ordering (always acquire in same global order).

12. RWLock — when does it help vs hurt?
    Show answer

    Helps: read-heavy workloads with rare writes (caches). Many readers proceed in parallel. Hurts: write-heavy or balanced — RWLock has higher overhead than plain mutex due to read-counter management; writer can starve. Test under workload before assuming RWLock.

13. Lock-free vs wait-free?
    Show answer

    Lock-free: at least one thread makes progress (system as a whole progresses). Wait-free: every thread makes progress in bounded steps (stronger). Most practical lock-free structures (Michael-Scott queue) are not wait-free; wait-free is rare due to complexity.

14. What is RCU?
    Show answer

    Read-Copy-Update. Readers access shared data without locking. Writers create new copies and atomically swap pointers. Old copies freed only after all readers that started before the swap have finished. Used in Linux kernel for read-heavy data (routing tables, etc.).

15. Why doesn't Python need volatile like Java/C++?
    Show answer

    Python's GIL serializes bytecode execution → all reads/writes are effectively atomic + visible at bytecode boundaries. Without GIL (free-threaded 3.13t), this guarantee weakens; PEP 703 introduces atomic primitives. Java's volatile ensures visibility across threads; C++ uses std::atomic.

16. What's the actor model?
    Show answer

    Concurrency primitive: actors are isolated entities with private state, communicate via async messages. No shared memory → no races. Used in Erlang, Akka. Tradeoffs: easier reasoning, but message-passing overhead and harder to handle some patterns (transactional updates).

17. Implement double-checked locking correctly.
    Show answer

    Classic singleton init. if (instance == null) { lock; if (instance == null) instance = new T(); unlock; }. Subtle bug in Java pre-5: instance write can be reordered before construction completes. Fix: declare instance volatile (Java) or use std::atomic with acquire/release (C++). Or just use static init (Java's class loader is thread-safe).

18. What does memory_order_relaxed guarantee?
    Show answer

    Atomicity only — no ordering with other operations. Use for counters where order doesn't matter. Reads/writes can be reordered by compiler / CPU. Faster than seq_cst on weak-memory architectures (ARM).

19. Why is std::shared_ptr thread-safe in some ways but not others?
    Show answer

    The reference count is atomic (thread-safe to copy/destroy shared_ptr from multiple threads). But the pointed-to object's contents are not protected — accessing the same object from multiple threads still needs a mutex. Common bug source.

20. What's the difference between condition variable's wait and a busy loop?
    Show answer

    Busy loop: thread spins, holding mutex or polling — wastes CPU. Condition variable: thread releases mutex, sleeps until notify, atomically reacquires mutex on wake. Always use a while loop around wait to handle spurious wakeups.