Disks and disk scheduling

A hard disk drive (HDD) has spinning platters, each with rings called tracks, divided into sectors. The tracks at the same position on every platter form a cylinder. An arm moves the read/write heads in and out.

Reading a sector takes three steps:

(7200 revolutions per minute is 120 per second, so one turn takes 1/120 s = 8.33 ms, and half a turn 4.17 ms.)

Seeking is the slowest part, so when many requests are waiting, the order in which the OS serves them matters a lot.

The algorithms

These are the textbook numbers: cylinders 0 to 199, the head at 53, and requests 98, 183, 37, 122, 14, 124, 65, 67. FCFS moves 640 cylinders; SSTF 236. Switch algorithms and directions, and open Compare.

Books differ on one point: whether the circular algorithms' jump back counts as head movement. The simulator counts it and also shows the total without it, so you can match your textbook.

#include <stdio.h>
#include <stdlib.h>

#define N 8

int main(void) {
    int request[N] = {98, 183, 37, 122, 14, 124, 65, 67};
    int served[N] = {0};
    int head = 53, total = 0;

    for (int k = 0; k < N; k++) {
        int best = -1;
        for (int i = 0; i < N; i++)        /* the nearest request not yet served */
            if (!served[i] && (best < 0 || abs(request[i] - head) < abs(request[best] - head)))
                best = i;
        total += abs(request[best] - head);
        head = request[best];
        served[best] = 1;
        printf("%d ", head);
    }
    printf("\ntotal head movement: %d cylinders\n", total);
    return 0;
}

SSDs

A solid-state drive (SSD) has no moving parts: every block is equally fast to reach, so seek-based scheduling does not help, and Linux mostly uses simple FCFS-like schedulers for them. SSDs have their own problems: a block can be written only a limited number of times, so the drive spreads writes evenly (wear levelling), and the OS tells it which blocks are free with TRIM.

RAID

RAID combines several disks into one, for speed, safety or both:

Parity is the XOR of the data blocks, so any one missing block can be rebuilt from the others. RAID is not a backup: deleting a file deletes it from every disk at once.

Mark lesson complete