OS and Computer Architecture Cheat Sheet

(Measured values on the course machine are in Modules 11 and 18.)

Concept

Numbers Every Engineer Should Know (order of magnitude) Mutex lock/unlock (uncontended) Main memory access SSD random read Network round trip in a data center (Measured values on the course machine are in Modules 11 and 18.) CPU time = IC × CPI × clock period Speedup = 1 / ((1 − f) + f / s)

AMAT = hit time + miss rate × miss penalty Average memory access time

Sets = size / (ways × line size); offset = log₂(line), index = log₂(sets), tag = rest Cache address split

Turnaround = completion − arrival; waiting = turnaround − burst

Effective access time (paging) = TLB hit ratio × (TLB + mem) + miss ratio × (TLB + 2 × mem) One-level page table

Disk access = seek + rotational latency (½ revolution) + transfer U ≤ n(2^(1/n) − 1) Rate-Monotonic schedulability bound Process and Thread APIs (POSIX) fork, execvp, waitpid, _exit pthread_create, pthread_join

pthread_mutex_lock/unlock, pthread_cond_wait/signal Locks and condition variables sem_init, sem_wait, sem_post

pipe, mkfifo, socketpair, mmap(MAP_SHARED) sigaction, kill, raise, alarm

open, read, write, close, lseek, fsync, unlink, rename mmap, munmap, mprotect Linux Diagnostic Commands ps, top, htop strace, ltrace System and library calls vmstat, free, iostat, pidstat Memory, CPU and I/O activity lscpu, lsblk, lspci, lsusb

perf stat/record, gprof, /usr/bin/time -v objdump -d, readelf, nm, ldd nice, chrt, taskset

unshare, nsenter, /proc/self/ns, /sys/fs/cgroup x86-64 System V Calling Convention

Arguments rdi rsi rdx rcx r8 r9, return rax; callee-saved rbx rbp r12–r15; system calls: number in rax, arguments rdi rsi rdx r10 r8 r9, syscall.

Why It Matters

A compact reference for revision and daily work.

Example

Quick checks you can run on any Linux system:

getconf PAGESIZE
getconf LEVEL1_DCACHE_LINESIZE
nproc
cat /proc/sys/kernel/randomize_va_space

Expected Result

On the course machine: page size 4096, cache line 64, 8 logical CPUs, ASLR level 2 (the last three verified in Modules 8, 18 and 28).

Common Mistakes

Treating latency numbers as exact — they vary by generation and system; the ratios are what matter.

Mixing the system-call register order (r10) with the function-call order (rcx).

Best Practices

Re-measure key numbers on your own hardware (Modules 11, 18 provide the programs).

Keep your own annotated cheat sheet.

Interview Relevance

The numbers table and formulas are asked about directly ("how long does a memory access take compared to an L1 hit?").

Practice Questions

Compute the effective access time for a 90% TLB hit ratio, 1 ns TLB and 100 ns memory.

Compute AMAT for a two-level cache: L1 1 ns / 5% miss, L2 4 ns / 20% miss, memory 100 ns.

How many 64-byte lines fit in a 32 KB cache?

What is the RMS bound for 3 tasks?

Quick Quiz

Q1. (Multiple choice) Which is faster? A) An SSD read B) A main-memory access C) A context switch D) A network round trip Answer: B.

Q2. (Predict the output) Sets in a 32 KB, 8-way cache with 64-byte lines?

Answer: 64 (verified in Module 18's challenge).

Q3. (True/False) In the Linux system-call convention the fourth argument is in rcx.

Answer: False. It is r10 (syscall overwrites rcx with the return address).

Q4. (Find the bug) "A context switch costs about the same as a function call."

Answer: It is thousands of times more expensive: microseconds versus nanoseconds, plus cache and TLB effects.

Coding Challenge

Compute the effective memory access time with a TLB for hit ratios 80%, 90%, 98% and 99% (TLB 1 ns, memory 100 ns, one-level page table).

#include <stdio.h>

int main(void)
{
    double tlb = 1, mem = 100, ratios[] = {0.80, 0.90, 0.98, 0.99};
    for (int i = 0; i < 4; i++) {
        double h = ratios[i];
        double eat = h * (tlb + mem) + (1 - h) * (tlb + 2 * mem);
        printf("TLB hit ratio %.0f%%: effective access time %.1f ns\n", h * 100, eat);
    }
    return 0;
}