Sistemi Operativi

Modulo 9: File System

Renzo Davoli

Alberto Montresor

Copyright © 2002-2005 Renzo Davoli, Alberto Montresor

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license can be found at: http://www.gnu.org/licenses/fdl.html#TOC1

Sezione 1

1. Visione utente

Introduzione

I computer possono utilizzare diversi media per registrare in modo permanente le informazioni

esempi: dischi rigidi, floppy, nastri, dischi ottici

ognuno di questi media ha caratteristiche fisiche diverse

Compito del file system è quello di astrarre la complessità di utilizzo dei diversi media proponendo una interfaccia per i sistemi di memorizzazione:

comune

efficiente

conveniente da usare

Introduzione

Dal punto di vista dell’utente, un file system è composto da due elementi:

file: unità logica di memorizzazione

directory: un insieme di informazioni per organizzare e fornire informazioni sui file che compongono un file system

Il concetto di file

è l'entità atomica di assegnazione/gestione della memoria secondaria

è una collezione di informazioni correlate

fornisce una vista logica uniforme ad informazioni correlate

Attributi dei file

Nome:

stringa di caratteri che permette agli utenti ed al sistema operativo di identificare un particolare file nel file system

alcuni sistemi differenziano fra caratteri maiusc./minusc., altri no

Tipo:

necessario in alcuni sistemi per identificare il tipo di file

Locazione e dimensione

informazioni sul posizionamento del file in memoria secondaria

Data e ora:

informazioni relative al tempo di creazione ed ultima modifica del file

Attributi dei file

Informazioni sulla proprietà

utenti, gruppi, etc.

utilizzato per accounting e autorizzazione

Attributi di protezione:

informazioni di accesso per verificare chi è autorizzato a eseguire operazioni sui file

Altri attributi

flag (sistema, archivio, hidden, etc.)

informazioni di locking

etc.

Tipi di file

A seconda della struttura interna

senza formato (stringa di byte): file testo,

con formato: file di record, file di database, a.out,...

A seconda del contenuto

ASCII/binario (visualizzabile o no, 7/8 bit)

sorgente, oggetto, ......

eseguibile (oggetto attivo)

Tipi di file

Alcuni S.O. supportano e riconoscono diversi tipi di file

conoscendo il tipo del file, il s.o. può evitare alcuni errori comuni, quali ad esempio stampare un file eseguibile

Esistono tre tecniche principali per identificare il tipo di un file

meccanismo delle estensioni

utilizzo di un attributo "tipo" associato al file nella directory

magic number

Tipi di file

MS-DOS:

nome del file 8+3 (nome + estensione)

riconoscimento delle estensioni .COM, .EXE, .BAT

Windows 9x / NT

nomi/estensioni di lunghezza variabile

riconoscimento delle estensioni .COM, .EXE, .BAT

associazione estensione / programma

Mac OS

programma creatore del file come attributo

Unix/Linux

magic number + estensione + euristica (UNIX).

Tipi di file: ulteriori distinzioni

In un file system, si distingue fra:

file regolari

directory

file di sistema per mantenere la struttura del file system

file speciali a blocchi

utilizzati per modellare dispositivi di I/O come i dischi

file speciali a caratteri

utilizzati per modellare device di I/O seriali come terminali, stampanti e reti

altri file speciali

ad es., pipe

Struttura dei file

I file possono essere strutturati in molti modi:

sequenze di byte

sequenze di record logici

file indicizzati (struttura ad albero)

1.

2.

3.

Struttura dei file

I sistemi operativi possono attuare diverse scelte nella gestione della struttura dei file:

scelta minimale

i file sono considerati semplici stringhe di byte, a parte i file eseguibili il cui formato è dettato dal s.o.

e.g., UNIX e MS-DOS

parte strutturata/parte a scelta dell'utente

e.g. Macintosh (resource fork / data fork)

diversi tipi di file predefiniti

e.g., VMS, MVS

Supporto alla struttura dei file

E’ un trade-off:

più formati:

codice di sistema più ingombrante

incompatibilità di programmi (accesso a file di formato differente

MA gestione efficiente e non duplicata per i formati speciali

meno formati

codice di sistema più snello

Struttura interna dei file

La struttura fisica è divisa in blocchi (multipli del settore) detti anche record fisici.

Per una gestione efficiente occorre risolvere il problema del packing dei record logici nei record fisici

record fisico (multiplo di blocco, unità di interscambio col livello di libreria)

record logico (unità di informazione vista dal livello applicativo)

blocchi

record logici

Esempio di record fisico scelto in modo inopportuno

Cambiando il livello di bloccaggio si limita lo spreco di memoria
secondaria

Metodi di accesso

Sequenziale

read, write

nastri

Ad accesso diretto

read pos, write pos (oppure operazione seek)

dischi

Indicizzato

read key, write key

database

Metodi di accesso: indice

Indice

è una tabella di corrispondenza chiave-posizione

Può essere memorizzato:

in memoria: metodo efficiente ma dispendioso

su disco

Esempio

casa	10

mare	25

sole	35

abete	44

bici	12

casa	33

bugia	xxx 38 xx

caio	iii 00 kkk

cane	iil 99 ooo

casa	ddd 33 ddd

Operazioni sui file

Operazioni fondamentali sui file

creazione

apertura/chiusura

lettura/scrittura/append

posizionamento

cancellazione

troncamento

lettura/scrittura attributi

Operazioni sui file

L'API (interfaccia per la programmazione) relativa alle operazioni su file è basata sulle operazioni open/close

i file devono essere “aperti” prima di effettuare operazioni e “chiusi” al termine.

L’astrazione relativa all’apertura/chiusura dei file è utile per

mantenere le strutture dati di accesso al file

controllare le modalità di accesso e gestire gli accessi concorrenti

definire un descrittore per le operazioni di accesso ai dati

Directory

L'organizzazione dei file system

è basata sul concetto di directory, che fornisce un'astrazione per un'insieme di file

in molti sistemi, le directory sono file (speciali)

Operazioni definite sulle directory

creazione

cancellazione

apertura di una directory

chiusura di una directory

lettura di una directory

rinominazione

link/unlink

Directory

Struttura di una directory

a livello singolo

a due livelli

ad albero

a grafo aciclico

a grafo

Directory strutturata ad albero

usr

home

bin

bin

include

lib

ls

cat

X11R6

lost+found

montreso

renzo

risultati
scritto

prossimo
compito

...

...

...

...

...

...

...

...

...

...

...

...

Directory strutturate a grafo aciclico

Nella struttura ad albero:

ogni file è contenuto in una directory univoca

E' anche possibile considerare grafi diversi dagli alberi

un file può essere contenuto in due o più directory

esiste un'unica copia del file suddetto:

ogni modifica al file è visibile in entrambe le directory

La struttura risultante prende il nome di
grafo diretto aciclico (DAG)

Directory strutturata a grafo aciclico

usr

home

bin

bin

include

lib

ls

cat

X11R6

lost+found

montreso

renzo

risultati
scritto

prossimo
compito

...

...

...

...

...

...

...

...

...

...

scritto
13-10

next
midterm

Semantica della coerenza

In un sistema operativo multitasking, i processi accedono ai file indipendentemente

Come vengono viste le modifiche ai file da parte dei vari processi?

In UNIX

le modifiche al contenuto di un file aperto vengono rese visibili agli altri processi immediatamente.

esistono due tipi di condivisione del file:

condivisione del puntatore alla posizione corrente nel file
(condivisione ottenibile con fork)

condivisione con distinti puntatori alla posizione corrente.

Sezione 2

2. Visione implementatore

Implementazione del file system

Problemi da tenere in considerazione

organizzazione di un disco

allocazione dello spazio in blocchi

gestione spazio libero

implementazione delle directory

tecniche per ottimizzare le prestazioni

tecniche per garantire la coerenza

Organizzazione del disco

Struttura di un disco

un disco può essere diviso in una o più partizioni, porzioni indipendenti del disco che possono ospitare file system distinti

il primo settore dei dischi è il cosiddetto master boot record (MBR)

è utilizzato per fare il boot del sistema

contiene la partition table (tabella delle partizioni)

contiene l'indicazione della partizione attiva

al boot, il MBR viene letto ed eseguito

MBR

Partizione 1

Partizione 2

Partizione 3

Struttura del disco

Organizzazione del disco

Struttura di una partizione

ogni partizione inizia con un boot block

il MBR carica il boot block della partizione attiva e lo esegue

il boot block carica il sistema operativo e lo esegue

l'organizzazione del resto della partizione dipende dal file system

Boot

Block

Superblock

Gestione

spazio libero

Gestione

Spazio occ.

Root

dir

File e directory

Struttura di una partizione

Organizzazione del disco

In generale

superblock

contiene informazioni sul tipo di file system e sui parametri fondamentali della sua organizzazione

tabelle per la gestione dello spazio libero

struttura dati contenente informazioni sui blocchi liberi

tabelle per la gestione dello spazio occupato

contiene informazioni sui file presenti nel sistema

non presente in tutti i file system

root dir

directory radice (del file system)

file e directory

Allocazione

Problema

l’hardware e il driver del disco forniscono accesso al disco visto come un insieme di blocchi dati di dimensione fissa.

partendo da questa struttura come si implementa l’astrazione di file?

in altre parole: come vengono scelti i blocchi dati da utilizzare per un file e come questi blocchi dati vengono collegati assieme a formare una struttura unica

Questo è il problema dell'allocazione

Allocazione contigua

Descrizione

i file sono memorizzati in sequenze
contigue di blocchi di dischi

Vantaggi

non è necessario utilizzare strutture
dati per collegare i blocchi

l'accesso sequenziale è efficiente

blocchi contigui non necessitano
operazioni di seek

l'accesso diretto è efficiente

block= offset/blocksize;

pos= offset%blocksize;

0- 5

6-11

12-17

18-23

24-29

30-35

36-41

Name

Start

Size

a

0

4

b

13

11

c

30

3

d

33

3

directory

Allocazione contigua

Svantaggi

si ripropongono tutte le problematiche dell’allocazione contigua in memoria centrale

frammentazione esterna

politica di scelta dell’area di blocchi liberi da usare per
allocare spazio per un file: first fit, best fit, worst fit....

inoltre:

i file non possono crescere!

Ma esiste almeno un tipo di file system in cui viene utilizzata allocazione contigua....

Allocazione concatenata

Descrizione

ogni file è costituito da un lista concatenata di blocchi.

ogni blocco contiene un puntatore al blocco successivo

il descrittore del file contiene i puntatori al primo e all’ultimo elemento della lista

Name

Start

End

a

0

4

directory

3

10

7

nil

6

nil

4

5

b

1

6

0-5

6-11

spazio allocabile

Allocazione concatenata

Vantaggi

risolve il problema della frammentazione esterna

l’accesso sequenziale o in “append mode" è efficiente

Svantaggi

l’accesso diretto è inefficiente

progressivamente l’efficienza globale del file system degrada
(i blocchi sono disseminati nel disco, aumenta il n. di seek)

la dimensione utile di un blocco non è una potenza di due

se il blocco è piccolo (512 byte) l’overhead per i puntatori può essere rilevante

Allocazione concatenata

Minimizzare l’overhead dovuto ai puntatori

i blocchi vengono riuniti in cluster (contenenti 4, 8, 16 blocchi) e vengono allocati in modo indivisibile

Vantaggi

la percentuale di spazio utilizzato per i puntatori diminuisce

Svantaggi

aumenta lo spazio sprecato per la frammentazione interna

Allocazione basata su FAT

Descrizione

invece di utilizzare parte del blocco dati per
contenere il puntatore al blocco successivo
si crea una tabella unica con un elemento
per blocco (o per cluster)

0-5

6-11

Name

Start

End

a

0

4

directory

b

1

6

spazio allocabile

3

10

7

nil

6

nil

4

5

FAT

Allocazione basata su FAT

Vantaggi

i blocchi dati sono interamente dedicati... ai dati

Svantaggi

la scansione richiede anche la lettura della FAT, aumentando così il numero di accessi al disco.

Vantaggi

è possibile fare caching in memoria dei blocchi FAT

l'accesso diretto diventa così più efficiente, in quanto la lista di puntatori può essere seguita in memoria

E’ il metodo usato da DOS

Allocazione indicizzata

Descrizione

l'elenco dei blocchi che compongono un file viene memorizzato in un blocco (o area) indice

per accedere ad un file, si carica in memoria la sua area indice e si utilizzano i puntatori contenuti

0, 3,
7, 4

2, 10,

5, 6

0-5

6-11

Name

Index

a

2

directory

b

8

spazio allocabile

Allocazione indicizzata

Vantaggi

risolve (come l’allocazione concatenata) il problema della frammentazione esterna.

è efficiente per l’accesso diretto

il blocco indice deve essere caricato in memoria solo quando il file è aperto

Svantaggi

la dimensione del blocco indice determina l’ampiezza massima del file

utilizzare blocchi indici troppo grandi comporta un notevole spreco di spazio

Come risolvere il trade-off?

Allocazione indicizzata - Possibili soluzioni

Concatenazione di blocchi indice

l’ultimo elemento del blocco indice non punta al blocco dati ma al blocco indice successivo

si ripropone il problema per l’accesso diretto a file di grandi dimensioni

Name

Index

a

0

directory

2, 3,
4, 9

7, 10,
11, nil

0-5

6-11

spazio allocabile

1, 5,
6, nil

b

8

Allocazione indicizzata - Possibili soluzioni

Indice multilivello

si utilizza un blocco indice dei blocchi indice

degradano le prestazioni, in quanto richiede un maggior numero di accessi

Name

Index

a

0

directory

1,2,
nil,nil

10,11,

nil,nil

0-5

6-11

spazio allocabile

3,4,
7,8

Allocazione indicizzata e UNIX

In UNIX

ogni file è associato ad un i-node (index node)

un i-node è una struttura dati contenente gli attributi del file, e un indice di blocchi diretti e indiretti, secondo uno schema misto

I-node

Attributes

Direct
blocks

Double indirect

Single indirect

Triple indirect

Data

Data

.

.

.

.

.

.

Index

Data

Data

.

.

.

.

.

.

Index

Index

Index

.

.

.

Data

Data

.

.

.

.

.

.

Allocazione e performance

Lo schema UNIX

garantisce buone performance nel caso di accesso sequenziale

file brevi sono acceduti più velocemente e occupano meno memoria

Ulteriori miglioramenti

pre-caricamento (per esempio nell’allocazione concatenata fornisce buone prestazioni per l’accesso sequenziale).

combinazione dell’allocazione contigua e indicizzata

contigua per piccoli file ove possibile

indicizzata per grandi file

Gestione spazio libero - Mappa di bit

Descrizione

ad ogni blocco corrisponde un bit in una bitmap

i blocchi liberi sono associati ad un bit di valore 0, i blocchi occupati sono associati ad un bit di valore 1

f1

f2

f3

1

1

1

1

1

0

0

1

1

1

1

1

0

0

0

0

0

1

1

1

0

0

0

0

0

1

2

3

4

5

6

7

8

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

Gestione spazio libero - Mappa di bit

Vantaggi

semplice, è possibile selezionare aree contigue

Svantaggi

la memorizzazione del vettore	può richiedere molto spazio

Nota:

Intel 80386 e succ. Motorola 68020 e succ. hanno istruzioni per trovare l’offset del primo bit acceso/spento in una word

Gestione spazio libero - Lista concatenata

Descrizione

i blocchi liberi vengono mantenuti in una lista
concatenata

si integra perfettamente con il metodo FAT
per l'allocazione delle aree libere

0-5

6-11

Name

Start

End

a

0

4

directory

b

1

6

spazio allocabile

3

10

7

nil

6

nil

4

5

FAT

Free list

Gestione spazio libero - Lista concatenata

Vantaggi

richiede poco spazio in memoria centrale

Svantaggi

l’allocazione di un’area di ampie dimensioni è costosa

l’allocazione di aree libere contigue è molto difficoltosa

Gestione spazio libero - Lista concatenata (blocchi)

Descrizione

è costituita da una lista concatenata di blocchi contenenti puntatori a blocchi liberi

12

35

23

32

33

45

22

11

32

55

27

34

53

65

28

19

39

59

97

94

93

95

08

nil

Free list

Gestione spazio libero - Lista concatenata (blocchi)

Vantaggi

ad ogni istante, è sufficiente mantenere in memoria semplicemente un blocco contenente elementi liberi

non è necessario utilizzare una struttura a dati a parte;
i blocchi contenenti elenchi di blocchi liberi possono essere mantenuti all'interno dei blocchi liberi stessi

Svantaggi

l’allocazione di un’area di ampie dimensioni è costosa

l’allocazione di aree libere contigue è molto difficoltosa

Gestione spazio libero: un po' di conti

Premesse

blocchi: 1K

dimensione partizione: 16GB

Mappa di bit

224 bit = 221 byte = 2048 blocchi = 2MB nella bitmap

Lista concatenata (FAT)

224 puntatori = 224*3 byte = 48MB nella FAT

Lista concatenata (blocchi)

spazio occupato nei blocchi liberi

Gestione spazio libero: un po' di conti

Scegliere la dimensione di un cluster

cluster grandi: velocità di lettura alta, frammentazione interna

cluster piccoli: minore frammentazione, velocità più bassa

dati ottenuti su file system reali, lunghezza mediana: 2Kb

© 1995-2002 Andrew S. Tanenbaum

Block size

Implementazione delle directory

Una directory

è un file speciale contenente informazioni sui file contenuti nella directory

una directory è suddivisa in un certo numero di directory entry

ogni directory entry deve permettere di accedere a tutte le informazioni necessarie per gestire il file

nome

attributi

informazioni di allocazione

Scelte implementative da considerare

attributi contenuti nelle directory entry oppure nell'i-node

lista lineare (array) vs hash table

Implementazione delle directory

Informazioni nelle directory entry

la directory entry contiene tutte le
informazioni necessarie associate
ad un file

utilizzata da MS-DOS

Informazione negli i-node

le informazioni sono contenute
negli inode; una directory entry
contiene un indice di inode

utilizzata in UNIX

nome file

attributi

info allocaz.

nome file

attributi

info allocaz.

nome

i-node

nome

i-node

nome

i-node

nome

i-node

Implementazione delle directory

Problema della lunghezza dei nomi

memorizzare nomi a lunghezza variabile nelle directory comporta una serie di problemi

Lunghezza fissa

è il meccanismo più semplice...

...ma presenta un trade-off:

spazio riservato molto grande, spreco di memoria

spazio riservato troppo piccolo, nomi troppo brevi

Lunghezza variabile

la struttura dati diviene più complessa

due possibili esempi nel lucido successivo

Implementazione della directory

© 1995-2002 Andrew S. Tanenbaum

Implementazione delle directory

Lista lineare

semplice da implementare

inefficiente nel caso di directory di grandi dimensioni

Tabella hash

occorre stabilire la dimensione della tabella di hash e il metodo di gestione delle collisioni

la gestione può essere inefficiente se ci sono numerose collisioni

Directory strutturata a grafo aciclico

Due implementazioni possibili

link simbolici

hard link

Link simbolici

viene creato un tipo speciale di directory entry, che contiene un riferimento (sotto forma di cammino assoluto) al file in questione

quando viene fatto un riferimento al file

si cerca nella directory

si scopre che si tratta di un link

viene risolto il link
(ovvero, viene utilizzato il cammino assoluto registrato nel file

Directory strutturata a grafo aciclico

Hard link

le informazioni relative al file vengono copiate in entrambe le directory

non è necessario una doppia ricerca nel file system

è impossibile distinguere la copia dall’originale

Considerazioni

una struttura a grafo diretto aciclico è più flessibile di un albero, ma crea tutta una serie di problemi nuovi

non tutti i file system sono basati su DAG; esempio MS-DOS non li supporta

Hard-link

Implementazione

E' necessario utilizzare la tecnica degli i-node

gli i-node devono contenere un contatore di riferimenti

Owner= C

Count = 1

Directory di C

Owner= C

Count = 2

Directory di C

Owner= C

Count = 1

Directory di B

Directory di B

Performance

Tecniche per migliorare le performance dei file system

Cache dei blocchi

recentemente usati

Tabella dei descrittori

dei file aperti

Buffer di blocco

per DMA

Buffer di traccia

memoria centrale

controller

Tecniche per garantire la coerenza

Problema

i meccanismi di caching possono causare inconsistenze nel file system

ad esempio, a causa di interruzioni di corrente

il problema è particolarmente critico per zone del disco contenenti FAT, bitmap, i-node, directory

Due possibili soluzioni:

curare (file system checker)

fsck, scandisk

prevenire (journaling file system)

ext3, reiserfs

Controlli di coerenza

Controlli sui blocchi

si costruiscono due tabelle, inizialmente poste a 0, per ognuno dei blocchi presenti nel file system

tabella used[i]:

conta quante volte il blocco i è presente nell'elenco dei blocchi di un file

ottenuta esaminando tutti i file nel file system

se il blocco i è indicizzato da un file, si incrementa il contatore

tabella free[i]

conta quante volte il blocco i è presente nell'elenco dei blocchi liberi

ottenuta esaminando la lista dei blocchi liberi

oppure "copiando" la bitmap

Controlli di coerenza

free[i] + used[i] = 1

il blocco è correttamente elencato nel file system

free[i] + used[i] = 0

il blocco i è mancante, ovvero non è né libero né occupato

problema: nessun problema di coerenza, ma spazio sprecato

azione: riportare il blocco nell'elenco dei blocchi liberi

free[i] > 1

il blocco compare più volte nella lista dei blocchi liberi

problema: nessun problema di coerenza (per ora), ma
in futuro il blocco potrebbe essere assegnato due volte

azione: mantenere una sola istanza

Controlli di coerenza

free[i] = 1, used[i] > 1

il blocco è sia libero che occupato

problema: nessun problema di coerenza (per ora), ma
in futuro il blocco potrebbe essere assegnato due volte

azione: togliere il blocco dall'elenco dei blocchi liberi

used[i] > 1

il blocco è utilizzato da due o più file contemporaneamente

problema: forti problemi di coerenza nei file!

azione: cercare un nuovo blocco, copiare interamente il blocco presente, utilizzare la nuova copia per risolvere il problema

File system basati su log

File system basati su log (o di tipo journaling)

ogni aggiornamento al file system è trattato come una transazione

una transazione è un'operazione che viene eseguita in modo atomico: o tutto, o niente

File system basati su log

Log

tutte le transazioni vengono memorizzate in un log

una transazione

si considera completata (committed) quando è stata memorizzata nel log

tuttavia, il file system può non essere ancora aggiornato

periodicamente, le transazioni nel log vengono effettuate nel file system

alla modifica del file system, la transazione viene rimossa dal log

se il sistema si guasta, tutte le transazioni nel log devono
essere ripetute

Esempio: MS-DOS

Nomi file:

8+3 caratteri

indici di blocco a 12-16 bit (MS-DOS, W95), 32 bit (W98)

© 1995-2002 Andrew S. Tanenbaum

Esempio: MS-DOS

Esempio: Windows 9x

Bytes

Struttura di una directory entry "compatibile con MSDOS"

Esempio: UNIX V7

Esempio: UNIX V7

Alberto Montresor

2002-08-19T11:31:52

Alberto Montresor