锁定免费竞技场分配器实施 - 正确吗？

Question

对于简单的指针收入分配器（它们有正式名称吗？），我正在寻找无锁算法。这似乎很琐碎，但是我想获得SOEM反馈，我的Impartimaiton是否正确。

不是线程安全实现：

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之间分配，则循环再次尝试。任何意见？

Answer 1

您当前的代码似乎有效。您的代码的行为与以下代码相同，这是一个简单的模式

do
{
    original = *data; // Capture.

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

编辑：我的最初关于互锁添加的建议在这里无法正常工作，因为您支持尝试分配和失败，即使剩下的空间不足。您已经修改了指针，并导致后续分配如果使用InterlockedAdd，则会失败。