Бесплатная реализация распределения арены - правильно?

Question

Для простого распределения по указателю (у них есть официальное имя?) Я ищу алгоритм без блокировки. Это кажется тривиальным, но я хотел бы получить отзыв о SOEM, правда ли мой реализат.

НЕ ТЕРЕЗАНА Реализация:

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

Моя попытка безопасной реализации потока:

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

куда CMPXCHG обмен с блокировкой сравнения с (destination, exchangeValue, comparand) аргументы, возвращая исходное значение

Для меня выглядит хорошо - если другая поток выделяется между током и CMPXCHG, петля снова пытается. Любые комментарии?

Answer 1

Ваш текущий код, кажется, работает. Ваш код ведет себя так же, как ниже код, который представляет собой простой шаблон, который вы можете использовать для реализации любого алгоритма без блокировки, который работает на одном словом данных без побочных эффектов

do
{
    original = *data; // Capture.

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

РЕДАКТИРОВАТЬ: Мое первоначальное предложение об блокированном добавлении здесь не совсем не сработает, потому что вы поддерживаете попытки выделить и терпеть неудачу, если не хватает места. Вы уже изменили указатель и заставили последующие выборы в сборе, если вы использовали InterlockedAdd.