无锁区域分配器实现-正确吗？

Question

对于一个简单的指针递增分配器（官方名称为何？），我正在寻找一种无锁算法。这似乎很简单，但我想得到一些反馈，以确保我的实现是正确的。

非线程安全实现：

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之间进行了分配，则循环会再次尝试。有什么评论吗？

- peterchen

---

@Neil - 我以前见过这样的模式。快速从类似的区域分配内存，用于操作的不同部分，并在完成后一次性释放整个内容。 - Michael

正如Michael所说，您只需整体释放块（头部）。非常适合构建大型、不可变/仅增长的数据结构。 - peterchen

这被称为线性分配器。 - Johan Kotlinski

@kotlinksi：从未听说过这个术语，但至少它是明确无误的。 - peterchen

Answer 1

您目前的代码似乎可以工作。您的代码与下面的代码行为相同，这是一个简单的模式，您可以使用它来实现任何在不产生副作用的情况下操作单个数据字的无锁算法。

do
{
    original = *data; // Capture.

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

编辑：我的原始建议使用InterlockedAdd在这里不太适用，因为您支持尝试分配并在剩余空间不足时失败。如果您使用InterlockedAdd已经修改了指针，则会导致后续的分配失败。

- Michael