Lock Free Arena Asignator Implementation - ¿Correcto?

Question

Para un asignador simple de incremento de puntero (¿tienen un nombre oficial?) Estoy buscando un algoritmo sin bloqueo. Parece trivial, pero me gustaría recibir comentarios de SOEM si mi implementación es correcto.

no implementación de hilo:

byte * head;  // current head of remaining buffer
byte * end;   // end of remaining buffer

void * Alloc(size_t size)
{
   if (end-head < size)
     return 0; // allocation failure

   void * result = head;
   head += size;
   return head;
}

Mi intento de implementación segura de un hilo:

void * Alloc(size_t size)
{
  byte * current;
  do 
  {
     current = head;
     if (end - current < size)
        return 0;  // allocation failure
  } while (CMPXCHG(&head, current+size, current) != current));
  return current;
}

dónde CMPXCHG es un intercambio de comparación entrelazado con (destination, exchangeValue, comparand) argumentos, devolviendo el valor original

Me parece bien: si otro hilo se asigna entre la corriente de entrada y CMPXCHG, el bucle intenta nuevamente. ¿Algún comentario?

Answer 1

Su código actual parece funcionar. Su código se comporta lo mismo que el siguiente código, que es un patrón simple que puede usar para implementar cualquier algoritmo sin bloqueo que funcione en una sola palabra de datos sin efectos secundarios

do
{
    original = *data; // Capture.

    result = DoOperation(original); // Attempt operation
} while (CMPXCHG(data, result, original) != original);

EDITAR: Mi sugerencia original de ADD entrelazado no funcionará aquí porque admite tratar de asignar y fallar si no queda suficiente espacio. Ya ha modificado el puntero y ha causado que las asignaciones posteriores fallaran si usó Interlockedadd.