Sartomiki.net

Realizzazione delle directory
Esistono principalmente due metodi per la realizzazione delle directory in un file system:
-lista concatenata. In questo caso i file contenuti in una directory sono contenuti in una lista lineare, contenente i nomi dei file e i puntatori ai blocchi di dati. Questo metodo è facilmente implementabile anche se è poco efficiente: una ricerca impiega nel caso peggiore un tempo O(n), una scrittura implica una prima ricerca, per verificare se il nome del file non sia già presente e una scrittura in fondo alla lista. Per migliorare i tempi di ricerca è possibile impiegare cache oppure usare liste ordinate, mediante l'utilizzo di B-alberi. La cancellazione consiste in una ricerca lineare ed una successiva liberazione dello spazio, che può avvenire in diversi modi:
--contrassegnando il file come non usato.
--aggiungendo il file ad una lista di oggetti non usati.
--copiando l'ultima locazione utilizzata in quella liberata e diminuendo le dimensioni della directory.
-tabella di hash. Secondo questo metodo si utilizza una lista lineare, per contenere gli elementi della directory, e una tabella di hash. La tabella di hash permette di ricavare la posizione dei file all'interno della lista ordinata, dato il nome, con un tempo di ricerca molto basso. Le maggiori difficoltà di implementazione di una tabella di hash, sono principalmente dovute al fatto che deve avere una dimensione fissa, in quanto una variazione della dimensione, causerebbe il ricalcolo di tutte le locazioni di memoria. Per evitare collisioni è necessario sostituire ogni elemento della tabella di hash con una lista di elementi.

Metodi di allocazione dei file
Solitamente i dischi permettono l'accesso diretto, garantendo quindi una certa flessibilità nell'allocazione dei file, in modo che il loro accesso sia efficiente e che tutto lo spazio a disposizione venga utilizzato. Alcuni sistemi operativi mettono a disposizione diversi metodi di allocazione per i file, altri invece ne rendono possibile solo uno tra:
-allocazione contigua, che prevede che ogni file debba occupare un insieme di blocchi contigui dello stesso disco. Una volta letto il primo blocco di un file, è possibile leggere i successivi in breve tempo, in quanto non è richiesto lo spostamento della testina, se non nel caso in cui si passi da un settore di un cilindro al cilindro successivo. L'allocazione contigua prevede, inoltre, che in una tabella del file system venga segnalato per ogni file, l'indirizzo di partenza e la lunghezza del file stesso (espressa in numero di blocchi). Il principale problema di cui soffre l'allocazione contigua è l'individuazione di spazio libero per nuovi file, in quanto gli algoritmi (uguali a quelli per l'allocazione della memoria principale) soffrono del problema della frammentazione esterna. Per rendere utilizzabile questo metodo è necessaria una procedura di compattazione (spesso molto onerosa, a meno che questa operazione non avvenga off-line, nel senso che il disco rimanga inutilizzabile durante tale processo).  Un ulteriore problema dell'allocazione contigua riguarda il fatto che una volta che si è allocato lo spazio per un file, esso non può essere esteso, nel caso in cui siano presenti altri file contigui. Per risolvere questo problema si può sovrastimare le dimensioni del file oppure riallocare lo spazio del file (frammentazione interna). Alcuni OS utilizzano un metodo di allocazione contigua modificato: per un file viene allocato una porzione di memoria prefissata, che, nel caso in cui risulti insufficiente, può essere ampliata con un'estensione di lunghezza fissata dall'utente (frammentazione interna).
-allocazione concatenata, che prevede che ogni file possa essere "sparso" per l'intero disco. Nella tabella dei file della directory è presente un record per ogni file, che indica il nome, l'indirizzo del blocco di partenza e l'indirizzo del blocco di fine del file. Ogni blocco, in una parte riservata di memoria, contiene il puntatore al blocco successivo, in modo da permettere di ricostruire il file. Questo metodo elimina completamente il problema della frammentazione esterna e permette file di lunghezza variabile. Il problema principale di questo metodo è che non è possibile effettuare l'accesso diretto per ogni parte del file, ma è possibile solo l'accesso sequenziale. Un altro problema è la quantità di memoria per ogni blocco, che viene sprecata per la memorizzazione dei puntatori. Per diminuire l'overhead, solitamente, si allocano un gruppo di blocchi contigui, detti cluster, ad uno stesso file, anziché allocare solo blocchi (aumenta la frammentazione interna). Un ulteriore problema è dato dall'affidabilità, in quanto, la perdita di un puntatore renderebbe illeggibile l'intero file. Una variante del metodo di allocazione concatenata prevede l'utilizzo di una file allocation table (FAT), contenuta in una parte del volume riservata (e caricata in RAM al momento del montaggio del file system). Le FAT non sono altro che delle tabelle, che contengono l'indirizzo del blocco successivo, dato il numero di un blocco. Le FAT, se caricate in una cache, consentono l'accesso diretto e un incremento notevole delle prestazioni.
-allocazione indicizzata, prevede la creazione di un blocco indice per ogni file. La directory memorizza per ogni file l'indirizzo dell'indice corrispondente. L'indice contiene l'elenco di tutti i blocchi utilizzati da ciascun file. Il tempo di accesso determinato da un'allocazione indicizzata non risulta essere troppo rapido, in quanto i blocchi dei dati si trovano sparsi per l'intero file system. Nel caso in cui l'indice risulti troppo piccolo per contenere tutti i blocchi di un file:
--schema concatenato, prevede di collegare tra loro più blocchi indice, per creare un blocco indice più grande
--indice a più livelli, prevede la creazione di un blocco indice di primo livello, che punta ad un insieme di blocchi indice di secondo livello.
--schema combinato, prevede che i primi record dell'indice puntino direttamente a un blocco, mentre i restanti puntino a blocchi indice. Questa tecnica è usata dall'UFS (gli inode contengono un certo numero di link a blocchi fisici, un indirizzo a un indice di secondo livello, un indirizzo ad un indice di terzo livello e un indirizzo ad un indice di terzo livello).
E' importante notare che non esiste in assoluto un metodo di allocazione migliore di un altro, in quanto dipende dal tipo di accesso e dallo scopo di ogni file. E' per questo motivo che alcuni sistemi prevedono di gestire i file ad accesso sequenziale utilizzando lo schema contiguo, mentre l'allocazione concatenata per i file che richiedono l'accesso diretto. In questi sistemi è possibile modificare il tipo del file copiando il vecchio file in uno nuovo. Alcuni sistemi prevedono di utilizzare l'allocazione contigua, per i file di piccola dimensione, e l'allocazione indicizzata, per i file più grossi. L'allocazione indicizzata per file piccoli creerebbe un overhead troppo consistente.
Sono inoltre possibili migliaia di ottimizzazioni implementate dai sistemi operativi, in quanto l'esecuzione di alcune centinaia di migliaia di istruzioni in più della CPU risulta essere molto più rapida di un'operazione di lettura/scrittura in più.

Gestione dello spazio libero
Siccome lo spazio dei dischi non è illimitato è necessario rilasciare la memoria non più utilizzata. Il sistema conserva una lista dello spazio libero, dove sono registrate tutte le locazioni di memoria disponibili. Esso può essere implementato in diversi modi:
-vettore di bit, che consiste in una mappa di bit, in cui ogni blocco è rappresentato da un bit: se esso è a 0 il blocco è assegnato, se a 1 è libero. Questo metodo è facilmente implementabile ed efficiente, in quanto basta controllare il valore di ogni riga per trovare un tot di blocchi contigui disponibili. Questa implementazione risulta utilizzabile se è possibile mantenere il vettore in memoria principale, per evitare continui accessi in memoria secondaria.
-lista concatenata, che viene implementata collegando, tramite puntatori una cella libera ad un'altra. Questa strategia non è molto efficiente, in quanto per ottenere n blocchi liberi si necessitano di n accessi in memoria.
-raggruppamento, che consiste nel memorizzare in ciascun blocco in un certo numero di blocchi liberi. In questo modo è possibile ricavare un buon numero di blocchi liberi con un solo accesso in memoria.
-conteggio, prevede di memorizzare l'indirizzo di un blocco libero, e il numero di locazioni contigue libere.

Efficienza e prestazioni
Esistono diversi accorgimenti per aumentare l'efficienza di un file system. Molti di essi dipendono principalmente dalla struttura del file system e dalle tecniche di realizzazione delle directory e di allocazione dei file.
Ad esempio in UNIX, gli inode vengono allocati preventivamente in una parte del disco, in modo tale che i blocchi di dati che verranno inseriti nelle directory, si trovino fisicamente vicini agli inode corrispondenti. In questo modo non saranno necessari molti spostamenti della testina per spostarsi dai dati all'inode.
Un altro accorgimento viene invece effettuato da BSD UNIX nello schema di file system basato su cluster. I cluster variano per dimensione e precisamente quelli più grandi vengono utilizzati per i file di grossa dimensione, mentre quelli più piccoli vengono utilizzati per i file più piccoli e le parti finali dei file di grosse dimensioni; grazie a questo metodo la frammentazione interna causata dai cluster diminuisce.
Questi sono solo due esempi che garantiscono una gestione efficiente di un file system, ma ne esistono moltissimi altri (basati ad esempio sulla frequenza di utilizzo di alcune informazioni legate ad un file o sulla dimensione dei puntatori).
Molto spesso i dischi sono muniti di una cache interna, in grado di memorizzare un'intera traccia del disco. Questa cache viene gestita dal controllore del disco e solitamente aumenta in modo considerevole le prestazioni del disco.
Alcuni OS riservano una sezione della memoria centrale come cache del disco, dove viene tenuta traccia dei blocchi usati, in previsione di un loro riutilizzo. Altri OS, invece, usano la memoria principale come cache delle pagine per memorizzare file, considerandoli formati da pagine anziché da blocchi. Altri OS, come Solaris, Linux e Windows usano la memoria principale delle pagine per memorizzare sia i processi sia i dati dei file (memoria virtuale unificata). L'esistenza di queste cache portano a volte problemi di gestione della memoria: un fenomeno che si può riscontrare è quello del double caching, che è causato dal fatto che la cache del disco non si può interfacciare direttamente con la cache delle pagine. E' per questo motivo che alcuni sistemi, come UNIX, utilizzano una cache unificata.
L'algoritmo LRU per la sostituzione dei blocchi dalle cache è in generale il più usato, anche se non è sempre la soluzione migliore. Siccome reperire informazioni provenienti da dispositivi di I/O sono molto più onerose del reperimento delle pagine, in Solaris 7 , il modulo di sostituzione dei dati in cache prediligeva eliminare i blocchi contenenti pagine, piuttosto che dati di I/O. In Solaris 8 è stato stabilito il rapporto minimo tra pagine e I/O. In Solaris 9 e 10 sono stati modificati ancora gli algoritmi di sostituzione.
Un altro fattore che può condizionare l'efficienza di una scrittura su disco può essere anche il fatto che essa possa avvenire in modo asincrono oppure no. Le scritture sincrone avvengono nell'ordine in cui le riceve il sottosistema del disco e non vengono memorizzate provvisoriamente. Le scritture asincrone prevedono che il blocco venga scritto prima che l'applicazione possa proseguire l'esecuzione (in questo caso è meglio utilizzare cache). Alcuni OS ottimizzano gli algoritmi di sostituzione delle pagine, anche in base a questo fattore.
Un altra tecnica per gestire in modo ottimale le cache è quella della lettura anticipata, che prevede che vengano memorizzate in cache preventivamente, oltre al blocco richiesto, anche i blocchi successivi.