10

我见过一些堆栈的无锁实现......我的问题是关于可见性，而不是原子性。例如，无锁堆栈的元素（不是指针）是否必须最多 64 位？我想是的，因为你不能保证知名度。真实的例子：这个结构可以安全地从无锁容器中插入和移除吗

struct person
{
   string name;
   uint32_t age;
}

编辑：有些人对这个问题感到困惑。稍微解释一下：如果作者将人推入堆栈，读者会得到它，是否保证读者看到（内存可见性）人的正确内容。

4

7 回答 7

3

我可能错了，但我认为这个问题是不正确的。

原子指令通常处理单指针长度数据；最多有两个指针长度的数据。

一个典型的结构不能被原子操作，因为它太大了。

因此，无锁堆栈将并且只会操作指向元素的指针（AFAIK 需要在指针长度边界上对齐 - 我知道没有平台不是这种情况）。

于 2011-09-29T03:31:05.503 回答
2

我必须承认自己对这个问题有点困惑......

通过操作指向节点的指针（机器大小和对齐）来存在无锁数据结构。然后这些节点包含您的无锁数据结构的真正“内容”。该内容可以具有您想要的任意大小，因此您的结构可以放在那里。无锁数据结构的常用节点如下所示：

结构节点 { ATOMIC_PTR 下一个；内容; }

其中内容可以是您想要的任何内容，指向包含某些内容的内存的指针或直接包含某些内容的内存。可见性在这里不是问题，因为在修改无锁数据结构时，您首先要分配一个新节点，然后用所需的内容填充它，最后使用原子操作来正确设置各种涉及的指针。因为这是你做的最后一件事，而且这些操作本身通常涉及内存屏障以保证可见性和排序，所以你很好。

于 2011-10-14T08:06:12.450 回答
1

根据 SO 上的其他 QnA，

每条 x86 互锁指令（包括 CAS）都意味着一个完整的内存屏障。因此，至少在 x86 上，我们不需要关心无锁容器元素的可见性（假设它们使用 CAS。）

于 2012-02-07T09:15:27.007 回答
0

是的，可以使用该结构。因为对于无锁数据结构，您只需要某种方式以原子方式更新表示结构内部的单个值。元素或有效负载的大小不会对其无锁性质产生任何影响。

据我了解，无锁数据结构的工作方式如下：

  1. 复制数据
  2. 修改数据
  3. 原子地检查原始对象是否未被修改并更新它
  4. 否则从头开始重复

所以只要第三步可以原子地执行，一切都很好。

使元素本身可原子更新不会给您带来任何好处，因为容器必须将它们作为一个组共同管理。

于 2011-09-29T03:45:54.293 回答
0

线程安全容器（无锁或带锁）解决了列表/容器的线程安全，而不是您放入容器中的项目的线程安全。因此，无锁堆栈将确保 push 和 pop 是线程安全且无锁的，但如果您有两个不同的线程持有指向同一个结构实例的指针（例如，被压入堆栈的线程仍然持有 ponter 和另一个线程弹出堆栈）您必须使用其他一些线程安全措施来确保结构的一致性

于 2011-11-28T11:09:04.540 回答
0

注意：请仅在您实际测试此方法时将此答案标记为正确。

关于您的问题是否可以从无锁容器中安全地插入和移除以下结构：

struct person
{
   string name;
   uint32_t age;
}

如果您使用冗余编码，任何长度的多字节序列都可以安全地从无锁容器中插入/删除。让我们假设我们已经有一次操作 4 个字节（32 位）的原子指令。uint32_t age在这种情况下，我们可以像这样对字段进行编码：

struct age_t
{
   uint32_t age_low;
   uint32_t age_high;
}

该字段age_low存储 32 位的低位（例如，低 16 位）uint32_t age。该字段age_high存储剩余的高位。从概念上讲：

struct age_t
{
   uint16_t age_low;
   uint16_t id_low;
   uint16_t age_high;
   uint16_t id_high;
}

字段应该包含一个标识作者的 ID id_low。id_high

一次读取被实现为两个原子 32 位读取，如果所有id_部分彼此等价，则读取成功。如果失败，则需要重新启动读取操作。

写入实现为两个原子 32 位写入，然后读取整个age_t值。写入成功，如果：上句中提到的读取成功并且读取的ID与写入的ID相等。

关于string值：原理是一样的。您只需要弄清楚如何拆分其二进制值，就像拆分值的方式一样age。在读/写整个person结构方面也是如此。

于 2011-10-12T21:45:51.543 回答
0

如果元素不必以任何特定顺序存储在堆栈或队列中，并且如果使用线程安全队列来保存未分配的项目，以及一个线程安全的出队来保存数据槽的索引，这些数据槽包含入队/堆叠的项目。将项目写入出队需要从“未分配的插槽”队列中提取一个数字，将所需的数据写入该插槽，然后将该数字的索引排入“主”出队中。获取一个项目需要从“主”出队中提取其编号，将其复制到其他地方，然后将该编号排入“未分配插槽”队列。

这种方法的一个警告是，虽然它可能是“无锁”的，因为停止的线程不能任意延迟其他线程的进度，但线程在从一个队列获取插槽索引的时间和将它存储在另一个队列中的时间可能会使数组槽在任意时间长度内不可用。相比之下，一些用于较小数据类型的无等待堆栈或队列实现没有这种限制。线程可能在读取或写入期间从存在中消失，并且系统将处于表示读取或写入完成的有效状态，或者处于表示它从未开始的有效状态。

于 2012-02-07T23:03:40.937 回答