Disk scheduling interview questions, with answers
On a hard disk, moving the read-write head is the slowest part of every request, so the order in which requests are served makes a large difference. Interviews ask for the algorithms and usually for a head-movement calculation, and increasingly for how SSDs and RAID change the picture.
The answers below cover disk access time, FCFS and SSTF, SCAN and LOOK, a worked head-movement example, why SSDs differ, and RAID levels. Then take the free Operating Systems diagnostic — ten questions across every OS topic in the bank — to see which of these you can explain but not yet apply.
The questions, with answers
1.What makes up the time to access a disk block?
In short: Seek time to move the head to the track, rotational latency for the sector to arrive, and transfer time to read it.
A hard disk request costs three parts. Seek time moves the arm to the right cylinder and is usually the largest, several milliseconds on average. Rotational latency is the wait for the sector to rotate under the head: on average half a revolution, about 4.17 ms for a 7200 RPM disk. Transfer time reads the data and is small for a single block. Disk scheduling reduces total seek time by reordering pending requests, while file systems reduce both seek and rotation by placing related blocks close together.
2.How do FCFS and SSTF disk scheduling differ?
In short: FCFS serves requests in arrival order; SSTF always serves the pending request nearest the current head position.
First-come, first-served handles requests in the order they arrive, which is fair and simple but can swing the head back and forth across the disk, producing large total seek distances. Shortest seek time first picks, at each step, the pending request closest to the head, which greatly reduces total movement compared with FCFS in most workloads. SSTF is a greedy choice, though: it does not always give the smallest possible total movement, and the order it produces depends on where the head happens to be when requests arrive.
3.How do the SCAN and LOOK algorithms work?
In short: SCAN sweeps the head to one end of the disk and back, serving requests on the way; LOOK reverses at the last request instead of the end.
SCAN, the elevator algorithm, moves the head in one direction serving every request it passes, travels to the end of the disk, then reverses and serves requests on the way back. Because the head keeps sweeping, every request is reached within a sweep. LOOK is the practical refinement: the head reverses as soon as there are no more requests ahead of it, instead of travelling to the physical end, which saves the needless movement. Both need the current direction of travel as well as the head position to determine the order of service.
4.How do you calculate total head movement for SCAN?
In short: Sum the distances in the order the sweep serves the requests, including the trip to the disk's end before reversing.
List the requests in the order the algorithm serves them, then add the absolute distance of each move. In the example, the head is at cylinder 50 moving toward higher cylinders on a disk with cylinders 0 to 199, and the pending requests are 20, 60, 90 and 150. SCAN serves 60, 90 and 150, continues to 199, then reverses to 20: 10 + 30 + 60 + 49 + 179 = 328 cylinders. LOOK would reverse at 150 and total 100 + 130 = 230 cylinders.
head 50, moving up, 0-199 requests: 20 60 90 150 50>60>90>150>199>20 10+30+60+49+179 = 328 LOOK: 100 + 130 = 230
5.Why does disk scheduling matter less for SSDs?
In short: SSDs have no moving head, so access time barely depends on the address and reordering by position saves almost nothing.
An SSD reads flash memory electronically, with no arm to move and no rotation to wait for, so a request costs about the same wherever its data is. Seek-optimising algorithms such as SSTF or SCAN therefore bring almost no benefit, and Linux uses simple schedulers such as none or mq-deadline for NVMe drives, aiming for fairness and low overhead instead. SSDs have their own constraints: data is written in pages but erased in larger blocks, so the drive's firmware performs wear levelling and garbage collection, and the operating system helps with the TRIM command.
6.What is RAID, and how do RAID 0, 1 and 5 differ?
In short: Combining disks for speed or redundancy: RAID 0 stripes, RAID 1 mirrors, and RAID 5 stripes with distributed parity.
RAID combines several disks into one logical volume. RAID 0 stripes data across disks for speed and full capacity but has no redundancy, so one failed disk loses everything. RAID 1 mirrors every block on two disks, surviving one failure at the cost of half the capacity. RAID 5 stripes data with parity blocks distributed across all disks, surviving one disk failure with only one disk's worth of capacity used for parity, but small writes are slow, since parity must be read and updated. RAID 10 combines mirroring and striping, and RAID 6 adds a second parity to survive two failures.
How the diagnostic asks it
One question from the Operating Systems bank, exactly as a sitting would show it. The bank has 3 on disk scheduling and 30 across Operating Systems.
The disk head is at cylinder 40. Pending requests are for cylinders 10, 22, 70, 95, 38 and 160. What is the total head movement under SSTF?
- 1294 cylinders
- 2200 cylinders
- 3180 cylinderscorrect
- 4150 cylinders
From 40, SSTF goes to 38 (2), then 22 (16), then 10 (12). The nearest remaining request is now 70 (60), then 95 (25) and 160 (65): 2 + 16 + 12 + 60 + 25 + 65 = 180 cylinders. 294 is FCFS, which serves the requests in the order given. 200 is SCAN moving toward 0, which travels to cylinder 0 before turning. 150 is only the distance from 10 to 160 and leaves out the first moves.
Measure it
Reading answers tells you what’s true. A diagnostic tells you what you get wrong.
10 Operating Systems questions across its topics, easy to hard, about fifteen minutes. You get a readiness figure with the arithmetic shown, the topics you missed named, and a practice set sized for today. Free: 1 diagnostic a month and 15 problems a day. No card.