Domenico Cotroneo » 20.Il File System

Il File System

Sommario

• Concetto di File e metodi di accesso
• Struttura delle directory
• Struttura del file system e metodi di allocazione
• Gestione dello spazio libero
• Cenni ai File System UNIX/Linux e Windows

Caratteristiche di un file system

Un file system è quella parte di un sistema operativo responsabile per la gestione e l’organizzazione dei file. In particolare, gli obiettivi di un FS sono quelli di garantirne:

1. la persistenza;
2. il recupero;
3. un meccanismo di naming;
4. la condivisione e la protezione.

Un FS fornisce alle applicazioni un’interfaccia unica per la gestione dei file.

Struttura di un file system

Concetto di File

Un file è un insieme di informazioni, correlate e registrate nella memoria secondaria, cui è stato assegnato un identificativo (nome).

Contengono sia dati sia attributi.

• I dati consistono in sequenze di byte accessibili dalle funzioni di read e write.
• Gli attributi sono delle informazioni che descrivono il file (tipo, lunghezza,data ultima modifica, proprietario, locazione, valore del file pointer, lista per il controllo degli accessi).

Directory

Al fine di gestire un elevato numero di file, un FS è strutturato in directory, cioè in un insieme di nodi contenenti informazioni su tutti i file.

Una directory è un file speciale creato con l’obiettivo di risolvere le corrispondenza tra il nome del file in formato testuale e il suo identificativo interno.

Struttura di directory ad albero

Ricerca efficiente.

Possibilità di raggruppamento.

Directory corrente (quella che contiene la maggior parte dei file di interesse corrente).

• cd /spell/mail/prog

Struttura di directory a grafo aciclico

Consente alle directory di avere sottodirectory e file condivisi

Struttura di directory a grafo aciclico

Nomi diversi possono riferirsi allo stesso file (aliasing)

Se a ogni operazione di cancellazione segue l’immediata rimozione del file, potrebbero rimanere puntatori a un file che ormai non esiste più.
Soluzioni:

• cercare tutti questi collegamenti e rimuoverli (backpointers);
• conservazione del file fino a che non siano stati cancellati tutti i riferimenti a esso.

Accesso ad un file system

• Controllo degli Accessi
• Accesso ad un file

Protezione nell’accesso ai file

L’accesso ai file va consentito soltanto agli utenti autorizzati, mediante uno schema di permessi di accesso.

Con riferimento ai sistemi UNIX, a ciascun file (normale, speciale o directory) sono associati alcuni attributi:

• proprietario (owner): è l’utente che ha creato il file;
• gruppo: è il gruppo di utenti a cui il proprietario appartiene;
• permessi (permissions): il tipo di operazioni che il proprietario, i membri del suo gruppo o gli altri utenti possono compiere sul file.

Proprietario, gruppo e permessi iniziali sono assegnati dal sistema al file al momento della sua creazione. Il proprietario potrà successivamente modificare tali attributi.

Permessi

Ad un file possono essere attribuiti i seguenti permessi

Esempio

Tipico FCB (Descrittore di File)

Operazioni su file

• Creazione;
• lettura;
• cancellazione;
• apertura – open(F_i): cerca sul disco la directory che contiene il FCB F_i, e carica tale FCB in memoria (Tabella dei file aperti);
• scrittura;
• riposizionamento nel file – file seek;
• chiusura – close (F_i): trasferisce il contenuto del FCB F_i in memoria sul file directory su disco.

Quasi tutti i FS forniscono un’interfaccia conforme allo standard POSIX.

Operazioni su file

Tipicamente le operazioni di un file System sono implementate nel Kernel come System call

Un esempio di una open

int fd= open (/home/cotroneo/didattica/so/monitor.c);

Alla open si fornisce un path name (che può essere assoluto o relativo) per individuare il file dato in ingresso.

Fase 1: Accesso al disco

• La system call “percorre” il percorso (path) fornito come parametro di ingresso nel seguente modo:
  • nella directory “home” cercherà la directory “cotroneo” e così via fino alla directory “so”;
  • si accede al FCB del file monitor.c, estraendo gli attributi e gli indirizzi fisici (cilindro, traccia , settore) ed allocando in memoria una struttura dati (file descriptor) contenente le informazioni estratte.

Fase 2: Accesso in memoria

• Ogni operazione successiva sul file utilizzerà le informazioni caricate in memoria nel file descriptor.

Metodi d’accesso al file

Accesso sequenziale: tempo di accesso dipendente dalla posizione

read next
write next
reset

Accesso diretto: tempo di accesso indipendente dalla posizione

read n
write n
position to n

read next
write next

n = numero relativo del blocco

Organizzazione fisica - Il layout del file system

Ogni disco può essere organizzato in più partizioni, ognuna delle quali può avere un proprio file system.
Ogni disco ha uno speciale settore (Settore 0), denominato MBR (Master Boot Record), che viene utilizzato per il bootstrap.
L’MBR contiene inoltre la tabella delle partizioni del disco (indirizzo iniziale e finale di ogni partizione), di cui solo una può essere etichettata con lo stato “Active”.
Quando il sistema parte, la BIOS accede al primo settore del disco (MBR), carica in memoria il contenuto e lo esegue. Il programma caricato si articola nei seguenti passi:

• localizza la partizione attiva.
• legge il primo blocco (boot block) della partizione attiva.
• il programma del boot block non fa altro che caricare il sistema operativo memorizzato in quella partizione.

Il layout del file system

Metodi di allocazione dei file

Definiscono il modo in cui i blocchi del disco sono assegnati ai file:

• allocazione contigua;
• allocazione concatenata;
• allocazione indicizzata.

Allocazione contigua

Allocazione contigua

Ciascun file occupa un insieme di blocchi contigui sul disco.
Vantaggi

• Per reperire tutto il file sono necessarie solo la posizione di inizio (block #) e la lunghezza (numero di blocchi).
• Possibile sia l’accesso sequenziale che diretto.

Svantaggi

• Frammentazione esterna (problema dell’allocazione dinamica della memoria) → Problema della compattazione del disco.
• I file non possono crescere.

Allocazione concatenata

I blocchi sui quali viene mappato ogni file sono organizzati in una lista concatenata.
Vantaggi

• non c’è frammentazione esterna;
• minor costo di allocazione.

Svantaggi

• possibilità di errore se un link viene danneggiato;
• maggior occupazione (spazio occupato dai puntatori);
• difficoltà di realizzazione dell’accesso diretto;
• costo della ricerca di un blocco.

Allocazione indicizzata

Colleziona tutti i puntatori insieme nel blocco di indice

Allocazione indicizzata

Richiede una tabella indice.
E’ possibile un accesso casuale.
Si ha un accesso dinamico senza frammentazione esterna, ma c’è il sovraccarico del blocco indice.
Dimensione del blocco indice: un blocco piccolo comporta meno spreco nel caso di file piccoli, ma per file grandi?

• Schema concatenato: si collegano blocchi della tabella indice (non si ha un limite alla dimensione).
• Indice a più livelli
• Schema combinato

Indice multilivello

Gestione dello spazio libero

La mappa dei bit richiede uno spazio ulteriore.

Esempio:

block size = 2¹² byte
disk size = 2³⁰ byte (1 gigabyte)
n = 2³⁰/2¹² = 2¹⁸ bit (o 32K byte)

Gestione dei file in UNIX

UNIX distingue 6 tipi di file:

1. Ordinary: file dati (sequenza di byte);
2. Directory;
3. Special: per mappare i dispositivi di I/O;
4. Named Pipe: costituisce un meccanismo di IPC via file;
5. Link: un nome alternativo per un file esistente;
6. Symbolic link: un file dati contenente il nome del file a cui è collegato.

inodes

Tutti i file UNIX sono gestiti e rappresentati tramite gli inode.

Un inode (index node) è una struttura di controllo (un FCB) che contiene tutte le informazioni di cui il SO ha bisogno per gestire il file corrispondente.

Ogni file è controllato da esattamente un inode, e viceversa, ma più nomi di file possono essere associati allo stesso inode (con il meccanismo dei link).

inodes: allocazione a indice multilivello con schema combinato

Il Virtual File System (VFS) di Linux

Il Virtual File System (VFS) di Linux

VFS presenta un’interfaccia uniforme ai processi, indipendentemente dal particolare file system adottato.

Definisce un modello generale di file, comune a tutti i file system:

• ogni file ha un nome logico corrispondente ad una directory;
• ogni file ha un proprietario che stabilisce i permessi di accesso;
• un file può essere creato, letto, scritto, distrutto;
• …

Anche VFS gestisce i file attraverso gli inode (detti anche v-node), i quali però non contengono informazioni circa i blocchi dati (tali informazioni sono gestite dal file system specifico)

Il file system ext2

Il second extended filesystem supporta tutte le caratteristiche di un filesystem standard Unix.
è in grado di gestire nomi di file lunghi (256 caratteri, estensibili a 1012) con una dimensione massima di 4 Tb.

Presenta diverse estensioni rispetto al FS Unix:

• dimensione dei blocchi configurabile in fase di installazione;
• attributi dei file ereditabili dalle directory;
• link simbolici veloci (memorizzati nell’inode, non in un blocco dati);
• supporto a file immutabili (read only) e append-only.

Il file system ext2

Il layout di una partizione ext2 prevede:

• Superblock: contiene informazioni complessive sulla partizione quali il numero di blocchi complessivo, il numero di inode, il numero di blocchi liberi, etc;
• Block bitmap: tabella in cui ad ogni bit è associato un blocco di dati. Lo stato del bit indica se il relativo blocco è libero o allocato ad un file;
• inode bitmap: tabella in cui ciascun bit è associato ad un “inode”. Lo stato del bit indica se il corrispondente inode è libero o in uso;
• inode table: tabella degli “inode”. Ogni elemento di questa tabella corrisponde ad un singolo file,
• Data blocks: la porzione di disco dove sono effettivamente memorizzati i dati;
• Directory: tabella che associa nomi arbitrari agli inode.

Il file system ext3

Introdotto nel 2001 nel kernel Linux 2.4.15
Rispetto al suo predecessore, introduce le seguenti caratteristiche:

• il journaling;
• aumento delle dimensioni del file system “a caldo”;
• per le directory molto grandi adotta un’indicizzazione basata su strutture ad albero.

Il journaling consiste nel gestire un “diario” (journal) delle modifiche da fare, in modo da evitare che errori e malfunzionamenti possano lasciare i file in uno stato inconsistente.

Limita il ricorso a specifici tool per il controllo della consistenza, come e2fsck.

Il file system ext4

Introdotto nel 2006 nel kernel Linux 2.6.19
Rispetto ad ext3, aggiunge:

• il supporto a volumi grandi, fino a 16 TB;
• l’utilizzo di gruppi contigui di blocchi, noti come extent per memorizzare file di grosse dimensioni (la massima dimensione di un extent è di 128 MB);
• l’allocazione multiblocco (in ext3 la decisione su dove allocare i blocchi di un file è fatta blocco per blocco)
• l’allocazione ritardata, per effettuare scelte di allocazione ottimizzate solo quando si decide effettivamente di salvare il file

Il file system NTFS di Windows

Introdotto negli anni novanta con Windows NT

Principali caratteristiche:

• recuperabilità, attraverso un sistema transazionale (basato su “journal”) per la gestione delle modifiche, e introducendo ridondanza per le strutture dati critiche;
• sicurezza: ad ogni file è associato un descrittore per specificare attributi di sicurezza e ACL secondo il Windows Object Model;
• supporto a file e dischi di grosse dimensioni;
• supporto a nomi di file lunghi.

Master File Table (MFT)

Contiene la lista di tutti i file e le cartelle (memorizzate come i file) presenti nel volume, ed è organizzata come un insieme di righe di un database relazionale (ogni riga corrisponde a un file o a una cartella).

Ogni riga è di 1024 byte e contiene:

• gli attributi del file o cartella, trattati come metadati (estensibilità);
• i dati del file, se il file è abbastanza piccolo da essere contenuto in una singola entry di MFT;
• i puntatori ai cluster che contengono i dati del file o a dei cluster “indice” (allocazione indicizzata multilivello).

System Files

La regione “System Files” del volume contiene i seguenti elementi:

• MFT-2: un mirror delle prime tre righe del MFT (utile per recuperare l’accesso alla MFT in caso di guasto di un settore);
• Log file: il journal in cui sono memorizzati i passi delle transazioni, per garantire la recuperabilità;
• Cluster bit map: per la gestione dello spazio libero;
• Attribute definition table: definisce gli attributi supportati dal volume (estensibilità).