Questions
1–2 questions per university paper
Difficulty
Medium
Importance
High yield for Operating Systems theory papers
Overview
File systems serve as the logical layer that organizes, stores, and retrieves data on physical storage media like HDDs and SSDs. Understanding this topic is critical for exams as it bridges high-level user abstraction with low-level hardware constraints. Aspirants must master how data is mapped to sectors and how the operating system optimizes disk access time.
File Allocation Methods
Allocation methods define how files are stored within disk blocks, directly impacting performance and external fragmentation. You must distinguish between the efficiency of contiguous, linked, and indexed schemes for both sequential and direct file access.
- Contiguous allocation: Best for sequential access, but suffers from severe external fragmentation.
- Linked allocation: Solves external fragmentation but does not support efficient random access.
- Indexed allocation: Uses an index block to store pointers to data blocks, supporting both random and sequential access.
- Indexed approach causes overhead due to the index block requirement.
- Linked list approach is susceptible to pointer failure, leading to data loss.
Directory Structures
Directory structures provide a mapping mechanism between filenames and the corresponding file blocks. They are organized logically to manage large numbers of files and enable hierarchical navigation in operating systems.
- Single-level directory: Simple but suffers from naming collisions.
- Two-level directory: Separates files per user; prevents naming conflicts between different users.
- Tree-structured directory: The most common structure, allowing arbitrary nesting of directories.
- Acyclic graph directory: Enables file sharing by allowing directories to point to the same file.
- General graph directory: Allows cycles, requiring complex cycle detection algorithms.
Disk Scheduling
Disk scheduling algorithms are designed to minimize the total seek time required to move the read/write head across a disk. Examiners often ask for calculations of total head movement based on a specific sequence of requested tracks.
- FCFS (First Come First Served): Simplest, but may lead to high head movement.
- SSTF (Shortest Seek Time First): Minimizes seek time but can cause starvation of distant requests.
- SCAN (Elevator Algorithm): Moves in one direction to the end, then reverses; ensures better fairness than SSTF.
- C-SCAN: Only services requests in one direction and returns immediately to the start, providing more uniform wait times.
- LOOK/C-LOOK: Improvements on SCAN that do not go all the way to the disk edge.
Formula Sheet
Total Seek Time = Sum of absolute differences between consecutive track positions.
Average Wait Time = Total Wait Time / Number of Requests.
Exam Tip
Always draw the disk head movement diagram when solving scheduling problems; it prevents calculation errors and secures step-marks.
Common Mistakes
- Confusing internal fragmentation with external fragmentation when discussing contiguous allocation.
- Neglecting to calculate the return path movement in C-SCAN or C-LOOK scheduling problems.
- Assuming that linked allocation allows random access with O(1) time complexity.
More Revision Notes
Ready to test yourself?
Play topic-wise File Systems questions in Aspirant Arcade — gamified MCQ practice.
Download Free