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

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

  1. Allocation et désallocation rapides

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

  3. Surcharge de métadonnées minimale

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

    Ce document présente un allocateur de mémoire sans locking. Il utilise uniquement le support de système d’exploitation largement disponible et les instructions atomiques matérielles. Il offre une disponibilité garantie même en cas de terminaison de threads arbitraire et d’échecs en cas de panne. Il est à l’abri du blocage, quelles que soient les règles de planification. Il peut donc être utilisé même dans les gestionnaires d’interruptions et les applications en temps réel sans nécessiter un support spécial du planificateur. En outre, en exploitant certaines structures de haut niveau de Hoard, notre allocateur est hautement évolutif, limite l’explosion d’espace à un facteur constant et est capable d’éviter le faux partage …

    Cela dépend de ce que vous entendez par efficacité. Si mon souci était d’accélérer les choses, je donnerais probablement à chaque thread son propre pool de mémoire distinct, ainsi qu’un «malloc» personnalisé utilisant la mémoire de ce pool. Bien sûr, si ma préoccupation était la rapidité, j’éviterais probablement l’allocation en premier lieu.

    Il n’y a pas de réponse unique. vous allez trouver un équilibre entre diverses préoccupations. Il sera pratiquement impossible d’obtenir un allocateur sans locking, mais vous pouvez soit effectuer le locking tôt et rarement (en allouant des pools importants pour chaque thread), soit créer des verrous si petits et serrés qu’ils doivent être corrects.

    Vous pouvez utiliser une liste sans verrou et deux ou trois seaux de tailles différentes.

    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 permettant d’effectuer des opérations sans liste et sans locking sur une seule liste liée sous Win32. Utilisez les opérations correspondantes sur d’autres systèmes d’exploitation.

    Désavantages :

    • sizeof( SLIST_ENTRY ) généraux de sizeof( SLIST_ENTRY )
    • Les seaux ne peuvent grandir efficacement qu’une fois au début, après quoi vous pouvez manquer de mémoire et vous devez demander au système d’exploitation / aux autres seaux. (D’autres seaux mènent à la fragmentation)
    • Cet exemple est un peu trop facile et doit être étendu pour traiter plus de cas