gestione della memoria intelligente con operazioni di tempo costante?

Question

Consideriamo un segmento di memoria (la cui dimensione può aumentare o ridurre, come un file, quando necessario) su cui è possibile eseguire due operazioni di base di allocazione di memoria che coinvolge i blocchi di dimensioni fisse:

• assegnazione di un blocco
• liberando un blocco allocato in precedenza che non viene più utilizzata.

Inoltre, come requisito, il sistema di gestione della memoria non è consentito di muoversi blocchi attualmente allocati. Loro indice / indirizzo deve rimanere invariata

L'algoritmo di gestione della memoria più semplice sarebbe incrementare un contatore globale (con valore iniziale 0) Utilizzando il nuovo valore come un indirizzo per l'assegnazione successiva. Tuttavia, questo non permetterà mai di accorciare il segmento in cui solo a pochi isolati assegnati rimangono.

Una migliore approccio:. Tenere il banco, ma mantenere un elenco di blocchi deallocato (che può essere fatto in tempo costante) e usarlo come fonte per nuove assegnazioni fino a quando non è vuota

Qual è il prossimo? C'è qualcosa di intelligente che può essere fatto, ancora con i vincoli di allocazione del tempo costante e deallocazione, che avrebbe mantenuto il segmento di memoria più breve possibile?

(Un obiettivo potrebbe essere quello di monitorare il blocco attualmente non assegnata con l'indirizzo più piccolo, ma non sembra essere fattibile in tempo costante ...)

Answer 1

Con blocchi di dimensione fissa, quello che hai descritto è un lista libera . Si tratta di una tecnica molto comune, con il seguente colpo di scena: la lista dei blocchi liberi viene immagazzinata nelle libere blocchi stessi. Nel codice C, sarebbe simile a questa:

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

Questo funziona bene finché tutti i blocchi allocati hanno la stessa dimensione, e che la dimensione è un multiplo della dimensione di un puntatore, in modo che l'allineamento è conservato. Allocazione e deallocazione sono tempo costante (cioè come tempo costante come accessi alla memoria e aggiunte elementare - in un moderno computer, un accesso di memoria può coinvolgere cache miss e anche memoria virtuale, quindi accessi al disco, in modo che il "costante di tempo" può essere molto grande). Non v'è alcun sovraccarico di memoria (non in più puntatori per-blocco o cose del genere, i blocchi allocati sono contigui). Inoltre, il puntatore di allocazione raggiunge un dato punto solo se, in una sola volta, che molti blocchi dovevano essere assegnati: poiché l'assegnazione preferisce usare la lista libera, il puntatore di allocazione viene aumentata solo se lo spazio sottostante il puntatore corrente è orologio pieno. In questo senso, questo è un ottimale tecnica.

decrescente il puntatore di allocazione dopo un rilascio può essere più complessa, dal momento che i blocchi liberi possono essere identificate in modo affidabile solo seguendo la lista libera, che attraversa in ordine imprevedibile. Se diminuendo la dimensione grande segmento quando possibile è importante per voi, si può desiderare di utilizzare una tecnica alternativa, con l'ulteriore overhead: tra due blocchi allocati, si inserisce un "buco". I fori sono collegati tra loro con una lista doppiamente collegata, in modo memoria. Avete bisogno di un formato di dati per un buco tale che è possibile individuare l'indirizzo di partenza buco da sapere dove finisce, e anche la dimensione del foro se si sa dove inizia il buco nella memoria. Poi, quando si rilascia un blocco, si crea un buco, che si unisce con il prossimo ed i fori precedenti, la ricostruzione (ancora in tempo costante) l'elenco ordinato di tutti i fori. L'overhead è quindi circa due parole puntatore-dimensionata per blocco assegnato; ma, a quel prezzo, è possibile rilevare in modo affidabile la presenza di un "buco finale", cioè un'occasione per diminuire la dimensione grande del segmento.

Ci sono molte possibili variazioni. Una buona relazione introduttiva è allocazione dinamica di memoria: un sondaggio e Critical Review da Wilson et al.

Answer 2

Questa risposta è sulle tecniche di gestione della memoria generiche. Mi mancava che la questione chiede il caso in cui tutti i blocchi hanno la stessa dimensione (e sono allineati).

---

Le strategie di base che è necessario conoscere sono di prima forma, il prossimo-fit, best-fit, e il amico sistema . Ho scritto un breve riassunto una volta per un corso ho insegnato, ho la speranza è leggibile. Io punto lì per un abbastanza esaustivo sondaggio .

In pratica vedrete varie modifiche di queste strategie di base. Ma nessuno di questi è in realtà costante di tempo! Non credo che sia possibile nel peggiore dei casi, utilizzando una quantità limitata di memoria.

Answer 3

Si consiglia di dare un'occhiata al ammortizzato analisi in particolare array dinamici. Anche se le operazioni non sono realmente fatto in tempo costante in ogni fase, nel lungo periodo sembra che sia il caso.