Struttura del File-System 6/10/14 - di-srv.unisa.itcicalese/SO/2014/ImplementazioneFS.pdf · Dati...

6/10/14!

1!

Implementazione del File System!

11.2! Silberschatz, Galvin and Gagne ©2005!Operating System Concepts – 7th Edition, Jan 1, 2005!

Struttura del File-System!

  Struttura dei File!  Unità logica di memorizzazione!  Collezione di informazioni correlate!

  File control block (inode) – struttura dati per le informazioni principali riguardanti un file!

  Fle system !  risiede in memoria secondaria (dischi)!  Organizzazione a livelli!


Livelli di un File System!

11.4! Silberschatz, Galvin and Gagne ©2005!Operating System Concepts – 7th Edition, Jan 1, 2005! 4

Filesystem!

6/10/14!

2!

11.5! Silberschatz, Galvin and Gagne ©2005!Operating System Concepts – 7th Edition, Jan 1, 2005! 5

filesystem (i-node)!


Tipico File Control Block (i-node)!


Strutture del FS mantenute in memoria!

  Tabella dei volumi/dispositivi montati!  Struttura delle directory !

  Dati relativi a directory cui si e’ fatto accesso di recente!  Tabella dei file aperti di sistema!

  Control block per ciascun file aperto!  Tabella dei file aperti per processo!


Strutture del FS mantenute in memoria!

6/10/14!

3!


Implementazione della Directory!

  Lista Lineare di nomi di file con puntatori ai blocchi dei dati.!  Semplice da programmare!  Lenta!

  Tabella Hash – lista lineare con struttura dati hash.!  Basso tempo di ricerca!  Problema delle collisioni – due o più nomi di file “hashed”

nella stessa locazione!  Taglia fissa!

  B-tree – alberi di ricerca!


Directory come B-tree!


Montaggio del File System (cap 10)!

  Un sistema può avere più file system nella struttura delle directory!

  Un file system deve essere montato (collegato) prima che sia possibile accedervi!

  La locazione dove un file system viene collegato alla struttura delle directory prende il nome di mount point!


(a) Esistente. (b) Partizione non montata!

6/10/14!

4!


Mount Point!


Metodi di Allocazione!

  Per metodo di allocazione si intende il modo in cui i blocchi del disco sono allocati ai file:!

  Allocazione contigua!

  Allocazione concatenata!

  Allocazione indicizzata!


Allocazione Contigua!

  Ogni file occupa un insieme di blocchi del disco contigui!

  Semplice – solo la locazione (blocco #) iniziale e la lunghezza (numero di blocchi) devono essere memorizzate !

  Accesso diretto !

  Spreco di spazio (problemi con l’allocazione dinamica)!

  Non è possibile aumentare la dimensione di un file!



  Funzione di mappatura logico/fisico!

LA/512!

Q!

R!

Blocco desiderato = Q + starting address Scostamento all’interno del blocco = R

6/10/14!

5!




Estensioni!

  Schema modificato di allocazione contigua!

  I blocchi sono allocati a gruppi detti estensioni (extent)!

  Un’estensione è una collezione di blocchi contigui!  Un file consiste di una o più estensioni, non necessariamente

contigue.!


Allocazione concatenata!

  Ogni file è un lista concatenata di blocchi!  tali blocchi possono essere distribuiti ovunque sul disco.!

puntatore!blocco =!


Allocazione Concatenata (Cont.)!

  Semplice – solo i blocchi iniziale e finale vanno memorizzati!  Sistema di gestione dello spazio libero – nessuno spreco !  Accesso diretto/random difficile da implementare!  Sistema di traduzione logico/fisico!

Q: numero del blocco nella lista concatenata di blocchi per il file!!R: Scostamento nel blocco!

!! Alternativa: File-allocation table (FAT)!! ! – metodo di allocazione dello spazio usato da MS-DOS e OS/2.!

LA/511!Q!

R!

6/10/14!

6!


Allocazione concatenata!


File-Allocation Table!


Allocazione Indicizzata!

  Mantiene insieme tutti i puntatori ai blocchi in un blocco indice.!  Vista logica:!

index table!


Esempio di Allocazione Indicizzata!

6/10/14!

7!


Allocazione Indicizzata (Cont.)!

  Necessita di una tabella indice!  Possibilità di accesso diretto/random!  Assenza di frammentazione esterna, ma possibile overhead

nel blocco indice.!  Per un file di taglia massima pari a 256K parole e blocchi di

taglia pari a 512 words, c’è bisogno di un solo blocco per mantenere l’indice.!

LA/512!Q!

R!

Q = scostamento nella tabella indice!R = scostamento nel blocco!


Allocazione Indicizzata – Lista!

  Per un file di taglia illimitata e dimensione dei blocchi pari a 512:!  Tabella indice implementata con lista concatenata

(taglia illimitata).!

LA / (512 x 511)!Q1!

R1!Q1 = blocco della tabella indice!R1 usato come segue:!

R1 / 512!Q2!

R2!

Q2 = scostamento nel blocco della tabella indice!R2 scostamento nel blocco del file:!


Allocazione Indicizzata – 2 Livelli!

  Indice a 2 livelli (taglia massima di un file 5123)!

LA / (512 x 512)!Q1!

R1!

Q1 = scostamento nell’indice esterno!R1 usato come segue:!

R1 / 512!Q2!

R2!

Q2 = scostamento nel blocco della tavola indice!R2 scostamento nel blocco del file:!


Allocazione Indicizzata!

!

outer-index!

index table! file!

6/10/14!

8!


Schema Misto: UNIX (4K byte per blocco)!


Gestione dello Spazio Libero!

  Bit vector (n blocchi)!

…!

0! 1! 2! n-1!

bit[i] =!

!

1 ⇒ block[i] free!0 ⇒ block[i] occupied!

Calcolo dell’indice del primo blocco libero!

(number of bits per word) *!(number of 0-value words) +!offset of first 1 bit!


Gestione dello Spazio Libero!

  Lo schema a Bit map può richiedere spazio eccessivo!  Es.:!

! !block size = 212 bytes!! !disk size = 230 bytes (1 gigabyte)!! !n = 230/212 = 218 bits (or 32K bytes)!

  È facile cercare spazi di memoria contigua !  Lista concatenata (free list)!

  Difficile trovare spazi di memoria contigua!  Ma non c’è spreco di spazio!

  Raggruppamento!  Un blocco contiene gli indirizzi di n blocchi liberi !

  Conteggio!  Indirizzo del primo libero e del numero di liberi consecutivi!


Gestione dello Spazio Libero (Cont.)!

  Problemi !  Bit map!

 Consistenza tra la copia sul disco e quella in memoria!

–  block[i] : bit[i] = 1 in memoria e bit[i] = 0 su disco !

6/10/14!

9!


Lista concatenata dello spazio libero!

Protezione ed Affidabilità del File System!


Protezione!

  Il creatore/possessore del File dovrebbe poter decidere:!  Le azioni possibili sul file!  E da chi esse sono effettuabili!

  Tipi di accesso ad un file!  lettura!  Scrittura!  esecuzione!  aggiunta in calce!  Cancellazione!  lista del contenuto (tipico per file di tipo directory)!


Liste di Accesso e Gruppi!

  Modalità di accesso: lettura (Read), scrittura (Write), esecuzione (eXecute)!  3 classi di utenti!

! ! ! ! !RWX!! !a) owner/user access !7 !⇒ !1 1 1

! ! ! !RWX!! !b) group access !6 ! ⇒ !1 1 0!! ! ! ! !RWX!! !c) public/others access !1 ! ⇒ !0 0 1!

  Possibilità di creare gruppi (con nome univoco), es. G, e aggiungervi utenti.!  Per un dato file (es. game) o subdirectory, si può definire l’accesso per un

dato gruppo di utenti.!

owner! group! public!

chmod! 761! game!

Collegare un gruppo ad un file chgrp G game

6/10/14!

10!


UNIX Directory - ls!


Regole di accesso per i processi!

  Identificativi per un processo P (es. UNIX)!  Real User/Group ID uid(P) !  Effective User/Group euid(P)!

  Identificativi per un file F!  Utente proprietario own(F)!  Gruppo principale grp(F) !!

!Un processo P accede al file F in lettura se !!!a) euid(P) = own(F) !!b) F ha i permessi di lettura per il proprietario!

!!L’esistenza di Effective UID permette ad utenti di eseguire comandi

con permessi di accesso da superutente!!!


Recovery!

  Test di consistenza !  confronta dati nella struttura della directory con i data

blocks sul disco,!  Prova a risolvere le inconsistenze!

  Uso di back up dei dati dal disco principale ad un altro dispositivo!  Recovery dei file persi mediante restore dall’unità di

back up!


Log Structured File Systems!

  Log structured (or journaling) file system !  Memorizza ogni modifica al file syst. come transazione!

  Ogni transazione memorizzata in un log!  Una transazione è committed se scritta nel log!  non è detto che il file syst. sia già aggiornato!

  Le transazioni nel log vengono realizzate sul file system asincronamente!  Una volta modificato il file syst., la transazione è eliminata dal log!

  In caso di crash del file system, tutte le transazioni nel log devono essere eseguite!

6/10/14!

11!


Virtual File System!

  Un Virtual File System (VFS) fornisce una prospettiva object-oriented all’implementazione di file system.!

  Permette di avere la stessa interfaccia di chiamate di sistema (API) per diversi tipi di file system.!

  L’ API si riferisce all’interfaccia del VFS, e non ad ogni specifico file system.!


Virtual File System - schema!


Efficienza e Performance!

  L’efficienza dipende da:!  Algoritmi di allocazione del disco e delle directory!  Dimensione dei puntatori ai blocchi!  Informazioni mantenute negli elementi delle directory!

  Performance!  disk cache!  free-behind and read-ahead – tecniche di ottimizzazione degli

accessi!  File mappati in memoria!  Uso di sezioni di memoria per implementare dischi virtuali o

dischi ram!


File Mappati in Memoria!

  I/O con file mappati in memoria permette la gestione dei file in termini di accessi alla memoria. Un blocco del disco viene mappato ad una pagina di memoria!

  Un file viene inizialmente letto mediante paginazione su richiesta. Una porzione del file della dimensione di una pagine viene inizialmente trasferita dal file-system in una pagina fisica. Ogni successiva istruzione di lettura/scrittura viene trattata come una operazione di accesso alla memoria.!

  I/O semplificato!  Accesso alla memoria piuttosto che read()write()!

  Più processi possono mappare lo stesso file in memoria!  Condivisione delle pagine!

6/10/14!

12!


Memory Mapped Files!


Multiple Disks!

 Disk I/O può migliorare se le operazioni sono distribuite su più testine di lettura/scrittura! O dischi multipli!

 Disk failures e recovery mediante memorizzazione con ridondanza!

!


RAID!

 Redundant Array of Independent Disks!

 Set di disk drive visti dal SO come un unico drive logico!

 Dati distribuiti sui dischi fisici ! La capacità non utilizzata per I dati è

usata per informazione ridondante per il recovery da situazioni di errore/failure.!


RAID 0 - Stripped!

•  Non un vero RAID – nessuna ridondanza!•  Nessuna possibilitaà di recovery!•  Molto veloce (parallel read/write)!

6/10/14!

13!


RAID 1 - Mirrored!

 Ridondanza = duplicazione! Letture in parallelo.! Semplice recovery (esistono due copie)!


RAID 2 (Usa codici di Hamming)!

 Rotazione sincronizzata! Uso di data stripping (extremely small)! Hamming code correggono errori su un

singolo bit e riconscono errori su 2 bit!


RAID 3 bit-interleaved parity!

 Simile a RAID-2 ma tutti i bit di parità sono memorizzati sullo stesso disco!


RAID 4 Block-level parity!

 A bit-by-bit parity strip is calculated across corresponding strips on each data disk!

 The parity bits are stored in the corresponding strip on the parity disk.!

6/10/14!

14!


RAID 5 Block-level Distributed parity!

 Similar to RAID-4 but distributing the parity bits across all drives!

Struttura del File-System 6/10/14 - di-srv.unisa.itcicalese/SO/2014/ImplementazioneFS.pdf · Dati...

Documents

Transcript of Struttura del File-System 6/10/14 - di-srv.unisa.itcicalese/SO/2014/ImplementazioneFS.pdf · Dati...