Why Operating Systems is a Score Booster
In GATE CSE, Operating Systems (OS) consistently accounts for 8-10 marks. Unlike Computer Organization or Algorithms, which can feature extremely twisted logical problems, OS questions are generally straightforward applications of numerical concepts or clear theoretical definitions.
If you know the formulas and the mechanics of the algorithms, you will get the marks. The syllabus revolves around three massive pillars: Process Management, Synchronization, and Memory Management. Master these, and you have mastered OS.
Pillar 1: Process Management & CPU Scheduling
This section tests your ability to track processes as they move through the CPU.
Key CPU Scheduling Algorithms:
- FCFS (First Come First Serve): Simple, non-preemptive. Suffers from the Convoy Effect.
- SJF (Shortest Job First): Optimal for average waiting time, but impossible to implement perfectly (cannot predict future burst times). Can be preemptive (SRTF - Shortest Remaining Time First) or non-preemptive.
- Round Robin (RR): Preemptive, based on a Time Quantum (TQ). Excellent for time-sharing systems. Understand how changing the TQ affects context switch overhead vs response time.
- Priority Scheduling: Can lead to starvation. Solution is Aging (gradually increasing priority over time).
GATE Question Pattern: You will be given a table with Process IDs, Arrival Times, and Burst Times. You must draw a Gantt chart and calculate the Average Turn Around Time (TAT) or Average Waiting Time (WT). Formulas to memorize:
- Completion Time (CT) = Time when process finishes execution.
- Turn Around Time (TAT) = CT - Arrival Time (AT).
- Waiting Time (WT) = TAT - Burst Time (BT).
Pitfall: In preemptive algorithms (like SRTF), carefully check the ready queue at every single time unit an arrival occurs.
Pillar 2: Concurrency & Process Synchronization
This is the most conceptually challenging part of OS. It deals with multiple processes accessing shared resources simultaneously (Critical Section Problem).
The Critical Section Requirements:
- Mutual Exclusion (Mandatory): Only one process inside at a time.
- Progress (Mandatory): If no one is in the CS, someone who wants to enter must be allowed to.
- Bounded Waiting (Optional but desired): A process shouldn't wait forever to enter.
Semaphores: An integer variable accessed only through two atomic operations: 'wait()' (or P, down) and 'signal()' (or V, up).
- Binary Semaphore (Mutex): Value is 0 or 1. Used for mutual exclusion.
- Counting Semaphore: Value domain is unrestricted. Used for resource counting.
Classic Problems:
- Producer-Consumer Problem: Understand the buffer synchronization using semaphores (Empty, Full, Mutex).
- Dining Philosophers Problem: Illustrates deadlock conditions.
Deadlocks: A situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.
- 4 Necessary Conditions (Coffman Conditions): Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait. All four must hold simultaneously.
- Deadlock Avoidance (Banker’s Algorithm): The most tested numerical concept here. You will be given Allocation, Max Need, and Available matrices. You must calculate the Need matrix (Need = Max - Allocation) and determine if a Safe Sequence exists. If it exists, the system is safe from deadlock.
Pillar 3: Memory Management
Memory management questions in GATE are highly numerical and test your understanding of address translation.
Contiguous Memory Allocation:
- Algorithms: First Fit, Best Fit (creates smallest leftover holes, leads to external fragmentation), Worst Fit.
- Fragmentation:
- Internal: Allocated block is larger than requested memory.
- External: Total free memory exists to satisfy a request, but it is not contiguous.
Paging (The core of OS memory questions): Solves external fragmentation by dividing physical memory into fixed-size Frames and logical memory into same-size Pages.
Crucial formulas and concepts:
- Logical Address = Page Number (p) + Page Offset (d).
- Physical Address = Frame Number (f) + Page Offset (d).
- Page Size = Frame Size.
- Number of pages = Logical Address Space / Page Size.
- Page Table Size = Number of Entries × Page Table Entry (PTE) size.
GATE Question Type: "A system has a 32-bit logical address space and 4KB page size. Find the number of entries in the page table." Solution: 32 bits = 2³² bytes address space. 4KB = 2¹² bytes page size. Number of pages = 2³² / 2¹² = 2²⁰ entries.
Translation Lookaside Buffer (TLB): A hardware cache for the page table.
- Effective Access Time (EAT) = (Hit ratio × TLB access time) + (Miss ratio × (TLB access time + Memory access time for Page Table)) + Memory access time for actual data.
Virtual Memory & Page Replacement: Allows execution of processes that are not completely in memory.
- Page Fault: Occurs when a requested page is not in physical memory.
- Algorithms:
- FIFO: Belady's Anomaly (increasing frames can increase page faults).
- LRU (Least Recently Used): Excellent algorithm, uses past knowledge.
- Optimal: Uses future knowledge (replace the page that will not be used for the longest time). Yields minimum page faults; used as a benchmark.
Disk Scheduling
Often a standalone 2-mark question. Given a sequence of disk track requests and an initial head position, calculate the total head movement.
- FCFS: Serve in order.
- SSTF (Shortest Seek Time First): Move to the closest request. Can cause starvation.
- SCAN (Elevator): Move to one end, serving requests, then reverse direction.
- C-SCAN: Move to one end, serving requests, return to the beginning without serving, then sweep again.
Preparation Strategy for OS
- Visualize the structures: Draw diagrams for paging and Gantt charts for CPU scheduling. Do not try to solve these in your head.
- Master the numericals: Banker's Algorithm, Paging address translation, and TLB Effective Access Time represent easy, guaranteed marks if you know the formulas.
- Practice PYQs intensively: OS concepts like semaphores can be presented in confusing pseudocode. The only way to decode them quickly is by having seen the variations in previous GATE papers.