Come scrivere un allocatore di memoria thread-safe ed efficiente, senza lock in C?

Question

Come scrivere un allocatore di memoria thread-safe ed efficiente senza lock in C? Da efficiente intendo:

1. veloce allocazione & deallocazione

2. utilizzo della memoria ottimale (spreco minimo e nessuna frammentazione esterna)

3. sovraccarico

   Minimal metadati

Answer 1

http://www.research.ibm.com/people/m/michael/pldi-2004.pdf

Questo documento presenta un allocatore di memoria completamente senza blocchi. Utilizza solo il supporto del sistema operativo ampiamente disponibile e le istruzioni atomiche dell'hardware. Offre una disponibilità garantita anche in caso di interruzione arbitraria del thread ed è immune al dead-lock indipendentemente dalle politiche di pianificazione, e quindi può essere utilizzato anche in gestori di interrupt e applicazioni in tempo reale senza richiedere il supporto speciale dello scheduler . Inoltre, sfruttando alcune strutture di alto livello dal Hoard, la nostra allocatore è altamente scalabile, limiti di spazio ingrandimento di un fattore costante, ed è in grado di evitare falsi condivisione ...

Answer 2

Depends su cosa intendi per efficienza. Se la mia preoccupazione era di rendere le cose veloci, allora probabilmente darei a ciascun thread il proprio pool di memoria separato con cui lavorare, e un 'malloc' personalizzato che prendesse memoria da quel pool. Certo, se la mia preoccupazione fosse la velocità, probabilmente eviterei l'allocazione in primo luogo.

Non c'è una risposta; dovrai bilanciare una serie di problemi. Sarà praticamente impossibile ottenere un allocatore lock-free, ma è possibile effettuare il lock in anticipo e raramente (allocando pool di grandi dimensioni per ogni thread) oppure è possibile rendere i blocchi così piccoli e stretti da essere corretti.

Answer 3

È possibile utilizzare un blocco gratuito elenco e un paio di secchi di diverse dimensioni.

Quindi:

typedef struct 
{ 
    union{ 
     SLIST_ENTRY entry; 
    void* list; 
}; 
byte mem[]; 
} mem_block; 

typedef struct 
{ 
    SLIST_HEADER root; 
} mem_block_list; 

#define BUCKET_COUNT 4 
#define BLOCKS_TO_ALLOCATE 16 

static mem_block_list Buckets[BUCKET_COUNT]; 

void init_buckets() 
{ 
    for(int i = 0; i < BUCKET_COUNT; ++i) 
    { 
     InitializeSListHead(&Buckets[i].root); 
     for(int j = 0; j < BLOCKS_TO_ALLOCATE; ++j) 
     { 
      mem_block* p = (mem_block*) malloc(sizeof(mem_block) + (0x1 << BUCKET_COUNT) * 0x8); 
      InterlockedPushEntrySList(&Buckets[i].root, &p->entry); 
     } 
    } 
} 

void* balloc(size_t size) 
{ 
    for(int i = 0; i < BUCKET_COUNT; ++i) 
    { 
     if(size <= (0x1 << i) * 0x8) 
     { 
      mem_block* p = (mem_block*) InterlockedPopEntrySList(&Buckets[i].root); 
      p->list = &Buckets[i]; 
     } 
    } 

    return 0; // block to large 
} 

void bfree(void* p) 
{ 
    mem_block* block = (mem_block*) (((byte*)p) - sizeof(block->entry)); 
    InterlockedPushEntrySList(((mem_block_list*)block)->root, &block->entry); 
} 

SLIST_ENTRY, InterlockedPushEntrySList, InterlockedPopEntrySList, InitializeSListHead sono funzioni per le operazioni-linked-lista unica senza blocchi sotto Win32. Utilizzare le operazioni corrispondenti su altri sistemi operativi.

Svantaggi:

• Overhead di sizeof(SLIST_ENTRY)
• I secchi possono crescere in modo efficiente solo una volta alla partenza, dopo che si può esaurire la memoria e devono chiedere agli OS/altri secchi. (Altri secchi porta ad frammentazione)
• questo esempio è un po 'troppo facile e deve essere esteso per gestire più casi