1

Implementazione del File System nel Sistema Operativo Unix

(Bach: the Design of the Unix Operating System (cap: 4, da 5.1 a 5.7, 5.12)

2

Argomenti

• Index node (I-NODE)• gestione dei file mediante i-node• struttura dei file regolari e delle directory• accesso ai file mediante directory• layout di un file system Unix• strutture dati per la gestione dei file• system call per la gestione dei file• pipes

3

Punto di vista dell’utente:eseguibili

• File regolari: testo

……..

• Directory: Per organizzare il file system

• file speciali: device fisici (tty, disks, printers...)

• Pipe: (per la comunicazione fra processi)

Punto di vista del kernel:

i-nodes + data

4

INDEX-NODE (I-NODE)

• i-node: rappresentazione interna di un file unix (blocco indice)

• Gli i-node risiedono su disco

• vengono copiati in memoria se necessario (in-core i-node)

pippo

link: pluto file i-node

........

5

un i-node su disco contiene:

• Proprietario del file

• tipo di file

• diritti di accesso

• data di accesso (al file, all’i-node)

• numero di link al file (link counter)

• indirizzi dei blocchi che contengono il file

• dimensioni del file

6

un i-node in memoria contiene:

• numero dell’inode su disco

• file system di appartenenza

• numero di istanze attive del file (es. compilatore)

• STATO DELL’I-NODE:– locked?– c’é un processo in attesa?– l’i-node in memoria é stato modificato?– il file in memoria é stato modificato?

7

i-node su disco:

1 2 3 4 ... ...

in core i-node list

:::: :::: ::::

free list (cache di i-node inattivi)Se un file acceduto non é in memoria, il s.o. cerca prima l’i-node nellafree list

8

accesso ad un i-node (iget)

• Cerca l’i-node in memoria primaria

• se non lo trovi, copia l’i-node da disco su un i-node della free list (possibilmente libero)

• se free-list = empty ERRORE

• incrementa il numero di istanze attive del file (reference count + 1)

• se i-node = locked WAIT

• N.B.: un i-node é locked solo nella system call che lo usa.

9

rilascio un i-node (iput)

• Decrementa il numero di istanze attive del file (reference count := reference count -1)

• se reference count == 0– metti l’i-node nella free list– se l’i-node é stato modificato, copialo su disco– 3 casi:

• il file é cambiato

• l’access-time é cambiato

• il proprietario / i permessi sono cambiati.

• Questa gestione é valida per qualsiasi tipo di file

10

Struttura dei file regolari

• Ogni blocco del disco é identificato da un numero

• Ogni i-node contiene un elenco dei blocchi che memorizzano il file

• Unix adotta l’allocazione gerarchica indicizzata dei blocchi del file

11

i puntatori ai blocchi del file nell’i-nodedata blocks

1024 B

1024 B

direct 0

direct 1

direct 9

...

...

single indirect

double indir.

triple indirect

256 indirizzi

1024 B

1024 B

1024 B

1024 B

1024 B

(1KB x 10)+(1KB x 256)+(1KB x 2562)+(1KB x 2563)=16GB

12

Esempio

40960

2781

02

08

----

769

010

011

012

27203

data block

n. 4096

un puntatore a 0 non fa riferimento ad alcun blocco

data block n. 76

13

Allocazione gerarchica indicizzata

• I puntatori con valore 0 non allocano blocchi, e quindi non si spreca spazio

• L’accesso é molto veloce per i file piccoli (< 10k)• Si puó aumentare la dimensione dei blocchi per

velocizzare l’accesso ai file grandi ma AUMENTA LA FRAMMENTAZIONE INTERNA

• Si puó usare un blocco per contenere l’ultimo frammento di piú file (implementazione BSD)

• Si puó anche mettere l’i-node nel 1o blocco del file (per file piccolissimi si risparmia molto spazio)

14

Struttura delle directory (semplificata)

• DIRECTORY: file organizzato ad array. Ogni entry ha due campi di 2 e 14 byte

i-node number file name(216 file) (attualmente il file name puó essere lungo 512 chars)

• il kernel alloca spazio per ogni directory come per i file ordinari

• Solo il kernel puó scrivere direttamente in una directory, in modo da garantirne la struttura.

15

struttura della directory /etc

byte offset in directory

i-node number

symbolic name of files

0 83 .

16 2 ..

32 1798 init

48 1276 motd

64 0 crash

80 2114 passwd

... ... ...

16

Conversione da path-name a i-node

• L’accesso ai file avviene mediante path-names

• il kernel lavora con i-node

• Ci vuole un ALGORITMO di CONVERSIONE dal path-name all’i-node

• Directory di partenza:– root (/) : i-node memorizzato in una var. globale– current directory: i-node memorizzato nella u-area

17

Algoritmo di conversionealgoritm namei /* conversione pathname - inodeinput pathname;output inode;{if (pathname starts from root)

working inode = root inodeelse

working inode = current directory inode;while (there is no more pathname) {

read next path name;verify that working inode is of directory, and access permission ok;read directory (working inode);if (component matches an entry in directory (working inode)) {

get inode number for matched component;release working inode;working inode = inode of matched component}

else /* component not in directory */return (no inode)}

return (working inode);}

18

Struttura interna del File System

• boot block (blocco 0)

• super block (blocco 1)

• i-node list

• data blocks

boot block super block i-node list data blocks....

19

Super Block

Il super block é una struttura che contiene le informazioni fondamentali su file system:

• dimensioni del file system

• numero di blocchi liberi

• indice del 1o blocco libero della lista

• dimensioni della lista di i-node

• numero di i-node liberi

• indice del 1o i-node libero nella lista di i-node lib.

• flag per indicare che il super block é stato modif.

20

Altri tipi di file Unix

• PIPE:– file di contenuto transitorio– i dati possono essere letti solo nell’ordine in cui

sono stati scritti (FIFO)– dimensione massima: 10 blocchi (i 10 blocchi ad

indirizzamento diretto dell’i-node)– servono per le comunicazioni veloci tra processi

21

Altri tipi di file Unix

• File speciali:– corrispondo ai device fisici– l’i-node non fa riferimento a blocchi di memoria– una subroutine di sistema usa il device nel modo

giusto attraverso due valori registrati nell’i-node:• MAJOR NUMBER = tipo di device (tty, disco, ...)• MINOR NUMBER = numero di unitá del device

– i file speciali possono essere usati dai programmi come si usano i file regolari

22

Strutture dati per gestire i file aperti:

• User file table:– lista dei file aperti per processo (memoriz. nella u-area)– di solito ha 20 entry (max 20 file aperti contemp.)– le entry puntano alla File table

• File table:– lista dei file aperti globale– sempre in memoria centrale– ogni entry contiene l’offset della prossima read/write– ogni entry punta ad un in-core i-node

• Lista degli in-core i-node

23

System call “OPEN”

• fd = open(“file”,MODE) (fd: user file descriptor)

• il kernel:– recupera l’i-node di “file” e controlla i permessi– alloca una nuova entry nella FILE TABLE che punterá

all’in-core i-node– setta a zero l’offset del puntatore in lettura/scrittura– alloca una nuova entry nella USER FILE TABLE che

punta alla entry corrispondente nella FILE TABLE– il file descriptor fd ha come valore l’indice della entry

nella USER FILE TABLE

24

File tables del kernel

• un file aperto in scrittura (fd = 5), ed uno aperto sia in lettura (fd = 3) che in scrittura (fd = 4)

01234567...

user file table count read 1.... .........count rd-wrt 1... .......count write 1... ......

file table

count /etc/passwd 2.... .........count myfile 1... .......... ... ...... ......

in-core i-node list

25

Perché la open:

• L’utente usa un file system simbolico

• il s.o. lavora solo in termini di i-node e blocchi

• la open stabilisce un collegamento efficiente tra un file e la sua organizzazione fisica

• la “close”distrugge il collegamento

26

User file descriptor 0, 1, 2

• 0 = Standard Input (STDIN)

• 1 = Standard Output (STDOUT)

• 2 = Standard Error (SDTERR)

• stdin, stdout, stderr sono assunti di default da tutti i processi

• la convenzione é utile per la redirezione dell’input/output e per l’uso delle pipe

• possono essere gestiti come normali file (cioé chiusi, riassegnati, riaperti, ...)

27

Esempio di redirezione dell’output

– ls > myfile

– close(stdout)

– fd=open(“myfile”,w)

– exec(“ls”)

– close(fd)

– fd=open(stdout)

01234567...

user file table count read 1count write 1count rd-wrt 1... .......count write 1... ......

file table

28

System call “READ”

• n = read (fd, where_to_put_chars, how_many)

• n = numero di caratteri letti

• OFFSET = OFFSET + n

• read é implementata in modo da poter richiedere la lettura di piú blocchi in anticipo per aumentare l’efficienza

29

System call “WRITE”

• n = write (fd, where_to_get_chars, how_many)

• n = numero di caratteri scritti

• OFFSET = OFFSET + n

• write puó richiedere l’allocazione di blocchi indiretti

• puó non avere effetto immediato sul file su disco a causa del buffer cache Unix

30

System call “LSEEK”

• position = lseek (fd, offset, from_where)

• from_where:– 0 OFFSET ATTUALE = inizio file– 1 OFFSET ATTUALE = OFFSET ATT. + offset– 2 OFFSET ATTUALE = File size + offset

31

System call “CREATE”

• fd = create(“file”,MODE) (fd: user file descriptor)

• crea “file” se non esiste, o lo azzera se esiste

• crea una entry per “file” nella directory specificata

• crea un nuovo i-node e lo copia su disco

• “file” é aperto in scrittura

32

system call “CLOSE”• close(3)• close(5)

01234567...

user file table

rilasciato.... .........count rd-wrt 1... .......

... ...

...

file table

count /etc/passwd 1.... .........

in-core i-node ritorna in free list

... ....

...

... ... ...... ......

i-node table

NULL

NULL

count := count -1

rilasciato

33

System call “LINK”

• link(existing_file_name, new_file_name) • Associa ad un file un nuovo nome• il kernel:

– recupera l’i-node di “file” e controlla i permessi– link-counter = link-counter + 1– alloca una nuova entry nella directory di new_file_name con

nuovo nome, e l’i-node di existing_file_name– (é cosí che funziona anche il comando Unix ln)– questo tipo di link si chiama hard link

34

System call “UNLINK”

• unlink(file_name)

• rimuove un link a file_name

• il kernel:– recupera l’i-node di “file” e controlla i permessi– link-counter = link-counter - 1– rimuove l’entry dalla directory di file_name– se link-counter = 0, rimuovi l’i-node (é cosí che

funziona anche il comando Unix rm)

35

Symbolic Link

• il numero di un i-node é unico solo nell’ambito di un file system

• un link fisico (hard link) non puó attraversare i file system

• per fare ció si usano i link simbolici– ln -s /usr/local/bin/prolog myprolog – nella entry della directory per myprolog non viene

registrato l’-inode del file prolog, ma il suo pathname assoluto.

– il link counter non viene modificato

36

File di tipo “PIPE”

• Permettono la comunicazione tra processi con un meccanismo di tipo FIFO

• UNNAMED PIPE– vengono riferite solo mediante file descriptor– solo processi in relazione padre/figlio possono usare

una unnamed pipe – sono automaticamente rimosse alla morte dei processi

• NAMED PIPE– esistono nel file system– qualsiasi processo puó usarne una (se ha i permessi)

37

Unnamed PIPE

• Risiedono solo in memoria primaria, per cui sono meccanismi di comunicazione velocissimi

• Vengono implementate come file normali usando un i-node.

• Solo i blocchi indirizzati direttamente vengono usati per lettura/scrittura, e sono gestiti in modo circolare.

• ad ogni pipe sono associati un file descriptor in lettura ed uno in scrittura

38

pipe(fds)

fds[0] = lettura

int fds[2]

fds[1] = scrittura

0 1 2 3 4 5 6 7 8 9

offset 0 offset 10239

read pointer write pointer

blocchi diretti dell’i-node

39

funzionamento della pipe

• i dati vengono letti nell’ordine in cui sono stati scritti (no lseek)

• i dati possono essere letti una sola volta (vengono “consumati”)

• un dato non puó essere sovrascritto prima che sia stato letto (il processo scrittore é messo in wait)

• la lettura di una pipe vuota provoca la sospensione del processo lettore

40

Esempio di uso di unnamed pipe

char string[] = “hello”main(){char buf[1024]char *cp1, *cp2;int fds[2]cp1 = string;cp2 = buf;while (*cp1) *cp2++ = *cp1++;pipe(fds);for (;;) {

write(fds[1], buf, 6);read (fds[0], buf, 6):}

}

Il processo scrive e legge sulla pipe all’infinito. Che succede se si scambiano i due comandi di scrittura/lettura?

41

named pipes

• mknod(file_name, PIPE, 0);

• crea il file file_name che viene gestito come una pipe

• file_name é un file del file system, quindi ogni processo lo vede e puó usarlo, se ha i permessi.

• anche questa pipe é sospensiva

42

esempio di uso di named pipe

#include <fcntl.h>

char string[] = ‘” hello”;

main(argc,argv)

int argc; char *argv[];

{

int fd;

char buf[256];

/* creazione di una named pipe con permessi di lettura/scrittura per tutti gli utenti */

mknod(“fifo”, 010777,0);

if (argc == 2 ) fd = open(“fifo”, O_WRONLY);

else fd = open(“fifo”, O_RDONLY);

for(;;)

if (argc == 2) write(fd, string, 6);

else read(fd, string, 6);

}