1 Implementazione del File System nel Sistema Operativo Unix (Bach: the Design of the Unix Operating...
-
Upload
calogera-salvatore -
Category
Documents
-
view
220 -
download
3
Transcript of 1 Implementazione del File System nel Sistema Operativo Unix (Bach: the Design of the Unix Operating...
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);
}