Unità D2

Archivi e file

Obiettivi

• Conoscere la differenza tra organizzazione logica e fisica

• Conoscere la differenza tra record logico e record fisico

• Sapere che cosa è un archivio fisicamente sequenziale

• Sapere che cosa è un archivio fisicamente non sequenziale

• Conoscere i vari tipi di allocazione di spazio della memoria di massa

Organizzazioni fisiche degli archivi

• Un singolo file può essere scritto su disco in modo diverso, a seconda del metodo utilizzato dal sistema operativo:– allocazione contigua;– allocazione concatenata;– allocazione indicizzata.

• La rappresentazione di un file su disco è una serie di bit di valore zero o uno.

• I dati scritti su disco sono suddivisi in parti di 8 bit ciascuna, ovvero 1 byte.

Record logici e fisici

• Record logici– Un record è un insieme di dati attinenti a una stessa entità.– I campi di un record descrivono caratteristiche dell’entità a

cui il record fa riferimento.• Record fisici

– Il blocco o record fisico rappresenta la quantità minima di informazione trasferibile dal disco alla memoria centrale e viceversa, rispettivamente con una singola operazione di lettura e scrittura.

– Il fattore di blocco è il numero di record logici che compongono un record fisico.

– Un record fisico si dice sbloccato se contiene uno e un solo record logico; si dice bloccato se è composto da più record logici; è detto infine multiblocco se ne occorre più di uno per memorizzare un record logico.

Fattore di blocco

Archivi sequenziali e allocazione contigua

• Intendiamo “archivi fisici sequenziali”; con questo termine vogliamo quindi indicare il modo in cui i file sono scritti su disco.

• Gli archivi sequenziali sono scritti sulla memoria di massa mediante la tecnica dell’allocazione contigua.

• I blocchi che costituiscono il file sono posti uno di seguito all’altro,

Allocazione contigua

Vantaggi e svantaggi

• Vantaggi– risparmio di tempo nella lettura del file (la testina

del disco non dovrà effettuare un grande spostamento per leggere i vari blocchi)

– l’accesso diretto può essere implementato in modo semplice conoscendo la dimensione dei blocchi e l’indirizzo su disco del primo blocco.

• Svantaggi– quando si deve scrivere un file su disco, è prima

necessario individuare un’area composta da blocchi contigui abbastanza capiente per contenere il file

Tecniche di allocazione

• Ricerca della prima area libera sufficientemente grande (first-fit);

• Ricerca della prima area libera sufficientemente grande, iniziando la scansione dal punto in cui si trova la testina (next-fit);

• Ricerca dell’area libera più piccola che possa contenere il file (best-fit);

• Ricerca dell’area libera più grande possibile (worst-fit).• Qualsiasi tecnica si utilizzi il disco verrà frammentato

sempre di più, fino a trovarsi in una situazione paradossale: non sarà possibile memorizzare un file poiché non esiste uno spazio contiguo abbastanza capiente, nonostante lo spazio libero complessivo sia notevolmente maggiore di quello necessario.

Archivi non sequenziali

• Un archivio non sequenziale è composto da blocchi sparsi su disco e non necessariamente contigui.

• Deve essere adottata una tecnica che consenta di ricostruire l’insieme dei blocchi che compongono il file. – si devono conoscere le posizioni di tutti i blocchi di un file– si deve poter ricostruire la sequenza corretta dei blocchi del

file.

• Tecniche adottate:– allocazione concatenata – allocazione indicizzata.

Allocazione concatenata

• Ogni directory contiene le informazioni relative al primo e ultimo blocco di ogni file

• Ogni blocco conterrà un riferimento a quello successivo consentendo così l’accesso ordinato a ciascuno di essi, fino a raggiungere l’ultimo blocco del file

• L’allocazione concatenata elimina il problema della frammentazione introdotto dall’allocazione contigua.

Un esempio

Allocazione concatenata: inconvenienti

• Accesso unicamente sequenziale – la struttura del file consente solo l’accesso in sequenza ai

singoli blocchi; in questo modo, per accedere al blocco N occorre prima scorrere tutti i blocchi fino all’N – 1.

– un file logicamente organizzato ad accesso diretto potrà comunque funzionare, ma con prestazioni limitate.

• Affidabilità– il fatto che i blocchi siano tutti sparsi su disco, e che si

acceda a quello successivo solo grazie al riferimento contenuto nel precedente, fa in modo che la sola perdita di un riferimento a un blocco impedisca la ricostruzione del file, e conseguentemente causi la perdita dei dati in esso contenuti.

Soluzioni ai problemi di affidabilità

• Concatenare i blocchi in modo doppio (o bidirezionale), inserendo un riferimento in ogni blocco, non solo a quello successivo ma anche al precedente.

• Inoltre, includendo nei blocchi anche il nome del file di appartenenza, un’apposita procedura del sistema operativo potrebbe ricostruire la struttura dei file danneggiati, recuperando così i dati persi.

• Una soluzione più efficiente è l’utilizzo di una tabella che rappresenti un’immagine virtuale dei blocchi su disco, chiamata FAT (File Allocation Table).

• La FAT contiene i riferimenti che vanno da un blocco a un altro senza ovviamente memorizzare i dati del file stesso

FAT

Allocazione indicizzata

• L’allocazione indicizzata organizza i riferimenti ai blocchi di un file in un vettore detto blocco indice.

• Esiste un blocco indice per ogni file presente sul filesystem.

• Il recupero dei blocchi è molto semplice: per leggere il blocco N di un file, il sistema non deve fare altro che accedere all’elemento N del blocco indice e leggere l’indirizzo della memoria di massa contenuto.

• L’allocazione indicizzata, in una forma specifica in cui i blocchi indice sono chiamati i-node, è il sistema di organizzazione utilizzato nei sistemi Unix.

Blocco indice