Formula Vault · OS

Operating Systems

Module 2

CPU Scheduling Algorithms

8 formulas

Core concepts

Preemptive: process can be interrupted mid-burst (SRTF, Round Robin, preemptive Priority). Non-preemptive: process holds the CPU until it terminates or blocks on I/O (FCFS, SJF, non-preemptive Priority)
For non-preemptive algorithms, Waiting Time always equals Response Time -- there's only ever one allocation to wait for
SJF minimizes average waiting time only among non-preemptive algorithms; its preemptive version SRTF can beat it
FCFS, Round Robin, and HRRN are starvation-free by design; SJF, SRTF, and Priority scheduling can starve a process indefinitely

Key formulas

Turnaround Time ☆

\[ TAT = CT - AT \]

Completion − Arrival

Waiting Time ☆

\[ WT = TAT - BT \]

Turnaround − Burst

Response Time ☆

\[ RT = \text{First Run} - AT \]

First allocation − Arrival

CPU Utilization ☆

\[ \eta = \frac{\sum BT}{\text{Total Schedule Time}} \times 100\% \]

Throughput ☆

\[ \frac{\text{Processes Completed}}{\text{Total Time Elapsed}} \]

Round Robin Limits ☆

\[ Q \to \infty \Rightarrow \text{FCFS} \qquad Q \to 0 \Rightarrow \text{Processor Sharing} \]

SJF Burst Prediction ☆

\[ \tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n \]

exponential average

HRRN Response Ratio ☆

\[ R = \frac{WT + BT}{BT} = 1 + \frac{WT}{BT} \]

Test your recall

Can you recall the turnaround time formula?

Reveal formula

\[ TAT = CT - AT \]

GATE traps 5 traps

Convoy effect is an FCFS problem

Convoy effect (short processes stuck behind one long CPU-bound process) is specific to FCFS.

SJF is optimal only among non-preemptive

SJF is optimal for average waiting time only among NON-preemptive algorithms -- SRTF, its preemptive version, can beat it. Don't call SJF unconditionally optimal.

HRRN and Round Robin never starve

Starvation is possible under SJF, SRTF, and Priority scheduling; FCFS, Round Robin, and HRRN are starvation-free by design (HRRN's ratio grows with waiting time, eventually forcing even long jobs to the front).

Round Robin tie-breaking

If a process's quantum expires at the exact instant a new process arrives, the standard GATE convention enqueues the NEW arrival first, then the just-preempted process -- getting this tie-break backwards is where most Round Robin waiting-time numericals go wrong.

Count the gaps, not the slices

Counting context switches: with N execution slices run back-to-back, there are only N-1 switches between them -- never add one after the very last process finishes. E.g. 3 processes needing 2+3+4=9 total quantum slices produce 8 context switches, not 9.

Module 3

Process Synchronization

3 formulas

Core concepts

Critical section requirements: Mutual Exclusion (mandatory), Progress (mandatory), Bounded Waiting (desirable)
wait(S)/P(S): S=S-1; if S<0, the process blocks. signal(S)/V(S): S=S+1; if S<=0, wake one blocked process
Binary semaphore: S in {0,1}; signal() called when S=1 leaves S=1. Counting semaphore: S is any integer, tracks a general resource count
Peterson's algorithm (2 processes, i and j): flag[i]=true; turn=j; while(flag[j] && turn==j); /* critical section */ flag[i]=false;
Producer-Consumer (bounded buffer, size N): semaphores mutex=1, empty=N, full=0. Producer: wait(empty); wait(mutex); ...; signal(mutex); signal(full)
Readers-Writers with reader priority can starve writers -- fixed with a turnstile/fair-queue variant. Dining Philosophers deadlocks if every philosopher grabs their left fork at once -- fixed by breaking symmetry (e.g. odd philosophers pick left-then-right, even pick right-then-left)

Key formulas

wait() / signal() ☆

\[ \text{wait}(S): S = S-1,\ \text{block if } S<0 \qquad \text{signal}(S): S = S+1,\ \text{wake one if } S\leq 0 \]

Final Semaphore Value ☆

\[ S_{final} = S_{init} - \#\text{wait} + \#\text{signal} \]

Unsynchronized Counter Bound ☆

\[ 2 \leq \text{count}_{final} \leq 2N \]

2 processes, N increments each, no lock

Test your recall

Can you recall the wait() / signal() formula?

Reveal formula

\[ \text{wait}(S): S = S-1,\ \text{block if } S<0 \qquad \text{signal}(S): S = S+1,\ \text{wake one if } S\leq 0 \]

GATE traps 5 traps

TSR fails bounded waiting, alternation fails progress

TestAndSet/Swap satisfy Mutual Exclusion and Progress but FAIL Bounded Waiting -- a process can be starved indefinitely even though the system as a whole always makes progress. Strict Alternation (a single turn variable) is the mirror image: it satisfies Bounded Waiting but FAILS Progress, since one process can be blocked by another that's idle in its remainder section.

Wait on the counting semaphore first

Deadlock via wait-order: if a Producer calls wait(mutex) BEFORE wait(empty), a full buffer leaves it holding mutex while blocked on empty -- the Consumer can never acquire mutex to free a slot, and the system deadlocks. Golden rule: always wait() on the counting semaphore before wait(mutex).

Peterson's line order isn't arbitrary

In Peterson's algorithm, flag[i]=true; turn=j; is not an arbitrary order -- swapping it to turn=j; flag[i]=true; opens a race window where both processes can read turn as favouring the other one at the moment they check, and neither one waits, violating Mutual Exclusion.

An unsynchronized count++ settles between 2 and 2N

A shared count++ (a non-atomic read-modify-write) executed N times each by 2 unsynchronized processes settles between 2 and 2N: 2N if every update lands cleanly, and a floor of 2 -- not lower -- because once a second write has landed anywhere, every later read is guaranteed to see a value of at least 1.

Deadlock ≠ starvation

Deadlock and starvation are different: deadlock is permanent mutual blocking; starvation is a process being repeatedly denied a resource that IS available -- reader-priority Readers-Writers can starve a writer without the system ever deadlocking.

Module 4

Deadlocks

6 formulas

Core concepts

4 Coffman conditions -- deadlock needs ALL simultaneously: Mutual Exclusion, Hold & Wait, No Preemption, Circular Wait
A Resource Allocation Graph is deadlock-free if and only if it can be completely reduced by processes requesting only currently-available resources
Safety algorithm: find a process i with Finish[i]=false and Need[i]<=Available; if found, Available += Allocation[i], Finish[i]=true, repeat; if no such i exists while unfinished processes remain, the state is UNSAFE
Resource-request grant test: grant immediately only if Request<=Need AND Request<=Available AND the resulting state still has a safe sequence

Key formulas

Resource Allocation Graph Rule ☆

\[ \text{Single-instance: cycle} \Leftrightarrow \text{deadlock} \]

multi-instance: cycle ⇒ possible, not certain

Need Matrix ☆

\[ \text{Need}[i] = \text{Max}[i] - \text{Allocation}[i] \]

Available Resources ☆

\[ \text{Available} = \text{Total} - \sum \text{Allocation} \]

Minimum Resources to Prevent Deadlock ☆

\[ R \geq \sum (\text{Max}_i - 1) + 1 \]

...for N Identical Processes ☆

\[ R \geq N \times (M-1) + 1 \]

N processes, each needing at most M

State Classification ☆

\[ \text{Deadlocked} \subset \text{Unsafe} \subset \text{All States} \]

Test your recall

Can you recall the resource allocation graph rule formula?

Reveal formula

\[ \text{Single-instance: cycle} \Leftrightarrow \text{deadlock} \]

GATE traps 4 traps

Unsafe ≠ deadlocked

An unsafe state is NOT the same as a deadlocked state -- it only means deadlock can no longer be GUARANTEED to be avoided from there. Every deadlocked state is unsafe, but plenty of unsafe states run to completion without ever deadlocking: deadlocked states are a subset of unsafe states, which are a subset of all possible states.

Prevention invalidates one Coffman condition

Deadlock prevention works by permanently invalidating one Coffman condition: Hold-and-Wait is invalidated by forcing a process to request all its resources upfront, before it runs; Circular Wait is invalidated by imposing a strict total ordering on resource types and requiring every request to follow strictly increasing order.

The +1 breaks the worst-case standoff

'Minimum resources to guarantee no deadlock' assumes the worst case -- every process holds exactly one unit less than its declared maximum, simultaneously. That worst-case standoff totals sum(Max_i - 1) units; one more unit than that breaks it, hence the '+1'.

A safe sequence need not be unique

Multiple processes can satisfy the safety algorithm's Need<=Available test at the same step -- any one of them can run next, so a system can have more than one valid safe sequence. The algorithm only needs to find ONE, not enumerate all of them.

Module 5

Memory Management & Paging

7 formulas

Core concepts

Logical Address = Page number (p) + Page offset (d); Physical Address = Frame number (f) + the same offset (d)
Paging causes internal fragmentation only (average loss = page size / 2 on the last page). Segmentation and plain contiguous allocation cause external fragmentation, which paging eliminates
Multi-level paging exists so a page table never needs one large contiguous allocation -- the page table's own pages get paged out just like any other data
where h = TLB hit ratio, t_TLB = TLB access time, t_mem = one main-memory access

Key formulas

Page Size = Frame Size ☆

\[ 2^{d} \]

Logical/Physical Address Space ☆

\[ \text{LAS} = 2^{\text{LA bits}} \qquad \text{PAS} = 2^{\text{PA bits}} \]

Number of Pages/Frames ☆

\[ \frac{\text{LAS}}{\text{Page Size}} \qquad \frac{\text{PAS}}{\text{Frame Size}} \]

Page Table Size ☆

\[ \text{Number of Pages} \times \text{PTE Size} \]

Entries per Page-Table Page ☆

\[ \frac{\text{Page Size}}{\text{PTE Size}} = 2^{e} \]

Effective Access Time ☆

\[ EAT = h(t_{TLB}+t_{mem}) + (1-h)(t_{TLB}+2t_{mem}) \]

EAT, k-Level Paging ☆

\[ EAT_{k\text{-level}} = h(t_{TLB}+t_{mem}) + (1-h)\big[t_{TLB}+(k+1)t_{mem}\big] \]

Test your recall

Can you recall the effective access time formula?

Reveal formula

\[ EAT = h(t_{TLB}+t_{mem}) + (1-h)(t_{TLB}+2t_{mem}) \]

GATE traps 4 traps

Multi-level paging caps entries per level

Multi-level paging exists so a page table never needs a large contiguous allocation of its own -- the page table's own pages get paged out just like any other data, which is exactly why each level's entry count is capped at page-size / PTE-size (one page-table page must itself fit in one frame).

A TLB miss costs (k+1) memory accesses

On a TLB miss with k-level paging, effective access time pays for k page-table walks PLUS the final data access -- that's (k+1) memory accesses on top of the TLB lookup, not k. Miscounting this off-by-one is the most common EAT numerical mistake.

Inverted page tables scale with physical frames

An Inverted Page Table has exactly one entry per PHYSICAL FRAME, not per virtual page -- its size is Physical Address Space / Frame Size, completely independent of how large the logical address space is. This is the opposite of a normal (forward) page table, which scales with virtual pages.

Carve out the offset bits first

When splitting a logical address across levels, carve out the offset bits FIRST (log2 of page size), then divide only the remaining page-number bits evenly across levels based on how many entries fit in one page-table frame -- forgetting to subtract the offset before splitting is a common setup error.

Module 6

Virtual Memory & File Systems

2 formulas

Core concepts

Demand paging loads a page only when referenced; accessing a page whose valid/invalid bit is invalid triggers a Page Fault trap to the OS
FIFO replaces the oldest-loaded page -- the classic algorithm that suffers Belady's Anomaly (more frames can mean MORE page faults); Second Chance, being FIFO-based, can show it too
Optimal/MIN replaces the page not needed for the longest time in the FUTURE (theoretical benchmark, not implementable). LRU replaces the page not referenced for the longest time in the PAST -- a stack algorithm, so it never exhibits Belady's Anomaly
Unix inode: direct block pointers -> data directly; single indirect -> one block of pointers; double indirect -> a block of pointer-blocks; triple indirect -> three levels of nesting
Disk scheduling: FCFS (simple, poor seek behaviour); SSTF (minimum seek from the current head position, starves distant requests); SCAN/Elevator (sweeps to the disk boundary, then reverses); C-SCAN (sweeps to the boundary, jumps back to the start -- uniform wait time); LOOK/C-LOOK (like SCAN/C-SCAN but reverses at the last actual request, not the physical boundary)
where p = page fault rate, PFST = page fault service time

Key formulas

Thrashing Condition ☆

\[ \sum \text{Working Sets} > \text{Total Physical Frames} \]

Effective Access Time (Paging) ☆

\[ EAT = (1-p)\,t_{mem} + p \times PFST \]

Test your recall

Can you recall the thrashing condition formula?

Reveal formula

\[ \sum \text{Working Sets} > \text{Total Physical Frames} \]

GATE traps 4 traps

First references are faults, not replacements

The first few references into a set of empty frames are page faults but NOT page replacements -- with 3 empty frames, the first 3 references cost 3 faults and 0 replacements, since nothing is evicted. Conflating fault count with replacement count is a common miscount.

SCAN uses the boundary, LOOK uses the request

SCAN measures its reversal leg against the physical track boundary (track 0 or the last track) even if no request lives there; LOOK measures against the FARTHEST ACTUAL REQUEST in that direction and reverses immediately after servicing it -- using the wrong reference point is the most common head-movement arithmetic error.

SSTF trades fairness for speed

SSTF greedily picks the nearest request every time, which minimizes total seek distance on average but can starve a request sitting far from the head if closer requests keep arriving -- fairness and efficiency trade off directly here.

Double-indirect blocks multiply, not add

A double-indirect block multiplies, not adds: with P pointers per block, double indirect alone reaches P^2 data blocks, dwarfing the direct and single-indirect contributions -- for typical block/pointer sizes it's what pushes maximum file size into the tens of megabytes and beyond.