Operating System for GATE
Operating Systems consistently carries 8 to 12 marks in the GATE CS paper, making it one of the most heavily tested subjects. Historical analysis shows tha...
GATE Weightage and Topic Priority in Operating Systems
Operating Systems consistently carries 8 to 12 marks in the GATE CS paper, making it one of the most heavily tested subjects. Historical analysis shows that process synchronization and deadlock together account for roughly 35 percent of OS marks, memory management accounts for another 30 percent, CPU scheduling contributes about 20 percent, and file systems and I/O take the remaining 15 percent.
For GATE specifically, process synchronization means mastering semaphores, the producer-consumer problem, the readers-writers problem, and the dining philosophers problem. You must be able to trace semaphore values through a concurrent execution, identify race conditions, and determine whether a given solution is correct or prone to deadlock/starvation. These questions often appear as two-mark problems with execution traces.
Memory management questions for GATE focus on page replacement algorithms (FIFO, LRU, Optimal), page table structures, and memory allocation strategies (first-fit, best-fit, worst-fit). Thrashing — when the OS spends more time swapping pages than executing processes — and the working set model for preventing it are also tested. Virtual-to-physical address translation with multi-level page tables is a reliable source of GATE numericals.
CPU scheduling questions require you to compute Gantt charts and derive performance metrics. Always draw the Gantt chart first when solving scheduling problems under exam conditions — it prevents errors in tracking which process runs when. For preemptive algorithms, mark every point where a new process arrives or a time quantum expires as a potential scheduling event.
File system questions may ask about i-node structures, disk block allocation strategies (contiguous, linked, indexed), and the maximum file size supported by a given i-node configuration. If an i-node has 10 direct pointers, one single-indirect pointer, and one double-indirect pointer, and each block is 4 KB with 4-byte pointers (1024 pointers per block), maximum file size is (10 + 1024 + 1024 squared) times 4 KB — a classic GATE calculation.
Synchronization and Semaphores for GATE
Synchronization is required whenever concurrent processes share data, because non-atomic operations on shared variables can produce incorrect results depending on the interleaving of instructions. The critical section problem requires any correct solution to satisfy mutual exclusion, progress, and bounded waiting.
Mutual exclusion ensures that at most one process executes in the critical section at any time. Progress ensures that if no process is in the critical section and some processes wish to enter, one of them will be selected within finite time. Bounded waiting ensures that a process waiting to enter the critical section will eventually do so — no process starves.
Semaphores are integer variables supporting two atomic operations: wait (decrement and block if the result is negative) and signal (increment and unblock a waiting process if any). Binary semaphores (values 0 and 1) implement mutual exclusion. Counting semaphores (non-negative integers) track the count of available instances of a resource.
The producer-consumer problem uses three semaphores: mutex (binary, initial value 1) to protect shared buffer access, empty (counting, initial value N for buffer size N) to track empty slots, and full (counting, initial value 0) to track filled slots. The producer does wait(empty), wait(mutex), produce, signal(mutex), signal(full). The consumer does wait(full), wait(mutex), consume, signal(mutex), signal(empty). GATE traces execution of this solution with specific schedules and asks for final semaphore values or whether deadlock occurs.
A common deadlock trap: if a producer calls wait(mutex) before wait(empty), and the buffer is full (empty equals zero), the producer blocks holding the mutex. No consumer can enter its critical section to free a slot, causing deadlock. This is why the ordering wait(empty) before wait(mutex) is mandatory in the producer. GATE has tested this exact scenario.
Virtual Memory and Page Replacement for GATE
Virtual memory allows processes to use more address space than physical RAM by storing pages on disk and loading them on demand. A page fault occurs when the process accesses a page not currently in memory; the OS must locate it on disk, load it into a free frame, update the page table, and restart the faulting instruction.
The three most tested page replacement algorithms are FIFO, LRU, and Optimal. FIFO replaces the page that has been in memory the longest. LRU replaces the page that was least recently used. Optimal (also called OPT or Belady's Optimal) replaces the page that will not be used for the longest time in the future — it is provably optimal but requires future knowledge, making it a theoretical benchmark rather than a practical algorithm.
Belady's Anomaly is the counterintuitive phenomenon where increasing the number of frames can increase the number of page faults for FIFO. GATE has asked students to demonstrate this with a specific reference string and frame counts. LRU and Optimal do not exhibit Belady's Anomaly — stack algorithms cannot.
For computing page fault rates in GATE problems, simulate the algorithm step by step. For a reference string such as 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with three frames using LRU: track the three frames and the last-use time of each. When a page fault occurs on page 3 and frames contain pages 4, 1, 2 (with page 4 being least recently used), replace page 4. Careful simulation prevents the simple counting errors that cost marks.
Working set theory provides a dynamic frame allocation approach. The working set of a process at time t with window size delta is the set of distinct pages referenced in the interval (t minus delta, t). Allocating frames equal to working set size prevents thrashing. GATE occasionally tests the concept of thrashing and how the OS detects and responds to it using the working set or page-fault frequency approach.