Appunti Sistemi operativi - parte 7

Lezione 30

Introduzione al file system

Il file system è quella parte del Sistema Operativo (SO) che ha lo scopo di organizzare e memorizzare i file. Abbiamo visto che il disco è un supporto di memoria secondaria del tipo non volatile e questa organizzazione logica del file garantisce la persistenza del file, l’organizzazione in directory sia ad albero, sia a grafo e ovviamente un meccanismo di recupero e di naming. Ogni file ha infatti un nome, un’estensione che conferisce significato al file dando info sul formato, sui programmi che possono leggerlo ed elaborarlo. Abbiamo poi la condivisione di un file e la protezione di un file nella sua forma più semplice come negli ottetti o ancora meccanismi più sofisticati di protezione come ad esempio l’Access Control List.

Struttura del file system

La struttura logica di un file system è presentata sopra; un file system deve preoccuparsi della memorizzazione del file e quindi ha una parte relativa all’organizzazione fisica. In questa parte il file viene visto come un insieme di blocchi che deve essere memorizzato oppure recuperato accedendo ad un dispositivo. Nello stato intermedio abbiamo un modulo di accesso, sostanzialmente un modulo che definisce i criteri di accesso al file, sia a livello di permessi e quindi i classici ottetti in UNIX oppure l’Access Control List. Ci sono poi i livelli fisici per l’accesso al blocco e quindi se l’accesso deve essere sequenziale oppure se deve essere casuale.

Abbiamo poi una struttura logica, cioè la struttura che ci dice come sono organizzati i file logicamente. I file sono organizzati in directory e le directory sono poi organizzate in modo gerarchico oppure in grafo aciclico mediante i così detti link, collegamenti per organizzazioni più complesse. Nella figura sotto possiamo osservare una struttura ad albero. Tutti i file system hanno un’organizzazione ad albero perché rende più efficiente la ricerca di un file ed ogni file può essere in qualche modo specificato da una stringa che prende il nome di path name. Il path name può essere sia assoluto e si parte da una directory che viene chiamata root della directory radice, ad esempio abbiamo che partendo da spell (percorso evidenziato in rosso nella figura sotto) abbiamo che il path name sarà /spell/mail/prog/list.

Abbiamo anche un’altra tipologia di path name che è quello relativo e che indica qual è il percorso per identificare un file partendo da una directory che non è una root. Nel caso in esame potrebbe ad esempio essere ..list. Le directory infatti hanno due file speciali che sono:

• .. -> Directory corrente
• . -> Directory superiore

Accesso e protezione nei file system

Nei sistemi più moderni come quelli Windows e UNIX l’organizzazione gerarchica dei file può essere estesa ad un grafo aciclico, cioè un grafo che non contiene cicli in quanto i cicli sono molto pericolosi e possono generare dei loop. Per grafo aciclico si intende che un file può essere riferito da diversi path, tipicamente su questi grafi per riferirsi ad uno stesso file si procede inserendo fisicamente un file nella stessa directory, poi si può collegare questo file ad altri path name attraverso dei link. Per esempio in Linux questi link possono essere:

• Simbolici -> Sono dei link che puntano a quel file ma non possono essere rimossi, se si rimuove un link viene rimosso il link ma non il file
• Hard Link -> Sono dei link che se rimossi permettono di rimuovere anche il file

Per quanto riguarda l’accesso al file system abbiamo tre punti importanti. Il primo punto riguarda i metodi di accesso ad un file che come abbiamo più volte visto può essere di tipo sequenziale oppure un tipo di accesso diretto.

Sia per quanto riguarda l’accesso diretto che l’accesso sequenziale possono essere implementati in un file system e questo dipende dal dispositivo. Abbiamo visto che i dischi tradizionali possono contenere un file ad accesso diretto ma il tempo di accesso non è mai uguale al blocco e non è mai indipendente dalla posizione di blocco del file. I dischi SSD sono dischi che hanno puramente un accesso diretto dove il tempo di accesso in un blocco non dipende mai dalla posizione nel blocco.

Protezione dei file

Per quanto riguarda la protezione abbiamo come detto che la protezione più semplice è quella dei 3 ottetti. Se in binario ad esempio abbiamo chmod 662 per un file significa che stiamo configurando l’ottetto come: questa configurazione ci indica che il proprietario può leggere e scrivere, il gruppo può leggere e scrivere mentre gli altri possono solo leggere, il 2 sopra non è una scelta frequente.

Per quanto riguarda l’accesso ad un file abbiamo che una directory è un file speciale che contiene una lista di entry. Ogni entry è relativa ad un file e sostanzialmente questa entry si riferisce ad un puntatore speciale ad una struttura dati del Kernel che si chiama file control block. Nelle directory sostanzialmente si ha che ad ogni file c’è un puntatore ad un file control block. Un file control block altro non è che un descrittore di un file e contiene tutte quelle informazioni necessarie al SO per la gestione corretta dei file. Ad esempio un tipico file control block contiene i permessi, la data di creazione, l’ultimo accesso in scrittura, chi è il proprietario, se ci sono access control list, la dimensione e quanti dati prende. Questo descrittore di file può essere più o meno complesso a seconda del file system.

Organizzazione fisica del disco

Il file system di un SO deve offrire un'interfaccia uniforme per poter eseguire le classiche operazioni sui file. Per parlare di organizzazione fisica dobbiamo prima capire come viene gestito il disco. Quando il PC parte, c’è un piccolo caricatore a bordo di una EPROM o di una FLASH nella motherboard. Questo caricatore non fa altro che un JMP ad una particolare parte del disco, caricare solo quella parte del disco ed eseguire quello che è contenuto nella parte del disco. Questa parte del disco viene chiamata master boot record (MBR). Abbiamo quindi un piccolo settore del disco, settore 0 o MBR, che contiene tutto ciò che occorre al SO per poter partire. Tipicamente abbiamo un caricatore del SO che è in grado di caricare il SO in memoria.

Lo MBR, come possiamo osservare dalla figura sotto, ha sostanzialmente una certa dimensione con un indirizzamento a 32-bit. Questo è uno dei limiti del MBR che può indirizzare fino a 2T e poi può indicizzare una tabella delle partizioni. Un disco può essere in qualche modo suddiviso in massimo 4 partizioni, dove alcune partizioni possono essere attive ed altre possono essere passive. Le partizioni attive sono quelle che contengono il SO e quindi il Master Boot Record (MBR) contiene il caricatore e poi sostanzialmente contiene l’indirizzo della partizione attiva che è poi quello dove si deve cominciare a caricare il SO. Una partizione ha un blocco del boot che contiene la parte del SO che deve essere caricata, ci sta poi un super block che contiene tutte le informazioni di controllo sulla partizione, abbiamo poi una parte dedicata alla gestione dello spazio libero e poi abbiamo dei blocchi dati.

Per completezza, oggi lo MBR sta venendo soppiantato dalla GPT (Global Partition Table) e questo perché lo MBR ha un limite sull’indirizzamento del disco che è pari a 2T. Oggigiorno questo tipo di dimensione sta piano piano venendo superato, può supportare fino a 4 partizioni primarie, ci sono dei trucchi per riuscire a fare più partizioni nel caso in cui si creano delle partizioni estese. Le partizioni primarie che possono potenzialmente essere attive e quindi sulle quali può essere caricato il SO possono essere 4. Questa problematica poteva essere un limite fino a qualche anno fa ma ad oggi con la virtualizzazione il numero di partizioni non costituisce più un vero e proprio problema perché con la virtualizzazione è difficile vedere una macchina con due SO installati. L’unico limite importante ad oggi per lo MBR è che la dimensione massima della partizione utilizzabile è di 2T. Questo limite viene superato dal GPT che è un nuovo standard di organizzazione fisica del disco che supera lo MBR, dove effettivamente su ogni partizione in un certo drive abbiamo che ogni partizione può essere identificata da un numero univoco e questo consente di avere quante partizioni si vuole, fino ad un indirizzamento che può essere molto lungo fino a 2⁶⁴ per la dimensione del blocco e quindi si arriva ad indirizzare fino al petabyte.

Ovviamente un disco così grosso se pure possa esistere è difficile da realizzare e la tecnologia odierna ancora non è pronta e per tale ragione abbiamo che questa transizione tra MBR e GPT sta avvenendo lentamente, questo sia per limiti fisici sia perché non c’è urgenza di avere molti SO caricati all’interno di un solo disco.

L’unità di memorizzazione dei file su disco è il blocco o il settore che fino ad ora abbiamo usato in modo intercambiabile. Questi due termini tuttavia rappresentano due cose diverse per tanto è importante fare chiarezza. Abbiamo visto che il settore fa parte della traccia e quindi la traccia la possiamo definire come l’insieme di settori, il settore nel SSD è quello che chiamiamo pagina. L’unità di trasferimento dei dischi è il blocco che viene ad essere visto come un insieme di settori, si parla di blocco come un insieme di settori e non di un solo settore in quanto il blocco ha una dimensione maggiore del settore e quindi ha un’efficienza di trasferimento maggiore. Più blocchi vengono ad essere trasferiti e minore sarà l’overhead e quindi ci sarà un’efficienza maggiore. Ecco il motivo per cui si preferisce avere un’unità di memorizzazione che si chiama blocco e che è vista come un insieme di settori.

Un altro motivo per cui si parla di blocco come insieme di settori è che tipicamente il blocco è uguale alla dimensione di una pagina e quindi avere come unità di trasferimento un blocco che è uguale proprio ad una pagina di memoria ha degli evidenti vantaggi in quanto è possibile muovere pagine in modo efficiente e deve essere così in quanto il trasferimento su disco deve essere efficiente perché deve minimizzare l’overhead. Abbiamo poi che un blocco può essere visto anche come un insieme di settori contigui, quindi se prendiamo come unità di trasferimento un insieme di settori contigui abbiamo evidenti vantaggi soprattutto nei dischi tradizionali di trasferimento tra dischi in quanto muoviamo sempre settori contigui. Abbiamo visto che anche per quanto riguarda i dischi SSD vi è un certo vantaggio se le letture sono relative a dei settori contigui. Poiché entrambe le tecnologie hanno dei benefici nella lettura sequenziale abbiamo allora un vantaggio nel definire un blocco come un insieme di settori contigui.

Allocazione dei file su disco

In generale esistono tre tipi di allocazione dei file su disco che definiscono i tre metodi principali per allocare i file su disco. Ogni file, come detto sopra, lo vediamo come un insieme di blocchi che per quanto detto prima abbiamo che ogni blocco è un insieme di settori contigui.

Allocazione contigua

Nell’allocazione contigua i blocchi di un file sono memorizzati in blocchi contigui. Supponiamo di avere la directory rappresentata sopra in figura, abbiamo che la directory contiene file f1, f2, f3 ed f5. Nell’allocazione contigua nella directory per ogni file memorizziamo il blocco dove inizia e la lunghezza, tipicamente abbiamo che 1 indica il primo blocco, il file f1 quindi dalla tabella sopra possiamo evincere che è allocato nel blocco 1 ed ha una lunghezza di 3 blocchi e quindi come possiamo vedere dalla rappresentazione della memoria a sinistra abbiamo che il file f1 si troverà nel blocco 1, 2 e 3.

Se ad esempio vediamo il file f3, abbiamo che dalla tabella a destra che rappresenta la directory sappiamo che inizia al blocco 21 ed è lungo 2, abbiamo allora che il file f3 comincia al blocco 21 e finisce al blocco 22. Possiamo osservare che l’allocazione che si ha è per blocchi contigui. I vantaggi di questo tipo di allocazione stanno nelle prestazioni a livello di efficienza però sebbene questa soluzione presentata sopra sia la soluzione migliore perché tutti i file sono memorizzati in blocchi contigui, questa soluzione comporta degli svantaggi in quanto se si hanno dei file che crescono e che quindi dinamicamente cambiano la propria dimensione, questo potrebbe causare dei problemi in quanto soprattutto per i file che crescono di dimensioni si potrebbero avere problemi di spazio. Nell’esempio sopra per il file f4, abbiamo che se vogliamo aggiungere un blocco a questo file, questo risulterà essere impossibile in quanto il disco è finito e quindi abbiamo una rigidità nella gestione dei file soprattutto per quei file le cui dimensioni cambiano dinamicamente. Abbiamo poi problematiche di frammentazione esterna e si hanno tutti quei problemi che abbiamo visto nella gestione della memoria a partizioni variabili e quindi vi è la necessità di dover ricorrere a degli algoritmi di compattazione della memoria.

Per l’allocazione contigua i metodi di accesso possono essere sia sequenziali che diretti, non c’è problema dal punto di vista del metodo solo che mentre l’accesso sequenziale è perfetto, l’accesso diretto dipende da quale blocco si vuole andare ad accedere nel file. Ad esempio, se vogliamo accedere al blocco 3 del file f1, il tempo di accesso sarà diverso rispetto a quello del blocco 1 dello stesso file. È possibile un accesso diretto ma il tempo è sempre dipendente dalla posizione del blocco alla quale si vuole accedere. Un blocco abbiamo detto che è un insieme di settori contigui, con l’allocazione sopra abbiamo il massimo delle prestazioni tanto è vero che questo tipo di allocazione viene ad essere usata sui i nastri di backup. I nastri di backup per il metodo di accesso diretto abbiamo che bisogna prima cercare il file ma una volta cercato il file il trasferimento risulta essere velocissimo.

Allocazione concatenata

L’allocazione concatenata o linked è un tipo di allocazione simile alle liste linkate viste a programmazione. Per superare il problema della compattazione e quindi della frammentazione esterna, questo tipo di allocazione non prevede un’allocazione a blocchi contigui ma un’allocazione indicizzata ed indipendente dalla posizione dei blocchi. Nella directory abbiamo un file f1, nel file f1 ci memorizziamo solo qual è il primo blocco e qual è la lunghezza, ogni blocco è fatto da un campo informativo e da un puntatore a next. Abbiamo allora che il primo blocco del file sarà 11, avremo poi che sarà il 2 il secondo blocco, poi l’8, il 15, il 9 ed il 5, abbiamo quindi che il file è in tutti blocchi in posizioni differenti. In questo caso non abbiamo frammentazione esterna perché il disco lo usiamo tutto e quindi non c’è nessun problema di frammentazione. Il costo dell’allocazione è semplice in quanto dobbiamo avere una lista di blocchi liberi e quindi ogni volta che viene ad essere richiesto un blocco, ne viene dato uno libero e questo lo si inserisce nella lista a puntatori.

Si hanno diversi svantaggi, ad esempio il fatto che il file è frammentato sul disco e quindi i blocchi sono sparpagliati comporta un maggior costo della ricerca di un blocco di un file. Supponiamo ad esempio che si voglia andare a ricercare il blocco 9, se l’allocazione è contigua più o meno abbiamo che il blocco 9 lo riusciamo subito a raggiungere, in questo caso abbiamo che la testina deve fare molti movimenti (salti) e quindi il costo per cercare un blocco può essere molto elevato. I metodi di accesso diretto per questo tipo di allocazione non ha senso implementarli in quanto il tipo di allocazione non si presta a tale metodo di accesso. Abbiamo poi un overhead dovuto alla gestione di questa parte next che fa perdere una parte di memoria del disco in quanto bisogna tener conto di tutti questi puntatori a next. Se si danneggia poi uno di questi puntatori in questi blocchi viene ad essere perso tutto quanto il file. Questi sono gli svantaggi di questo tipo di allocazione. L’allocazione contigua e l’allocazione concatenata soffrono di frammentazione interna in quanto se diciamo ad esempio che un blocco è fatto da 10 settori e vogliamo allocare un file con 6 settori, abbiamo che comunque allochiamo un blocco e quindi 3 settori vengono ad essere persi, abbiamo allora che la frammentazione interna c’è sempre e dipende dalla dimensione del blocco.

Standard FAT32

Lo standard FAT32 è un file system reale linked che viene ad essere ancora utilizzato ad esempio per le pendrive e che una volta era uno standard de facto per i sistemi come Windows 95. La FAT sta per File Allocation Table ed è un tipo di allocazione concatenata di un disco. Nei SO Microsoft abbiamo che si usa anche il concetto di cluster, abbiamo che Microsoft ha un blocco che tipicamente è la dimensione della pagina e che è un insieme di tracce e poi abbiamo un cluster che è un insieme di blocchi. Microsoft per cercare di forzare un tipo di allocazione contigua coniò il concetto di cluster che è ancora presente nel file system NTFS come insieme di blocchi per favorire ancora di più le prestazioni dovute alla contiguità.

Un cluster è sostanzialmente un insieme di settori consecutivi, tipicamente nei dischi tradizionali abbiamo che la dimensione è di 512 byte e un cluster può essere tipicamente un insieme di settori che nell’esempio in questione supponiamo che ha una dimensione di 2Kb. Nell’allocazione concatenata e in particolare quella FAT abbiamo che se supponiamo di avere due file, uno che prende il nome di gary.txt ed un altro che si chiama hello.jpg, abbiamo che il file gary.txt ha una dimensione di 1034 byte ed inizia al cluster 6...