Frammentazione
Da Wikipedia, l'enciclopedia libera.
In informatica, la frammentazione indica il fenomeno della suddivisione di una sequenza di dati in più parti, al fine di memorizzarli o di trasmetterli.
Indice |
[modifica] Frammentazione nella memorizzazione dei dati
Il fenomeno si verifica quando si inseriscono e si rimuovono processi dalla memoria centrale (RAM), oppure file da una memoria di massa (ad es. un Hard Disk). Dato che la memoria è, a livello logico, una sequenza contigua di spazi (celle o settori) atti a contenere unità elementari di dati, e che normalmente un oggetto da memorizzare (un programma o un file) si compone di numerose unità elementari contigue, l'organizzazione di tali sequenze in memoria deve seguire una qualche regola che consenta di aggiungere e rimuovere tali oggetti con accesso casuale. Infatti, ripetute aggiunte o rimozioni di sequenze di dati di dimensioni eterogenee comportano una "frammentazione" dello spazio libero disponibile, che quindi non risulta più essere contiguo. La ricostruzione della sequenza originale dei dati memorizzati può quindi introdurre delle complicazioni nella struttura di memorizzazione, o dei cali di prestazioni, a seconda del tipo di memoria in cui tali dati vengono memorizzati. Qualunque disco rigido, infatti, lavora alle massime prestazioni solo qualora debba scrivere o leggere dati memorizzati in posizioni contigue: il "salto" fisico della testina di lettura del disco da un settore ad un altro posto in diversi cilindri introduce dei rallentamenti che, in casi particolari, possono raggiungere livelli critici.
La differenza tra la frammentazione in memoria primaria e secondaria consta nella diversa modalità con cui i dati devono essere memorizzati. In memoria primaria, un programma deve essere necessariamente caricato in una area di memoria libera di dimensione pari almeno alla dimensione del programma stesso. Il caricamento e lo scaricamento di programmi in maniera disordinata introduce un incremento del numero di aree di memoria libere, ciascuna di dimensione sempre minore. Pertanto è possibile ad un certo momento che, all'atto del caricamento di un programma in memoria, non vi sia un'area di memoria contigua abbastanza grande, sebbene la memoria complessiva libera sia sufficiente.
Per semplicità, d'ora in poi ci si riferisce sempre alla memoria secondaria ed a file di dati, in quanto il ragionamento può facilmente essere esteso anche alla memoria primaria. Vengono generalmente individuati due tipi di frammentazione, di cui solo uno influisce sulle prestazioni del sistema:
- Frammentazione interna
- La memoria è suddivisa in blocchi di grandezza uguale B (es. un settore di un disco). Quando un file di dimensione D deve essere memorizzato, vengono riempiti completamente (D div B)-1 blocchi di memoria, ed uno che ne conterrà D mod B. La frammentazione interna consiste nello spazio di memoria che rimane libero ed inutilizzato nell'ultimo blocco. Questo tipo di frammentazione non influisce sulle prestazioni del sistema ma comporta uno spreco di memoria. Come caso particolare, se D mod B == 0, allora vengono occupati esattamente D div B blocchi di memoria, e lo spreco diventa nullo. Ovviamente, tale spreco risulta essere percentualmente molto piccolo se D >> B, mentre risulta essere molto alto in caso di file di dimensioni comparabili a B. Per esemplificare, se un file di 1.637.257 byte deve essere memorizzato in un disco avente settori da 4096 byte, allora saranno occupati completamente 399 settori, mentre uno sarà occupato per 2953 byte (infatti 4096x399+2953=1637257). In tal caso, lo spazio sprecato è circa dello 0,18%. Se invece deve essere memorizzato un file di 1000 byte, allora lo spreco è di 3096 byte, ovvero del 75,59%.
- Frammentazione esterna
- In genere, il controller dell'hard disk cerca di minimizzare i tempi di accesso al disco, tentando di memorizzare un file in settori contigui e ridurre al massimo lo spostamento delle testine (azione che introduce notevoli rallentamenti nell'accesso ai dati). Tuttavia, in seguito alla ripetuta memorizzazione e cancellazione di file di dimensione eterogenea effettuata in maniera disordinata, si verifica una riduzione dello spazio contiguo massimo disponibile. In tal caso, un nuovo file di dimensioni sufficientemente ampie che deve essere memorizzato verrà scritto presumibilmente in settori e cilindri non adiacenti. Questo può portare ad un aumento anche notevole dei tempi di lettura e scrittura, introducendo un calo notevole delle prestazioni del sistema.
Le soluzioni possibili per migliorare le prestazioni del sistema sono state oggetto di studio approfondito in campo informatico. Nel caso di un disco, si tratta di riordinare i frammenti dei file in modo da risultare adiacenti l'uno all'altro, minimizzandone quindi i tempi di accesso. Nel caso della memoria, è necessario massimizzare la memoria contigua disponibile. Entrambi i problemi, tuttavia, sono riconducibili al problema dello zaino, e quindi hanno tempo di soluzione pseudo-polinomiale. Nel primo caso si fa uso di appositi programmi, detti deframmentatori; nel secondo caso è possibile che il sistema operativo si occupi di tale problema, così come è possibile fare uso esplicito del garbage collection.
[modifica] Frammentazione nella trasmissione dei dati
Nelle reti di trasmissione di dati a pacchetti, come ad esempio in IPv4, viene introdotta una quantità, detta MTU (Maximum Transmission Unit, unità massima di trasmissione) che indica la la quantità massima di dati che, nella rete, può essere trasmessa in un singolo pacchetto. Ad esempio, in una rete Ethernet la dimensione MTU standard è di 1500 byte (dimensione massima del pacchetto IP), mentre in una rete Token ring è di 4096. La frammentazione avviene quando viene inserito nella rete un pacchetto di dimensione superiore alla MTU, e questo deve essere trasmesso.
[modifica] Esempio
Si supponga ad esempio che un pacchetto IP di 2396 byte debba essere trasmesso in una rete Ethernet (con MTU=1500). Allora questo pacchetto dovrà essere frammentato in due pacchetti.
- Primo pacchetto
- Sarà lungo complessivamente 1500 byte, pari alla MTU della rete Ethernet. Di questi, 20 saranno usati per l'intestazione IP, 24 bytes saranno di intestazione TCP, e 1456 saranno di dati. Inoltre questo pacchetto avrà, nell'intestazione IP, il bit DF settato a 0 per indicare "frammentazione possibile", il flag MF posto ad 1 per indicare "ulteriori frammenti presenti", ed il campo di "Fragmentation Offset" (Scostamento di Frammentazione) posto a 0. Quest'ultimo campo viene misurato in termini di unità di 8 byte (64 bit).
- Secondo pacchetto
- sarà lungo 940 byte in tutto. Come prima, 20 sono di intestazione IP, 24 di intestazione TCP, ed 896 di dati. Nell'intestazione IP ci saranno quindi il bit DF sempre uguale a 0, ma il bit MF posto ad 0 per indicare "ultimo frammento". Il "Fragmentation offset" ora avrà valore 182 (ovvero 1456/8).
Si noti che 2396 si ottiene sommando le dimensioni degli header oltre a quelle dei dati: pertanto 2396 = 24 + 20 + 1456 + 896.
La frammentazione è particolarmente conosciuta in internet, in quanto sovente i router posti lungo il percorso utilizzano diversi mezzi fisici per il collegamento, e quindi differenti protocolli di rete, ognuno con il proprio MTU.
[modifica] Voci correlate
Portale Informatica: accedi alle voci di Wikipedia che parlano di Informatica
