Esercizio - Scheduling del disco con FCFS, SSTF, SCAN e C-SCAN (slide di memoria di massa, eserciziario, esercizio 95)

Parte 1: l'esempio delle slide

Distanza fra due cilindri $a$ e $b$: $|a-b|$. Testina in 53, richieste da servire: $98,183,37,122,14,124,65,67$.

FCFS (nell'ordine di arrivo): $53\to98\to183\to37\to122\to14\to124\to65\to67$.

Totale $=45+85+146+85+108+110+59+2=\mathbf{640}$ cilindri.

SSTF (sempre la più vicina): da 53 la più vicina è 65 (distanza 12), poi 67 (2), poi 37 (30), poi 14 (23), poi 98 (84), 122 (24), 124 (2), 183 (59):

$$12+2+30+23+84+24+2+59=\mathbf{236}.$$

SCAN (ascensore). La testina parte verso il cilindro 0 (direzione scelta dalla slide) servendo 37 e 14, arriva a 0, inverte e sale servendo 65, 67, 98, 122, 124, 183:

$$(53-0)+(183-0)=53+183=\mathbf{236}.$$

Se la direzione iniziale fosse verso l'alto: $53\to199$ (146), poi $199\to14$ servendo 37 e 14 (185): totale $\mathbf{331}$. Lo SCAN dipende dalla direzione iniziale.

C-SCAN. Si sale servendo 65, 67, 98, 122, 124, 183, si arriva a 199, si torna subito a 0 senza servire nulla, poi si sale a servire 14 e 37:

$$(199-53)+(199-0)+(37-0)=146+199+37=\mathbf{382}$$

(contando il ritorno di 199 cilindri; senza contarlo, $146+37=183$).

Varianti: LOOK (SCAN che si ferma all'ultima richiesta, verso il basso poi verso l'alto: $39+169=208$) e C-LOOK (si va solo fino alla richiesta più alta, $130$, poi si torna alla più bassa, $169$, poi $23$: $322$).

Parte 2: esercizio 95

La testina è su 50. Si usa la regola "dopo ogni completamento si sceglie, fra le richieste già arrivate, la più vicina nella direzione corrente; se non ce ne sono si inverte". All'inizio la prima richiesta arriva in salita (traccia 70 contro 50), quindi la direzione è verso l'alto.

Sequenza di servizio: $1,4,3,5,7,8,2,6$, con istanti di completamento (ms) $22, 27, 32, 72, 102, 112, 127, 132$. È la stessa tabella della soluzione del corso.

Osservazioni:

• a $t=22$ la 2 (65) è già pendente ma è dietro la testina (70): sale prima su 75 e 80;
• a $t=72$ la 7 (90) è arrivata a $t=38$ e viene servita solo dopo l'inversione: parte a $t=72$, dopo 34 ms di attesa;
• la richiesta 8 (80) arriva a $t=100$, durante il servizio della 7, e viene presa durante la discesa, prima della 2 e della 6.

Un simulatore in C

Il programma calcola lo spostamento totale con i quattro algoritmi della parte 1 (non gestisce gli istanti di arrivo della parte 2). Si compila con gcc -Wall -Wextra -o disco disco.c (compilato qui con zig cc per Linux, senza avvisi; non eseguito).

/* disco.c - spostamento totale della testina con FCFS, SSTF, SCAN e C-SCAN.
 * Compilare:  gcc -Wall -Wextra -o disco disco.c
 * Usare:      ./disco 53 98 183 37 122 14 124 65 67
 *             (la prima e' la posizione della testina, le altre le richieste;
 *              il disco ha i cilindri da 0 a 199)
 */
#include <stdio.h>
#include <stdlib.h>

#define MAXC 199 /* ultimo cilindro */

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; }

static int fcfs(int testina, const int *r, int n) {
    int tot = 0;
    for (int i = 0; i < n; i++) { tot += dist(testina, r[i]); testina = r[i]; }
    return tot;
}

static int sstf(int testina, const int *r, int n) {
    int fatto[64] = {0}, tot = 0;
    for (int passo = 0; passo < n; passo++) {
        int migliore = -1;
        for (int i = 0; i < n; i++)
            if (!fatto[i] && (migliore < 0 || dist(testina, r[i]) < dist(testina, r[migliore])))
                migliore = i;
        fatto[migliore] = 1;
        tot += dist(testina, r[migliore]);
        testina = r[migliore];
    }
    return tot;
}

/* SCAN: prima verso 0 fino in fondo, poi verso l'alto fino all'ultima richiesta */
static int scan(int testina, int *ord, int n) {
    int tot = 0, sotto = 0, max = testina;
    for (int i = 0; i < n; i++) {
        if (ord[i] < testina) sotto++;
        if (ord[i] > max) max = ord[i];
    }
    if (sotto > 0) tot += testina - 0; /* scende fino al cilindro 0 */
    else return max - testina;         /* niente sotto: si va solo in su */
    if (max > testina) tot += max - 0; /* poi risale fino alla richiesta piu' alta */
    return tot;
}

/* C-SCAN: verso l'alto fino a MAXC, ritorno a 0 (conta), poi fino all'ultima richiesta bassa */
static int cscan(int testina, int *ord, int n) {
    int tot = 0, alto = 0, maxbasso = -1;
    for (int i = 0; i < n; i++) {
        if (ord[i] >= testina) alto++;
        else if (ord[i] > maxbasso) maxbasso = ord[i];
    }
    if (alto > 0) tot += MAXC - testina;
    if (maxbasso >= 0) tot += MAXC + maxbasso; /* ritorno 199 -> 0, poi 0 -> maxbasso */
    return tot;
}

int main(int argc, char **argv) {
    if (argc < 3 || argc > 60) { fprintf(stderr, "uso: %s testina r1 r2 ...\n", argv[0]); return 1; }
    int testina = atoi(argv[1]), n = argc - 2, r[64], ord[64];
    for (int i = 0; i < n; i++) ord[i] = r[i] = atoi(argv[i + 2]);
    qsort(ord, (size_t)n, sizeof ord[0], cmp);

    printf("FCFS   %d\n", fcfs(testina, r, n));
    printf("SSTF   %d\n", sstf(testina, r, n));
    printf("SCAN   %d\n", scan(testina, ord, n));
    printf("C-SCAN %d\n", cscan(testina, ord, n));
    return 0;
}

Con l'esempio della slide l'output atteso è FCFS 640, SSTF 236, SCAN 236, C-SCAN 382 (valori calcolati con lo stesso metodo in Python). Lo SCAN del programma scende prima verso 0.

Errori tipici

• Fare servire a SCAN una richiesta dietro la testina prima di aver finito la direzione corrente.
• Considerare nelle scelte anche le richieste non ancora arrivate (nell'esercizio 95, la 7 a $t=32$).
• Dimenticare di contare l'andata fino all'estremo (0 o 199) in SCAN e C-SCAN puri, o il ritorno in C-SCAN.
• Non specificare la direzione iniziale dello SCAN: cambia il risultato (236 contro 331).
• Dimenticare che la testina aspetta ferma quando non ci sono richieste (da $t=0$ a $t=2$).