Algoritmi di scheduling del disco

Ciao! Oggi vorrei presentarvi alcuni algoritmi di scheduling del disco.
Come dice wikipedia (http://en.wikipedia.org/wiki/I/O_scheduling), lo scheduling del disco serve per decidere in fase di lettura (o scrittura) quali blocchi verranno letti prima e quali blocchi verrano letti un secondo momento.
Questi algoritmi, come tutti, possono essere efficienti o meno, possono risparmiare tempo come risorse e non è sempre detto che algoritmi che abbassano al minimo la somma dei seek time siano in tutti i casi meglio di altri.

Quando al disco viene data una coda di richieste si può soddisfare con i seguenti algoritmi:

• (FIFO) o (FCFS) First In, First Out, conosciuto anche come First Come First Served;
• (SSTF) Shortest seek first, conosciuto anche come Shortest Seek / Service Time First;
• (SCAN) Algoritmo dell'ascensore (includendo le varianti, C-SCAN, LOOK, e C-LOOK);
• (RSS) Random scheduling;
• (LIFO) Last In, First Out;
• Noop scheduler;
• Deadline scheduler.

In questo post vi mostrerò solo i FCFS, SSTF, SCAN, LOOK, C-SCAN, C-LOOK.

Per tutti gli esempi seguirò il seguente schema:

• dimensione del disco: 1000 cilindri, numerati da 0 a 999
• coda delle richieste: 500, 700, 100, 200, 10, 390, 800, 250, 750
• posizione iniziale della testina sul cilindro: 400
• spostamento traccia da n a n±1: 1ms

NOTA BENE: nel caso troviate errori nei calcoli e/o nei grafici vi prego di segnalarmeli. Grazie!

FCFS (First Come First Served)

Come dice il nome vengono servite le richieste nell'ordine in cui arrivano.

Nel nostro esempio l'ordine di chiamata è: 500, 700, 100, 200, 10, 390, 800, 250, 750.
Quindi: (500-400) + (700-500) + (700-100) + (200-100) + (200-10) + (390-10) + (800-390) + (800-250) + (750-250) = 3030

Il tempo per soddifsare le richieste è: 2930ms 3030ms

SSTF (Shortest Seek Time First)

Questo algoritmo di scheduling sceglie la richiesta con seek time minore rispetto alla posizione corrente. Se ad esempio le richieste sono 100, 150, 160, 300, l'ordine in cui l'algoritmo le sceglierà, a partire da 150, sarà: [160, 100, 300].

Nota: Per comodità riodino la lista delle richieste [10, 100, 200, 250, 390, 500, 700, 750, 800]

Nel nostro esempio l'ordine di chiamata è: 390, 500, 700, 750, 800, 250, 200, 100, 10

Il tempo per soddifsare le richieste è: 10+110+200+50+50+550 +50+100+90 = 1210ms

Shorted Seek Time First è un algoritmo molto efficiente anche se potenzialmente può essere soggetto a starvation ("morire di fame").

SCAN

L'algoritmo SCAN serve in una direzione e quando arriva al bordo del disco cambia direzione servendo i rimanenti elementi.

Nel nostro esempio l'ordine di chiamata è: 500, 700, 750, 800, (999), 390, 250, 200, 100, 10. 

Il tempo per soddifsare le richieste è: 1588ms.

Una volta arrivato alla fine tornando indietro serve le richieste rimanenti.

LOOK

Il funzionamento è identico all'algoritmo di SCAN. L'unica differenza è che con questo algoritmo non è necessario raggiungere i bordi del disco. 

Nel nostro esempio l'ordine di chiamata è: 500, 700, 750, 800, 390, 250, 200, 100, 10. 

Il tempo per soddifsare le richieste è: 1190ms.

C-SCAN (Circular SCAN)

La testina segue le richieste in ordine (da una parte o dall'altra, in genere si procede seguendo un ordine crescente) finchè non arriva all'estremo del disco. Una volta arrivato all'estremo del disco torna al'inizio (senza servire richieste) e riparte.

Nel nostro esempio l'ordine di chiamata è: 500, 700, 750, 800, (999), (0), 10, 100, 200, 250, 390. 

Il tempo per soddifsare le richieste è: 989ms.

I numeri tra parentesi sono i "bordi" del disco. Vanno sommati anche i tempi per raggiungere i bordi o distaccarsi da essi!

C-LOOK (Circular LOOK)

Questo algoritmo è una variante dell'algoritmo C-SCAN. Con questo algoritmo non è neccessario arrivare fino ai bordi del disco.

Nel nostro esempio l'ordine di chiamata è: 500, 700, 750, 800, (790), 10, 100, 200, 250, 390. 

Il tempo per soddifsare le richieste è: 790ms.

Sostanzialmente è una miglioria di C-SCAN.




Quando ho cercato informazioni sullo scheduling del disco non ho trovato molto, quindi spero che questo post possa aiutarvi ed esservi utile!