Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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

Controlli di coerenza

Il blocco e’ assegnato a due file. Gravi problemi di coerenza. Soluzione: si pone used[i]=1 ma un file risultera’ corrotto.


File system con annotazioni

Basati su un giornale delle annotazioni

  1. Prima di ogni operazione sul f.s. si annotano le modifiche
  2. Si effettuano le operazioni
  3. Si rimuovono le annotazioni

In caso di caduta del sistema durante la modifica, le annotazioni nel giornale permettono di ripristinare la coerenza del file fystem


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion