OS · whole subject on one page

Short notes: Operating Systems

Every topic in revision form: the key ideas, formulas, the question types GATE asks, and the traps. Read it the night before.

1. 🧵 Processes, Threads & System Calls

Medium ●●15 PYQs →

The base vocabulary of the subject, plus a reliable fork() question: count the processes or the prints.

  • Process, PCB and process states. A process is a program in execution: code, data, heap, stack and CPU state. The OS keeps a process control block (PCB) per process: state, program counter, registers, scheduling info, memory info, open files. States: New → Ready → Running, then Running → Waiting (I/O or event), Running → Ready (time slice over or preempted), Running → Terminated. A Waiting process goes back to Ready, never directly to Running.
    → Waiting → Ready, never Waiting → Running. The PCB holds everything needed to resume.
  • Context switch, modes and system calls. A context switch saves the state of one process in its PCB and loads another: pure overhead, no useful work. The CPU runs in user mode or kernel mode. A system call is a controlled entry into kernel mode (via a trap / software interrupt); the mode bit is set, the kernel runs, then returns. Privileged instructions (I/O, halt, changing the mode bit or page tables) fault in user mode. Interrupts are asynchronous (from devices); traps and exceptions are caused by the running instruction.
    → Mode switch ≠ context switch. Privileged instructions fault in user mode; a trap enters the kernel on purpose.
  • Threads versus processes. A thread is a unit of CPU execution inside a process. Threads of one process share code, data, heap, open files and the address space; each has its own stack, registers and program counter. Thread creation and switching are cheaper than for processes and sharing needs no IPC, but one thread can corrupt the others. User-level threads are invisible to the kernel (fast, but one blocking call blocks all, no multi-core use); kernel-level threads are scheduled by the kernel.
    → Threads share the address space, not the stack. User-level threads: one block blocks all.
  • fork() and process trees. fork() creates a copy of the calling process. It returns 0 in the child and the child's pid (non-zero) in the parent, and both continue from the next statement. n unconditional forks in a row give 2ⁿ processes in total (2ⁿ − 1 children). In if (fork() == 0) only the child enters the branch; with && and || the second fork runs only in the parent or only in the child respectively. wait() makes the parent block until a child exits; a child whose parent has not waited is a zombie.
    → n sequential forks: 2ⁿ processes. Child continues after the fork. Conditions like == 0 or && limit who forks.

Formulas

Processes after n sequential forks
2ⁿ in total, 2ⁿ − 1 new children
Fork in a loop (for i in 1..n)
2ⁿ processes (every process, including children, keeps looping)
fork() return value
0 in the child, child pid in the parent, −1 on failure
Context-switch overhead
efficiency = quantum / (quantum + switch time)

What GATE asks

  • ★★★How many processes / times is something printed after these forks. Draw the tree. Remember that a child inherits the loop counter value at the time of the fork.
  • ★★★Which operations need kernel mode / which are privileged. I/O instructions, halt, setting the timer and changing the mode bit are privileged; reading the clock may not be.
  • ★★★Thread versus process properties. What is shared (address space, files) and what is private (stack, registers).
  • ★★★Which transitions are possible in the state diagram. Waiting → Running and Ready → Waiting do not exist.

Traps

After fork() the child does not restart from the top: it continues after the fork call.
Variables are copied, not shared, between parent and child: a child's change is invisible to the parent.
A user-level thread blocking on I/O blocks the whole process, because the kernel only sees one thread.
Interrupt-driven preemption is not a system call: system calls are requested by the program, interrupts come from hardware.

2. ⏱️ CPU Scheduling

High yield ●●●13 PYQs →

Almost every paper has a Gantt-chart numerical: average waiting or turnaround time for SRTF, round robin or priority.

  • Scheduling metrics and the Gantt chart. Arrival time (AT), burst time (BT), completion time (CT). Turnaround = CT − AT. Waiting = Turnaround − BT. Response = first CPU time − AT. Draw a Gantt chart left to right and note the idle gaps when no process has arrived. The scheduler picks from the ready queue; the dispatcher does the switch. Preemptive policies can take the CPU away; non-preemptive ones wait for the burst to end or block.
    → TAT = CT − AT. WT = TAT − BT. RT = first run − AT. Do not forget idle time.
  • FCFS, SJF and SRTF. FCFS: first come first served, non-preemptive, simple but suffers the convoy effect (short jobs stuck behind a long one). SJF: shortest next burst first, non-preemptive, gives the minimum average waiting time among non-preemptive policies. SRTF: the preemptive version: when a new process arrives with a burst shorter than the remaining time of the running one, it preempts. Both can starve long jobs, and the burst length must be predicted (exponential averaging).
    → SJF/SRTF: optimal for waiting time but can starve long jobs and need the burst length in advance.
  • Round robin. Each process gets a time quantum q, then goes to the back of the ready queue. Preemptive, fair, good response time. A very large q behaves like FCFS; a very small q wastes time on context switches. With n processes the longest a process waits for its first turn is (n − 1)q. When a process arrives at the same instant a quantum ends, the usual convention is: the new arrival enters the queue before the preempted process.
    → RR: large q → FCFS, tiny q → all overhead. Arrivals join the queue before the preempted process.
  • Priority scheduling, starvation and aging. The CPU goes to the highest-priority ready process (check whether a smaller number means higher priority). Can be preemptive or not. Starvation: low-priority processes may never run. Aging raises the priority of a waiting process over time. Priority inversion: a high-priority process waits for a lock held by a low-priority one that a medium-priority process keeps preempting; fixed by priority inheritance.
    → Priority: check the numbering. Starvation is cured by aging; inversion by priority inheritance.
  • Multilevel queues, feedback queues and real-time. Multilevel queue: separate queues (system, interactive, batch), each with its own policy, strict priority between queues. Multilevel feedback queue: processes move between queues based on behaviour: CPU hogs sink to lower queues with longer quanta, I/O-bound ones stay on top. Real-time: rate monotonic (static, shorter period = higher priority; schedulable if utilisation ≤ n(2^(1/n) − 1)) and EDF (dynamic, earliest deadline first; schedulable if utilisation ≤ 1).
    → RM bound n(2^(1/n) − 1) is sufficient only; EDF: U ≤ 1.

Formulas

Turnaround time
TAT = CT − AT
Waiting time
WT = TAT − BT
Response time
RT = (first time on CPU) − AT
CPU utilisation
useful time / total time, where total includes context-switch time
Round robin first wait
at most (n − 1) × q for n processes that all arrived
Rate-monotonic bound
U = Σ Cᵢ/Tᵢ ≤ n (2^(1/n) − 1) (sufficient test); EDF: U ≤ 1
Exponential averaging
τ(n+1) = α·t(n) + (1 − α)·τ(n)

What GATE asks

  • ★★★Average waiting / turnaround time for SRTF, RR or priority. Draw the Gantt chart carefully, mark preemption points and arrival ties, then compute WT = TAT − BT.
  • ★★★Which algorithm gives minimum average waiting time or can starve. SJF is optimal for waiting time; SJF, SRTF and priority can starve; RR and FCFS cannot.
  • ★★★Effect of the time quantum. Large q turns RR into FCFS; small q raises context-switch overhead; compute CPU efficiency.
  • ★★★Processes with I/O bursts. Alternate CPU and I/O bursts: the CPU is idle only if every process is in I/O.

Traps

Idle time: if no process has arrived, the Gantt chart has a gap. Do not skip it.
In SRTF compare the new arrival with the remaining time of the running process, not its original burst.
Priority numbers: check whether lower number = higher priority before choosing.
In round robin, the order of the queue when an arrival coincides with a quantum expiry changes the answer: follow the stated convention.

3. 🔒 Synchronization & Concurrency

High yield ●●●10 PYQs →

Semaphore programs and critical-section solutions are tested every year: does it ensure mutual exclusion, deadlock freedom, what outputs are possible.

  • Race conditions and the critical-section problem. A race condition is when the result depends on the interleaving of operations on shared data, e.g. counter++ is load, add, store, so two threads can lose an update. The critical section is code touching shared data. A correct solution needs three things: mutual exclusion (one at a time), progress (a process outside the critical section cannot block others from entering; the decision cannot be postponed forever) and bounded waiting (no process waits indefinitely while others repeatedly enter).
    → Mutual exclusion, progress, bounded waiting. Lost updates are the symptom of a race.
  • Software and hardware solutions. Peterson's algorithm (two processes): set flag[i] = true, set turn = j, wait while flag[j] and turn == j. It satisfies all three requirements. Strict alternation (turn only) gives mutual exclusion but violates progress. Flags only can deadlock. Hardware: test-and-set and compare-and-swap are atomic; a spinlock built on them gives mutual exclusion but not bounded waiting by itself, and spins (busy waiting). Disabling interrupts works on a single CPU only.
    → Peterson: flag, then turn = other, wait while other wants and has the turn. Test-and-set: atomic but no bounded waiting.
  • Semaphores. A semaphore is an integer with two atomic operations: P (wait): wait until S > 0, then S = S − 1; V (signal): S = S + 1 (waking one waiter). A binary semaphore (initial 1) acts as a mutex lock; a counting semaphore (initial n) controls n identical resources. A semaphore initialised to 0 enforces an order (A must run before B). Typical bugs: P and V swapped, P(S) twice in a row, P on two semaphores in opposite orders (deadlock).
    → Binary semaphore starts at 1; counting at n; "order" semaphore starts at 0. P(S)P(S) blocks forever.
  • Classic problems. Producer-consumer (bounded buffer of n): semaphores empty = n, full = 0, mutex = 1; the producer does P(empty), P(mutex), add, V(mutex), V(full). Taking mutex before empty can deadlock. Readers-writers: many readers or one writer; the first reader locks writers out and the last one lets them back in; reader-preference can starve writers. Dining philosophers: if every philosopher grabs the left fork first, all can hold one fork and deadlock; fixes: allow at most n − 1 at the table, pick up both forks atomically, or make one philosopher left-handed (resource ordering).
    → empty = n, full = 0, mutex = 1; counting semaphores first, mutex innermost. Philosophers: break circular wait.
  • Monitors, condition variables and priority inversion. A monitor is a language-level construct: shared data plus procedures, with only one process active inside at a time. Condition variables support wait() (release the monitor and sleep) and signal() (wake one waiter). Unlike a semaphore, a signal with nobody waiting is lost. Other tools: mutex (owned by the locker), spinlock (busy-wait, good only for very short waits on multiprocessors), barrier. Priority inversion and its fix, priority inheritance, belong here too.
    → Monitor: one active process, signal can be lost. Semaphore: count remembered. Spinlock: only for very short waits on multiprocessors.

Formulas

Critical-section requirements
mutual exclusion + progress + bounded waiting
Binary semaphore
init 1; P(S) before the critical section, V(S) after
Bounded buffer
empty = n, full = 0, mutex = 1
Counting semaphore value
initial value − (P completed) + (V completed) ≥ 0; if negative in the textbook form, |value| = number of blocked processes
Peterson entry
flag[i] = true; turn = j; while (flag[j] && turn == j);

What GATE asks

  • ★★★Does this solution guarantee mutual exclusion / progress / bounded waiting?. Try the bad interleaving: both set flags, or both check before either sets.
  • ★★★Semaphore code: possible outputs or final value. Track the semaphore value, which processes block, and which orders of P and V are possible.
  • ★★★Producer-consumer / readers-writers / philosophers variants. Find the missing or misplaced P or V, or the deadlock caused by the wrong order.
  • ★★★Minimum or maximum value of a shared variable. Interleave the load, add and store steps to find the extreme result.

Traps

Spinlock vs mutex: a spinlock never sleeps, so on a single CPU it wastes the whole quantum.
Test-and-set gives mutual exclusion but not bounded waiting on its own.
A semaphore signal is remembered; a condition-variable signal with no waiter is lost.
Do not confuse deadlock (nobody can proceed) with starvation (someone is unlucky forever).

4. 🚧 Deadlock

High yield ●●●9 PYQs →

A steady source of marks: Banker's safe sequence, minimum resources for deadlock freedom, and cycle questions on resource allocation graphs.

  • Deadlock conditions and handling. Deadlock needs all four Coffman conditions: mutual exclusion, hold and wait, no preemption, circular wait. Breaking any one prevents it. Strategies: prevention (negate a condition: request all resources at once, allow preemption, impose a global ordering on resources), avoidance (needs advance information: Banker's algorithm), detection and recovery, or ignore it (the ostrich approach used by most general-purpose systems).
    → Four conditions all needed. Ordering breaks circular wait; all-at-once breaks hold-and-wait.
  • Resource allocation graph. Vertices: processes (circles) and resources (squares with a dot per instance). Request edge P → R, assignment edge R → P. With one instance per resource, a cycle is both necessary and sufficient for deadlock. With several instances, a cycle is only necessary: another process outside the cycle may release an instance and break it. No cycle always means no deadlock.
    → Single instance: cycle ⇔ deadlock. Several instances: cycle is only necessary. No cycle: never deadlock.
  • Prevention and avoidance: safe states and Banker's algorithm. A state is safe if some order of finishing exists in which every process can obtain its maximum need. Safe ⇒ no deadlock; unsafe does not mean deadlocked, only that deadlock is possible. Need = Max − Allocation. Safety algorithm: Work = Available; repeatedly pick a process with Need ≤ Work, let it finish and add its Allocation to Work. A request is granted only if Request ≤ Need, Request ≤ Available, and the state after a trial grant is still safe.
    → Need = Max − Alloc. Safe ⇒ no deadlock; unsafe ⇏ deadlock. Banker's needs maximum claims in advance.
  • Detection, recovery and the minimum-resources formula. Detection uses the same reduction as Banker's but with each process's current Request instead of Need; processes that can never finish are deadlocked. Recovery: kill all deadlocked processes, kill one at a time, or preempt resources and roll back. Classic counting question: n processes each needing at most m instances of one resource type; deadlock cannot occur if the number of resources R ≥ n(m − 1) + 1. With different needs mᵢ: R ≥ Σ(mᵢ − 1) + 1. The worst case gives everyone one fewer than they need.
    → R ≥ n(m − 1) + 1 for one resource type. Detection = Banker's with Request instead of Need.

Formulas

Coffman conditions
mutual exclusion, hold and wait, no preemption, circular wait
Need matrix
Need = Max − Allocation
Safety test
find Pᵢ with Needᵢ ≤ Work; Work += Allocationᵢ; repeat until all finish or none fits
Deadlock-free with n processes needing ≤ m each
R ≥ n(m − 1) + 1
Different needs mᵢ
R ≥ Σ (mᵢ − 1) + 1 = Σ mᵢ − n + 1
Max processes for given R, each needing m
n ≤ (R − 1) / (m − 1)

What GATE asks

  • ★★★Is the system in a safe state / how many safe sequences. Compute Need, run the safety test; count distinct valid orders if asked.
  • ★★★Minimum number of resources to avoid deadlock. R = n(m − 1) + 1, or the generalisation with different maximums.
  • ★★★Is there a deadlock in this allocation graph. Single instance: look for a cycle. Multiple instances: run detection.
  • ★★★Statements about prevention vs avoidance vs detection. Which condition does an ordering or an all-at-once request break?

Traps

Unsafe ≠ deadlock. A system in an unsafe state may still finish if processes happen to release resources early.
A cycle with several instances does not prove deadlock.
For the formula R = n(m − 1) + 1 the resources must all be of one type.
Banker's algorithm needs each process's maximum claim in advance: detection does not.

5. 🧱 Memory Management

High yield ●●●11 PYQs →

Paging arithmetic (page table size, bits in an address, TLB access time) is among the most predictable numerical questions in OS.

  • Address binding and relocation. A program uses logical (virtual) addresses; the hardware (the MMU) turns them into physical addresses. Binding can happen at compile time (absolute code), load time (relocatable) or run time (needs hardware: a relocation (base) register plus a limit register for protection). The logical address space is what the program sees; the physical address space is real RAM. Dynamic loading and linking bring in routines only when needed.
    → Physical = base + logical, after checking logical < limit.
  • Contiguous allocation and fragmentation. Each process gets one contiguous block. Placement policies for a request: first fit (first hole big enough), best fit (smallest hole big enough; leaves tiny useless holes, slow), worst fit (largest hole), next fit (first fit resuming from the last placement). External fragmentation: enough total free memory but no single hole large enough; cured by compaction (needs run-time binding) or by paging. Internal fragmentation: waste inside an allocated block, e.g. fixed partitions or the last page of a process.
    → External fragmentation: variable partitions. Internal: fixed partitions and pages. Best fit is not always best.
  • Paging and address translation. Physical memory is split into frames, logical memory into pages of the same size. A logical address = page number | offset. The page table maps page → frame; physical address = frame × page size + offset. If the address has L bits and the page size is 2^d, there are L − d page-number bits and d offset bits. Paging removes external fragmentation but leaves internal fragmentation (on average half a page per process).
    → offset bits = log₂(page size); page bits = address bits − offset bits; PA = frame × size + offset.
  • Page table size, multilevel and inverted tables. Page table size = number of pages × entry size = (virtual size ÷ page size) × entry size. A single table can be huge, so a multilevel table pages the page table itself: the page number is split into fields, one per level, and each table is ideally one page long (entries per page = page size ÷ entry size). Only the levels that are used need to exist. An inverted page table has one entry per physical frame (size = frames × entry size) and is searched by hashing (pid, page).
    → Flat size = pages × entry; multilevel levels make each table fit a page; inverted size = frames × entry.
  • TLB and effective access time. The TLB is a small associative cache of recent page-table entries. On a hit the translation costs one TLB lookup; on a miss the page table (in memory) must be walked. For a one-level table: EMAT = h(t + m) + (1 − h)(t + m + m), i.e. a miss costs one extra memory access to fetch the PTE. With k page-table levels a miss costs k extra accesses. Context switches flush the TLB unless it has address-space ids.
    → EMAT = h(t + m) + (1 − h)(t + (k + 1)m). The TLB is always probed first.
  • Segmentation and segmented paging. Segmentation splits a program into logical units (code, stack, data) of variable size. A logical address is (segment number, offset); the segment table holds base and limit; the offset is checked against the limit (else a trap). It follows the programmer's view and eases sharing and protection, but suffers external fragmentation. Segmented paging (Intel style) pages each segment, combining the two: no external fragmentation and logical sharing.
    → Segmentation: variable size, base + limit, external fragmentation. Paging: fixed size, internal fragmentation.

Formulas

Address split
virtual address bits = page number bits + offset bits; offset bits = log₂(page size)
Number of pages / frames
virtual size ÷ page size; physical size ÷ page size
Page table size
(number of pages) × (entry size)
Entries per page (multilevel)
page size ÷ entry size, so a level uses log₂(that) bits
Inverted page table size
(number of frames) × (entry size)
EMAT, 1-level paging with TLB
h(t + m) + (1 − h)(t + 2m)
EMAT, k-level paging with TLB
h(t + m) + (1 − h)(t + (k + 1)m)
Average internal fragmentation
≈ page size / 2 per process

What GATE asks

  • ★★★Page table size or number of bits in the page-table entry. Pages × entry size, where an entry holds frame number plus valid, dirty and protection bits.
  • ★★★Multilevel paging: bits per level / number of levels. Make each table fit one page: entries per page gives the bits for that level.
  • ★★★Effective access time with TLB (and page-fault terms). Weight the hit and miss paths; count memory accesses for the walk.
  • ★★★First/best/worst fit placement and fragmentation. Place each request in order; best fit may leave small unusable holes.

Traps

The page-table entry has more than the frame number: valid, reference, dirty and protection bits.
In EMAT problems say whether the TLB lookup time is added on a hit and on a miss: both.
The offset bits depend on the page size only, not on the memory size.
Internal fragmentation belongs to paging and fixed partitions; external to segmentation and variable partitions.

6. 💾 Virtual Memory

High yield ●●●9 PYQs →

Page replacement traces (count the faults for FIFO, LRU, Optimal) and Belady's anomaly are asked nearly every year.

  • Demand paging and page faults. With demand paging a page is brought in only when first referenced. Each page-table entry has a valid bit. On a reference to an invalid page the hardware traps (page fault); the OS finds a free frame (or evicts a victim), reads the page from disk, updates the table and restarts the instruction. A page fault is far more expensive than a memory access (milliseconds against nanoseconds), so the fault rate must be tiny. Copy-on-write and memory-mapped files use the same mechanism.
    → Page fault: trap, find frame, read page, update table, restart instruction.
  • Page replacement: FIFO, LRU and Optimal. When no frame is free, a policy picks the victim. FIFO: evict the page that has been in memory longest. LRU: evict the page not used for the longest time (good approximation of the future, costly to implement exactly; hardware uses reference bits, the clock / second-chance algorithm). Optimal (OPT): evict the page used farthest in the future: the minimum possible faults, but impossible in practice, so it is the benchmark. To count faults draw one column per reference and mark hits and faults.
    → OPT ≤ LRU ≤ FIFO usually. Faults ≥ number of distinct pages. LRU and OPT are stack algorithms.
  • Belady's anomaly and stack algorithms. Belady's anomaly: with FIFO, giving a process more frames can cause more page faults. The classic string 1 2 3 4 1 2 5 1 2 3 4 5 gives 9 faults with 3 frames and 10 with 4. Stack algorithms (LRU and OPT) have the inclusion property: the set of pages in n frames is always a subset of the set in n + 1 frames, so they never show the anomaly. More frames never hurt LRU or OPT.
    → FIFO can show the anomaly (9 → 10 on 1 2 3 4 1 2 5 1 2 3 4 5); LRU and OPT never.
  • Effective access time with page faults. With page-fault rate p, memory access time m and page-fault service time s: EAT = (1 − p)·m + p·s. Because s is about a million times m, even p = 0.001 makes the system dramatically slower, so exam questions ask what p keeps the slowdown within a given percentage. If a fraction of victims are dirty, the service time includes writing the victim back: s = read time + (fraction dirty) × write time. Combine with TLB and page-table terms when the question says so.
    → EAT = (1 − p)m + ps. Watch the units (ms vs ns) and add the write-back for dirty victims.
  • Thrashing, working set and frame allocation. Thrashing: processes do not have enough frames for their working pages, so they fault constantly and the CPU sits idle, which tempts the scheduler to admit more processes and makes it worse. The working-set model keeps the pages used in the last Δ references; the sum of working-set sizes must not exceed the number of frames. Cures: lower the degree of multiprogramming, page-fault-frequency control. Allocation: equal, proportional to size, or priority-based; local replacement (own frames) limits interference, global replacement can steal frames from others.
    → Thrashing = constant faulting. Remedy: fewer processes, working-set or PFF control.

Formulas

Effective access time
EAT = (1 − p)·m + p·(page-fault service time)
Fault service with dirty victims
s = read + (fraction dirty) × write + overhead
Belady's string
1 2 3 4 1 2 5 1 2 3 4 5: FIFO has 9 faults with 3 frames, 10 with 4
Hit ratio
hits / references = 1 − faults / references
Working-set demand
D = Σ WSSᵢ; thrashing if D > number of frames
Page faults lower bound
at least the number of distinct pages referenced (compulsory misses)

What GATE asks

  • ★★★Number of page faults for a reference string (FIFO / LRU / OPT). Fill a frame table column by column; for OPT look ahead for the farthest next use.
  • ★★★Belady's anomaly: which policy can show it. FIFO yes; LRU and OPT no (stack algorithms).
  • ★★★Effective access time with page faults. EAT = (1 − p)m + p·s; solve for p to meet a slowdown target.
  • ★★★Thrashing and working-set statements. Which actions reduce thrashing (fewer processes) and which worsen it (more processes).

Traps

In OPT, ties (pages never used again) can be broken arbitrarily, but the fault count is the same.
LRU is a stack algorithm, so adding frames never increases its faults.
Count hits as hits: the initial loading of an empty frame is still a fault.
The dirty-bit term is only added when the victim is dirty: read the fraction in the question.

7. 🗂️ File Systems

Medium ●●5 PYQs →

Inode and allocation-method arithmetic (maximum file size, FAT size) is a regular numerical question.

  • Files, directories and access methods. A file is a named sequence of bytes with attributes (name, size, type, protection, times). Operations: create, open, read, write, seek, close. Access: sequential, direct (random) or indexed. Directories: single-level, two-level, tree (the usual one), acyclic graph (links), general graph. A hard link is another directory entry pointing to the same inode (the file survives until the last link is removed, same file system only); a soft (symbolic) link stores a path name and can dangle. The open-file tables are per process and system-wide.
    → Hard link: same inode, same file system. Soft link: path, may dangle, may cross file systems.
  • Allocation: contiguous, linked, FAT and indexed. Contiguous: a start block and a length; fast sequential and direct access, but external fragmentation and growth is hard. Linked: each block holds a pointer to the next; no fragmentation but direct access means following the chain, and a pointer lost means the rest lost. FAT: the pointers are kept in a table in memory (one entry per block), which makes random access fast. Indexed: an index block lists the file's blocks; supports direct access; large files need multi-level indexes. FAT size = number of blocks × entry size.
    → Contiguous: fast but fragments. Linked: slow direct access. FAT and indexed: direct access without fragmentation.
  • UNIX inode and maximum file size. An inode holds the file's attributes and block pointers: typically d direct pointers, one single-indirect, one double-indirect and one triple-indirect pointer. With block size B and pointer size P a block holds B / P pointers. Maximum file size = (d + (B/P) + (B/P)² + (B/P)³) × B. The directory entry holds only the name and inode number, so renaming never copies the data. Small files use only the direct pointers (fast); the blocks reached through indirection cost extra disk accesses.
    → Pointers per block = B/P. Max size = (d + B/P + (B/P)² + (B/P)³) × B.
  • Free-space management and file-system structure. Free blocks can be tracked with a bit map (one bit per block; easy to find a run of blocks; size = number of blocks / 8 bytes), a linked list of free blocks, grouping (a free block stores the addresses of n others) or counting (start address plus run length). A disk is divided into partitions, mounted into the directory tree. Layered design: application → logical file system → file-organisation module → basic file system → I/O control → devices. Journaling logs metadata changes first so a crash can be repaired quickly.
    → Bit map = blocks / 8 bytes. Journaling protects metadata.

Formulas

Pointers per block
B / P (block size ÷ pointer size)
Maximum file size (inode)
(d + B/P + (B/P)² + (B/P)³) × B with d direct pointers
FAT size
(number of blocks on the disk) × (entry size)
Bit-map size
number of blocks bits = blocks / 8 bytes
Blocks for a file of S bytes
⌈S / B⌉
Entry bits needed
at least ⌈log₂(number of blocks)⌉ bits per pointer

What GATE asks

  • ★★★Maximum file size with direct and indirect pointers. Compute B/P, then add each level; be careful with how many direct pointers.
  • ★★★How many disk accesses to reach byte k of a file. Count the indirect blocks that must be read before the data block.
  • ★★★Compare allocation methods. Which has external fragmentation, which supports direct access, which is robust.
  • ★★★Hard link versus soft link. Link counts, deleting the original, crossing file systems.

Traps

Linked allocation has no external fragmentation but slow direct access and wasted pointer space in every block.
A hard link cannot cross file systems; a soft link can, and may dangle.
The number of pointers in a block uses the pointer size, not the block-number size you want to address.
Directory entries do not hold data: rename and move inside one file system are cheap.

8. 💿 Disk Scheduling & I/O

Medium ●●12 PYQs →

Disk access time and head-movement questions (FCFS, SSTF, SCAN, C-SCAN) are quick marks if the definitions are clear.

  • Disk structure and access time. A disk has platters, tracks (cylinders when stacked), sectors. Time to access a block = seek time (move the arm to the cylinder) + rotational latency (wait for the sector, on average half a rotation = 30/RPM seconds) + transfer time (data size ÷ transfer rate, or fraction of a track × rotation time). Seek time dominates, so the OS reorders requests. SSDs have no seek or rotation but have limited write cycles and erase blocks.
    → Latency = ½ rotation. Transfer = fraction of a track × rotation time.
  • Disk scheduling algorithms. FCFS: serve in arrival order, fair but long movement. SSTF: nearest request next, good throughput but can starve far requests. SCAN (elevator): sweep in one direction to the disk end, then reverse. LOOK: like SCAN but turn around at the last request. C-SCAN / C-LOOK: serve in one direction only, then jump back to the start; gives more uniform waiting time. Total head movement is the sum of |difference| between consecutive cylinders; read the question for whether the return jump counts.
    → SCAN goes to the disk end, LOOK to the last request. SSTF can starve. C-versions give uniform waiting.
  • I/O transfer: polling, interrupts and DMA. Programmed I/O (polling): the CPU repeatedly checks the device status: simple but wastes CPU. Interrupt-driven I/O: the device signals when ready; the CPU does other work but takes an interrupt per byte or word. DMA: a controller moves a whole block between device and memory without the CPU, interrupting once at the end; it steals bus cycles (cycle stealing). Cycle-stealing percentage = DMA time ÷ total time. Use DMA for big, fast transfers and interrupts for slow character devices.
    → DMA: one interrupt per block, cycle stealing. Polling wastes CPU; interrupts cost per word.
  • Buffering, spooling, device drivers and RAID. Buffering smooths speed differences; caching keeps a copy of data; spooling queues output for a device that serves one job at a time (printer). The kernel I/O subsystem hides devices behind device drivers. RAID: 0 stripes (speed, no redundancy), 1 mirrors (half the capacity), 5 stripes with distributed parity (survives one disk failure, capacity (n − 1) disks). Usable capacity: RAID 0 = n, RAID 1 = n/2, RAID 5 = n − 1 disks.
    → Buffer smooths, cache reuses, spool queues. RAID 5: n − 1 usable, survives one failure.

Formulas

Disk access time
T = seek + rotational latency + transfer
Average rotational latency
½ × (60 / RPM) seconds = 30 / RPM s
Transfer time
bytes ÷ transfer rate, or (bytes / track size) × rotation time
Total head movement
Σ |cᵢ − cᵢ₋₁| over the service order
RAID capacity (n disks)
RAID 0: n; RAID 1: n/2; RAID 5: n − 1
DMA cycle stealing
fraction of time = DMA transfer time ÷ total time

What GATE asks

  • ★★★Total head movement for a request queue. Write the service order and add up the cylinder differences; for SCAN include the trip to the end.
  • ★★★Disk access time for a block or file. Add seek, half-rotation latency and transfer; use the stated RPM and sector size.
  • ★★★Compare polling, interrupts and DMA. CPU overhead, bus use and when each is appropriate.
  • ★★★Which scheduler starves requests. SSTF (and SCAN variants less so); C-SCAN gives uniform waiting.

Traps

SCAN goes to the physical end of the disk; LOOK stops at the last request.
Average rotational latency is half a rotation, not a full one.
Check units: transfer rate in MB/s against sizes in KB, and RPM against seconds.
DMA still uses the memory bus: it steals cycles from the CPU even though it does not interrupt per word.