Algoritmo dell'ascensore

L'algoritmo dell'ascensore (anche detto SCAN) è un algoritmo di disk scheduling per stabilire l'ordine in cui devono essere processate le richieste di lettura e richieste di scrittura su disco rigido.

L'algoritmo funziona in maniera simile al shortest seek time first (SSTF) ma, a differenza di quest'ultimo, viene scelto il cilindro con il minore seek time solo nella direzione in cui si sta muovendo la testina, la quale si sposta continuamente avanti e indietro attraversando tutte le tracce del disco.^[1]

Il nome dell'algoritmo (in inglese elevator algorithm) deriva proprio da questo movimento bidirezionale.

Descrizione

Se arriva una nuova richiesta mentre l'unità di I/O è inattiva, il movimento iniziale della testina sarà in direzione della traccia in cui i dati sono/saranno memorizzati. Appena arrivano ulteriori richieste, vengono elaborate solo se compatibili con la direzione corrente del movimento del braccio, fino a quando la testina non raggiunge il bordo (interno o esterno) del disco. Quando ciò accade, la direzione del braccio viene invertita, e le richieste rimaste in attesa vengono servite.^[2]

Varianti

Una variante di questo algoritmo garantisce che tutte le richieste vengano servite in una sola direzione. Ciò è implementabile, quando la testina giunge al bordo del disco, facendola ripartire dall'estremo opposto. Questo algoritmo è l'"algoritmo dell'ascensore circolare" (circular elevator algorithm), meglio noto come C-SCAN (o circular SCAN).^[2]

Dell'algoritmo SCAN sono state implementate anche altre varianti, fra cui:

FSCAN
LOOK (e C-LOOK)
N-Step-SCAN

Note

^ Gestione dei buffer e I/O scheduling (PDF), su dis.uniroma1.it, MIDLAB (Middleware Laboratory) - La Sapienza. URL consultato il 25 gennaio 2015 (archiviato dall'url originale il 23 febbraio 2005).
^ ^a ^b (EN) Disk scheduling, su dcs.ed.ac.uk, Università di Edimburgo, Department of Informatics. URL consultato il 21 gennaio 2008 (archiviato dall'url originale il 6 giugno 2008).

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica

[1] Gestione dei buffer e I/O scheduling (PDF), su dis.uniroma1.it, MIDLAB (Middleware Laboratory) - La Sapienza. URL consultato il 25 gennaio 2015 (archiviato dall'url originale il 23 febbraio 2005).

[ed.ac.uk-2] (EN) Disk scheduling, su dcs.ed.ac.uk, Università di Edimburgo, Department of Informatics. URL consultato il 21 gennaio 2008 (archiviato dall'url originale il 6 giugno 2008).

[1]

[2]