--- title: "Interleaving; SSTF, SCAN, C-SCAN order" subject: "Operating System" chapter: 6 key: "semester_6/operating_system:interleaving-winchester-disk-scheduling" source: https://www.bctengineer.com/q/semester_6/operating_system/interleaving-winchester-disk-scheduling site: BCT Engineering --- # Interleaving; SSTF, SCAN, C-SCAN order Operating System · Chapter 6: I/O Management and Disk Scheduling - Asked in: 2068 Bhadra, 2+6 marks - Video: [L-6.3: Disk Scheduling Algorithm | Operating System](https://www.youtube.com/watch?v=9uoa_p8q47Y) — Gate Smashers - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/operating_system/interleaving-winchester-disk-scheduling - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-6 ## Question 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. ## 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). ## Answer #### 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: ```text 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: | Sector | 3518 | 1846 | 8924 | 6672 | 1590 | 4126 | 107 | 9750 | 158 | 6621 | 446 | 11 | |---|---|---|---|---|---|---|---|---|---|---|---|---| | Cylinder | 17 | 9 | 44 | 33 | 7 | 20 | 0 | 48 | 0 | 33 | 2 | 0 | 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. ```text 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): ```text 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): ```text 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) ``` | Algorithm | Service order (sector numbers) | Movement | |---|---|---| | SSTF | 1846, 1590, 446, 11, 107, 158, 3518, 4126, 6621, 6672, 8924, 9750 | 58 | | 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 | (Within cylinder 0 the order of 11, 107, 158 may differ by rotational position; this does not change the movement.) ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Why is interleaving used? A. To store more sectors per track B. Logically consecutive sectors are separated so the controller is ready when the next sector arrives, avoiding a wasted revolution C. To reduce seek time between cylinders D. To make sectors contiguous Answer: B. Without it the head would already have passed the next sector while data is being transferred. (Key point: Interleaving purpose) 2. With 4 double-sided platters and 25 sectors per track, how many sectors are in a cylinder? A. 100 B. 50 C. 200 D. 25 Answer: C. 4 x 2 surfaces x 25 sectors = 200. (Key point: Sectors per cylinder) 3. Which cylinder holds sector 3518 here? A. 35 B. 18 C. 14 D. 17 Answer: D. 3518 div 200 = 17. (Key point: Cylinder number) 4. From cylinder 10 (requests at 9 and 17 nearby), SSTF serves first: A. Cylinder 9 (sector 1846), distance 1 B. Cylinder 17, because the arm moves upward C. Cylinder 0 D. Cylinder 48 Answer: A. SSTF picks the nearest cylinder regardless of direction. (Key point: SSTF first move) ## Related in Operating System - [Disk scheduling: FCFS, SSTF, SCAN, LOOK, C-SCAN](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adisk-200-cyl-head-moving-60) — Operating System, chapter 6 - [Disk scheduling with 100 cylinders](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adisk-100-cyl-fcfs-sstf-look-cscan-scan) — Operating System, chapter 6, asked 2× - [Disk scheduling, 1000 cylinders, head at 345](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adisk-1000-cyl-fifo-sstf-scan) — Operating System, chapter 6 - [Structured I/O software; SCAN vs SSTF](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Astructured-io-software-scan-vs-sstf) — Operating System, chapter 6 - [Disk scheduling with 5000 cylinders](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adisk-5000-cyl-fcfs-scan-look-cscan-sstf) — Operating System, chapter 6, asked 2× - [Disk scheduling with 50 cylinders](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adisk-50-cyl-fcfs-sstf-scan-look-cscan) — Operating System, chapter 6 ## Related in other subjects - [Maximum voltage of 3-disc string, 17.5 kV per unit](https://www.bctengineer.com/question.md?key=semester_4%2Fpower_system_analysis_i%3Amax-voltage-3-disc-17-5kv) — Power System Analysis I, chapter 2 - [Z-transform of a finite two-sided sequence](https://www.bctengineer.com/question.md?key=semester_6%2Fdigital_control_system%3Az-transform-finite-sequence) — Digital Control System, chapter 2 - [Time to scan one row of pixels](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Arow-scan-time-refresh) — Computer Graphics, chapter 1 - [Explain online order sequence diagram](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Aorder-processing-sequence-diagram-explain) — Object Oriented Analysis and Design, chapter 2