Operating Systems

Complete Short Notes

Gate Smashers Playlist (92 Videos) | Varun Sir
GATE CSE 2027 | AIR <100 Topper Style
Maximum Information • Minimum Words • GATE PYQ Focused

Chapter 1: Introduction to Operating Systems

What is an OS?
• OS = Interface between user and hardware; manages resources (CPU, memory, I/O)
• Kernel = Core of OS, always resident in memory
• OS = Kernel + System Programs + Utilities

Goals of OS
• Primary: Convenience (ease of use)
• Secondary: Efficiency (optimal resource utilization)

Types of Operating Systems

Type Key Feature Example
Batch OS Jobs grouped, no interaction IBM OS/360
Multiprogramming Multiple jobs in memory; CPU never idle Early mainframes
Multitasking / Time- CPU switches rapidly; user interaction possible UNIX
Sharing
Real-Time OS (RTOS) Strict timing deadlines VxWorks, FreeRTOS
Distributed OS Multiple machines appear as one Amoeba

Privileged Instructions & Dual Mode

• Kernel mode: Full access to hardware & all instructions
• User mode: Restricted; cannot execute privileged instructions
• Privileged examples: I/O instructions, interrupt handling, modify PCB, halt CPU
• User → Kernel: via System Call (trap/software interrupt)

System Calls
• Interface between user program and OS kernel
Category Examples
Process Control fork(), exec(), wait(), exit(), abort()
File Management open(), close(), read(), write(), delete()
Device Management ioctl(), read(), write()
Information Maintenance getpid(), alarm(), sleep()
Communication pipe(), socket(), send(), recv()

📌 GATE PYQ Focus (Last 10 Years)

★ Difference: multiprogramming vs multitasking (multiprogramming = multiple jobs in memory;
multitasking = time-sharing with CPU switching)
★ What is a privileged instruction? Examples (I/O, interrupt control)
★ Kernel mode vs user mode transitions
★ System call examples and categories
★ Types of OS and their characteristics

Chapter 2: Process Management

Process vs Program
Aspect Program Process
Nature Passive (stored on disk) Active (in execution)
Contents Code only Code + Data + Stack + Heap + PCB
Instance One Multiple processes possible

Process Control Block (PCB)

• Process ID (PID)
• Process State (new/ready/running/blocked/terminated)
• Program Counter (PC) – address of next instruction
• CPU Registers – all register values
• Memory management info – page table, segment table
• Scheduling info – priority, pointers
• I/O status – open files, devices allocated

Process States
New ──► Ready ──► Running ──► Terminated
▲ │
│ I/O Request
│ ▼
I/O Complete Waiting/Blocked

Transition Event Direction

Ready → Running Dispatcher selects process Scheduled
Running → Ready Timer interrupt / preemption Preempted
Running → Blocked I/O request / wait() Blocked
Blocked → Ready I/O completion / event occurs Unblocked
Running → Terminated exit() / abort() Completed

Context Switch
• Save state of current process (to PCB), load state of next
• Pure overhead – no useful work done during switch
• Triggered by: timer interrupt, system call, I/O request

fork() – Key Facts (GATE TRICK!)

fork() return values:
→ Returns 0 to child process
→ Returns child's PID to parent
→ Returns -1 on failure

n fork() calls → 2^n total processes (including parent)

→ 2^n - 1 child processes

fork(); fork(); fork(); → 2^3 = 8 processes, 7 children

NOTE: If fork() inside if/else, count carefully which branch executes!

Zombie vs Orphan Process

Zombie Process Orphan Process
Definition Child finished, parent hasn't called Parent died before child
wait()
PCB Status PCB still exists in process table Adopted by init (PID 1)
Fix Parent calls wait() init calls wait() for it
Resource Uses PCB entry only Full resource usage

Process vs Thread
Aspect Process Thread
Address Space Separate per process Shared within process
Creation overhead High Low (lightweight)
Communication IPC needed (pipes, sockets) Direct via shared memory
Context switch Slow (full PCB save) Fast (minimal state)
Crash impact Isolated from others Crashes all threads in process
Resources Has own resources Shares resources

Thread Types & Models

Type Managed By Blocking Multiprocessor
User-Level Thread (ULT) Thread library Blocks entire process Cannot exploit
Kernel-Level Thread (KLT) OS Kernel Only that thread blocks Can exploit
Model Mapping Advantage Disadvantage
Many-to-One Many ULT → 1 KLT Efficient One block = all block
One-to-One 1 ULT → 1 KLT True parallelism High overhead
Many-to-Many Many ULT → Many KLT Best of both Complex

📌 GATE PYQ Focus (Last 10 Years)

★ fork() return values (0 to child, child-PID to parent, -1 on error)
★ Number of processes created by n fork() calls = 2^n
★ Zombie process – definition and how to fix
★ Orphan process – adopted by init
★ Thread vs process comparison
★ User-level vs kernel-level thread (blocking behavior)
★ Context switch overhead – pure overhead concept

Chapter 3: CPU Scheduling

Scheduling Queues & Schedulers
Scheduler Also Called Transition Frequency
Long-Term Job Scheduler New → Ready Infrequent; controls
multiprogramming degree
Short-Term CPU Scheduler Ready → Running Very frequent (every ~100ms)
Medium-Term Swapper Suspend/Resume Medium; swap in/out processes

Scheduling Criteria
Criterion Goal Formula
CPU Utilization Maximize (40-90%) CPU busy time / Total time
Throughput Maximize # processes / unit time
Turnaround Time (TAT) Minimize CT - AT
Waiting Time (WT) Minimize TAT - BT = Start - AT (non-preemptive)
Response Time Minimize First response - AT

Scheduling Algorithms
Algorithm Preemptive Starvation Key Property Weakness
FCFS No No Simplest; FIFO order Convoy effect
SJF No Yes Optimal avg WT Need future
knowledge
SRTF Yes Yes Preemptive SJF Starvation of long
jobs
Priority Both Yes Higher priority first Starvation; fix: Aging
Round Robin Yes No Time quantum q; fair High overhead if q
small
MLFQ Yes No Processes can move queues Complex to configure

Key Algorithm Details

• FCFS Convoy Effect: Short jobs wait behind long jobs → poor I/O utilization
• SJF: Provably optimal for minimizing average waiting time (non-preemptive)
• SRTF: New arrival preempts current if new BT < remaining BT of current
• Aging: Gradually increase priority of long-waiting processes → prevents starvation
• Round Robin: q → ∞ becomes FCFS; q → 0 too many context switches
• Multilevel Queue: No migration between queues; Multilevel Feedback Queue: allows migration

TAT = Completion Time (CT) - Arrival Time (AT)

WT = TAT - Burst Time (BT)
WT = Start Time - AT (only if no preemption)
Response Time = First CPU start - AT
Throughput = # processes completed / Total time span
CPU Utilization = Busy time / Total time × 100%

📌 GATE PYQ Focus (Last 10 Years)

★ FCFS convoy effect explanation
★ SJF is optimal for average waiting time (proof concept)
★ Round Robin: effect of time quantum on performance
★ Multilevel Feedback Queue – can mimic all other algorithms
★ Calculate avg WT/TAT from Gantt chart (MOST ASKED – practice numerical!)
★ SRTF preemption: new arrival preempts if new BT < remaining BT
★ Priority scheduling + aging to prevent starvation

Chapter 4: Process Synchronization & Deadlock

Critical Section Problem
• Critical Section (CS): Code segment accessing shared resources
• Race Condition: Multiple processes access shared data concurrently → inconsistent results

Requirements for CS Solution

Requirement Meaning
1. Mutual Exclusion Only ONE process in CS at a time
2. Progress If no process in CS, selection must proceed (not postponed forever)
3. Bounded Waiting Finite limit on how many times others enter before waiting process gets
in
Peterson's Solution (2 processes)
// Process Pi:
flag[i] = true; // I want to enter
turn = j; // But you go first
while (flag[j] && turn == j); // Wait if j wants in AND it's j's turn
// ---- CRITICAL SECTION ----
flag[i] = false; // I'm done

Note: Software solution, valid only for 2 processes

Satisfies: Mutual Exclusion + Progress + Bounded Waiting ✓

Semaphores
Operation Code Effect
wait(S) / P(S) while S≤0; S--; Decrement; block if 0
signal(S) / V(S) S++; Increment; wake blocked

Type Value Range Use

Binary Semaphore (Mutex) 0 or 1 Mutual exclusion
Counting Semaphore 0 to N Resource counting

Classical Synchronization Problems

1. Producer-Consumer (Bounded Buffer)
Semaphores: mutex = 1, full = 0, empty = n (buffer capacity)

Producer: Consumer:
wait(empty) ← MUST BE wait(full) ← MUST BE
wait(mutex) BEFORE wait(mutex) BEFORE
produce() mutex! consume() mutex!
signal(mutex) signal(mutex)
signal(full) signal(empty)

⚠️ GATE TRICK: Always wait(empty/full) BEFORE wait(mutex) → else DEADLOCK!

2. Readers-Writers Problem
• First R-W: Readers have priority (writers may starve)
• Second R-W: Writers have priority (readers may starve)
readcount = 0, mutex = 1, wrt = 1

Reader: Writer:
wait(mutex) wait(wrt)
readcount++ WRITE
if readcount==1: wait(wrt) signal(wrt)
signal(mutex)
READ
 wait(mutex)
readcount--
if readcount==0: signal(wrt)
signal(mutex)

3. Dining Philosophers
• 5 philosophers, 5 chopsticks (semaphores)
• Naive solution: all pick left → DEADLOCK!
• Solution 1: Allow max 4 philosophers to sit simultaneously
• Solution 2: Odd philosophers pick left-right; even pick right-left
• Solution 3: Pick both chopsticks atomically (mutex for pick-up)

Monitors
• High-level construct; mutual exclusion built-in (only one process active)
• Condition variables: wait() and signal()
• [Link]() → releases monitor, suspends calling process
• [Link]() → wakes one waiting process; no-op if none waiting
• Monitor vs Semaphore: Monitor is safer (harder to misuse)

Deadlock
Coffman's 4 Conditions (ALL must hold simultaneously)
Condition Meaning Prevention (deny this)
Mutual Exclusion Resource held exclusively Make resources sharable (not always
possible)
Hold and Wait Process holds & waits for more Request all resources at start OR release
before requesting more
No Preemption Cannot forcibly take resource Allow preemption (save & restore state)
Circular Wait Cycle of waiting processes Total ordering of resource types; request in
order

Resource Allocation Graph (RAG)

• Request edge: P → R (process requests resource instance)
• Assignment edge: R → P (resource instance assigned to process)
• Single instance resources: Cycle in RAG ↔ Deadlock (necessary and sufficient)
• Multiple instance resources: Cycle necessary but NOT sufficient for deadlock

Banker's Algorithm (Deadlock Avoidance)

Data Structures (n processes, m resources):
Available[m] – free instances of each resource
Max[n×m] – max demand of each process
Allocation[n×m] – current allocation
Need[n×m] = Max - Allocation

Safety Algorithm:
 Work = Available; Finish[i] = false for all i
Find i: !Finish[i] AND Need[i] ≤ Work
Work += Allocation[i]; Finish[i] = true
Repeat until no such i found
If all Finish[i] = true → SAFE STATE ✓

Resource Request:
If Request[i] ≤ Need[i] AND Request[i] ≤ Available:
Tentatively allocate → run safety check → if safe: grant, else rollback

Deadlock Handling Strategies

Strategy Approach Cost Used In
Prevention Negate one Coffman condition Low utilization Some systems
Avoidance Banker's algorithm; stay in safe Need advance info Real-time systems
state
Detection + Run detection periodically; kill or Overhead + recovery Some DBs
Recovery preempt cost
Ignore (Ostrich) Assume deadlock rare; do Deadlock may occur Windows, Linux
nothing (default!)

📌 GATE PYQ Focus (Last 10 Years)

★ Banker's algorithm – finding safe sequence, Need matrix calculation (VERY FREQUENTLY
ASKED)
★ Deadlock conditions – which can be violated for prevention and how
★ RAG: Single instance: cycle ↔ deadlock; Multi-instance: cycle is only necessary
★ Peterson's solution – satisfies all 3 CS requirements
★ Semaphore wait/signal order in producer-consumer (deadlock if order wrong)
★ Monitor – mutual exclusion built-in; condition variable wait vs signal
★ Dining philosophers – deadlock scenario and solutions
★ Deadlock vs starvation vs livelock differences

Chapter 5: Memory Management

Address Types & Binding
Binding Time Address Type When Hardware
Needed
Compile Time Absolute (physical) If memory location known at compile None
time
Load Time Relocatable Binding at program load None
Execution Time Logical ≠ Physical Binding deferred to runtime MMU required
• Logical Address = Virtual Address (generated by CPU)
• Physical Address = Actual RAM address
 • MMU (Memory Management Unit): Translates logical → physical at runtime

Contiguous Memory Allocation

Strategy Fragmentation Performance Notes
Fixed Partitioning Internal (wasted inside partition) Simple Easy to implement
Variable Partitioning External (gaps between Moderate Compaction needed
partitions)

Allocation Strategies
Strategy Method Fragmentation Speed
First Fit First hole ≥ requested size Moderate Fastest
Best Fit Smallest hole ≥ requested size Worst (tiny leftovers) Slower
Worst Fit Largest hole Bad Slowest
• First Fit and Best Fit outperform Worst Fit in practice
• External Fragmentation fix: Compaction (expensive) or Paging/Segmentation

Paging
• Divide logical memory into fixed-size pages; physical memory into frames (same size)
• Page size = power of 2 (simplifies address calculation)
• No external fragmentation; internal fragmentation in last page (max: page size - 1 bytes)

Address Translation
Logical Address → [Page Number (p) | Page Offset (d)]

p = Logical Address / Page Size (integer division)

d = Logical Address mod Page Size

Physical Address = Frame[p] × Page Size + d

Example: Logical=2049, Page Size=1024

p = 2049/1024 = 2, d = 2049%1024 = 1
If Frame[2]=5: Physical = 5×1024 + 1 = 5121

TLB (Translation Lookaside Buffer)

• Hardware cache for page table entries
• TLB Hit: Frame found in TLB → 1 memory access total
• TLB Miss: Access page table in memory → 2 memory accesses total

EAT = h × (α + m) + (1-h) × (α + 2m)

h = TLB hit ratio

α = TLB access time
m = Memory access time
 Example: h=0.9, α=10ns, m=100ns
EAT = 0.9(10+100) + 0.1(10+200) = 0.9(110) + 0.1(210) = 99+21 = 120ns

Multi-Level Paging
• Page table itself is paged to reduce page table size in memory
• 2-level paging: Logical = [p1 | p2 | d] → 3 memory accesses (no TLB)
• k-level paging → k+1 memory accesses without TLB
• TLB reduces all multi-level accesses to ≈ 1+α regardless of levels

Inverted Page Table

• One entry per physical frame (not per logical page)
• Indexed by frame; entry contains (PID, page number)
• Search: find (PID, page) → get frame number
• Saves space (# frames << # logical pages); slower lookup (linear search or hash)

Segmentation
• Divide logical space into variable-size segments (code, data, stack)
• Logical address: <segment number, offset>
• Segment table: base + limit per segment
• External fragmentation (like variable partitioning); no internal fragmentation

Aspect Paging Segmentation

Division basis Fixed size (hardware view) Variable size (programmer view)
Fragmentation Internal only External only
Address [page no | offset] [segment no | offset]
Sharing Hard (page boundary issue) Easy (share a segment)
Protection Less natural Natural (segment-based)

📌 GATE PYQ Focus (Last 10 Years)

★ TLB EAT calculation with given hit rate, TLB time, memory time (VERY FREQUENTLY ASKED)
★ Page number and page offset calculation from logical address
★ Internal vs external fragmentation – which occurs where
★ Multi-level paging – number of memory accesses = levels + 1
★ Inverted page table – saves space, slower lookup
★ First fit vs best fit vs worst fit performance
★ Segmentation vs paging fragmentation types
Chapter 6: Virtual Memory
Demand Paging
• Pages loaded into memory only when accessed (lazy loading)
• Valid-Invalid bit in page table: v = in memory, i = not in memory
• Page Fault: CPU accesses page with invalid bit → trap to OS

Page Fault Handling Steps

1. CPU references address → check page table → bit = invalid
2. OS trap (page fault interrupt)
3. Find free frame (from free-frame list)
4. Schedule disk I/O to load page from backing store
5. Update page table: set frame number, valid bit = 1
6. Restart the faulting instruction

Dominant cost: DISK I/O time (milliseconds vs nanoseconds for memory)

EAT with page faults:

EAT = (1 - p) × m + p × T_pf

p = page fault rate (0 ≤ p ≤ 1)

m = memory access time
T_pf = page fault service time (≈ disk access ≈ 8ms)

For <10% degradation: p < 1 / (400,000) approx

Copy-on-Write (COW)
• After fork(), parent and child share same physical pages
• A copy is made only when either process writes to a shared page
• Highly efficient for fork() + exec() pattern (exec overwrites without needing copies)

Page Replacement Algorithms

Algorithm Replace Which? Belady's Anomaly Optimal? Impl
eme
ntab
le?
FIFO Oldest page in memory YES ← bad No Yes
(eas
y)
Optimal (OPT/MIN) Not used for longest future No YES (best) No
time (nee
ds
futur
e)
LRU Not used for longest past time No Near-optimal Costl
y
Second Chance FIFO + reference bit check No LRU approx Yes
(Clock) (effici
ent)

LRU Implementation Methods

• Counter Method: Each page has time-of-last-use counter; replace minimum counter
• Stack Method: Keep doubly linked list; recently used → top; replace bottom (tail)
• Both costly in hardware; approximations used in practice

Clock (Second Chance) Algorithm

Each page has a Reference bit (R).
When page accessed: R = 1
Replacement process (clock hand sweeps):
If R = 1: Clear to 0, advance hand (give second chance)
If R = 0: REPLACE this page

Enhanced: Use (R, M) bits: prefer (0,0) > (0,1) > (1,0) > (1,1)

Thrashing
• Process spends more time paging than executing → CPU utilization collapses
• Cause: Too many processes, each with insufficient frames → continuous page faults
• Feedback loop: Low CPU util → OS adds more processes → more faults → worse

Solutions to Thrashing
• Working Set Model: Track pages used in last Δ (window) time units → allocate accordingly
• Page Fault Frequency (PFF): If fault rate too high → give more frames; too low → take frames
• Reduce degree of multiprogramming (swap out some processes)

Frame Allocation Policies

Policy Description Notes
Equal Allocation m frames / n processes each Ignores process size
Proportional Allocation Frames ∝ process size Fairer
Global Replacement Can steal frames from other Better utilization but can cause thrashing
processes
Local Replacement Only replace own frames More predictable behavior

📌 GATE PYQ Focus (Last 10 Years)

★ Page replacement calculations – FIFO, LRU, OPT (MOST ASKED – practice many problems!)
★ Belady's anomaly – only FIFO suffers; OPT and LRU do not
★ EAT with page fault rate calculation
★ Thrashing – definition, cause, solution (working set model)
★ Copy-on-Write – why it makes fork() efficient
 ★ Clock algorithm – second chance principle
★ Optimal algorithm – not implementable but used as benchmark

Chapter 7: File System

File Allocation Methods
Method Access External Frag? Internal Frag? Advantage Disadv
antage
Contiguous Sequential & Direct YES No Fast, simple Fragme
ntation,
pre-
allocati
on
Linked Sequential only No No No ext frag Slow
direct,
pointer
overhe
ad
FAT Sequential & Direct No No Direct via FAT table FAT
must
be in
memor
y
Indexed Sequential & Direct No No Direct access Index
block
overhe
ad

Unix Inode Structure

Inode contains:
12 Direct block pointers → 12 × B bytes
1 Single Indirect pointer → (B/P) × B bytes
1 Double Indirect pointer → (B/P)² × B bytes
1 Triple Indirect pointer → (B/P)³ × B bytes

Max File Size = 12B + (B/P)×B + (B/P)²×B + (B/P)³×B

B = Block size in bytes

P = Pointer size in bytes
Pointers per block = B/P

Example: B = 1KB = 1024, P = 4 bytes → B/P = 256

Max size = 12×1 + 256×1 + 256²×1 + 256³×1 KB
= 12 + 256 + 65536 + 16777216 KB ≈ 16 GB

Hard Link vs Symbolic (Soft) Link

Aspect Hard Link Symbolic (Soft) Link
Points to Inode directly File name/path
If original deleted File still accessible Dangling link (broken)
Cross filesystem Not allowed Allowed
Inode Same inode as original Different inode
Directory entry Another name for same inode Separate file containing path

Disk Scheduling
Algorithm Starvation Total Seek Key Property
FCFS No Highest Fair but no optimization
SSTF YES Low (greedy) Nearest request first; not globally optimal
SCAN (Elevator) No Medium Sweeps back and forth to disk ends
C-SCAN No Medium One direction only; jump back to start
LOOK No Low SCAN but only to last request
C-LOOK No Lowest Best practical; circular with last-request limit

RAID Levels
RAID Level Description Overhead Use Case
RAID 0 Striping only – no redundancy 0% Max performance, no fault
tolerance
RAID 1 Mirroring – full copy 100% (2× storage) High reliability
RAID 5 Striping + distributed parity 1 disk Best read performance +
redundancy
RAID 6 Like RAID 5 + extra parity 2 disks Can survive 2 disk failures
RAID 10 Mirror of stripes (1+0) 50% High performance +
reliability

📌 GATE PYQ Focus (Last 10 Years)

★ Maximum file size with Unix inode (direct + 3 levels indirect) – calculation
★ Number of disk accesses to read a block using indexed allocation
★ Hard link vs soft link – behavior when original is deleted
★ FCFS, SSTF, SCAN, C-SCAN head movement calculation
★ SSTF starvation – why and when
★ RAID 0, 1, 5 – differences in redundancy and overhead
★ Linked allocation – FAT variation and its advantage
Chapter 8: I/O Systems
I/O Control Methods
Method CPU Role Best For Efficiency
Programmed I/O (Polling) Continuously checks device Simple/slow devices Low – wastes
(busy wait) CPU
Interrupt-Driven I/O Handles interrupt after each byte Character devices Medium
(keyboard)
DMA (Direct Memory Access) Sets up transfer; interrupted only Block devices (disk) High – CPU
at end free during
transfer

DMA Working
1. CPU gives DMA: source address, destination address, byte count
2. DMA takes over the bus and transfers data directly to/from memory
3. DMA interrupts CPU when transfer is complete
4. CPU only involved at START and END of transfer

Advantage: CPU free during large data transfers → better throughput

Used for: Disk I/O, network cards, graphics

Buffering
• Single Buffer: Producer → buffer → consumer; one at a time
• Double Buffer: Two buffers alternate → producer fills one while consumer empties other
• Circular Buffer: Ring of N buffers; enables pipeline processing
• Purpose: Smooth out speed mismatch between producer and consumer

Spooling
• Simultaneous Peripheral Operations On-Line
• Buffer for devices serving one job at a time (e.g., printer)
• Jobs written to disk spool; device pulls from spool queue
• Allows multiple processes to 'use' exclusive device concurrently

📌 GATE PYQ Focus (Last 10 Years)

★ DMA – working principle and when it is used
★ Interrupt vs polling trade-offs (CPU efficiency)
★ Spooling – purpose and common example (printer)
★ Buffering types – single vs double buffer
 ONE-PAGE FORMULA SHEET & QUICK REVISION
SUMMARY
Operating Systems – GATE CSE 2027

CPU Scheduling Formulas

TAT (Turnaround Time) = Completion Time (CT) - Arrival Time (AT)
WT (Waiting Time) = TAT - Burst Time (BT)
WT (non-preemptive) = Start Time - AT [only when no preemption before first run]
Response Time = First CPU allocation start - AT
Throughput = # processes / Time span
CPU Utilization = 1 - (1 - p)^n [p = I/O wait fraction, n =
multiprogramming degree]

Memory Management Formulas

Page Number (p) = Logical Address ÷ Page Size (integer division)
Page Offset (d) = Logical Address mod Page Size
Physical Addr = Frame[p] × Page Size + d

EAT (with TLB) = h(α + m) + (1-h)(α + 2m)

h = hit rate, α = TLB time, m = memory time

EAT (with PF) = (1-p)×m + p×T_pf

p = page fault rate, T_pf = page fault service time

Max file size = 12B + (B/P)×B + (B/P)²×B + (B/P)³×B

B = block size, P = pointer size

Disk Access = Seek Time + Rotational Latency + Transfer Time

Avg Rot Latency = 1/2 × (1/RPM in seconds)

Process Management Quick Facts

Concept Key Point
fork() returns 0 → child | child-PID → parent | -1 → error
n fork() calls 2^n total processes, 2^n - 1 children
Zombie Child done, parent didn't wait()
Orphan Parent died; adopted by init (PID 1)
Context Switch Pure overhead; saves/loads PCB
ULT vs KLT ULT: fast switch, blocks all; KLT: true parallelism

Scheduling Summary
Algorithm Preemptive? Starvation? Key Fact
FCFS No No Convoy effect; simple
SJF No Yes Optimal avg WT
SRTF Yes Yes Best preemptive
Priority Both Yes Fix: Aging
Round Robin Yes No Time quantum q; larger q→FCFS
MLFQ Yes No Most flexible; can mimic others

Synchronization & Deadlock

Concept Key Point
CS Requirements Mutual Exclusion + Progress + Bounded Waiting
Peterson's Software; 2 processes only; uses flag[] and turn
Semaphore order wait(full/empty) BEFORE wait(mutex) in Prod-Consumer
Deadlock conditions ME + Hold&Wait + No Preemption + Circular Wait
Banker's safety Need ≤ Work → grant; add Allocation to Work; repeat
RAG (single) Cycle ↔ Deadlock (iff)
RAG (multi) Cycle → possible deadlock (necessary not sufficient)
Safe state Safe state ≠ No deadlock; Unsafe ≠ Deadlock (may or may not)

Memory Fragmentation Summary

Allocation Int. Frag Ext. Frag Notes
Fixed Partition Yes No Simple
Variable Partition No Yes Compaction needed
Paging Yes (last page) No Best for elimination of ext. frag
Segmentation No Yes Meaningful division
Paged Segmentation Yes (last page) No Used in Intel x86

Page Replacement Summary

Algorithm Belady's? Optimal? Note
FIFO YES No Simple; suffers Belady's anomaly
OPT No YES Benchmark only; not implementable
LRU No Near-optimal Costly; counter or stack implementation
Clock No Approx LRU Efficient approximation; used in practice

File System & Disk

Concept Key Point
Contiguous Fast; external fragmentation; hard to grow
Linked/FAT No ext frag; sequential only; FAT in memory
Indexed (Inode) Direct access; 12 direct + 3 indirect levels
Hard Link Same inode; file survives original deletion
Soft Link Different inode; breaks if original deleted
RAID 0 Striping; no redundancy; best performance
RAID 1 Mirroring; 100% overhead; best reliability
RAID 5 Distributed parity; 1 disk overhead; balanced
Disk SSTF Greedy; starvation possible
C-LOOK Best practical disk algorithm; uniform wait

📌 Top 5 Most Asked GATE OS Topics

Rank Topic Frequency
1 Page Replacement (FIFO, LRU, OPT) – numerical problems Almost every year
2 CPU Scheduling – Gantt chart, avg WT/TAT calculation Almost every year
3 Banker's Algorithm – safe sequence, Need matrix Very frequent
4 TLB EAT calculation with hit ratio Very frequent
5 Semaphore problems – Producer-Consumer, Readers-Writers Frequent

Best of luck – GATE CSE 2027! You've got this! 🎯

Notes based on Gate Smashers OS Playlist (92 videos) by Varun Sir