File System Concetti e tecniche generali



Scaricare 1.24 Mb.
12.11.2018
Dimensione del file1.24 Mb.


File System


Il file system

  • Il file system è la parte del SO che si occupa di mantenere i dati/programmi in modo persistente

  • Tipicamente le astrazioni fornite sono:

    • File : unità di informazione memorizzata in modo persistente
    • Directory : astrazione che permette di raggruppare assieme più file


Struttura di un File

  • Come può essere strutturata l’informazione all’interno di un file

    • sequenze di byte, sequenze di record , alberi con chiave


Accesso ai File

  • Accesso diretto (random)

    • i byte/record possono essere letti in qualsiasi ordine
    • una read può essere specificata …
      • specificando la posizione del dato da accedere ad ogni chiamata, …
      • usando una speciale operazione (la seek) per posizionare la testina prima di iniziare più letture
    • nei moderni sistemi operativi tutti i file sono automaticamente ad accesso diretto


Tipici attributi di un file



Operazioni su File

  • Create

  • Delete

  • Open

  • Close

  • Read

  • Write



File system gerarchici



Operazioni sulle directory

  • Create

  • Delete

  • Opendir

  • Closedir



Implementazione di un File System (1)

  • Come rappresentare i file ?

    • i dati sono memorizzati in unità (blocchi) di ampiezza fissa (tipicamente 1,2 KB)
    • si devono memorizzare gli attributi e la posizione dei singoli blocchi
  • Come rappresentare le directory ?

    • generalmente sono file con uno speciale formato
  • Come organizzare lo spazio disco ?

    • allocazione dei blocchi relativi ad un singolo file
    • gestione blocchi liberi
    • tenere traccia della root directory


Implementazione di un FS: Unix (2)



Implementazione dei File (1)

  • Allocazione contigua dello spazio disco

    • ogni file viene memorizzato in un gruppo di blocchi contigui (run)
    • es :


Allocazione contigua (2)



Allocazione contigua (3)

  • Fenomeno della frammentazione interna :

    • se l’ultimo blocco non è del tutto pieno si spreca dello spazio


Allocazione contigua (4)

  • Vantaggi dell’allocazione contigua:

    • è facile tenere traccia dei blocchi che appartengono a ciascun file
      • indirizzo su disco del blocco iniziale (B)
      • lunghezza del file (in blocchi)
    • se voglio l’indirizzo del blocco X del file
      • ind(X) = B + X
    • le prestazioni della lettura sono eccellenti
      • basta una seek ed è possibile leggere tutto il file in blocchi contigui (senza rotational delay …)


Allocazione contigua (5)

  • Svantaggi dell’allocazione contigua:

    • (1) frammentazione esterna : es
    • dopo un po’ il disco sarà frammentato in un insieme di buchi (hole), troppo piccoli per contenere un file (es. file R 5 blocchi)
    • de-frammentazione del disco :


Allocazione contigua (6)

  • Svantaggi dell’allocazione contigua (cont.):

    • (2) l’ampiezza massima di un file deve essere decisa al momento della creazione
      • dobbiamo riservare un numero adeguato di blocchi per la sua crescita futura
      • ancora spazio sprecato
      • difficile da stimare ed utilizzare : es prima di iniziare ad editare un file di testo devo dire quanto sarà lungo … altrimenti l’editing può fallire!!!!


Allocazione contigua (7)

  • Svantaggi dell’allocazione contigua (cont.):

    • (2) l’ampiezza massima di un file deve essere decisa al momento della creazione
      • dobbiamo riservare un numero adeguato di blocchi per la sua crescita futura
      • ancora spazio sprecato
      • difficile da stimare ed utilizzare : es prima di iniziare ad editare un file di testo devo dire quanto sarà lungo … altrimenti l’editing può fallire!!!!
  • L’allocazione contigua viene utilizzata nei FS dei CD ROM e DVD !!



File: lista concatenata di blocchi

  • Memorizzazione come lista concatenata di blocchi



File: lista concatenata di blocchi (2)

  • Vantaggi della lista concatenata :

    • non c’è frammentazione esterna
    • per ogni file è necessario mantenere solo il puntatore al primo blocco
  • Problemi :

    • lettura di tutto il file molto lenta
    • accesso random molto lento
    • perdita di un certo numero di byte iniziali
      • l’ampiezza di blocco non è più una potenza di 2
      • diventa più costoso il calcolo del blocco ...


File: lista concatenata di blocchi (3)

  • Es. indirizzi di 4 byte, blocchi fisici di 1 K

    • se voglio effettuare una read di 40 byte dall’indirizzo 2046
    • divido 2046 per (1024 -4=1020) :
      • risultato = 2, resto = 6
      • devo leggere 40 byte, in blocco 2 a partire dal byte 6
    • le divisioni per numeri arbitrari sono operazioni estremamente costose
    • le divisioni per potenze di 2 sono shift !!


Liste concatenate con FAT



Liste concatenate con FAT

  • Vantaggi :

    • l’ampiezza di blocco è una potenza di due
    • accesso casuale più veloce (non accede alla memoria secondaria
  • Svantaggi :

    • tutta la FAT deve stare in memoria
    • disco 20 GB, blocchi 1K
      • ampiezza FAT = 4* 20M !
      • Paginazione, lentezza etc ...


Index-node (i-node)

  • Es. i-node di un file Unix



Index-node (i-node) (2)

  • Vantaggi :

    • solo gli i-node dei file in uso devono risiedere in RAM
    • lo spazio è proporzionale al numero massimo di file aperti e non dipende dall’ampiezza del disco
    • l’efficienza decresce con l’ampiezza del file


Implementazione delle Directory (1)

  • Devono permettere di recuperare tutte le informazioni relative ai file contenuti

  • Punto fondamentale : associare il nome del file (una stringa di caratteri) ad attributi e dati (indirizzo/i dei blocchi)

    • diversi formati
    • diverse restrizioni sui possibili nomi dei file
      • lunghezza fissa o arbitraria
      • case sensitiveness : pippo e PiPPo


Implementazione delle Directory (2)

  • Soluzione più semplice :

    • la directory contiene una tabella con un elemento per ogni file
    • attributi e indirizzi del blocchi del file X sono memorizzati direttamente nell’elemento della tabella relativo ad X
    • è la soluzione usata dai FS FAT-16, FAT-32


Implementazione delle Directory (3)



Implementazione delle directory (4)

  • Una directory in un sistema con i-node

    • es da Unix V7


Due modi di trattare i nomi di file “lunghi”

  • Due modi di trattare i nomi di file “lunghi”

    • (a) In linea (b) In un heap


Ricerca di un file X in una directory

  • Ricerca di un file X in una directory

    • tipicamente i nomi dei file non sono in ordine (ricerca lineare)
    • se aspettiamo directory con centinaia di file si possono usare hash table


Implementazione delle directory (7)

  • Ricerca di un file X in una directory

    • tipicamente i nomi dei file non sono in ordine (ricerca lineare)
    • se aspettiamo directory con centinaia di file si possono usare hash table
    • alternativamente si può fare il caching di file acceduti recentemente (Berkley FFS)


Gestione dello spazio disco (1)

  • Praticamente tutti i file system:

    • dividono i file in blocchi di ampiezza fissata ed eseguono letture e scritture su blocchi o multipli
    • i blocchi non sono contigui su disco
  • Problema 1 : come scegliere l’ampiezza del blocco?

    • Blocchi piccoli usano meglio lo spazio disco
      • diminuiscono la frammentazione interna
    • Blocchi grandi velocizzano gli accessi


Gestione dello spazio disco (2)

  • Problema 2 : come tenere traccia dei blocchi liberi su disco ?

    • Free list
      • lista concatenata di blocchi pieni di indirizzi di blocchi liberi
    • Bitmap
      • una mappa di bit con un bit per ogni blocco
      • es. 0 blocco libero, 1 blocco in uso
      • mantiene la contiguità dei blocchi (allocare un file su blocchi vicini diminuisce il tempo di seek in letture consecutive


Gestione dello spazio disco (3)



Gestione dello spazio disco (4)

  • (a) blocco di puntatori ai blocchi liberi quasi pieno (RAM)

    • - tre blocchi di puntatori su disco
  • (b) situazione dopo aver liberato un file di 3 blocchi

  • (c) strategia alternativa per gestire i 3 blocchi

    • - gli elementi in grigio puntano a blocchi di disco liberi


Gestione dello spazio disco (4)

  • Il meccanismo delle quote per tener traccia dello spazio disco utilizzato da ciascun utente



Affidabilità di un file system

  • Problemi legati all’hw del disco

    • settori difettosi
    • blocchi corrotti
      • raccolti in file fittizi (bad block files)


Gestione degli errori del disco

  • Una traccia con un settore difettoso

  • Sostituzione del settore difettoso con un settore di riserva

  • Slittamento dei settori per evitare quello difettoso



Affidabilità di un file system (2)

  • Backup periodici

    • copia delle informazioni del FS per poterle utilizzare in caso di
      • crash del disco, alluvioni etc ...
      • cancellazioni accidentali
    • backup fisico
      • si copiano tutti i blocchi del disco (su tape o altro)
    • backup logico
      • si copiano file e directory modificati dopo una certa data


Stable Storage

  • Memorizzazione stabile

  • Permette di mettersi al riparo da errori che si verificano durante una scrittura :

    • sto effettuando una write()
    • dopo la scrittura calcolo i codici correttori di errore (ECC) che segnalano un malfunzionamento
    • a questo punto il vecchio valore del settore è andato perso ed il nuovo è sbagliato!
  • Nello stable storage, ogni volta che eseguiamo una scrittura si garantisce che il valore scritto è corretto oppure è uguale a quello vecchio



Stable Storage (2)

  • Come viene realizzato lo stable storage:

  • due dischi, più software

  • assunzioni :

    • quando effettuiamo una write() di un blocco si scrive una valore corretto o scorretto
    • un valore scorretto può essere determinato rileggendo il valore e controllando gli ECC
    • la probabilità che lo stesso settore X abbia malfunzionamenti su due dischi diversi è trascurabile


Stable Storage (3)

  • Implementazione :

    • Ogni blocco viene implementato usando due blocchi con lo stesso indirizzo sui due dischi.
      • Scritture : scrive la stessa infromazione prima nel primo disco (blocco X) e poi nel secondo (blocco X)
      • Letture : legge dal primo disco e se ci sono errori dal secondo
    • Recovery dopo un crash
      • si leggono tutti i blocchi dei due dischi e si confrontano
      • se sono corretti e uno dei due ha l’ECC sbagliato, viene sovrascritto con l’altro
      • se sono diversi ma corretti, il blocco del primo disco viene scritto sul secondo


Stable Storage (4)

    • Casi possibili di crash in uno stable storage


Consistenza di un File System (1)

  • Problema:

    • tipicamente i file system leggono un bloccho, lo modificano e scrivono la copia aggiornata più tardi
    • se avviene un crash prima della scrittura della copia aggiornata il FS può trovarsi in uno stato inconsistente
    • il problema è ancora più preoccupante se si tratta di i-node, informazioni di una directory o informazioni sui blocchi liberi
  • Ci sono utility che

    • controllano la consistenza di un file system
    • lo riportano in uno sttao consistente (eventualmente con la perdita di dati)
    • es: scandisk (Windows) fsck (Unix)


Consistenza di un File System (2)

  • Funzionamento di fsck

  • Verifica la consistenza dei blocchi

    • scandisce i-node e blocchi liberi
    • costrisce tabella blocchi liberi e tabella blocchi in uso
      • 00 missing block - viene aggiunto alla lista libera
      • 20 duplicate free block - viene ricostruita la lista libera
      • 02 duplicate data block - viene duplicato il blocco per avere una copia diversa in ciascun file
  • Verifica la consistenza delle directory

    • scandisce le directory
    • costruisce la tabella di occorrenza file
    • controlla la consistenza fra la tabella di occorrenza ed il conto degli hard link nell’i-node
      • se differiscono si modifica l’i-node


Consistenza di un File System (3)

    • (a) consistente (consistent)
    • (b) blocco mancante (missing block)
    • (c) blocco duplicato nella lista libera (duplicate free block)
    • (d) blocco dati duplicato (duplicate data block)


Prestazioni di un File System (1)

  • Strutture dati per il cache dei blocchi

  • Hash su dispositivo::indirizzo del blocco

  • I blocchi critici per la consistenza del FS vengono scritti subito (i-node, directory, lista libera)



Prestazioni di un File System (2)

  • Si effettua la lettura anticipata (read ahead)

    • si controlla il pattern di accesso del disco e se ne tiene traccia nell’i-node
    • se l’accesso è sequenziale si leggono in anticipo i prossimi blocchi della sequenza e si memorizzano nella cache
  • Si cerca di allocare blocchi di disco ‘vicini’ per blocchi logici ‘vicini’ di uno stesso file

  • Si ottimizza l’allocazione degli i-node

    • si cerca di minimizzare il tempo di seek quando si segue un path name


Prestazioni di un File System (3)

    • (a) Gli i-node sono piazzati all’inizio del disco
    • (b) Il disco è diviso in gruppi di cilindri, ognuno con i suoi blocchi ed i suoi i-node




Condividi con i tuoi amici:


©astratto.info 2019
invia messaggio

    Pagina principale