问题标签 [lockless]

在使用无锁队列实现来存储指向一组预分配缓冲区的指针时，我发现一些缓冲区仍在由一个线程写入，而另一个线程开始使用它。我已经用内存屏障保护了缓冲区的写入和读取，但它似乎不起作用。

线程 1 循环：

线程 2 循环：

一段时间后我得到“失败”作为输出，这意味着线程 2 看到 A 和 B 块的无序执行。我希望这些事情有条不紊地发生。我该如何解决？（假设 time_diff 总是返回一个正数）

队列来源：http ://pastebin.com/raw.php?i=PFBzMPPF

完整来源：https ://docs.google.com/file/d/0B8gY3VVJJr1IMktobnhYelBva2c/edit?usp=docslist_api

I've been working on a lockless c++11 fifo buffer. And I've almost got it. However one small detail has gotten the better of me. The buffer has a head pointed to by:

Of the type:

And then there are the produce:

And consume:

Functions.

All seems to work well. However I reckon there is one flaw. If all nodes are consumed whilst executing a produce. The data will be added to the last element. Even though the element already has been deleted.

To be more precise, if this line has been executed:

And the loaded node wasn't zero. The next element of the last node will be changed. Regardless of whether the nodes are being deleted in the meantime or not. The nodes will not be physically deleted as long as the produce function is being excuted, because of the shared pointers.

However, the main pointer will be set to NULL. And therefore the new node will be deleted as soon as the produce function is exited.

Would anybody happen to know a solution for this problem:)?

我为这篇长篇博文先道歉，但正如你可能看到的那样，我已经考虑这个问题已经有一段时间了，我觉得在我的脑袋爆炸之前我需要其他人的一些意见:-)

一段时间以来，我一直在尝试各种方法来构建满足以下所有标准的游戏引擎：

• 对象更新和对象渲染完全分离
• 完全决定论
• 以个人速度更新和渲染
• 不阻塞共享资源

对象更新和对象渲染完全分离

对象更新和对象渲染的分离似乎对于确保在向图形 API 发送数据和交换缓冲区时优化资源使用至关重要。即使您想确保完全并行性以使用 CPU 的多个内核，似乎仍然必须管理这种分离。

完全决定论

许多游戏类型，尤其是多人游戏版本，必须确保完全确定性。否则玩家将体验到同一游戏的不同状态，有效地打破了游戏逻辑。游戏回放也需要确定性。并且它对于其他目的非常有用，在这些目的中，每次模拟运行在给定相同的起始条件和输入的情况下每次都产生相同的结果是很重要的。

以个人速度更新和渲染

这确实是完全确定性的先决条件，因为您不能让模拟依赖于渲染速度（即各种显示器刷新率、图形适配器速度等）。在最佳条件下，更新速度应设置为某个固定间隔（例如，每秒 25 次更新 - 可能会更少，具体取决于更新类型），并且渲染速度应为客户端的显示器刷新率/图形适配器允许的任何值。

这意味着应该允许渲染速度高于更新速度。虽然这听起来像是一种浪费，但有一些已知的技巧可以确保增加的渲染周期不会浪费（内插/外推），这意味着更快的监视器/适配器将获得更令人愉悦的视觉体验。

但是，还必须允许渲染速度低于更新速度，即使这确实会导致浪费更新周期 - 至少添加的更新周期不会全部呈现给用户。然而，这对于确保流畅的多人游戏体验是必要的，即使其中一个客户端中的渲染由于某种原因突然缓慢爬行也是如此。

不阻塞共享资源

如果要实现上述其他标准，还必须遵循我们不能允许渲染等待更新，反之亦然。当然，很明显，当 2 个不同的线程共享对资源的访问并且一个线程正在更新其中一些资源时，就不可能保证永远不会发生阻塞。但是，可以将这种阻塞保持在绝对最小值 - 例如，在更新对象队列和先前渲染对象队列之间切换指针引用时。

所以...

我对这里所有熟练的人的问题是：我要求太多了吗？

我一直在许多网站上阅读有关这些不同主题的想法。但是，我所看到的建议似乎总是忽略了其中的一部分。也许原因是你不能在不妥协的情况下拥有这一切。

很久以前，当我把我的想法放在这个线程中时，我开始了这个看似常见的任务： 关于渲染循环策略的思考

那时我的第一个天真假设是，更新和读取是否同时发生并不重要，因为这种变化对象状态是如此之小，以至于您不应该注意到一个对象是否偶尔领先另一个对象。

现在我有点聪明了，但有时仍然感到困惑。

一种可以满足我所有愿望的方法的最有希望和最详细的描述是：http: //blog.slapware.eu/game-engine/programming/multithreaded-renderloop-part1/ 一个三态模型将确保渲染器始终可以选择一个新的队列进行渲染，而无需等待（切换指针引用时可能只有一微秒）。同时，更新程序总是可以访问构建下一个状态树所需的 2 个队列（1 个队列用于创建/更新下一个状态，1 个队列用于读取先前状态 - 即使渲染器将其读取为出色地）。

我最近有时间对此进行示例实现，并且效果很好，但是有两个问题。

• 一个是必须处理对所有相关对象的多个引用的小问题
• 另一个更严重（除非我太需要了）。这就是在给定快速屏幕刷新率的情况下，外推法（与内插法相反）用于维持视觉上令人愉悦的状态表示。虽然这两种方法都可以显示偏离可靠计算的对象状态的状态，但在我看来，当预测无法代表现实时，外推法会产生更多可见的伪影。我的立场似乎得到了支持： http ://gafferongames.com/networked-physics/snapshots-and-interpolation/ 据我所知，不可能在三态设计中实现插值，因为它要求渲染器始终具有对 2 个队列的读取访问权限，以计算两个已知状态之间的中间状态。

因此，我正在尝试扩展 slapware-blog 上建议的三态模型，以利用插值而不是外推 - 同时尝试简化多参考结构。虽然在我看来是可能的，但我想知道价格是否太高。为了实现我所有的目标，我需要拥有

• 2 个由渲染器独占的队列（或状态）（它们可以被另一个线程用于只读目的，但在渲染期间从不更新或切换
• 1 个具有最新更新状态的队列（或状态）准备好切换到渲染器，当它完成渲染当前场景时
• 1 个队列（或状态），下一帧由更新程序构建/更新
• 1 个队列（或状态），包含上次构建/更新的帧的副本。这与上次发送到渲染器的状态相同，因此更新器应该可以访问该队列/状态以读取先前的状态，并且渲染器应该可以访问以渲染状态。

因此，这意味着我应该始终保留 4 个渲染状态副本，以使该设计能够平稳、无锁定、确定地运行。

我担心我想太多了。因此，如果你们中的任何人建议将我拉回地面，或建议可以改进的地方，对设计的批评，或者可能是对解释如何实现这些目标的良好资源的引用，或者为什么会这样或不是一个好主意 - 请和他们一起打我:-)

所以，假设我有一个struct A { int val1; int val2}; 和一个std::queue<A> fifo

两个线程，Reader线程：从A读取所有内容，并清除。写入线程：一次写入一个 A 到队列。

std::queue 是否足以维护一个具有一个读取器和一个写入器的无锁线程安全 fifo 容器？如果没有，任何其他 stl 容器可以工作吗？dequeue 是 std::queue 中的默认底层。

我有一个生产者将作业一个接一个地放入队列中，另一个线程一个接一个地从队列中取出作业。我在网上的某个地方看到它可以无锁地完成。什么是正确的做法？无锁实现通常更难维护吗？假设这个项目的性能并不重要，正确性更重要。

我很感兴趣，因为这个值会影响我想要使用（很棒的）ldrex/strex同步原语的数据结构在内存中的位置。

ARMv7-M 架构参考说：

标记内存块的大小称为 Exclusives 预留粒度。Exclusives 预留粒度在以下之间实现定义：

• 一个词，在 a == 2 的实现中
• 512 字，在 a == 11 的实现中。

因此，对于给定的实现，例如 STM32F407，我应该能够找到使用的值。但我不能，在我浏览过的各种文件中。

有人知道吗？还有，你是怎么找到的？

在阅读Albahari's Threading in C#时，我注意到“无锁更新”模式SpinWait在循环结束时使用 a ：

注意最后的spinWait.SpinOnce()调用。这个调用是否只需要在单线程环境中产生线程，还是有其他目的？

根据 MSDN，Stopwatch类实例方法对于多线程访问是不安全的。这也可以通过检查各个方法来确认。

但是，由于我只需要在我的代码中的几个位置使用简单的“经过时间”的计时器，我想知道它是否仍然可以无锁地完成，使用类似的东西：

由于_stopwatch.ElapsedMilliseconds基本上是对 的调用QueryPerformanceCounter，我假设从多个线程调用它是安全的吗？与常规的不同之Stopwatch处在于，这个类基本上一直在运行，所以我不需要像以前那样保持任何附加状态（“运行”或“停止”）Stopwatch。

（更新）

在@Scott 在下面的答案中提出建议后，我意识到它Stopwatch提供了一个简单的静态GetTimestamp方法，它返回原始QueryPerformanceCounter刻度。换句话说，代码可以修改成这样，这是线程安全的：

澄清一下，这段代码的想法是：

1. 有一种简单快捷的方法来检查自某个操作/事件以来是否已经过去了时间，
2. 如果从多个线程调用方法，则不应破坏状态，
3. 必须对操作系统时钟变化不敏感（用户变化、NTP 同步、时区等）

我会像这样使用它：

对于具有多个读取器线程和单个写入器线程的场景，允许读取器读取稍微过时的数据，我编写了一个无锁控制流，如下所示，其最基本的伪代码形式如下所示：

让我们调用MAX_READING_DURATION一个调用read()可以完成的最长时间，以及一个调用可以完成MIN_WRITING_DURATION的最短时间write()。

现在，shared_pointer保证是原子的，只要MAX_READING_DURATION < ELEMENT_COUNT(ARRAY) * MIN_WRITING_DURATION，这个方案应该是完全安全的。

还是我忽略了什么？如果不是，我敢肯定这是众所周知的事情，我想知道正确的术语，所以当我向其他人解释/倡导这种方法时，我可以使用它。

我试图了解 Linux 内核中的无锁列表。这是在 llist.h 中定义的。为什么他们有两个结构，来定义一个列表：

为什么不只有一个具有指向下一个节点的指针的结构呢？它类似于内核中的双向链表实现。