12. File System

Il file system fornisce il meccanismo per la memorizzazione e lโ€™accesso di dati e programmi. Consiste di una collezione di file e della struttura di cartelle (directory).

Interfaccia del file system

Concetto di file

Il sistema operativo astrae dalle caratteristiche fisiche dei supporti di memorizzazione fornendo una loro visione logica. Si considera un file come uno spazio di indirizzamento logico e contiguo rappresentante un insieme di informazioni correlate identificate da un nome. I file possono essere dati di qualsiasi tipo e programmi.

Attributi di un file

Su disco, nella struttura della directory, sono salvati per ogni file il nome (unica informazione in formato leggibile), tipo, posizione (puntatore allo spazio fisico sul dispositivo), dimensione, protezione (controllo sui permessi), tempo, data e identificazione dellโ€™utente.

Operazioni sui file

Struttura dei file

I tipi di file possono essere usati per indicare la struttura interna del file. Di seguito 3 esempi di struttura di file.

  1. Nessuna struttura: si considera un file come una sequenza di parole o bytes, come avviene ad esempio in Unix.
  2. Struttura a record semplice: un record รจ una riga di lunghezza fissa o variabile.
  3. Struttura complessa: come accade nei documenti formattati e i formati ricaricabili (load module).

Le ultime due si possono emulare con la prima usando caratteri di controllo.

Metodi di accesso

Sequenziale

Questo metodo viene usato da editor e compilatori, permettono le operazioni read next, write next, reset (rewind). Non รจ permesso il rewrite in quanto si rischia inconsistenza se si scrive qualcosa a metร  del file in quanto si potrebbe eliminare ciรฒ che sta dopo.

Diretto

Come accade nel database in cui un file รจ una sequenza numerata di blocchi detti record. Le operazioni permesse sono read n, write n, position to n, read next, write next, rewrite n.

Struttura delle directory

Le directory sono una collezione di nodi contenenti informazioni sui file. Si trovano entrambi sul disco e determinano la struttura del file system. Per ogni file contengono il nome, tipo, indirizzo, lunghezza attuale, massima lunghezza, data di ultimo accesso, data di ultima modifica, proprietario e informazioni di protezione.

Operazioni sulla directory

Organizzazione logica

I vantaggi dellโ€™organizzazione logica delle directory sono lโ€™efficienza (rapido accesso ad un file), nomenclatura conveniente agli utenti in quanto permette stessi nomi per file e utenti diversi e nomi diversi per lo stesso file e raggruppamento: i file vengono classificati logicamente per un criterio come il tipo o la protezione.

Grazie alle directory il file system puรฒ assumere diverse strutture, definite durante l'implementazione. Vediamone alcune.

Directory a un livello

In questo metodo si trova una singola directory per tutti gli utenti. Nascono problemi di nomenclatura, in quanto รจ difficile ricordare se un nome esiste giร  e inventarne sempre di nuovi. Nascono inoltre problemi di raggruppamento.

Directory a due livelli

In questo metodo si trova una directory separata per ogni utente. Nasce il concetto di percorso (path), รจ possibile usare lo stesso nome di file per utenti diversi e la ricerca รจ efficiente. Non esiste comunque raggruppamento e si pone il problema di dove mettere i programmi di sistema condivisi dagli utenti (in Unix si usa PATH).

Directory ad albero

In questo metodo la directory viene implementata come un albero permettendo una ricerca efficiente e la possibilitร  di raggruppamento. Nasce il concetto di working directory e i nomi di percorso possono essere assoluti o relativi. Tuttavia manca ancora la possibilitร  di condivisione di file e directory.

Directory a grafo aciclico

In questo metodo si espande la versione ad albero a grafo aciclico per permettere la condivisione di file.
La condivisione avviene:

Directory a grafo generico

Questo metodo nasce come estensione della directory a grafo aciclico e si deve garantire che le ricerche terminino per evitare loop infiniti nellโ€™attraversamento del grafo (visto che in questo caso puรฒ avere cicli). Per risolvere questo problema si puรฒ permettere di collegare solo file non directory o usare un algoritmo di controllo di esistenza di un ciclo ogni volta che si crea un nuovo collegamento, che puรฒ essere costoso.

Mount di un file system

Il mount di un file system รจ il processo attraverso il quale un file system viene aggiunto al sistema operativo e reso accessibile. Quando si crea un file system, รจ possibile renderlo modulare, consentendo di collegare (mount) e scollegare (unmount) interi file system a file system esistenti.
Prima di poter accedere a un file system perรฒ, รจ necessario montarlo. Il processo di montaggio richiede che un file system sia associato a un punto specifico del sistema operativo, noto come "mount point". Il mount point รจ una directory esistente nel sistema di file che funge da punto di accesso al file system che viene montato. Una volta montato, il file system diventa parte integrante del sistema operativo e puรฒ essere utilizzato per leggere o scrivere dati.

Condivisione di file

La condivisione di file รจ importante in sistemi multiutente ed รจ realizzabile tramite uno schema di protezione. Nei sistemi distribuiti, i file possono essere condivisi attraverso una rete. Per esempio, il Network File System (NFS) รจ un tipico schema di condivisione di file via rete.

Protezione

Il possessore di un file deve poter controllare cosa รจ possibile fare su un file e da parte di chi. Per farlo si puรฒ implementare una lista di accesso per ogni file o directory che lista chi puรฒ fare cosa.
Gli utenti si possono raggruppare in tre classi con una perdita di generalitร : il proprietario, il gruppo (utenti appartenenti allo stesso gruppo del proprietario) e gli altri. Per ogni classe i permessi possono essere di read(r), write(w) ed execute(x).

CHMOD

In Unix per esempio, รจ possibile cambiare i permessi di un file utilizzando il comando chmod.
Un esempio di utilizzo puรฒ essere il seguente:

chmod 754 nome_file

dove le 3 cifre rappresentano rispettivamente il livello di permessi per l'utente, il livello di permessi del gruppo e il livello di permessi generale. In base alla cifra si ha una serie di permessi. La tabella seguente indica il significato dei singoli valori:

Valore decimale Permessi
7 lettura, scrittura ed esecuzione
6 lettura e scrittura
5 lettura ed esecuzione
4 solo lettura
3 scrittura ed esecuzione
2 solo scrittura
1 solo esecuzione
0 nessuno

Dunque nel nostro esempio il proprietario ha i permessi di read, write ed execution, il gruppo non ha la write, e gli altri solo la read.

Implementazione di un file system

Per gestire un file system si usano diverse strutture dati in parte su disco e in parte in memoria. Le caratteristiche, pur avendo una base comune sono fortemente dipendenti dal sistema operativo e dal tipo di file system.

Strutture su disco

Strutture in memoria

Allocazione dello spazio su disco

I blocchi su disco possono essere allocati in modi diversi con lโ€™obiettivo di minimizzare i tempi di accesso e massimizzare lโ€™utilizzo dello spazio.

Allocazione contigua

In questo metodo ogni file occupa un insieme di blocchi contigui su disco. Lโ€™entry della directory รจ semplice in quanto contiene lโ€™indirizzo del blocco di partenza e la lunghezza del file.

FileSystem-AllocContigua.png600

Vantaggi
Svantaggi
Variante

Alcuni file system moderni usano uno schema modificato di allocazione contigua come Linux ext2fs basato sullโ€™extent, una serie di blocchi contigui su disco. Il file system alloca extent invece di blocchi singoli che in generale non sono contigui e si prestano pertanto per lโ€™allocazione a lista.

Allocazione a lista

In questo metodo ogni file รจ costituito da una lista di blocchi concatenati, che possono essere sparsi ovunque nel disco.
La directory contiene puntatori al primo e allโ€™ultimo blocco e ogni blocco contiene un puntatore al blocco successivo. Considerando X lโ€™indirizzo logico e N la dimensione del blocco, X(Nโˆ’1) รจ il numero
del blocco nella lista, mentre Xmod(Nโˆ’1) รจ lโ€™offset allโ€™interno del blocco.

FileSystem-AllocLista.png600

Vantaggi
Svantaggi
Variante - FAT (file allocation table)

Una variante che migliora l'accesso casuale fa uso della File Allocation Table (FAT). Questa รจ una tabella che occupa i primi blocchi del volume e contiene una lista di tutti i blocchi allocati. Inoltre, per ogni blocco si registra anche la posizione del suo blocco successivo. Purtroppo le dimensioni della FAT (spesso FAT32 perchรจ con entry di 32 bit) impediscono una scansione efficiente e cominciano ad occupare una porzione significativa di memoria con l'aumentare delle dimensioni del disco. Questi svantaggi rendono oggi l'uso della FAT proibitivo.
Lโ€™accesso diretto ai file di grandi dimensioni, per esempio utilizzando la system call lseek, puรฒ essere inefficiente nei file system di tipo FAT a causa del modo in cui i dati vengono organizzati e gestiti. In un file system FAT, i dati vengono memorizzati in cluster di dimensioni fisse. Quando si accede a un file, il sistema operativo deve seguire una catena di cluster per trovare il cluster corretto che contiene i dati richiesti. Per i file di grandi dimensioni, questo puรฒ comportare il passaggio attraverso molti cluster, il che puรฒ richiedere molto tempo. Inoltre, se il file รจ frammentato (cioรจ i suoi cluster non sono contigui), il tempo necessario per trovare il cluster corretto puรฒ aumentare ulteriormente. Questo puรฒ rendere lโ€™accesso diretto ai file di grandi dimensioni utilizzando lseek inefficiente nei file system di tipo FAT.

Allocazione indicizzata

In questo metodo ogni file ha un blocco indice (index block) che contiene la tabella degli indirizzi dei blocchi fisici, ossia il blocco indice punta a tutti gli altri blocchi dello stesso file. La directory contiene lโ€™indirizzo del blocco indice. Se X รจ lโ€™indirizzo logico e N la dimensione del blocco XN รจ lโ€™offset nella index table e XmodN รจ lโ€™offset allโ€™interno del blocco dati.

FileSystem-AllocIndicizzata.png600

Vantaggi
Svantaggi
Indici multilivello

Il blocco indice punta ad altri blocchi indici, che punteranno ai dati dei file veri e propri.
Sia X lโ€™indirizzo logico e N la dimensione del blocco in parole. Xnโ€€โ‹…N รจ il blocco della index table di primo livello e Xmod(Nโ‹…N)=R, dove RN รจ lโ€™offset nel blocco della index table di secondo livello e RmodN รจ lโ€™offset nel blocco dati.
Per esempio, blocchi da 4KB consentono 1K indici da 4 byte, mentre due livelli di indici consentono file da 4GB.

Schema concatenato

Si usano piรน blocchi indice collegati tramite una lista concatenata: lโ€™ultimo degli indici di un blocco indice punta a un altro blocco indice. XN(Nโˆ’1) รจ il numero del blocco indice allโ€™interno della lista dei blocchi indice e Xmod(N(Nโˆ’1))=R, dove RNโˆ’1 รจ lโ€™offset nel blocco indice e RmodN รจ lโ€™offset nel blocco dati.

Esempio

N = 1KB = 256 parole (parola=32bit)

Max file = 256 blocchi da 1KB = 256KB

Schema combinato

Unix usa lo schema combinato in cui ad ogni file รจ associato un i-node (index-node) che contiene gli attributi del file e fa da blocco indice. Gli i-node sono gestiti dal sistema operativo e memorizzati in modo permanente in una porzione riservata al sistema operativo di solito allโ€™inizio del disco. Per memorizzare i blocchi di dati del file, ogni i-node contiene:

SchemaCombinato.png700

Implementazione delle directory

Le directory vengono implementate con lo stesso meccanismo usato per memorizzare i file. Non contengono dati, ma una lista di file e directory. Questo spazio puรฒ essere memorizzato in due modi:

Gestione dello spazio libero

Per tenere traccia dello spazio libero su disco si mantiene una mappa dei blocchi liberi. Per creare un file si cercano blocchi liberi nella mappa e per rimuovere un file si aggiungono i suoi blocchi a tale mappa. Vediamo ora diverse alternative per implementare la mappa.

Vettore di bit

Si mantiene un vettore in cui ogni posizione indica se un blocco รจ occupato o no. Bit[i]=0 implica che il blocco i รจ libero e Bit[i]=1 implica che รจ occupato. La mappa di bit richiede spazio extra ed รจ efficiente solo se il vettore รจ mantenibile tutto in memoria. Risulta comunque facile ottenere blocchi contigui.

Lista concatenata di blocchi liberi (free list)

Ogni blocco libero punta ad un altro blocco libero. Permette spreco minimo(solo per la testa della lista) ma lo spazio contiguo non รจ ottenibile.

Raggruppamento

Il concetto รจ simile a quello della lista concatenata, ma qui un blocco contiene la lista di nโˆ’1 indirizzi di blocchi liberi, e l'ultima entry punta ad un altro blocco usato come lista. Fornisce rapidamente un gran numero di blocchi liberi.

Conteggio

Si usa una lista che contiene ad ogni entry un blocco libero e quanti blocchi liberi consecutivi seguono.
La lista risulta piรน corta se il contatore รจ maggiore di 1 per ogni gruppo di blocchi liberi.

Efficienza e prestazioni

Efficienza

Il disco รจ un collo di bottiglia e lโ€™efficienza dipende dall'algoritmo di allocazione dello spazio su disco e dal tipo di dati contenuti nella directory.

Prestazioni

Il controller del disco possiede una piccola cache che รจ in grado di contenere unโ€™intera traccia ma non basta per garantire prestazioni elevate, pertanto si usano dischi virtuali (RAM disk) e cache del disco o buffer cache.

Dischi virtuali

Parte della memoria viene gestita come se fosse un disco: il driver di un RAM disk accetta tutte le operazioni standard dei dischi eseguendole in memoria. รˆ veloce ma supporta solo file temporanei. Viene gestito dallโ€™utente che scrive sul RAM disk invece che sul disco.

Cache del disco

รˆ una porzione di memoria che memorizza blocchi usati di frequente, simile alla cache tra memoria e CPU.
Viene gestita dal sistema operativo e sfrutta il principio di localitร  spaziale e temporale. Il trasferimento di dati nella memoria del processo utente non richiede spostamento di byte. Nascono problematiche riguardanti la politica di rimpiazzamento del blocco (se la cache รจ piena devo scegliere il blocco da togliere usando LRU, LFU, RANDOM, ecc.) e la politica di scrittura. Cioรจ se devo scrivere sul blocco usato di recente, intanto scrivo su quello in cache ma quando aggiorno quello originale che รจ memorizzato su disco?
Posso decidere di fare write-back, ovvero scrivere solo quando devo rimuovere il blocco dalla cache (puรฒ generare problemi di affidabilitร  in caso di crash) oppure write-through, scrivendo sempre (meno efficiente, la cache รจ praticamente in sola lettura).

Recupero

I problemi di consistenza tra disco e cache possono essere risolti attraverso un controllo di consistenza che confronta i dati nella directory con i dati su disco e sistema le inconsistenze, oppure attraverso lโ€™uso di programmi di sistema per fare il backup del disco su memoria di massa come i nastri che permettono il recupero di file persi tramite il restore dei dati di backup.

File system log structured

Si registra ogni cambiamento del file system come una transazione. Tutte le transazioni sono scritte su log e considerate completate quando vengono scritte su log (anche se il file system puรฒ non essere aggiornato). Le transazioni sono scritte in modo asincrono nel file system e quando il file system รจ modificato la transazione viene cancellata dal log. Se il sistema va in crash le transazioni non avvenute sono quelle presenti sul log.
In questo modo si ottimizza il numero di seek.