Struttura del file system
 Struttura del file
Sistemi Operativi
Giuseppe Prencipe
Unità di memorizzazione logica
Raccolta di informazioni correlate
 Il file system risiede permanentemente nella memoria
secondaria
Realizzazione del file system
 I dischi sono convenienti per memorizzare i file
Un blocco può essere letto, modificato e riscrtitto nella stessa
posizione
È possibile l’accesso diretto a qualsiasi bloccoun file si può
accedere in modo sequenziale o diretto
1
Struttura del file system
2
File system stratificato
 Per aumentare l’efficienza, i dati da e verso i dischi si
trasferiscono a blocchi (e non a byte)
Ogni livello utilizza le funzionalità
dei livelli inferiori per crearne delle altre
Ogni blocco è costituito da uno o più settori
 Di soliro un settore è 512 byte (varia tra 32 e 4096)
 Per fornire un conveniente accesso al disco, il SO utilizza uno
o più file system
 Due problemi nella progettazione di un FS
Definizione dell’aspetto del FS agli occhi dell’utente (aspetto logico)
 Attributi file, operazioni ammesse sui file, struttura a directory
Progettazione di algoritmi e strutture dati che facciano
corrispondere il FS logico ai dispositivi fisici di memoria secondaria
 Il file system ha tipicamente una struttura stratificata
3
File system stratificato
4
File system stratificato
Controllo I/O: cosituito dai
driver dei dispositivi e dei gestori
dei segnali d’interruzione
Controllo I/O: cosituito dai
driver dei dispositivi e dei gestori
dei segnali d’interruzione
Si occupa del trasferimento di
info tra memoria centrale e secondaria
Si occupa del trasferimento di
info tra memoria centrale e secondaria
Riceve comandi ad alto livello
(recupera blocco X), e genera istruzioni
(di basso livello) specifiche per i dispositivi,
usate dal controllore che funge da interfaccia
tra i dispositivi e il sistema
5
1
6
File system stratificato
File system stratificato
Un driver di dispositivo scrive
specifiche configurazioni di bit
in specifiche locazioni della memoria
del controllore di I/O per indicare le
azioni che il dispositivo deve compiere
e in quali locazioni
Il file system di base invia
comandi all’appropriato
driver di dispositivo per leggere/scrivere
blocchi fisici nel disco
Ogni blocco fisico si identifica con
un indirizzo: #unità, #cilindro, #superficie,
#settore
7
8
File system stratificato
File system stratificato
Il modulo di organizzazione dei file
è a conoscenza dei blocchi logici dei file
e dei blocchi fisici nel disco
Il modulo di organizzazione dei file
è a conoscenza dei blocchi logici dei file
e dei blocchi fisici nel disco
Conscendo la locazione dei file, può
tradurre gli indirizzi dei blocchi logici
(che il file system di base deve trasferire) in
indirizzi dei blocchi fisici
Conscendo la locazione dei file, può
tradurre gli indirizzi dei blocchi logici (che
il file system di base deve trasferire) in
indirizzi dei blocchi fisici
I blocchi logici di un file sono numerati da
1 (o 0) a n. I blocchi fisici non hanno la stessa
numerazionenecessaria traduzione
9
File system stratificato
Struttura del file system
Il file system logico gestisce tutte le
strutture del file system
 Esistono molti tipi di file system
Gestisce la struttura a directory
Mantiene le strutture dei file tramite
i descrittori di file (FD) (detti anche
blocco di controllo dei file
(FCB, file control block)):
struttura di memorizzazione che contiene
informazioni sui file,
come la proprietà, i permessi e la posizione del contenuto
11
2
10
Ad es., la maggior parte dei CD-ROM è scritta nel
formato High Sierra (definito tramite accordo tra
produttori)
Unix usa lo Unix File System per il suo file system
di base
Windows 2000 gestisce file system per FAT, FAT32
e NTFS (Windows NT file system), CD-ROM, DVD e
floppy
 L’uso della stratificazione nella realizzazione di un file
system permette il riutilizzo del codice
Il codice di controllo dell’I/O e talvolta del file
system di base si può usare per più file system
12
Realizzazione del file system
Strutture su disco
 Per essere realizzato, il file system richiede diverse strutture
 Blocco di controllo dell’avviamento
dati
 Alcune di esse sono usate sui dischi altre in memoria
secondaria
 Variano a seconda dei sistemi operativi, ma i princìpi
generali sono gli stessi
 Vediamone alcune....
(boot control block) contiene le informazioni necessarie al sistema
per l’avvio da una data partizione. Di solito è il primo blocco della
partizione
Tipicamente, per sicurezza, viene copiato in vari punti prestabiliti
del disco. In questo modo se il blocco originale si corrompe, è
possibile far partire il sistema leggendo da una delle copie
13
Strutture su disco
14
Strutture su disco
 Blocco di controllo dell’avviamento
(boot control block) contiene le informazioni necessarie al sistema
per l’avvio da una data partizione. Di solito è il primo blocco della
partizione
Tipicamente, per sicurezza, viene copiato in vari punti prestabiliti
del disco. In questo modo se il blocco originale si corrompe, è
possibile far partire il sistema leggendo da una delle copie
 Blocchi di controllo delle partizioni
 Strutture di directory
 Descrittori di file
Contengono i dettagli sui file
 Permessi d’accesso
 Proprietari
 Dimensioni
 Locazioni dei blocchi di dati
(partition control block) contengono i dettagli riguardanti la
relativa partizione
In UNIX si chiamano inode
In NTFS queste info sono memorizzate all’interno della tabella
principale dei file, realizzata come database relazionale, con una
riga per file
 Numero e dimensione dei blocchi nel disco
 Contatore blocchi liberi e relativi puntatori
 Contatore descrittore di file liberi e relativi puntatori
15
Tipico descrittore di file
16
Strutture in memoria
 Servono sia per la gestione del file system sia per migliorare
le prestazioni attraverso l’uso di cache
permessi per il file
data e ora di creazione, di ultimo accesso e di ultima scrittura
proprietario del file, gruppo
dimensione del file
blocchi di dati del file
17
3
18
Strutture in memoria
Strutture in memoria
 Servono sia per la gestione del file system sia per migliorare
 Servono sia per la gestione del file system sia per migliorare
le prestazioni attraverso l’uso di cache
 Tabella delle partizioni
le prestazioni attraverso l’uso di cache
 Tabella delle partizioni
(partition table) contiene le info su ciascuna delle partizioni
montate
(partition table) contiene le info su ciascuna delle partizioni
montate
 Struttura directory
19
20
Strutture in memoria
Gestione file
 Servono sia per la gestione del file system sia per migliorare
 Creazione file
le prestazioni attraverso l’uso di cache
 Tabella delle partizioni
Si fa una chiamata al FS logico che assegna un nuovo descrittore
di file
Carica nella memoria la directory appropriata,
L’aggiorna con il nuovo nome di file e il relativo descrittore,
E la riscrive su disco
(partition table) contiene le info su ciascuna delle partizioni
montate
 Struttura directory
 Tabella generale dei file aperti
Contiene una copia del descrittore di file per ciascun file aperto
 Tabella dei file aperti per ciascun processo
Contiene un puntatore al relativo elemento della tabella generale
dei file aperti
21
22
Gestione file
Gestione file
 Creazione file
 Aprire un file
Si fa una chiamata al FS logico che assegna un nuovo descrittore
di file
Carica nella memoria la directory appropriata,
L’aggiorna con il nuovo nome di file e il relativo descrittore,
E la riscrive su disco
La open passa un nome di file al file system
Questo nome viene cercato nella struttura delle directory
 alcune porzioni della struttura sono tenute in memoria per ottimizzare le
operazioni
 Alcuni SO trattano le directory come file (UNIX)
Viene aggiunto un campo che distingue file e directory
 Altri dispongono di chiamate di sistema differenti per file e
directory (Windows NT)
23
4
24
Gestione file
Gestione file
 Aprire un file
 Aprire un file
La open passa un nome di file al file system
Questo nome viene cercato nella struttura delle directory
La open passa un nome di file al file system
Questo nome viene cercato nella struttura delle directory
 alcune porzioni della struttura sono tenute in memoria per ottimizzare le
operazioni
 alcune porzioni della struttura sono tenute in memoria per ottimizzare le
operazioni
Una volta che il file è stato trovato, si copia il suo descrittore nella
tabella generale dei file aperti (in memoria)
Una volta che il file è stato trovato, si copia il suo descrittore nella
tabella generale dei file aperti (in memoria)
 Ricordo che questa tabella memorizza anche il numero di processi che
hanno correntemente aperto quel file
 Ricordo che questa tabella memorizza anche il numero di processi che
hanno correntemente aperto quel file
Si crea un elemento nella tabella dei file aperti del processo che
ha eseguito la open, con un puntatore al relativo elemento nella
tabella di sistema
 Ci sono anche altri campi: puntatore alla posizione corrente nel file, tipo di
accesso richiesto al momento della open
25
26
Gestione file
Gestione file
 Aprire un file
 Aprire un file
La open riporta un puntatore all’elemento appropriato nella tabella
dei file aperti del processo
La open riporta un puntatore all’elemento appropriato nella tabella
dei file aperti del processo
Tutte le operazioni sul file si svolgeranno usando questo puntatore
 Il nome del file potrebbe non essere memorizzato nella tabella (visto che il
sistema lo usa solo per individuare il file su disco)
L’elemento nella tabella viene chiamato descritttore di file (file
descriptor—UNIX) o maniglia di file (file handle—Windows 2000)
27
Gestione file
Gestione file
 Aprire un file
 Aprire un file
La open riporta un puntatore all’elemento appropriato nella tabella
dei file aperti del processo
Tutte le operazioni sul file si svolgeranno usando questo puntatore
 Il nome del file potrebbe non essere memorizzato nella tabella (visto che il
sistema lo usa solo per individuare il file su disco)
L’elemento nella tabella viene chiamato descritttore di file (file
descriptor—UNIX) o maniglia di file (file handle—Windows 2000)
 NOTA: nella descrizione appena data, la open non è
La open riporta un puntatore all’elemento appropriato nella tabella
dei file aperti del processo
Tutte le operazioni sul file si svolgeranno usando questo puntatore
 Il nome del file potrebbe non essere memorizzato nella tabella (visto che il
sistema lo usa solo per individuare il file su disco)
L’elemento nella tabella viene chiamato descritttore di file (file
descriptor—UNIX) o maniglia di file (file handle—Windows 2000)
 NOTA: nella descrizione appena data, la open non è
“ottimizzata”....????
“ottimizzata”....????
SCHEMA VISTO: (opencreo elemento in tabella generalecreo
elemento in tabella processo)
29
5
28
Al momento della open prima si controlla che il file non sia già
aperto (dalla tabella generale)
In questo caso, si aggiunge solo l’elemento nella tabella del
processo
30
Riepilogo grafico
Gestione file
 Chiudere un file
Si cancella l’elemento nella tabella dei file aperti del processo
Si decrementa il contatore associato al file nella tabella generale
Se tutti i processo che avevano aperto il file lo hanno ora chiuso
 Si elimina il relativo elemento dalla tabella generale
struttura di directory
 Si riscrive l’info aggiornata sul file nella struttura delle directory nei dischi
apertura
(nome del file)
struttura di directory
descrittore di file
spazio d’utente
memoria del nucleo
memoria secondaria
(a): Apertura
31
Riepilogo grafico
32
Partizioni e montaggio
 Un disco si può suddividere in più partizioni, o una
partizione può comprendere più dischi
indice
 Una partizione può essere priva di file system (raw partition)
Es.: swap area in UNIX. Viene usato un formato specifico
blocchi dei dati
lettura
(tramite l’indice)
spazio d’utente
tabella dei file
aperti del processo
tabella generale
dei file aperti
memoria del nucleo
descrittore di file
memoria secondaria
(b): Lettura
33
34
Partizioni e montaggio
Partizioni e montaggio
 Un disco si può suddividere in più partizioni, o una
 Nella fase di caricamento, si esegue il montaggio della
partizione può comprendere più dischi
 Una partizione può essere priva di file system (raw partition)
Es.: swap area in UNIX. Viene usato un formato specifico
 Le informazioni per avviare il sistema si possono registrare
in un’apposita partizione
Sono memorizzate in un formato proprio, dato che all’inizio non
sono caricati i driver di dispositivo del FS
Sono memorizzate sequenzialmente, e vengono caricate in
memoria come un’immagine
L’immagine d’avviamento può contenere più info di quelle che
servono per avviare un solo SO
partizione radice, che contiene il nucleo del SO e altri file di
sistema
 Il montaggio delle altre partizioni può avvenire
automaticamente in questa fase, o può essere fatto
esplicitamente in seguito
 Gestione di più SO (uno per partizione)
35
6
36
Partizioni e montaggio
File system virtuali
 Nella fase di caricamento, si esegue il montaggio della
 I SO moderni devono prevedere la possibilità di integrare
partizione radice, che contiene il nucleo del SO e altri file di
sistema
 Il montaggio delle altre partizioni può avvenire
automaticamente in questa fase, o può essere fatto
esplicitamente in seguito
 Durante il montaggio, si verifica che il dispositivo contenga
un FS valido
diversi tipi di FS in un’unica struttura a directory
Se così non fosse, si verifica lo coerenza della partizione e si
procede a eventuali correzioni
37
38
File system virtuali
File system virtuali
 I SO moderni devono prevedere la possibilità di integrare
 I SO moderni devono prevedere la possibilità di integrare
diversi tipi di FS in un’unica struttura a directory
 Un modo per ottenere questo è di scrivere procedure di
gestione di file e directory diverse per ciascun tipo di file
system....
diversi tipi di FS in un’unica struttura a directory
 Un modo per ottenere questo è di scrivere procedure di
gestione di file e directory diverse per ciascun tipo di file
system....
 ....ovviamente inefficiente!!!!
 Un altro metodo consiste nel separare le funzioni di base
delle chiamate di sistema dai dettagli di realizzazione
39
File system virtuali
File system virtuali
 Per ottenere questo, si realizza il FS in vari strati
 Il file system virtuale svolge due funzioni importanti
Il primo è l’interfaccia del file system, basata sulle
chiamate open, read, write e close
Il secondo strato è il file system virtuale (VFS,
virtual file system)
Separare le operazioni generiche del file system
dalla loro realizzazione definendo un’interfaccia
uniforme
Il VFS è basato su una struttura di
rappresentazione dei file detta vnode che contiene
un indicatore numerico unico per tutta la rete per
ciascun file
La struttura di vnode è utilizzata sia per i file che
per le directory
41
7
40
42
Schema di un file system virtuale
Realizzazione delle directory
 Lista lineare contenente i nomi dei file con puntatori ai
blocchi di dati
metodo di facile programmazione
esecuzione onerosa in termini di tempo
 Per creare un file bisogna....????
43
44
Realizzazione delle directory
Realizzazione delle directory
 Lista lineare contenente i nomi dei file con puntatori ai
 Lista lineare contenente i nomi dei file con puntatori ai
blocchi di dati
blocchi di dati
metodo di facile programmazione
esecuzione onerosa in termini di tempo
metodo di facile programmazione
esecuzione onerosa in termini di tempo
 Per creare un file bisogna....????
 Per creare un file bisogna....????
Scandire la lista per controllare che non ci sia già un file con lo
stesso nome
Aggiungere un elemento alla fine della lista
Scandire la lista per controllare che non ci sia già un file con lo
stesso nome
Aggiungere un elemento alla fine della lista
 Per cancellare un file bisogna....????
 Per cancellare un file bisogna....????
Cercare il file (scansione lineare)
Rilasciare lo spazio assegnato
45
46
Realizzazione delle directory
Realizzazione delle directory
 Si può riutilizzare un elemento della directory
 Si può riutilizzare un elemento della directory
Marcandolo come libero quando il file che occupa quell’elemento
viene cancellato
Aggiungendolo a una lista di elementi di directory liberi
Copiando l’ultimo elemento della directory in un elemento appena
liberato (in seguito a cancellazione)perchè vorrei fare così....????
Marcandolo come libero quando il file che occupa quell’elemento
viene cancellato
Aggiungendolo a una lista di elementi di directory liberi
Copiando l’ultimo elemento della directory in un elemento appena
liberato (in seguito a cancellazione)perchè vorrei fare così....????
 Per diminuire la lunghezza della directory
47
8
48
Realizzazione delle directory
Realizzazione delle directory
 Si può riutilizzare un elemento della directory
 Tabella hash: lista lineare con struttura di dati hash
Marcandolo come libero quando il file che occupa quell’elemento
viene cancellato
Aggiungendolo a una lista di elementy di directory liberi
Copiando l’ultimo elemento della directory in un elemento appena
liberato (in seguito a cancellazione)perchè vorrei fare così....????
 Per diminuire la lunghezza della directory
La chiave di ricerca è data dal nome del file da cercare
Diminuisce notevolmente il tempo di ricerca nella directory
Collisioni: situazioni in cui da due nomi di file si ottiene un
riferimento alla stessa locazione
 Es.: lista concatenata per ogni elemento (rallenta le ricerche)
Le maggiori difficoltà nascono dal fatto che la tabella ha
dimensione fissa
 Il vero svantaggio è dato dalla ricerca lineare
Lenta
 Inoltre i file non sono ordinati (non è possibile una ricerca
binaria)
49
Metodi di assegnazione
50
Assegnazione contigua
 Un metodo di assegnazione indica il modo in cui i blocchi di
disco vengono assegnati ai file
 Ciascun file deve occupare un insieme di blocchi contigui nel
disco
 Semplice: è richiesto solo l’indirizzo del primo blocco (inteso
come numero di blocco) e la lunghezza (espressa in blocchi)
Assegnazione contigua
 Si possono realizzare sia l’accesso sequenziale che quello
diretto a file....????
Assegnazione concatenata
Assegnazione indicizzata
51
Assegnazione contigua
52
Assegnazione contigua
 Ciascun file deve occupare un insieme di blocchi contigui nel
 Ciascun file deve occupare un insieme di blocchi contigui nel
disco
 Semplice: è richiesto solo l’indirizzo del primo blocco (inteso
come numero di blocco) e la lunghezza (espressa in blocchi)
 Si possono realizzare sia l’accesso sequenziale che quello
diretto a file....????
 Problemi....????
disco
 Semplice: è richiesto solo l’indirizzo del primo blocco (inteso
come numero di blocco) e la lunghezza (espressa in blocchi)
 Si possono realizzare sia l’accesso sequenziale che quello
diretto a file....????
 Problemi....????
Individuazione dello spazio per un nuovo file. Si può considerare
come un’istanza del problema dell’assegnazione dinamica della
memoria (già visto....)
 First-fit, best-fit, worst-fit
 Problemi di frammentazione....di che tipo????
53
9
54
Assegnazione contigua dello spazio dei dischi
Assegnazione contigua
 Ciascun file deve occupare un insieme di blocchi contigui nel
disco
 Semplice: è richiesto solo l’indirizzo del primo blocco (inteso
come numero di blocco) e la lunghezza (espressa in blocchi)
 Si possono realizzare sia l’accesso sequenziale che quello
diretto a file....????
 Problemi....????
Individuazione dello spazio per un nuovo file. Si può considerare
come un’istanza del problema dell’assegnazione dinamica della
memoria (già visto....)
 First-fit, best-fit, worst-fit
 Problemi di frammentazione....di che tipo????

Esterna!!!!
55
56
Assegnazione contigua
Assegnazione contigua
 Un altro problema è quello della determinazione della
 Un altro problema è quello della determinazione della
quantità di spazio necessaria per un file
quantità di spazio necessaria per un file
Se un file viene copiatosi conosce già la sua dimensioneOK
Se un file viene copiatosi conosce già la sua dimensioneOK
Altrimenti (nuovo file), non si sa a priori quanto crescerà il file
 È possibile che a un certo punto non si possa più gestire il file perchè è
cresciuto troppo, e non ci sono blocchi disponibili adiacenti a quelli occupati
57
58
Assegnazione contigua
Assegnazione contigua
 Un altro problema è quello della determinazione della
 Un altro problema è quello della determinazione della
quantità di spazio necessaria per un file
quantità di spazio necessaria per un file
Se un file viene copiatosi conosce già la sua dimensioneOK
Altrimenti (nuovo file), non si sa a priori quanto crescerà il file
Se un file viene copiatosi conosce già la sua dimensioneOK
Altrimenti (nuovo file), non si sa a priori quanto crescerà il file
 È possibile che a un certo punto non si possa più gestire il file perchè è
cresciuto troppo, e non ci sono blocchi disponibili adiacenti a quelli occupati
 È possibile che a un certo punto non si possa più gestire il file perchè è
cresciuto troppo, e non ci sono blocchi disponibili adiacenti a quelli occupati
 Due possibilità
 Due possibilità

Il programma utente viene terminato, l’utente alloca più spazio e poi il programma
viene rieseguito


Il programma utente viene terminato, l’utente alloca più spazio e poi il programma
viene rieseguito
Si cerca un buco più grande, e si sposta il file (l’utente non si accorge di nulla....è
solo più lento)
Se in anticipo alloco molto più spazio, e il file cresce lentamente
frammentazione esterna!!!!
59
10
60
Sistemi con estensione
Assegnazione concatenata
 Molti sistemi più recenti (ad es. il file system Veritas) usano
 Ciascun file è composto da una lista concatenata di blocchi
uno schema di assegnazione contigua modificato
del disco i quali possono essere sparsi in qualsiasi punto del
disco stesso
 I file system con estensione aggiungono, alla porzione di
spazio contiguo assegnata, un’altra porzione di spazio
(estensione)
blocco =
puntatore
 Un’estensione è un blocco contiguo di dischi. La locazione
dei blocchi dei file si registra come una locazione e un
numero dei blocchi, insieme con l’indirizzo del primo blocco
dell’estensione seguente
 La directory contiene il puntatore al primo blocco
61
62
Assegnazione concatenata
Assegnazione concatenata
 Semplice: necessita solo dell’indirizzo di partenza
 Sistema di gestione dello spazio libero: non c’è spreco di
spazio
 Per leggere, si cerca il blocco seguendo la lista
 Per scrivere, si cerca un blocco libero (sistema di gestione
blocchi liberi), e si concatena questo blocco al termine della
lista
63
64
FAT
Assegnazione concatenata
 Una variante importante del metodo di assegnazione
 Non esiste frammentazione esterna
 Svantaggio: per trovare l’i -esimo blocco, bisogna scandire la
lista
Questo comporta lo spostamento della testina in posti differenti del
disco (al contrario dell’assegnazione contigua)la gestione dei file a
accesso diretto risulta inefficiente
concatenata consiste nell’uso della tabella di assegnazione dei
file (FAT, file allocation table). Tale metodo di assegnazione,
semplice ma efficiente, dello spazio dei dischi è usato nei
sistemi operativi MS-DOS e OS/2
 La FAT ha un elemento per ogni blocco del disco ed è
indicizzata dal numero di blocco. La si usa come lista
concatenata
 Svantaggio: spazio richiesto dai puntatori
Soluzione: assegnare gruppi di blocchi
 Svantaggio: affidabilità
Caos se uno dei puntatori si rovina....
Soluzione parziale: usare liste doppiamente concatenatepiù spazio
puntatori!!!!
65
11
66
FAT
Tabella di assegnazione dei file (FAT)
 Una variante importante del metodo di assegnazione




elemento della directory
concatenata consiste nell’uso della tabella di assegnazione dei
file (FAT, file allocation table). Tale metodo di assegnazione,
semplice ma efficiente, dello spazio dei dischi è usato nei
sistemi operativi MS-DOS e OS/2
La FAT ha un elemento per ogni blocco del disco ed è
indicizzata dal numero di blocco. La si usa come lista
concatenata
La directory contiene il numero del primo blocco del file
L’elemento della FAT indicizzato dal quel numero di blocco
contiene il numero di blocco successivo, e così via
La FAT viene memorizzata in una sezione riservata all’inizio di
ogni partizione
test
217
nome
blocco iniziale
0
217
618
339
fine-file
618
339
numero dei blocchi del disco –1
FAT
67
FAT
68
FAT
 Per leggere un blocco, cosa si fa....????
 Per localizzare un blocco, cosa si fa....????
La testina si sposta sulla FAT, individua la locazione del blocco, e poi
si sposta sul blocco da leggeredue spostamenti di testina nel caso
peggiore
Migliora la gestione dell’accesso diretto a file (dato che la locazione
del blocco si trova leggendo la FAT)
69
70
Esempio di assegnazione indicizzata
Assegnazione indicizzata
 Raggruppa tutti i puntatori in una sola locazione: il blocco
indice
tabella indice
71
12
72
Assegnazione indicizzata
Assegnazione indicizzata
 Necessita di tabella indice
 Accesso dinamico senza frammentazione esterna
 Lo spazio aggiuntivo richiesto è maggiore di quello richiesto
 Ogni file deve avere un blocco indice, quindi è auspicabile che
dallo schema concatenato
Es.: file con due blocchi
 Questo solleva il problema della dimensione del blocco indice
questo sia quanto più piccolo possibile; ma se il blocco indice
è troppo piccolo, non può contenere un numero di puntatori
sufficiente per un file di grandi dimensioni, quindi è necessario
disporre di un meccanismo per la gestione di questa
situazione:
Schema concatenato
Indice a più livelli
Schema combinato.
73
74
Assegnazione indicizzata
Assegnazione indicizzata
 Schema concatenato
 Schema concatenato
Si collegano tra loro più blocchi indice (se necessari per gestire file
grandi)
Si collegano tra loro più blocchi indice (se necessari per gestire file
grandi)
 Indice a più livelli
Si impiega un blocco indice di primo livello che punta a un insieme
di blocchi indice di secondo livello che, a loro volta, puntano ai
blocchi del file
Per accedere a un blocco
 Il sistema accede al primo livello, individua il corretto blocco indice di
secondo livello, e con esso trova il blocco dati richiesto
 Questo schema si può estendere fino a 3 o 4 livelli
75
76
Schema combinato: UNIX
 Ogni inode contiene 15
puntatori
•12 puntano direttamente
a blocchi dati
•Gli altri 3 puntano a
blocchi indiretti
•Con puntatori di 32 bit, si
arriva a gestire file di 4GB
•Con puntatori di 64 bit, si
arriva all’ordine dei terabyte
77
13
Prestazioni
 Leggete il Par. 12.4.4 che tratta l’argomento delle differenze
di prestazioni fra i vari metodi visti....
78
Gestione dello spazio libero
Gestione dello spazio libero
 Dato che lo spazio su disco è limitato, è necessario
 Vettore di bit
riutilizzare i blocchi rilasciati in seguito a cancellazione di file
 Per tenere traccia dello spazio libero in un disco, il SO
conserva un elenco dei blocchi liberi
 Lista concatenata
Vi sono registrati i blocchi non utilizzati (da file o directory)
 Raggruppamento
 Per creare un file, si cerca nell’elenco dei blocchi liberi la
quantità di spazio necessaria, la si assegna al file, e la si
rimuove dall’elenco
 Quando si cancella un file, si aggiungono i suoi blocchi
all’elenco
 Conteggio
79
80
Gestione dello spazio libero
Gestione dello spazio libero
 L’elenco si realizza tramite vettore di bit (ogni blocco è
 L’elenco si realizza tramite vettore di bit (ogni blocco è
rappresentato da un bit)
0 1
2
rappresentato da un bit)
n-1
0 1
2
bit[i] =
n-1
…
1 ⇒ blocco[i] libero
678
678
…
bit[i] =
0 ⇒ blocco[i] assegnato
1 ⇒ blocco[i] libero
0 ⇒ blocco[i] assegnato
 Per cercare un blocco libero, si controlla il vettore a “parole”: se una
parola è 0blocchi occupati; se una parola non è 0si controlla ogni
bit in quella parola per trovare il blocco libero
Si procede così perchè tipicamente si ha una istruzione assembler
che controlla se una parola è zero
 Il numero del blocco libero è dato dalla seguente espressione....????
81
:
82
Gestione dello spazio libero
 L’elenco si realizza tramite vettore di bit (ogni blocco è
Gestione dello spazio libero
rappresentato da un bit)
0 1
2
n-1
 I vantaggi principali di questo metodo sono la sua relativa
678
…
bit[i] =
semplicità ed efficienza nel trovare il primo blocco libero o n
blocchi liberi consecutivi nel disco
1 ⇒ blocco[i] libero
0 ⇒ blocco[i] assegnato
 Le caratteristiche dell’architettura guidano le funzioni del
 Per cercare un blocco libero, si controlla il vettore a “parole”: se una
parola è 0blocchi occupati; se una parola non è 0si controlla ogni
bit in quella parola per trovare il blocco libero
Si procede così perchè tipicamente si ha una istruzione assembler
che controlla se una parola è zero
 Il numero del blocco libero è dato dalla seguente espressione....????
(numero di bit per parola) x (numero di parole di valore 0) +scostamento del primo bit 1
83
:
14
sistema operativo. Sfortunatamente, i vettori di bit sono
efficienti solo se tutto il vettore è mantenuto nella memoria
centrale, e viene di tanto in tanto scritto nella memoria
secondaria allo scopo di consentire eventuali operazioni di
ripristino; è possibile tenere il vettore nella memoria
centrale se i dischi sono piccoli, come quelli usati nei
microcalcolatori; tale soluzione non è applicabile ai dischi
più grandi.
84
Lista concatenata dei blocchi liberi
Lista concatenata dei blocchi liberi
 Non efficiente:
 I blocchi liberi vengono
 I blocchi liberi vengono
collegati a lista
 Un puntatore alla testa
della lista è conservato
in una speciale locazione
del disco e caricato in
memoria
collegati a lista
 Un puntatore alla testa
della lista è conservato
in una speciale locazione
del disco e caricato in
memoria
bisogna scandire
la lista
Fortunatament
e non è
un’operazione
frequente
Inoltre il SO
ha solitamente
bisogno di un
solo blocco
libero da
assegnare a un
file
85
86
Altri metodi
Efficienza
 Raggruppamento
 L’efficienza dipende da:
Si memorizzano gli indirizzi di n blocchi liberi nel primo di questi
Algoritmi usati per l’assegnazione del disco
Gestione delle directory
Dimensioni dei puntatori (32 o 64 bit)influenza la dimensione
dei file
 Conteggio
Nell’elenco si tiene l’indirizzo del primo blocco libero e il numero di
n blocchi liberi contigui che seguono il primo blocco
87
88
Prestazioni
 Le prestazioni possono essere migliorate in vari modi
Prestazioni
Cache del disco: sezione separata della memoria
centrale dove tenere i blocchi in previsione di un loro
utilizzo entro breve tempo
Cache delle pagine: soluzione che impiega tecniche di
memoria virtuale per la gestione dei dati dei file come
pagine anziché come blocchi di file system
 Le prestazioni possono essere migliorate in vari modi
Alcuni controllori di disco contengono una memoria locale per la
creazione di una cache sufficientemente grande da contenere
un’intera traccia del disco
Il controllore trasferisce quindi al SO tutte le richieste di settori
Quando i blocchi sono trasferiti in memoria centrale, il sistema
può memorizzarli in una propria cache
 Cache del disco: sezione separata della memoria centrale dove tenere i
blocchi in previsione di un loro utilizzo entro breve tempo
89
15
90
Prestazioni
 Le prestazioni possono essere migliorate in vari modi
Diverse locazioni di cache per i dischi
Cache del disco: sezione separata della memoria
centrale dove tenere i blocchi in previsione di un loro
utilizzo entro breve tempo
Cache delle pagine: soluzione che impiega tecniche di
memoria virtuale per la gestione dei dati dei file come
pagine anziché come blocchi di file system
Alcuni sistemi prevedono la buffer cache unificata
Si considerino le due possibilità per aprire un file e
accedervi:
 Associazione alla memoria (si trattano i blocchi del
file come pagine in memoria, e si usano le tecniche
della memoria virtuale)
 Ordinarie chiamate di sistema read e write
91
92
I/O senza una buffer cache unificata
Buffer cache unificata
 Con una buffer cache unificata, sia l’associazione alla
memoria sia le chiamate del sistema read e write usano la
stessa cache delle pagine.
Double caching
93
94
Prestazioni
I/O con una buffer cache unificata
 Interazioni tra cache delle pagine, file system e driver dei
dischi
Quando si scrivono dati in un file su disco, le pagine si scrivono le
pagine nella cache
Il driver del disco le ordina secondo gli indirizzi del disco
Questo permette di ridurre il tempo di ricerca per la testina, e di
scrivere i dati secondo una sequenza che sfrutti la rotazione del disco
95
16
96
Prestazioni
 Interazioni tra cache delle pagine, file system e driver dei
Prestazioni
dischi
Quando si scrivono dati in un file su disco, le pagine si scrivono le
pagine nella cache
Il driver del disco le ordina secondo gli indirizzi del disco
Questo permette di ridurre il tempo di ricerca per la testina, e di
scrivere i dati secondo una sequenza che sfrutti la rotazione del disco
 Scritture sincrone
 Alcuni sistemi ottimizzano la cache delle pagine adottando
specifici algoritmi di sostituzione, secondo il tipo d’accesso
 Le pagine di un file acceduto in modo sequenziale non si
sostituiscono con LRU
Rilascio indietro (free-behind)
 Rimuove una pagina dalal memoria di transito non appena si verifica una
richiesta della pagina successiva
I dati non vanno in cache e la procedura chiamante attende che i
dati raggiungano il disco (no ottimizzazioni dette al punto
precedente)
Lettura anticipata (read-ahead)
 Si leggono e si mettono in cache la pagina richiesta e un certo numero di
pagine successive
 Scritture asincrone
Si memorizzano i dati in cache, e si restituisce immediatamente il
controllo alla procedura chiamante
97
98
Prestazioni
Ripristino
 Per migliorare le prestazioni nei PC si riserva e si gestisce
 Il sistema deve garantire che un malfunzionamento non
una sezione della memoria come un disco virtuale o
disco RAM
comporti la perdita di dati o la loro incoerenza (tra memoria
e disco)
 Una parte delle info delle directory sono tenute in memoria
centrale per velocizzare gli accessi
Il driver di questo disco accetta tutte le operazioni ordinarie dei
dischi, ma le esegue in questa sezione della memoria invece che
su disco
Operazioni più veloci, ma la memoria è temporanea
Tipicamente, la versione in memoria centrale è più aggiornata
 Se il sistema crolla
Tabella dei file aperti viene persa, e con essa qualsiasi modifica
alle directory alle quali i file aperti appartengono
Questo può lasciare il sistema in uno stato di incoerenza
99
100
Ripristino
Ripristino
 Il verificatore della coerenza confronta i dati delle
 Il verificatore della coerenza confronta i dati delle
directory con quelli contenuti nei blocchi dei dischi,
tentando di correggere ogni incoerenza
directory con quelli contenuti nei blocchi dei dischi,
tentando di correggere ogni incoerenza
Tipicamente durante il riavvio del sistema
Tipicamente durante il riavvio del sistema
 Si possono anche utilizzare i programmi di sistema che
consentono di fare delle copie di riserva (backup) dei dati
residenti nei dischi su altri dispositivi di registrazione dati
(dischetti, nastri magnetici o dischi ottici)
 Il ripristino della situazione antecedente la perdita di un
singolo file o di un intero disco richiederà il recupero
(restore) dei dati dalle copie di riserva
101
17
102
File system con annotazione delle modifiche
Ripristino
 I file system annotati (journaling) tengono traccia di
 Per velocizzare le operazioni di backup, si procede a
copiatura incrementale (solo le modifiche) e periodicamente
si effettua la copiatura completa dei file
ogni aggiornamento (sono detti anche file system
orientati alle transazioni e basati sull’annotazione
delle modifiche, log-based transaction-oriented file
system)
103
File system con annotazione delle modifiche
104
File system con annotazione delle modifiche
 I file system annotati (journaling) tengono traccia di
ogni aggiornamento (sono detti anche file system
orientati alle transazioni e basati sull’annotazione
delle modifiche, log-based transaction-oriented file
system)
 Ogni insieme di operazioni che esegue uno specifico
compito si chiama transazione. Una volta che le
modifiche sono riportate nel file di registrazione
(giornale), le operazioni si considerano portate a termine
con successo (committed) e la chiamata del sistema può
restituire il controllo al processo utente, permettendogli
di proseguire la sua esecuzione
 I file system annotati (journaling) tengono traccia di
ogni aggiornamento (sono detti anche file system
orientati alle transazioni e basati sull’annotazione
delle modifiche, log-based transaction-oriented file
system)
 Ogni insieme di operazioni che esegue uno specifico
compito si chiama transazione. Una volta che le
modifiche sono riportate nel file di registrazione
(giornale), le operazioni si considerano portate a termine
con successo (committed) e la chiamata del sistema può
restituire il controllo al processo utente, permettendogli
di proseguire la sua esecuzione
 Nel frattempo si applicano le modifiche alle effettive
strutture del file system
 Quando un’intera transazione è stata completata, se ne
rimuovono le annotazioni dal giornale delle modifiche
105
File system con annotazione delle modifiche
File system con annotazione delle modifiche
 Se si verifica un crollo del sistema, tutte le transazioni nel
 Se si verifica un crollo del sistema, tutte le transazioni nel
giornale delle modifiche devono ancora essere eseguite
 Nel caso in cui una transazione sia fallita (aborted), cioè
non portata a termine prima del crollo, si devono
annullare tutti i cambiamenti applicati al file system da
quella transazione, mantenendo la coerenza del file
system
giornale delle modifiche devono ancora essere eseguite
 Nel caso in cui una transazione sia fallita (aborted), cioè
non portata a termine prima del crollo, si devono
annullare tutti i cambiamenti applicati al file system da
quella transazione, mantenendo la coerenza del file
system
 Il giornale delle modifiche si potrebbe mantenere in una
sezione separata del file system, o anche in un disco
separato.
 Un vantaggio nell’uso del giornale sta nel fatto che gli
aggiornamenti sono più rapidi di quelli che si applicano
direttamente alle strutture su disco
I cambiamenti si applicano in modo asincrono nei dischi
107
18
106
108
NFS
NFS
 NFS è sia una definizione che una realizzazione di un
 Nel contesto dell’NFS si considera un insieme di stazioni di
sistema per l’accesso a file remoti attraverso LAN (o anche
WAN)
 La versione qui descritta fa parte del sistema operativo
lavoro interconnesse come un insieme di calcolatori
indipendenti con file system indipendenti. Lo scopo è quello
di permettere un certo grado di condivisione tra questi file
system, su richiesta esplicita, in modo trasparente
Solaris, che è a sua volta una versione modificata dello
UNIX SVR4, delle stazioni di lavoro Sun e altre architetture.
Utilizza i protocolli TCP/IP o UDP/IP (secondo la rete di
comunicazione)
109
NFS
NFS
 Nel contesto dell’NFS si considera un insieme di stazioni di
 Nel contesto dell’NFS si considera un insieme di stazioni di
lavoro interconnesse come un insieme di calcolatori
indipendenti con file system indipendenti. Lo scopo è quello
di permettere un certo grado di condivisione tra questi file
system, su richiesta esplicita, in modo trasparente.
lavoro interconnesse come un insieme di calcolatori
indipendenti con file system indipendenti. Lo scopo è quello
di permettere un certo grado di condivisione tra questi file
system, su richiesta esplicita, in modo trasparente.
Una directory remota è montata su una directory di un file system
locale. La directory montata assume l’aspetto di un sottoalbero
integrato nel file system locale, e sostituisce il sottoalbero che
discende dalla directory locale
Una directory remota è montata su una directory di un file system
locale. La directory montata assume l’aspetto di un sottoalbero
integrato nel file system locale, e sostituisce il sottoalbero che
discende dalla directory locale
La directory remota si specifica come argomento dell’operazione
di montaggio in modo esplicito; si deve fornire la locazione (o il
nome del calcolatore) della directory remota. Tuttavia, da questo
momento in poi, gli utenti possono accedere ai file della directory
remota in modo del tutto trasparente
111
112
NFS
NFS
 Uno degli scopi nella progettazione dell’NFS era quello di
 Uno degli scopi nella progettazione dell’NFS era quello di
operare in un ambiente eterogeneo di calcolatori, sistemi
operativi e architetture di rete. La definizione dell’NFS è
indipendente da questi mezzi e quindi incoraggia altre
realizzazioni
operare in un ambiente eterogeneo di calcolatori, sistemi
operativi e architetture di rete. La definizione dell’NFS è
indipendente da questi mezzi e quindi incoraggia altre
realizzazioni
 Questa indipendenza si ottiene usando primitive RPC
costruite su un protocollo di rappresentazione esterna dei
dati (XDR, external data representation) usato tra due
interfacce indipendenti dalla realizzazione
 La definizione dell’NFS distingue tra i servizi offerti da un
meccanismo di montaggio e gli effettivi servizi d’accesso ai
file remoti
113
19
110
114
Tre file system indipendenti
Tre file system indipendenti
Montiamo S1:/usr/shared in U:/usr/local....
115
116
Protocollo di montaggio
Montaggio nell’NFS
 Stabilisce la connessione logica iniziale tra un server e un client
 Comprende il nome della directory remota da montare e il
nome del calcolatore server in cui tale directory è memorizzata.
La richiesta di montaggi si associa alla RPC corrispondente e
s’invia al server di montaggio in esecuzione nello specifico
calcolatore server
Lista di esportazione: specifica i file system locali esportati
per il montaggio e i nomi dei calcolatori ai queli è permessa
tale operazione
Montaggio di S1:/usr/shared in U:/usr/local
Montaggi a cascata
S2:/usr/dir2 in U:/usr/local/dir1
(cioè, montata in una directory remota)
117
Protocollo di montaggio
Protocollo NFS
 Stabilisce la connessione logica iniziale tra un server e un client
 Comprende il nome della directory remota da montare e il
nome del calcolatore server in cui tale directory è memorizzata.
La richiesta di montaggi si associa alla RPC corrispondente e
s’invia al server di montaggio in esecuzione nello specifico
calcolatore server
Lista di esportazione: specifica i file system locali esportati
per il montaggio e i nomi dei calcolatori ai queli è permessa
tale operazione
 Quando il server riceve una richiesta di montaggio conforme
alla propria lista di esportazione, riporta al client una maniglia
di file (file handle) da usare come chiave per ulteriori accessi al
file
 La maniglia di file contiene tutte le informazioni di cui ha
bisogno il server per gestire un proprio file
119
20
118
 Offre un insieme di RPC per operazioni su file remoti che
svolgono le seguenti operazioni:
ricerca di un file in una directory
lettura di un insieme di elementi di una directory
manipolazione di collegamenti e di directory
accesso ad attributi di file
lettura e scrittura di file
120
Architettura NFS
Protocollo NFS
 Offre un insieme di RPC per operazioni su file remoti che
svolgono le seguenti operazioni:
ricerca di un file in una directory
lettura di un insieme di elementi di una directory
manipolazione di collegamenti e di directory
accesso ad attributi di file
lettura e scrittura di file
 Interfaccia del file system UNIX (basata sulle chiamate
open, read, write e close e sui descrittori di file)
 File system virtuale (VFS, virtual file system): identifica i
file locali da quelli remoti e invoca l’appropriata operazione
del file system
 Una caratteristica importante dei server NFS è l’assenza
dell’informazione di stato
I server non coservano info sui client
Ogni richiesta deve fornire un insieme completo di argomenti
 Un vantaggio di questa architettura è che il client e il server
 I dati modificati si devono riscrivere nei dischi del server prima
che i risultati siano riportati al client
 Il protocollo NFS non fornisce meccanismi per il controllo della
concorrenza
sono identici; così un calcolatore può essere un client, un
server o entrambi
121
122
Schema dell’architettura NFS
Traduzione dei nomi di percorso
 La traduzione dei nomi di percorso si compie suddividendo il
percorso stesso in nomi componenti ed eseguendo una
chiamata lookup nell’NFS separata per ogni coppia formata
da un nome componente e un vnode di directory
 Una cache per la ricerca dei nomi delle directory, nel sito
del client, conserva i vnode per i nomi delle directory
remote; in questo modo si accelerano i riferimento ai file
con lo stesso nome di percorso iniziale
123
124
Funzionamento remoto
 Tra le normali chiamate del sistema dello UNIX per operazioni su file e
le RPC del protocollo NFS esiste una corrispondenza quasi da uno a uno
 Dal punto di vista concettuale, l’NFS aderisce al paradigma del servizio
remoto, ma in pratica si usano tecniche di memorizzazione transitoria e
cache per migliorare le prestazioni
 Non c’è corrispondenza diretta tra un’operazione remota e una RPC, le
RPC prelevano blocchi e attributi del file che memorizzano localmente
nelle cache. Le successive operazioni remote usano i dati nella cache,
soggetti a vincoli di coerenza
 Esistono due cache: la cache degli attributi dei file (informazioni sugli
inode) e la cache dei blocchi di file
 I client non liberano i blocchi di scrittura differita finché il server non ha
confermato che i dati sono stati scritti sui dischi
125
21
Per oggi basta!!!!
126