Frammentazione (informatica)

In informatica e telecomunicazioni la frammentazione indica il processo di suddivisione di una sequenza di dati in più parti, al fine di memorizzarli su apposito supporto di memorizzazione o di trasmetterli in rete.

Nella memorizzazione dei dati

Esempio della frammentazione di una memoria di massa

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. In tal caso, in memorie secondarie come i dischi la ricostruzione della sequenza originale dei dati memorizzati è fatta in modo inefficiente, con cali di prestazioni; 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.

Ciò non si verifica tipicamente per le memorie primarie, perché la differenza tra la frammentazione in memoria primaria e secondaria consta nella diversa modalità con cui i dati devono essere memorizzati. Infatti in memoria primaria un programma viene caricato in una area di memoria libera di dimensione pari almeno alla dimensione del programma stesso oppure (memoria virtuale) in un certo numero di aree di memoria di lunghezza fissa (pagine) in cui è divisa la memoria. Tuttavia, in entrambi i casi i dati sono riferiti con accesso diretto e non c'è un vantaggio temporale nell'accedere due pagine consecutive o due pagine con indirizzi di memoria lontani.

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\gg 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 4096 • 399 + 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.

Nella trasmissione dei dati

Nelle reti di trasmissione di dati a pacchetti, come ad esempio in IPv4, viene introdotta una quantità, detta Maximum Transmission Unit (MTU), che indica la quantità massima di dati che può essere trasmessa in rete, con un singolo pacchetto. Ad esempio, in una rete Ethernet la dimensione MTU standard è di 1500 byte, mentre in una rete Token ring è di 4096 byte. La frammentazione avviene quando viene inserito nella rete un pacchetto di dimensione superiore alla MTU, e questo deve essere trasmesso.

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 byte 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 a livello datalink, ognuno con il proprio MTU.

Nel caso di protocolli che supportano un limite minimo di dati da trasmettere si opererà in maniera opposta ovvero tramite assemblamento di pacchetti o riempimento di zeri (zero padding) per il raggiungimento del limite minimo richiesto di bit.

In ogni caso in ricezione sarà ripristinato il flusso continuo di dati tramite riassemblaggio ordinato di tutti i pacchetti relativi alla stessa trasmissione.

Voci correlate

• Deframmentazione
• Hard Disk
• Maximum Transmission Unit (MTU)
• Protocollo di rete
• Reti di calcolatori

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla frammentazione

Collegamenti esterni

• (EN) fragmentation, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL

Controllo di autorità	LCCN (EN) sh85128360 · J9U (EN, HE) 987007536417005171