GATE CS & IT Engineering Operating System Syllabus

What is the disk data transfer rate in terms of bytes per track and RPM?

$$\text{Transfer Rate} = (\text{bytes per track}) \times \frac{r}{60} \text{ bytes/second}$$ where $r$ is the rotation speed in RPM (number of tracks read per second times track capacity).

What is internal fragmentation and in which memory allocation scheme does it occur?

Internal fragmentation is the unused space inside an allocated block/partition because the allocation is larger than the requested memory. It occurs in fixed-size partitioning and in paging (within the last page).

What is external fragmentation and which allocation scheme suffers from it?

External fragmentation is free memory split into small non-contiguous holes that collectively are large enough but individually too small to satisfy a request. It occurs in variable-size partitioning and pure segmentation.

Compare First-Fit, Best-Fit, and Worst-Fit memory allocation strategies.

First-Fit allocates the first hole large enough (fast). Best-Fit allocates the smallest hole that fits (least leftover but more external fragmentation and slow). Worst-Fit allocates the largest hole (leaves large usable remainder but wastes big holes).

In paging, how is a logical address split, and what does each part index?

A logical address is split into a page number $p$ and a page offset $d$. $p$ indexes the page table to find the frame number; $d$ is the offset within the frame. If logical address space is $2^m$ and page size is $2^n$, then $p$ has $m-n$ bits and $d$ has $n$ bits.

What is the purpose of a Translation Lookaside Buffer (TLB)?

The TLB is a small, fast associative cache that stores recent page-number-to-frame-number translations, avoiding a slow page-table lookup in main memory for each address translation.

Give the formula for Effective Memory Access Time (EMAT) with a TLB of hit ratio $h$, TLB access time $t$, and memory access time $m$.

$$\text{EMAT} = h(t + m) + (1-h)(t + 2m)$$ assuming the page table is in memory (one extra access on a TLB miss).

What is the key difference between paging and segmentation?

Paging divides memory into fixed-size pages/frames (transparent to the programmer, causes internal fragmentation). Segmentation divides memory into variable-size logical units like code, stack, data (visible to the programmer, causes external fragmentation).

How does a segmentation address translation use the segment table?

A logical address is $\langle$segment number $s$, offset $d\rangle$. The segment table gives a base and a limit for segment $s$. If $d < \text{limit}$, the physical address is base $+ d$; otherwise a trap (addressing error) occurs.

What is the difference between logical (virtual) and physical address space?

A logical address is generated by the CPU and seen by the process; a physical address is the actual location in main memory. The Memory Management Unit (MMU) maps logical to physical addresses at runtime.

What is demand paging in virtual memory?

Demand paging loads a page into memory only when it is referenced (a page fault occurs), rather than loading the entire process upfront. This reduces memory use and startup I/O via lazy loading.

Give the formula for the Effective Access Time (EAT) under demand paging with page-fault rate $p$, memory access time $m$, and page-fault service time $f$.

$$\text{EAT} = (1-p)\,m + p\,f$$ where $p$ is the probability of a page fault and $f$ includes the time to service the fault (swap in the page).

What is Belady's Anomaly and which page-replacement algorithm exhibits it?

Belady's Anomaly is the counterintuitive phenomenon where increasing the number of page frames increases the number of page faults. It can occur with the FIFO page-replacement algorithm.

How does the Optimal (OPT/MIN) page-replacement algorithm work, and why is it not practical?

OPT replaces the page that will not be used for the longest time in the future, giving the minimum possible page faults. It is impractical because it requires future knowledge of the reference string; it is used only as a benchmark.

Describe the LRU (Least Recently Used) page-replacement algorithm.

LRU replaces the page that has not been used for the longest time in the past, approximating OPT using past behavior. It can be implemented with counters/timestamps or a stack and does not suffer from Belady's Anomaly (it is a stack algorithm).

What is thrashing in virtual memory, and what causes it?

Thrashing is when a process spends more time paging (swapping pages in and out) than executing, due to having too few frames to hold its working set. A high degree of multiprogramming causes it; it can be controlled using the working-set model or page-fault frequency.

State the principle of locality of reference and its two types.

Programs tend to reference a small, clustered set of pages over a short time. Temporal locality: a referenced item is likely referenced again soon. Spatial locality: items near a referenced item are likely referenced soon.

What is the working set of a process, and how is it defined with a window $\Delta$?

The working set $W(t,\Delta)$ is the set of distinct pages referenced in the most recent $\Delta$ memory references. Its size approximates the locality; if total working-set demand exceeds available frames, thrashing occurs.

For a page reference string with FIFO and 3 frames, what data structure determines the victim page?

FIFO uses a queue: the page that has been in memory the longest (the one at the front of the queue / first loaded) is selected as the victim, regardless of usage.

What is the difference between a page fault and a segmentation fault?

A page fault is a normal event where a referenced valid page is not in memory and must be brought in from disk. A segmentation fault is an illegal memory access (e.g., offset beyond a segment's limit or invalid address) that the OS treats as an error.

How does the second-chance (clock) page-replacement algorithm work?

It is FIFO with a reference bit. When a page is selected for replacement, if its reference bit is 1, it is given a second chance (bit cleared to 0, moved to the rear); if 0, it is replaced. The pages are scanned cyclically like a clock.

In an inverted page table, what is stored and what is its main advantage?

An inverted page table has one entry per physical frame, storing the (process-id, page-number) pair occupying that frame. Its advantage is that table size depends on physical memory, not on each process's virtual address space, saving memory.

What are the three common methods of allocating disk blocks to files?

Contiguous allocation (blocks are consecutive), Linked allocation (each block points to the next), and Indexed allocation (an index block holds pointers to all of the file's blocks).

What are the advantages and disadvantages of contiguous file allocation?

Advantages: simple, supports fast sequential and direct (random) access with minimal seeking. Disadvantages: suffers external fragmentation and difficulty in growing files / finding space for new files.

What is the main disadvantage of linked file allocation?

Linked allocation supports only efficient sequential access; direct access is slow because reaching block $i$ requires following $i$ pointers. It also wastes space for pointers and is vulnerable if a pointer is corrupted.

What is an i-node (index node) in a Unix file system, and what does it contain?

An i-node is a data structure storing a file's metadata: permissions, owner, size, timestamps, link count, and pointers to the file's data blocks (direct, single, double, and triple indirect pointers). It does not store the file name.

In a Unix-style inode with direct and indirect block pointers, how is large-file addressing achieved?

The inode holds some direct block pointers plus single, double, and triple indirect pointers. Each indirection level points to a block of pointers, allowing the maximum file size to scale roughly as (direct $+ k + k^2 + k^3$) blocks, where $k$ is the number of pointers per block.

What is the difference between a hard link and a symbolic (soft) link?

A hard link is another directory entry pointing to the same inode (same file, shares the inode and increments link count). A symbolic link is a separate file containing the pathname of the target; it can cross file systems but breaks if the target is deleted.

How does a File Allocation Table (FAT) file system track file blocks?

FAT keeps a table at the start of the volume with one entry per disk block. Each entry holds the index of the next block in the file (forming a chain), with special markers for end-of-file and free blocks, improving random access over plain linked allocation.

What are the two main methods of free-space management on disk?

Bit vector (bitmap): one bit per block indicating free/allocated, simple and allows finding contiguous runs but needs the whole map. Linked list (free list): free blocks are chained together; space-efficient but slow to traverse for contiguous space.

Compute the maximum file size for a Unix inode with 10 direct, 1 single, 1 double, and 1 triple indirect pointer, with block size 1 KB and 4-byte block pointers.

Pointers per block $k = 1024/4 = 256$. Max size $= (10 + 256 + 256^{2} + 256^{3})$ blocks $\times 1\text{ KB} = (10 + 256 + 65536 + 16777216)\,\text{KB} \approx 16\,\text{GB}$.