⚡ Cheatsheet: Operating Systems

Scheduling Formulas

• Turnaround Time (TAT): \(Completion Time - Arrival Time\).
• Waiting Time (WT): \(TAT - Burst Time\).
• Convoy Effect: Short process stuck behind long process (FCFS).
• Starvation: Low priority process never executes (SJF/Priority). Aging prevents this.

Deadlocks

• Conditions: Mutual Exclusion, Hold & Wait, No Preemption, Circular Wait. (All 4 must hold).
• Banker's Algorithm:
• Need = Max - Allocation.
• Safety Check: Find process where Need <= Available. Add its Allocation to Available. Repeat.

Memory Management

• Logical Address: generated by CPU. Physical Address: actual RAM location.
• Paging:
• \(PA = f \times PageSize + d\) (where \(f\) is frame number).
• Page Table Size = \(NumPages \times PTE\_Size\).
• Multi-level Paging: Outer Page Table fits in 1 frame.
• TLB: \(EMAT = (H \times T_{tlb}) + (1-H) \times (T_{tlb} + 2 \times T_{mem})\).
• Segmentation: \(<Segment No, Offset>\). Bounds checking: \(Offset < Limit\).

Disk Scheduling

• SSTF: Shortest Seek Time First. High throughput, possible starvation.
• SCAN: Elevator algo. Go to end, reverse.
• C-SCAN: Circular SCAN. Go to end, jump to start, go to end.

⚠️ Common Traps

• Fork: fork() returns 0 to child, child PID to parent. Total processes = \(2^n\).
• Semaphore: Binary Semaphore vs Mutex. Mutex has ownership (only owner can unlock). Semaphore contributes to deadlock if wait order is circular.
• Belady's Anomaly: In FIFO page replacement, increasing frames can INCREASE page faults.
• Thrashing: CPU utilization drops because system spends all time paging. Solution: Decresae Multiprogramming Degree.