реализация распределителя арены без блокировки - правильно? - PullRequest
Новая
       13

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

4 голосов
/ 29 августа 2009

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

не поточно-ориентированная реализация: 

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) аргументами, возвращающий исходное значение

Выглядит хорошо для меня - если другой поток распределяет между get-current и cmpxchg, цикл повторяется. Есть комментарии?

1 Ответ

2 голосов
/ 29 августа 2009

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

do
{
    original = *data; // Capture.

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

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

...