4

Herlihy 和 Shavit 的书（多处理器编程艺术）内存回收解决方案使用 Java 的AtomicStampedReference<T>;.

要在 C++ 中为 x86_64 编写一个，我想至少需要一个 12 字节的交换操作 - 8 个用于 64 位指针，4 个用于 int。

是否有对此的 x86 硬件支持，如果没有，是否有任何关于如何在没有它的情况下进行无等待内存回收的指针？

4

7 回答 7

3

Windows 为您提供了一堆原子的互锁函数，可以用来做您想做的事情。其他平台也存在类似的功能，我相信 Boost 也有一个互锁的库。

你的问题不是很清楚，我也没有 Herlihy 和 Shavit 的副本。也许如果您详细说明或提供了概述您想要做什么的伪代码，我们可以给您一个更具体的答案。

于 2009-06-30T05:46:28.793 回答
3

是的，有硬件支持，但我不知道它是否被 C++ 库公开。无论如何，如果你不介意做一些低级的不可移植的汇编语言技巧 - 在英特尔手册中查找 CMPXCHG16B 指令。

于 2009-06-30T08:13:06.837 回答
2

好吧，希望，我有这本书，

对于其他可能提供答案的人，重点是实现这个类：

class AtomicReference<T>{
  public:
    void set(T *ref, int stamp){ ... }
    T *get(int *stamp){ ... }
  private:  
    T *_ref; 
    int _stamp;

};

以无锁方式，以便：

  • set() 以原子方式更新引用和标记。
  • get() 返回引用并将 *stamp 设置为与引用对应的标记。

请JDonner，如果我错了，请纠正我。

现在我的回答是：我不认为你可以在没有锁的情况下做到这一点（锁可以是 while(test_and_set() != ..)）。因此，对此没有无锁算法。这意味着可以通过寄存器为任何 N 构建一个无锁的 N。

如果您查看本书 pragma 9.8.1，AtomicMarkableReference 与整数标记的单个位相同。作者建议从指针中“窃取”一点以从单个单词中提取标记和指针（几乎被引用）这显然意味着他们想使用单个原子寄存器来做到这一点。

但是，可能有一种方法可以在没有它的情况下实现无等待内存回收。我不知道。

于 2009-06-30T06:26:38.150 回答
2

是的，x64 支持这个；您需要使用 CMPXCHG16B。

于 2009-10-05T15:08:59.800 回答
2

依靠指针将使用少于 64 位这一事实，您可以节省一点内存。首先，定义一个compare&set函数（这个 ASM 在 GCC 和 ICC 中工作）：

inline bool CAS_ (volatile uint64_t* mem, uint64_t old_val, uint64_t new_val)
{
  unsigned long old_high = old_val >> 32, old_low = old_val;
  unsigned long new_high = new_val >> 32, new_low = new_val;

  char res = 0;
  asm volatile("lock; cmpxchg8b (%6);"
               "setz %7; "
               : "=a" (old_low),  // 0
                 "=d" (old_high)  // 1
               : "0" (old_low),   // 2
                 "1" (old_high),  // 3
                 "b" (new_low),   // 4
                 "c" (new_high),  // 5
                 "r" (mem),       // 6
                 "m" (res)        // 7
               : "cc", "memory");
  return res;
}

然后，您需要构建一个标记指针类型。我假设一个缓存线宽度为 128 字节的 40 位指针（如 Nehalem）。与缓存行对齐将通过减少错误共享、争用等来极大地提高速度；在某些情况下，这显然需要使用更多内存。

template <typename pointer_type, typename tag_type, int PtrAlign=7, int PtrWidth=40>
struct tagged_pointer
{
  static const unsigned int PtrMask = (1 << (PtrWidth - PtrAlign)) - 1;
  static const unsigned int TagMask = ~ PtrMask;

  typedef unsigned long raw_value_type;

  raw_value_type raw_m_;

  tagged_pointer () : raw_m_(0) {}
  tagged_pointer (pointer_type ptr) { this->pack(ptr, 0); }
  tagged_pointer (pointer_type ptr, tag_type tag) { this->pack(ptr, tag); }

  void pack (pointer_type ptr, tag_type tag)
  {
    this->raw_m_ = 0;
    this->raw_m_ |= ((ptr >> PtrAlign) & PtrMask);
    this->raw_m_ |= ((tag << (PtrWidth - PtrAlign)) & TagMask);
  }

  pointer_type ptr () const
  {
    raw_value_type p = (this->raw_m_ & PtrMask) << PtrAlign;
    return *reinterpret_cast<pointer_type*>(&p);
  }

  tag_type tag () const
  {
    raw_value_type t = (this->raw_m_ & TagMask) >> (PtrWidth - PtrAlign_;
    return *reinterpret_cast<tag_type*>(&t);
  }
};

我没有机会调试这段代码，所以你需要这样做，但这是一般的想法。

于 2010-05-24T17:59:57.630 回答
2

注意，在 x86_64 架构和 gcc 上，您可以启用 128 位 CAS。它可以通过-mcx16gcc 选项启用。

int main()
{
   __int128_t x = 0;
   __sync_bool_compare_and_swap(&x,0,10);
   return 0;
}

编译：

gcc -mcx16 file.c
于 2011-10-17T11:42:03.227 回答
1

cmpxchg16b 操作提供了预期的操作，但要注意一些较旧的 x86-64 处理器没有此指令。

然后，您只需要使用计数器、指针和 asm-inline 代码构建一个实体。我在这里写了一篇关于这个主题的博客文章：实现通用双字比较和交换

不过，如果您只是想防止提前释放和 ABA 问题，则不需要此操作。危险指针更简单，不需要特定的 asm 代码（只要您使用 C++11 原子值。）我有一个关于 bitbucket 的 repo，其中包含各种无锁算法的实验实现：无锁实验（请注意，所有这些实现都是用于实验的玩具，而不是可靠且经过测试的生产代码。）

于 2013-07-20T18:00:22.617 回答