Disk Structure and Disk (I/O) Scheduling: short notes (Operating Systems)

Revision mode

Introduction

A hard disk drive (HDD) stores data on spinning platters and reads it with heads on a moving arm. Reaching a block means moving the arm to the right track and waiting for the right sector to rotate under the head, and both waits are mechanical: milliseconds, millions of times slower than a memory access. When many requests are pending, the order in which they are served changes the total arm movement a great deal. Disk scheduling chooses that order.

Disk geometry, addressing and the components of access time fix the cost of a request. The six classical scheduling algorithms (FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK) are run on one request queue, with the conventions that decide the numerical answer: the initial head direction, whether SCAN and C-SCAN travel to the end of the disk, and whether the return sweep of C-SCAN and C-LOOK is counted.

Prerequisites

Operating System Structure and System Calls: a read or write system call becomes a request to the device driver, which queues it for the disk.

Core concepts

Disk geometry

Term	Meaning
Platter	A rigid disk coated on both sides; several are stacked on one spindle
Surface	One side of a platter, with one read-write head
Track	A concentric ring on a surface
Sector	The smallest addressable unit on a track (traditionally 512 bytes; 4 KB on newer drives)
Cylinder	The set of tracks at the same arm position on all surfaces
Arm assembly	Moves all heads together, so all heads are always on the same cylinder

Capacity. Capacity = surfaces $\times$ tracks per surface $\times$ sectors per track $\times$ bytes per sector (if every track has the same number of sectors). A drive with 8 surfaces, 10,000 cylinders, 500 sectors per track and 512-byte sectors holds $8 \times 10{,}000 \times 500 \times 512 = 20{,}480{,}000{,}000$ bytes. Real drives use zoned recording: outer tracks hold more sectors than inner ones, so the formula applies per zone.

Logical block addressing. The drive presents a linear array of logical blocks. The traditional mapping goes sector by sector along a track, then head by head through a cylinder, then cylinder by cylinder. With $H$ heads, $S$ sectors per track and sectors numbered from 1:

\text{LBA} = (c \times H + h) \times S + (s - 1).

With $H = 8$ and $S = 500$ , cylinder 2, head 3, sector 10 is LBA $(2 \times 8 + 3) \times 500 + 9 = 9{,}509$ .

Access time

T_{\text{access}} = T_{\text{seek}} + T_{\text{rotation}} + T_{\text{transfer}}

Seek time: moving the arm to the cylinder. Quoted as an average; scheduling tries to reduce the total.
Rotational latency: waiting for the sector. At $r$ revolutions per second, one revolution takes $1/r$ ; the average latency is half a revolution.
Transfer time: the fraction of a revolution occupied by the sectors read. Reading $k$ of the $S$ sectors of a track takes $k/S$ of a revolution.

Example. 7,200 RPM, average seek 4 ms, 500 sectors of 512 bytes per track. One revolution takes $60/7200$ s $= 8.333$ ms, so the average rotational latency is 4.167 ms. Reading one 4 KB block (8 sectors) takes $8/500$ of a revolution $= 0.133$ ms, and the access costs $4 + 4.167 + 0.133 = 8.3$ ms. The sustained transfer rate from one track is $500 \times 512$ bytes per 8.333 ms $= 30{,}720{,}000$ bytes per second.

Random versus sequential. A 2 MB file is 512 blocks of 4 KB. Read as 512 random blocks it costs $512 \times 8.3 = 4{,}249.6$ ms. Stored contiguously it costs one seek and one latency plus the transfer of 4,096 sectors, $4096/500 = 8.192$ revolutions or 68.267 ms: about 76.43 ms in total, ignoring track-to-track switches. This is why allocation that keeps files contiguous matters (see File Allocation Methods and Free-Space Management).

Seek versus movement. The standard measure is total head movement in cylinders. If a question gives a time per cylinder crossed, multiply: 250 cylinders at 0.1 ms each is 25 ms of seeking.

The scheduling algorithms

Pending requests are cylinder numbers. The algorithms differ only in the order of service.

Algorithm	Rule	Starvation	Notes
FCFS	Serve in arrival order	No	Fair, often long movement
SSTF	Serve the pending request closest to the head	Yes: far requests can wait forever	Greedy; not optimal
SCAN (elevator)	Move in one direction serving requests, go on to the last cylinder, then reverse	No	Requests near the middle wait less on average than those near the edges
LOOK	As SCAN, but reverse at the last request in the current direction	No	The usual implementation of "SCAN"
C-SCAN	Move in one direction to the last cylinder, return to the first cylinder without serving, continue in the same direction	No	More uniform waiting time
C-LOOK	As C-SCAN, but stop at the last request in the sweep direction; upward jumps highest-to-lowest pending, downward lowest-to-highest pending	No	The usual implementation of "C-SCAN"

Conventions to fix before computing.

Direction. SCAN, LOOK, C-SCAN and C-LOOK need an initial direction. A question gives it directly, or gives the previously served cylinder: from 90 to 100 means the head is moving towards higher cylinders.
End of disk. SCAN and C-SCAN travel to the last cylinder (199 here) before reversing or returning, even if no request lies there; LOOK and C-LOOK do not.
Return sweep. Whether the return of C-SCAN (199 to 0) or the jump of C-LOOK (highest-to-lowest pending for an upward sweep, lowest-to-highest for a downward sweep) counts as head movement. Many textbooks count it (it is real arm motion, though fast); some questions say it is not counted. Give the total the question asks for, and state which.
Ties in SSTF. If two requests are equally close, a tie rule is needed; the traces take the lower cylinder.

Algorithms and pseudocode

Text

SCHEDULE-LOOK(head, Q, dir):            -- dir is UP or DOWN; Q is a set of cylinders
    order <- empty list
    if dir = UP then
        append the requests >= head, ascending, to order
        append the requests < head, descending, to order
    else
        append the requests <= head, descending, to order
        append the requests > head, ascending, to order
    return order

SCAN differs only by visiting the last cylinder before reversing (if any request remains on the other side); C-SCAN and C-LOOK append the second group in the same direction as the first. Each of these orders costs $O(n \lg n)$ for $n$ requests (a sort); SSTF done naively costs $O(n^2)$ , $O(n \lg n)$ with a balanced search tree keyed on cylinder.

Worked example: one queue, six algorithms

Cylinders 0 to 199. The head is at cylinder 100, moving towards higher cylinders (the previous request was at 90). Queue, in arrival order:

55,\ 130,\ 85,\ 170,\ 20,\ 140,\ 190,\ 65

Algorithm	Order of service	Total movement
FCFS	100, 55, 130, 85, 170, 20, 140, 190, 65	695
SSTF	100, 85, 65, 55, 20, 130, 140, 170, 190	250
SCAN	100, 130, 140, 170, 190, (199), 85, 65, 55, 20	278
LOOK	100, 130, 140, 170, 190, 85, 65, 55, 20	260
C-SCAN	100, 130, 140, 170, 190, (199), (0), 20, 55, 65, 85	383 with the return, 184 without
C-LOOK	100, 130, 140, 170, 190, 20, 55, 65, 85	325 with the jump, 155 without

Cylinders in parentheses are reached by the arm but have no request.

FCFS: $45 + 75 + 45 + 85 + 150 + 120 + 50 + 125 = 695$ .
SSTF: from 100 the nearest is 85 (15), then 65 (20), 55 (10), then 20 (35, closer than 130 at 75), then 130 (110), 140, 170, 190 (10, 30, 20): total 250. SSTF went down first although the head was moving up; direction plays no part in SSTF.
SCAN: up to 199 (99), then down to 20 (179): 278.
LOOK: up to 190 (90), then down to 20 (170): 260.
C-SCAN: up to 199 (99), return to 0 (199), up to 85 (85): 383; without the return, $99 + 85 = 184$ .
C-LOOK: up to 190 (90), jump to 20 (170), up to 85 (65): 325; without the jump, $90 + 65 = 155$ .

Head movement under the six algorithms — Figure 2. Head paths for the queue 55, 130, 85, 170, 20, 140, 190, 65 with the head at 100 moving up: FCFS 695 cylinders, SSTF 250, SCAN 278, LOOK 260, C-SCAN 383 (return counted) and C-LOOK 325 (jump counted).

Same queue, head moving down. SCAN: 100, 85, 65, 55, 20, (0), 130, 140, 170, 190, total $100 + 190 = 290$ . LOOK: $80 + 170 = 250$ . C-SCAN: down to 0, return to 199, down to 130: $100 + 199 + 69 = 368$ . C-LOOK: down to 20, jump to 190, down to 130: $80 + 170 + 60 = 310$ . The direction changes every answer except FCFS and SSTF.

From head movement to service time

Use the disk of the access-time example (average rotational latency 4.167 ms, 0.133 ms to transfer one 4 KB block) and suppose the arm needs 0.1 ms per cylinder moved. Each of the 8 requests in the worked queue reads one block.

Schedule	Cylinders	Seek time	Latency and transfer	Total
FCFS	695	69.5 ms	$8 \times 4.3 = 34.4$ ms	103.9 ms
SSTF	250	25.0 ms	34.4 ms	59.4 ms

Scheduling changes only the seek term; rotational latency and transfer are paid once per request whatever the order. The gain from scheduling therefore shrinks as latency and transfer grow relative to seek time.

An SSTF tie

Head at 50, requests 40, 60 and 90. Both 40 and 60 are 10 cylinders away.

Lower first (the tie rule used in the traces): 50, 40, 60, 90, moving $10 + 20 + 30 = 60$ cylinders.
Higher first: 50, 60, 40, 90, moving $10 + 20 + 50 = 80$ cylinders. After 60 the nearest request is 40 (20 away), not 90 (30 away): SSTF re-chooses at every step.

The tie rule changes the total from 60 to 80 cylinders, so a question must state it; when it does not, say which rule you used.

Important properties and observations

SSTF minimises each next seek, not the total; it can starve requests far from a busy region and is not optimal in general. With the head at 10 and requests 0, 15 and 25, SSTF serves 15, 25, 0 for $5 + 10 + 25 = 40$ cylinders, while 0, 15, 25 costs $10 + 25 = 35$ . (On the worked example SSTF's 250 happens to be optimal.)
SCAN and LOOK bound the wait of every request by about two sweeps; C-SCAN and C-LOOK by about one sweep plus the return, giving more uniform waiting times.
LOOK never moves more than SCAN on the same queue and direction, and C-LOOK never more than C-SCAN, under the same counting convention.
Scheduling is often less consequential with little queueing, but sweep algorithms can still incur extra movement depending on direction and end-of-disk conventions.
On solid-state drives there is no seek or rotation, so simple FCFS ordering (with merging of adjacent requests) is common; the six algorithms are about mechanical disks.

Common misconceptions.

"SCAN reverses at the last request." That is LOOK; SCAN goes to the end of the disk.
"SSTF is optimal." It is greedy; the queue order it produces can be beaten, and it can starve requests.
"The C-SCAN return is free." It is real arm movement; whether it is counted is a convention.

GATE examination perspective

Read the conventions first. Direction (or previous cylinder), disk range, end-of-disk travel, and whether the return sweep counts.
Totals by segments. For sweep algorithms, total movement is the sum of the straight segments (up, then down or jump), not of each hop.
Seek time from movement. Multiply cylinders by the time per cylinder if given; add rotational latency and transfer only if the question asks for access time.
Access-time arithmetic. Average latency is half a revolution; transfer time is the fraction of the track read.
CHS and LBA conversions. Fix whether sectors start at 0 or 1.

Summary

Access time = seek + rotational latency + transfer; average latency is half a revolution.
Capacity = surfaces $\times$ tracks $\times$ sectors $\times$ bytes per sector; LBA $= (cH + h)S + (s - 1)$ .
FCFS is fair but long; SSTF is greedy and can starve.
SCAN goes to the disk end and reverses; LOOK reverses at the last request.
C-SCAN returns to the physical starting end and sweeps one way. Upward C-LOOK jumps from the highest served request to the lowest pending one; downward C-LOOK jumps from the lowest served request to the highest pending one.
State the direction and whether the return sweep counts; on the example queue the totals were FCFS 695, SSTF 250, SCAN 278, LOOK 260, C-SCAN 383, C-LOOK 325.
Contiguous layout turns many random accesses into one seek plus a long transfer.

Sources

A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10th ed., Wiley: Chapter 11 (11.1 Overview of Mass-Storage Structure, 11.2 HDD Scheduling, whose subsections cover FCFS, SCAN and C-SCAN; 11.3 NVM Scheduling).
A. S. Tanenbaum, H. Bos, Modern Operating Systems, 4th ed., Pearson: Chapter 5 (5.4.1 Disk Hardware, 5.4.3 Disk Arm Scheduling Algorithms).