Laface 2001 - Bach 12.1 Sistemi Operativi Modulo 12: File System Livelli logici per laccesso ai file...
-
Upload
sonia-rossa -
Category
Documents
-
view
212 -
download
0
Transcript of Laface 2001 - Bach 12.1 Sistemi Operativi Modulo 12: File System Livelli logici per laccesso ai file...
Sistemi Operativi Laface 2001 - Bach12.1
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 Laface 2001 - Bach12.2
Livelli logici per l’accesso ai file
Tape device driverDisk device driver
Basic File System
Basic I/O Supervisor
Logical I/O
Pile SequenzialiSequenziali indicizzati
Indicizzati Hash
Programmi utente
Sistemi Operativi Laface 2001 - Bach12.3
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 Laface 2001 - Bach12.4
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.
Main File
Overflow File
Indice
Livelli di
Indicizzazione
12
Sistemi Operativi Laface 2001 - Bach12.5
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.
Primary File Overflow File
Chiave
Funzione di hash
f
Sistemi Operativi Laface 2001 - Bach12.6
Directory
reorder
spell programs bin
stat dist mail p mail e find hex count
exp prog prt copy reorder list find hex count
list spell obj all first last
Sistemi Operativi Laface 2001 - Bach12.7
Funzioni di accesso ai file
nomi dei file
Operazioni,
Comandi utente
Gestione delle directory
Controllo degli accessi degli
utenti
Struttura dei file
Funzioni di manipolazione
dei file
Metodi di accesso
Record
Gestione dei blocchi
Blocchi fisici nei buffer in memoria principale
Scheduling del disco
Funzioni del File management
Allocazione dei file
Blocchi fisici in memoria secondaria
Gestione dello spazio libero
Funzioni del Sistema Operativo
Sistemi Operativi Laface 2001 - Bach12.8
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 Laface 2001 - Bach12.9
Allocazione contigua
• Vantaggio: velocità d’accesso
• Svantaggi: frammentazione dello spazio disponibile
Sistemi Operativi Laface 2001 - Bach12.10
Allocazione linkata
10
3210
7654
1198
15141312
19181716
23222120
27262524
31302928
10
16 25
1
-1
File Blocco inizio Blocco di fine
prova 9 25
directory
Sistemi Operativi Laface 2001 - Bach12.11
Allocazione linkata - FAT
test 217 ......
elemento della directory
nome blocco iniziale
618
fine del file
339
FAT
Numero dei blocchi
0
217
339
618
-1
217
Sistemi Operativi Laface 2001 - Bach12.12
Allocazione indicizzata
10
3210
7654
1198
15141312
19181716
23222120
27262524
31302928
19
File Blocco indice prova 19
directory
91611025-1
Sistemi Operativi Laface 2001 - Bach12.13
Organizzazione di un File System di UNIX
Blocco di boot
Super blocco
Lista degli inode
Blocchi di dati
Sistemi Operativi Laface 2001 - Bach12.14
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 Laface 2001 - Bach12.15
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 Laface 2001 - Bach12.16
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 Laface 2001 - Bach12.17
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 Laface 2001 - Bach12.18
Funzioni di gestione del File system
algoritmi di allocazione dei buffer
getblk brelse bread breada bwrite
iget iput bmap
namei alloc free ialloc ifree
Sistemi Operativi Laface 2001 - Bach12.19
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 Laface 2001 - Bach12.20
igetprocedura igetinput: numero di inode nel file systemoutput: 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;}}
procedura igetinput: numero di inode nel file systemoutput: 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 Laface 2001 - Bach12.21
Struttura di un file normale
0
1
2
3
4
5
6
7
8
9
indiretto singolo
indiretto doppio
indiretto triplo
I-node Blocchi di dati
Sistemi Operativi Laface 2001 - Bach12.22
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 = 64 Mbyte
• 1 blocco triplamente indiretto con 256 blocchi
doppiamente indiretti = 16 Gbyte
Sistemi Operativi Laface 2001 - Bach12.23
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 Laface 2001 - Bach12.24
iput
procedura iputinput: puntatore all’inode in memoriaoutput: 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;}
procedura iputinput: puntatore all’inode in memoriaoutput: 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 Laface 2001 - Bach12.25
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 Laface 2001 - Bach12.26
bmapprocedura bmap input: (1) inode (2) offset in byteoutput:(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;}}
procedura bmap input: (1) inode (2) offset in byteoutput:(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 Laface 2001 - Bach12.27
Esempio di Inode
4096
228
45423
0
0
11111
0
101
367
0
428
9156
824
I-node
367 blocco di dati331
9156 indirezione doppia
3333
331 indirezione singola
3333 blocco di dati
Sistemi Operativi Laface 2001 - Bach12.28
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 Laface 2001 - Bach12.29
1.mkdir junk2.for i in 1 2 3 4 53.do 4.echo salve > junk/$i5.done6.ls -ld junk7.ls -l junk8.chmod -r junk9.ls -ld junk10.ls junk11.ls -l junk12.cd junk13.pwd14.ls -l15.echo *16.cd ..17.chmod +r junk18.chmod -x junk19.ls junk20.ls -l junk21.cd junk22.chmod +x junk
1.mkdir junk2.for i in 1 2 3 4 53.do 4.echo salve > junk/$i5.done6.ls -ld junk7.ls -l junk8.chmod -r junk9.ls -ld junk10.ls junk11.ls -l junk12.cd junk13.pwd14.ls -l15.echo *16.cd ..17.chmod +r junk18.chmod -x junk19.ls junk20.ls -l junk21.cd junk22.chmod +x junk
drwxr-xr-x 2 user1 512 Feb 20 16:24 junk-rw-r--r-- 1 user1 6 Feb 20 16:24 1-rw-r--r-- 1 user1 6 Feb 20 16:24 2-rw-r--r-- 1 user1 6 Feb 20 16:24 3-rw-r--r-- 1 user1 6 Feb 20 16:24 4-rw-r--r-- 1 user1 6 Feb 20 16:24 5d-wx--x--x 2 user1 512 Feb 20 16:24 junkjunk unreadablejunk unreadable/home2/user1/prova/junk. unreadable*12345ls: junk/1: Permission deniedls: junk/2: Permission deniedls: junk/3: Permission deniedls: junk/4: Permission deniedls: junk/5: Permission deniedtotal 0command: junk: Permission denied
drwxr-xr-x 2 user1 512 Feb 20 16:24 junk-rw-r--r-- 1 user1 6 Feb 20 16:24 1-rw-r--r-- 1 user1 6 Feb 20 16:24 2-rw-r--r-- 1 user1 6 Feb 20 16:24 3-rw-r--r-- 1 user1 6 Feb 20 16:24 4-rw-r--r-- 1 user1 6 Feb 20 16:24 5d-wx--x--x 2 user1 512 Feb 20 16:24 junkjunk unreadablejunk unreadable/home2/user1/prova/junk. unreadable*12345ls: junk/1: Permission deniedls: junk/2: Permission deniedls: junk/3: Permission deniedls: junk/4: Permission deniedls: junk/5: Permission deniedtotal 0command: junk: Permission denied
Sistemi Operativi Laface 2001 - Bach12.30
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 Laface 2001 - Bach12.31
namei
procedura namei /* converte pathname in inode */input: pathnameoutput: 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);}
procedura namei /* converte pathname in inode */input: pathnameoutput: 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 Laface 2001 - Bach12.32
Scansione del pathname ../a/ba Inode
.. Inode
b Inode
. Inode
b
Current dir
Parent dir
a directory
Current directory
U-area
Inodes
Files
Sistemi Operativi Laface 2001 - Bach12.33
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 Laface 2001 - Bach12.34
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 Laface 2001 - Bach12.35
Allocazione di blocchi di disco
. . . . . . . . . . . . . . . . . .
109
109 106 103 100
211 208 205 202 . . . . . . . . . . . . . .112
Lista del superblocco
211
310 307 304 301 . . . . . . . . . . . . . .214
310
409 406 403 400 . . . . . . . . . . . . . .313
Sistemi Operativi Laface 2001 - Bach12.36
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 Laface 2001 - Bach12.37
Esempio di alloc e free
a, b - Configurazione iniziale e dopo il rilascio del blocco 949
109
109. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Lista del superblocco
109211208205202
. . . . . . . . . . . . . .112
109
109. . . . . . . . . . . . . . . . . . . . . . . . . . .
.
Lista del superblocco
109211208205202
. . . . . . . . . . . . . .112
949
Lista del super blocco Lista del superblocco
109
109. . . . . . . . . . . . . . . . . . . . . . . . . . . .
109211208205202
. . . . . . . . . . . . . .112
211
211208205202. . . . . . . . . . . . . .
112
109
344341338335. . . . . . . . . . . . . .
243
c, d - Assegnazione del blocco 949 ed assegnazione del blocco 109 con riempimento della free list del super blocco