OS cheat sheet

Numbers

Formulas

── SCHEDULING ───────────────────────────────────────────────────
Turnaround time  TAT = Completion − Arrival
Waiting time     WT  = TAT − Burst
Response time        = first_run − Arrival        # what users feel
Throughput           = jobs / total time
Response ratio       = (Wait + Burst) / Burst     # HRRN picks the max

── PAGING ───────────────────────────────────────────────────────
page size 2ⁿ         → offset = n bits
virtual address v bits → page number = (v − n) bits
entries per flat table = 2^(v−n)
flat table size        = 2^(v−n) × entry_size
physical address       = frame_number × page_size + offset
                         # the offset is NEVER translated

TLB reach            = TLB entries × page size
Effective access time (TLB)
  = hit_ratio × (TLB + mem) + (1−hit) × (TLB + levels×mem + mem)

── VIRTUAL MEMORY ───────────────────────────────────────────────
Effective access time = (1−p) × mem_access + p × fault_service_time
  100 ns memory, 8 ms fault, p = 0.001  →  ~8.1 µs  (81× slower)
  for <10% slowdown you need p < ~1.2 × 10⁻⁶

── DISK (spinning) ──────────────────────────────────────────────
access = seek + rotational latency + transfer
rotational latency (avg) = 0.5 / (rpm / 60)
  7200 rpm → 4.17 ms      15000 rpm → 2 ms

── RAID ─────────────────────────────────────────────────────────
RAID 0   usable = 100%       survives 0
RAID 1   usable = 50%        survives 1
RAID 5   usable = (n−1)/n    survives 1   write penalty = 4 I/Os
RAID 6   usable = (n−2)/n    survives 2   write penalty = 6 I/Os
RAID 10  usable = 50%        survives ≥1  no parity penalty

── CONCURRENCY ──────────────────────────────────────────────────
semaphore S:  wait(S)   S--; if (S<0) block
              signal(S) S++; if (S<=0) wake one
              S < 0 ⇒ |S| threads are waiting

Threads for CPU-bound work  ≈ cores
Threads for I/O-bound work  ≈ cores × (1 + wait/compute)

Scheduling algorithms at a glance

Page replacement

Synchronisation quick reference

── BOUNDED BUFFER (memorise this) ───────────────────────────────
semaphore empty = N, full = 0;  mutex m;

Producer                       Consumer
  wait(empty)                    wait(full)
  wait(m)                        wait(m)
  insert                         remove
  signal(m)                      signal(m)
  signal(full)                   signal(empty)

# Counting semaphore BEFORE the mutex, always. Reversed = deadlock.

── DEADLOCK: the four conditions ────────────────────────────────
mutual exclusion · hold and wait · no preemption · circular wait
ALL FOUR must hold. Break circular wait with global lock ordering —
it is the only one that is free at runtime.

── BANKER'S ─────────────────────────────────────────────────────
Need = Max − Allocation
repeat: find any process with Need ≤ Available
        → pretend it finishes, Available += its Allocation
all retired ⇒ SAFE (a completion order exists)
safe ≠ unsafe ≠ deadlocked   (unsafe = deadlock POSSIBLE, not certain)

The distinction table

Linux commands that prove you've used it

── CPU & scheduling ─────────────────────────────────────────────
$ top -H                 # per-THREAD view; find the hot thread
$ vmstat 1               # r=runnable b=blocked cs=switches wa=iowait
$ pidstat -t 1           # per-thread CPU over time
$ taskset -c 0-3 ./app   # pin to cores (cache affinity)
$ chrt -f 50 ./app       # run with SCHED_FIFO priority 50
$ nice -n 10 ./batch     # lower priority

── MEMORY ───────────────────────────────────────────────────────
$ free -h                # watch "available", not "free"
$ ps -eo pid,rss,vsz,maj_flt --sort=-rss | head
$ cat /proc/PID/smaps_rollup   # PSS — honest shared-page accounting
$ cat /proc/PID/status         # VmRSS, VmSwap, Threads
$ dmesg -T | grep -i "killed process"   # the OOM killer

── FILES & I/O ──────────────────────────────────────────────────
$ df -h                  # disk full?
$ du -sh *               # where did it go?
$ lsof +L1               # DELETED files still held open ← the classic
$ lsof -p PID            # what this process has open
$ ls /proc/PID/fd | wc -l      # fd count vs ulimit -n
$ iostat -x 1            # %util, await per device
$ stat file              # inode number, link count, timestamps

── PROCESSES & SYSCALLS ─────────────────────────────────────────
$ ps -eo pid,ppid,state,comm     # state D or Z is the interesting bit
$ strace -c -p PID       # WHICH syscalls, and how many
$ strace -f -e trace=openat ./app
$ ltrace ./app           # library calls instead
$ cat /proc/PID/stack    # where a D-state process is stuck
$ perf top               # sampling profiler, kernel + user

── CONTAINERS ───────────────────────────────────────────────────
$ cat /sys/fs/cgroup/memory.max        # the real limit
$ cat /sys/fs/cgroup/cpu.stat          # nr_throttled = CPU quota pain
$ lsns                                 # namespaces on the box
# exit code 137 = 128 + 9 = SIGKILL = usually the cgroup OOM killer

Decision trees

Concurrency model for a service

Is the work CPU-bound or I/O-bound?
├─ CPU-bound  → thread pool sized ≈ core count
│               (more threads add switches, not capacity)
└─ I/O-bound  → how much concurrency?
                ├─ hundreds      → thread pool, cores × (1 + wait/compute)
                ├─ thousands+    → event loop (epoll) or green threads
                └─ untrusted/crashy work → separate PROCESSES, accept the cost

Which synchronisation primitive

Can you avoid sharing entirely?
├─ YES → do that. Per-thread copies, immutable data, message passing.
└─ NO  → what are you protecting?
         ├─ a data structure        → mutex (document the lock ORDER)
         ├─ N interchangeable slots → counting semaphore
         ├─ "wait until X"          → condvar + mutex, in a while loop
         ├─ one counter/flag        → atomic
         └─ measured hot contention → consider lock-free, and prove it helps

Diagnosing a slow box

Check `vmstat 1` first. Then:
  wa high, b high      → I/O bound. iostat -x, find the device.
  si/so nonzero         → THRASHING. Reduce concurrency or add RAM.
  cs enormous           → too many runnable threads / lock convoy.
  r >> cores, us high   → genuine CPU saturation. Profile with perf.
  us low, sy high       → syscall storm. strace -c.
  nothing unusual       → it's not this box. Look at the dependency.

Storage choice

Random writes and you care about latency?  → RAID 10, SSD
Sequential, capacity-driven, archival?      → RAID 6, spinning disk
Need snapshots / checksums / bit-rot safety? → ZFS or Btrfs (CoW)
Need maximum database throughput?            → ext4/XFS on RAID 10, and
                                               remember: RAID is NOT a backup