Date post: | 01-May-2015 |
Category: |
Documents |
Upload: | giuseppe-gambino |
View: | 216 times |
Download: | 0 times |
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 [email protected]@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