Disk Management and Scheduling
Learning Goals
- Describe the physical structure of a hard disk: platters, tracks, sectors, cylinders, and seek time vs rotational latency vs transfer time.
- Apply FCFS, SSTF, SCAN (Elevator), C-SCAN, and LOOK/C-LOOK scheduling algorithms and calculate total head movement.
- Understand disk formatting (low-level vs logical), boot blocks, and bad block handling.
- Compute the average access time for a given disk workload.
Disk Structure: The Anatomy of a Hard Drive
A magnetic hard disk drive (HDD) stores data on platters — circular, rigid disks coated with magnetic material.
| Term | Definition |
|---|---|
| Platter | A circular disk coated with magnetic material. Multiple platters are stacked on a spindle. |
| Track | One of many concentric circles on a platter surface. |
| Sector | The smallest physical storage unit on a disk (traditionally 512 bytes, modern drives use 4 KB). |
| Cylinder | The set of tracks at the same radial position across all platters. The head can read all tracks in a cylinder without moving. |
| Cluster (Block) | The smallest logical unit the OS can allocate. Typically a power-of-two multiple of sectors (e.g., 4 KB = 8 × 512-byte sectors). |
Disk Access Time
When the OS requests a disk read, three time components add up:
| Component | Description | Typical Range |
|---|---|---|
| Seek Time | Time to move the read/write head to the correct track (cylinder). This is the dominant cost. | 3–15 ms |
| Rotational Latency | Time for the platter to rotate so the desired sector is under the head. Average = half a rotation. | 2–8 ms (7200 RPM: 4.17 ms avg) |
| Transfer Time | Time to read/write the actual data once the head is positioned. | 0.1–1 ms per sector |
Formula: Total Access Time = Seek Time + Rotational Latency + Transfer Time
Example: A disk with 7200 RPM (rotations per minute), average seek time 5 ms, transferring a 4 KB block.
- Rotational latency per half rotation =
(60 / 7200) / 2 × 1000= 4.17 ms - Transfer time for 4 KB (assume 100 MB/s) =
4000 / 100000000= 0.04 ms - Total = 5 + 4.17 + 0.04 = 9.21 ms — most of the time is spent seeking and waiting for the rotation.
Disk Scheduling Algorithms — SCAN, C-SCAN, SSTF Explained
Disk Scheduling Algorithms
Disk scheduling aims to minimize the seek time — the time spent moving the head between tracks. The OS maintains a queue of pending I/O requests (track/sector numbers) and selects the order in which to service them.
1. First-Come, First-Served (FCFS)
Process requests in the order they arrive. Simple but inefficient.
| Pros | Cons |
|---|---|
| Fair — no request is starved | Very poor seek time — the head bounces all over the disk |
| Simple to implement | Convoy effect — one request far from the current position delays all subsequent requests |
2. Shortest Seek Time First (SSTF)
Select the request that is closest to the current head position.
| Pros | Cons |
|---|---|
| Reduces total seek time compared to FCFS | Starvation — requests far from the head may never be served if new nearby requests keep arriving |
| Simple to implement | Not optimal — it is a greedy algorithm that makes locally optimal decisions |
3. SCAN (Elevator Algorithm)
The head moves in one direction, servicing all requests along the way, until it reaches the end of the disk. Then it reverses direction and repeats. This is like an elevator moving up and down a building — it services floors in the direction of travel before reversing.
| Pros | Cons |
|---|---|
| No starvation — every request will eventually be serviced when the head passes over it | Requests at the edge of the disk wait longer |
| Predictable behavior | The head travels to the end of the disk even if no requests exist there |
4. C-SCAN (Circular SCAN)
A variant of SCAN that provides more uniform waiting times. The head moves in only one direction, servicing requests along the way. When it reaches the end, it immediately jumps back to the beginning (without servicing any requests on the return) and starts again.
| Pros | Cons |
|---|---|
| Uniform waiting time — a request at track 100 waits roughly the same as a request at track 200 | The jump (seek from last track to first) takes time |
| No starvation |
5. LOOK and C-LOOK
Variants of SCAN and C-SCAN that only travel as far as the last request in each direction, rather than going to the end of the disk.
SCAN: Head → ... → last request → END of disk → reverse → ... → first request → START of disk LOOK: Head → ... → last request → reverse → ... → first request (no unnecessary travel)
LOOK is what real operating systems implement (Linux, Windows). The term "elevator algorithm" usually refers to LOOK.
Why SSTF Favors Middle Cylinders [2019 Q9]
SSTF (Shortest Seek Time First) always selects the nearest pending request. Over time, this creates a statistical bias toward the middle cylinders:
| Region | Probability of being serviced | Explanation |
|---|---|---|
| Middle cylinders | High | The head spends most of its time here because there are cylinders on both sides — nearby requests exist in both directions |
| Innermost cylinders | Low | Only outer cylinders are on one side. If the head is far from the innermost edge, it will almost always pick a closer request toward the middle instead |
| Outermost cylinders | Low | Same as innermost — only inner cylinders on one side, so requests near the edge are rarely the closest |
The Intuition: Imagine a line of people waiting at a counter. The counter server (disk head) always serves the closest person. People at the ends of the line are rarely the closest to the server because there are always people closer to the middle. The server ends up mostly serving people near the middle, and people at the ends could wait indefinitely — starvation.
Key Exam Point [2019 Q9]: SSTF tends to favor middle cylinders over innermost and outermost cylinders because the head is statistically more likely to be near the middle, and closer requests from the middle continually arrive, starving the edge requests.
Scheduling Algorithm Comparison
| Algorithm | Starvation | Direction Change | Head Travels to End? | Best For |
|---|---|---|---|---|
| FCFS | No | No | No | Minimum fairness guarantee |
| SSTF | Yes | N/A | No | Light load, short queues |
| SCAN | No | At end of disk | Yes | Moderate load, fairness |
| C-SCAN | No | Jump to start | Yes (then jump) | Uniform wait times |
| LOOK | No | At last request | No | Real systems (Linux, Windows) |
| C-LOOK | No | Jump to first request | No | Uniform wait times, real systems |
Calculate Total Head Movement for SCAN and C-SCAN
- 1Step 1
Request queue: [98, 183, 37, 122, 14, 124, 65, 67]. Current head position: 53. Direction: moving towards 0 (left). Disk has 200 cylinders (0–199). We will calculate total head movement for SCAN, C-SCAN, and SSTF.
- 2Step 2
From 53: closest is 65 (12 away). From 65: closest is 67 (2 away). From 67: closest is 37 (30 away). From 37: closest is 14 (23 away). From 14: closest is 98 (84 away). From 98: closest is 122 (24 away). From 122: closest is 124 (2 away). From 124: closest is 183 (59 away). Total = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 cylinders.
- 3Step 3
Head at 53 moving left. Service: 37, 14. Then reach 0 (end). Reverse direction, move right. Service: 65, 67, 98, 122, 124, 183.
Total = |53−37| + |37−14| + |14−0| + |0−65| + |65−67| + |67−98| + |98−122| + |122−124| + |124−183| = 16 + 23 + 14 + 65 + 2 + 31 + 24 + 2 + 59 = 236 cylinders.
- 4Step 4
Head at 53 moving left. Service: 37, 14. Reach 0. Immediately jump to 199 (no servicing). Then continue moving left. Service: 183, 124, 122, 98, 67, 65.
Total = |53−37| + |37−14| + |14−0| + |0−199| + |199−183| + |183−124| + |124−122| + |122−98| + |98−67| + |67−65| = 16 + 23 + 14 + 199 + 16 + 59 + 2 + 24 + 31 + 2 = 386 cylinders.
- 5Step 5
SSTF = 236, SCAN = 236, C-SCAN = 386. For this particular queue, SSTF and SCAN tie for lowest head movement. C-SCAN is higher due to the long jump from 0→199. However, C-SCAN provides more uniform waiting times — the requests near the edge of the disk are not penalized as badly as in SCAN. The jump cost is a one-time fixed overhead.
PYQ Numerical Worked Examples
Example 1: SSTF with 100 Cylinders [2022 Q2b — 7 marks]
Problem: Disk has 100 cylinders (0-99). Head at cylinder 50. Queue: [4, 34, 10, 7, 19, 73, 2, 15, 6, 20]. It takes 1 ms to move between adjacent cylinders. Calculate total time using SSTF.
Solution (step by step):
| Step | Current | Nearest Request | Distance | Queue After |
|---|---|---|---|---|
| Start | 50 | — | — | [4,34,10,7,19,73,2,15,6,20] |
| 1 | 50 → 34 | 34 (16 away) | 16 | [4,10,7,19,73,2,15,6,20] |
| 2 | 34 → 20 | 20 (14 away) | 14 | [4,10,7,19,73,2,15,6] |
| 3 | 20 → 19 | 19 (1 away) | 1 | [4,10,7,73,2,15,6] |
| 4 | 19 → 15 | 15 (4 away) | 4 | [4,10,7,73,2,6] |
| 5 | 15 → 10 | 10 (5 away) | 5 | [4,7,73,2,6] |
| 6 | 10 → 7 | 7 (3 away) | 3 | [4,73,2,6] |
| 7 | 7 → 6 | 6 (1 away) | 1 | [4,73,2] |
| 8 | 6 → 4 | 4 (2 away) | 2 | [73,2] |
| 9 | 4 → 2 | 2 (2 away) | 2 | [73] |
| 10 | 2 → 73 | 73 (71 away) | 71 | [] |
Total distance = 16 + 14 + 1 + 4 + 5 + 3 + 1 + 2 + 2 + 71 = 119 cylinders. Total time = 119 ms.
Example 2: FCFS, SCAN, C-SCAN with 5000 Cylinders [2023 Q8b — 9 marks]
Problem: Disk has 5000 cylinders (0-4999). Current head at 2150. Previous request was 1805 (direction = moving towards higher numbers). Queue: [2069, 1212, 2296, 2800, 544, 1618, 356, 1523, 4965, 3681].
FCFS: Service in order: 2150 → 2069 → 1212 → 2296 → 2800 → 544 → 1618 → 356 → 1523 → 4965 → 3681.
- Distances: |2150-2069|=81, |2069-1212|=857, |1212-2296|=1084, |2296-2800|=504, |2800-544|=2256, |544-1618|=1074, |1618-356|=1262, |356-1523|=1167, |1523-4965|=3442, |4965-3681|=1284.
- Total = 81+857+1084+504+2256+1074+1262+1167+3442+1284 = 14,011 cylinders.
SCAN (moving upward): Service upward first: 2150 → 2296 → 2800 → 3681 → 4965. Hit end (4999). Reverse downward: 2069 → 1618 → 1523 → 1212 → 544 → 356.
- |2150-2296|=146, |2296-2800|=504, |2800-3681|=881, |3681-4965|=1284, |4965-4999|=34, |4999-2069|=2930, |2069-1618|=451, |1618-1523|=95, |1523-1212|=311, |1212-544|=668, |544-356|=188.
- Total = 146+504+881+1284+34+2930+451+95+311+668+188 = 7,492 cylinders.
C-SCAN (moving upward): Service upward: 2150 → 2296 → 2800 → 3681 → 4965. Hit end (4999). Jump to 0. Service upward again: 356 → 544 → 1212 → 1523 → 1618 → 2069.
- Distances upward: 146+504+881+1284+34 = 2849. Jump: |4999-0| = 4999. Service from 0: 356+188+668+311+95+451 = 2069.
- Total = 2849 + 4999 + 2069 = 9,917 cylinders.
Example 3: SSTF with 5000 Cylinders [2024 Q9b — 7 marks]
Problem: Disk has 5000 cylinders (0-4999). Current head at 143. Previous request was 125 (moving toward higher numbers). Queue: [86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130].
Solution: Nearest to 143 is 130 (13 away). Then 86 (44 away). Then 913 (827 away). Then 948 (35 away). Then 1022 (74 away). Then 1470 (448 away). Then 1509 (39 away). Then 1750 (241 away). Then 1774 (24 away).
- |143-130|=13, |130-86|=44, |86-913|=827, |913-948|=35, |948-1022|=74, |1022-1470|=448, |1470-1509|=39, |1509-1750|=241, |1750-1774|=24.
- Total = 13+44+827+35+74+448+39+241+24 = 1,745 cylinders.
Disk Formatting and Partitioning
Before a disk can be used, it must go through several layers of preparation.
1. Low-Level Formatting (Physical Formatting)
The disk controller or OS creates sector headers and trailers on each track. Each sector now has:
- Header: Sector number, track number, error-correcting code (ECC) fields.
- Data Area: The actual data (traditionally 512 bytes, now 4 KB in Advanced Format drives).
- Trailer: ECC bytes to detect and correct read errors.
This step is typically done at the factory for modern drives. The sector size is fixed.
2. Partitioning
The disk is divided into partitions — each partition can hold a different file system.
1// A typical partition table (MBR): 2// Partition 1: /dev/sda1 — ext4 (Linux root filesystem) — 100 GB 3// Partition 2: /dev/sda2 — swap (Linux swap space) — 8 GB 4// Partition 3: /dev/sda3 — NTFS (Windows data) — 392 GB
- MBR (Master Boot Record): The first sector of the disk. Contains:
- The boot loader code (first 446 bytes).
- The partition table (4 entries × 16 bytes = 64 bytes).
- The boot signature (0x55AA).
- GPT (GUID Partition Table): Modern replacement for MBR. Supports disks larger than 2 TB and unlimited partitions.
3. Logical Formatting (Creating a File System)
The OS writes the file system data structures to the partition:
| Structure | Purpose |
|---|---|
| Superblock | Stores overall file system metadata: total block count, free block count, inode count, block size, etc. |
| Inode Table | An array of inode structures — one inode per file/directory. |
| Free Space Map | Bitmap or other structure tracking which blocks are free. |
| Root Directory | The initial directory entry (/) |
| Log/Journal | For journaling file systems (ext3, ext4, NTFS) — records pending changes for crash recovery. |
Boot Block and Booting
When a computer is powered on, the following boot sequence occurs:
- ROM Bootstrap: The CPU starts executing code in ROM (BIOS or UEFI) at a fixed address.
- Load Boot Block: The ROM reads the first sector of the boot disk (the boot block or MBR) into RAM.
- Execute Boot Loader: The boot block code (e.g., GRUB stage 1) loads a larger boot loader (GRUB stage 2).
- Load OS Kernel: The boot loader reads the OS kernel from disk into memory and starts execution.
Bad Block Handling
Despite modern manufacturing precision, disks inevitably develop bad blocks (also called bad sectors) — physical defects that make a sector unreadable.
How Bad Blocks are Handled
| Method | Description | Used By |
|---|---|---|
| Sector Sparing | The disk controller reserves a pool of spare sectors. When a bad sector is detected, the controller transparently remaps the bad sector's logical address to a spare sector. The OS never knows it happened. | Modern HDDs and SSDs — this is built into the drive's firmware |
| Sector Slipping | When a bad block is in a specific track, all blocks from the bad block onward are shifted by one to make room. The spare sector fills the gap. | Older drives |
| Bad Block Forwarding | The OS maintains a bad block file. When the OS attempts to read a bad block, the file system marks it and no longer uses it. | Older file systems (before spare sectors became standard) |
S.M.A.R.T. (Self-Monitoring, Analysis, and Reporting Technology)
Modern drives continuously monitor their own health. Key metrics tracked:
| Metric | What It Measures |
|---|---|
| Reallocated Sector Count | Number of sectors that have been remapped to spare sectors. A rising count = drive is failing. |
| Pending Sector Count | Sectors that may be going bad — currently unreadable but not yet reallocated. |
| Seek Error Rate | Frequency of head positioning errors. |
| Spin-Up Time | Time for the disk to reach operating speed. |
| Temperature | Internal drive temperature. Excess heat accelerates failure. |
When a drive's S.M.A.R.T. metrics cross certain thresholds, the OS can warn the user to back up data before the drive fails completely.
Knowledge Check
Which disk scheduling algorithm can cause starvation of requests?