CEFRIELCEFRIELConsorzio per la Formazione e la RicercaConsorzio per la Formazione e la Ricercain Ingegneria dell’Informazionein Ingegneria dell’Informazione

PolitecnicoPolitecnicodi Milanodi Milano

Il File SystemIl File System

Master in ConvergenzaMaster in Convergenza

Docente:Docente:

Carlo BrandoleseCarlo Brandolese

Politecnico di MilanoPolitecnico di Milanobrandole@elet.polimi.itbrandole@elet.polimi.it

www.elet.polimi.it/~brandolewww.elet.polimi.it/~brandole

- - 22 - -

SommarioSommario

FileAttributiOperazioniStruttura

OrganizzazioneDirectoryProtezione

ImplementazioneAllocazioneGestione dello spazio liberoRealizzazione delle directory

- - 33 - -

FileFile

Il concetto di file offre una visone omogenea delle informazioni memorizzateLa visone non dipende dal tipo di dispositivo fisico su cui le informazioni vengono memorizzateUn file è costituito da:

Un insieme di informazioni omogeneeUn nome simbolicoUn insieme di attributi

Un file può contenere:DatiProgrammiRiferimenti

- - 44 - -

AttributiAttributi

Ad un file sono associati alcuni attributi che ne descrivono alcune caratteristiche

NomeE’ un nome simbolico con cui ci si riferisce ad esso

TipoDefinisce il tipo dei dati contenutiA volte il tipo viene definito attraverso una estensione del nome

LocazioneE’ un puntatore alla posizione fisica sul dispositivo

DimensioneDimensione dei dati espressa in bytes o blocchi

- - 55 - -

AttributiAttributi

ProtezioneDefinisce le politiche di gestione degli accessi

Ora e DataIndicano il momento della creazione, dell’ultima modifica o dell’ultimo accesso

ProprietarioIndica il nome dell’utente che ha creato il file

- - 66 - -

OperazioniOperazioni

Sui file possono essere compiute diverse operazioniLe operazioni vengono svolte attraverso delle richieste di servizi al sistema operativoLe operazioni più comuni sono elencate nel seguito

CreazioneViene aggiunto un nuovo file al file systemLe operazioni richieste sono:

Allocazione

Creazione del nuovo descrittore del file

Aggiunta del descrittore al file system

- - 77 - -

OperazioniOperazioni

ScritturaAggiunge dati a ad un file già creatoPer scrivere dati su un file è necessario fornire

Il nome del fileI dati da scrivere

Il SO mantiene un puntatore alla posizione corrente

LetturaPreleva dati da un file già creatoPer leggere dati da un file è necessario fornire

Il nome del fileUn puntatore ad zona di memoria destinazione dei dati

Il SO mantiene un puntatore alla posizione corrente

- - 88 - -

OperazioniOperazioni

RiposizionamentoSposta la posizione dei puntatori di lettura/scritturaLe operazioni permesse dipendono dal tipo di accessoSpesso viene mantenuto dal file system un solo puntatore valido per la lettura e per la scrittura

CancellazioneElimina un filePer eliminare un file è necessario specificarne il nomeLe operazioni necessarie sono:

Deallocazione dello spazio sul dispositivo fisicoAggiunta alla lista dello spazio disponibile sul discoRimozione del descrittore del file dal file system

- - 99 - -

OperazioniOperazioni

Tutte le operazioni richiedono l’accesso ad un file Il file system deve cercare il file sul dispositivo

Per rendere più efficiente la ricerca, il file system mantiene una tabella dei file in usoI file in uso si dicono aperti

Servizi forniti dal sistema operativoOpen

Sulla base del nome individua la posizione del file Copia il descrittore del file nella tabella dei file in uso

CloseSulla base del nome individua il descrittore del fileElimina il descrittore dalla tabella dei file in uso

- - 1010 - -

StrutturaStruttura

Un file system haStruttura logica

I dati sono organizzati in unità logiche di lunghezza fissa ma arbitraria dette record

Nel sistema UNIX un record è un byte

Struttura fisicaI dati sono organizzati in unità fisiche di lunghezza fissa e dipendente dal dispositivo dette blocchi

Dimensioni tipiche dei blocchi di unità a disco rigido variano da 32 a 4096 bytes, tipicamente 512

La struttura logica e fisica sono differentiI dati vengono impaccati prima di essere memorizzati in modo da sfruttare al meglio il dispositivo

- - 1111 - -

Struttura: EsempioStruttura: Esempio

Tale differenza, unitamente alla dimensione fissata dei blocchi provoca uno spreco di spazioSi consideri un file lungo 1350 byte ed un disco con blocchi da 512 bytes

0 512 1024 1350 1536

Questa parte del blocco (186 byte) viene sprecata e non è utilizzabile da altri file

Questo fenomeno è detto frammentazione interna

- - 1212 - -

Struttura: AccessoStruttura: Accesso

Accesso sequenzialeI dati sono letti/scritti in sequenzaLe operazioni disponibili per tali file sono

Lettura e scritturaPosizionamento all’inizio o alla fine del filePosizionamento sul record precedente o successivo

Accesso diretto o casualeI dati vengono letti e scritti in una qualsiasi posizioneLa posizione deve essere specificata in termini di blocco logico, relativamente all’inizio del fileI blocchi logici devono avere dimensione fissa per consentire il calcolo della posizione effettiva dei dati

- - 1313 - -

StrutturaStruttura

Le memorie di massa contengono milioni di fileNecessità di condividere uno o più fileTale mole di dati necessita una strutturazioneUn file system è organizzato in

PartizioniContengono insiemi di file correlati

DirectoryUna partizione è suddivisa in directoryContengono informazioni sui file e fungono da indice

FileContengono effettivamente i dati o i programmi

- - 1414 - -

DirectoryDirectory

Sulle directory è possibile compiere alcune operazioni

Ricerca di un fileSulla base di un nome o una espressione regolare consente di recuperare le informazioni su uno o più file

Creazione di un fileAlla directory viene aggiunto un elemento che raccoglie le informazioni sul nuovo file

Rimozione di un fileEliminazione di un descrittore di file. Il descrittore deve essre prima individuato tramite una operazione di ricerca

- - 1515 - -

DirectoryDirectory

Rimozione di un fileEliminazione di un descrittore di fileIl descrittore deve essre prima individuato tramite una operazione di ricerca

Elenco dei fileProduce l’elenco dei nomi ed eventualmente altre informazioni relative ai file memorizzati

Rinomina di un fileModifica il nome di un file già presente nella directoryIl descrittore deve essre prima individuato tramite una operazione di ricerca

- - 1616 - -

Directory a singolo livelloDirectory a singolo livello

Tutti i file sono contenuti in una sola directoryQuesta struttura è molto semplice ma presenta alcuni problemi

Con molti file è difficile garantire che tutti i nomi siano diversiCon molti file le dimensioni della directory diventano grandi a discapito del tempo di accesso Utenti differenti possono accedere agli stessi file

tmp test data jhon cc emacs

- - 1717 - -

Directory a due livelliDirectory a due livelli

Directory principaleContiene un elenco di directory, una per utente (root)La gestione affidata ad un amministratore (superuser)

Directory utenteContengono i file di un singolo utente (home)I singoli utenti vedono e gestiscono solo i file nella propria home directory

Quando un utente richiede l’accesso ad un file, il SO ne cerca il nome nella home directory dell’utentePer accedere ai file di altri utenti si utilizza il path name cioè la composizione del nome dell’utente e del nome del file

- - 1818 - -

Directory a due livelliDirectory a due livelli

Gli applicativi sono accessibili a tutti gli utentiA tale scopo esiste una directory specifica (bin)I file sono

Prima cercati nella directory dell’utente Se la ricerca fallisce, nella directory degli applicativi

bin mike bill jhon

gcc tcsh emacs test data gnu data foo

- - 1919 - -

Directory ad alberoDirectory ad albero

Ha un numeo arbitrario di livelliUn utente accede ai file attraverso il path namePer semplificare l’accesso ai file viene definito il concetto di current working directory (cwd)I file vengono cercati nella directory correnteSe un file non è nella directory corrente:

Si usa il suo path nameSi cambia la directory corrente

Il SO dispone di alcuni comandi per gestire la cwd

cd dir La directory dir diviene la cwdpwd Mostra il nome della cwd

- - 2020 - -

Directory ad alberoDirectory ad albero

Un esempio di directory ad albero è il seguente

bin mike bill jhon

gcc tcsh test data gnu data foo

aax data type mary work

her mom much

- - 2121 - -

Directory a grafo aciclicoDirectory a grafo aciclico

Utenti diversi vogliono condividere uno o più filePer semplificare l’accesso gli utenti vorrebbero vedere i file condivisi nella propria homeEsistono due soluzioni con caratteristiche differenti

DuplicazioneI file condivisi sono duplicati nelle home degli utentiSpreco di spazio e problemi di allineamento

RiferimentoViene copiato solo il descrittore del file Gli utenti accedono di fatto allo stesso fileLa gestione dei riferimenti richiede un sistema operativo più complesso

- - 2222 - -

Directory a grafo aciclicoDirectory a grafo aciclico

La soluzione migliore è quella basata sui riferimentiSi ha una maggiore complessità del SO, infatti

Deve garantire che il grafo risultante sia aciclicoQuando un file viene rimosso si presenta il problema di come trattare i riferimenti a quel fileUtenti differenti possono accedere simultaneamente allo steso file con il rischio di compromettelo.

Una implementazione sono link di UNIXSoft link: Quando un file viene rimosso i riferimenti rimangono invariati ma puntano ad un file inesistenteHard link: Un file viene rimosso effettivamente solo quando tutti i riferimenti ad esso sono stati eliminati

- - 2323 - -

Directory a grafo aciclicoDirectory a grafo aciclico

Esempio di directory a grafo aciclico:

bin mike bill jhon

gcc tcsh test data gnu much foo

aax data foo mary work

her mom much

- - 2424 - -

Directory a grafo generaleDirectory a grafo generale

Estensione Rimuovere il vincolo di aciclicità del grafoIn questo caso possono esistere riferimenti circolari

Tale struttura risulta estremamente flessibile ma comporta una ulteriore complicazione del sistema operativo, in particolare

Nella ricerca di un file il sistema operativo deve evitare di entrare in un loopGli algoritmi di visita sono più complessiIl problema della rimozione di un file è più complesso

Una soluzione possibile Limitare la profondità di un path name

- - 2525 - -

Directory a grafo generaleDirectory a grafo generale

bin mike bill jhon

gcc mike test data gnu much foo

aax data foo mary work

gnu mom much

Esempio di directory a grafo generale:

- - 2626 - -

Protezione Protezione

I dati di un file system necessitano di protezione

Protezione da danni fisiciMalfunzionamenti dei dispositiviDanni meccanici e/o elettriciSoluzione: backup e mirroring

Protezione da accessi impropriRiservatezzaModifica o eliminazione accidentale di datiSoluzione: definizione di una politica di accesso

Con il termine protezione ci si riferisce allaDefinizione di una politica di accesso Implementazione di una politica di accesso

- - 2727 - -

Protezione Protezione

Alcune banali politiche di accessoOgni utente accede solo ai propri file

Scelta limitante, ad esempio per i gruppi di lavoroOgni utente accede a tutti i file

È assente una politica di accesso

La soluzione consiste nell’accesso controllatoSi definiscono regole di accesso ai file sulla base di

Identità e gruppo di lavoro dell’utenteProprietà dei file

Tali regole dipendono dal tipo di operazione richiesta

LetturaScrittura, eliminazione o aggiuntaEsecuzione o lista

- - 2828 - -

Protezione: Liste di accessoProtezione: Liste di accesso

L’accesso ed le operazioni consentite dipendono dalla identità dell’utenteAd ogni file è associata una lista di accesso o ACL

Indica quali operazioni sono consentite a quali utentiAlla richiesta di una operazione il SO controlla la lista di accesso per verificare se il richiedente:

È contemplato Ha il permesso di compiere quel tipo di operazione

Questa soluzione presenta alcuni svantaggi:Le ACL possono avere dimensioni notevoliLe ACL devono essere create e gestite per ogni fileIl tempo di accesso ad un file viene prolungato

- - 2929 - -

Protezione: UNIXProtezione: UNIX

UNIX adotta una soluzione semplificata Gli utenti sono identificati in base a

username Identificativo dell’utentegroup Identificativo di gruppo

Gli utenti sono raggruppati in tre classiowner Il proprietario del filegroup I membri del gruppo del proprietario del fileall Tutti gli utenti

Le operazioni sono raggruppate in tre classiread Lettura, copiawrite Scrittura, modifica, eliminazioneexecute Esecuzione

- - 3030 - -

Protezione: UNIXProtezione: UNIX

Ad ogni file sono associatiOwnerGroupMode

Il mode è formato da tre gruppi di bitOgni gruppo si riferisce ad una classe di utentiOgni bit del gruppo si riferisce ad una operazione

rwx rwx rwx owner group all

execute

write

read

111 101 101

rwx rwx rwx

7 5 5

- - 3131 - -

ImplementazioneImplementazione

Il sistema operativo fornisce una visione logica del file system fornendo

File, directory, linkAttributi e politiche di accessoOperazioniMapping del file system logico sui dispositivi fisici

Il file system è una struttura stratificata o a livelliOgni livello usa le funzioni fornite dal livello inferioreOgni livello implementa e fornisce funzioni al livello superioreIl livello più basso è costituito dai dispositivi hardware

- - 3232 - -

ImplementazioneImplementazione

I livelli in cui viene suddiviso il file system sono

Applicazione

File System Logico

Modulo di Organizzaione

dei file

File System di Base

Controllo dell’I/O

Dispositivi

Richiedono funzioni al file system logico.

Sulla base del nome di un file e dell’organizzazione delle directory, genera richieste al modulo per l’organizzazione dei file. Legge i descrittori dei file restituendo la posizione.

Conosce l’organizzazione logica e fisica. Traduce le richieste logiche in richieste fisiche verso il file system di base. Genera il numero assoluto di un blocco dato il suo numero relativo all’ inizio del file.

Invia comandi generali alla parte di controllo dell’I/O. Dato il numero di blocco assoluto genera informazioni specifiche quali faccia, settore, traccia, blocco fisico.

Generano i segnali di controllo a partire dai comandi ricevuti. Tali programmi prendono il nome di driver.

Eseguono i comandi richiesti attraverso i driver.

- - 3333 - -

Allocazione ContiguaAllocazione Contigua

I blocchi di un file sono adiacentiUn file di n blocchi è memorizzato nelle posizioni adiacenti b, b+1, …,b+n-2, b+n-1Un descrittore deve indicare solo la coppia (b,n)Problema

Allocazione di spazio per un nuovo fileI tempi di accesso sono brevi in quanto l’accesso

A due blocchi successivi b e b+1 non richiede lo spostamento della testinaAl blocco logico k richiede l’accesso al blocco fisico b+k

134 135 136 … 141

data (134, 8 )

- - 3434 - -

Allocazione ContiguaAllocazione Contigua

Dato un file di m blocchi è necessario individuare una porzione di disco costituita da almeno m blocchi contiguiSi usano tre politiche:

First-Fit: La prima zona, di almeno m blocchi, viene usataBest-Fit: La zona più piccola, di almeno m blocchi, viene usataWorst-Fit: La zona più grande, di almeno m blocchi, viene usata

Le tecniche migliori sono le prime due, in particolare il metodo first-fit risulta più veloceL’allocazione contigua crea, nel tempo, zone inutilizzate di piccole dimensioniTali zone hanno una bassa probabilità di contenere un fileQuesto fenomeno viene detto frammentazione esterna

- - 3535 - -

Allocazione ContiguaAllocazione Contigua

Una soluzione consiste nella compattazione dei dischi

I file su un disco vengono letti e memorizzati temporaneamente altrove (ad esempio su un disco)Il disco originale viene completamente cancellatoI file vengono riscritti in sequenza

Questa operazione è molto costosa in termini di tempo e deve essere compiuta con una certa frequenzaUna soluzione migliore sta nella memorizzazione di un file in due zone differenti, ognuna formata da blocchi contiguiLa zona aggiuntiva prende il nome di extentSono ancora necessari algoritmi per la ricerca di spazio disponibile

- - 3636 - -

Allocazione ContiguaAllocazione Contigua

Un descrittore di file indica (b, e, n1, n2):b: base della sezione principale e: base dell’extentn1: dimensioni della sezione principalen2: dimensione dell’extent

11 12 13 …

data (11, 131, 3, 5 )

130 131 132 133 134 135 …

- - 3737 - -

Allocazione ConcatenataAllocazione Concatenata

L’idea dell’uso di un extent può essere estesa a ad un numero maggiore di estensioniIn questo modo un file è costituito da una sequenza di blocchi in cui:

Il descrittore contine il riferimento al primo e ultimo bloccoOgni blocco contiene un riferimento al blocco successivo

11 12 13 …

data (12, 132 )

130 131 132 133 134 135 …

- - 3838 - -

Allocazione ConcatenataAllocazione Concatenata

Questa soluzione risolve tutti i problemi tipici della allocazione contigua, in particolare:

Non si ha frammentazione esterna

Una parte di ogni blocco è dedicata a contenere un riferimento al blocco successivo

La memorizzazione dei riferimenti riduce lo spazio disponibile per i datiCon blocchi di 512 byte e riferimenti di 4 byte si ha uno spreco di spazio pari allo 0.78% del disco

Dati Riferimento

- - 3939 - -

Allocazione ConcatenataAllocazione Concatenata

Anche questo metodo presenta alcuni svantaggiPer l’accesso casuale è comunque necessario scorrere il file dall’inizio fino al blocco desideratoL’accesso ad un file è meno efficiente in quanto può comportare molti riposizionamenti della testina

Una soluzione consiste nel raggruppare più blocchi in un cluster e prevedere l’accesso ai tali gruppi piuttosto che ai singoli blocchi:

Si ha un miglioramento delle prestazioni per via del numero minore di riposizionamenti della testinaSi ha una riduzione dello spazio utilizzato per i riferimentiSi ha una maggiore frammentazione interna

- - 4040 - -

Allocazione IndicizzataAllocazione Indicizzata

Più efficiente della allocazione concatenataI riferimenti ai blocchi di un file sono raggruppati e memorizzati in un unico blocco indiceUn blocco indice è quindi:

Un vettore di riferimenti ai blocchi del fileL’i-esimo elemento del vettore si riferisce all’i-esimo blocco del file

Il descrittore contiene il riferimento al blocco indiceIn questo modo si ottiene:

Eliminzaione della frammentazione esternaAccesso casuale ai blocchi molto efficiente

- - 4141 - -

Allocazione IndicizzataAllocazione Indicizzata

EOF indica un riferimento vuotoSe un file è costituito da pochi blocchi

Sottoutilizzo del blocco indice (dimensioni fissate)

11 12 13 14 15 16 ...

data (13)

130 131 132 133 134 135 …

16133131EOFEOFEOF

- - 4242 - -

Allocazione IndicizzataAllocazione Indicizzata

E’ importante scegliere una dimensione opportuna per il blocco indicie

Se troppo grande, molto spazio viene sprecatoSe troppo piccolo, non consente di trattare file di grandi dimensioniIn genere il blocco indice coincide con quello fisico

Esistono tre schemi possibili per risolvere i problemi legati alla gestione di file di diverse dimensioni

Schema concatenatoSchema multilivelloSchema combinato

- - 4343 - -

Allocazione IndicizzataAllocazione Indicizzata

Schema concatenato:Il blocco indice ha i riferimenti ai blocchi del fileL’ultimo elemento del blocco indice contiene un riferimento ad un secondo blocco indice, se il file è di grandi dimensioniL’ultimo elemento del blocco indice contiene EOF se tutti i blocchi del file sono già stati referenziati

data (13)

161331311833498

361451132110017

614266EOFEOFEOF

13 98 106

- - 4444 - -

Allocazione IndicizzataAllocazione Indicizzata

Schema multilivello:Un blocco indice di primo livello contiene i riferimenti ai blocchi indice di secondo livelloUn blocco di secondo livello contiene i firerimenti ai blocchi di dati

data (13)

98124106EOFEOF

361451132110

614266EOFEOF

13

98

106

- - 4545 - -

Allocazione IndicizzataAllocazione Indicizzata

Schema combinato:La parte iniziale di un blocco indice contiene riferimenti a blocchi di dati del fileGli ultimi elementi del blocco indice contengono riferimenti ad altri blocchi indiceSe il file ha dimensioni ridotte non viene utilizzato il secondo livello

data (13)

9812410698EOF

3614511EOFEOF

13

98

- - 4646 - -

Allocazione: UNIX Allocazione: UNIX i-nodei-node

ModeOwner, group

TimestampSize

Number of blocksNumber of references

Direct blocks (12)

Single indirect blocksDouble indirect blocksTriple indirect blocks

Data

Data

Data

Data

Data

Data

Data

Data

Data

Data

Data

Data

Data

i-node

- - 4747 - -

Gestione dello spazio liberoGestione dello spazio libero

All’atto della creazione di un nuovo file è necessario individuare sul disco il primo blocco liberoUna soluzione sta nell’uso un vettore di bit in cui

La posizione del bit indica il numero del bloccoSe il bit vale 0 il blocco è già utilizzatoSe il bit vale 1 il blocco è disponibile

Si individua il primo blocco libero in questo modoSi scorrono le parole (di b bit) fino alla prima diversa da 0Sia k il numero di parole uguali a zeroSi trova l’offset d del primo bit con valore 1L’indirizzo n del blocco è dato da n = k x b + d

- - 4848 - -

Gestione dello spazio liberoGestione dello spazio libero

Una soluzione alternativa si basa sull’utilizzo di una lista concatenata, simile a quella utilizzata per i fileIn questo schema:

La posizione del primo blocco disponibile è memorizzata in una zona riservata del discoOgni blocco disponibile contiene un riferimento al blocco disponibile successivo

Questa soluzione è migliore della precedente per dischi di grandi dimensioni

- - 4949 - -

Realizzazione delle directoryRealizzazione delle directory

La soluzione più semplice è una lista lineare in cui ogni elemento contiene

Il nome del file Il descrittore del file

Per velocizzare le operazioni di accesso la lista viene ordinata lessicograficamente

bar

i-node

data

i-node

foo

i-node

zap

i-node

end

Data Data Data Data

- - 5050 - -

Realizzazione delle directoryRealizzazione delle directory

Le operazioni sui file EliminazioneCreazioneRinomina ...

Richiedono una ricerca del nomeLa ricerca è di semplice realizzazione ma è poco efficiente ( è lineare nel numero degli elementi)Una lista ordinata lessicograficamente:

Consente una ricerca binaria (logaritmica)Comporta problemi aggiuntivi per mantenere la lista in ordine

- - 5151 - -

Realizzazione delle directoryRealizzazione delle directory

Una tecnica più efficiente consiste nell’uso di una tabella di hash o funzione di hashLa funzione di hash

sulla base del nome del file,resrtituisce un riferimento, detto chiave o key, al descrittore di file

I descrittori sono memorizzati in una lista lineare

Funzionedi hash

Key 1

Key 2

Key 3

Key N

foo

- - 5252 - -

Realizzazione delle directoryRealizzazione delle directory

Un limite di questo metodo sta nei potenziali conflitti cioè quelle situazioni in cui per due nomi differenti la tabella restituisce lo stesso puntatore

Funzionedi hash

Key 1

Key 2

Key K

Key N

foo

Funzionedi hashfrob

- - 5353 - -

Realizzazione delle directoryRealizzazione delle directory

Una soluzone è quella di utilizzare liste lineari di elementi aventi lo stesso codice di hashSi ha un impatto notevole sulle prestazioni che comunque risultano migliori rispetto all’uso di una lista lineare semplice

Key 1

Key 2

Key K

Key N

alpha

i-node

arpa

i-node

ax

i-node

end

foo

i-node

frob

i-node

end

end