Heaps: Perché c'è un compromesso tra la quantità di spazio occupato (frammentazione) e la velocità con cui vengono eseguite le operazioni?

La frammentazione viene dalla memoria che è inutilizzabile. L'allocazione dinamica è simile a giocare a Tetris: se giochi velocemente, finisci con buchi (frammentazione) e non puoi prevedere quale tipo di blocco cadrà dopo. Con l'allocazione dinamica, non puoi prevedere quando e quale memoria sarà liberata - immagina di giocare a Tetris dove i blocchi scompaiono casualmente! Ricorda inoltre che l'allocazione dinamica potrebbe richiedere l'allocazione di blocchi di dimensioni variabili: Tetris implicherebbe polynominos anziché tetrominos!

Un po 'sulle tecniche di allocazione dinamica:

Il modo in cui hai descritto è l'allocazione dei blocchi a dimensione fissa. Di solito è implementato come lista gratuita . Il problema con questo metodo è che non può allocare blocchi di dimensioni diverse e può portare a un cattivo comportamento nella cache.

Uno dei modi più semplici per implementare l'allocazione dinamica è allocazione della memoria buddy - implementato come un albero binario che soddisfa l'heap proprietà. Il problema con questo metodo è che ha una frammentazione interna. La frammentazione interna deriva dall'uso di tecniche che utilizzano blocchi predeterminati, in genere poteri di 2. Ciò significa che allocare 150 byte allocerebbe effettivamente un blocco di 256, sprecando 106 byte a causa della frammentazione interna.

Altri metodi cercano di ridurre al minimo la frammentazione, come allocazione lastre . L'allocazione delle lastre viene principalmente utilizzata per i kernel, poiché è stata progettata per allocare piccoli oggetti: non è l'ideale per malloc per scopi generici.

Comunque, il punto a cui sto andando è che tutto dipende dal tipo di allocazioni che stai facendo. I sistemi operativi non sanno quale metodo di allocazione sarebbe il migliore per un programma, ed è per questo che ne scelgono uno che bilancia la velocità con la frammentazione. È quasi impossibile avere la frammentazione 0 senza spingere continuamente i dati, è solo la natura dell'allocazione dinamica.

But I was wondering how these two criteria were related, namely, why there is a 'tradeoff' and why a faster heap makes it difficult for a smaller heap in size.

Quando arriva una richiesta, devi decidere dove allocarla. La cosa più rapida da fare sarebbe semplicemente assegnarla in cima all'heap ma ciò porterebbe a uno spreco di memoria folle. Fondamentalmente ogni posizione di memoria verrebbe utilizzata solo una volta nel corso dell'esecuzione dei programmi.

Quindi i gestori di memoria mantengono uno o più elenchi di blocchi liberi. Mantenere e cercare questi elenchi per trovare il miglior blocco possibile richiede tempo e porta a compromessi. Usi semplicemente il primo blocco che si adatta o continui a cercare nella speranza che trovi una misura esatta? Rilevi il caso in cui due blocchi adiacenti sono liberi e li unisci in un blocco libero più grande ?.

Also, why does a particular allocation alignment need to exist (for instance 8- or 16- byte) when then word size is clearly 4 bytes?

Ci sono alcuni motivi.

1. Lo standard C richiede che i blocchi di memoria allocati siano allineati in modo da soddisfare i requisiti di allineamento di tutti i tipi standard. Quindi, se la tua piattaforma richiede un allineamento a 8 byte per i doppi e lunghi, allora malloc deve allineare i suoi blocchi su un limite di 8 byte.
2. Il gestore della memoria deve memorizzare i metadati per entrambi allocati (ricorda in C puoi liberare un blocco senza specificare la sua dimensione) e blocchi liberi. La pratica normale è quella di memorizzare questi metadati accanto al blocco stesso piuttosto che avere una struttura dati separata. Per facilitare l'unione di blocchi adiacenti, è opportuno consentire la distinzione di un blocco assegnato e di un blocco libero controllando l'intestazione all'inizio del blocco.

Metti insieme questi requisiti e ha senso avere una struttura dati con due campi, ciascuno di dimensione puntatore all'inizio di ciascun blocco. Un campo specifica se il blocco è libero e se è così che cosa è il blocco successivo nella lista libera. L'altro campo specifica la dimensione del blocco.