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. Let us take the file system first, then the moving arm.
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.
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 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 you should know are 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, both aimed at making allocation of consecutive blocks cheaper.
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. Here is how each algorithm services the queue and the total head movement it costs.
FCFS services requests in arrival order: 53 to 98 to 183 to 37 to 122 to 14 to 124 to 65 to 67. Adding the absolute jumps gives a total head movement of 640 cylinders. Simple and fair, but the arm swings wildly.
SSTF, shortest seek time first, always services the nearest pending request: 53, 65, 67, 37, 14, 98, 122, 124, 183. That totals 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 for 37 and 14. The total is 146 plus 185, which is 331 cylinders.
C-SCAN sweeps one way to the end, jumps back to the start, and sweeps the same direction again, giving more uniform waiting: up to 199, back to 0, then up to 37. Counting the full return sweep, that is 146 plus 199 plus 37, or 382 cylinders; some texts do not count the return jump, so state your assumption.
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
File Management carries over 150 published questions in the KnowledgeGate bank and Disc Scheduling over 90 more, inside the close-to-2,000 Operating Systems total. GATE almost always gives you a request queue with a starting head position and asks for the total head movement or the servicing order under a named algorithm, so the worked procedure above is the whole game. Conceptual questions ask which allocation method allows fast direct access, why linked allocation is poor for it, or which scheduling algorithm can cause starvation. Learn to compute head movement carefully, watching the direction assumption, and these become quick marks.
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.
Work the arm-movement problems on the file management learn module, then test yourself with our file systems allocation MCQs and disk scheduling MCQs.
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.
