Sistemi operativi: algoritmi di scheduling del disco, allocazione di file contigua con liste indicizzate, paginazione multilivello

Argomenti più comuni esame di sistemi operativi

Ingegneria informatica ed elettronica

• Algoritmi di scheduling disco (FCFS, SS, SST, C-SCAN, ride…)
• Allocazione di file contigua e con lista indicizzate
• Paginazione multilivello

Algoritmi di scheduling del disco

Gli algoritmi di scheduling del disco servono a stabilire l'ordine in cui il driver del disco deve eseguire le richieste di lettura/scrittura generate dai processi in esecuzione sui sistemi.

• Algoritmo FCFS: Le richieste sono evase a seconda del loro tempo di arrivo. Non introduce problemi di starvation. Ha basse prestazioni per accessi frequenti (tuttavia sufficiente per sistemi mono-utente) es. slide 30 in raccolta slide I/O.
• Algoritmo SSFT (Shortest Seek Time First): Viene evasa per prima la traccia con il tempo di ricerca (seek time) inferiore, a partire dalla posizione corrente della testina. Si può verificare la starvation: le richieste lontane dal centro ottengono un pessimo servizio (al limite potrebbero essere rinviate all’infinito). Di solito si comporta meglio del FCFS.
• Algoritmo SCAN: Scansiona il disco da traccia 0 a traccia massima ogni volta, servendo le richieste mentre attraversa i cilindri finché non completa il tragitto. A questo punto, il braccio inverte la marcia e la procedura continua. Quindi le testine attraversano continuamente il disco nelle due direzioni.
• Algoritmo C-SCAN: La scansione è sempre nella stessa direzione. Tempi di attesa più uniformi rispetto allo SCAN (anche se ha tempi maggiori). Quando la testina giunge all’altro estremo del disco, ritorna immediatamente all’inizio del disco stesso, senza servire le richieste durante il viaggio di ritorno (tuttavia l’ammontare dello spostamento da una parte all’altra viene comunque considerato).
• Algoritmo LOOK e C-LOOK: Sono rispettivamente come SCAN e C-SCAN, ma non necessitano di raggiungere la traccia minima e massima. Quando non hanno più richieste in una direzione, la cambiano (LOOK) o ripartono (C-LOOK). Esiste un limite superiore al movimento della testina: uno spostamento di due volte il numero di tracce necessariamente permette di soddisfare qualunque coda di richieste. Performance molto buone per carichi elevati.

Confronto di algoritmi

La valutazione si basa su un modello di richieste: distanza totale che deve compiere la testina, tempo richiesto (proporzionale alla distanza), tempi di latenza e di trasferimento vengono ignorati perché non possono essere sotto il controllo del SO (dipendono dall'hardware e dall'ammontare dei dati trasferiti).