Esercizio 14algoritmi di scheduling del disco

In questa pagina 4

Testo (svolto in aula, lezione del 7 novembre 2016). L'informazione sul disco è organizzata in cilindri e settori. Si considerino gli algoritmi di selezione della prossima richiesta:

FCFS: le richieste sono servite nell'ordine di arrivo;
SSTF (shortest seek time first): si serve la richiesta più vicina al cilindro corrente;
ascensore (elevator): la testina avanza o retrocede verso il cilindro più vicino senza cambiare direzione finché esistono richieste in quella direzione.

Sia data la sequenza di richieste per i cilindri 10, 20, 15, 5, 40, 8, 35, arrivate in quest'ordine. Assumendo un costo di 5 ms per lo spostamento della testina da un cilindro a uno adiacente e che la testina abbia appena finito di servire una richiesta sul cilindro 15, determinare il costo complessivo di posizionamento per ciascun algoritmo, con l'ordine di servizio.

Il costo è (numero di cilindri attraversati) × 5 ms. Vedi Memoria esterna - dischi, RAID e memorie ottiche.

FCFS

Spostamento	15→10	10→20	20→15	15→5	5→40	40→8	8→35
Cilindri	5	10	5	10	35	32	27

Totale $124$ cilindri → $124 \cdot 5 =$ 620 ms.

SSTF

La richiesta sul 15 si serve subito (0 cilindri). Poi 10 e 20 sono alla stessa distanza (5): si provano entrambe.

Prima il 10: 15 → 15 (0) → 10 (5) → 8 (2) → 5 (3) → 20 (15) → 35 (15) → 40 (5). Totale 45 cilindri → 225 ms.
Prima il 20: 15 → 15 (0) → 20 (5) → 10 (10) → 8 (2) → 5 (3) → 35 (30) → 40 (5). Totale 55 cilindri → 275 ms.

La scelta migliore è passare prima per il 10: 225 ms.

Ascensore

Direzione iniziale verso l'alto: 15 (0) → 20 (5) → 35 (15) → 40 (5), non ci sono altre richieste sopra, si inverte → 10 (30) → 8 (2) → 5 (3). Totale 60 cilindri → 300 ms.
Direzione iniziale verso il basso: 15 (0) → 10 (5) → 8 (2) → 5 (3), si inverte → 20 (15) → 35 (15) → 40 (5). Totale 45 cilindri → 225 ms (stessa sequenza di SSTF).

Confronto

Algoritmo	Cilindri	Tempo
FCFS	124	620 ms
SSTF	45 (o 55)	225 ms (o 275)
ascensore	45 (giù) o 60 (su)	225 o 300 ms

FCFS è il più equo ma il più costoso. SSTF e ascensore rinunciano all'ordine di arrivo in cambio di efficienza; l'ascensore in più cambia direzione una sola volta, riducendo lo sforzo meccanico del braccio.

Versione ripasso

Testo (svolto in aula, lezione del 7 novembre 2016). L'informazione sul disco è organizzata in cilindri e settori. Si considerino gli algoritmi di selezione della prossima richiesta:

FCFS: le richieste sono servite nell'ordine di arrivo;
SSTF (shortest seek time first): si serve la richiesta più vicina al cilindro corrente;
ascensore (elevator): la testina avanza o retrocede verso il cilindro più vicino senza cambiare direzione finché esistono richieste in quella direzione.

Metodo: costo = cilindri attraversati $\times$ 5 ms (Memoria esterna - dischi, RAID e memorie ottiche); la richiesta sul 15 costa 0.

FCFS (15, 10, 20, 15, 5, 40, 8, 35): $5 + 10 + 5 + 10 + 35 + 32 + 27 = 124$ cilindri $\to$ 620 ms.
SSTF: 10 e 20 sono alla stessa distanza. Prima il 10: 15, 10, 8, 5, 20, 35, 40 con $5 + 2 + 3 + 15 + 15 + 5 = 45$ cilindri $\to$ 225 ms. Prima il 20: 15, 20, 10, 8, 5, 35, 40 con $5 + 10 + 2 + 3 + 30 + 5 = 55$ cilindri $\to$ 275 ms. Migliore: 225 ms.
Ascensore verso l'alto: 15, 20, 35, 40, poi 10, 8, 5: $5 + 15 + 5 + 30 + 2 + 3 = 60$ cilindri $\to$ 300 ms. Verso il basso: 15, 10, 8, 5, poi 20, 35, 40: $5 + 2 + 3 + 15 + 15 + 5 = 45$ cilindri $\to$ 225 ms.

FCFS è il più equo e il più costoso; l'ascensore inverte la direzione una sola volta.

Lezioni in cui compare

Lezione 13 · RAID ed esercizi sui dischi

Teoria collegata

Memoria esterna - dischi, RAID e memorie ottiche