Comment écrire un allocateur de mémoire sans verrous et efficace, sans verrou, en C?

Question

Comment écrire un allocateur de mémoire sans verrous et efficace, sans verrou en C? Par efficace, je veux dire:

1. allocation rapide & désallocation

2. utilisation optimale de la mémoire (de perte minimale et pas de fragmentation externe)

3. tête méta-données minimales

Answer 1

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

Cet article présente un allocateur de mémoire complètement verrouillage libre. Il utilise uniquement un support de système d'exploitation largement disponible et des instructions atomiques matérielles. Il offre une disponibilité garantie même en cas de terminaison et de panne, et il est protégé contre les dead lock quelles que soient les règles de programmation. Il peut donc être utilisé même dans les gestionnaires d'interruptions et les applications en temps réel sans nécessiter de prise en charge de planificateur. . En outre, en tirant parti des structures de haut niveau de Hoard, notre allocateur est hautement évolutive, limite l'espace blowup à un facteur constant, et est capable d'éviter le partage de faux ...

Answer 2

Depends sur ce que vous entendez par efficacité. Si mon souci était de rendre les choses rapides, alors je donnerais probablement à chaque thread son propre pool de mémoire séparé, et un 'malloc' personnalisé qui prendrait la mémoire de ce pool. Bien sûr, si mon souci était la rapidité, j'éviterais probablement la répartition en premier lieu.

Il n'y a pas une seule réponse; vous équilibrez une gamme de préoccupations. Il sera pratiquement impossible d'obtenir un allocateur sans verrou, mais vous pouvez soit effectuer le verrouillage tôt et peu souvent (en allouant de grands pools pour chaque thread), soit rendre les verrous si petits et serrés qu'ils doivent être corrects.

Answer 3

Vous pouvez utiliser un verrou libre liste et quelques seaux de différentes tailles.

Alors:

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 sont des fonctions de verrouillage sans opérations unique liste chaînée sous Win32. Utilisez les opérations correspondantes sur d'autres systèmes d'exploitation.

Inconvénients:

• aériennes de sizeof(SLIST_ENTRY)
• Les seaux ne peuvent se développer efficacement une fois au début, après que vous pouvez exécuter de mémoire et doivent demander à l'OS/d'autres seaux. (D'autres seaux conduit à la fragmentation)
• Cet échantillon est un peu trop facile et doit être étendue à traiter davantage d'affaires