This page condenses the OS fundamentals lessons into one review sheet. Use it to refresh the big picture before a design discussion or an exam; follow the links when a line doesn't feel obvious anymore.
Race conditions#
A race condition needs all three:
- Shared data
- At least one write
- No synchronization
Remove one: don't share (thread-local), don't write (immutable), or synchronize.
Atomic vs spinlock vs mutex#
The three tools differ in what they protect and in what a waiting thread does.
| Atomic op | Spinlock | Mutex | |
|---|---|---|---|
| What | One indivisible operation on one value | A flag you hold across a multi-step critical section | Same as a spinlock: a flag you hold across a region |
| Waiting | None; nobody holds anything (retry on CAS failure) | Waiter loops checking it (stays on the CPU, burns cycles) | Waiter sleeps; the OS wakes it later |
| Use | counter++, set a flag, swap one pointer |
Very short critical sections, no-sleep contexts (interrupt handlers) | Longer critical sections, normal application code |
| Cost | Cheapest: a single hardware instruction | Wasted CPU while waiting | Context-switch overhead while waiting |
The shape to remember: an atomic op is a different kind of thing (the operation is the work). A spinlock and a mutex are the same kind of thing (hold a flag, run a region) that differ only in what the waiter does: spin or sleep.
Selection rule:
- One value, one step → atomic
- Multi-step region, very short wait or can't sleep → spinlock
- Multi-step region, longer wait → mutex
Spinlocks are ordinary shared variables: you can have as many as you need (typically one per protected resource), and each is shared by all cores, not copied per core. They only help on multi-core machines.
Common alternatives to a plain mutex:
- Semaphore: allows N holders instead of one (a binary semaphore looks like a mutex but has no owner). Limits access to a pool of resources.
- Spinlock: same job as a mutex, but the waiter spins instead of sleeping.
- Reader-writer lock: many concurrent readers or one writer. Beats a mutex when reads dominate.
Semaphores#
Semaphores solve coordination, not data protection:
- Counting semaphore (N): cap concurrency (connection pools, in-flight request limits).
- Binary semaphore starting at 0: signal "something happened" from one thread to another.
- No ownership: any thread may release. Great for signaling, unsafe as a data lock.
In practice you combine them: semaphores to coordinate, a mutex to protect. The producer–consumer problem uses empty = N, full = 0 and a mutex, and must acquire the semaphore before the mutex.
Deadlock#
Deadlock needs all four conditions; prevention breaks one:
| Condition | How to break it |
|---|---|
| Circular wait | Global lock ordering (most practical) |
| Hold and wait | Acquire all locks at once, or none |
| No preemption | lock.acquire(timeout=...); release and retry (with rollback) |
| Mutual exclusion | Make resources sharable, e.g. read-write locks |
Liveness failures#
Three different failures all mean "some work never finishes."
| Deadlock | Starvation | Livelock | |
|---|---|---|---|
| Symptom | Blocked in a cycle, ~0% CPU | Ready but always skipped | Busy, no progress |
| Fix | Lock ordering | Aging, fair locks | Random backoff |
Details: Starvation vs Deadlock vs Livelock.
CPU scheduling#
CPU scheduling in one line each:
| Algorithm | Idea | Weakness |
|---|---|---|
| FCFS | Run in arrival order | Convoy effect: short jobs wait behind long ones |
| SJF | Shortest burst first | Needs burst times you rarely know; long jobs can starve |
| Round robin | Fixed quantum, then back of the queue | Quantum is hard to tune: too small thrashes, too large becomes FCFS |
| Priority | Highest priority runs first; static or dynamic (boost I/O-bound, lower CPU hogs) | Starvation unless you add aging |
| MLFQ | Several RR queues; demote CPU hogs, keep I/O-bound tasks high, age waiters up | More complex, but no manual tuning |
Processes, threads and switching#
These are the building blocks the other lessons rest on.
- A process owns an isolated address space; its threads share heap, data, code and files but keep their own stack and registers.
- Virtual memory maps per-process pages to frames; the TLB caches translations.
- A context switch between threads is cheap; between processes it also changes page tables and leaves the TLB and caches cold.
sleep()keeps locks;wait()releases them (sleep vs wait).
Scaling work#
Match the concurrency model to the kind of work you are doing.
- Thread pools: CPU-bound ≈ one thread per core; I/O-bound ≈
cores × (1 + wait/compute); bounded queue plus a rejection policy. - Async vs multithreading: async for waiting, threads/processes for computing, both for mixed workloads.
- Python GIL: threads help I/O-bound Python only; use processes for CPU-bound work, and you still need locks.
Key takeaways#
- Races need shared data, a writer and no synchronization.
- Atomic for one value; spinlock for tiny no-sleep regions; mutex for everything else in application code.
- Semaphores coordinate and limit; mutexes protect.
- Lock ordering prevents most deadlocks; aging and fair locks prevent starvation; random backoff breaks livelock.
- Match the concurrency model to the work: pools and async for I/O, one thread per core for CPU.