Operating Systems Documentation
OS on one page — processes, threads, scheduling formulas, synchronization, deadlocks, paging, page replacement, file systems and disk scheduling.
A one-page reference for OS: definitions, formulas, the algorithms you're asked to solve by hand, and the comparisons interviewers love. Each section links to a detailed note with worked examples. For a revision list of questions, see Top 50 OS interview questions.
1. OS Basics
| Term | Meaning |
|---|---|
| Kernel | Core of the OS running in privileged (kernel) mode |
| System call | A program's request to the kernel: fork, exec, read, write, open |
| User vs kernel mode | Restricted vs full hardware access; a system call or interrupt switches modes |
| Interrupt | A signal (from hardware or software) that makes the CPU run a handler |
| Monolithic kernel | All services in the kernel (Linux) — fast, less isolated |
| Microkernel | Minimal kernel, services in user space — reliable, more overhead |
Types of OS: batch, time-sharing, real-time (hard/soft), distributed, embedded, mobile.
2. Processes
new → ready ⇄ running → terminated
↑ ↓
└── waiting (I/O)
- PCB stores: PID, state, program counter, registers, priority, memory info, open files.
- Memory layout: text (code) · data (globals) · heap (grows up) · stack (grows down).
fork()returns 0 to the child and the child's PID to the parent; n forks in sequence → 2ⁿ processes.- Zombie: finished, exit status not collected. Orphan: parent died; adopted by init/systemd.
- IPC: pipes, FIFOs, message queues, shared memory (fastest), sockets, signals.
Details: Process vs Thread.
3. Threads
| Process | Thread | |
|---|---|---|
| Memory | Own address space | Shares code, data, heap |
| Own | Everything | Stack, registers, PC |
| Creation / switch | Heavy | Light |
| Crash | Isolated | Can kill the whole process |
| Communication | IPC | Shared variables |
User-level threads: fast, but a blocking call blocks all. Kernel threads: real parallelism. Models: many-to-one, one-to-one (Linux/Windows), many-to-many.
4. CPU Scheduling Formulas
Turnaround time (TAT) = Completion time − Arrival time
Waiting time (WT) = TAT − Burst time
Response time = First time on CPU − Arrival time
Throughput = processes completed / time
5. Scheduling Algorithms
| Algorithm | Preemptive | Picks | Problem |
|---|---|---|---|
| FCFS | No | Earliest arrival | Convoy effect |
| SJF | No | Shortest burst | Starvation, needs burst estimates |
| SRTF | Yes | Shortest remaining time | Starvation, many switches |
| Priority | Either | Highest priority | Starvation → fix with aging |
| Round Robin | Yes | Next in queue, each runs ≤ quantum | Large quantum ≈ FCFS; small = overhead |
| Multilevel feedback queue | Yes | Moves processes between priority queues | Tuning |
- Minimum average waiting time: SJF (non-preemptive), SRTF overall.
- Best response time: Round Robin.
Solved example with Gantt charts for all of them: CPU Scheduling Algorithms.
6. Synchronization
- Race condition: result depends on timing of threads touching shared data.
- Critical section requirements: mutual exclusion, progress, bounded waiting.
| Tool | Idea |
|---|---|
| Mutex | Lock owned by one thread: lock() / unlock() |
| Binary semaphore | Value 0/1, wait (P) / signal (V) |
| Counting semaphore | Value N — N identical resources |
| Monitor | Only one thread inside; condition variables to wait |
| Spinlock | Busy-waits; OK for very short sections on multicore |
wait(S): while (S <= 0) ; S-- // P, down
signal(S): S++ // V, up
Classic problems: producer–consumer (empty, full, mutex), readers–writers, dining philosophers. Details: Process Synchronization.
7. Deadlocks
Four necessary conditions (all must hold): mutual exclusion, hold and wait, no preemption, circular wait.
| Strategy | How |
|---|---|
| Prevention | Break a condition — e.g. order resources and always request in increasing order |
| Avoidance | Banker's algorithm: grant only if the state stays safe |
| Detection & recovery | Find cycles (wait-for graph), kill or roll back a process |
| Ignore | Ostrich approach — most desktop OSes |
Banker's: Need = Max − Allocation
Safe sequence: repeatedly pick a process with Need ≤ Available,
then Available += its Allocation
Resource-allocation graph: no cycle → no deadlock; cycle with single-instance resources → deadlock. Details with a solved example: Deadlocks.
8. Memory Management
| Term | Meaning |
|---|---|
| Logical address | Generated by the CPU / program |
| Physical address | Real RAM address; MMU translates |
| Internal fragmentation | Waste inside an allocated block |
| External fragmentation | Free memory split into unusable holes |
| First / best / worst fit | Which hole to allocate in contiguous allocation |
Paging: pages (logical) ↔ frames (physical), same size; no external fragmentation.
Logical address = page number p + offset d (page size 2^n → low n bits = offset)
Physical address = frame × page size + offset
EAT with TLB = h × (TLB + mem) + (1 − h) × (TLB + 2 × mem)
Segmentation: variable-size logical segments (code, stack, heap) with base + limit. Details: Memory Management, Paging and Virtual Memory.
9. Virtual Memory and Page Replacement
- Demand paging: load a page only when first used; a missing page causes a page fault.
- Thrashing: too few frames → constant page faults → CPU does little work.
- Copy-on-write: after
fork(), pages are shared until written.
| Algorithm | Replaces | Note |
|---|---|---|
| FIFO | Oldest loaded page | Belady's anomaly possible |
| LRU | Least recently used | Good in practice; costly to track exactly |
| Optimal | Page used farthest in the future | Theoretical best (benchmark) |
| LFU | Least frequently used | Old popular pages stick |
| Clock (second chance) | FIFO with a reference bit | LRU approximation used in real OSes |
Details: Page Replacement Algorithms.
10. File Systems
| Allocation | Pros | Cons |
|---|---|---|
| Contiguous | Fast sequential and random access | External fragmentation, hard to grow |
| Linked | No fragmentation, easy to grow | Slow random access, pointer overhead |
| Indexed | Fast random access | Index block overhead |
- Inode (Unix): metadata + block pointers (direct, single/double/triple indirect); the file name lives in the directory entry.
- Hard link: another name for the same inode. Soft (symbolic) link: a file containing a path.
- Journaling file systems (ext4, NTFS) log changes to recover after crashes.
11. Disk Scheduling
| Algorithm | Idea |
|---|---|
| FCFS | In request order |
| SSTF | Nearest request next (starvation possible) |
| SCAN (elevator) | Sweep to one end, then reverse |
| C-SCAN | Sweep one way, jump back to the start |
| LOOK / C-LOOK | Like SCAN/C-SCAN but turn at the last request |
Total head movement = sum of |differences| between consecutive positions. Details: File Systems and Disk Scheduling.
12. Linux Commands for OS Concepts
ps aux # processes
top / htop # live CPU and memory
kill -9 <pid> # force-stop a process
nice -n 10 cmd # start with lower priority
free -h # memory and swap
vmstat 1 # paging, CPU, I/O every second
lsof -p <pid> # open files of a process
df -h; du -sh dir # disk usage
More in the Linux docs.
13. Comparisons Interviewers Ask
| Question | Short answer |
|---|---|
| Process vs program | Program = file on disk; process = program in execution |
| Mutex vs semaphore | Mutex = owned lock; semaphore = counter, not owned |
| Paging vs segmentation | Fixed invisible pages vs variable logical segments |
| Deadlock vs starvation | Everyone waits forever vs one never gets a turn |
| Preemptive vs non-preemptive | OS can take the CPU away vs runs until it blocks/ends |
| Concurrency vs parallelism | Interleaving tasks vs running at the same instant |
| Hard vs soft real-time | Missing a deadline is failure vs degraded quality |
14. Cheat Sheet & References
Formulas
TAT = CT − AT WT = TAT − BT
Need = Max − Allocation
Physical = frame × page_size + offset
EAT = h(TLB + m) + (1 − h)(TLB + 2m)
Pages = 2^(logical bits) / page_size
Algorithms at a glance
Scheduling: FCFS · SJF · SRTF · Priority (+aging) · RR · MLFQ
Page replacement: FIFO · LRU · Optimal · LFU · Clock
Disk: FCFS · SSTF · SCAN · C-SCAN · LOOK · C-LOOK
Deadlock: prevent · avoid (Banker's) · detect & recover · ignore
Remember
fork(): 0 in child, child PID in parent; n forks → 2^n processes
Deadlock needs ALL FOUR: mutual exclusion, hold & wait, no preemption, circular wait
FIFO can show Belady's anomaly; LRU and Optimal cannot
Threads share code/data/heap; each has its own stack + registers