Disk scheduling

Why it exists

A hard disk has a moving arm that must travel to the right track before any data can be read. That movement (the seek) takes milliseconds, thousands of times longer than the CPU takes to run an instruction, and it dominates the time of a disk access. When several processes have requests waiting, the order in which the OS serves them decides how far the head moves in total, and therefore how long they wait. Disk scheduling chooses that order. GATE gives a head position and a request queue and asks for the total head movement under each algorithm, or which algorithm gives the least movement or avoids starvation.

Prerequisites

The disk's geometry is covered by the (not yet written) page on secondary storage, so the facts used here are recalled below. The I/O request normally ends in a DMA transfer.

Precise definitions

Disk structure. A disk has platters with surfaces; each surface is divided into concentric tracks, each track into sectors. The tracks at the same position on all surfaces form a cylinder. A head on a movable arm reads and writes. A disk address is (cylinder, head, sector) or a logical block number mapped to that.

Access time for one request:

$T_{access} = T_{seek} + T_{rotational\ latency} + T_{transfer}.$

• Seek time: moving the arm to the requested cylinder (roughly proportional to the distance plus a start-up time).
• Rotational latency: waiting for the wanted sector to rotate under the head, on average half a revolution: $\frac{1}{2} \cdot \frac{60}{\text{RPM}}$ seconds.
• Transfer time: for the wanted data to pass under the head: (data size / data on one track) $\times$ one revolution time.

Seek time is the largest of the three and the only one that scheduling can reduce, so the algorithms try to minimize head movement, the total number of tracks crossed.

Algorithms. The head is at track $h$, and the requests are for tracks $r_1, \ldots, r_n$ (tracks $0, \ldots, N - 1$). A request queue is the list of pending requests.

Total head movement is $\sum |p_k - p_{k-1}|$ over the positions the head visits. For the sweeps, with the head moving toward higher tracks first, $U$ the highest request and $D$ the lowest request below the head, $L = N - 1$ the last track:

• LOOK: $(U - h) + (U - D)$ (if requests exist on both sides);
• SCAN: $(L - h) + (L - D)$;
• C-LOOK: $(U - h) + (U - D) + (D' - D)$, where $D'$ is the highest request below the head;
• C-SCAN: $(L - h) + L + D'$ (the return from $L$ to 0 counted).

Conventions that change the answer. (1) Initial direction: the question normally says it; otherwise the head is assumed to move toward the nearer end or toward higher tracks. (2) SCAN after reversing stops at the last request; some solutions continue to track 0, which changes the number. (3) Return sweep in C-SCAN and C-LOOK: counted as head movement in some solutions, not in others; check what the question asks (the page gives both). (4) Rotational delay is ignored by these algorithms.

Choosing. Under light load FCFS is fine. SSTF is simple and good but unfair. SCAN and C-SCAN (and their LOOK versions) perform better under heavy load because they cannot starve a request. The performance depends on how the file system lays out files: contiguous files need less head movement.

How it works

The animations use one request list so that the totals can be compared: a disk with tracks 0 to 199, head at track 40, pending requests 82, 170, 43, 140, 24, 16, 190. The head path is drawn with time going down the page; the dots at the top are the requests (orange, turning green when served); the counter shows the head movement so far.

FCFS serves in arrival order and crosses the disk several times: 652 tracks.

SSTF always goes to the nearest pending request: 204 tracks, but the far requests wait. (A different order, down to 16 first and then up, would need only 198.)

SCAN moves up to the end of the disk (199), reverses, and serves 24 and 16 on the way down: 342.

LOOK turns back at 190, the last request: 324.

C-SCAN serves upward, goes to 199, returns to 0, and sweeps up again to 16 and 24: 382 counting the return sweep (183 without it).

C-LOOK turns at 190 and jumps to the lowest request, 16, then sweeps up to 24: 332 counting the jump (158 without it).

Worked examples

#include <stdio.h>
 
int main(void) {
    /* 7200 rpm disk, average seek 9 ms, 200 sectors of 512 bytes per track */
    double rpm = 7200, seek = 9, sectors = 200;
    double rotation = 60000.0 / rpm;                 /* ms per revolution */
    double latency = rotation / 2;                   /* on average half a revolution */
    double transfer = rotation / sectors;            /* one sector passes under the head */
    printf("one revolution %.3f ms, average rotational latency %.3f ms, transfer of one sector %.3f ms\n", rotation, latency, transfer);
    printf("average access time for one sector: %.3f ms (seek %.0f + latency %.3f + transfer %.3f)\n", seek + latency + transfer, seek, latency, transfer);
    printf("data rate: %.2f MB/s\n", sectors * 512 / (rotation / 1000) / 1e6);
    return 0;
}

one revolution 8.333 ms, average rotational latency 4.167 ms, transfer of one sector 0.042 ms
average access time for one sector: 13.208 ms (seek 9 + latency 4.167 + transfer 0.042)
data rate: 12.29 MB/s

#include <stdio.h>
#include <stdlib.h>
 
#define N 7
#define TRACKS 200
 
static const int req[N] = {82, 170, 43, 140, 24, 16, 190};
static const int start = 40;
 
static int cmp(const void *a, const void *b) { return *(const int *)a - *(const int *)b; }
 
int main(void) {
    int sorted[N];
    for (int i = 0; i < N; i++) sorted[i] = req[i];
    qsort(sorted, N, sizeof sorted[0], cmp);
    int below = 0;                                  /* requests below the head */
    while (below < N && sorted[below] < start) below++;
    int lo = sorted[0], hi = sorted[N - 1], last = TRACKS - 1;
    int upmax = below < N ? hi : start, downmin = below > 0 ? lo : start;
 
    int fcfs = 0, cur = start;
    for (int i = 0; i < N; i++) { fcfs += abs(req[i] - cur); cur = req[i]; }
 
    int sstf = 0, done[N] = {0};
    cur = start;
    for (int k = 0; k < N; k++) {
        int best = -1;
        for (int i = 0; i < N; i++)
            if (!done[i] && (best < 0 || abs(req[i] - cur) < abs(req[best] - cur))) best = i;
        sstf += abs(req[best] - cur); cur = req[best]; done[best] = 1;
    }
 
    int look = (upmax - start) + (upmax - downmin);
    int scan = (last - start) + (last - downmin);
    int clook = (upmax - start) + (upmax - downmin) + (sorted[below - 1] - downmin);
    int cscan = (last - start) + last + sorted[below - 1];
    printf("FCFS %d, SSTF %d\nSCAN %d, LOOK %d\nC-SCAN %d (counting the return sweep), C-LOOK %d (counting the jump)\n", fcfs, sstf, scan, look, cscan, clook);
    printf("C-SCAN without counting the return sweep: %d; C-LOOK without the jump: %d\n", cscan - last, clook - (upmax - downmin));
    return 0;
}

FCFS 652, SSTF 204
SCAN 342, LOOK 324
C-SCAN 382 (counting the return sweep), C-LOOK 332 (counting the jump)
C-SCAN without counting the return sweep: 183; C-LOOK without the jump: 158

Cheat box

Traps and GATE patterns

Connections

The order of requests is decided by the OS, but the data then moves by DMA. The disk's geometry and timing are in secondary storage. Like CPU scheduling, the aim is to order a queue to cut waiting, and the same trade between average and fairness applies (SSTF is to disks what SJF is to the CPU: good on average, can starve). The I/O subsystem places the requests in the queue, and the layout chosen by file allocation decides how far apart the requests of a file are.

PYQs

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 the following five disk access requests of
the form (request id, cylinder number) that are present
in the disk scheduler queue at a given time:

(P, 155), (Q, 85), (R, 110), (S, 30), (T, 115)

Assume the head is positioned at cylinder 100. The
scheduler follows
Shortest
Seek Time
First
scheduling to service the requests.

Which one of the following statements is FALSE?

Consider a storage disk with 4 platters (numbered
as 0, 1, 2 and 3), 200 cylinders (numbered as 0, 1,
..., 199), and 256 sectors per track (numbered as 0,
1, ... 255). The following 6 disk requests of the
form [sector number, cylinder number, platter
number] are received by the disk controller at the
same time:
[120, 72, 2], [180, 134, 1], [60, 20, 0], [212, 86, 3],
[56, 116, 2], [118, 16, 1]

Currently the head is positioned at sector number
100 of cylinder 80, and is moving towards higher
cylinder numbers. The average power dissipation in
moving the head over 100 cylinders is 20 milliwatts
and for reversing the direction of the head
movement once is 15 milliwatts. Power dissipation
associated with rotational latency and switching of
head between different platters is negligible.

The total power consumption in milliwatts to
satisfy all of the above disk requests using the
Shortest Seek Time First disk scheduling algorithm
is ______ .

Consider a disk queue with requests for I/O to
blocks on cylinders 47, 38, 121, 191, 87, 11, 92, 10.
The C-LOOK scheduling algorithm is used. The
head is initially at cylinder number 63, moving
towards larger cylinder numbers on its servicing
pass. The cylinders are numbered from 0 to 199.
The total head movement (in number of cylinders)
incurred while servicing these requests is
___________.

Suppose the following disk request sequence (track
numbers) for a disk with 100 tracks is given: 45, 20,
90, 10, 50, 60, 80, 25, 70. Assume that the initial
position of the R/W head is on track 50. The
additional distance that will be traversed by the R/W
head when the Shortest Seek Time First (SSTF)
algorithm is used compared to the SCAN (Elevator)
algorithm (assuming that SCAN algorithm moves
towards 100 when it starts execution) is _________
tracks.

Suppose a disk has 201 cylinders, numbered from
0 to 200. At some time the disk arm is at cylinder
100, and there is a queue of disk access requests for
cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If
Shortest-Seek Time First (SSTF) is being used for
scheduling the disk access, the request for cylinder
90 is serviced after servicing ____________
number of requests.

Consider a disk system with 100 cylinders. The
requests to access the cylinders occur in following
sequence :

4, 34, 10, 7, 19, 73, 2, 15, 6, 20.

Assuming that the head is currently at cylinder 50,
what is the time taken to satisfy all requests if it takes
1 ms to move from one cylinder to adjacent one and
the shortest seek time first policy is used ?

For a magnetic disk with concentric circular tracks,
the seek latency is not linearly proportional to the
seek distance due to

Self-check

Revision card

References