Home

Federica EU

1/30

Marco Lapegna » 18.L'organizzazione fisica dei file system

Sistemi operativi

L’organizzazione fisica dei file system

Problema

Un problema fondamentale nella realizzazione di un f.s. e’ la definizione di algoritmi e strutture dati per far corrispondere il file system logico (file, directory,…) al file system fisico (dispositivi fisici della memoria secondaria)

Struttura del file system

Struttura del disco

e’ suddiviso in partizioni (minidischi, volumi, …)
ogni file system e’ contenuto in una partizione e una partizione puo’ contenere un solo file system

Organizzazione di una partizione

Dipende dal s.o. e dal file system

In generale una partizione e’ divisa in 4 aree distinte

Area di bootstrap
Area di controllo
Area dei file descriptor
Area dei blocchi dati

Oranizzazione di una partizione

Area di bootstrap

Contiene il programma per l’inizializzazione del sistema e si trova nel primo blocco di una partizione
Diversi nomi
- Boot block (Unix file system), Partition boot sector (NTFS)

Area dei file descriptor

Contiene le strutture dati e gli indirizzi dei blocchi dei dati dei file
Diversi nomi
- i-list (UFS)

Organizzazione di una partizione

Area di controllo

Contiene informazioni su tutta la partizione
- Dimensione della partizione
- Numero e posizione dei blocchi liberi
- Dimensione della i-list (area dei file descriptor)
Diversi nomi
- Superblocco (UFS), Master file table (NTFS)

Area dei dati

Contiene i blocchi dei dati dei file e i blocchi liberi

Area dei blocchi dei dati

Problema: come allocare lo spazio disco ai file in modo da avere spreco minimo di memoria e rapidità di accesso?

Il metodo di allocazione dello spazio su disco descrive come i blocchi fisici del disco vengono allocati ai file:

Allocazione contigua
Allocazione concatenata
Allocazione indicizzata

Allocazione contigua

Ogni file occupa un insieme di blocchi contigui.

Per reperire il file occorrono solo la locazione iniziale e la lunghezza

Principali problemi:

i file non possono crescere
frammentazione

Allocazione concatenata

I blocchi possono essere sparsi ovunque nel disco.

Ciascun file è una lista di blocchi collegati da puntatori.
Principali problemi:

per trovare un blocco e’ necessario scorrere tutta la lista sul disco
scarsa efficienza

Allocazione tabellare

Unica tabella che contiene la lista dei puntatori ai blocchi del disco
Per trovare un blocco si scorre la lista nella tabella e non sul disco
File Allocation Table FAT (MS-DOS)

FAT (Microsoft)

Prima versione della FAT dell’MS-DOS 1.0 (FAT12) usava 12 bit per l’indirizzamento dei blocchi.

Allocazione indicizzata

Colleziona tutti i puntatori in un unico blocco indice.

La directory contiene l’indirizzo del blocco indice

Principali problemi:

overhead per l’accesso al blocco indice (comunque inferiore all’allocazione concatenata)

Esempio

File di grandi dimensioni

se il file ha dimensione maggiore di 256Kbyte e’ possibile concatenare i blocchi indice.

Una alternativa

Il blocco indice punta a blocchi indice di secondo (e terzo) livello.

Schema combinato: Unix

Nel Unix File System, l’area dei descrittori (chiamata i-list: index list) contiene una tabella di descrittori chiamati i-node (index node)

Ogni i-node e’ accessibile attraverso l’indice della tabella (i-number)

Un i-node contiene gli attributi di un file

Tra gli attributi vi sono gli indirizzi dei blocchi

12 diretti
1 indiretto singolo
1 indiretto doppio
1 indiretto triplo

Schema combinato: Unix

I-node di UNIX

Gestione dello spazio libero

L’area di controllo (superblocco) di una partizione contiene le informazioni sulla posizione dei blocchi liberi

Tre possibili gestioni:

Bitmap
Lista dello spazio libero
Raggruppamento

Bitmap

Vettore di bit (n blocchi)

Vantaggi: Buone prestazioni se il vettore è conservato in memoria centrale.

Svantaggi: per trovare un blocco libero puo’ essere necessario esaminare gran parte della bitmap

Lista concatenata

Lista di blocchi liberi legati da puntatori

Puntatori alla testa e alla coda sono memorizzati nel superblocco

Vantaggio: 1 accesso per trovare un blocco libero
Svantaggio: inefficiente se e’ necessario trovare molti blocchi

Raggruppamento

Raggruppamento: memorizzazione degli indirizzi di n blocchi liberi sul primo di tali blocchi. Sull’ultimo sono indirizzati altri blocchi, etc.

Vantaggio: rapida ricerca di blocchi liberi
Svantaggio: gestione inefficiente se il numero di blocchi e’ grande

Efficienza e prestazioni

Per migliorare le prestazioni, i blocchi piu’ usati sono tenuti in memoria centrale (cache del disco)

Gestione analoga alla paginazione

Quante volte la cache viene sincronizzata col disco?

periodicamente (UNIX)
ad ogni richiesta di scrittura (MS-DOS)

Estrarre un dischetto sotto MS-DOS non è critico, con UNIX occorre smontare il dispositivo

Incoerenza

Uso tipico dei file:

si legge un blocco da disco
si modifica il blocco in memoria
lo si riscrive

Se si verifica un crash:

alcuni blocchi non sono scritti
il file system diventa incoerente

Tecniche per garantire la coerenza

Il problema della consistenza e’ particolarmente rilevante per “blocchi critici” (blocchi che contengono FAT, i-node, bitmap,…)

Due possibili soluzioni

curare (file system checker)
- Strumenti come fsck (Unix), scandisk (windows)
prevenire (file system con annotazioni)
- Ext3, NTFS

Controlli di coerenza

Due tabelle used e free che contengono un elemento per ogni blocco dati del sistema

used[i]: Si inizializza a 0, si incrementa se il blocco viene assegnato ad un file e si decrementa se viene rilasciato
free[i]: Si inizializza a 1, si decrementa quando il blocco viene assegnato ad un file e si incrementa quando ritorna libero

Controlli di coerenza

Nessun errore. Ogni blocco e’ correttamente elencato nel sistema
Blocco mancante. Nessun problema di coerenza ma spazio sprecato. Soluzione: si pone free[i]=1

Controlli di coerenza

Nessun errore ma il blocco potrebbe essere assegnato due volte. Soluzione: si pone free[i]=1
Blocco libero o occupato? Nessun problema ma il blocco potrebbe essere assegnato due volte . Soluzione: si pone free[i]=0