:: Capitolo 12: Implementazione del file system ::
Torna alla pagina di Sistemi Operativi
12.1 Struttura del file system
Il compito del file system è quello di far reperire le informazioni in modo rapido. Sono due i problemi per realizzare il file system:
1.Come far apparire il file system all'utente;
2.Come memorizzare il file system logico nel disco.
Il file system è composto da livelli:
1.Controllo dell'I/O: gestisce interruzioni fra memoria principale e dispositivi;
2.File system di base: gestisce comandi generici per leggere e scrivere blocchi fisici dal disco;
3.Modulo di organizzazione dei file: gestisce l'organizzazione dei blocchi fisici in modo da ricostruire ogni file;
4.File system logico: gestisce i metadati (informazioni che descrivono la struttura interna del file system).
12.2.1 Panoramica sulla realizzazione del file system
Il file system contiene diverse informazioni riguardanti:
- Blocco di controllo del boot: contiene informazioni necessarie per l'avvio del sistema;
- Blocco di controllo della partizione: contiene dei dettagli sulla partizione (num blocchi liberi/occupati ecc.);
- Directory: organizzano i file;
- Blocchi di controllo di file: contengono dettagli sui file (permessi, dimensione, posizione dei blocchi occupati).
Il file system contiene informazioni anche riguardanti la memoria:
- tabella delle partizioni: contiene informazione sulle partizioni;
- descrittori della directory;
- Tabella dei file aperti: contiene copia del FCB di ogni file aperto;
- Tabella dei file aperti per ogni processo: contiene puntatore all'elemento appropriato nella tabella dei file aperti.
Per creare un file bisogna effettuare una chiamata di sistema per il file system che crea un nuovo FCB e aggiorna la sua directory (dove verrà posizionato il file). Per operare su tale file lo si deve prima aprire. Aprire un file consiste nel portare nella tabella dei file aperti il suo FCB. La chiamata open() restituisce un puntatore che punta al file aperto nella tabella. Tutte le operazioni avverranno mediante quel puntatore. Al solito si usa un contatore per sapere quanti processi stanno usando questo file. Quanto il contatore è peri a 0 si può togliere il file dalla tabella dei file aperti.
12.2.2 Partizioni e montaggio
Ci possono essere più partizioni su un disco:
- disco grezzo: partizioni senza un file system particolare;
- partizioni per avvio del computer: contiene una sequenza di blocchi da caricare in memoria;
Per sistemi che hanno più sistemi operativi installati è necessario un avvio duplice, all'avvio viene caricato un loader in memoria, il quale può far scegliere che sistema far partire.
Partizione radice-> è quella partizione che contiene il codice del kernel, essa viene montata al momento dell'avvio. Solo dopo che è stata montata si possono montare tutte altre partizioni. Si mantiene una tabella di montaggio per sapere appunto quale e che tipo di file system è stato montato.
12.2.3 File system virtuali
Per realizzare file system diversi posso realizzare delle procedure per ogni tipo di file system. Questo metodo non è ottimale.
Per isolare le chiamate di sistema di base dai dettagli implementativi suddivido il file system in tre livelli principali:
1.Interfaccia del file system;
2.File system virtuale (VFS);
3.Rete.
Vantaggi file system virtuale:
- Separa le operazioni generiche dalla loro realizzazione-> consente accesso trasparente;
- il VFS è basato sulla rappresentazione del file, detta vnode il quale contiene identificatore univoco del file. Unicità richiesta nella rete.
Il VSF distingue i file system remoti da quelli locali, distinguendo ulteriormente questi ultimi in base al loro tipo.
12.3 Realizzazione delle directory
Le directory possono essere realizzate in modi diversi, ognuno dei quali presenta pro e contro.
12.3.1Lista
Metodo più semplice. Si mantiene una lista dei nomi che fanno riferimento (mediante puntatori) alle informazioni. Molto semplice da implementare ma richiede tempo lineare per cercare un file al suo interno, nel caso venga usato frequentemente un file il tempo di attesa aumenta.
Un'alternativa sarebbe quella di utilizzare una lista ordinata-> diminuisce il tempo di ricerca, ma aumenta il tempo di inserimento degli elementi.
12.3.2 Tabella di hash
Tabella di hash-> si memorizzano gli elementi in tale tabella. Mediante una funzione di hash ci si calcola il valore in base al parametro in entrata e tale funzione restituisce il puntatore alla locazione desiderata.
Collisioni-> è possibile che la funzione di hash identifichi due file con lo stesso valore.
Il problema delle tabelle di hash è la dimensione, che in genere è fissa e la dipendenza dalla funzione di hash.
12.4 Metodi di allocazione
Ci sono tre metodi per allocare i file su disco:
1.Contigua;
2.Collegata;
3.Indicizzata.
12.4.1 Allocazione contigua
Richiede che ogni file occupi un certo numero di blocchi contigui su disco. Si parte ad allocare dal blocco b, poi b+1, b+2, ecc...
L'accesso all'informazione allocata in questo modo è semplice. Il file system ricorda solo il primo blocco referenziato, poi avanza al successivo.
Problemi: Tale allocazione soffre si frammentazione esterna. Lo spazio su disco viene suddiviso in piccole partizioni a mano a mano che si alloca lo spazio. Si arriverà ad un punto che non sarà possibile allocare altri blocchi. Ma sommando i buchi fra una partizione e l'altra se ne potrebbero allocare altri.
Soluzione: Si potrebbe effettuare una compattazione di tali blocchi -> durante tale operazione le normali operazioni non sono consentite.
Un problema più pesante è quello che non si può sapere a priori quanto spazio occuperà un processo durante la sua vita. Se si alloca poco spazio tale processo non potrebbe più avanzare, dunque dovrebbe essere terminato. Una soluzione potrebbe essere quella si assegnare delle estensioni.
12.4.2 Allocazione collegata
Ogni file è una lista collegata di blocchi su disco. Con tale metodo si individua un blocco di partenza, i successi blocchi possono essere sparsi ovunque sul disco. Essi sono collegati mediante un puntare. La directory conterrà un puntatore al primo blocco, uno all'ultimo blocco del file.
Risolvo tutti i problemi dell'allocazione contigua (frammentazione esterna, dimensione file).
Problemi: è efficiente solo per file sequenziali, se voglio accedere ad un determinato blocco devo scorrere prima tutti quelli prima per poter raggiungere quello desiderato. Un secondo problema è che i puntatori portano via spazio per l'informazione (il 0.78% è occupato dai puntatori).
Soluzione: Raggruppo i blocchi in cluster-> metto alcuni blocchi in un unico cluster. In questo modo il ci sarà solo un puntatore per i blocchi che ho raggruppato in un cluster.
Un problema più rilevante è quello dell'inaffidabilità, i puntatori ai blocchi successivi potrebbero danneggiarsi-> i blocchi potrebbero essere isolati, o peggio si potrebbe avere un collegamento ad un altro blocco.
12.4.3 Allocazione indicizzata
Ogni file possiede un blocco indice, il quale è un vettore di indirizzi dei blocchi presenti su disco. l' i-esimo indice punta all'i-esimo blocco su disco.
Questo metodo non soffre di frammentazione esterna ed è in grado di accedere direttamente all'informazione.
Problema-> se ci sono pochi indirizzi nel vettore (il quale è memorizzato in un blocco a parte) si sprecherebbe un blocco. In caso contrario potrebbero esserci più indirizzi di quelli memorizzabili su un blocco.
- Schema collegato: il blocco indice è un blocco del disco, se si devono memorizzare molti indici si possono mettere assieme più blocchi indici. La fine del blocco è denotata con nil, oppure è utilizzato un puntatore nel caso si debba aggiungere un altro blocco indice;
- Indice multi livello: si utilizzano più livelli di blocchi indice, per poi giungere alle informazioni;
- Schema combinato: combinazione dei due metodi precedenti. Si utilizzano i primi puntatori per arrivare alle informazioni, gli altri portano ad altri indici, che potrebbero portare alle informazioni o ad altri indici.
12.5 Gestione dello spazio libero
E' importante anche sapere come dover gestire lo spazio libero per l'allocazione di nuovi file.
12.5.1 Vettore di bit
Bit Map (o bit vector)-> tramite i bit posso stabilire quali blocchi sono liberi:
1->blocco libero;
0->blocco allocato.
Vantaggi-> semplicità di realizzazione ed efficiente nel trovare il primo o i primi n blocchi liberi.
Svantaggi-> è inefficiente se tale bit vector non è mantenuto nella memoria centrale per intero.
12.5.2 Lista collegata
Si mantiene una lista collegata dei blocchi liberi. Si parte dal primo blocco libero, il quale punta al successivo blocco libero. Il puntatore viene mantenuto in una locazione del disco.\\
Svantaggio: tale metodo è inefficiente nel caso si debba attraversare l'intera lista. L'attraversamento però non è un'azione frequente, in quanto il sistema il più delle volte avrà bisogno di un singolo blocco libero alla volta.
12.5.3 Raggruppamento
Un metodo alternativo è quello di porre gli indirizzi dei blocchi liberi in un blocco. La reperibilità di un certo numero di blocchi liberi è immediata.
12.5.4 Conteggio
Un metodo alternativo è quello di tenere l'indirizzo del primo blocco libero e il numero di blocchi liberi dopo il primo indirizzo.
12.6.1 Efficienza
L'efficienza dello spazio libero che si ha sul disco dipende fortemente da che tipo di algoritmo si decide di utilizzare. Ogni algoritmo presenta dei vantaggi e dei svantaggi che devono essere presi in considerazione per la gestione dello spazio libero.
12.6.2 Prestazioni
E' possibile aumentare le prestazioni utilizzando la cache per la gestione dei blocchi. Generalmente in cache si mantengono i blocchi che saranno utilizzati a breve, di modo tale che non si debba accedere nuovamente al disco->risparmio notevole di tempo.
Altri sistemi memorizzano nella cache i dati al posto dei blocchi fisici->cache delle pagine. [...]
12.7 Recupero del file system
Directory mantenute in memoria centrale e su disco-> un guasto potrebbe provocare una perdita di dati o l'incoerenza degli stessi.
12.7.1 Controllo della coerenza
Le informazioni della directory sono mantenute in memoria centrale e nella cache per velocizzare il tempo di accesso. Un blocco improvviso del computer potrebbe far perdere tutte le modifiche effettuate lasciando il file system in una situazione non coerente.
Il controllore della coerenza confronta i dati della struttura della directory con quelli presenti su disco e ripara eventuali incoerenze.
12.7.2 Backup e ripristino
Per non perdere i dati è consigliabile effettuare dei backup periodici dei dati. Così facendo è possibile, in caso di guasto, ripristinare il guasto utilizzando proprio questi backup. E' possibile effettuare dei backup incrementali, ovvero partendo da un backup completo è possibile effettuare un backup dei dati che hanno subito delle modifiche.
12.8 File system basato sulla registrazione delle attività
Con tale file system si registrano tutte le attività svolte dall'elaboratore. Più in particolare tutte le modifiche apportate ai metadati sono registrate in un regitro (log). Ogni insieme di operazioni sono raggruppate in transazioni. Quando si vuole effettuare un'operazione, essa è scritta sul registro ed è da considerarsi da svolgere. Quando tale operazione sarà svolta potrà essere tolta da tale registro. Nel caso in cui il sistemi si blocchi all'interno di questo registro ci saranno zero o più operazioni che non sono state completate. E' possibile dunque, mediante questo registro effettuare di nuovo tutte quelle operazioni che sono rimaste pendenti.
12.9 NFS
Network File System (NFS) è un file system di rete, il quale è utilizzato per accedere a dei file remoti mediante la rete LAN.
12.9.1 Descrizione
I computer presenti sulla rete sono indipendenti. La condivisione avviene mediante la struttura client-server. Per rendere possibile la condivisione di tali file il client deve per prima cosa iniziare un punto di montaggio.
Consiste nel montare una directory del file system remoto con una directory del file system locale. Così facendo si rende disponibile la directory contente il file remoto voluto.
Es. s1: /usr/shared/dir1; t2: /usr/local. L'effetto di montaggio di s1: /usr/shared su t2: /usr/local è: /usr/local/dir1.\\
Nota: la directory /usr/local non sarà più visibile.
Un aspetto molto importante è che un client che ha montato un file system in remoto egli non avrà accesso agli altri file system che sono stati montati su quella macchina.\\
Tramite le RPC (Remote Procedure Call) il NFS può operare in un ambiente eterogeneo, dove le macchine possono montare sistemi operativi differenti.
12.9.2 Il protocollo di montaggio
Protocollo di montaggio-> stabilisce una connessione logica fra il server e il client. Successivamente si deve montare il file system, quindi si deve passare il nome della macchina remota.
La richiesta di montaggio è mappata in una RPC e poi inoltrata al server. Il server mantiene una lista di esportazione-> contiene le informazioni sui permessi di montaggi. Quando gli arriva la richiesta verifica che il client abbia i permessi. Se il client possiede i permessi il server gli restituisce un descrittore di file, che servirà al client per i successivi accessi.
12.9.3 Il protocollo NFS
Come detto il protocollo opera su un insiemi di primitive di RPC, le quali consentono anche altre operazioni:
- Ricerca di un file in una directory;
- Lettura di un gruppo di elementi dalla directory;
- Manipolazione dei collegamenti e delle directory;
- Accesso agli attributi dei file;
- Lettura e scrittura dei file.
12.9.4 Traduzione del nome del percorso
Dato che ogni client possiede un suo schema del proprio spazio dei nomi logico occorre una traduzione, affinché tale nome sia comprensibile al server. Tale operazione è costosa dato che il percorso del nome è spezzettato ed ogni pezzetto è inviato al server. Tale operazione però è indispensabile. Per rendere queste traduzioni più veloci si potrebbe memorizzare tale frammento di traduzione all'interno della cache.
12.9.5 Operazioni remote
Esiste una corrispondenza biunivoca fra le normali chiamate di sistema per le operazioni sui file e le operazioni effettuate mediante le RPC.
Nonostante il NFS utilizzi le operazioni remote per migliorare le prestazioni utilizza la cache e i buffer, con tutti i vincoli di coerenza necessari.
