Formula sheet
Every formula from every topic. Type to filter.
🧵 Processes, Threads & System Calls
Processes after n sequential forks
2ⁿ in total, 2ⁿ − 1 new children
Fork in a loop (for i in 1..n)
2ⁿ processes (every process, including children, keeps looping)
fork() return value
0 in the child, child pid in the parent, −1 on failure
Context-switch overhead
efficiency = quantum / (quantum + switch time)
⏱️ CPU Scheduling
Turnaround time
TAT = CT − AT
Waiting time
WT = TAT − BT
Response time
RT = (first time on CPU) − AT
CPU utilisation
useful time / total time, where total includes context-switch time
Round robin first wait
at most (n − 1) × q for n processes that all arrived
Rate-monotonic bound
U = Σ Cᵢ/Tᵢ ≤ n (2^(1/n) − 1) (sufficient test); EDF: U ≤ 1
Exponential averaging
τ(n+1) = α·t(n) + (1 − α)·τ(n)
🔒 Synchronization & Concurrency
Critical-section requirements
mutual exclusion + progress + bounded waiting
Binary semaphore
init 1; P(S) before the critical section, V(S) after
Bounded buffer
empty = n, full = 0, mutex = 1
Counting semaphore value
initial value − (P completed) + (V completed) ≥ 0; if negative in the textbook form, |value| = number of blocked processes
Peterson entry
flag[i] = true; turn = j; while (flag[j] && turn == j);
🚧 Deadlock
Coffman conditions
mutual exclusion, hold and wait, no preemption, circular wait
Need matrix
Need = Max − Allocation
Safety test
find Pᵢ with Needᵢ ≤ Work; Work += Allocationᵢ; repeat until all finish or none fits
Deadlock-free with n processes needing ≤ m each
R ≥ n(m − 1) + 1
Different needs mᵢ
R ≥ Σ (mᵢ − 1) + 1 = Σ mᵢ − n + 1
Max processes for given R, each needing m
n ≤ (R − 1) / (m − 1)
🧱 Memory Management
Address split
virtual address bits = page number bits + offset bits; offset bits = log₂(page size)
Number of pages / frames
virtual size ÷ page size; physical size ÷ page size
Page table size
(number of pages) × (entry size)
Entries per page (multilevel)
page size ÷ entry size, so a level uses log₂(that) bits
Inverted page table size
(number of frames) × (entry size)
EMAT, 1-level paging with TLB
h(t + m) + (1 − h)(t + 2m)
EMAT, k-level paging with TLB
h(t + m) + (1 − h)(t + (k + 1)m)
Average internal fragmentation
≈ page size / 2 per process
💾 Virtual Memory
Effective access time
EAT = (1 − p)·m + p·(page-fault service time)
Fault service with dirty victims
s = read + (fraction dirty) × write + overhead
Belady's string
1 2 3 4 1 2 5 1 2 3 4 5: FIFO has 9 faults with 3 frames, 10 with 4
Hit ratio
hits / references = 1 − faults / references
Working-set demand
D = Σ WSSᵢ; thrashing if D > number of frames
Page faults lower bound
at least the number of distinct pages referenced (compulsory misses)
🗂️ File Systems
Pointers per block
B / P (block size ÷ pointer size)
Maximum file size (inode)
(d + B/P + (B/P)² + (B/P)³) × B with d direct pointers
FAT size
(number of blocks on the disk) × (entry size)
Bit-map size
number of blocks bits = blocks / 8 bytes
Blocks for a file of S bytes
⌈S / B⌉
Entry bits needed
at least ⌈log₂(number of blocks)⌉ bits per pointer
💿 Disk Scheduling & I/O
Disk access time
T = seek + rotational latency + transfer
Average rotational latency
½ × (60 / RPM) seconds = 30 / RPM s
Transfer time
bytes ÷ transfer rate, or (bytes / track size) × rotation time
Total head movement
Σ |cᵢ − cᵢ₋₁| over the service order
RAID capacity (n disks)
RAID 0: n; RAID 1: n/2; RAID 5: n − 1
DMA cycle stealing
fraction of time = DMA transfer time ÷ total time