GATE CS & IT Engineering Operating System Flashcards

24 sample cards from the Operating System deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. 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).

2. 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.

3. 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.

4. 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.

5. 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).

6. 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.

7. 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.

8. 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).

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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).

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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}$.

What this deck covers

Operating System flashcards FAQ