锁定自由竞技场分配器实现 - 正确？ [英] lock free arena allocator implementation - correct?

问题描述

一个简单的指针增量分配器（他们有一个正式名称？）我在寻找一个无锁算法。这似乎微不足道，但我想得到soem反馈，我的实现是否正确。

for a simple pointer-increment allocator (do they have an official name?) I am looking for a lock-free algorithm. It seems trivial, but I'd like to get soem feedback whether my implementaiton is correct.

不是线程安全实现：

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）参数的互锁比较交换，返回原始值

where CMPXCHG is an interlocked compare exchange with (destination, exchangeValue, comparand) arguments, returning the original value

- 如果另一个线程在get-current和cmpxchg之间分配，则循环再次尝试。任何意见？

Looks good to me - if another thread allocates between the get-current and cmpxchg, the loop attempts again. Any comments?

推荐答案

您当前的代码似乎工作。您的代码的行为与以下代码相同，这是一个简单的模式，您可以用于实现任何无锁算法，对单个数据字操作，而没有副作用。

Your current code appears to work. Your code behaves the same as the below code, which is a simple pattern that you can use for implementing any lock-free algorithm that operates on a single word of data without side-effects

do
{
    original = *data; // Capture.

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

编辑：我原来的联锁添加的建议不会在这里工作，因为你支持尝试分配和如果没有足够的空间，则失败。如果您使用InterlockedAdd，您已经修改了指针并导致后续的alloc失败。

My original suggestion of interlocked add won't quite work here because you support trying to allocate and failing if not enough space left. You've already modified the pointer and causing subsequent allocs to fail if you used InterlockedAdd.

这篇关于锁定自由竞技场分配器实现 - 正确？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！