Torna alla pagina di Sistemi Operativi
:: Appunti caotici ::
Lezione 4 Realizzazione dei file: Allocazione dei blocchi
...
...
L'allocazione contigua prevede l'ordinamento sequenziale adiacente dei blocchi, ovvero avrò fisicamente un blocco dietro l'altro. Sostanzialmente si numerano progressivamente i blocchi e se ne prendono insiemi contigui da assegnare ai file.
Nella figura sulla slide si osserva un disco con quattro blocchi fisici per ogni traccia. Da notare come il blocco 0 non sia inteso come quello di boot, ma è il primo allocabile ai file.
Caratteristiche dell'allocazione contigua:
Per evitare sfridi e conseguenti ricompattazioni, o quanto meno per limitarle, devo abbandonare il criterio di allocazione contigua fisica e abbracciare quello di contiguità logica. Questa si realizza con una lista dei blocchi (linked allocation) da mantenere all'interno del disco. Ogni blocco conterrà al suo interno il puntatore al blocco successivo, via via fino all'ultimo. Per aggiungere un nuovo blocco al file sarà sufficiente modificare solo il puntatore dell'ultimo blocco.
Se applico un algoritmo di assegnamento dei blocchi furbo, farò in modo di assegnare in via preferenziale i blocchi contigui anche fisicamente, così da risparmiare tempo evitando di saltare tra una traccia e l'altra.
Caratteristiche dell'allocazione collegata:
File allocation Table (FAT), in cui ho tanti entry quanti sono i blocchi fisici del disco. In questo modo ho l'enorme vantaggio di non dover più andare a leggere blocco per blocco fisico per trovare quello desiderato, ma basterà fare una scansione rapida in tabella. Tuttavia per file grossi si perde comunque una barca di tempo per effettuare gli accessi.
Si utilizzano degli indici (i-node) contenenti la sequenza dei puntatori ai blocchi fisici. In questo modo si riduce di molto il tempo di accesso diretto: non devo più leggere tutta la lista finché arrivo al blocco k interessato, ma leggo direttamente da tabella guardando alla riga k. Con questa tecnica si recupera la contiguità fisica dei blocchi traslandola all'interno della tabella degli i-node, dal momento che gli indici sono fisicamente contigui.
NB: ogni file ha la sua tabella indice, al contrario della FAT che è unica per ogni partizione. Anche le tabelle indice vanno memorizzate in uno dei blocchi di servizio del disco (ad esempio l'1).
Se ho un file composto da tot elementi di dimensione L, ogni elemento k sarà preceduto da k elementi (perché la sequenza parte dalla posizione 0). In particolare, dato F la larghezza del blocco fisico, l'operazione\\ (k*L)/F
è molto istruttiva dato che la parte intera del risultato rappresenta il blocco in cui si trova l'informazione ricercata, mentre il resto del rapporto è lo spiazzamento dalla posizione 0 del blocco fisico.
Caratteristiche dell'allocazione indicizzata:
Blocco indice con schema collegato. Il principio è che quando esaurisco gli entry di un i-node, utilizzo l'ultima riga per collegarla ad un'altra i-node.
L'accesso diretto è un po' più lento perché se il blocco desiderato non è nel primo i-node, per sapere dove si trova dovrò prima passare a quello successivo (se sono nell'i-node 1 e il blocco si trova nel 5, dovrò prima attraversare quelli di mezzo).
Blocco indice con indice multi-livello. Aggiro i problemi della soluzione precedente mettendo le informazioni in una struttura ad albero piuttosto che in una lineare, così da avere tempi di accesso di tipo logaritmico.
Blocco indice con schema combinato, in cui tra le informazioni mantenute nel descrittore del file inserisco sia i-node ad accesso diretto che multilivello. Notare infatti che non è sempre comodo avere una struttura multilivello perché costringe ad una indirettezza di accesso che non sempre è utile/desiderabile, come ad esempio per i file piccoli. Sarebbe IDIOTA perderci tanto tempo per niente. :|
...
...
Vettore di bit: Bitmap. Scrivo in un vettore una serie di 0 o di 1 a seconda che un blocco sia libero (0) o usato da qualche file (1).
...
...