Quick reference

Formulas, tables and algorithms from all nine chapters on one searchable page — for revision before the midterm and final.

OS goals and definitions

Execute user programs and make solving problems easier; convenient to use; efficient use of hardware.
Kernel: the one program running at all times. System programs ship with the OS; application programs do not.
OS is interrupt driven: hardware interrupts, software interrupts (traps/exceptions: errors, system calls).

Dual mode and timer

Mode bit: 1 = user, 0 = kernel. A system call traps to kernel mode; return resets to user mode.
Privileged instructions run only in kernel mode (set timer, I/O, disable interrupts, load base/limit).
Timer: OS sets a counter; at zero an interrupt returns control to the OS.

Storage hierarchy

Level	Access time	Managed by
registers	0.25–0.5 ns	compiler
cache	0.5–25 ns	hardware
main memory	80–250 ns	OS
SSD	25–50 µs	OS
magnetic disk	5 ms	OS

Types of system calls

Type	Unix examples
Process control	fork(), exit(), wait()
File management	open(), read(), write(), close()
Device management	ioctl(), read(), write()
Information maintenance	getpid(), alarm(), sleep()
Communications	pipe(), shm_open(), mmap()
Protection	chmod(), umask(), chown()

OS structures

Structure	Example	Key idea
Monolithic	original UNIX, Linux	everything below the system-call interface in one kernel
Layered	—	layer i uses only layers below; 0 = hardware, N = UI
Microkernel	Mach (Darwin)	minimal kernel, services in user space, message passing
Modules	Linux, Solaris	loadable kernel modules
Hybrid	Windows, macOS, iOS, Android	mix of the above

Process states and PCB

new → (admitted) ready → (dispatch) running → (interrupt) ready · running → (I/O or event wait) waiting → (completion) ready · running → (exit) terminated

PCB: state, program counter, registers, scheduling info, memory-management info, accounting info, I/O status.

fork, exec, wait

pid = fork(): returns 0 in the child, the child’s pid in the parent, < 0 on error.
n successive fork() calls → 2ⁿ processes.
exec() replaces the program in the same process (same pid); returns only on failure.
wait(): parent waits for a child. No wait → zombie; parent dies first → orphan.

IPC

Shared memory or message passing (send/receive).
Direct: send(P, m), receive(Q, m). Indirect: mailboxes, send(A, m).
Blocking = synchronous; both blocking = rendezvous.
Buffering: zero capacity (sender waits), bounded (waits if full), unbounded (never waits).

Contiguous allocation

Legal address a: base ≤ a < base + limit, otherwise trap.
First-fit: first hole big enough. Best-fit: smallest big enough. Worst-fit: largest.
External fragmentation: enough total space but not contiguous. 50-percent rule: N blocks allocated → 0.5 N lost.

Paging formulas

p = ⌊address ÷ page size⌋ d = address mod page size
physical = frame[p] × page size + d
logical space 2^m, page 2ⁿ → p has m − n bits, d has n bits
internal fragmentation = page size − (process size mod page size)

32-bit, 4 KB pages: 2²⁰ entries × 4 B = 4 MB per page table. Two-level split: p1 10 | p2 10 | d 12.

TLB and effective access time

EAT = h × m + (1 − h) × 2m

h = hit ratio, m = memory access time. 80% and 10 ns → 12 ns; 99% → 10.1 ns.

Swapping

swap time = size ÷ transfer rate; context switch with swapping = swap out + swap in

100 MB at 50 MB/s → 2000 ms each way, 4000 ms total.

Page replacement

Algorithm	Victim	3 frames, class string
FIFO	oldest page	15 faults
Optimal	not used for longest time	9
LRU	least recently used	12
Second chance	FIFO, but skip (and clear) pages with ref bit 1
LFU / MFU	smallest / largest reference count

Class string: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1. Belady’s anomaly (FIFO): 1,2,3,4,1,2,5,1,2,3,4,5 gives 9 faults with 3 frames, 10 with 4. Enhanced second chance classes, best first: (0,0), (0,1), (1,0), (1,1).

Threads and Amdahl’s law

speedup ≤ 1 / (S + (1 − S) / N), limit 1 / S

Models: many-to-one (one blocks → all block), one-to-one (Windows, Linux), many-to-many, two-level (bound threads). 75% parallel on 2 cores → 1.6.

Scheduling formulas

turnaround = completion − arrival
waiting = turnaround − burst
response = first run − arrival
Little: n = λ × W

FCFS (convoy effect) · SJF optimal for average waiting · SRTF = preemptive SJF · RR: no process waits more than (n − 1)q · priority: smallest number first, aging cures starvation.

Critical section

Requirements: mutual exclusion, progress, bounded waiting.
Peterson: flag[i] = true; turn = j; while (flag[j] && turn == j); … flag[i] = false;
test_and_set returns the old value and sets true; compare_and_swap sets new only if *value == expected.
Semaphore: wait(S) { while (S <= 0); S--; } signal(S) { S++; }. Binary semaphore = mutex lock.

Deadlock conditions and handling

Mutual exclusion, hold and wait, no preemption, circular wait — all four at once.
RAG: no cycle → no deadlock; cycle → deadlock if single instances, possible otherwise.
Handle by prevention, avoidance (safe state, Banker’s), detection + recovery, or ignoring.

Banker’s algorithm

Need = Max − Allocation

Work = Available; Finish[i] = false.
Find i with Finish[i] = false and Need_i ≤ Work.
Work += Allocation_i; Finish[i] = true; repeat.
All Finish true → safe.

Request: Request ≤ Need (else error), Request ≤ Available (else wait), pretend to allocate, grant only if the new state is safe. Detection uses Request instead of Need and starts processes with no allocation as finished.