Implementierung der freien Arena Allocator - Richtig?

Question

Für einen einfachen Allocator für Zeiger-Inkremente (haben sie einen offiziellen Namen?), suche ich nach einem schlossfreien Algorithmus. Es scheint trivial zu sein, aber ich möchte soem Feedback erhalten, ob mein Implementa -Arten korrekt ist.

Nicht Threadsafe -Implementierung:

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;
}

Mein Versuch, einen Thread -Safe -Implementierung zu erzielen:

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;
}

wo CMPXCHG ist ein unverstockter Vergleichsaustausch mit (destination, exchangeValue, comparand) Argumente, die den ursprünglichen Wert zurückgeben

Sieht gut aus für mich - Wenn ein anderer Thread zwischen Treffen und CMPXchg zugibt, versucht der Schleifen erneut. Irgendwelche Kommentare?

Answer 1

Ihr aktueller Code scheint zu funktionieren. Ihr Code verhält sich genauso wie der folgende Code. Dies ist ein einfaches Muster, das Sie für die Implementierung eines lock-freien Algorithmus verwenden können, der auf einem einzigen Datenwort ohne Nebenwirkungen arbeitet

do
{
    original = *data; // Capture.

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

Bearbeiten: Mein ursprünglicher Vorschlag von Interlocked Add funktioniert hier nicht ganz, da Sie versuchen, zu versuchen, zuzuweisen und zu versagen, wenn nicht genug Platz übrig. Sie haben den Zeiger bereits geändert und nachfolgende Allocs versagen, wenn Sie InterlockedAdd verwendet haben.