Operating Systems, from process to physical memory.
Every program you've ever run only worked because something quieter was managing the CPU, the memory, and the disk underneath it. This is that layer - explained, diagrammed, and boiled down to cheat sheets you can actually revise from.
What is an Operating System, really?
Strip away the desktop icons and it comes down to one job: turn one pile of shared hardware into something many programs can use safely, fairly, and at the same time.
// definition
Operating System (OS): system software that sits between hardware and applications, managing the CPU, memory, storage, and I/O devices, and exposing them to programs through a consistent set of services (system calls).
Think of the OS as a resource manager and a referee at the same time — it hands out CPU time slices, memory pages, and disk blocks, and it stops one program from trampling another's.
Why we use one
- • Lets many programs share one CPU, one RAM, one disk — without each one needing to know about the others.
- • Provides a stable, hardware-independent API (system calls) so software isn't rewritten per device.
- • Enforces protection: one process's bug or malice can't (normally) corrupt another's memory.
Why we need one
- • Hardware is dumb and single-minded — a CPU just executes instructions, it has no idea what "fair" means.
- • Without an arbiter, two programs writing to the same memory address is a crash waiting to happen.
- • Users need files, windows, and networking to *feel* simple — the OS absorbs the real complexity.
What if it disappeared?
Take the OS away and you're left with bare-metal hardware and no shared rules. Every application would need to hand-manage the CPU timeline itself, talk to disk controllers in raw hardware commands, and trust every other running program not to overwrite its memory. There'd be no multitasking, no file system abstraction, no plug-and-play devices — you'd be back to one program, one machine, one operator, like the earliest batch-processing computers of the 1950s.
Use cases
The same core ideas — scheduling, memory isolation, IPC — show up everywhere, just tuned differently.
Mobile
Android/iOS schedule apps, isolate them via processes/sandboxes, and manage battery-aware power states.
Servers & Cloud
Linux/Windows Server hosts thousands of containers and VMs, each relying on the kernel's scheduler and memory manager.
Embedded
Washing machines, routers, and car ECUs run tiny kernels (FreeRTOS, Zephyr) tuned for one job and a hard deadline.
IoT
Sensors run event-driven, low-power kernels that sleep almost always and wake only to sample and transmit.
Real-Time Control
Anti-lock brakes, pacemakers, and robotics need an RTOS that guarantees *when* a task finishes, not just that it does.
Virtualization
Hypervisors are OS-like layers that multiplex hardware across whole guest operating systems (VMware, KVM, Hyper-V).
Operating System structure
How the OS's own internals are organized changes how fast, safe, and maintainable it is.
Monolithic
Every service (drivers, FS, scheduler) runs in kernel space as one big program. Fast, but one bug can crash everything.
e.g. Linux, classic UNIX
Layered
The OS is split into numbered layers, each only using services of the layer below it.
e.g. Early THE OS
Microkernel
Kernel keeps only the bare minimum (IPC, scheduling, basic memory); drivers & file systems run in user space.
e.g. Minix, QNX, seL4
Hybrid
Monolithic core for speed, with microkernel-style modularity for select services.
e.g. Windows NT, macOS (XNU)
Process management
A process is a program in execution — its code plus its own private stack, heap, data, and CPU register state.
// definition
Process Control Block (PCB): the kernel's record for a process — PID, program counter, CPU registers, scheduling info, memory limits, and open file list. It's what makes a context switch possible.
// definition
Context switch: saving the PCB of the running process and loading the PCB of the next one, so the CPU can jump between processes and still resume each exactly where it left off.
fig — Process state transitions
CPU scheduling
The scheduler decides which ready process gets the CPU next — the policy it uses trades off fairness, throughput, and responsiveness.
| Algorithm | Preemptive? | Starvation risk | Convoy effect | Best for |
|---|---|---|---|---|
| FCFS | No | No | Yes | Simplicity, batch jobs |
| SJF | No | Yes (long jobs) | No | Minimizing avg. waiting time |
| SRTF | Yes | Yes | No | SJF + new-arrival responsiveness |
| Priority | Either | Yes | No | Importance-based ordering |
| Round Robin | Yes | No | No | Time-sharing, fairness |
| MLFQ | Yes | Possible | No | Mixed CPU/IO-bound workloads |
Turnaround = Completion − Arrival. Waiting = Turnaround − Burst. Get comfortable with a Gantt chart by hand for FCFS/SJF/RR — almost every exam question reduces to this.
Process synchronization
When multiple processes/threads touch shared data, uncoordinated access causes race conditions — synchronization is how we stop that.
// definition
Critical section: the part of code where a process accesses shared resources. A valid solution needs mutual exclusion, progress, and bounded waiting.
// definition
Race condition: the outcome of concurrent execution depends on the exact timing/order of operations — usually a sign a critical section wasn't protected.
| Primitive | How it works | Typical use |
|---|---|---|
| Mutex | 1 owner, binary lock/unlock | Protect a single critical section |
| Semaphore (counting) | Integer count, signal/wait | Bound access to N identical resources |
| Binary Semaphore | 0/1, any thread can signal | Signaling between threads (not just mutual exclusion) |
| Monitor | Language-level lock + condition vars | High-level mutual exclusion (Java `synchronized`) |
| Spinlock | Busy-waits instead of sleeping | Very short critical sections on multicore |
Classic synchronization problems
Deadlocks
A deadlock is a set of processes each waiting for a resource held by another in the set — none of them can ever proceed.
fig — Resource Allocation Graph — a cycle means deadlock (single-instance resources)
4 necessary conditions
Mutual Exclusion: At least one resource is held in a non-shareable mode.
Hold and Wait: A process holds one resource while waiting for another.
No Preemption: A resource can only be released voluntarily by the process holding it.
Circular Wait: A closed chain of processes, each waiting on a resource held by the next.
All four must hold simultaneously for a deadlock to be possible.
Handling strategies
| Strategy | Approach |
|---|---|
| Prevention | Deny one of the 4 conditions structurally (e.g. request all resources at once). |
| Avoidance | Grant requests only if the system stays in a safe state — Banker's Algorithm. |
| Detection & Recovery | Let deadlocks happen, detect via a wait-for graph, then kill/preempt a process. |
| Ignorance (Ostrich) | Assume it's rare enough not to bother — what most general-purpose OSes actually do. |
Banker's Algorithm (avoidance) checks, before granting a request, whether the system stays in a safe state — a state with at least one order in which every process could still finish. If no such order exists, the request is delayed.
Inter-process communication (IPC)
Processes have separate address spaces by design — IPC is the sanctioned way for them to exchange data anyway.
Shared Memory
The OS maps the same physical memory region into both processes' address spaces. Fast (no kernel involved after setup), but the processes must synchronize access themselves.
Message Passing
Processes exchange data via send()/receive() through the kernel — pipes, message queues, sockets. Simpler to get right, slower than shared memory.
Multithreading models
Threads are lightweight processes that share an address space. How user threads map onto kernel threads defines the model.
Many-to-One
Many user threads map to one kernel thread. Fast to create, but one blocking call blocks all threads.
One-to-One
Each user thread gets its own kernel thread. True concurrency, but thread creation is heavier (Windows, Linux).
Many-to-Many
Many user threads multiplexed over a smaller/equal pool of kernel threads — flexible, but complex to implement.
Memory management, logical vs. physical address space
A running program only ever sees a logical address — the MMU translates it to a physical one at run time.
// definition
Logical address: generated by the CPU during a program's execution; also called a virtual address. It's what the program itself sees and uses.
// definition
Physical address: the actual location in RAM. The Memory Management Unit (MMU) maps every logical address to one, transparently to the program.
fig — Logical → physical address translation
Contiguous memory allocation
Each process gets one unbroken block of memory. Simple to address, but memory fragments over time.
| Strategy | Rule | Trade-off |
|---|---|---|
| First Fit | Allocate the first hole big enough | Fast, but can leave lots of tiny gaps near the front |
| Best Fit | Allocate the smallest hole that still fits | Less wasted space per hole, but slow and causes tiny unusable slivers |
| Worst Fit | Allocate the largest available hole | Leaves a bigger, more reusable leftover hole |
External fragmentation (holes scattered between allocations) is the core weakness here — it's the reason paging exists.
Paging
Logical memory is split into fixed-size pages, physical memory into same-size frames — any page can live in any frame, killing external fragmentation.
fig — Page-table based address translation
Logical Address
Page Table
Physical Address
// definition
TLB (Translation Lookaside Buffer): a small, fast cache of recent page-table lookups — avoids hitting main memory twice (once for the page table, once for data) on every access.
// definition
Internal fragmentation: the wasted space inside the last page of a process, when its size isn't an exact multiple of the page size. Paging trades external for internal fragmentation.
Segmentation
Memory is divided by logical unit — code, stack, heap, data — each segment sized to what it actually needs, not a fixed page size.
fig — Segment table + variable-size memory regions
Segment Table (per segment: base + limit)
| Segment | Base | Limit |
|---|---|---|
| Stack | 1400 | 1000 |
| Heap | 2600 | 400 |
| Code | 0 | 600 |
| Data | 3200 | 1100 |
Physical Memory (variable-size chunks)
Segmentation matches how programmers think (functions, arrays, the stack) but re-introduces external fragmentation — which is why most real systems combine it with paging (segmented paging).
Swapping
When physical memory is oversubscribed, the OS temporarily moves an idle process (or its pages) out to disk to free RAM for someone more active.
Modern OSes mostly swap out individual pages rather than whole processes — this is the mechanism behind virtual memory letting you "use" more RAM than you physically have.
Storage management & disk structure
Disks are addressed as a huge array of logical blocks; the OS decides in what order to service pending requests to minimize costly seek time.
fig — Disk-arm movement under SCAN scheduling
| Algorithm | Sweep pattern | Note |
|---|---|---|
| FCFS | Service in arrival order | Fair but can cause long seeks |
| SSTF | Nearest request first | Low seek time, can starve far requests |
| SCAN | Sweep like an elevator, reverse at the end | No starvation, uneven wait at edges |
| C-SCAN | Sweep one direction only, jump back to start | Uniform wait time across disk |
| LOOK | Like SCAN but reverses at last request, not disk end | Avoids wasted travel to empty ends |
| C-LOOK | Like C-SCAN but jumps to first request, not disk start | Most efficient of the family |
Real-time systems
Correctness here depends on both the result and the time it arrives in — a perfect answer delivered late can be a failure.
Hard real-time
Missing a deadline is a system failure, full stop. Airbag controllers, pacemakers, flight-control computers.
Soft real-time
Missing a deadline degrades quality but isn't catastrophic. Video streaming, online gaming, audio playback.
Two named scheduling algorithms worth remembering: Rate Monotonic Scheduling (fixed priority — shorter period ⇒ higher priority) and Earliest Deadline First (dynamic priority — whoever's deadline is soonest runs next).
Cheat sheets & imp. points
Formulas, comparisons, and the lines examiners actually look for — skim this the night before.
Memory formulas
| Quantity | Formula |
|---|---|
| Logical address space size | 2^m (m = bits in logical address) |
| Physical address space size | 2^n (n = bits in physical address) |
| Number of pages | Logical space size ÷ Page size |
| Number of frames | Physical space size ÷ Frame size |
| Page table size | Number of pages × size of one entry |
| Effective Access Time (EAT) | hit_ratio × mem_time + miss_ratio × (mem_time × 2) |
One-line "imp." recall per topic
Most-confused pairs
Process vs Thread
A process owns memory/resources; a thread is a schedulable path of execution inside one.
Paging vs Segmentation
Paging = fixed-size, invisible to programmer. Segmentation = variable-size, matches program structure.
Mutex vs Semaphore
Mutex has ownership (only the locker unlocks it). A semaphore is just a counter anyone can signal.
Deadlock vs Starvation
Deadlock: nobody proceeds, ever. Starvation: someone eventually proceeds, just not this someone, for a long time.
Multiprogramming vs Multitasking
Multiprogramming keeps the CPU busy across jobs; multitasking specifically time-slices for interactive responsiveness.
Logical Address vs Physical Address
Logical = what the CPU/program generates. Physical = what actually appears on the memory bus.