OS · GATE CS 2027
9 topics and 21 sheets. Open a topic for its sheets and the topics it depends on.
How a program enters the kernel (dual mode, traps, system calls), what the OS keeps for each process (PCB, states, context switch), how fork() multiplies processes and what it prints, and how threads share an address space under the many-to-one, one-to-one and many-to-many models.
Scheduling criteria and the metrics read off a Gantt chart (completion, turnaround, waiting, response), then FCFS, SJF, SRTF, round robin, priority with aging, multilevel and feedback queues and HRRN, with tie and arrival conventions and context-switch overhead.
Inter-process communication by shared memory, message passing and pipes; race conditions and the three critical-section requirements; Peterson, bakery and hardware instructions; semaphores, mutexes and monitors; producer-consumer, readers-writers and dining philosophers.
The four necessary conditions, resource-allocation and wait-for graphs, prevention by breaking a condition, avoidance with the Banker's safety and request algorithms, detection with the Request matrix, recovery, and the minimum number of resources that rules deadlock out.
Contiguous allocation with relocation and limit registers, first, best, next and worst fit, internal and external fragmentation, segmentation tables, paging address splits, page-table sizes, multilevel, inverted and hashed page tables.
TLB lookups and effective access time, demand paging and page-fault service, FIFO, LRU, optimal and clock replacement traces, Belady's anomaly, frame allocation, thrashing and the working-set model.
Files, directories and links, contiguous, linked, FAT and indexed allocation, inode block pointers and maximum file size, disk reads per access, and free-space management with bitmaps, lists, grouping and counting.
Disk geometry, capacity and access time (seek, rotational latency, transfer), FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK head movement, the return-sweep convention, and how the CPU moves data with programmed I/O, interrupts and DMA.
The wrong turns that cost marks, the recognition cues and routines for each question pattern, and a last-day sheet of formulas, anchor numbers and checks.
Dual-mode operation with a hardware mode bit, privileged instructions and what happens when user code tries one; traps, exceptions and interrupts as the only ways into the kernel; the step-by-step path of a system call through the libc wrapper, the trap, the system-call table and return-from-trap; how parameters are passed; the classes of system calls with POSIX examples; library calls that may or may not reach the kernel; and the difference between a mode switch and a context switch.
Program versus process and the process memory layout; the process control block and its fields; the five-state model with its six transitions and the transitions that cannot happen; suspended states and the medium-term scheduler; long-, short- and medium-term schedulers; what a context switch saves and why it is pure overhead; CPU-bound versus I/O-bound processes; zombie and orphan processes, exec, wait and exit.
What fork() returns in the parent and the child, the 2 to the n rule and when it breaks, forks in loops, forks guarded by if, and forks inside && and || expressions, how many lines a loop of fork and printf prints, why a child sees its own copy of every variable, how stdio buffering can make text appear twice, what wait and exec change, and the solved GATE CS 2024 Set 1 Q.57. Every count was produced by a process-tree simulator.
What threads of one process share and what each thread owns; user-level versus kernel-level threads, who schedules them and what happens when one blocks; the many-to-one, one-to-one, many-to-many and two-level models; why thread creation and switching are cheaper than for processes; concurrency versus parallelism and Amdahl's law with computed speedups; the POSIX thread calls; and threading issues: fork in a threaded process, signals, cancellation and thread-safe code.
Scheduling criteria and when the scheduler runs; preemptive versus non-preemptive policies and the dispatcher; completion, turnaround, waiting and response time with their conditions; FCFS, SJF and SRTF timelines and averages on one worked example with a Gantt chart; idle gaps and utilisation; when SJF and SRTF are optimal; predicting the next burst by exponential averaging; and the solved GATE CS 2024 Set 2 Q.37 and 2025 Set 2 Q.26. Every timeline and average was produced by a scheduling simulator.
Round robin with a full ready-queue trace and the convention for arrivals at a slice boundary; how the quantum changes the result, up to FCFS; context-switch overhead placed on the timeline with its effect on efficiency; preemptive and non-preemptive priority, starvation and aging; multilevel and multilevel feedback queues with a traced example; highest response ratio next; a comparison of averages; and the solved GATE CS 2026 Set 1 Q.64. All values come from a scheduling simulator.
Why processes need IPC; shared memory versus message passing and their costs; direct and indirect (mailbox) naming; blocking and non-blocking send and receive; zero, bounded and unbounded buffering; anonymous pipes and their end-of-file and broken-pipe rules, named pipes (FIFOs), message queues, signals and sockets; a computed pipe-capacity example; and a single-slot producer-consumer handoff that shows why shared memory still needs synchronization.
Race conditions shown with the lost-update interleaving and the range of final values when two processes increment a shared counter; the three requirements for a critical-section solution; the classic two-process attempts and which requirement each breaks; Peterson's algorithm and its assumptions; the bakery algorithm for n processes; disabling interrupts; test-and-set, swap and compare-and-swap locks, the bounded-waiting version, spinlocks and memory ordering. All claims about the protocols were checked by exhaustive state search.
Semaphore wait and signal in the non-negative model and in the blocking model where the value can go negative; counting versus binary semaphores; value arithmetic after many operations; forcing an order of events with semaphores initialised to 0, with exhaustively enumerated outputs; mutex versus binary semaphore; monitors and condition variables with Hoare and Mesa signalling; and the solved GATE CS 2024 Set 2 Q.46 on a deadlock caused by waiting while holding a semaphore.
The bounded-buffer producer-consumer solution with its three semaphores and what happens when the producer or the consumer takes the mutex first; the first readers-writers solution with the read count, why readers share and writers are exclusive, and why writers can starve; the dining philosophers, the deadlock when all pick up the left chopstick, and four ways to prevent it. Deadlock and exclusion claims were checked by a full state-space search.
Deadlock defined and separated from starvation and livelock; the four necessary conditions; the resource-allocation graph and the wait-for graph, and why a cycle means deadlock only with single-instance resources, with a figure of a cycle that is not a deadlock; prevention by breaking each condition, including resource ordering; the four handling strategies; and the minimum number of resource units that makes deadlock impossible, checked by brute force, with the solved GATE CS 2026 Set 1 Q.35.
The Banker's data structures (Available, Max, Allocation, Need); the safety algorithm with a full worked run and the number of safe sequences; the resource-request algorithm with grant, deny, wait and error outcomes on the same example; safe versus unsafe versus deadlocked; the detection algorithm that uses current Request instead of Need, with a worked example that finds a deadlocked set; recovery by termination or preemption; and the cost of each algorithm.
Logical versus physical addresses, binding time and the MMU; relocation and limit registers with checked translations; fixed and variable partitions; first, best, next and worst fit on one worked hole list with every allocation computed; internal and external fragmentation, compaction and the fifty-percent rule; swapping; segmentation with a segment table, the offset-below-limit rule and worked translations; and segmentation compared with paging.
Pages, frames and the address split into page number and offset; page and frame counts; the page-table entry and its control bits with a computed entry size; single-level page-table size per process; multilevel paging with the levels formula, a two-level translation figure and the memory a sparse process really needs; inverted and hashed page tables; internal fragmentation and the page-size trade-off; and the solved GATE CS 2024 Set 1 Q.62. Every size was computed by script.
The translation path with a TLB, from hit to miss to page fault, in one figure; effective access time with a TLB for one or more page-table levels, with the TLB time counted or ignored; the hit ratio needed for a target; TLB reach and address-space identifiers; demand paging and the steps of page-fault service; effective access time with page faults, with dirty victims and combined with a TLB; copy-on-write; and equal versus proportional frame allocation. Every number was computed by script.
FIFO, LRU and optimal replacement traced side by side on one reference string; fault counts on the classic 20-reference string including clock and LFU; Belady's anomaly and the stack property; the clock (second chance) algorithm; implementing LRU; local versus global replacement; thrashing, the working-set model and page-fault frequency; and the solved GATE CS 2025 Set 1 Q.54 on a look-ahead window. Every trace and count was produced by a replacement simulator.
Files, attributes and the open-file tables; directory structures from single-level to acyclic graph; hard and soft links; contiguous, linked, FAT and indexed allocation with their access costs; the inode block map and the maximum file size formula with computed values; disk reads needed to reach a given byte offset; pointer size from disk size; and free-space management by bitmap, linked list, grouping and counting, with bitmap and FAT sizes. All values were computed by script.
Disk geometry, capacity and transfer rate; access time as seek plus rotational latency plus transfer, with computed latencies for common speeds; random versus sequential reads; FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK with head paths and totals on two worked queues and a figure of SCAN and C-SCAN; the return-sweep convention; seek time at a fixed cost per cylinder; programmed I/O, interrupt-driven I/O and DMA; buffering and spooling; and the solved GATE CS 2024 Set 2 Q.53. All values were computed by script.
The common wrong intuitions across the Operating Systems pack, one row each: the wrong belief, the correct rule, and the check or consequence to remember, grouped from system calls and processes through synchronization, deadlock, scheduling, memory, virtual memory, files and disks, with a link to the sheet that explains each rule.
The recurring Operating Systems question patterns, each with its recognition cue, the first step and method, the check that can change the answer, and the usual failure, with a pointer to the sheet that holds the routine and the solved past questions in the pack; followed by a generic routine for any numerical OS question.
A one-page summary of the Operating Systems pack: the essential formulas with their conditions for scheduling, deadlock, paging, access time, files and disks; the key one-line facts for processes, threads, synchronization and memory; replacement policies and Belady; anchor numbers from the solved past questions; and the checks to run before marking an answer.
Computer Organization & ArchitectureData StructuresDatabase Management Systems
