¿Cómo escribir un asignador de memoria sin locking, eficiente y seguro para subprocesos en C?

¿Cómo escribir un asignador de memoria sin locking, eficiente y seguro para subprocesos en C? Por eficiente quiero decir:

  1. Asignación rápida y desasignación

  2. Uso óptimo de la memoria (desperdicio mínimo y sin fragmentación externa)

  3. Gastos generales mínimos de metadatos

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

Este documento presenta un asignador de memoria completamente libre de locking. Utiliza solo soporte de sistema operativo ampliamente disponible e instrucciones atómicas de hardware. Ofrece una disponibilidad garantizada incluso bajo una terminación de subprocesos arbitraria y un fallo de locking, y es inmune al locking sin importar las políticas de progtwigción, y por lo tanto puede usarse incluso en controladores de interrupción y aplicaciones en tiempo real sin requerir soporte especial del progtwigdor. Además, al aprovechar algunas estructuras de alto nivel de Hoard, nuestro asignador es altamente escalable, limita la explosión del espacio a un factor constante y es capaz de evitar el intercambio falso …

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

No hay una sola respuesta; Usted estará equilibrando una serie de preocupaciones. Será prácticamente imposible obtener un asignador sin locking, pero puede hacer el locking antes y con poca frecuencia (asignando grupos grandes para cada subproceso) o puede hacer que los lockings sean tan pequeños y ajustados que deben ser correctos.

Puede utilizar una lista de locking libre y un par de cubos de diferentes tamaños.

Asi que :

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 para operaciones de lista de enlaces únicos sin locking bajo Win32. Utilice las operaciones correspondientes en otros sistemas operativos.

Inconvenientes:

  • sizeof( SLIST_ENTRY )
  • Los cubos solo pueden crecer de manera eficiente una vez al inicio, después de eso puede quedarse sin memoria y tener que preguntar al SO / otros cubos. (Otros cubos llevan a la fragmentación)
  • Esta muestra es un poco demasiado fácil y debe extenderse para manejar más casos