Skip to main content

Interleaving; SSTF, SCAN, C-SCAN order

Short answer

Interleaving spaces logically consecutive sectors to allow controller processing time. With 200 sectors/cylinder, SSTF order: 1846,1590,446,11,107,158,3518,4126,6621,6672,8924,9750 (58 cylinders). SCAN: 3518,4126,6621,6672,8924,9750,1846,1590,446,11,107,158 (188). C-SCAN: 3518,4126,6621,6672,8924,9750,11,107,158,446,1590,1846 (197).

What is interleaving? Consider a Winchester-style hard disc with 100 cylinders, four double-sided platters and 25 sectors per track. The following is the (time-ordered) sequence of requests for disc sectors: {3518, 1846, 8924, 6672, 1590, 4126, 107, 9750, 158, 6621, 446, 11}. The disc arm is currently at cylinder 10, moving towards 100. For each of SSTF, SCAN and C-SCAN, give the order in which the above requests would be served.

Interleaving

Interleaving is the technique of numbering the sectors of a track so that logically consecutive sectors are not placed in physically adjacent positions but separated by one or more sectors. After reading a sector, the controller needs time to transfer the data to memory/process it; if the next sector were adjacent, the head would already have passed it and a whole revolution would be wasted. With an interleave factor of 2:1 an 8-sector track is numbered:

 physical slot : 0 1 2 3 4 5 6 7
 logical sector: 0 4 1 5 2 6 3 7

so the next logical sector arrives just when the controller is ready, increasing the data rate.

Disk scheduling numerical

Sectors per cylinder = 4 platters x 2 sides x 25 sectors = 200. Cylinder = sector number div 200 (cylinders 0 to 99). Head at cylinder 10, moving towards 100 (upward). Requests in cylinder form:

Sector3518184689246672159041261079750158662144611
Cylinder179443372004803320

Requests in the same cylinder need no arm movement and are served in sector order.

SSTF (nearest cylinder first). From 10 the nearest is 9 (distance 1) vs 17 (7). Then 7, 2, 0 (sectors 11, 107, 158), then 17, 20, 33, 44, 48.

 Order of sectors: 1846, 1590, 446, 11, 107, 158,
                   3518, 4126, 6621, 6672, 8924, 9750
 Cylinders: 10 -> 9 -> 7 -> 2 -> 0 -> 17 -> 20 -> 33 -> 44 -> 48
 Head movement = 1+2+5+2+17+3+13+11+4 = 58 cylinders

SCAN (elevator; go up to the end, then reverse):

 Order of sectors: 3518, 4126, 6621, 6672, 8924, 9750,
                   (arm goes to cylinder 99, reverses)
                   1846, 1590, 446, 11, 107, 158
 Cylinders: 10 -> 17 -> 20 -> 33 -> 44 -> 48 -> 99 -> 9 -> 7 -> 2 -> 0
 Head movement = 89 + 99 = 188 cylinders

C-SCAN (go up serving requests; at the end return to cylinder 0 without serving; serve upward again):

 Order of sectors: 3518, 4126, 6621, 6672, 8924, 9750,
                   (arm to 99, returns to 0)
                   11, 107, 158, 446, 1590, 1846
 Cylinders: 10 -> 17 -> 20 -> 33 -> 44 -> 48 -> 99 -> 0 -> 2 -> 7 -> 9
 Head movement = 89 + 99 + 9 = 197 cylinders (including the return)
AlgorithmService order (sector numbers)Movement
SSTF1846, 1590, 446, 11, 107, 158, 3518, 4126, 6621, 6672, 8924, 975058
SCAN3518, 4126, 6621, 6672, 8924, 9750, 1846, 1590, 446, 11, 107, 158188
C-SCAN3518, 4126, 6621, 6672, 8924, 9750, 11, 107, 158, 446, 1590, 1846197

(Within cylinder 0 the order of 11, 107, 158 may differ by rotational position; this does not change the movement.)

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Operating System chapter 6 questions →