Concurrency, OS Threads, And Memory

What's being tested

Interviewers probe your ability to reason about concurrency primitives, OS threads, and memory model interactions to build correct, low-latency, deterministic software. They expect clear tradeoffs between user-space and kernel mechanisms, measurable costs (context-switch, cache effects, page faults), and practical synchronization choices. Optiver values predictable latency and correctness under load, so show how your design guarantees ordering, atomicity, and recoverability.

Core knowledge

• Process vs thread: a process is an isolated address space; a thread shares that space and file descriptors. On Linux use `fork`/`exec` and `pthread` APIs to illustrate differences.

• Virtual memory and page fault handling: kernel resolves faults, possibly loading pages via `mmap`; page faults cost micro- to milliseconds depending on IO. Expect copy-on-write semantics after `fork`.

• TLB, CPU caches, and cache coherence: TLB misses and cache line invalidation dominate latency; false sharing (adjacent fields on same cache line) kills throughput on multicore.

• Memory ordering and memory barrier: languages expose weaker models; use `std::atomic` with acquire-release semantics or full fences (`atomic_thread_fence`) to enforce ordering, not just volatile.

• Atomic operations and lock-free: `compare_exchange_strong` and `fetch_add` are cheap on a single core but cost cache-coherence traffic cross-core; use only when correctness and progress are proven.

• Locks tradeoffs: mutex (blocking, uses `futex` on Linux) reduces CPU spin but causes context switches; spinlock wastes cycles but is preferable for very short critical sections on same NUMA node.

• Context switch and syscall costs: a context switch can cost thousands of cycles; a syscall (user→kernel→user) adds overhead—batch small operations or use shared-memory/eventfd to avoid frequent syscalls.

• Scheduler & preemption: kernel scheduler decisions (timeslices, priority) affect latency and fairness; be aware of priority inversion and mitigation (priority inheritance, `SCHED_FIFO` tweaks).

• Heap vs stack: per-thread stack is fixed and cheap; dynamic allocations (`malloc`, `mmap`) have fragmentation and locking costs; use per-thread caches (arenas) for high throughput.

• NUMA and locality: memory access latency depends on node affinity; pin threads (`pthread_setaffinity_np`) and allocate (`numa_alloc_onnode`) to reduce remote memory penalties.

• Amdahl's law quantifies parallel speedup: $S(N)=\frac{1}{(1-p)+p/N}$ — optimize the parallel fraction p and minimize serial bottlenecks for low-latency systems.

Worked example — Design an Event-Driven CPU Overheat Controller

Frame: ask for simulation granularity, number of cores, deterministic ordering, whether events can be simultaneous, and cooling-actuator latency. Key pillars: (1) represent each core as a finite-state machine (per-core state) with temperature and cooling mode, (2) use an ordered event stream (monotonic timestamps + tie-breaker) to drive deterministic transitions, (3) a scheduling model for actuators (shared vs per-core cooling) and atomic updates, (4) safe shutdown and idempotent transition logging. Implementation sketch: choose a single-threaded event loop for determinism or a multi-threaded worker pool with a global sequencer (sequence numbers) to preserve ordering; use a deterministic priority queue for pending events and versioned state to detect out-of-order processing. Tradeoff: a single-threaded loop is simple and deterministic but may not meet wall-clock throughput; a multi-threaded design gains parallelism at the cost of complexity (synchronization, replay). Close by proposing test harnesses (fuzzed timestamped traces), deterministic replay logs, and monitoring hooks; say "if more time, I'd add persisted event logs and state checkpoints for crash recovery."

A second angle — Explain OS processes, threads, and memory

When asked to explain core OS abstractions, start by differentiating user-space and kernel-space responsibilities: address spaces, descriptors, and process isolation live in kernel-managed structures. Emphasize threading models: kernel threads vs user-level threads, and consequences for blocking syscalls. Discuss memory mapping (`mmap`) versus anonymous heap, and the role of page tables and TLBs. Show how scheduling and preemption interact with synchronization primitives (e.g., why a blocking mutex can hide latency but introduces context-switch cost). Finish by describing common developer APIs (`pthread_create`, `std::thread`, `madvise`) and when you'd prefer each.

Common pitfalls

Pitfall: Equating threads with processes.
Many candidates answer interchangeably; explicitly state differences in address space, descriptor sharing, and copy-on-write behavior to avoid missing isolation and performance implications.

Pitfall: Optimizing for assumed contention without measurement.
Jumping to lock-free data structures is tempting; explain why you'd instrument (`perf`, `latency histograms`) first and prefer per-thread batching or fine-grained locking unless hot-path contention is proven.

Pitfall: Not calling out non-functional requirements.
Failing to state determinism, failure modes, or test plans costs points; always describe how you'd validate ordering, recover from crashes, and measure `p99` latency.

Connections

Interviewers may pivot to I/O multiplexing (`epoll`/`kqueue`), low-latency memory allocators and garbage collection impact, or distributed synchronization (consensus, clock sync) when the scope grows beyond a single host. Be ready to discuss profiling tools (`perf`, `eBPF`) and kernel tuning knobs.

Further reading

• Operating Systems: Three Easy Pieces — practical chapters on virtual memory, concurrency, and scheduling.

• The Art of Multiprocessor Programming — deep coverage of lock-free algorithms and memory models; good for proofs and concurrent data structures.