Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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


La struttura logica di un file system.

  • File
  • Directory (o Folder)

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

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.

File system montabile

Un file system può avere parti residenti su device removibili (es. dischetti, USB pen), o su altre partizioni del disco fisso.

Tipicamente i file system consentono di agganciare (sganciare) il file system che si trova su di un dispositivo all’albero dei file principale (montaggio).


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

Ad un file possono essere attribuiti i seguenti permessi

Esempio

Esempio


Accesso al file

Tipicamente una directory contiene un lista di entries, una per ogni file, contenente le informazioni relative al file associato.

Nella maggior parte dei SO ogni entry contiene un puntatore ad una struttura dati associata al file, denominata FCB.

File control block – struttura di memorizzazione che contiente le informazioni su un file.


Tipico FCB (Descrittore di File)


Operazioni su file

  • Creazione;
  • lettura;
  • cancellazione;
  • apertura – open(Fi): cerca sul disco la directory che contiene il FCB Fi, e carica tale FCB in memoria (Tabella dei file aperti);
  • scrittura;
  • riposizionamento nel file – file seek;
  • chiusura – close (Fi): trasferisce il contenuto del FCB Fi 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

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


Block vs. Sector

Il sistema operativo usa una dimensione del blocco in genere maggiore di quella del settore del disco. Ogni blocco consiste di un certo numero di settori consecutivi.

Quali sono i motivi di questa scelta?

  • Un blocco di dimensione maggiore aumenta l’efficienza di trasferimento.
  • Può essere conveniente avere una dimensione del blocco della stessa dimensione di una pagina in memoria.

Ogni blocco contiene un insieme di settori contigui.


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 (linked)

Ciascun file è una lista concatenata di blocchi su disco: i blocchi possono essere sparpagliati ovunque sul disco.

Si alloca quanto è richiesto, e poi si concatenano i blocchi insieme.


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.

FAT

File-allocation table (FAT)

Allocazione dello spazio su disco usata da MS-DOS e OS/2.

La FAT è una tabella con un elemento per ogni blocco disco ed è indirizzato dal numero di blocco.

La FAT consente di avere i puntatori localizzati sul disco e non sparsi.

Velocizza anche l’accesso diretto.


Allocazione indicizzata

Colleziona tutti i puntatori insieme nel blocco di indice

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

Lista concatenata (free list)

  • Non è facile prendere spazio contiguo
  • Non si spreca spazio

Raggruppamento: memorizzazione degli indirizzi di n blocchi liberi sul primo di tali blocchi. Sull’ultimo sono indirizzati altri blocchi, e così via.

Conteggio: Si indica un blocco libero, e da quanti altri blocchi liberi (contigui) è seguito.

Vettore di bit   (n blocchi)

Vettore di bit (n blocchi)


Gestione dello spazio libero

La mappa dei bit richiede uno spazio ulteriore.

Esempio:

block size = 212 byte
disk size = 230 byte (1 gigabyte)
n = 230/212 = 218 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.

Unità di storage di NTFS

Sector: la più piccola unità di storage (512 byte).

Cluster: uno o più settori contigui; la dimensione effettiva dei cluster varia da 1 a 128 settori, e dipende dalla dimensione complessiva del volume (a volumi grandi corrispondono cluster grandi e viceversa).

Volume: una partizione logica del disco.

Layout di un volume NTFS

Layout di un volume NTFS


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à).

I materiali di supporto della lezione

P. Ancilotti, M. Boari, A. Ciampolini, G. Lipari, “Sistemi Operativi”, Mc-Graw-Hill (Cap.6)

W. Stallings, Operating Systems, par. 12.8 – 12.10

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion