Realizzazione del file system
•
•
•
•
•
•
Struttura del file system
Metodi di allocazione
Gestione dello spazio libero
Implementazione di directory
Efficienza e prestazioni
Recuperi
Sistemi operativi
11.1
Struttura del file system
•
•
•
•
Struttura di file
– Unità di memoriazzazione logica
– Collezione di informazioni correlate
Il file system si trova nella memoria secondaria (dischi).
Il file system viene organizzato secondo livelli.
File control block – struttura di memorizzazione che consiste di
informazioni su un file.
Sistemi operativi
11.2
Allocazione contigua
•
•
•
•
•
•
Ciascun file occupa un insieme di blocchi contigui sul disco.
Per reperire tutto il file sono necessarie solo la posizione di inizio
(block #) e la lunghezza (numero di blocchi).
Accesso casuale.
Spreco di spazio. Frammentazione esterna (problema
dell’allocazione dinamica della memoria).
I files non possono crescere (=> frammentazione interna).
Q
Mappatura da logico a fisico.
LA/512
R
– Blocco da accedere = indirizzo iniziale
– Spostamento nel blocco = R
Sistemi operativi
11.3
Allocazione concatenata (linked)
•
•
Ciascun file è una lista concatenata di blocchi su disco: i blocchi possono
essere sparpagliati ovunque sul disco.
Si alloca quanto è richiesto, e poi si concatenano i blocchi insieme.
Sistemi operativi
11.4
Allocazione concatenata
•
•
•
•
Semplice – richiede solo l’indirizzo di inizio
Sistema di gestione dello spazio libero – non si ha spazio perso
Non è possibile l’accesso casuale
Mappatura da logico a fisico
Q
LA/511
R
– Il bocco da accedere è il Q–mo nella catena di blocchi che
rappresentano il file.
– Spostamento nel blocco = R + 1
•
File-allocation table (FAT) – allocazione dello spazio su disco usata da
MS-DOS e OS/2. La FAT è una tabella con un elemento per ogni blocco
disco ed è indirizzato dal numero di blocco. La FAT consente di avere i
puntatori localizzati sul disco e non sparsi.
Sistemi operativi
11.5
Allocazione indicizzata
•
Colleziona tutti i puntatori insieme nel blocco di indice.
Sistemi operativi
11.6
Allocazione indicizzata
•
•
•
•
Richiede una tabella di indice
E’ possibile un accesso casuale
Si ha un accesso dinamico senza frammentazione esterna, ma
c’è il sovraccarico del blocco di indice.
Se si ha un file di dimensione massima 256K parole e con una
dimensione di blocco di 512 parole, è necessario solo un blocco
per l’indice.
Q
LA/512
R
– Q = spostamento nella tabella indice
– R = spostamento nel blocco
Sistemi operativi
11.7
Schema concatenato
•
•
Mappatura logico–fisica in un file di dimensione non limitata
(dimensione del blocco di 512 parole).
Schema concatenato – Si collegano blocchi della tabella indice
(non si ha un limite alla dimensione).
Q1
LA / (512 x 511)
R1
– Q1 = blocco della tabella indice
– R1 è impiegato come segue:
Q2
R1 / 512
R2
– Q2 = spostamento nel blocco della tabella indice
– R2 spostamento nel blocco del file:
Sistemi operativi
11.8
Indice multilivello

outer-index
index table
Sistemi operativi
11.9
file
Schema combinato: UNIX (4K byte per blocco)
Sistemi operativi
11.10
Gestione dello spazio libero
•
Vettore di bit (n blocchi)
0 1 2
n-1
…
bit[i] =
•
0  block[i] occupato
1  block[i] libero
Calcolo del numero del primo blocco libero. Si scorre il vettore,
cercando il primo byte diverso da 0.
(numero di bit per parola) *
(numero di parole con valore 0) +
offset del primo bit a 1
•
Funziona bene se il vettore è conservato in memoria centrale.
Sistemi operativi
11.11
Gestione dello spazio libero
•
La mappa dei bit richiede uno spazio ulteriore. Esempio:
block size = 212 byte
disk size = 230 byte (1 gigabyte)
n = 230/212 = 218 bit (o 32K byte)
•
•
•
•
E’ semplice avere file contigui
Lista concatenata (free list)
– Non è facile prendere spazio contiguo
– Non si spreca spazio
Raggruppamento: memorizzazione degli indirizzi di n blocchi
liberi sul primo di tali blocchi. Sull’ultimo sono indirizzati altri
blocchi, e così via.
Conteggio: Si indica un blocco libero, e da quanti altri blocchi
liberi (contigui) è seguito.
Sistemi operativi
11.12
Gestione dello spazio libero
•
E’ necessario proteggere:
– Puntatore alla lista dei blocchi liberi
– Mappa di bit
 Deve essere tenuta sul disco
 Le copie in memoria e sul disco possono essere diverse
 Non si può permettere a block[i] di essere in una
situazione in cui bit[i] = 1 in memoria e bit[i] = 0 su disco.
– Soluzione:
 Porrre bit[i] = 1 sul disco.
 Allocare block[i]
 Porre bit[i] = 1 in memoria
Sistemi operativi
11.13
Realizzazione di directory
•
•
Lista lineare di nomi di file con puntatori ai blocchi di dati.
– Semplice da implementare
– Esecuzione onerosa (dal punto di vista del tempo di
calcolo).
Tabella hash – lista lineare con struttura hash.
– Migliora il tempo di ricerca nella directory
– Collisione – situazione in cui due nomi di file generano lo
stesso indirizzo hash nella tabella
– dimensione fissa
Sistemi operativi
11.14
Efficienza e prestazioni
•
•
L’efficienza dipende da:
– allocazione su disco e algoritmi di gestione delle directory
– tipi di dati conservati nell’elemento della directory
corrispondente al file
Prestazione
– disk cache – sezioni separate della memoria impiegate per
blocchi usati molto spesso
– free-behind e read-ahead – tecniche per ottimizzare
l’accesso sequenziale
– si migliorano le prestazioni dei PC dedicando sezioni della
memoria come dischi virtuali o dischi RAM.
Sistemi operativi
11.15
Varie posizioni per disk–caching
Sistemi operativi
11.16
Recupero
•
•
•
Verificatore di coerenza – confronta i dati nella directory con
blocchi di dati sul disco, e cerca di fissare le incoerenze.
Si impiegano programmi di sistema per copiare (back up) dati dal
disco ad un altro dispositivo di memorizzazione (dischetto, nastro
magnetico).
Si recuperano file persi o dischi danneggiati ricaricandoli dal
back–up.
Sistemi operativi
11.17