verrouiller la mise en œuvre de allocateur libre arène - correcte?

Question

pour un allocateur simple, pointeur-incrément (ils ont un nom officiel?) Je cherche un algorithme sans blocage. Il semble trivial, mais je voudrais obtenir une rétroaction soem si mon implementaiton est correct.

non mise en œuvre threadsafe:

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

Ma tentative de fil mise en œuvre sûre:

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

où CMPXCHG est un échange avec agrafé comparer les arguments de (destination, exchangeValue, comparand), renvoyant la valeur originale

me semble bon - si un autre thread alloue entre le get-courant et cmpxchg, la boucle tente à nouveau. Tous les commentaires?

Answer 1

Votre code actuel semble fonctionner. Votre code se comporte comme le code ci-dessous, qui est un modèle simple que vous pouvez utiliser pour mettre en œuvre tout algorithme sans verrouillage qui fonctionne sur un seul mot de données sans effets secondaires

do
{
    original = *data; // Capture.

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

EDIT: Ma suggestion originale d'ajouter agrafé ne fonctionnera pas tout à fait ici parce que vous essayez d'allouer un soutien et à défaut sinon assez de place. Vous avez déjà modifié le pointeur et provoquant allocs ultérieures à l'échec si vous avez utilisé InterlockedAdd.