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

Sistemi Operativi (Ingegneria informatica ed elettronica)

Algoritmi di scheduling disco tutti (FCFS, SS, SST, Cscan, ride …)

– 16

Allocazione di file contigua e con lista indicizzate –

17

Paginazione multilivello – 18

16. Descrivere gli 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 hannopiù 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 ed all'ammontare dei dati trasferiti). Occorre conoscere posizione iniziale, direzione di spostamento. Gestione degli errori su disco: generalmente è il driver del disco che gestisce gli errori che possono essere: - errori di programmazione (richiesta di settori inesistenti) - errori di checksum (transitori o permanenti) - errori di posizionamento (recalibrare) 17. Metodi diallocazione dei file

I tre principali metodi di allocazione dei file sono: allocazione contigua, allocazione con liste e allocazione indicizzata.

Contigua: ogni file deve occupare un insieme di blocchi contigui sul disco (allocati al momento della creazione del file). È il metodo di implementazione più semplice ma richiede di sapere a priori la dimensione del file. Questo provoca problemi di frammentazione (pezzi di memoria sprecati) e di espansione del file (se è finito lo spazio libero nella memoria riservata a quel specifico file).

Con liste: ogni file è composto da una lista concatenata di blocchi del disco i quali possono essere sparsi in qualsiasi punto della memoria (risolvendo così i problemi dell'allocazione contigua). Posso sfruttare anche piccole parti di memoria "spargendo" questi blocchi e assegnandogli i corretti puntatori (ogni blocco ha un puntatore che punta al blocco successivo): in questo modo il file può crescere di

dimensione fino a che ci sarà spazio nella memoria (anche in punti diversi). Il problema di questo tipo di allocazione è che non garantisce un efficiente accesso diretto al file: i puntatori sono contenuti nei blocchi e di conseguenza sono sparsi nella memoria. Questo fa sì che durante la lettura bisogna saltare accedendo a parti diverse di memoria per accedere al punto desiderato.

Indicizzata: risolve il problema individuato nell'allocazione con liste, raggruppando tutti i puntatori in un'unica locazione, il blocco indice. Ogni file possiede un blocco indice che contiene diversi elementi: l'elemento i-esimo contiene l'indirizzo in memoria dell'i-esimo blocco costituente il file (garantendo così un costo minore durante l'accesso). Il costo aggiuntivo di questo metodo di allocazione è dato dal fatto di tenere questo blocco indice, mentre prima non era necessario.

18. Paginazione multilivello Quando il numero dei bit utilizzato

Dal calcolatore per l'indirizzamento raggiunge valori elevati (32 o 64 bit), l'enorme dimensione della tabella delle pagine (utilizzata per la traduzione di indirizzi virtuali nei rispettivi indirizzi fisici) diventa proibitiva.

Una soluzione a questo tipo di problema è la paginazione multilivello: si suddivide la tabella delle pagine in parti più piccole e si creano più livelli di indirizzamento.