Modulo 12: File System
• Livelli logici per l’accesso ai file
• Organizzazione dei file su disco
• Organizzazione di un File System di UNIX
Sistemi Operativi
12.1
Laface 2001 - Bach
Livelli logici per l’accesso ai file
Programmi utente
Pile
Sequenziali
Sequenziali
indicizzati
Indicizzati
Hash
Logical I/O
Basic I/O Supervisor
Basic File System
Disk device driver
Sistemi Operativi
Tape device driver
12.2
Laface 2001 - Bach
Strutture di file
• Pila : i dati sono organizzati in record di dimensioni non
definita mantenuti nell’ordine con il quale arrivano
• I file sequenziali : hanno una struttura formata da record di
dimensione fissa e tutti con la stessa suddivisione in
campi.
– Un campo, detto chiave del record, permette di
identificare un record in maniera univoca e quindi di
stabilire un ordinamento tra i record.
Sistemi Operativi
12.3
Laface 2001 - Bach
Strutture di file
•
I file sequenziali indicizzati memorizzano delle informazioni
ulteriori per accelerare l’introduzione e la ricerca dei dati.
1. un file di indice con il quale gestire gli accessi casuali
2. un file di overflow per consentire gli inserimenti di nuovi
elementi mantenendo l’ordinamento complessivo.
Livelli di
Indicizzazione
2
1
Main File
Indice
Overflow File
Sistemi Operativi
12.4
Laface 2001 - Bach
Strutture di file
•
I file ad accesso diretto o gestiti mediante hashing
– I record non necessitano un ordinamento sequenziale.
– Sono usati qualora sia necessario un accesso molto
rapido ed i record hanno dimensione fissa.
Funzione di
hash
Chiave
f
Primary File
Sistemi Operativi
12.5
Overflow File
Laface 2001 - Bach
Directory
spell
stat
mail
prog
list
dist
copy
obj
Sistemi Operativi
spell
find
prt
bin
count
programs
hex
find
exp
last
all
12.6
reorder
list
p
reorder
e
mail
count
first
Laface 2001 - Bach
hex
Funzioni di accesso ai file
Blocchi fisici nei buffer in Blocchi fisici in
memoria principale
memoria secondaria
Record
Struttura dei file
Metodi di
Gestione delle
directory
accesso
Scheduling
del disco
Gestione dei
blocchi
Comandi
utente
Funzioni di
manipolazione
dei file
Operazioni,
nomi dei file
Gestione dello
spazio libero
Allocazione dei
file
Controllo degli
accessi degli
utenti
Funzioni del Sistema Operativo
Funzioni del File management
Sistemi Operativi
12.7
Laface 2001 - Bach
Organizzazione dei file su disco
•
Descrittore del file
– Tipo del file
– Tipo di file system
– Volume
– Indirizzo di partenza
– Dimensioni
– Owner
– Azioni permesse
– Informazioni d’uso (quando/chi ha scritto/letto/modificato per
ultimo, …)
Sistemi Operativi
12.8
Laface 2001 - Bach
Allocazione contigua
• Vantaggio: velocità d’accesso
• Svantaggi: frammentazione dello spazio disponibile
Sistemi Operativi
12.9
Laface 2001 - Bach
Allocazione linkata
directory
0
1
4
5
8
9
12
13
14
15
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
16
Sistemi Operativi
1
10
16
-1
2
3
6
7
10
25
File
prova
Blocco inizio
9
Blocco di fine
25
11
12.10
Laface 2001 - Bach
Allocazione linkata - FAT
elemento della directory
test
nome
0
blocco
iniziale
217
Numero dei blocchi
Sistemi Operativi
FAT
217
......
12.11
217
618
339
fine del file
618
339
-1
Laface 2001 - Bach
Allocazione indicizzata
directory
Sistemi Operativi
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
File
prova
Blocco indice
19
19
12.12
9
16
1
10
25
-1
Laface 2001 - Bach
Organizzazione di un File System di UNIX
Blocco
di boot
Super
blocco
Sistemi Operativi
Lista degli
inode
12.13
Blocchi di
dati
Laface 2001 - Bach
Organizzazione di un File System di UNIX
•
•
•
•
il blocco di boot risiede generalmente nel primo settore che
costituisce il File System e contiene il codice di bootstrap che
viene eseguito dalla macchina all’avviamento
il superblocco serve per descrivere lo stato del File System
ovvero la sua dimensione, quanti file può contenere, dove trovare
spazio libero sul disco ed altre informazioni
la lista degli inode contiene tutti I descrittori disponibili nel
sistema e la sua dimensione dipende da quanto specificato in
fase di configurazione del sistema
i blocchi di dato contenenti i file utente e quelli di gestione del
sistema
Sistemi Operativi
12.14
Laface 2001 - Bach
Inode
•
•
•
•
•
•
•
Proprietario: il possesso del file è condiviso tra un proprietario ed
un gruppo. Il Super User ha diritto di accesso a tutti i file del
sistema.
Tipo di file: normale, directory, speciale a blocchi o a caratteri,..
Permessi di accesso al file: tre classi di utenti: proprietario,
gruppo del proprietario e altri utenti.
– I permessi di lettura, scrittura ed esecuzione possono essere
fissati individualmente per ogni classe.
– Poiché le directory non possono essere eseguite, i permessi di
esecuzione per una directory consentono l’attraversamento
della directory.
Tempi di accesso al file: riportano l’ultima volta che il file è stato
modificato, riferito e l’ultima volta che è stato modificato l’inode.
Numero di link al file
Dimensione del file
Tabella degli indirizzi di disco dei dati in un file
Sistemi Operativi
12.15
Laface 2001 - Bach
Esempio di Inode
Proprietario:
laftes1
Gruppo:
laface
Tipo:
file ordinario
Permessi:
rwxr-xr-x
Accesso:
23 Ottobre 2001
h: 8:15
Modificato:
22 Ottobre 2001
h: 10:30
Inode:
23 Ottobre 2001
h: 13:30
Dimensione:
3050 byte
Indirizzi su disco
(13 puntatori)
Sistemi Operativi
12.16
Laface 2001 - Bach
Copia di un Inode in memoria
•
•
•
•
•
ll numero dell’inode
Lo stato dell’inode che indica se
– l’inode è occupato
– la copia in memoria dell’inode è diversa da quella su disco a
causa degli aggiornamenti che ancora non sono stati registrati
– il file è un punto di mount
il numero del device logico del File System che contiene il file
un contatore di quanti riferimenti al file sono contemporaneamente
attivi
i puntatori ad altri inode in memoria, al fine di poterli organizzare in
code e liste come già visto per i buffer
Sistemi Operativi
12.17
Laface 2001 - Bach
Funzioni di gestione del File system
namei
alloc
iget
iput
free ialloc
ifree
bmap
algoritmi di allocazione dei buffer
getblk
Sistemi Operativi
brelse
bread
12.18
breada
bwrite
Laface 2001 - Bach
iget
•
La funzione iget alloca in memoria una copia dell’inode associato
al file restituendo in output un inode con un contatore di riferimenti
incrementato di 1 (hash table e cache per efficienza).
•
L’inode viene bloccato durante una chiamata di sistema per evitare
che altri processi possano accedervi contemporaneamente e creare
situazioni inconsistenti. Il blocco viene rilasciato solo alla fine della
chiamata.
•
Nel caso l’inode non sia presente nella coda hash, viene ricercato il
primo inode disponibile presente nella free list ed occupato.
•
Nel caso la free list sia vuota, il kernel restituisce un errore.
Sistemi Operativi
12.19
Laface 2001 - Bach
iget
procedura
iget
input:
numero di inode nel file system
output:
inode bloccato
{
while (non fatto){
if (inode nella cache di inode){
if (inode bloccato){
sleep (evento inode libero);
continue;
}
if (inode nella free list di inode)
togli inode dalla free list;
incrementa contatore di riferimenti all’inode;
return inode;
}
/* inode non presente nella cache di inode */
if (nessun inode nella free list)
return errore;
togli il nuovo inode dalle free list;
azzera numero di inode e di file system;
togli inode dalla vecchia coda hash, inserisci nella nuova;
leggi inode da disco (procedura bread);
inizializza inode;
return inode;
}}
Sistemi Operativi
12.20
Laface 2001 - Bach
Struttura di un file normale
I-node
Blocchi di dati
0
1
2
3
4
5
6
7
8
9
indiretto singolo
indiretto doppio
indiretto triplo
Sistemi Operativi
12.21
Laface 2001 - Bach
Index block
• 10 blocchi diretti da 1 Kbyte ciascuno = 10 Kbyte
• 1 blocco indiretto con 256 blocchi diretti = 256 Kbyte
• 1 blocco doppiamente indiretto con 256 blocchi indiretti
• 1 blocco triplamente indiretto con 256 blocchi
= 64 Mbyte
doppiamente indiretti = 16 Gbyte
Sistemi Operativi
12.22
Laface 2001 - Bach
iput
• La procedura di rilascio di un inode iput
viene invocata
quando viene eseguita la close di un file.
• Viene bloccato l’inode per evitare inconsistenze.
• Contatore di riferimenti è decrementato.
• Se tale contatore vale zero, il kernel scrive l’inode su disco
se la copia presente in memoria differisce da quella su
disco.
• Inoltre, non essendoci più alcuna copia attiva del file,
l’inode deve essere liberato e riposto nella free list.
• Il kernel rilascia anche tutti i blocchi di dati associati al file
e libera l’inode nel caso il numero di link sia zero.
Sistemi Operativi
12.23
Laface 2001 - Bach
iput
procedura
iput
input: puntatore all’inode in memoria
output: nessuno
{
blocca l’inode se non è già bloccato;
decrementa il contatore di riferimenti dell’inode;
if (contatore di riferimenti == 0){
if (contatore di link all’inode == 0)
{
libera blocchi di disco del file (procedura free);
pone tipo file a = 0;
libera inode (procedura ifree);
}
if (file acceduto o file cambiato o inode cambiato)
aggiorna inode di disco;
metti inode nella free list;
}
rilascia blocco inode;
}
Sistemi Operativi
12.24
Laface 2001 - Bach
bmap
•
•
serve per convertire un offset in byte all’interno di un file nel
corrispondente numero di blocco fisico su disco.
dato un offset, ricava tramite l'uso delle catene di puntatori
presenti nell’inode, qual è il blocco nel quale sono effettivamente
presenti i dati richiesti, e restituisce un puntatore a quel blocco.
Sistemi Operativi
12.25
Laface 2001 - Bach
bmap
procedura bmap
input:
(1) inode (2) offset in byte
output:
(1) numero blocco nel file system,(2) offset in byte nel blocco
(3) byte di I/O nel blocco. (4) numero blocco per lettura in avanti
{
calcola numero blocco logico nel file dall’offset in byte;
calcola byte iniziale nel blocco per l’I/O;
calcola numero di byte da copiare per l’utente;
controlla se è applicabile la lettura in avanti, marca l’inode;
determina il livello di indirezione;
while (non al necessario livello di indirezione){
calcola indice nell’inode e il blocco indirizzato dal numero di
blocco logico nel file;
prende il numero di blocco del disco dall’inode o dal blocco
indiretto; (eventuale brelse)
if (non altri livelli di indirezione) return numero blocco;
legge blocco indiretto;
sistema il numero di blocco logico nel file a seconda del
livello di indirezione;
}}
Sistemi Operativi
12.26
Laface 2001 - Bach
Esempio di Inode
I-node
4096
228
45423
0
0
11111
0
101
367 blocco di
dati
367
0
331
428
9156
824
3333
3333 blocco
di dati
9156 indirezione
doppia
331 indirezione
singola
Sistemi Operativi
12.27
Laface 2001 - Bach
Directory
• r:
la directory è leggibile e quindi il suo contenuto può
essere visualizzato
• w:
è possibile creare nuove entry o rimuovere quelle già
presenti attraverso le chiamate di sistema creat,
mknod, link ed unlink
• x: un processo può attraversare la directory, cioé leggere il
contenuto degli Inode associati ai nomi di file contenuti
nella directory.
Sistemi Operativi
12.28
Laface 2001 - Bach
1. mkdir junk
2. for i in 1 2 3 4 5
3. do
4. echo salve > junk/$i
5. done
6. ls -ld junk
7. ls -l junk
8. chmod -r junk
9. ls -ld junk
10.ls junk
11.ls -l junk
12.cd junk
13.pwd
14.ls -l
15.echo *
16.cd ..
17.chmod +r junk
18.chmod -x junk
19.ls junk
20.ls -l junk
21.cd junk
22.chmod +x junk
Sistemi Operativi
drwxr-xr-x 2 user1 512 Feb 20 16:24
-rw-r--r-- 1 user1
6 Feb 20 16:24
-rw-r--r-- 1 user1
6 Feb 20 16:24
-rw-r--r-- 1 user1
6 Feb 20 16:24
-rw-r--r-- 1 user1
6 Feb 20 16:24
-rw-r--r-- 1 user1
6 Feb 20 16:24
d-wx--x--x 2 user1 512 Feb 20 16:24
junk unreadable
junk unreadable
/home2/user1/prova/junk
. unreadable
*
1
2
3
4
5
ls: junk/1: Permission denied
ls: junk/2: Permission denied
ls: junk/3: Permission denied
ls: junk/4: Permission denied
ls: junk/5: Permission denied
total 0
command: junk: Permission denied
12.29
junk
1
2
3
4
5
junk
Laface 2001 - Bach
namei
•
•
•
•
•
La procedura namei converte un pathname in un inode in modo
da poter accedere ad un file.
Analizza un componente del pathname alla volta, convertendolo
nel relativo inode.
Il puntatore all’inode della directory corrente di un processo è
contenuta nella u-area.
La directory corrente di ogni processo al momento della
creazione coincide con quella del processo padre, ma la può
cambiare usando la system call chdir.
Tutte le ricerche di pathname partono dalla directory corrente del
processo a meno che il pathname non inizi con “/” che indica un
pathname assoluto.
Sistemi Operativi
12.30
Laface 2001 - Bach
namei
procedura namei
/* converte pathname in inode */
input:
pathname
output: inode bloccato
{
if (pathname parte dalla radice)
inode lavoro = indice radice (procedura iget);
else
inode lavoro = inode directory attuale (procedura iget);
while (pathname non finito){
leggi successivo componente pathname dall'input;
verifica che l'inode lavoro sia una directory, permessi di accesso OK;
if (inode lavoro è radice e il componente è "..") continue;
leggi directory (inode lavoro) usando le procedure bmap, bread, brelse;
if (componente coincide con un'entry di directory (inode lavoro)) {
prende numero inode componente coincidente;
rilascia inode lavoro (procedura iput);
inode lavoro = inode componente coincidente (procedura iget);
}
else
/* componente non nella directory */
return (nessun inode);
}
return (inode lavoro);
}
Sistemi Operativi
12.31
Laface 2001 - Bach
Scansione del pathname ../a/b
a Inode
U-area
Current
directory
.. Inode
Inodes
b Inode
. Inode
b
Current dir
Files
Parent dir
a directory
Sistemi Operativi
12.32
Laface 2001 - Bach
Superblocco
•
•
•
•
•
•
•
•
•
•
dimensione del File System
numero di blocchi liberi disponibili nel File System
lista dei blocchi liberi disponibili nel File System
indirizzo del successivo blocco libero nella lista dei blocchi liberi
dimensione della lista di inode
numero di inode liberi nel File System
lista di inode liberi nel File System
indirizzo del successivo inode libero nella lista degli inode liberi
campi di lock per la lista di blocchi liberi e di inode liberi
flag che indica se il super blocco è stato modificato
Sistemi Operativi
12.33
Laface 2001 - Bach
ialloc - ifree
•
•
•
•
La procedura ialloc assegna un inode del disco ad un file che deve
essere creato.
Il File System mantiene una lista lineare di inode nella quale gli inode
liberi presentano il campo tipo uguale a zero.
Quando un processo richiede un nuovo inode, il kernel non effettua
una ricerca lineare sulla lista perché risulterebbe troppo costosa, ma
mantiene nel super blocco un array degli inode liberi presenti nel File
System.
La procedura ifree rilascia l’inode di un file che stato cancellato
(mediante la system call unlink), e non è attualmente in uso.
Sistemi Operativi
12.34
Laface 2001 - Bach
Allocazione di blocchi di disco
Lista del superblocco
109
106
103
100
208
205
202
. . . . . . . . . . . . . 112
.
307
304
301
. . . . . . . . . . . . . 214
.
406
403
400
. . . . . . . . . . . . . 313
.
. . . . . . . . . . . . . . . . . .
109
211
211
310
310
409
Sistemi Operativi
12.35
Laface 2001 - Bach
alloc
•
La procedura alloc permette di allocare il primo blocco libero
presente nella lista contenuta nel super blocco.
•
Se il blocco è l’ultimo disponibile nella cache del super blocco, il
kernel usa il numero ottenuto come puntatore ad un blocco
contenente il prossimo elemento della lista linkata, che viene
caricato integralmente nella cache.
•
Il blocco che conteneva indirizzi di blocchi liberi del disco, ormai
vuoto, viene usato come blocco di dati da allocare al processo
che lo richiede.
Sistemi Operativi
12.36
Laface 2001 - Bach
Esempio di alloc e free
Lista del superblocco
Lista del superblocco
. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
109
109 949
109
109
211 208205202
. . . . . . . . . . . . . .
112
109
109
211 208205202
.
. . . . . . . . . . . . . .
112
a, b - Configurazione iniziale e dopo il rilascio del blocco 949
Lista del super blocco
109
Lista del superblocco
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
109
109
211 208205202
211 208205202
. . . . . . . . . . . . . .
112
211
109
344341338335
. . . . . . . . . . . . . .
112
. . . . . . . . . . . . . .
243
c, d - Assegnazione del blocco 949 ed assegnazione del blocco 109
con riempimento della free list del super blocco
Sistemi Operativi
12.37
Laface 2001 - Bach