MATHEMATICAL VAULT · GATE CS/IT
Operating Systems Formula Vault
Comprehensive mathematical compilation: exact formulas, variable definitions, boundary constraints, and practical calculation shortcuts.
Memory Management & Paging
Effective Memory Access Time (EMAT) with TLB
EMAT = h · (t_tlb + t_m) + (1 - h) · (t_tlb + (k + 1) · t_m)- •h = TLB Hit Ratio (between 0.0 and 1.0)
- •t_tlb = TLB lookup / search time (e.g. 10–20 ns)
- •t_m = Main memory (RAM) access time (e.g. 100 ns)
- •k = Number of page table levels (k=1 for single-level, k=2 for two-level, etc.)
Exam Application: On a TLB hit, the CPU accesses TLB then RAM once: (t_tlb + t_m). On a TLB miss, the CPU accesses TLB, traverses all k levels of page tables in RAM, and then accesses the actual data in RAM: (t_tlb + (k + 1) · t_m).
Parallel TLB Lookup Variant
EMAT = h · (t_m) + (1 - h) · (t_tlb + (k + 1) · t_m)- •Used when the problem states TLB and Cache/RAM are looked up simultaneously.
Exam Application: Carefully check if the exam question states sequential search or parallel lookup.
Page Table & Address Translation Invariants
Number of Pages = 2^(Logical Address Bits - Offset Bits) = LAS / Page Size- •LAS = Logical Address Space
- •Offset bits d = log2(Page Size in bytes)
- •Frame bits f = log2(PAS / Page Size) where PAS = Physical Address Space
- •Page Table Size = Number of Pages · Page Table Entry (PTE) size
Exam Application: Page size and Frame size are always strictly identical.
Deadlocks & Resource Allocation
Deadlock-Free Resource Condition (Pigeonhole Invariant)
M ≥ N · (K - 1) + 1- •M = Minimum total instances of the resource required to guarantee NO deadlock
- •N = Total number of active concurrent processes
- •K = Maximum resource demand of each process (each process requires at most K units)
Exam Application: Worst-case deadlock allocation happens when all N processes hold K-1 instances and wait for the last unit (total allocated = N · (K - 1)). Adding 1 more unit ensures at least one process can finish.
Heterogeneous Demands Deadlock Bound
M ≥ ∑ (Max_Demand(P_i) - 1) + 1- •Used when processes have differing maximum resource demands K1, K2, ..., Kn.
Exam Application: Sum the (Max - 1) for every individual process, then add 1.
Banker's Algorithm Need Matrix
Need[i][j] = Max[i][j] - Allocation[i][j]- •Work Vector initially = Available Vector
- •Process P_i is safe if: Need[i] ≤ Work
- •New Work = Work + Allocation[i]
Exam Application: Once P_i finishes, it releases ALL its currently allocated resources back to Work.
CPU Scheduling Metrics
Turnaround Time (TAT)
TAT = CT - AT- •CT = Completion Time (exact moment process finishes all execution)
- •AT = Arrival Time (exact moment process enters the Ready queue)
Exam Application: Always find CT from the completed Gantt chart first, then subtract AT.
Waiting Time (WT)
WT = TAT - BT- •BT = CPU Burst Time (total execution time required by the process)
- •TAT = Turnaround Time
Exam Application: Waiting time is the total idle time spent in the Ready queue waiting for CPU.
Highest Response Ratio Next (HRRN)
Response Ratio = (W + S) / S = 1 + (W / S)- •W = Waiting time spent in ready queue so far
- •S = Expected CPU service / burst time
Exam Application: Prevents starvation of long processes while still favoring shorter jobs.
Process Synchronization & Semaphores
Semaphore Value Balance Equation
Final S = Initial S - (Number of P operations) + (Number of V operations)- •P(S) or wait(S): decrements S by 1
- •V(S) or signal(S): increments S by 1
- •If Final S < 0, exactly |Final S| processes are currently blocked in the queue
- •If Final S ≥ 0, exactly 0 processes are blocked in the queue
Exam Application: Tested every year in GATE to verify blocked process counts.
Storage Systems & Disk Scheduling
Total Head Movement (Seek Distance)
Total Seek = ∑ |Cylinder_{current} - Cylinder_{next}|- •Evaluated sequentially across the servicing order determined by the algorithm (SSTF, SCAN, LOOK, C-SCAN, C-LOOK).
Exam Application: SCAN travels to the end boundary cylinder (0 or Max-1); LOOK only travels to the furthest request.
Unix Inode Maximum File Size Formula
Max File Size = (Direct + Indirect · P + DoubleIndirect · P² + TripleIndirect · P³) · BlockSize- •P = Number of disk block pointers per block = Block Size / Pointer Size
- •Direct = Number of direct block pointers (typically 12)
- •Indirect = Number of single indirect pointers (typically 1)
- •DoubleIndirect = Number of double indirect pointers (typically 1)
Exam Application: Ensure all units are converted consistently to Bytes before multiplying by Block Size.