9

我正在寻找 LWARX 和 STWCX 的等价物（在 PowerPC 处理器上找到）或在 x86 平台上实现类似功能的方法。此外，哪里是了解此类事情的最佳地点（即，用于锁定/无等待编程的好文章/网站/论坛）。

编辑
我想我可能需要提供更多细节，因为假设我只是在寻找 CAS（比较和交换）操作。我想要做的是实现一个无锁引用计数系统，它带有可以被多个线程访问和更改的智能指针。我基本上需要一种在 x86 处理器上实现以下功能的方法。

int* IncrementAndRetrieve(int **ptr)
{
  整数值；
  诠释 *pval;
  做
  {
    // 获取指向值的指针
    pval = *ptr;

    // 如果为NULL，则返回NULL，智能指针
    // 然后也将变为 NULL
    如果（pval == NULL）
      返回空值；

    // 获取引用计数
    val = lwarx(pval);

    // 确保我们从中获取值的指针
    // 仍然是 'ptr' 所指的同一个
    如果（pval！= *ptr）
      继续;

    // 如果有其他线程，则通过 'stwcx' 增加引用计数
    // 做了任何可能破坏的事情，那么它应该
    //失败并重试
  } while(!stwcx(pval, val + 1));
  返回 pval;
}

我真的需要一些能够相当准确地模仿 LWARX 和 STWCX 的东西来实现这一点（我想不出一种方法来使用 CompareExchange、交换或添加我迄今为止为 x86 找到的函数）。

谢谢

4

6 回答 6

11

正如迈克尔所说，您可能正在寻找的是cmpxchg说明。

重要的是要指出，完成此操作的 PPC 方法称为加载链接/条件存储(LL/SC)，而 x86 架构使用比较和交换(CAS)。LL/SC 比 CAS 具有更强的语义，因为对条件地址处的值的任何更改都将导致存储失败，即使其他更改将值替换为与加载条件相同的值。另一方面，CAS 在这种情况下会成功。这被称为 ABA 问题（有关更多信息，请参阅 CAS 链接）。

如果您需要 x86 架构上更强的语义，您可以使用 x86s 双宽度比较和交换 (DWCAS) 指令cmpxchg8b或cmpxchg16b在 x86_64 下进行近似。这使您可以一次原子地交换两个连续的“自然大小”的单词，而不仅仅是通常的单词。基本思想是两个词之一包含感兴趣的值，另一个包含始终递增的“突变计数”。尽管这在技术上并不能消除问题，但突变计数器在尝试之间回绕的可能性非常低，以至于它是大多数用途的合理替代品。

于 2009-07-20T12:45:03.883 回答
2

x86 不像 PPC 那样直接支持“乐观并发”——相反，x86 对并发的支持基于“锁定前缀”，请参见此处。（一些所谓的“原子”指令，例如 XCHG，实际上是通过固有地断言 LOCK 前缀来获得它们的原子性，无论汇编代码程序员是否实际编写了它）。用外交的话来说，它并不完全是“防弹”的（事实上，它很容易发生事故，我会说;-)。

于 2009-07-18T16:30:21.257 回答
1

您可能正在寻找 cmpxchg 系列指令。

您需要在这些之前使用锁定指令以获得等效的行为。

在这里查看可用内容的快速概览。

你最终可能会得到类似这样的东西：

mov ecx,dword ptr [esp+4]
mov edx,dword ptr [esp+8]
mov eax,dword ptr [esp+12]
lock cmpxchg dword ptr [ecx],edx
ret 12

你应该阅读这篇论文...

编辑

针对更新后的问题，您是否想做类似Boost shared_ptr的事情？如果是这样，请查看该代码和该目录中的文件 - 它们肯定会让您入门。

于 2009-07-18T16:31:23.923 回答
1

如果您使用 64 位并限制自己说 1tb 的堆，您可以将计数器打包到 24 个未使用的最高位中。如果您有字对齐的指针，则底部 5 位也可用。

int* IncrementAndRetrieve(int **ptr)
{
  int val;
  int *unpacked;
  do
  {   
    val = *ptr;
    unpacked = unpack(val);

    if(unpacked == NULL)
      return NULL;
    // pointer is on the bottom
  } while(!cas(unpacked, val, val + 1));
  return unpacked;
}
于 2009-09-26T17:18:07.690 回答
1

不知道 LWARX 和 STWCX 是否会使整个缓存行无效，CAS 和 DCAS 会。这意味着除非您愿意丢弃大量内存（每个独立的“可锁定”指针 64 字节），否则如果您真的将软件推向压力，您将不会看到太大的改进。到目前为止，我看到的最好的结果是人们有意识地使用 64b，围绕它规划他们的结构（包装不会成为争用主题的东西），保持一切都在 64b 边界上对齐，并使用明确的读写数据屏障。缓存行失效可能会花费大约 20 到 100 个周期，这使得它成为一个更大的实际性能问题，然后只是避免锁定。

此外，您必须计划不同的内存分配策略来管理受控泄漏（如果您可以将代码划分为逻辑“请求处理” - 一个请求“泄漏”，然后在最后释放它的所有内存块）或数据化分配管理因此，一个处于争用状态的结构永远不会收到由相同结构/集合的元素重新分配的内存（以防止 ABA）。其中一些可能非常违反直觉，但要么就是这样，要么为 GC 付出代价。

于 2010-08-10T13:34:49.237 回答
0

您正在尝试做的事情不会按您期望的方式工作。您在上面实现的操作可以通过 InterlockedIncrement 函数（Win32 函数；程序集：XADD）来完成。

您的代码没有按照您的想法执行的原因是另一个线程仍然可以在第二次读取 *ptr 和 stwcx 之间更改值，而不会使 stwcx 无效。

于 2009-07-25T15:30:34.420 回答