Disk structure and access time

Why it exists

A disk is where programs, files and databases live, and it is millions of times slower than memory. Reading one byte takes the same time as reading a whole track, because almost all of the time goes into moving the arm and waiting for the platter to turn. So GATE asks two kinds of questions: bookkeeping (how big is the disk, how many bits name a sector, which sector number is the address ⟨c, h, s⟩, in which cylinder does a file end) and timing (how long does it take to read one sector, a file of $n$ sectors, a file scattered over the disk). This page gives the model, the formulas and the traps. How the operating system orders the requests is on the disk scheduling page.

Prerequisites

The disk is the bottom level of the memory hierarchy: the largest, cheapest and slowest level.

Precise definitions

Structure. A disk has one or more platters on a common spindle that turns at a fixed speed in revolutions per minute (rpm). Each platter has two surfaces (a recording surface is one side). Each surface is divided into concentric tracks, each track into sectors, the smallest unit that can be read or written. One head per surface, all mounted on one arm, moves together; the tracks that the heads are over at one arm position form a cylinder.

• tracks on one surface $=$ number of cylinders $C$; surfaces $H$; sectors per track $S$; bytes per sector $B$;
• tracks on the disk $= C \cdot H$; sectors $= C \cdot H \cdot S$;
• $\text{capacity} = C \cdot H \cdot S \cdot B, \qquad \text{track capacity} = S \cdot B.$

A question that gives the capacity asks for one unknown from this product (for example the number of cylinders $= \text{capacity} / (H \cdot S \cdot B)$).

Units. In GATE questions $1\,\text{KB} = 2^{10}$, $1\,\text{MB} = 2^{20}$, $1\,\text{GB} = 2^{30}$ bytes for sizes, but a transfer rate such as "$50 \times 10^6$ bytes per second" is decimal as written. Convert before you divide.

Addresses. A sector is named by the triple $\langle c, h, s \rangle$ (cylinder, surface, sector), each field counted from $0$. Its sector number (position in the whole sequence) depends on how files are laid out. GATE uses the cylinder-wise layout: fill a track, then the next surface of the same cylinder (no arm movement), then the next cylinder:

$n = (c \cdot H + h) \cdot S + s, \qquad c = \lfloor n / (H S) \rfloor, \quad h = \lfloor n / S \rfloor \bmod H, \quad s = n \bmod S.$

A sector can be named by one number, needing $\lceil \log_2 (C H S) \rceil$ bits, or by the three fields, needing $\lceil \log_2 C \rceil + \lceil \log_2 H \rceil + \lceil \log_2 S \rceil$ bits. The two are equal when $C$, $H$ and $S$ are powers of two and the second is larger otherwise; read which one the question asks for.

Time to access a sector.

$T_{access} = T_{seek} + T_{rot} + T_{transfer} \;(+\; T_{controller}).$

• $T_{rev} = 60 / \text{rpm}$ seconds per revolution.
• Seek $T_{seek}$: moving the arm to the cylinder; usually given (an average, or a track-to-track time). For uniformly random requests the average distance is about one third of the number of tracks.
• Rotational latency: waiting for the sector to arrive under the head: between $0$ and $T_{rev}$, on average half a revolution, $T_{rot} = \tfrac{1}{2} T_{rev}$.
• Transfer: the wanted bytes pass under the head: $T_{transfer} = \dfrac{\text{bytes}}{S \cdot B} \cdot T_{rev} = \dfrac{\text{bytes}}{\text{data rate}}$, with data rate $= S B / T_{rev}$. One sector takes $T_{rev} / S$.
• Controller overhead, when the question gives it (for example "ten times the disk transfer time"), is added.

Reading a file. Scattered sectors pay seek + rotation + transfer every time: $n\,(T_{seek} + T_{rot} + T_{sector})$. A contiguous file pays one seek and one rotational wait, and then streams: $T_{seek} + T_{rot} + n\,T_{sector}$ (plus a track switch each time it crosses to the next track).

GATE model and real hardware. GATE model: a constant $S$ on every track, sector numbers from $0$, the formulas above. Real hardware: outer tracks are longer and hold more sectors (zoned bit recording), so $S$ depends on the track and the sector number is no longer a simple formula; the legacy CHS address counts sectors from $1$ (so $n = (cH + h)S + (s - 1)$); modern drives hide the geometry behind logical block addresses and remap bad sectors. Flash storage (SSD) has no arm and no rotation, so none of the timing formulas apply to it.

How it works

The tables below are filled one row at a time. Every number is computed by a script from exact arithmetic, not typed.

Capacity and the size of an address. Four disks; the tracks, sectors and capacity follow from the product, and the two ways of naming a sector need different numbers of bits (Disk Y: 19 bits as one number, 20 as three fields).

From ⟨cylinder, surface, sector⟩ to a sector number. One cylinder of Disk Y holds $10 \times 50 = 500$ sectors, so each step in the cylinder field adds 500, each step in the surface field adds 50 and each step in the sector field adds 1.

And back. Two integer divisions: by the sectors per cylinder (the quotient is the cylinder), then the rest by the sectors per track (the quotient is the surface, the rest the sector).

Rotation and access time. The faster the spindle, the shorter the revolution and the wait; the transfer of one sector is tiny next to the seek and the wait.

Reading a file. The same 800-sector file, scattered or contiguous. Paying the seek and the wait once instead of 800 times makes the contiguous read over 300 times faster; and a layout that ignores the rotation when it changes tracks loses a whole revolution each time.

Worked examples

#include <stdio.h>
 
static int bits(long n) {
    int b = 0;
    while ((1L << b) < n) b++;
    return b;
}
 
int main(void) {
    long geo[2][4] = {{2000, 8, 400, 512}, {1000, 10, 50, 512}};   /* cylinders, surfaces, sectors per track, bytes per sector */
    for (int i = 0; i < 2; i++) {
        long c = geo[i][0], h = geo[i][1], s = geo[i][2], b = geo[i][3];
        long sectors = c * h * s;
        printf("disk %d: %ld tracks, %ld sectors, capacity %ld bytes (%.3f MiB)\n", i + 1, c * h, sectors, sectors * b, sectors * b / 1048576.0);
        printf("        sector number: %d bits; fields: %d + %d + %d = %d bits\n", bits(sectors), bits(c), bits(h), bits(s), bits(c) + bits(h) + bits(s));
    }
    /* a disk of 64 GiB with 16 surfaces, 2048 sectors per track of 512 bytes: how many cylinders? */
    long capacity = 64L << 30, h = 16, s = 2048, b = 512;
    printf("64 GiB disk: cylinders = %ld\n", capacity / (h * s * b));
    return 0;
}

disk 1: 16000 tracks, 6400000 sectors, capacity 3276800000 bytes (3125.000 MiB)
        sector number: 23 bits; fields: 11 + 3 + 9 = 23 bits
disk 2: 10000 tracks, 500000 sectors, capacity 256000000 bytes (244.141 MiB)
        sector number: 19 bits; fields: 10 + 4 + 6 = 20 bits
64 GiB disk: cylinders = 4096

#include <stdio.h>
 
#define CYL 1000L
#define SURF 10L
#define SECT 50L
 
static long to_number(long c, long h, long s) { return (c * SURF + h) * SECT + s; }
 
int main(void) {
    printf("<37,6,12> is sector %ld\n", to_number(37, 6, 12));
    long n = 123456;
    printf("sector %ld is <%ld,%ld,%ld>\n", n, n / (SURF * SECT), (n / SECT) % SURF, n % SECT);
 
    /* every address in cylinder-major order must get the next number, and the inverse must give the address back */
    long expect = 0, bad = 0;
    for (long c = 0; c < CYL; c++)
        for (long h = 0; h < SURF; h++)
            for (long s = 0; s < SECT; s++) {
                long m = to_number(c, h, s);
                if (m != expect) bad++;
                if (m / (SURF * SECT) != c || (m / SECT) % SURF != h || m % SECT != s) bad++;
                expect++;
            }
    printf("checked %ld sectors, %ld mismatches\n", expect, bad);
 
    /* a file of 20000 KB (sectors of 512 bytes) stored contiguously from <120,7,30> */
    long sectors = 20000L * 1024 / 512;
    long first = to_number(120, 7, 30), last = first + sectors - 1;
    printf("file: %ld sectors, from number %ld to %ld, last sector <%ld,%ld,%ld>\n", sectors, first, last, last / (SURF * SECT), (last / SECT) % SURF, last % SECT);
    return 0;
}

<37,6,12> is sector 18812
sector 123456 is <246,9,6>
checked 500000 sectors, 0 mismatches
file: 40000 sectors, from number 60380 to 100379, last sector <200,7,29>

#include <stdio.h>
 
int main(void) {
    double rpm = 10000, seek = 6.0, spt = 200;           /* ms */
    double rev = 60000.0 / rpm, latency = rev / 2, sector = rev / spt;
    printf("revolution %.3f ms, average latency %.3f ms, one sector %.3f ms\n", rev, latency, sector);
    printf("one random sector: %.3f ms\n", seek + latency + sector);
    double n = 300;
    printf("300 sectors scattered: %.3f ms\n", n * (seek + latency + sector));
    printf("300 sectors contiguous, free track switches: %.3f ms\n", seek + latency + n * sector);
    printf("ratio %.1f\n", n * (seek + latency + sector) / (seek + latency + n * sector));
    return 0;
}

revolution 6.000 ms, average latency 3.000 ms, one sector 0.030 ms
one random sector: 9.030 ms
300 sectors scattered: 2709.000 ms
300 sectors contiguous, free track switches: 18.000 ms
ratio 150.5

#include <stdio.h>
 
int main(void) {
    double rev = 60.0 / 10000;                 /* seconds */
    double latency = rev / 2;
    double seek = 3 * latency;
    double transfer = 512 / 40e6;
    double controller = 5 * transfer;
    printf("latency %.4f ms, seek %.4f ms, disk transfer %.6f ms, controller %.6f ms\n", latency * 1e3, seek * 1e3, transfer * 1e3, controller * 1e3);
    printf("average time %.4f ms\n", (seek + latency + transfer + controller) * 1e3);
    return 0;
}

latency 3.0000 ms, seek 9.0000 ms, disk transfer 0.012800 ms, controller 0.064000 ms
average time 12.0768 ms

Cheat box

Traps and GATE patterns

Connections

The disk is the slowest level of the memory hierarchy; its cost per access is what caches and buffer pools exist to hide. The operating system chooses the order of requests to cut the seek part in disk scheduling, lays files out contiguously or in blocks in file allocation, and the data then moves by DMA. A database computes how many blocks a file or an index occupies from the block size and the record size in file organisation, because every block touched is one disk access of the kind computed here.

PYQs

Consider a typical disk that rotates at 15000
rotations per minute (RPM) and has a transfer rate
of 50 × 106 bytes /sec. If the average seek time of
the disk is twice the average rotational delay and
the controller's transfer time is 10 times the disk
transfer time, the average time (in milliseconds) to
read or write a 512-byte sector of the disk is .

Consider a disk pack with a seek time of 4
milliseconds and rotational speed of 10000 rotations
per minute (RPM). It has 600 sectors per track and
each sector can store 512 bytes of data. Consider a file
stored in the disk. The file contains 2000 sectors
Assume that every sector access necessitates a seek,
And the average rotational latency for accessing each
sector is half of the time for one complete rotation.
The total time (in milliseconds) needed to read the
entire file is

Consider a hard disk with 16 recording surfaces (0-
15) having 16384 cylinders (0-16383) and each
Computer Organization and Architecture

cylinder contains 64 sectors (0-63). Data storage
capacity in each sector is 512 bytes. Data are
organized cylinder-wise and addressing format is
<cylinder no., surface no., sector no>. A file of
size 42797 KB is stored in the disk and the starting
disk location of the file is < 1200, 9, 40>. What is
the cylinder number of the last sector of the file, if
it is stored in a contiguous manner?

An application loads 100 libraries at start-up.
Loading each library requires exactly one disk
access. The seek time of the disk to a random
location is given as 10 ms . Rotational speed of disk
is 6000 rpm . If all 100 libraries are loaded from
random locations on the disk, how long does it take
to load all libraries? (The time to transfer data from
the disk block once the head has been positioned at
the start of the block may be neglected.)

Consider the disk drive with the following
specifications: 16 surfaces, 512 tracks/surface, 512
sectors/track, 1 KB/sector, rotation speed 3000
rpm. The disk is operated in cycle stealing mode
whereby whenever one byte is ready it is sent to
memory, similarly, for writing, the disk interface
reads a 4-byte word from the memory in each
DMA cycle. Memory cycle time is 40 nsec The
maximum percentage of time that the CPU gets
blocked during DMA operation is

Consider a hard disk with a rotational speed of
15000 rpm. The time to move the read/write head
from a track to its adjacent track is 1 millisecond.
Initially, the head is on track 0. The number of
sectors per track is 400, and the sector size is 1024
bytes.

It is necessary to transfer data from 10 randomly
located sectors in each of the following tracks in the
order: 5, 12, and 7.

The total time for the data transfer (in milliseconds)
from
the
hard
disk
is
______.
(rounded off to one decimal place)

Consider a disk with the following specifications:
rotation speed of 6000 RPM, average seek time of
5 milliseconds, 500 sectors/track, 512-byte sectors.
A file has content stored in 3000 sectors located
randomly on the disk. Assuming average rotational
latency, the total time (in seconds, rounded off to 2
decimal places) to read the entire file from the disk is
______

Consider a 512 GB hard disk with 32 storage
surfaces. There are 4096 sectors per track and each
sector holds 1024 bytes of data. The number of
cylinders in the hard disk is ______

Consider a typical disk that rotates at 15000 rotations
per minute (RPM) and has a transfer rate of 50 ×
106bytes/sec. If the average seek time of the disk is
twice the average rotational delay and the controller's
transfer time is 10 times the disk transfer time, the
average time (in milliseconds) to read or write a 512-
byte sector of the disk is ______

Consider a disk pack with a seek time of 4
milliseconds and rotational speed of 10000 rotations
per minute (RPM). It has 600 sectors per track and
each sector can store 512 bytes of data. Consider a file
stored in the disk. The file contains 2000 sectors.
Assume that every sector access necessitates a seek,
and the average rotational latency for accessing each
sector is half of the time for one complete rotation.
The total time (in milliseconds) needed to read the
entire file is ______

Consider a hard disk with 16 recording surfaces (0–
15) having 16384 cylinders (0–16383) and each
cylinder contains 64 sectors (0–63). Each sector
stores 512 bytes. Data are organized cylinder-wise
and the addressing format is (cylinder no., surface
no., sector no.). A file of size 42797 KB is stored
starting at disk location (1200, 9, 40). What is the
cylinder number of the last sector of the file, if it is
stored contiguously?

An application loads 100 libraries at startup. Loading
each library requires exactly one disk access. The
seek time of the disk to a random location is given as
10 ms. Rotational speed of disk is 6000 rpm. If all 100
libraries are loaded from random locations on the
disk, how long does it take to load all libraries? (The
time to transfer data from the disk block once the head
has been positioned at the start of the block may be
neglected.)

A hard disk has 63 sectors per track, 10 platters each
with 2 recording surfaces and 1000 cylinders. The
address of a sector is given as a triple (c,h,s), where c
is the cylinder number, h is the surface number and s
is the sector number. Thus, the 0th sector is addressed
as ⟨0,0,0⟩, the 1st sector as ⟨0,0,1⟩, and so on.

The address ⟨400,16,29⟩ corresponds to sector
number:

A hard disk has 63 sectors per track, 10 platters
each with 2 recording surfaces and 1000 cylinders.
The address of a sector is given as a triple (c,h,s),
where c is the cylinder number, h is the surface
number and s is the sector number. Thus, the 0th
sector is addressed as ⟨0,0,0⟩, the 1st sector as
⟨0,0,1⟩, and so on.

The address of 1039th sector is

Consider a disk pack with 16 surfaces, 128 tracks per
surface and 256 sectors per track. 512 bytes of data
are stored in a bit serial manner in a sector. The
capacity of the disk pack and the number of bits
required to specify a particular sector in the disk pack
are respectively:

Self-check

Revision card

References