bloccare implementazione libera arena allocatore - corretta?

Question

per un semplice puntatore allocatore di incremento (non hanno un nome ufficiale?) Sto cercando un algoritmo senza blocchi. Sembra banale, ma mi piacerebbe ottenere un feedback soem se la mia implementaiton è corretta.

Non threadsafe implementazione:

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

Il mio tentativo di un filo realizzazione sicura:

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

dove CMPXCHG è uno scambio interbloccato confrontare con argomenti (destination, exchangeValue, comparand), restituendo il valore originale

Sembra buono per me - se un altro thread alloca tra il get-corrente e cmpxchg, il ciclo tenta di nuovo. Eventuali commenti?

Answer 1

Il codice attuale sembra funzionare. Il tuo codice si comporta come il codice qui sotto, che è un modello semplice che è possibile utilizzare per l'attuazione di qualsiasi algoritmo senza blocchi che opera su una sola parola di dati senza effetti collaterali

do
{
    original = *data; // Capture.

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

EDIT: Il mio suggerimento originale di interblocco aggiuntivo non sarà del tutto lavorare qui perché il supporto cercando di allocare e non riuscendo, se non abbastanza spazio lasciato. Hai già modificato il puntatore e causando Allocati successivi a fallire se si è utilizzato InterlockedAdd.