¿Cómo se escribe un asignador de memoria sin enclavamiento, seguro y seguro para subprocesos en C?

Question

¿Cómo se escribe un asignador de memoria sin enclavamiento seguro y eficaz para subprocesos en C? Por eficiente que quiero decir:

1. asignación rápida & desasignación

2. uso de memoria óptima (mínima desperdicio y no fragmentación externa)

3. overhead

   meta-datos Minimal

Answer 1

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

Este artículo presenta un asignador de memoria completamente libre de bloqueo. Utiliza solo soporte de sistema operativo ampliamente disponible e instrucciones atómicas de hardware. Ofrece disponibilidad garantizada incluso bajo terminación arbitraria y fallo de bloqueo, y es inmune a dead-lock independientemente de las políticas de programación, y por lo tanto puede ser usado incluso en controladores de interrupción y aplicaciones en tiempo real sin requerir soporte de programador especial . Además, mediante el aprovechamiento de algunas estructuras de alto nivel de Tesoro, nuestra asignador es altamente escalable, los límites de espacio explosión de un factor constante, y es capaz de evitar la falsa compartición ...

Answer 2

Depends en lo que quieres decir con eficiencia. Si mi preocupación era hacer las cosas rápido, entonces probablemente le daría a cada hilo su propio grupo de memoria separado para trabajar, y un 'malloc' personalizado que tomara la memoria de ese conjunto. Por supuesto, si mi preocupación era la velocidad, probablemente evitaría la asignación en primer lugar.

No hay una respuesta; estarás equilibrando una variedad de preocupaciones. Será prácticamente imposible obtener un asignador libre de bloqueos, pero puede hacer el bloqueo temprano y con poca frecuencia (asignando grupos grandes para cada hilo) o puede hacer los bloqueos tan pequeños y apretados que deben ser correctos.

Answer 3

Se puede utilizar un cierre libre lista y un par de cubos de diferentes tamaños.

Así:

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 son funciones de las operaciones de lista única-ligado sin bloqueo bajo Win32. Use las operaciones correspondientes en otros sistemas operativos.

inconvenientes:

• sobrecarga de sizeof(SLIST_ENTRY)
• Los cubos sólo pueden crecer de manera eficiente una vez al inicio, después de que se puede ejecutar sin memoria y tienen que pedir a los OS/otros cubos. (Otros cubos conduce a la fragmentación)
• Esta muestra es un poco demasiado fácil y debe ser extendido para manejar más casos