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 (worstfit).
• 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
Scarica

Unità D2 - Alberto Ferrari