Recall refresh,
conversational depth.
You have done the course, so most of this is three clean sentences per topic rather than a rebuild. The exception is cache locality at the bottom, which you should be able to reach for unprompted, because it is the payoff line in a sequencer answer.
Process against thread
A process owns an address space and a set of resources. A thread is a schedulable execution context inside a process, and every thread in a process shares that address space, so they share the heap, the globals and the file descriptor table. What each thread keeps to itself is its stack, its registers including the program counter, and its thread-local storage.
| Shared between threads | Private to each thread |
|---|---|
| Heap and all dynamically allocated memory | Stack, typically 1 to 8 MB of reserved address space |
| Global and static data | Registers, including the program counter and stack pointer |
| Open file descriptors and sockets | Thread-local storage |
| Code, and loaded libraries | Signal mask, and errno |
| The page table, so pointers mean the same thing everywhere | Scheduling priority |
Everything that follows is a consequence of that one line. Communication between threads is free because a pointer is valid in all of them, and communication between processes needs a pipe, a socket or explicitly shared memory because a pointer in one process is meaningless in another. Threads therefore need locking around shared state, and processes mostly do not. And a thread that corrupts memory or segfaults takes the whole process with it, whereas a crashed process leaves its siblings alive, which is why browsers and databases put untrusted or risky work in separate processes on purpose.
Creation cost differs for the same reason. A thread needs a
stack and a scheduler entry, on the order of tens of
microseconds. A process needs a new address space and page
tables, on the order of hundreds of microseconds to
milliseconds, which fork softens by sharing the
parent's pages copy-on-write until one side writes.
This is precisely why multiprocessing escapes
Python's interpreter lock and threads do not. Separate
processes have separate interpreters because they have
separate address spaces, so there is no shared interpreter
state to serialise. You pay for it at the boundary, since
anything crossing it must be serialised and copied rather
than pointed at.
The four deadlock conditions
All four must hold at once. That is the useful part, because it means every practical fix works by breaking exactly one of them, and naming which one is what makes the answer sound like understanding.
| Condition | Means | Break it by |
|---|---|---|
| Mutual exclusion | A resource cannot be shared, so only one holder at a time | Using lock-free structures, immutable data, or per-thread copies. Often impossible, since the exclusion is the point. |
| Hold and wait | A thread holding one resource requests another | Acquiring everything you need in one atomic step, or releasing everything before asking for more. |
| No preemption | A resource cannot be taken away from its holder |
Timeouts. try_lock with a back-off
gives the system a way to force a release.
|
| Circular wait | A cycle exists in the who-waits-for-whom graph | Global lock ordering. Number every lock and always acquire in ascending order. |
Lock ordering is the fix that is actually used, and the reason it works is worth stating: if every thread acquires locks in ascending order, then a thread waiting for lock n holds only locks below n. Any cycle would require some thread to be waiting for something numbered below what it holds, which the rule forbids. The cycle cannot form, so the deadlock cannot happen. That is a proof rather than a mitigation, which is why it beats timeouts and retries.
# the classic: two threads, two locks, opposite order
# thread A: with lock1: with lock2: ...
# thread B: with lock2: with lock1: ...
# the fix: order by a stable identity, so both threads agree
first, second = sorted([lock_a, lock_b], key=id)
with first:
with second:
...Livelock: threads keep responding to each other and making no progress, so they are busy rather than stuck. Starvation: a thread is permanently outcompeted for a resource it is technically eligible for. Neither is a deadlock, and a deadlock detector will not find them.
Blocking against non-blocking I/O
A blocking call does not return until the data is ready, so the kernel moves the thread off the run queue and it consumes no CPU while it waits. A non-blocking call returns immediately, either with whatever data was available or with an error saying there is nothing yet, which leaves the caller responsible for finding out when to try again. Readiness notification through something like epoll is what makes the second usable, because it lets one thread wait on thousands of descriptors at once.
The important correction to a common misconception: a blocked thread is not spinning, it is not burning cycles, and it is not being polled. It has been removed from the scheduler's run queue entirely and will be put back when the data arrives. Blocking is cheap in CPU terms. What it costs is a whole thread, with its stack and its scheduler entry, sitting idle per outstanding operation.
So the real trade is about how many concurrent operations
you need. A hundred connections with a thread each is
completely reasonable and much simpler to write. A hundred
thousand connections with a thread each is hundreds of
gigabytes of stack and a scheduler drowning in context
switches, so you switch to one thread watching all of them
through a readiness API. That is exactly the trade Python's
asyncio makes on your behalf.
| Model | How it waits | Cost per connection |
|---|---|---|
| Blocking, thread per connection | Thread sleeps in the kernel | A stack, plus a scheduler entry |
| Non-blocking with polling | Caller retries in a loop | CPU burned on failed attempts. Almost never right. |
| Non-blocking with readiness notification | One thread waits on many descriptors | A few hundred bytes of state |
| Asynchronous completion, io_uring or IOCP | Kernel performs the operation and reports it finished | Similar, with fewer syscalls per operation |
Worth having the distinction ready: readiness models tell you "you can read now, go ahead", while completion models tell you "I already read it, here is the data". The second removes a syscall per operation, which is what makes io_uring interesting for high message rates.
Why a context switch costs
The visible part is small: save the registers, swap the stack pointer, load the new thread's registers, and if it is a different process also switch the page table root. That is a few hundred nanoseconds of direct work, perhaps one to two microseconds including the scheduler decision.
The bill you actually pay is indirect and larger.
- Cache pollution. The incoming thread's working set is not in L1 or L2, and the code and data it needs will evict what the outgoing thread had. When the first thread resumes, it takes thousands of cache misses to warm back up. This is usually the dominant cost.
- TLB flushing. Switching to a different process means a different page table, so the translation cache is invalidated. Every memory access then needs a page walk until the TLB refills. Tagged TLBs reduce this but do not remove it.
- Branch predictor state. The predictor has learned the outgoing thread's branches and now mispredicts the incoming one's until it relearns.
- Pipeline drain. The trap into the kernel serialises the pipeline, throwing away speculative work in flight.
So a switch that measures at 1 to 2 microseconds of direct cost frequently costs 10 to 50 microseconds of real throughput once the cold caches are counted. That is the number that matters and the reason it is worth mentioning.
Pinning a thread to a core keeps its cache warm and stops the scheduler moving it. Busy-waiting instead of blocking trades CPU for the avoided switch, which is a good trade when the wait is shorter than the switch cost. Running fewer threads than cores means nobody is preempted. And a lock-free ring buffer avoids the switch entirely, since a thread that never blocks is never descheduled.
Virtual memory and page faults
Every process sees its own flat address space, and the hardware translates those virtual addresses to physical ones through per-process page tables, one 4 KB page at a time. That gives isolation for free, since a process simply has no way to name another's memory, and it lets the kernel allocate lazily, because a mapping can exist with no physical page behind it yet. A page fault is the hardware trapping to the kernel when a translation is missing, and the kernel then either supplies a page or kills the process.
| Kind of fault | What happens | Cost |
|---|---|---|
| Minor | The page is in physical memory but not in this process's table yet, or it is a copy-on-write page being written for the first time. The kernel fixes the mapping. | Roughly a microsecond |
| Major | The page is not in memory at all and must come from disk or swap. | Microseconds on NVMe, milliseconds on a spinning disk. Four to six orders of magnitude worse. |
| Invalid | The address is not mapped at all. This is a segmentation fault. | The process dies |
The TLB is a small hardware cache of recent translations, on the order of a few thousand entries, and it exists because otherwise every memory access would need several extra memory accesses just to walk the page table. At 4 KB per page a few thousand entries covers only a few megabytes, which is why a program striding randomly through a large heap can thrash the TLB even when the data is all resident. Huge pages, at 2 MB each, are the standard fix: same TLB, a thousand times the coverage.
Two allocation consequences worth knowing.
malloc of a gigabyte usually returns instantly
and uses no physical memory, because the kernel only records
the mapping and supplies pages on first touch. And
overcommit means the total of all promises can exceed
physical memory, which is fine until everyone touches their
pages at once and the out-of-memory killer has to choose a
victim.
Mutex against semaphore against condition variable
Distinguish them by the question each one answers rather than by their APIs.
| Answers | Key property | Typical use | |
|---|---|---|---|
| Mutex | "Only one at a time in here" | Has an owner. Whoever locked it must unlock it, which is what makes priority inheritance possible. | Protecting a shared structure while you mutate it |
| Semaphore | "At most N at a time" | A counter with no owner. Any thread may signal, including one that never waited. | Limiting concurrency to a pool, or signalling between a producer and a consumer |
| Condition variable | "Sleep until this becomes true" | Always paired with a mutex. Waiting atomically releases the mutex and sleeps, then reacquires on wake. | A bounded queue: wait while empty, wait while full |
A binary semaphore looks like a mutex and is not one, and the difference matters. A mutex has an owner, so the system knows who is holding up whom and can boost that thread's priority to unstick a high-priority waiter. A semaphore has no owner, so it can be posted by a thread that never waited, which is exactly what you need for signalling from an interrupt handler or a producer, and exactly what makes it wrong for mutual exclusion.
Why the condition variable release must be atomic
You hold the mutex, check the predicate, and find the queue
empty. If waiting were two separate steps, unlock and then
sleep, a producer could run in the gap, add an item and
signal a condition nobody is waiting on yet. You would then
sleep forever with work sitting in the queue.
wait() releasing the mutex and sleeping as one
atomic operation is what closes that window, and it is the
single reason condition variables exist rather than being
assembled from a mutex and a sleep.
with cv: # hold the mutex
while not queue: # while, never if
cv.wait() # atomically release + sleep, reacquire on wake
item = queue.pop()while, never if
Two reasons. Spurious wakeups are permitted by the specification, so a thread can wake with nothing having changed. And with several waiters, another thread may take the item between your wake and your reacquiring the mutex. Both mean the predicate must be rechecked after waking, so the wait belongs in a loop.
A read-write lock allows many concurrent readers or one writer, which pays off only when reads greatly outnumber writes. A spinlock busy-waits instead of sleeping, which is right only when the critical section is shorter than a context switch, and disastrous otherwise.
Cache lines, locality, and why a ring buffer wins
This is the one to be able to reach for without being asked. It is the answer to "why is your sequencer fast", and it connects directly back to the NumPy page.
The numbers the argument rests on
| Where the data is | Latency, roughly | Relative |
|---|---|---|
| Register | 0 cycles | — |
| L1 cache | about 1 ns, 4 cycles | 1x |
| L2 cache | about 4 ns | 4x |
| L3 cache, shared | about 15 ns | 15x |
| Main memory | about 80 to 100 ns | roughly 100x |
Two structural facts sit on top of those numbers. Memory moves in 64-byte cache lines, never in single bytes, so touching one byte fetches the 63 around it whether you want them or not. And the hardware prefetcher detects sequential and fixed-stride access and fetches ahead of you, so a predictable walk hides the memory latency almost entirely while an unpredictable one exposes all of it.
That is why a factor of 100 in latency does not turn into a factor of 100 in runtime for good code, and why it very much does for bad code. The gap is not really cache against memory, it is predictable access against unpredictable access.
The bounded window question
You need the last N events, with old ones expiring as new ones arrive. Two implementations:
| Ring buffer | Hash map | |
|---|---|---|
| Memory | One contiguous array of N slots, allocated once | A table plus a separately allocated node per entry, scattered across the heap |
| Adding an entry |
Write at head, advance
head = (head + 1) % N. Overwrites the
oldest for free.
|
Hash, probe, possibly allocate a node, and separately track and evict the oldest |
| Walking the window | Sequential addresses. One miss brings in 64 bytes, so with 16-byte entries the next three are already there, and the prefetcher has the following lines in flight. | A pointer chase to an unpredictable address per entry. Nothing to prefetch, because the next address is only known once the current node has arrived. |
| Allocation | None after startup, so no allocator locks and no fragmentation | Per insert, unless pooled |
| Eviction | Implicit in the wraparound | Explicit bookkeeping, usually a second structure |
The window is bounded and I only ever touch it in order, so I do not need the hash map's ability to look up an arbitrary key. A ring buffer gives me the same operations on one contiguous allocation, so a walk is sequential, one cache miss brings in the next several entries, and the prefetcher stays ahead of me. The hash map scatters a node per entry across the heap, so every step is a pointer chase to an address the hardware could not predict, and each one exposes the full memory latency. That is roughly two orders of magnitude on the access, not a constant factor.
The honest qualifier, which strengthens rather than weakens the answer: this holds because the access pattern is sequential over a bounded window. If you genuinely needed to look up an arbitrary order ID out of millions, a hash map is the right structure and the pointer chase is the price of the capability. The ring buffer wins here because you never needed that capability. Choosing the weaker structure when the weaker structure suffices is the actual insight.
Cache line race
Because the fixed cost of a DRAM access dominates the marginal cost of the bytes. Selecting a row and column in the memory array is most of the latency, and once that row is open, streaming out 64 bytes instead of 8 costs almost nothing extra. Transferring in blocks amortises the expensive setup over more useful data.
Larger lines also mean fewer tags to store, since the cache must track the address of each block it holds and a bigger block means less metadata per byte cached.
Two compounding effects. First, one miss pays for several elements: at 16 bytes per entry, a single 64-byte fetch delivers four, so three out of four accesses hit L1 for free. Second, and more importantly, the prefetcher can see the pattern. A fixed stride is predictable, so the hardware issues the next fetches before you ask, and the memory latency overlaps with the work you are already doing instead of stalling you.
Scattered access defeats both. Each entry is on its own line, so nothing is shared, and the next address is stored inside the current node, so it cannot be known until that node has arrived. The misses serialise: you pay the full latency, one after another, with nothing overlapping.
Because they are different circuits solving different problems. An L1 cache is small, built from SRAM with roughly six transistors per bit, and sits within a few millimetres of the core, so it can answer in a handful of cycles. DRAM is one transistor and one capacitor per bit, which is why it is dense and cheap enough to sell by the gigabyte, but reading it means sensing a tiny charge, amplifying it, and destroying and rewriting the row in the process. It also lives off-chip, across a bus with its own protocol and queueing.
You cannot have both. Making L1 big would make it slow, since a larger array takes longer to address and signals take longer to cross it. That is exactly why there is a hierarchy at all: each level trades capacity against latency, and the hierarchy is an admission that no single technology can be both large and fast.
Name it, one line, move on
select passes the whole descriptor set to
the kernel on every call and scans it, so it is O(n) per
call and capped near 1024. epoll registers
interest once and returns only what is ready, so it is
O(ready) and scales to hundreds of thousands.
kqueue is the BSD and macOS equivalent.