Il File System

(1)

Il File System

(2)

Indice

4. Il File System 5. Vantaggi del FS 6. Protezione

7. Condivisione 8. I file - 1 9. I file - 2

10. Attributi dei file 11. Directory

12. Livelli di astrazione - 1 13. Livelli di astrazione - 2

14. Struttura logica vs Struttura fisica 15. Compiti del file system

16. Integrità dei dati e affidabilità 17. Struttura logica di un file – 1 18. Struttura logica di un file – 2

19. Struttura logica di un file – 3 20. Struttura logica di un file – 4 21. Struttura logica di un file – 5 22. Metodo di accesso

23. Accesso sequenziale 24. Accesso diretto

25. Descrittore del file 26. Directory – 1

27. Directory – 2 28. Directory – 3

29. Directory simbolica 30. Directory di base 31. Tipi di directory – 1 32. Tipi di directory – 2

(3)

Indice

33. Tipi di directory – 3

34. Operazione di I/O su file - 1 35. Operazione di I/O su file - 2 36. Operazione di I/O su file - 3 37. Operazione di I/O su file - 4 38. Operazione di I/O su file - 5 39. Operazione di I/O su file - 6 40. File system fisico

41. Descrittore sistema archiv. - 1 42. Descrittore sistema archiv. – 2 43. Allocazione spazio su disco 44. Allocazione contigua - 1 45. Allocazione contigua - 2

46. Allocazione concatenata - 1 47. Allocazione concatenata - 2

48. Allocazione concatenata – FAT – 1 49. Allocazione concatenata – FAT – 2 50. FAT - 1

51. FAT - 2

52. Allocazione indicizzata 53. Blocchi indice - 1

54. Blocchi indice - 2

55. Nodi indice (Unix → Linux) 56. i-node

57. Blocchi liberi

(4)

Il file system

Il file system è quel modulo del sistema operativo che fornisce i meccanismi di accesso e

memorizzazione delle informazioni (programmi e dati) allocate in memoria di massa.

 Identifica e cataloga tutti i file presenti.

 Gestisce le operazioni sui file, offrendo primitive e utility di gestione.

 Assegna l’uso dei file ai processi (attuando anche meccanismi di protezione).

 Gestisce l’allocazione delle aree su disco.

(5)

Vantaggi del file system

• Il compito di leggere e scrivere sui dispositivi

potrebbe essere affidato ai processi, ma la gestione da parte del S.O. tramite il file system riduce i

problemi per i processi e permette di controllare la protezione e di gestire la condivisione.

• Inoltre si solleva l’utente dalla necessità di muovere esplicitamente i dati tra la memoria principale e la memoria secondaria e dal dover gestire i dati in modo diverso, a seconda del supporto su cui sono fisicamente memorizzati.

(6)

Protezione

• Il file system offre meccanismi di protezione per stabilire chi può effettuare operazioni sui file e quali.

• Solitamente chi crea il file viene considerato il proprietario e può stabilire quali operazioni possono essere effettuate dagli altri utenti.

• Ogni volta che viene richiesta un’operazione sul file il file system controlla se l’operazione è

permessa.

(7)

Condivisione

• Più processi possono aprire sessioni contemporanee su uno stesso file: questo potrebbe causare

situazioni di inconsistenza dei dati.

• Per evitare ciò il file system gestisce gli accessi

contemporanei: un blocco può essere condiviso in fase di lettura, ma non se sono previste operazioni di aggiornamento.

• Questo tipo di gestione può portare a situazioni di stallo, che viene risolto predisponendo gli

aggiornamenti in un ordine opportuno.

(8)

I file

^{- 1}

I file sono l’astrazione logica delle risorse che il S.O.

definisce per conservare informazioni in modo permanente su memoria di massa.

I dati contenuti in un file sono correlati e trattati unitariamente.

Dal punto di vista dell’utente un file è la più piccola porzione di informazione logica che può essere

memorizzata in memoria di massa, in altre parole i dati non possono essere scritti in memoria

secondaria se non vengono inclusi in un file.

I file

^{- 1}

(9)

I file

^{- 2}

In generale un file è una sequenza di bit, byte, righe o record il cui significato è definito dal creatore del file e dall’utente.

I file possono contenere informazioni di vario tipo:

Programmi (sorgente, oggetto, eseguibili)

Dati (l’estensione indica l’applicazione che li ha generati)

Speciali (file di sistema o astrazione di dispositivi)

Directory (descrivono altri file)

(10)

Attributi dei file

Ogni file è individuato nel file system da un nome

simbolico ed è caratterizzato da un insieme di attributi.

Solitamente:

 tipo: stabilisce l’appartenenza ad una classe (eseguibili, batch, testo, etc)

 indirizzo: puntatore alla memoria secondaria

 dimensione: numero di byte di cui è composto il file

 data e ora: di creazione e/o di modifica In S.O. multiutente anche:

 creatore e possessore (anche distinti)

 protezione: diritti di accesso al file per ciascun utente

(11)

Livelli di astrazione

^-1

La struttura dei dati all’interno di un file può essere vista da tre livelli di astrazione distinti:

• Livello utente

– Il programma utente associa significato al contenuto del file

• Livello di struttura logica

– I dati grezzi (non interpretati) sono raggruppati dal S.O. in strutture logiche per facilitarne il trattamento

• Livello di struttura fisica

– Il S.O. mappa le strutture logiche sulle strutture fisiche della memoria secondaria disponibile (es. blocchi su disco)

(13)

Livelli di astrazione

^{- 2}

Livello Oggetti gestiti Chiamate tipiche (primitive)

Utenti interattivi

(linguaggio dei comandi) FILE COPY, DELETE,

RENAME

Programmi applicativi e di sistema (chiamate al

sistema operativo)

PARTI DI FILE (indirizzamento logico all’interno

del file)

OPEN, CLOSE, SEEK, READ, WRITE

Device driver

SETTORI (cilindro, testina,

settore)

OPEN, CLOSE, SEEK, READ, WRITE

(14)

Struttura logica vs Struttura fisica

Sulle memorie di massa i dati sono raggruppati in modo da formare delle strutture, detti record fisici o blocchi, sulle quali è possibile compiere le operazioni di lettura/scrittura.

In pratica il record fisico rappresenta l’unità di informazione indivisibile che può essere trasferita dalla memoria di

massa a quella centrale con una sola operazione di I/O.

Tale unità dipende dalla struttura HW del sistema e, in

generale, non coincide con l’unità logica di informazione (record logico).

È quindi possibile che un record fisico contenga più record logici o che un record logico richieda più record fisici per la sua registrazione.

(15)

Compiti del file system

Realizza l’indipendenza dai dispositivi, nascondendo la collocazione dei file e la loro eventuale allocazione su più dispositivi

quindi

i processi che devono accedere ai file in lettura e/o scrittura non devono preoccuparsi di sapere dove questi sono

allocati fisicamente: è sufficiente che usino primitive come read(..) o write(..).

Fa corrispondere un modello logico del file a una struttura fisica sul supporto di memoria e stabilisce i metodi di

memorizzazione e di accesso.

(16)

Integrità dei dati e affidabilità

• Il file system deve garantire l’affidabilità dei file con meccanismi di verifica e ripristino della

consistenza.

• Le cause principali di inconsistenza dei dati sono l’immissione di dati errati e l’interruzione

improvvisa di programmi di elaborazione.

Procedure di validazione dei dati inseriti

Procedure di recovery e transazioni

(17)

Struttura logica di un file

^{- 1}

• Le possibili strutture logiche di un file sono:

– A sequenza di byte (byte stream) – A record di lunghezza fissa

– A record di lunghezza variabile

(18)

Struttura logica di un file

^{- 2}

• Sequenza di byte (byte stream)

– La struttura logica più rudimentale e flessibile

• la scelta di UNIX (→Linux) e Windows

– Il programma utente sa come dare significato al contenuto informativo del file

• minimo sforzo per il S/O

– L’accesso ai dati utilizza un puntatore relativo all’inizio del file

– Lettura e scrittura operano a blocchi di byte

(19)

Struttura logica di un file

^{- 3}

• Record di lunghezza fissa

– È difficile stimare a priori la lunghezza dei record – Gli spazi non utilizzati sono riempiti da caratteri

speciali (es. NULL o SPACE)

– L’accesso ai dati può essere diretto o sequenziale e utilizza un puntatore al record corrente

– Lettura e scrittura operano su record singoli

– Scelta obsoleta e legata a specifiche limitazioni dell’architettura di sistema

(20)

Struttura logica di un file

^{- 4}

• Record di lunghezza variabile

– Struttura interna di ogni record descritta e

identificata univocamente da una chiave (key) posta in posizione fissa e nota nel record

– Chiavi raccolte in una tabella a sé stante (file indice), ordinata per chiave, contenente anche i puntatori all’inizio del record

– Accesso ai dati per chiave di record

(21)

Struttura logica di un file

^{- 5}

• Record di lunghezza variabile

– L’accesso a un record avviene a partire dal file indice tramite il campo chiave

File indice

Ab..

Be..

Bo..

Ma...

Zi...

Ab..

Be..

Bo..

Ma...

Zi...

File dati

(22)

Metodo di accesso

Per metodo di accesso si intende la modalità secondo cui è possibile accedere a un singolo elemento (record logico) del file.

 Accesso sequenziale: per accedere ad un determinato record è necessario scorrere sequenzialmente quelli che lo precedono

• Si applica a file di record di lunghezza variabile

 Accesso diretto: un puntatore consente di posizionarsi direttamente sull’elemento desiderato

• Si applica a file di record di lunghezza fissa

(23)

Accesso sequenziale

• Scansione dall’inizio del file di tutti i record fino a quello cercato

1 2 3 4

5 Carattere prefissato

(es.CR) per indicare la fine del record

Per leggere il record 5 è necessario leggere prima tutti i byte dei record 1, 2, 3, 4

(24)

Accesso diretto

• Accesso diretto (random) al record cercato

1 2 3 4 5

Lunghezza prefissata

Per leggere il record 5, sapendo la lunghezza dei record, ci si può posizionare direttamente sul suo primo byte

(25)

Descrittore del file

È la struttura dati che contiene gli attributi di un file, cioè tutte le informazioni necessarie per la gestione del file e per l’accesso al suo

contenuto.

Deve essere memorizzato in modo permanente.

Il descrittore di ogni file viene inserito come record nella directory.

(26)

Directory simbolica

• La directory simbolica contiene, per ogni file, il nome simbolico e un puntatore al record della directory di base in cui sono contenute tutte le informazioni riguardanti il file. La directory di base contiene invece l’insieme completo delle informazioni.

DIRECTORY SIMBOLICA

NUM ID-FILE ID

dove:

NUM = num. progressivo ID-FILE = identificativo file

ID = identificativo del file nella directory di base

(30)

Directory di base

DIRECTORY DI BASE

ID-FILE LUNG-REC N-REC INDIRIZZO ACCESSO CREAZIONE MODIFICA ID

Solo la directory simbolica è caricata in memoria centrale:

attraverso l’identificativo (ID) sono reperite tutte le informazioni presenti nella directory di base.

(31)

Tipi di directory

^{- 1}

Struttura gerarchica a N livelli

• La modalità più frequente è quella in cui le directory hanno una struttura ad albero:

esistono più file directory e ogni descrittore può contenere il nome di un file o di

un’altra directory (sottodirectory), partendo da una directory principale (root).

(32)

Tipi di directory

^{- 2}

(33)

Tipi di directory

^{- 3}

• Tale struttura agevola i meccanismi di ricerca di un file, poiché ogni directory contiene un numero limitato di file

• Permette di avere file con lo stesso nome in directory diverse

• Il file system rende disponibili le operazioni di gestione delle directory (creazione,

cancellazione..) e aggiorna le directory

quando vengono eseguite operazioni sui file.

(34)

Operazione di I/O su file

^{- 1}

• Una operazione di I/O su file genera una

interruzione che richiede l’intervento del sistema operativo.

• Una generica richiesta di operazione su un record del file può avere la seguente sintassi:

leggi (file, destinazione, i)

nome del file su cui eseguire l’operazione

variabile in cui memorizzare il record

posizione logica del record nel file

(35)

Cosa accade dal momento in cui al File System perviene la richiesta di lettura?

Vengono effettuate nell’ordine le seguenti operazioni:

1. Scansione dell’albero delle directories per trovare la directory del file a cui è richiesto l’accesso

2. Estrazione dal descrittore delle informazioni relative al file cercato. Una volta reperito, il descrittore viene copiato in RAM nella cosiddetta tabella dei file

aperti, in modo da rendere più veloce l’elaborazione del file.

L’allocazione del descrittore nella tabella dei file

aperti corrisponde all’operazione di apertura del file.

Operazione di I/O su file

^{- 2}

(36)

3. Verifica dei controlli d’accesso, che possono essere di tipo statico (determinano se il processo ha il

permesso di effettuare l’operazione richiesta sul file) o dinamico (verificano se ci sono altri processi che stanno usando in modo condiviso il file e stanno eseguendo operazioni che impediscono al momento di procedere)

4. Calcolo dell’indirizzo logico del record all’interno del file (espresso in byte, come se il file fosse un byte stream), utilizzando le informazioni sul tipo di

organizzazione e la lunghezza del record. La richiesta di operare su un record viene quindi trattata come

richiesta di accesso a uno o più byte.

Operazione di I/O su file

^{- 3}

(37)

Operazione di I/O su file

^{- 4}

Esempio:

Se l’organizzazione di un file fosse a record di lunghezza fissa, la dimensione di ciascun record LR = 512 bytes e l’accesso fosse diretto, si avrebbe che la richiesta di

accedere al 3° record (NR) si trasformerebbe nella richiesta di accedere al byte logico di indirizzo

Ind = (NR –1) * LR = (3 – 1) * 512 = 1024

LR

record 1 record 2 record 3

(38)

5. Calcolo dell’indirizzo fisico: a partire dall’indirizzo logico, il file system fisico individua il numero del blocco che contiene il record richiesto, in base alla lunghezza dei blocchi, e l’indirizzo relativo del

record all’interno del blocco.

Il calcolo del n. del blocco è ancora indipendente dal tipo e dalle caratteristiche della periferica e dalla

modalità di allocazione dello spazio sulla periferica.

6. Interfaccia con la gestione dei dispositivi:

l’esecuzione vera e propria dell’operazione richiede l’intervento del gestore dei dispositivi e l’utilizzo del driver della periferica.

Operazione di I/O su file

^{- 5}

(39)

Operazione di I/O su file

^{- 6}

• Utilizzando il driver della periferica si effettua la

conversione del numero di blocco nell’indirizzo fisico

relativo alla periferica (per es. numero di cilindro, testina e settore su un disco).

• Viene generato un processo di I/O che al termine genera una interruzione.

Buffer di I/O

lettura di un blocco

(40)

File system fisico

Ogni dispositivo che permette la memorizzazione dei file contiene anche un descrittore del sistema di archiviazione, una struttura con le informazioni sul modo in cui è organizzata la memorizzazione dei dati sul dispositivo.

Le informazioni contenute nel descrittore del sistema di archiviazione dipendono dal tipo di dispositivo e dalla tecnica di allocazione utilizzata.

(41)

Descrittore del sistema di archiviazione

^{- 1}

Il descrittore del sistema di archiviazione su disco può contenere:

– L’etichetta del disco

– Il valore della lunghezza massima dei file che si possono memorizzare

– Informazioni sulla tabella dei descrittori dei file

– Informazioni sulle tabelle usate per l’assegnazione dei blocchi ai file

– L’indicazione del primo blocco utilizzato per i file e il numero di blocchi presenti

(42)

Descrittore del sistema di archiviazione

^{- 2}

Dopo il descrittore del sistema di archiviazione si trovano:

– La mappa dei descrittori di file con lo stato di assegnazione dei descrittori di file

– La tabella dei descrittori

– la FAT con le informazioni dei blocchi ai file o la mappa dei blocchi che indica la disponibilità dei blocchi

Al termine delle strutture di dati del file system si trovano i blocchi disponibili per i file.

(43)

Allocazione dello spazio su disco

L’allocazione dello spazio su disco avviene per blocchi, secondo tre possibili tecniche:

allocazione contigua, allocazione concatenata, allocazione indicizzata.

In ogni caso bisogna usare delle informazioni aggiuntive per conoscere quali blocchi sono assegnati ad ogni file.

(44)

Allocazione contigua

^{- 1}

Ogni file è mappato su un insieme di blocchi fisicamente contigui.

Vantaggi:

– basso costo della ricerca di un blocco

– possibilità di accesso sequenziale e diretto

Svantaggi:

– individuazione dello spazio libero per l’allocazione di un nuovo file – frammentazione esterna: a mano a mano che si riempie il disco

rimangono zone contigue non utilizzabili – Ricompattazione periodica molto costosa

(45)

Allocazione contigua

^{- 2}

file inizio lunghezza

count 0 2

f 6 2

tr 14 3

mail 19 6

list 28 4

Allocazione concatenata

^{- 1}

I blocchi sui quali viene mappato il file sono organizzati in una lista concatenata: ciascun blocco di file deve contenere il puntatore al blocco successivo (o fine lista).

Vantaggi:

– non c’è frammentazione esterna

– Non si deve dichiarare la dimensione del file quando lo si crea

Svantaggi:

– possibilità di errore se un link viene danneggiato – maggiore occupazione (spazio per i puntatori)

– costo della ricerca di un blocco (continui accessi al disco)

– l’accesso sequenziale resta semplice, quello diretto diventa oneroso

(47)

Allocazione concatenata

^{- 2}

Allocazione concatenata – FAT -

¹

Un’importante variazione al metodo di

allocazione concatenata è l’uso della tabella di allocazione dei file (File Allocation Table o FAT), usato dai sistemi operativi MS-DOS.

Si usa una tabella per ogni partizione formata da tanti elementi quanti sono i blocchi del disco; ogni elemento può contenere un

puntatore al blocco successivo se il blocco appartiene a un file, o una indicazione che il blocco è libero.

(49)

Allocazione concatenata – FAT -

²

Il numero del primo blocco del file viene memorizzato nel descrittore del file e consente l’accesso al resto del file.

La catena di puntatori viene scorsa solo all’interno della tabella, che può essere

copiata in memoria centrale per rendere più veloce l’accesso.

(50)

FAT

^{- 1}

Si tratta di una tecnica di allocazione

efficiente perché la ricerca di un blocco

avviene accedendo alle informazioni riunite in un’unica tabella piuttosto che dislocate nei vari blocchi sparsi sul disco.

Vantaggi:

• Non comporta frammentazione esterna

• Consente accesso sequenziale e diretto

(51)

FAT

^{- 2}

#

# 4

# 5 6 EOF

# 0

1 2 3 4 5 6 7

0 1

3

7

test …. 2

nome blocco di partenza

descrittore del file

(n. blocchi del disco – 1)

(52)

Se il sistema operativo non supporta la FAT si

ricorre all’allocazione indicizzata, che riunisce i puntatori ai blocchi in strutture apposite (l’intero blocco contiene quindi solo dati)

Ci sono due strategie di organizzazione – blocco indice

– nodo indice (i-node) Vantaggi:

• Non comporta frammentazione esterna

• Consente accesso sequenziale e diretto

Blocchi indice

Allocazione indicizzata

(53)

Ogni file ha il proprio blocco indice, che è un array di indirizzi dei blocchi su disco.

L’i-esimo elemento nel blocco indice punta all’i- esimo blocco del file; la directory contiene

l’indirizzo del blocco indice.

Svantaggi:spazio sprecato dal blocco indice nel caso in cui un file sia formato da pochi blocchi.

Si pone la questione di quanto debba essere grande un blocco indice.

Blocchi indice

^{- 1}

(54)

Blocchi indice

^{- 2}

Esempio di allocazione indicizzata con

blocchi indice

(55)

Nodi indice (Unix → Linux)

Si usa una struttura indice (i-node) per ogni file, con gli attributi del file e i puntatori ai suoi blocchi

– L’i-node è contenuto in un blocco dedicato – Linux usa i-node da 64 bytes

In RAM una tabella di i-node per i soli file in uso

Un i-node contiene un numero limitato di puntatori a blocchi → più livelli di puntatori (punt. indiretti)

(56)

i-node

Esempio di allocazione

indicizzata con nodi indice (i-node)

(57)

Blocchi liberi

Il file system deve inoltre poter sempre individuare i blocchi liberi da assegnare ad un nuovo file: per questo utilizza tecniche che ne agevolino la ricerca

– blocchi liberi concatenati in una lista

– tabella di puntatori ai blocchi liberi organizzati a lista – mappa dei blocchi liberi (ogni puntatore individua il

primo blocco di un’area libera seguito dal n. di blocchi liberi contigui)

– bit map: si usa una sequenza di bit, uno per blocco, che indica se il blocco corrispondente è libero o occupato