File System
Concetti e tecniche generali
1
Il file system
• Il file system è la parte del SO che si occupa
di mantenere i dati/programmi in modo
persistente
• Tipicamente le astrazioni fornite sono:
– File : unità di informazione memorizzata in
modo persistente
– Directory : astrazione che permette di
raggruppare assieme più file
2
Struttura di un File
• Come può essere strutturata l’informazione
all’interno di un file
– sequenze di byte, sequenze di record , alberi con
chiave
3
Accesso ai File
• Accesso diretto (random)
– i byte/record possono essere letti in qualsiasi ordine
– una read può essere specificata …
• specificando la posizione del dato da accedere ad ogni
chiamata, …
• usando una speciale operazione (la seek) per posizionare
la testina prima di iniziare più letture
– nei moderni sistemi operativi tutti i file sono
automaticamente ad accesso diretto
4
Tipici attributi di un file
5
Operazioni su File
1.
2.
3.
4.
5.
6.
Create
Delete
Open
Close
Read
Write
7. Append
8. Seek
9. Get attributes
10.Set Attributes
11.Rename
6
File system gerarchici
root directory
A
B
C
f
B1 Ss.c B2
C1
C3
C2
d
e
• Tutti i file system attuali sono gerarchici
– utilizzano i path name visti in Unix
– separatori root diversi
7
Operazioni sulle directory
1.
2.
3.
4.
Create
Delete
Opendir
Closedir
5. Readdir
6. Rename
7. Link
8. Unlink
8
Implementazione di un File System (1)
• Come rappresentare i file ?
– i dati sono memorizzati in unità (blocchi) di ampiezza fissa
(tipicamente 1,2 KB)
– si devono memorizzare gli attributi e la posizione dei singoli
blocchi
• Come rappresentare le directory ?
– generalmente sono file con uno speciale formato
• Come organizzare lo spazio disco ?
– allocazione dei blocchi relativi ad un singolo file
– gestione blocchi liberi
– tenere traccia della root directory
9
Implementazione di un FS: Unix (2)
Tabella delle partizioni
Part 1
Part 2
...
root d.
Blocchi di dati
Part k
MBR
Superblocco
I-nodi
Free mgm
Riservato al boot block
10
Implementazione dei File (1)
• Allocazione contigua dello spazio disco
– ogni file viene memorizzato in un gruppo di
blocchi contigui (run)
– es :
Situazione iniziale (tutti i blocchi sono liberi)
run
Situazione dopo l’allocazione del File A (4 blocchi)
11
Allocazione contigua (2)
Situazione dopo l’allocazione del File A (4 blocchi) e B (3 blocchi)
File D (3 blocchi)
File B (3 blocchi)
File A (4 blocchi)
File C (6 blocchi)
File G (3 blocchi)
File E (5 blocchi)
Situazione dopo la cancellazione di B e D
Blocchi liberi
12
Allocazione contigua (3)
• Fenomeno della frammentazione interna :
– se l’ultimo blocco non è del tutto pieno si
spreca dello spazio
13
Allocazione contigua (4)
• Vantaggi dell’allocazione contigua:
– è facile tenere traccia dei blocchi che
appartengono a ciascun file
• indirizzo su disco del blocco iniziale (B)
• lunghezza del file (in blocchi)
– se voglio l’indirizzo del blocco X del file
• ind(X) = B + X
– le prestazioni della lettura sono eccellenti
• basta una seek ed è possibile leggere tutto il file in
blocchi contigui (senza rotational delay …)
14
Allocazione contigua (5)
• Svantaggi dell’allocazione contigua:
– (1) frammentazione esterna : es
Situazione dopo la cancellazione di B e D
– dopo un po’ il disco sarà frammentato in un
insieme di buchi (hole), troppo piccoli per
contenere un file (es. file R 5 blocchi)
– de-frammentazione del disco :
15
Allocazione contigua (6)
• Svantaggi dell’allocazione contigua (cont.):
– (2) l’ampiezza massima di un file deve essere
decisa al momento della creazione
• dobbiamo riservare un numero adeguato di blocchi
per la sua crescita futura
• ancora spazio sprecato
• difficile da stimare ed utilizzare : es prima di iniziare
ad editare un file di testo devo dire quanto sarà
lungo … altrimenti l’editing può fallire!!!!
16
Allocazione contigua (7)
• Svantaggi dell’allocazione contigua (cont.):
– (2) l’ampiezza massima di un file deve essere
decisa al momento della creazione
• dobbiamo riservare un numero adeguato di blocchi
per la sua crescita futura
• ancora spazio sprecato
• difficile da stimare ed utilizzare : es prima di iniziare
ad editare un file di testo devo dire quanto sarà
lungo … altrimenti l’editing può fallire!!!!
• L’allocazione contigua viene utilizzata nei
FS dei CD ROM e DVD !!
17
File: lista concatenata di blocchi
Memorizzazione come lista concatenata di blocchi
18
File: lista concatenata di blocchi (2)
• Vantaggi della lista concatenata :
– non c’è frammentazione esterna
– per ogni file è necessario mantenere solo il
puntatore al primo blocco
• Problemi :
– lettura di tutto il file molto lenta
– accesso random molto lento
– perdita di un certo numero di byte iniziali
• l’ampiezza di blocco non è più una potenza di 2
• diventa più costoso il calcolo del blocco ...
19
File: lista concatenata di blocchi (3)
• Es. indirizzi di 4 byte, blocchi fisici di 1 K
– se voglio effettuare una read di 40 byte
dall’indirizzo 2046
– divido 2046 per (1024 -4=1020) :
• risultato = 2, resto = 6
• devo leggere 40 byte, in blocco 2 a partire dal byte 6
– le divisioni per numeri arbitrari sono operazioni
estremamente costose
– le divisioni per potenze di 2 sono shift !!
20
Liste concatenate con FAT
terminatore
La FAT si trova
in memoria centrale
21
Liste concatenate con FAT
• Vantaggi :
– l’ampiezza di blocco è una potenza di due
– accesso casuale più veloce (non accede alla
memoria secondaria
• Svantaggi :
– tutta la FAT deve stare in memoria
– disco 20 GB, blocchi 1K
• ampiezza FAT = 4* 20M !
• Paginazione, lentezza etc ...
22
Index-node (i-node)
• Es. i-node di un file Unix
Attributi
Dati su disco
Ind blocco 1
Ind blocco 2
...
Ind blocco N
Single indirect
...
Double indirect
Triple indirect
23
Index-node (i-node) (2)
• Vantaggi :
– solo gli i-node dei file in uso devono risiedere
in RAM
– lo spazio è proporzionale al numero massimo di
file aperti e non dipende dall’ampiezza del
disco
– l’efficienza decresce con l’ampiezza del file
24
Implementazione delle Directory (1)
• Devono permettere di recuperare tutte le
informazioni relative ai file contenuti
• Punto fondamentale : associare il nome del
file (una stringa di caratteri) ad attributi e
dati (indirizzo/i dei blocchi)
– diversi formati
– diverse restrizioni sui possibili nomi dei file
• lunghezza fissa o arbitraria
• case sensitiveness : pippo e PiPPo
25
Implementazione delle Directory (2)
• Soluzione più semplice :
– la directory contiene una tabella con un
elemento per ogni file
– attributi e indirizzi del blocchi del file X sono
memorizzati direttamente nell’elemento della
tabella relativo ad X
– è la soluzione usata dai FS FAT-16, FAT-32
26
Implementazione delle Directory (3)
games
attributi
Blocco/i
mail
attributi
Blocco/i
news
attributi
Blocco/i
work
attributi
Blocco/i
27
Implementazione delle directory (4)
Una directory in un sistema con i-node
– es da Unix V7
4
.(punto)
16
..(punto punto)
12
e
18
d
Numero di
i-node
C1
4
C2
d
16
e
12
18
Blocco dati relativo alla
directory C2
28
Implementazione delle directory (5)
• Due modi di trattare i nomi di file “lunghi”
– (a) In linea (b) In un heap
29
Implementazione delle directory (6)
• Ricerca di un file X in una directory
– tipicamente i nomi dei file non sono in ordine (ricerca
lineare)
– se aspettiamo directory con centinaia di file si possono
usare hash table
nomefile
Funzione hash (0..N-1)
Es : H(nomefile)=f(nomefile)%N
N-1
Ricerca:
1. X= H(nomefile)
2. Ispeziono la lista
X
che parte da X
3. Se nomefile non sta nella
lista non c’è
tabella
0
30
Implementazione delle directory (7)
• Ricerca di un file X in una directory
– tipicamente i nomi dei file non sono in ordine
(ricerca lineare)
– se aspettiamo directory con centinaia di file si
possono usare hash table
– alternativamente si può fare il caching di file
acceduti recentemente (Berkley FFS)
31
Gestione dello spazio disco (1)
• Praticamente tutti i file system:
– dividono i file in blocchi di ampiezza fissata ed
eseguono letture e scritture su blocchi o
multipli
– i blocchi non sono contigui su disco
• Problema 1 : come scegliere l’ampiezza del
blocco?
– Blocchi piccoli usano meglio lo spazio disco
• diminuiscono la frammentazione interna
– Blocchi grandi velocizzano gli accessi
• diminuiscono seek e rotational delay
32
Gestione dello spazio disco (2)
• Problema 2 : come tenere traccia dei blocchi
liberi su disco ?
– Free list
• lista concatenata di blocchi pieni di indirizzi di
blocchi liberi
– Bitmap
• una mappa di bit con un bit per ogni blocco
• es. 0 blocco libero, 1 blocco in uso
• mantiene la contiguità dei blocchi (allocare un file
su blocchi vicini diminuisce il tempo di seek in
letture consecutive
33
Gestione dello spazio disco (3)
Free list
Bitmap
34
Gestione dello spazio disco (4)
(a) blocco di puntatori ai blocchi liberi quasi pieno (RAM)
- tre blocchi di puntatori su disco
(b) situazione dopo aver liberato un file di 3 blocchi
(c) strategia alternativa per gestire i 3 blocchi
- gli elementi in grigio puntano a blocchi di disco liberi
35
Gestione dello spazio disco (4)
Tabella dei file aperti
Attributi
userid = 8
Tabella delle quote
Soft block limit
Hard block limit
pun_quota
….
Current # blocks
# block warning left
Quota utente 8
(una struct
per ogni
utente con file
aperti)
Soft file limit
Hard file limit
Current # file
# file warning left
Il meccanismo delle quote per tener traccia dello
spazio disco utilizzato da ciascun utente
36
Affidabilità di un file system
• Problemi legati all’hw del disco
– settori difettosi
• sostituzione con spare sectors
– blocchi corrotti
• raccolti in file fittizi (bad block files)
37
Gestione degli errori del disco
• Una traccia con un settore difettoso
• Sostituzione del settore difettoso con un
settore di riserva
• Slittamento dei settori per evitare quello
difettoso
38
Affidabilità di un file system (2)
• Backup periodici
– copia delle informazioni del FS per poterle
utilizzare in caso di
• crash del disco, alluvioni etc ...
• cancellazioni accidentali
– backup fisico
• si copiano tutti i blocchi del disco (su tape o altro)
– backup logico
• si copiano file e directory modificati dopo una certa
data
39
Stable Storage
• Memorizzazione stabile
• Permette di mettersi al riparo da errori che si
verificano durante una scrittura :
– sto effettuando una write()
– dopo la scrittura calcolo i codici correttori di errore
(ECC) che segnalano un malfunzionamento
– a questo punto il vecchio valore del settore è andato
perso ed il nuovo è sbagliato!
• Nello stable storage, ogni volta che eseguiamo
una scrittura si garantisce che il valore scritto è
corretto oppure è uguale a quello vecchio
40
Stable Storage (2)
Come viene realizzato lo stable storage:
• due dischi, più software
• assunzioni :
– quando effettuiamo una write() di un blocco si scrive una
valore corretto o scorretto
– un valore scorretto può essere determinato rileggendo il
valore e controllando gli ECC
– la probabilità che lo stesso settore X abbia
malfunzionamenti su due dischi diversi è trascurabile
41
Stable Storage (3)
Implementazione :
– Ogni blocco viene implementato usando due blocchi
con lo stesso indirizzo sui due dischi.
• Scritture : scrive la stessa infromazione prima nel primo
disco (blocco X) e poi nel secondo (blocco X)
• Letture : legge dal primo disco e se ci sono errori dal
secondo
– Recovery dopo un crash
• si leggono tutti i blocchi dei due dischi e si confrontano
• se sono corretti e uno dei due ha l’ECC sbagliato, viene
sovrascritto con l’altro
• se sono diversi ma corretti, il blocco del primo disco
viene scritto sul secondo
42
Stable Storage (4)
– Casi possibili di crash in uno stable storage
43
Consistenza di un File System (1)
• Problema:
– tipicamente i file system leggono un bloccho, lo
modificano e scrivono la copia aggiornata più tardi
– se avviene un crash prima della scrittura della copia
aggiornata il FS può trovarsi in uno stato inconsistente
– il problema è ancora più preoccupante se si tratta di inode, informazioni di una directory o informazioni sui
blocchi liberi
• Ci sono utility che
– controllano la consistenza di un file system
– lo riportano in uno sttao consistente (eventualmente con
la perdita di dati)
– es: scandisk (Windows) fsck (Unix)
44
Consistenza di un File System (2)
Funzionamento di fsck
• Verifica la consistenza dei blocchi
– scandisce i-node e blocchi liberi
– costrisce tabella blocchi liberi e tabella blocchi in uso
• 00 missing block - viene aggiunto alla lista libera
• 20 duplicate free block - viene ricostruita la lista libera
• 02 duplicate data block - viene duplicato il blocco per avere una
copia diversa in ciascun file
• Verifica la consistenza delle directory
– scandisce le directory
– costruisce la tabella di occorrenza file
– controlla la consistenza fra la tabella di occorrenza ed il
conto degli hard link nell’i-node
• se differiscono si modifica l’i-node
45
Consistenza di un File System (3)
Numero di blocco
(c)
Numero di blocco
(d)
(a) consistente (consistent)
(b) blocco mancante (missing block)
(c) blocco duplicato nella lista libera (duplicate free block)
(d) blocco dati duplicato (duplicate data block)
46
Prestazioni di un File System (1)
Block cache
Buffer cache
• Strutture dati per il cache dei blocchi
• Hash su dispositivo::indirizzo del blocco
• I blocchi critici per la consistenza del FS vengono
scritti subito (i-node, directory, lista libera)
47
Prestazioni di un File System (2)
• Si effettua la lettura anticipata (read ahead)
– si controlla il pattern di accesso del disco e se
ne tiene traccia nell’i-node
– se l’accesso è sequenziale si leggono in anticipo
i prossimi blocchi della sequenza e si
memorizzano nella cache
• Si cerca di allocare blocchi di disco ‘vicini’
per blocchi logici ‘vicini’ di uno stesso file
• Si ottimizza l’allocazione degli i-node
– si cerca di minimizzare il tempo di seek quando
si segue un path name
48
Prestazioni di un File System (3)
(a) Gli i-node sono piazzati all’inizio del disco
(b) Il disco è diviso in gruppi di cilindri, ognuno con i suoi
blocchi ed i suoi i-node
49