Algoritmo per allocare in modo efficiente la memoria

Question

Algoritmo per allocare in modo efficiente la memoria

#1 da (3 voti)

2

Dati i seguenti vincoli:

Nessun multithreading.
Non interessa l'utilizzo della cache dell'hardware.

Ti stai chiedendo quale sarebbe uno schema di allocazione della memoria ragionevolmente ottimale.

Dalla mia conoscenza limitata, un'implementazione è Liste gratuite , ma dice che hanno alcuni problemi. Poi c'è la gestione degli amici e l'allocazione dinamica.

Nel complesso, la procedura sembra essere la seguente:

Assegna blocco
1. Trova spazio disponibile
2. Se ne esiste qualcuno, quindi usalo.
3. In caso contrario,
  1. Calcola le modifiche che dovresti apportare ai blocchi di memoria per soddisfare la richiesta. Ciò si traduce in una serie di movimenti di blocchi per aprire un intervallo di dimensioni appropriate per soddisfare la richiesta.
  2. Dato che sai come mescolare i blocchi, fallo.
  3. Quindi alloca la memoria.
  4. Potenzialmente spostati su altri blocchi se hai tempo, per sbarazzarti di parte della frammentazione.
4. Return

La parte centrale di questo è dove inizia a diventare difficile. Ci deve essere qualche struttura dati associata ai blocchi liberi / usati, forse, per renderlo efficiente navigare in essi. Quindi chiedendo quanto tempo possiamo dedicare alla ricerca di una posizione ideale. È come se si debba calcolare e prevedere quale sia lo scenario migliore, ma ciò richiederebbe il calcolo di un sacco di cose. Poi c'è il problema di fare una specie di GC e ripulire l'organizzazione della memoria. Tutto questo in cima al bilanciamento della memoria di copia, che è un piccolo successo di prestazioni. Chi l'avrebbe mai pensato così complesso.

Per riassumere, chiedendosi come sia una procedura standard di allocazione della memoria è piuttosto ottimale. Ho visto le implementazioni C delle variazioni di malloc ma è difficile raccogliere tutti i pezzi da quanto è grande e complesso.

Per riferimento, sto pensando a come se un ricordo fosse organizzato in questo modo:

type 1
type 2
type 3

Se sono imballati insieme, se type 1 ha bisogno di più spazio, chiedi se aggiunge alla fine:

[empty]
type 2
type 3
type 1

O se avrebbe dato più spazio spostando:

type 1
[empty]
type 2
type 3

Ma poi inizia a complicarsi. Si potrebbe attenuare questo un po ' assegnando un po' più spazio del necessario, ma alla fine diventerà troppo grande per la sua posizione, quindi come bilanciarlo. È lì che mi confondo. Vengo da JavaScript Land.

memory malloc

posta Lance Pollard 26.04.2018 - 05:53

fonte

1 risposta

Leggi altre domande sui tag memory malloc

Esistono standard per la gestione dei tergicristalli nelle applicazioni? Quale modello di progettazione per una sequenza di processori sulla stessa lista?

score 3 · Accepted Answer

Immaginiamo per un momento che tutti i tuoi Item s abbiano le stesse dimensioni. Uno schema semplice dovrebbe quindi avere un gruppo di elementi, più un bit per ciascuno per indicare se è assegnato o meno. Quindi l'algoritmo è semplicemente "loop through the pool finché non trovi un Item vuoto".

Questo è uno schema di allocazione bitmap.

Una variazione più veloce di questo schema è di avere il Item s libero da un elenco collegato. Quindi per allocare rimuovi un blocco dalla lista libera (e potresti anche usare lo spazio per il puntatore come dati, dato che non viene usato quando il blocco è allocato). Per liberarlo, aggiungilo nuovamente all'elenco collegato.

Questo è l'approccio per le liste libere che hai menzionato.

Espandendola ad allocazione di dimensioni variabili, hai l'intera area di memoria con cui lavori con un singolo "Item". Quando hai bisogno di uno spazio più piccolo, lo dividi a metà e esegui l'algoritmo in modo ricorsivo. Quando hai una misura adatta, contrassegnala come "allocata" e restituiscila. Per liberarlo, contrassegnalo come "non allocato" e unisci le aree come necessario.

Questo è lo schema di assegnazione dei buddy.

La maggior parte degli algoritmi di allocazione non esegue la compattazione, ovvero spostando i blocchi di memoria in giro per creare più spazio. Evitano invece la frammentazione. E quando la loro piscina è piena, chiedono al sistema più memoria (il sistema normalmente alloca la memoria in pagine intere (normalmente 4 KB ciascuna), quindi devono essere suddivise).

Inoltre, normalmente la garbage collection viene eseguita a un livello più alto (vedi garbage collector di munificent " tutorial " per maggiori dettagli).

Un buon rappresentante di uno schema di allocazione "comune" è malloc di Doug Lea . È usato da glibc e in molti altri posti. Include una piccola panoramica dell'algoritmo nella sua pagina.

Il fatto è che è necessario il giusto schema di allocazione per il problema in questione. Ad esempio, la malloc di Doug Lea è adattata e ottimizzata per essere ragionevolmente veloce, compatta e sicura (può rilevare alcuni errori di utilizzo), ma se tutto quello che stai facendo è l'allocazione dei blocchi fissa, probabilmente un approccio alla lista collegata sarà molto più performante.

La pagina di Wikipedia sulla gestione della memoria ha una panoramica di alcuni schemi di allocazione, ma se vuoi tutti i dettagli I consiglio davvero l'Art of Computer Programming di Knuth, che ha un'intera sezione del secondo capitolo (volume 1) dedicata a questo problema (considerando le dimensioni del libro, questo significa davvero qualcosa).