代码之家  ›  专栏  ›  技术社区  ›  peterchen

无锁竞技场分配器实现-正确吗?

  •  5
  • peterchen  · 技术社区  · 16 年前

    对于一个简单的指针增量分配器(它们有正式名称吗?),我正在寻找一种无锁算法。这看起来微不足道,但我想得到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)

    在我看来,这很好——如果另一个线程在get current和cmpxchg之间分配,循环将再次尝试。有什么意见吗?

    1 回复  |  直到 16 年前
        1
  •  2
  •   Michael    16 年前

    do
    {
        original = *data; // Capture.
    
        result = DoOperation(original); // Attempt operation
    } while (CMPXCHG(data, result, original) != original);