Operating SystemsDisk Structure

Disk Structure

LevelIntermediate

Duration60 mins

TopicDisk Structure

3 / 5

Cylinders

The Third Dimension of Disk Organization

We have explored platters and surfaces (the physical storage medium), and tracks and sectors (the two-dimensional organization on each surface). But a hard disk drive is not a single surface—it's a stack of multiple platters, each with two surfaces, all rotating together on a common spindle.

When we consider all surfaces simultaneously, a powerful organizational concept emerges: the cylinder. A cylinder is the collection of all tracks at the same radial distance across all platters. Think of it as an imaginary vertical "barrel" passing through the platter stack—every track touched by this barrel constitutes one cylinder.

This three-dimensional perspective is not merely academic. Cylinders form the basis of efficient data layout, disk scheduling algorithms, and the historical CHS addressing scheme. Understanding cylinders reveals why certain performance optimizations work and how disk access patterns translate to physical head movements.

What You Will Learn

By the end of this page, you will understand: the definition and geometry of disk cylinders; why cylinder-based access minimizes seek time; how cylinders relate to the CHS addressing scheme; cylinder allocation strategies in file systems; and the modern relevance of cylinder concepts despite LBA abstraction.

Cylinder Definition and Geometry

1.1 Formal Definition

A cylinder is defined as the set of all tracks that share the same radial position across all surfaces in a disk drive. If a drive has $P$ platters with $2P$ surfaces (both sides of each platter), then a single cylinder contains $2P$ tracks.

Mathematical Definition:

$$\text{Cylinder}_n = {\text{Track}_n \text{ on Surface } s \mid s \in {0, 1, 2, ..., 2P-1}}$$

Where:

$n$ = Cylinder number (track number on each surface)
$P$ = Number of platters
$2P$ = Number of surfaces (assuming all surfaces are active)

Visualization:

Imagine a stack of LP records on a spindle. Each record is a platter. Draw a circle on the top record at some radius. If you could draw that same circle on every record in the stack and connect them vertically, you'd have a cylindrical shape—hence the name "cylinder."

Converting Mermaid diagram...

1.2 Cylinder Capacity

The total capacity of a single cylinder can be calculated as:

$$\text{Cylinder Capacity} = \text{Surfaces} \times \text{Sectors per Track} \times \text{Bytes per Sector}$$

Example Calculation:

For a drive with:

4 platters (8 surfaces)
800 sectors per track (outer zone)
4096 bytes per sector

$$\text{Cylinder Capacity} = 8 \times 800 \times 4096 = 26,214,400 \text{ bytes} \approx 25 \text{ MB}$$

Note that due to Zoned Bit Recording (ZBR), cylinder capacity varies across the drive:

Outer cylinders (low cylinder numbers) have more sectors per track
Inner cylinders (high cylinder numbers) have fewer sectors per track

Cylinder Position	Relative Capacity	Relative Speed
Outer (Cylinder 0)	100%	100%
Middle	~75%	~75%
Inner (Cylinder N)	~50%	~50%

Head Count May Not Equal Surface Count

In some drive designs, not all physical surfaces are used for data storage. The outer surfaces (top of first platter, bottom of last platter) may be unused due to susceptibility to contamination. Additionally, drive specifications might list "3 heads" for a 2-platter drive, indicating one surface is reserved for servo or unused. Always verify actual head count when calculating geometry.

The Performance Rationale: Why Cylinders Matter

The cylinder concept exists because of a fundamental asymmetry in disk access times. Understanding this asymmetry reveals why cylinder-aware data placement dramatically improves performance.

2.1 Access Time Components

Reading or writing data involves three primary time components:

Component	Definition	Typical Time
Seek Time	Time to move the actuator arm to the target cylinder	3-15 ms
Rotational Latency	Time waiting for the target sector to rotate under the head	2-8 ms (avg half rotation)
Transfer Time	Time to read/write the actual data	Microseconds to milliseconds

The Key Insight:

Seek time is by far the largest component. Moving from one cylinder to another requires physical movement of the actuator arm—a mechanical operation that takes milliseconds.

However, switching between heads within the same cylinder requires no physical movement. All tracks in a cylinder are at the same radial position. The actuator arm is already positioned correctly for any track in the cylinder.

Within-Cylinder Access (Fast)

•Electronic head switching only
•Switching time: ~0.5-1 ms
•No mechanical movement required
•All 8 tracks instantly accessible
•Cylinder capacity read with one seek

Cross-Cylinder Access (Slow)

•Mechanical actuator movement
•Seek time: 3-15 ms (1+ track)
•Full track-to-track: ~0.5-2 ms
•Average seek: ~8-10 ms
•Full stroke: 15-20 ms

2.2 Access Time Comparison

Scenario: Reading 25 MB of data

Assume a drive with:

8 surfaces (4 platters)
25 MB per cylinder (approximately)
7200 RPM (8.33 ms per rotation)
Average seek time: 8 ms

Option A: Data spread across 8 cylinders (8 tracks, one per cylinder)

8 seek operations: 8 × 8 ms = 64 ms
8 head switches: negligible
Data transfer: ~8 ms (one track per seek)
Total: ~80-100 ms

Option B: Data concentrated in 1 cylinder (8 tracks on same cylinder)

1 seek operation: 8 ms
7 head switches: 7 × 0.5 ms = 3.5 ms
Data transfer: ~8 ms
Total: ~20 ms

Speedup: 4-5× faster by placing related data on the same cylinder.

2.3 The Cylinder Group Optimization

This performance insight drives file system design. Intelligent file systems:

Allocate related data (files in same directory) to the same or adjacent cylinders
Keep file data and metadata on the same cylinder when possible
Group inodes and data blocks by cylinder group (e.g., ext4 block groups, FFS cylinder groups)
Minimize head movements between reads in typical access patterns

The Decline of Cylinder Awareness

Modern drives heavily abstract geometry via LBA, and features like Native Command Queuing (NCQ) allow drives to reorder operations internally. SSDs eliminate seek time entirely. Nevertheless, understanding cylinder-based optimization explains the design of file systems like ext4/UFS that were architected around this principle.

Cylinders in the CHS Addressing Scheme

The cylinder concept is codified in the Cylinder-Head-Sector (CHS) addressing scheme—the original method for specifying disk locations. While LBA has replaced CHS for most purposes, understanding CHS provides insight into disk architecture and legacy system compatibility.

3.1 CHS Address Structure

A CHS address specifies:

C (Cylinder): Which cylinder (radial position), numbered 0 to max
H (Head): Which read/write head (i.e., which surface), numbered 0 to max
S (Sector): Which sector within the track, numbered 1 to max (note: 1-based!)

Address Tuple Example: CHS (500, 3, 42)

Cylinder 500 (501st cylinder from outer edge)
Head 3 (4th head, i.e., bottom surface of second platter in a 4-platter drive)
Sector 42 (42nd sector on that track)

3.2 CHS Address Space Calculation

The total addressable capacity under CHS:

$$\text{Total Sectors} = C_{\max} \times H_{\max} \times S_{\max}$$ $$\text{Capacity} = \text{Total Sectors} \times \text{Bytes per Sector}$$

CHS Limitations Through History
Interface	Max Cylinders	Max Heads	Max Sectors	Max Capacity @ 512B
Original IBM PC BIOS	1,024	16	63	504 MB
Extended INT 13h	1,024	256	63	8.4 GB
ATA-1 Specification	65,536	16	255	136.9 GB
Practical Limit	16,383	16	63	8.4 GB (BIOS limited)

3.3 Why Sector Numbering Starts at 1

Unreviewingly, CHS sector numbers are 1-based while cylinder and head numbers are 0-based. This inconsistency stems from the original IBM PC design:

Track 0, Sector 1 contains the Master Boot Record (MBR)
Zero was considered an invalid sector number for error detection
The convention persisted for backward compatibility

Consequence: Maximum sectors per track is 63, not 64, because 6 bits encode values 1-63 (not 0-63).

3.4 CHS-to-LBA Translation

The translation from CHS to LBA follows a specific formula:

$$\text{LBA} = (C \times \text{HeadsPerCylinder} + H) \times \text{SectorsPerTrack} + (S - 1)$$

The $S - 1$ accounts for the 1-based sector numbering.

Example:

CHS = (0, 0, 1) → LBA = 0 (first sector)
CHS = (0, 0, 63) → LBA = 62 (last sector of first track)
CHS = (0, 1, 1) → LBA = 63 (first sector of second track/head)

CHS and LBA Conversion Utilities
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/*
 * CHS ↔ LBA Conversion Utilities
 * 
 * These functions demonstrate the mathematical relationship between
 * physical disk geometry (CHS) and logical block addressing (LBA).
 * Modern systems use LBA exclusively, but understanding CHS is 
 * essential for boot sector analysis and legacy compatibility.
 */
 
#include <stdint.h>
#include <stdbool.h>
 
/* Drive geometry parameters */
typedef struct {
    uint16_t cylinders;        /* Total cylinders (C) */
    uint8_t  heads;            /* Heads per cylinder (H) - i.e., surfaces */
    uint8_t  sectors_per_track; /* Sectors per track (S) - typically 63 */
    uint64_t total_sectors;    /* Total LBA sectors (for verification) */
} DriveGeometry;
 
/* CHS address structure */
typedef struct {
    uint16_t cylinder;  /* 0-based, 0 to (cylinders-1) */
    uint8_t  head;      /* 0-based, 0 to (heads-1) */
    uint8_t  sector;    /* 1-based, 1 to sectors_per_track */
} CHSAddress;
 
/*
 * Convert CHS to LBA
 * 
 * Formula: LBA = ((C × H_total) + H) × S_total + (S - 1)
 * 
 * Returns: 64-bit LBA value
 */
uint64_t chs_to_lba(CHSAddress chs, const DriveGeometry* geom) {
    return ((uint64_t)chs.cylinder * geom->heads + chs.head) 
           * geom->sectors_per_track 
           + (chs.sector - 1);  /* Sector is 1-based */
}
 
/*
 * Convert LBA to CHS
 * 
 * Returns: CHS address structure
 * Note: May overflow if drive geometry doesn't match actual drive
 */
CHSAddress lba_to_chs(uint64_t lba, const DriveGeometry* geom) {
    CHSAddress chs;
    
    /* Sector is 1-based */
    chs.sector = (lba % geom->sectors_per_track) + 1;
    
    /* Remaining LBA after removing sector offset */
    uint64_t temp = lba / geom->sectors_per_track;
    
    /* Head within cylinder */
    chs.head = temp % geom->heads;
    
    /* Cylinder number */
    chs.cylinder = temp / geom->heads;
    
    return chs;
}
 
/*
 * Validate CHS address against geometry limits
 */
bool is_valid_chs(CHSAddress chs, const DriveGeometry* geom) {
    return (chs.cylinder < geom->cylinders) &&
           (chs.head < geom->heads) &&
           (chs.sector >= 1 && chs.sector <= geom->sectors_per_track);
}
 
/*
 * Calculate total drive capacity in bytes
 */
uint64_t calculate_capacity(const DriveGeometry* geom, uint16_t bytes_per_sector) {
    return (uint64_t)geom->cylinders 
           * geom->heads 
           * geom->sectors_per_track 
           * bytes_per_sector;
}
 
/*
 * Example: Working with a typical drive geometry
 */
void example_usage() {
    /* Typical BIOS-reported geometry (not real physical geometry) */
    DriveGeometry geom = {
        .cylinders = 16383,        /* Max BIOS cylinders */
        .heads = 16,               /* Heads per cylinder */
        .sectors_per_track = 63,   /* Standard sectors per track */
        .total_sectors = 16383 * 16 * 63  /* ~8.4 GB limit */
    };
    
    /* Example: Convert LBA 100000 to CHS */
    CHSAddress chs = lba_to_chs(100000, &geom);
    /* Result: cylinder=99, head=3, sector=10 */
    
    /* Verify round-trip */
    uint64_t lba_back = chs_to_lba(chs, &geom);
    /* lba_back should equal 100000 */
    
    /* Calculate 8.4 GB BIOS limit */
    uint64_t capacity = calculate_capacity(&geom, 512);
    /* capacity = 8,422,686,720 bytes ≈ 8.4 GB */
}

The 8.4 GB Barrier

The combination of BIOS limitations (1024 cylinders × 256 heads × 63 sectors) created the infamous 8.4 GB barrier in the late 1990s. Drives larger than 8.4 GB required BIOS extensions (INT 13h extensions) or LBA translation in the BIOS. This legacy affects MBR partitioning to this day.

Cylinder Groups in File Systems

The performance benefits of cylinder-localized access profoundly influenced file system design. The cylinder group concept, introduced by the Berkeley Fast File System (FFS) in 1984, exemplifies this optimization.

4.1 The FFS/UFS Cylinder Group Model

The Berkeley Fast File System (later Unix File System, UFS) pioneered cylinder groups:

Design Principles:

Divide the disk into cylinder groups — Each group spans a contiguous range of cylinders
Distribute metadata across groups — Each group has its own inode table, block bitmap, and superblock backup
Allocate files within their directory's group — Files in the same directory are likely accessed together
Keep file data near its inode — Reduces seek between inode lookup and data read
Balance group utilization — Spread new directories across groups to prevent hotspots

Converting Mermaid diagram...

4.2 Cylinder Group Structure in Detail

Each cylinder group contains:

Component	Purpose	Typical Size
Superblock Copy	Redundant copy for crash recovery	1-2 blocks
Cylinder Group Descriptor	Free block/inode counts, flags	1 block
Inode Allocation Bitmap	Tracks which inodes are in use	Varies
Block Allocation Bitmap	Tracks which data blocks are in use	Varies
Inode Table	Actual inode structures for this group	Many blocks
Data Blocks	Actual file content storage	Most of group

4.3 Allocation Policy

The cylinder group allocator follows sophisticated rules:

Directory Placement:

New directories go into the cylinder group with the most free inodes and lowest existing directory count
This spreads the directory tree across groups

File Placement:

Files are allocated in the same cylinder group as their parent directory
If the parent's group is full, search nearby groups

Large File Handling:

Large files that would fill a cylinder group are split across groups
Data blocks every 48 KB (historically) would move to a new group
Balances locality with group utilization

4.4 Modern Relevance: ext4 Block Groups

Linux ext4 inherits the cylinder group concept as block groups:

ext4 Block Group Structure:
├── Superblock (copy, in some groups)
├── Group Descriptors (copies, in some groups)
├── Block Bitmap (1 block)
├── Inode Bitmap (1 block)
├── Inode Table (multiple blocks)
└── Data Blocks (bulk of group)

While ext4 doesn't strictly map block groups to physical cylinders (LBA abstraction obscures this), the principle remains:

Related files should be physically proximate
Metadata should be near its associated data
Spreading allocation prevents fragmentation hot spots

Block Group Sizing:

With 4 KB blocks and a single block for the block bitmap:

Maximum blocks per group: 32,768 (8 × 4096 bits)
Maximum group size: 128 MB

This is much smaller than physical cylinder groups, but the locality principle persists at this granularity.

The Flex Block Groups Extension

ext4 introduces flexible block groups: multiple block groups can combine their metadata (bitmaps, inode tables) at the start of the first group. This improves metadata locality and enables more efficient allocation, though it abstracts further from physical cylinders.

Cylinder Skew and Interleaving

Reading data across an entire cylinder—track by track—isn't as simple as head switching. The timing of sector positions across tracks introduces complexities that engineers address through skew and interleaving.

5.1 The Head Switching Latency Problem

When the drive finishes reading the last sector of track N on surface 0 and switches to surface 1 to continue reading, a brief delay occurs:

Electronic switching time: ~0.5-1 ms
Servo settling time: Additional microseconds for positioning confirmation

During this delay, the platter continues rotating. If sector 0 on the next track is directly below sector 0 on the previous track, spinning for 1 ms at 7200 RPM means:

$$\text{Rotation during switch} = \frac{1 \text{ ms}}{8.33 \text{ ms/rotation}} \approx 0.12 \text{ rotations} \approx 7-8 \text{ sectors}$$

The head arrives at the new track, but sector 0 has already passed! The drive must wait almost a full rotation to read sector 0—wasting 8+ ms.

5.2 Track Skew (Head Skew)

Track skew offsets the angular position of sector numbering between adjacent tracks on the same cylinder:

Track Skew Example (8-Head Drive)
Surface	Position of Sector 0	Relative Offset
Surface 0	0° (reference)	0 sectors
Surface 1	10°	+7 sectors
Surface 2	20°	+14 sectors
Surface 3	30°	+21 sectors
Surface 4	40°	+28 sectors
Surface 5	50°	+35 sectors
Surface 6	60°	+42 sectors
Surface 7	70°	+49 sectors

With this skew, after reading the last sector of surface 0 and switching to surface 1, the head arrives just as sector 0 of surface 1 is approaching—no rotational delay.

5.3 Cylinder Skew (Track-to-Track Skew)

Cylinder skew addresses the delay when the actuator arm must move to an adjacent cylinder (seek). Even a single-track seek takes 0.5-2 ms, during which the platter rotates:

$$\text{Rotation during seek} = \frac{1 \text{ ms}}{8.33 \text{ ms/rotation}} \approx 0.12 \text{ rotations} \approx 7-8 \text{ sectors}$$

Cylinder skew offsets sector numbering between adjacent cylinders to account for seek time:

Cylinder	Position of Sector 0	Offset from Previous
Cylinder 0	0°	-
Cylinder 1	12°	+8 sectors
Cylinder 2	24°	+8 sectors
...	...	...

5.4 Modern Relevance

While modern drives handle skew internally (invisible to the OS), the concept explains:

Why sequential LBA access is optimized by drive firmware
The internal geometry is far more complex than simple CHS suggests
Performance modeling must account for head and track switching overhead

Sector Interleaving (Historical)

Early drives (1980s-1990s) used sector interleaving—numbering sectors 1, 4, 7, 2, 5, 8, 3, 6 instead of 1, 2, 3, 4... This gave slow controllers time to process each sector before the next arrived. Modern controllers are fast enough that 1:1 interleaving (no interleave) is universal.

Cylinder Concepts in Modern Systems

While LBA has replaced CHS for addressing, and SSDs have eliminated mechanical seek entirely, the cylinder concept remains relevant in specific contexts.

6.1 LBA Abstraction: What's Hidden

Modern drives translate LBA to physical location via internal firmware:

OS Request: Read LBA 12345678
    ↓
Drive Firmware: Zone lookup → Physical cylinder, head, sector
    ↓
Actuator positions, head reads, data returned

The firmware handles:

Zone-based sector mapping (different sectors-per-track across disk)
Defect skipping (bad sectors replaced with spares)
Track skew (optimized for sequential access)
Translation tables (stored in drive NVRAM)

6.2 Where Cylinder Awareness Persists

Modern Uses of Cylinder Concepts

•Disk Forensics — Recovering data requires understanding physical layout, especially for damaged drives where firmware translation tables are lost.
•Legacy BIOS Boot — MBR-based booting still uses CHS addressing for the boot sector and partition table. BIOS reads partition start addresses in CHS format.
•RAID Controller Optimization — Some RAID controllers optimize stripe layout based on cylinder geometry for sequential performance.
•Short-Stroking — High-performance configurations use only outer cylinders for consistent low latency. Requires cylinder awareness.
•Secure Erase Verification — Verifying complete erasure may require understanding physical sector allocation patterns.
•Performance Analysis — Understanding why certain access patterns are slow requires cylinder-aware thinking (seeks vs. head switches).

6.3 SSDs: The Post-Cylinder Era

Solid-state drives eliminate cylinders entirely:

No rotating platters → No tracks or cylinders
No actuator arm → No seek time
No head switching → No cylinder-based optimization
Flash pages and blocks have different geometry

However, SSDs have their own "geometry" considerations:

SSD Geometry	Closest HDD Analog	Performance Impact
Page (4-16 KB)	Sector	Smallest read/write unit
Block (256 KB - 4 MB)	Track (sort of)	Smallest erase unit
Plane (collection of blocks)	Surface (very loosely)	Parallel operations
Die	Platter	Multiplies bandwidth

SSD "geometry" affects write amplification, wear leveling, and performance variability—topics for SSD-specific discussions.

Partition Tools and Fake Geometry

Modern partitioning tools (like fdisk, gdisk) may report "cylinders" for HDD alignment, but these are often logical constructs (e.g., 1 cylinder = 2048 sectors = 1 MB) for alignment purposes, not reflective of physical geometry. GPT partitioning abandons CHS entirely, using LBA exclusively.

Cylinder-Based Disk I/O Scheduling

The cylinder concept is foundational to disk I/O scheduling algorithms. These algorithms, implemented in drive firmware and OS I/O schedulers, minimize seek time by organizing requests based on cylinder position.

7.1 The Scheduling Challenge

When multiple I/O requests are pending, the order in which they're serviced dramatically affects total seek time:

Example Queue: Requests for cylinders [98, 183, 37, 122, 14, 124, 65, 67]

Head currently at cylinder 53

The total seek distance depends on the order of servicing.

7.2 Classic Cylinder-Aware Algorithms

Disk Scheduling Algorithms Overview
Algorithm	Strategy	Seek Distance (Example)	Characteristics
FCFS	First-Come, First-Served	640 cylinders	Fair but very inefficient; high seek distances
SSTF	Shortest Seek Time First	236 cylinders	Efficient but can starve distant requests
SCAN (Elevator)	Move in one direction, service all, reverse	331 cylinders	Predictable, fair, slightly suboptimal
C-SCAN	Move one direction, jump back to start	382 cylinders	More uniform wait times than SCAN
LOOK	Like SCAN, but reverse at last request	299 cylinders	Avoids going to disk edges unnecessarily
C-LOOK	Like C-SCAN, but reverse at last request	322 cylinders	Combines benefits of LOOK and C-SCAN

7.3 Understanding SCAN (Elevator Algorithm)

Process:

Head moves in one direction (e.g., toward higher cylinders)
Services all requests in that direction
Reaches the end of the disk (or last request in LOOK)
Reverses direction and services remaining requests

Why "Elevator"? Just like an elevator services floors in one direction before reversing, the disk head sweeps across cylinders.

Advantages:

Predictable service times
Bounded maximum wait (one full sweep + partial sweep)
Simple to implement

Disadvantages:

Cylinders at edges (0, max) get serviced less frequently than middle
Not optimal for heavy loads concentrated on one area

7.4 Modern I/O Schedulers

Linux kernel I/O schedulers build on these principles:

Scheduler	Description	Best For
noop	No reordering (FIFO)	SSDs, VMs with host-side scheduling
deadline	Prioritizes request age with cylinder sorting	Databases, latency-sensitive
cfq (Complete Fair Queuing)	Per-process queues, cylinder-sorted	Desktop responsiveness
mq-deadline	Multi-queue deadline for NVMe	Modern NVMe SSDs
bfq	Budget Fair Queueing	Interactive workloads

SCAN Algorithm Implementation
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/*
 * SCAN (Elevator) Disk Scheduling Algorithm
 * 
 * Demonstrates cylinder-based I/O request ordering.
 * This is a simplified educational implementation.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
#define MAX_REQUESTS 100
 
typedef struct {
    int cylinder;      /* Target cylinder for this request */
    int request_id;    /* Original request identifier */
    bool processed;    /* Has this request been serviced? */
} DiskRequest;
 
typedef struct {
    int current_cylinder;    /* Current head position */
    int direction;           /* 1 = toward higher cylinders, -1 = toward lower */
    int max_cylinder;        /* Maximum cylinder number */
    DiskRequest requests[MAX_REQUESTS];
    int request_count;
    int total_seek_distance;
} DiskScheduler;
 
/*
 * Add a request to the scheduler queue
 */
void add_request(DiskScheduler* sched, int cylinder, int id) {
    if (sched->request_count < MAX_REQUESTS) {
        sched->requests[sched->request_count].cylinder = cylinder;
        sched->requests[sched->request_count].request_id = id;
        sched->requests[sched->request_count].processed = false;
        sched->request_count++;
    }
}
 
/*
 * SCAN Algorithm: Service requests in current direction, then reverse
 * Returns: Service order array (by request_id)
 */
void scan_schedule(DiskScheduler* sched, int* service_order) {
    int order_idx = 0;
    int serviced = 0;
    
    while (serviced < sched->request_count) {
        int next_idx = -1;
        int min_distance = sched->max_cylinder + 1;
        
        /* Find closest request in current direction */
        for (int i = 0; i < sched->request_count; i++) {
            if (sched->requests[i].processed) continue;
            
            int distance = sched->requests[i].cylinder - sched->current_cylinder;
            
            /* Check if request is in our current direction */
            bool in_direction = (sched->direction > 0) ? 
                                (distance >= 0) : (distance <= 0);
            
            if (in_direction && abs(distance) < min_distance) {
                min_distance = abs(distance);
                next_idx = i;
            }
        }
        
        if (next_idx >= 0) {
            /* Service this request */
            sched->total_seek_distance += min_distance;
            sched->current_cylinder = sched->requests[next_idx].cylinder;
            sched->requests[next_idx].processed = true;
            service_order[order_idx++] = sched->requests[next_idx].request_id;
            serviced++;
        } else {
            /* No requests in current direction - reverse */
            sched->direction = -sched->direction;
        }
    }
}
 
/*
 * Example usage
 */
int main() {
    DiskScheduler sched = {
        .current_cylinder = 53,
        .direction = 1,        /* Start moving toward higher cylinders */
        .max_cylinder = 199,
        .request_count = 0,
        .total_seek_distance = 0
    };
    
    /* Add requests for cylinders: 98, 183, 37, 122, 14, 124, 65, 67 */
    add_request(&sched, 98, 1);
    add_request(&sched, 183, 2);
    add_request(&sched, 37, 3);
    add_request(&sched, 122, 4);
    add_request(&sched, 14, 5);
    add_request(&sched, 124, 6);
    add_request(&sched, 65, 7);
    add_request(&sched, 67, 8);
    
    int service_order[MAX_REQUESTS];
    scan_schedule(&sched, service_order);
    
    printf("SCAN Schedule (starting at cylinder 53, direction: up):
");
    printf("Service order: ");
    for (int i = 0; i < sched.request_count; i++) {
        printf("%d ", service_order[i]);
    }
    printf("
Total seek distance: %d cylinders
", sched.total_seek_distance);
    
    return 0;
}
 
/* Expected output:
 * Service order: 7 8 1 4 6 2 3 5
 * (Cylinders: 65, 67, 98, 122, 124, 183, then reverse: 37, 14)
 * Total seek distance: ~299 cylinders (LOOK variant)
 */

Native Command Queuing (NCQ)

Modern SATA drives support Native Command Queuing (NCQ), allowing up to 32 commands to be queued at the drive. The drive's firmware (not the OS) reorders commands for optimal seek patterns. This moves scheduling responsibility from the OS to the drive, where actual geometry is known.

Summary: Cylinders

We have explored the three-dimensional concept of disk cylinders—the vertical alignment of tracks across all platters. Let's consolidate the key insights:

Key Takeaways

•A cylinder is all tracks at the same radius — Spanning all surfaces, accessible with head switching alone (no seek).
•Within-cylinder access is fast — Electronic head switching (~0.5ms) vs. mechanical seeks (3-15ms) makes cylinder-local data far faster to access.
•CHS addressing encodes cylinder position — Historical addressing directly specified cylinder, head, sector—revealing physical geometry.
•File systems optimize via cylinder groups — FFS, UFS, and ext4 allocate related data in localized groups to minimize seek distances.
•Skew accounts for switching delays — Track and cylinder skew offset sector numbering to enable continuous data streaming.
•Disk scheduling algorithms are cylinder-aware — SCAN, C-SCAN, LOOK, and SSTF all minimize total seek distance by ordering requests by cylinder.
•LBA abstraction hides physical cylinders — Modern systems use logical addresses, but performance still reflects the underlying physics.
•SSDs eliminate cylinder relevance — No mechanical components means cylinder concepts don't apply to solid-state storage.

What's Next:

With geometry concepts complete (platters, surfaces, tracks, sectors, cylinders), we now examine Disk Addressing (CHS, LBA)—the evolution of address schemes from physical CHS coordinates to abstract LBA block numbers, including the practical implications for boot processes, partition tables, and OS management.

Page Complete

You now understand the cylinder concept—why it exists, how it optimizes access, and its pervasive influence on file system design and disk scheduling. This foundation prepares you for understanding addressing schemes and ultimately disk geometry as presented to operating systems.

3 / 5

Loading learning content...

Operating SystemsDisk Structure

Disk Structure

LevelIntermediate

Duration60 mins

TopicDisk Structure

3 / 5

Cylinders

The Third Dimension of Disk Organization

What You Will Learn

Cylinder Definition and Geometry

1.1 Formal Definition

Mathematical Definition:

$$\text{Cylinder}_n = {\text{Track}_n \text{ on Surface } s \mid s \in {0, 1, 2, ..., 2P-1}}$$

Where:

$n$ = Cylinder number (track number on each surface)
$P$ = Number of platters
$2P$ = Number of surfaces (assuming all surfaces are active)

Visualization:

Converting Mermaid diagram...

1.2 Cylinder Capacity

The total capacity of a single cylinder can be calculated as:

$$\text{Cylinder Capacity} = \text{Surfaces} \times \text{Sectors per Track} \times \text{Bytes per Sector}$$

Example Calculation:

For a drive with:

4 platters (8 surfaces)
800 sectors per track (outer zone)
4096 bytes per sector

$$\text{Cylinder Capacity} = 8 \times 800 \times 4096 = 26,214,400 \text{ bytes} \approx 25 \text{ MB}$$

Note that due to Zoned Bit Recording (ZBR), cylinder capacity varies across the drive:

Outer cylinders (low cylinder numbers) have more sectors per track
Inner cylinders (high cylinder numbers) have fewer sectors per track

Cylinder Position	Relative Capacity	Relative Speed
Outer (Cylinder 0)	100%	100%
Middle	~75%	~75%
Inner (Cylinder N)	~50%	~50%

Head Count May Not Equal Surface Count

The Performance Rationale: Why Cylinders Matter

The cylinder concept exists because of a fundamental asymmetry in disk access times. Understanding this asymmetry reveals why cylinder-aware data placement dramatically improves performance.

2.1 Access Time Components

Reading or writing data involves three primary time components:

Component	Definition	Typical Time
Seek Time	Time to move the actuator arm to the target cylinder	3-15 ms
Rotational Latency	Time waiting for the target sector to rotate under the head	2-8 ms (avg half rotation)
Transfer Time	Time to read/write the actual data	Microseconds to milliseconds

The Key Insight:

Seek time is by far the largest component. Moving from one cylinder to another requires physical movement of the actuator arm—a mechanical operation that takes milliseconds.

Within-Cylinder Access (Fast)

•Electronic head switching only
•Switching time: ~0.5-1 ms
•No mechanical movement required
•All 8 tracks instantly accessible
•Cylinder capacity read with one seek

Cross-Cylinder Access (Slow)

•Mechanical actuator movement
•Seek time: 3-15 ms (1+ track)
•Full track-to-track: ~0.5-2 ms
•Average seek: ~8-10 ms
•Full stroke: 15-20 ms

2.2 Access Time Comparison

Scenario: Reading 25 MB of data

Assume a drive with:

8 surfaces (4 platters)
25 MB per cylinder (approximately)
7200 RPM (8.33 ms per rotation)
Average seek time: 8 ms

Option A: Data spread across 8 cylinders (8 tracks, one per cylinder)

8 seek operations: 8 × 8 ms = 64 ms
8 head switches: negligible
Data transfer: ~8 ms (one track per seek)
Total: ~80-100 ms

Option B: Data concentrated in 1 cylinder (8 tracks on same cylinder)

1 seek operation: 8 ms
7 head switches: 7 × 0.5 ms = 3.5 ms
Data transfer: ~8 ms
Total: ~20 ms

Speedup: 4-5× faster by placing related data on the same cylinder.

2.3 The Cylinder Group Optimization

This performance insight drives file system design. Intelligent file systems:

Allocate related data (files in same directory) to the same or adjacent cylinders
Keep file data and metadata on the same cylinder when possible
Group inodes and data blocks by cylinder group (e.g., ext4 block groups, FFS cylinder groups)
Minimize head movements between reads in typical access patterns

The Decline of Cylinder Awareness

Cylinders in the CHS Addressing Scheme

3.1 CHS Address Structure

A CHS address specifies:

C (Cylinder): Which cylinder (radial position), numbered 0 to max
H (Head): Which read/write head (i.e., which surface), numbered 0 to max
S (Sector): Which sector within the track, numbered 1 to max (note: 1-based!)

Address Tuple Example: CHS (500, 3, 42)

Cylinder 500 (501st cylinder from outer edge)
Head 3 (4th head, i.e., bottom surface of second platter in a 4-platter drive)
Sector 42 (42nd sector on that track)

3.2 CHS Address Space Calculation

The total addressable capacity under CHS:

$$\text{Total Sectors} = C_{\max} \times H_{\max} \times S_{\max}$$ $$\text{Capacity} = \text{Total Sectors} \times \text{Bytes per Sector}$$

CHS Limitations Through History
Interface	Max Cylinders	Max Heads	Max Sectors	Max Capacity @ 512B
Original IBM PC BIOS	1,024	16	63	504 MB
Extended INT 13h	1,024	256	63	8.4 GB
ATA-1 Specification	65,536	16	255	136.9 GB
Practical Limit	16,383	16	63	8.4 GB (BIOS limited)

3.3 Why Sector Numbering Starts at 1

Unreviewingly, CHS sector numbers are 1-based while cylinder and head numbers are 0-based. This inconsistency stems from the original IBM PC design:

Track 0, Sector 1 contains the Master Boot Record (MBR)
Zero was considered an invalid sector number for error detection
The convention persisted for backward compatibility

Consequence: Maximum sectors per track is 63, not 64, because 6 bits encode values 1-63 (not 0-63).

3.4 CHS-to-LBA Translation

The translation from CHS to LBA follows a specific formula:

$$\text{LBA} = (C \times \text{HeadsPerCylinder} + H) \times \text{SectorsPerTrack} + (S - 1)$$

The $S - 1$ accounts for the 1-based sector numbering.

Example:

CHS = (0, 0, 1) → LBA = 0 (first sector)
CHS = (0, 0, 63) → LBA = 62 (last sector of first track)
CHS = (0, 1, 1) → LBA = 63 (first sector of second track/head)

CHS and LBA Conversion Utilities
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/*
 * CHS ↔ LBA Conversion Utilities
 * 
 * These functions demonstrate the mathematical relationship between
 * physical disk geometry (CHS) and logical block addressing (LBA).
 * Modern systems use LBA exclusively, but understanding CHS is 
 * essential for boot sector analysis and legacy compatibility.
 */
 
#include <stdint.h>
#include <stdbool.h>
 
/* Drive geometry parameters */
typedef struct {
    uint16_t cylinders;        /* Total cylinders (C) */
    uint8_t  heads;            /* Heads per cylinder (H) - i.e., surfaces */
    uint8_t  sectors_per_track; /* Sectors per track (S) - typically 63 */
    uint64_t total_sectors;    /* Total LBA sectors (for verification) */
} DriveGeometry;
 
/* CHS address structure */
typedef struct {
    uint16_t cylinder;  /* 0-based, 0 to (cylinders-1) */
    uint8_t  head;      /* 0-based, 0 to (heads-1) */
    uint8_t  sector;    /* 1-based, 1 to sectors_per_track */
} CHSAddress;
 
/*
 * Convert CHS to LBA
 * 
 * Formula: LBA = ((C × H_total) + H) × S_total + (S - 1)
 * 
 * Returns: 64-bit LBA value
 */
uint64_t chs_to_lba(CHSAddress chs, const DriveGeometry* geom) {
    return ((uint64_t)chs.cylinder * geom->heads + chs.head) 
           * geom->sectors_per_track 
           + (chs.sector - 1);  /* Sector is 1-based */
}
 
/*
 * Convert LBA to CHS
 * 
 * Returns: CHS address structure
 * Note: May overflow if drive geometry doesn't match actual drive
 */
CHSAddress lba_to_chs(uint64_t lba, const DriveGeometry* geom) {
    CHSAddress chs;
    
    /* Sector is 1-based */
    chs.sector = (lba % geom->sectors_per_track) + 1;
    
    /* Remaining LBA after removing sector offset */
    uint64_t temp = lba / geom->sectors_per_track;
    
    /* Head within cylinder */
    chs.head = temp % geom->heads;
    
    /* Cylinder number */
    chs.cylinder = temp / geom->heads;
    
    return chs;
}
 
/*
 * Validate CHS address against geometry limits
 */
bool is_valid_chs(CHSAddress chs, const DriveGeometry* geom) {
    return (chs.cylinder < geom->cylinders) &&
           (chs.head < geom->heads) &&
           (chs.sector >= 1 && chs.sector <= geom->sectors_per_track);
}
 
/*
 * Calculate total drive capacity in bytes
 */
uint64_t calculate_capacity(const DriveGeometry* geom, uint16_t bytes_per_sector) {
    return (uint64_t)geom->cylinders 
           * geom->heads 
           * geom->sectors_per_track 
           * bytes_per_sector;
}
 
/*
 * Example: Working with a typical drive geometry
 */
void example_usage() {
    /* Typical BIOS-reported geometry (not real physical geometry) */
    DriveGeometry geom = {
        .cylinders = 16383,        /* Max BIOS cylinders */
        .heads = 16,               /* Heads per cylinder */
        .sectors_per_track = 63,   /* Standard sectors per track */
        .total_sectors = 16383 * 16 * 63  /* ~8.4 GB limit */
    };
    
    /* Example: Convert LBA 100000 to CHS */
    CHSAddress chs = lba_to_chs(100000, &geom);
    /* Result: cylinder=99, head=3, sector=10 */
    
    /* Verify round-trip */
    uint64_t lba_back = chs_to_lba(chs, &geom);
    /* lba_back should equal 100000 */
    
    /* Calculate 8.4 GB BIOS limit */
    uint64_t capacity = calculate_capacity(&geom, 512);
    /* capacity = 8,422,686,720 bytes ≈ 8.4 GB */
}

The 8.4 GB Barrier

Cylinder Groups in File Systems

4.1 The FFS/UFS Cylinder Group Model

The Berkeley Fast File System (later Unix File System, UFS) pioneered cylinder groups:

Design Principles:

Divide the disk into cylinder groups — Each group spans a contiguous range of cylinders
Distribute metadata across groups — Each group has its own inode table, block bitmap, and superblock backup
Allocate files within their directory's group — Files in the same directory are likely accessed together
Keep file data near its inode — Reduces seek between inode lookup and data read
Balance group utilization — Spread new directories across groups to prevent hotspots

Converting Mermaid diagram...

4.2 Cylinder Group Structure in Detail

Each cylinder group contains:

Component	Purpose	Typical Size
Superblock Copy	Redundant copy for crash recovery	1-2 blocks
Cylinder Group Descriptor	Free block/inode counts, flags	1 block
Inode Allocation Bitmap	Tracks which inodes are in use	Varies
Block Allocation Bitmap	Tracks which data blocks are in use	Varies
Inode Table	Actual inode structures for this group	Many blocks
Data Blocks	Actual file content storage	Most of group

4.3 Allocation Policy

The cylinder group allocator follows sophisticated rules:

Directory Placement:

New directories go into the cylinder group with the most free inodes and lowest existing directory count
This spreads the directory tree across groups

File Placement:

Files are allocated in the same cylinder group as their parent directory
If the parent's group is full, search nearby groups

Large File Handling:

Large files that would fill a cylinder group are split across groups
Data blocks every 48 KB (historically) would move to a new group
Balances locality with group utilization

4.4 Modern Relevance: ext4 Block Groups

Linux ext4 inherits the cylinder group concept as block groups:

ext4 Block Group Structure:
├── Superblock (copy, in some groups)
├── Group Descriptors (copies, in some groups)
├── Block Bitmap (1 block)
├── Inode Bitmap (1 block)
├── Inode Table (multiple blocks)
└── Data Blocks (bulk of group)

While ext4 doesn't strictly map block groups to physical cylinders (LBA abstraction obscures this), the principle remains:

Related files should be physically proximate
Metadata should be near its associated data
Spreading allocation prevents fragmentation hot spots

Block Group Sizing:

With 4 KB blocks and a single block for the block bitmap:

Maximum blocks per group: 32,768 (8 × 4096 bits)
Maximum group size: 128 MB

This is much smaller than physical cylinder groups, but the locality principle persists at this granularity.

The Flex Block Groups Extension

Cylinder Skew and Interleaving

5.1 The Head Switching Latency Problem

When the drive finishes reading the last sector of track N on surface 0 and switches to surface 1 to continue reading, a brief delay occurs:

Electronic switching time: ~0.5-1 ms
Servo settling time: Additional microseconds for positioning confirmation

During this delay, the platter continues rotating. If sector 0 on the next track is directly below sector 0 on the previous track, spinning for 1 ms at 7200 RPM means:

$$\text{Rotation during switch} = \frac{1 \text{ ms}}{8.33 \text{ ms/rotation}} \approx 0.12 \text{ rotations} \approx 7-8 \text{ sectors}$$

The head arrives at the new track, but sector 0 has already passed! The drive must wait almost a full rotation to read sector 0—wasting 8+ ms.

5.2 Track Skew (Head Skew)

Track skew offsets the angular position of sector numbering between adjacent tracks on the same cylinder:

Track Skew Example (8-Head Drive)
Surface	Position of Sector 0	Relative Offset
Surface 0	0° (reference)	0 sectors
Surface 1	10°	+7 sectors
Surface 2	20°	+14 sectors
Surface 3	30°	+21 sectors
Surface 4	40°	+28 sectors
Surface 5	50°	+35 sectors
Surface 6	60°	+42 sectors
Surface 7	70°	+49 sectors

With this skew, after reading the last sector of surface 0 and switching to surface 1, the head arrives just as sector 0 of surface 1 is approaching—no rotational delay.

5.3 Cylinder Skew (Track-to-Track Skew)

Cylinder skew addresses the delay when the actuator arm must move to an adjacent cylinder (seek). Even a single-track seek takes 0.5-2 ms, during which the platter rotates:

$$\text{Rotation during seek} = \frac{1 \text{ ms}}{8.33 \text{ ms/rotation}} \approx 0.12 \text{ rotations} \approx 7-8 \text{ sectors}$$

Cylinder skew offsets sector numbering between adjacent cylinders to account for seek time:

Cylinder	Position of Sector 0	Offset from Previous
Cylinder 0	0°	-
Cylinder 1	12°	+8 sectors
Cylinder 2	24°	+8 sectors
...	...	...

5.4 Modern Relevance

While modern drives handle skew internally (invisible to the OS), the concept explains:

Why sequential LBA access is optimized by drive firmware
The internal geometry is far more complex than simple CHS suggests
Performance modeling must account for head and track switching overhead

Sector Interleaving (Historical)

Cylinder Concepts in Modern Systems

While LBA has replaced CHS for addressing, and SSDs have eliminated mechanical seek entirely, the cylinder concept remains relevant in specific contexts.

6.1 LBA Abstraction: What's Hidden

Modern drives translate LBA to physical location via internal firmware:

OS Request: Read LBA 12345678
    ↓
Drive Firmware: Zone lookup → Physical cylinder, head, sector
    ↓
Actuator positions, head reads, data returned

The firmware handles:

Zone-based sector mapping (different sectors-per-track across disk)
Defect skipping (bad sectors replaced with spares)
Track skew (optimized for sequential access)
Translation tables (stored in drive NVRAM)

6.2 Where Cylinder Awareness Persists

Modern Uses of Cylinder Concepts

•Disk Forensics — Recovering data requires understanding physical layout, especially for damaged drives where firmware translation tables are lost.
•Legacy BIOS Boot — MBR-based booting still uses CHS addressing for the boot sector and partition table. BIOS reads partition start addresses in CHS format.
•RAID Controller Optimization — Some RAID controllers optimize stripe layout based on cylinder geometry for sequential performance.
•Short-Stroking — High-performance configurations use only outer cylinders for consistent low latency. Requires cylinder awareness.
•Secure Erase Verification — Verifying complete erasure may require understanding physical sector allocation patterns.
•Performance Analysis — Understanding why certain access patterns are slow requires cylinder-aware thinking (seeks vs. head switches).

6.3 SSDs: The Post-Cylinder Era

Solid-state drives eliminate cylinders entirely:

No rotating platters → No tracks or cylinders
No actuator arm → No seek time
No head switching → No cylinder-based optimization
Flash pages and blocks have different geometry

However, SSDs have their own "geometry" considerations:

SSD Geometry	Closest HDD Analog	Performance Impact
Page (4-16 KB)	Sector	Smallest read/write unit
Block (256 KB - 4 MB)	Track (sort of)	Smallest erase unit
Plane (collection of blocks)	Surface (very loosely)	Parallel operations
Die	Platter	Multiplies bandwidth

SSD "geometry" affects write amplification, wear leveling, and performance variability—topics for SSD-specific discussions.

Partition Tools and Fake Geometry

Cylinder-Based Disk I/O Scheduling

7.1 The Scheduling Challenge

When multiple I/O requests are pending, the order in which they're serviced dramatically affects total seek time:

Example Queue: Requests for cylinders [98, 183, 37, 122, 14, 124, 65, 67]

Head currently at cylinder 53

The total seek distance depends on the order of servicing.

7.2 Classic Cylinder-Aware Algorithms

Disk Scheduling Algorithms Overview
Algorithm	Strategy	Seek Distance (Example)	Characteristics
FCFS	First-Come, First-Served	640 cylinders	Fair but very inefficient; high seek distances
SSTF	Shortest Seek Time First	236 cylinders	Efficient but can starve distant requests
SCAN (Elevator)	Move in one direction, service all, reverse	331 cylinders	Predictable, fair, slightly suboptimal
C-SCAN	Move one direction, jump back to start	382 cylinders	More uniform wait times than SCAN
LOOK	Like SCAN, but reverse at last request	299 cylinders	Avoids going to disk edges unnecessarily
C-LOOK	Like C-SCAN, but reverse at last request	322 cylinders	Combines benefits of LOOK and C-SCAN

7.3 Understanding SCAN (Elevator Algorithm)

Process:

Head moves in one direction (e.g., toward higher cylinders)
Services all requests in that direction
Reaches the end of the disk (or last request in LOOK)
Reverses direction and services remaining requests

Why "Elevator"? Just like an elevator services floors in one direction before reversing, the disk head sweeps across cylinders.

Advantages:

Predictable service times
Bounded maximum wait (one full sweep + partial sweep)
Simple to implement

Disadvantages:

Cylinders at edges (0, max) get serviced less frequently than middle
Not optimal for heavy loads concentrated on one area

7.4 Modern I/O Schedulers

Linux kernel I/O schedulers build on these principles:

Scheduler	Description	Best For
noop	No reordering (FIFO)	SSDs, VMs with host-side scheduling
deadline	Prioritizes request age with cylinder sorting	Databases, latency-sensitive
cfq (Complete Fair Queuing)	Per-process queues, cylinder-sorted	Desktop responsiveness
mq-deadline	Multi-queue deadline for NVMe	Modern NVMe SSDs
bfq	Budget Fair Queueing	Interactive workloads

SCAN Algorithm Implementation
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/*
 * SCAN (Elevator) Disk Scheduling Algorithm
 * 
 * Demonstrates cylinder-based I/O request ordering.
 * This is a simplified educational implementation.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
#define MAX_REQUESTS 100
 
typedef struct {
    int cylinder;      /* Target cylinder for this request */
    int request_id;    /* Original request identifier */
    bool processed;    /* Has this request been serviced? */
} DiskRequest;
 
typedef struct {
    int current_cylinder;    /* Current head position */
    int direction;           /* 1 = toward higher cylinders, -1 = toward lower */
    int max_cylinder;        /* Maximum cylinder number */
    DiskRequest requests[MAX_REQUESTS];
    int request_count;
    int total_seek_distance;
} DiskScheduler;
 
/*
 * Add a request to the scheduler queue
 */
void add_request(DiskScheduler* sched, int cylinder, int id) {
    if (sched->request_count < MAX_REQUESTS) {
        sched->requests[sched->request_count].cylinder = cylinder;
        sched->requests[sched->request_count].request_id = id;
        sched->requests[sched->request_count].processed = false;
        sched->request_count++;
    }
}
 
/*
 * SCAN Algorithm: Service requests in current direction, then reverse
 * Returns: Service order array (by request_id)
 */
void scan_schedule(DiskScheduler* sched, int* service_order) {
    int order_idx = 0;
    int serviced = 0;
    
    while (serviced < sched->request_count) {
        int next_idx = -1;
        int min_distance = sched->max_cylinder + 1;
        
        /* Find closest request in current direction */
        for (int i = 0; i < sched->request_count; i++) {
            if (sched->requests[i].processed) continue;
            
            int distance = sched->requests[i].cylinder - sched->current_cylinder;
            
            /* Check if request is in our current direction */
            bool in_direction = (sched->direction > 0) ? 
                                (distance >= 0) : (distance <= 0);
            
            if (in_direction && abs(distance) < min_distance) {
                min_distance = abs(distance);
                next_idx = i;
            }
        }
        
        if (next_idx >= 0) {
            /* Service this request */
            sched->total_seek_distance += min_distance;
            sched->current_cylinder = sched->requests[next_idx].cylinder;
            sched->requests[next_idx].processed = true;
            service_order[order_idx++] = sched->requests[next_idx].request_id;
            serviced++;
        } else {
            /* No requests in current direction - reverse */
            sched->direction = -sched->direction;
        }
    }
}
 
/*
 * Example usage
 */
int main() {
    DiskScheduler sched = {
        .current_cylinder = 53,
        .direction = 1,        /* Start moving toward higher cylinders */
        .max_cylinder = 199,
        .request_count = 0,
        .total_seek_distance = 0
    };
    
    /* Add requests for cylinders: 98, 183, 37, 122, 14, 124, 65, 67 */
    add_request(&sched, 98, 1);
    add_request(&sched, 183, 2);
    add_request(&sched, 37, 3);
    add_request(&sched, 122, 4);
    add_request(&sched, 14, 5);
    add_request(&sched, 124, 6);
    add_request(&sched, 65, 7);
    add_request(&sched, 67, 8);
    
    int service_order[MAX_REQUESTS];
    scan_schedule(&sched, service_order);
    
    printf("SCAN Schedule (starting at cylinder 53, direction: up):
");
    printf("Service order: ");
    for (int i = 0; i < sched.request_count; i++) {
        printf("%d ", service_order[i]);
    }
    printf("
Total seek distance: %d cylinders
", sched.total_seek_distance);
    
    return 0;
}
 
/* Expected output:
 * Service order: 7 8 1 4 6 2 3 5
 * (Cylinders: 65, 67, 98, 122, 124, 183, then reverse: 37, 14)
 * Total seek distance: ~299 cylinders (LOOK variant)
 */

Native Command Queuing (NCQ)

Summary: Cylinders

We have explored the three-dimensional concept of disk cylinders—the vertical alignment of tracks across all platters. Let's consolidate the key insights:

Key Takeaways

•A cylinder is all tracks at the same radius — Spanning all surfaces, accessible with head switching alone (no seek).
•Within-cylinder access is fast — Electronic head switching (~0.5ms) vs. mechanical seeks (3-15ms) makes cylinder-local data far faster to access.
•CHS addressing encodes cylinder position — Historical addressing directly specified cylinder, head, sector—revealing physical geometry.
•File systems optimize via cylinder groups — FFS, UFS, and ext4 allocate related data in localized groups to minimize seek distances.
•Skew accounts for switching delays — Track and cylinder skew offset sector numbering to enable continuous data streaming.
•Disk scheduling algorithms are cylinder-aware — SCAN, C-SCAN, LOOK, and SSTF all minimize total seek distance by ordering requests by cylinder.
•LBA abstraction hides physical cylinders — Modern systems use logical addresses, but performance still reflects the underlying physics.
•SSDs eliminate cylinder relevance — No mechanical components means cylinder concepts don't apply to solid-state storage.

What's Next:

Page Complete

3 / 5