Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

References