Torna alla pagina di Sistemi Operativi
:: Appunti caotici ::
Lezione 4
Realizzazione dei file: Allocazione dei blocchi
Pag 1
Sommario
...
Pag 2
Allocazione dei blocchi
...
Allocazione contigua (1)
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.
Pag 3
Allocazione contigua (2)
Caratteristiche dell'allocazione contigua:
- accesso rapido al blocco successivo, senza avere enormi movimenti della testina
- accesso diretto lento, perché prima di accedere ai blocchi dovrò calcolarmi dove si trovano
- problema di mancanza di spazio contiguo per l'allocazione di un nuovo file o per l'estensione di un file esistente. E' la grossa fregatura di questa tecnica, difficilmente eludibile dal momento che per evitarla dovrei sapere a priori quanto spazio serve a un file, e questa informazione non è sempre fornita
- frammentazione esterna, che si contrasta (con timidi successi) con la compattazione
- frammentazione interna come conseguenza dell'estensione del file
Allocazione collegata (1)
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.
Pag 4
Allocazione collegata (2)
Caratteristiche dell'allocazione collegata:
- nessuna frammentazione esterna, perché tutti i blocchi che servono si andranno a prendere nel disco ovunque se ne trovino di liberi
- accesso diretto lento, perché non abbiamo più accessi fisicamente sequenziali, ma sparsi a caso. Andranno dunque consultati con una scansione della lista
- va considerato che in media il numero di blocchi per file aumenta, perché riservando una porzione del loro spazio per memorizzare i puntatori, vado a togliere dei byte per i dati. Una soluzione è stata l'introduzione del concetto di cluster, in cui anziché considerare singoli blocchi della lista si considerano gruppi fisicamente contigui. In questo modo si mantengono puntatori tra cluster, riducendo il tempo di posizionamento sia per letture sequenziali che ad accesso diretto
- probliemi di affidabilità in caso di guasto in un blocco fisico. Se si rovina il contenuto di un blocco non perdo solo i dati, ma anche il puntatore al blocco successivo, quindi tutte le informazioni sulla coda. E' preferibile quindi non mantenere tutte queste informazioni all'interno dei blocchi stessi, ma in una tabella esterna di esterna, salvata su disco (possibilmente nel settore 1) per rimanere permanente. Nella prossima slide ne parleremo meglio
Allocazione collegata (3)
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.
Pag 5
Allocazione indicizzata (1)
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.
Allocazione indicizzata (2)
Caratteristiche dell'allocazione indicizzata:
- ho un indice per file
- nessuna frammentazione esterna perché tutti i blocchi sono ugualmente validi per scriverci dentro
- accesso diretto veloce. Posso ridurre i tempi di accessi sequenziali usando un algoritmo di allocazione che minimizzi la distanza fisica dei blocchi logicamente contigui nel disco
- affidabilità, perché in caso di guasto che distrugga un blocco fisico, il malfunzionamento è circoscritto ad esso e non si ripercuote sulla coda. Si può inoltre aumentare l'affidabilità mantenendo più copie su disco delle i-node o delle FAT
- il dimensionamento del blocco indice può essere per schema collegato, indice multilivello o schema combinato
Pag 6
Allocazione indicizzata (3)
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).
Allocazione indicizzata (4)
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.
Pag 7
Allocazione indicizzata (5)
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. :|
Miglioramento delle prestazioni per allocazione
...
Pag 8
Gestione dello spazio libero (1)
...
Gestione dello spazio libero (2)
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).
Pag 9
Gestione dello spazio libero (3)
...
Gestione dello spazio libero (4)
...
Torna alla pagina di Sistemi Operativi
