A file system is the operating system's answer to a simple-sounding question: where on the disk does each file's data actually live, and how do we find it again quickly? Disk scheduling is the follow-up: when many read and write requests are queued, in what order should the head service them so the disk arm travels least? Both are mechanical once you know the rules, and both are steady exam scorers. The two meet in the same place: how the file system scatters a file's blocks across the disk decides how far the arm has to travel to read it back.
File allocation methods
The file system must record which disk blocks belong to each file. There are three classic strategies.
Contiguous allocation stores a file in consecutive blocks. Access is fast and simple, and both sequential and direct access are easy, but files cannot grow easily and the disk suffers external fragmentation, the same scattered-holes problem memory allocation has.
Linked allocation stores a file as a chain of blocks, each holding a pointer to the next. Files grow freely and there is no external fragmentation, but direct access is slow because you must follow the chain, and a single corrupted pointer loses the rest of the file.
Indexed allocation gives each file an index block listing all its data-block addresses. Direct access is fast and there is no external fragmentation, at the cost of space for the index block, which for very large files may itself need multiple levels.
The Unix inode is the well-known real-world design: a mostly indexed scheme with direct block pointers plus single, double and triple indirect blocks to handle files of any size. The block-by-block layout of each method is walked through in the file management learn module.
Directory structures and free-space management
A directory maps human file names to their on-disk metadata. The structures range from a single flat directory, simple but with name clashes, to the two-level directory that gives every user a private space, to the tree-structured directory almost everyone uses, to acyclic-graph directories that allow shared files through links.
The system also tracks which blocks are free. The two standard methods are a bit vector, one bit per block set to free or used, which makes finding contiguous free runs easy and is compact, and a linked list of free blocks, which wastes no extra structure but makes contiguous searches slow. Two refinements make allocating consecutive blocks cheaper: grouping, where the first free block stores the addresses of the next several free blocks, and counting, which stores a starting block plus a run length instead of listing every free block one by one.
Disk geometry and seek time
A hard disk stores data on concentric tracks, each divided into sectors, with the same track position across platters forming a cylinder. To read a block the disk does three things: seek time moves the arm to the right cylinder, rotational latency waits for the sector to spin under the head, and transfer time reads the data. Seek time dominates and is the part disk scheduling can reduce, by choosing the order in which to service pending cylinder requests so the arm travels less. Rotational latency is usually taken as the average half-rotation time, and the sum of seek, latency and transfer is the disk access time that questions ask you to minimise.
Disk scheduling: a worked comparison
Take a request queue of cylinders and a disk that spans cylinders 0 to 199, with the head starting at cylinder 53. The pending requests are:
98, 183, 37, 122, 14, 124, 65, 67
Assume, where direction matters, that the head first moves toward higher-numbered cylinders. Each algorithm picks a different service order, and each order costs a different amount of arm travel.
FCFS services requests in arrival order: 53 to 98 to 183 to 37 to 122 to 14 to 124 to 65 to 67. The jumps are 45, 85, 146, 85, 108, 110, 59 and 2, which add to 640 cylinders. Simple and fair, but the arm swings wildly across the platter.
SSTF, shortest seek time first, always services the nearest pending request: 53, 65, 67, 37, 14, 98, 122, 124, 183. The hops are 12, 2, 30, 23, 84, 24, 2 and 59, totalling 236 cylinders, far less, but it can starve requests far from the head.
SCAN, the elevator algorithm, moves in one direction servicing everything, reaches the end, then reverses: 65, 67, 98, 122, 124, 183, on to cylinder 199, then back down for 37 and 14. That is 53 up to 199, a travel of 146, then 199 down to 14, a travel of 185, so 331 cylinders in all.
C-SCAN sweeps one way to the end, jumps back to the start, and sweeps the same direction again, which spreads waiting more evenly: up to 199, back to 0, then up through 14 to 37. Counting the return jump, that is 146 plus 199 plus 37, or 382 cylinders; some texts leave the return jump out of the total, so state your assumption before you add.
Putting the totals together:
Algorithm | Total head movement |
|---|---|
FCFS | 640 |
SSTF | 236 |
SCAN | 331 |
C-SCAN | 382 |
SSTF wins on raw movement here, SCAN and C-SCAN give fairer waiting, and FCFS is the baseline everything improves on.
How this is tested in GATE
Our Operating Systems question set runs to close to 2,000 questions, of which over 150 sit on file management and more than 90 on disk scheduling. The numerical pattern barely varies: you are handed a request queue and a starting head position and asked for the total head movement, or the servicing order, under a named algorithm. Careful arithmetic on the gaps is the whole game.
Read the algorithm name before you start adding. LOOK and C-LOOK behave like SCAN and C-SCAN but turn at the last pending request instead of at the disk edge, so on this same queue LOOK turns at 183 rather than 199 and costs 130 plus 169, which is 299 cylinders, not 331. Conceptual questions ask which allocation method allows fast direct access, why linked allocation is poor for it, or which scheduling algorithm can starve a request. Both kinds are drilled with full solutions in our file systems allocation MCQs and disk scheduling MCQs.
The short version
For files, know the three allocation methods and what each trades away, plus how directories and free-space maps work. For the disk, remember that seek time dominates and that scheduling reorders requests to shrink arm travel. Hand-compute total head movement for FCFS, SSTF, SCAN and C-SCAN on one queue, being explicit about direction, and the topic is yours.
For the whole GATE CS syllabus in order, GATE Guidance by Sanchit Sir sequences OS with everything else, and more explainers sit on the CS Fundamentals category.
