Part 3 of 7 · 5 min read
FCFS and SSTF
Think of two shoppers. One walks the aisles in the order of the list on paper. The other always grabs the nearest item. The second walks less, and an item at the far end of the shop may wait a long time. The analogy stops in one place: a shopper chooses the order once, and a disk queue keeps receiving new items while the arm moves.
In plain words: FCFS (first come, first served) serves requests in arrival order. It is fair and simple and it can move the arm a long way. SSTF (shortest seek time first) always serves the waiting request that is nearest to the head. It moves the arm much less, and it can starve a far request if new nearby requests keep arriving.
A worked example. FCFS on the queue 95, 180, 34, 119, 11, 123, 62, 64 with the head at 50 moves 45, 85, 146, 85, 108, 112, 61 and 2 cylinders, in total 644. At 0.05 ms per cylinder this costs 32.2 ms. SSTF serves 62, 64, 34, 11, 95, 119, 123, 180 and moves 12, 2, 30, 23, 84, 24, 4 and 57 cylinders. The total is 236, which costs 11.8 ms. SSTF moves the arm 63% less.
The key lines. This C program computes all the totals of sections 2 to 4 for one queue.
#include <stdio.h>
#include <stdlib.h>
#define N 8
#define MAXCYL 199
static int dist(int a, int b) { return abs(a - b); }
static int cmp(const void *a, const void *b) { return *(const int *)a - *(const int *)b; }
int main(void) {
int q[N] = {95, 180, 34, 119, 11, 123, 62, 64};
int start = 50, pos, total;
pos = start; total = 0; /* FCFS */
for (int i = 0; i < N; i++) { total += dist(pos, q[i]); pos = q[i]; }
printf("FCFS %d\n", total);
int done[N] = {0}; /* SSTF */
pos = start; total = 0;
printf("SSTF order:");
for (int k = 0; k < N; k++) {
int best = -1;
for (int i = 0; i < N; i++)
if (!done[i] && (best < 0 || dist(pos, q[i]) < dist(pos, q[best]))) best = i;
total += dist(pos, q[best]); pos = q[best]; done[best] = 1;
printf(" %d", pos);
}
printf("\nSSTF %d\n", total);
int s[N]; for (int i = 0; i < N; i++) s[i] = q[i];
qsort(s, N, sizeof s[0], cmp);
int first_up = 0; while (first_up < N && s[first_up] < start) first_up++;
total = (MAXCYL - start) + (MAXCYL - s[0]); /* SCAN, up first */
printf("SCAN (up first) %d\n", total);
total = (s[N - 1] - start) + (s[N - 1] - s[0]); /* LOOK, up first */
printf("LOOK (up first) %d\n", total);
total = (MAXCYL - start) + MAXCYL + s[first_up - 1]; /* C-SCAN, return counted */
printf("C-SCAN (up) %d\n", total);
total = (s[N - 1] - start) + (s[N - 1] - s[0]) + (s[first_up - 1] - s[0]); /* C-LOOK */
printf("C-LOOK (up) %d\n", total);
return 0;
}
Output on the test machine:
FCFS 644
SSTF order: 62 64 34 11 95 119 123 180
SSTF 236
SCAN (up first) 337
LOOK (up first) 299
C-SCAN (up) 382
C-LOOK (up) 322
Starvation. Suppose the head is at 100 and a request for cylinder 190 waits. A new request arrives for each request that is served: 101, then 99, then 102, then 98 and so on. At each step a nearby request is closer than 190, so SSTF never serves it. The request for 190 waits for as long as the stream lasts. FCFS cannot do this, because an old request is always served before newer ones.
Starvation
Starvation is a state in which a request or a process waits for an unbounded time because other requests are always chosen before it. It is a failure of fairness and not of correctness, since every single choice may look reasonable.
Example: under SSTF a request for cylinder 190 may wait without end while requests near cylinder 100 keep arriving.
Check yourself: 1. In the worked example, which request makes FCFS expensive? 2. Why does SSTF give a lower total than FCFS here? 3. Does SSTF find the best possible order? Think of a queue of 50, 51, 49, 52, 48 with the head at 50.