07 — Operating systems and concurrency

Your largest gap, and the one the email spells out in the most detail — three full bullets naming processes, threads, locks, mutexes, semaphores, monitors, deadlock, livelock, context switching and scheduling. It is also narrow: nothing about paging, file systems or drivers. Study exactly the list.

Prereqs: none · Reading: 12 min · Cards: 20 · Code: code/concorrencia.py

The map

Everything here follows from one fact: threads share memory and processes do not. That single difference generates the whole topic. Because threads share the heap, two of them can interleave mid-update and corrupt it, which is why locks exist. Because locks make threads wait on each other, they can wait in a cycle, which is deadlock. Because a thread must sometimes stop and another start, the OS has to save and restore execution state, which is context switching — and because that is expensive, thread pools exist.

The second organising idea is that synchronisation primitives differ by what they own. A mutex has an owner; a semaphore is a counter with none; a monitor bundles data, lock and waiting condition into one object. Almost every question in this area is really asking which of those three you would reach for, and why.

What decides your score here

The mutex-versus-semaphore answer, given as ownership. It is the single most likely question in this topic. Almost everyone answers "a mutex is binary and a semaphore counts", which is a 2. The answer is ownership, and what ownership buys.

Knowing the GIL does not make Python thread-safe. This is the trick question, and answering it badly undoes whatever else you said about concurrency.

Coffman, and which condition you would break. Naming four conditions is knowledge; saying which one you break in practice and why the others are worse is judgement.

Processes and threads

A thread owns its stack, its registers and its program counter — that triple is the execution context, and nothing else belongs to it. The heap, the globals, the code segment and the file descriptors are all shared with its sibling threads. A process owns all of it, inside an isolated address space.

The consequence is the entire trade-off. Threads are cheap to create and cheap to switch between — roughly ten microseconds to create, one to five to switch — but because they share the heap, races are possible and you pay in synchronisation and in bugs. Processes cost ten to a hundred times more to create and are isolated by construction, but communication then requires explicit IPC: pipes, sockets, or shared memory you set up deliberately.

Context switching, and who starts it

A context switch saves one thread's execution state and restores another's. What gets saved is the program counter, stack pointer, general-purpose registers, status flags, and — when switching between processes — the pointer to the page table. It lives in the kernel's process or thread control block.

There are exactly two origins, and the email calls out the distinction. Involuntary: the hardware timer interrupt fires, typically every one to ten milliseconds, the hardware saves the minimum and jumps into the kernel, and the scheduler decides whether to switch. Other hardware interrupts — I/O completing, a packet arriving — can trigger the same path. Voluntary: the thread gives up the CPU itself, because it made a blocking syscall, tried to take a held lock, called sleep or yield, or finished.

Why it is expensive is the interesting part, because the direct cost of shuffling registers is small. The real cost is indirect: the incoming thread has a cold cache, and every miss is hundreds of cycles. Switching between processes additionally flushes the TLB, because the address space changed and the old translations are invalid — which is precisely why threads in one process are cheaper to switch between. The branch predictor is cold too. All of this is why thread pools exist: past some rate, creating and switching costs more than the work.

The primitives, by ownership

A mutex is a binary lock with an owner. Only the thread that acquired it may release it, and that ownership is not bureaucracy — it is what lets the OS detect misuse and perform priority inheritance, temporarily raising a lock holder's priority so a high-priority waiter is not blocked behind a preempted low-priority one. Use it to protect a critical section, and always with with, so an exception cannot leak the lock.

A semaphore is a counter with no owner. acquire decrements and blocks at zero; release increments. Because there is no owner, thread A can release what thread B acquired — which is exactly what makes it good for signalling between threads and for capping access to N resources, and exactly what makes it wrong for mutual exclusion. A bug in one thread can release another thread's critical section and nothing detects it, and with no owner there is no priority inheritance, so you are exposed to priority inversion.

That is the answer to the favourite question: the difference is ownership, and what ownership buys. Almost everyone stops at "binary versus counting".

A monitor is an object bundling the data, the lock protecting it, and the condition variables you wait on. It is a language construct rather than an OS one — Java's synchronized with wait and notify, Python's threading.Condition. And queue.Queue is a monitor off the shelf, which you should prefer to hand-rolled locking whenever it fits.

A condition variable is not a lock; it is a wait queue attached to one. wait() atomically releases the lock and sleeps, then re-acquires before returning.

Two rules about condition variables that are both bugs waiting to happen. Wait in a while, never an if — because of spurious wakeups, and because between the notify and the moment you hold the lock again another thread may have consumed the item. The predicate has to be rechecked. And use notify_all when threads wait on different predicates on the same condition, otherwise you can wake a thread whose predicate is still false and nobody makes progress.

Deadlock, and which condition to break

Deadlock requires all four Coffman conditions simultaneously: mutual exclusion, hold and wait, no preemption, and circular wait. Breaking any one of them eliminates it.

In practice you break circular wait, with a global lock ordering: number the locks and require every thread to acquire them in increasing order. No cycle can form. It is cheap, it is local to each call site, and it does not change what the program means.

The others are worse, and being able to say why is what makes this a judgement answer rather than a recital. Mutual exclusion is usually the entire point of the lock. No preemption means being able to kill and roll back, which databases can do because they have transactions and ordinary code cannot. And eliminating hold-and-wait means acquiring everything up front, which destroys concurrency.

Other defences worth naming: a timeout on acquire with a back-off, and deadlock detection via a wait-for graph plus killing a victim, which is what a database does.

Livelock is not deadlock. In deadlock the threads are blocked and stopped. In livelock they are running, changing state, and making no progress — which typically arises from the naive deadlock fix: detect the conflict, release everything, retry, and collide again in lockstep. The cure is randomised backoff, the same idea as Ethernet. Starvation is different again: the other threads do progress, and one never gets its turn. Fair queueing or priority aging fixes that.

Scheduling

Every modern OS is preemptive: the kernel takes the CPU back at the timer interrupt, so a thread stuck in an infinite loop cannot freeze the machine. Cooperative scheduling means a task only yields voluntarily, which is exactly asyncio's model — and why one blocking time.sleep() inside a coroutine stalls the entire event loop.

The policies, and the flaw in each: first-come-first-served suffers the convoy effect, where one long job holds up everyone. Shortest-job-first is optimal for mean waiting time but starves long jobs and requires predicting durations you do not know. Round-robin is fair and simple, but a smaller quantum means more context switches. Priority scheduling starves the low end unless you add aging. Multi-level feedback queues approximate shortest-job-first without prediction, by demoting anything that burns a full quantum. And Linux uses CFS, which runs whoever has run least, ordered in a red-black tree by virtual runtime.

Two terms that come up: CPU-bound versus I/O-bound — schedulers favour I/O-bound work because it yields quickly and keeps devices busy — and the fact that throughput, latency and fairness cannot all be maximised at once.

Modern concurrency

Concurrency is not parallelism. Concurrency is structuring work into tasks that progress independently; parallelism is running them at the same instant on different cores. You can have concurrency on a single core, and knowing that distinction scores.

Shared memory with locks is fast and race-prone. Message passing — each task owning its state and communicating over channels — is Go's and Erlang's model: "don't communicate by sharing memory; share memory by communicating." Lock-free structures use hardware compare-and-swap; worth knowing they exist, and that their cost is the difficulty of getting them right.

Two hardware realities. Memory reordering: compilers and CPUs reorder instructions, so without barriers another thread can observe your writes out of order. And false sharing: two independent variables landing in the same 64-byte cache line make cores invalidate each other's caches, and performance collapses with no logical race at all.

Amdahl's law bounds everything: speedup is limited by the serial fraction. At five percent serial, the ceiling is twenty times no matter how many cores you add.

Python, because they will push on it

The GIL means only one thread executes Python bytecode at a time. So threading gives no CPU parallelism in CPython, though it does give I/O concurrency, because the GIL is released during blocking I/O and inside C extensions.

And the trick question: the GIL does not make your code thread-safe. It guarantees one thread runs bytecode at a time; it does not make compound operations atomic. An increment compiles to load, add, store, and the interpreter can switch between them. You still need a lock.

There is a nuance worth having, because it takes this answer from correct to demonstrably understood. CPython only considers switching threads where it checks the eval breaker — at backward jumps and function calls. A bare x += 1 in a tight loop has neither between the load and the store, so it is almost never interrupted, and the race does not show up in your test. Put a single function call between the read and the write, which is how real code is written, and thousands of updates vanish. Run code/concorrencia.py and watch it happen. The lesson is that "I tested it and there was no race" proves nothing: whether the race appears depends on an interpreter implementation detail, not on your logic.

Which model to choose: multiprocessing for CPU-bound work, because the GIL blocks real parallelism and you pay for it in serialisation. threading for a few dozen blocking I/O calls, because it is simplest. asyncio for thousands of concurrent connections, because a coroutine costs far less than a thread — with the trap that one blocking call inside a coroutine stalls everything.

Say it

Cover the answers. Out loud, in English. This module has twenty scheduled cards; these are the six that matter most.

Now do this

The LeetCode concurrency problems are the fastest way in, but the exercises below them are worth more.

1. Print in Order — 15 min. Two semaphores, no polling.
2. Print FooBar Alternately — 20 min. The ping-pong invariant.
3. Building H2O — 30 min. Counted semaphores plus a barrier; release the permits after the barrier.
4. The Dining Philosophers — 30 min. Name the deadlock first, then fix it with a global ordering.

Then, off LeetCode and worth more than all four: write a deliberate deadlock with two locks and two threads acquiring in opposite orders, prove it hangs, and fix it by ordering. And run code/concorrencia.py to see the lost updates with your own eyes.

Stop when you can answer the mutex-versus-semaphore question and the GIL question without hesitating, and the concept cards for this module are averaging four or better.