问题标签 [lockless]

我真的不明白如何使某些数据结构无锁。例如，如果您有一个链表，那么您可以使用互斥锁围绕操作，或者如果在您忙于将新节点重新链接在一起时执行另一个线程，您可能会遇到竞争条件。

“无锁”的概念（我理解它并不意味着“无锁”，而是意味着线程可以在不等待其他线程完成的情况下继续前进）只是没有意义。

有人可以向我展示一个使用堆栈、队列或链表等实现为“无锁”的简单示例，因为我无法理解如何在不干扰其他线程生产力的情况下防止竞争条件？这两个目标肯定相互矛盾吗？

想象一个场景：2 个核心在同一时间做什么 CaS。处理器需要读取一个旧值，然后放置一个新值，旧值相同。如果他们同时阅读呢？或者那里的变量上是否有任何类型的锁定，以防止其他内核读取？

这就是我到目前为止所拥有的，我是否朝着正确的方向前进？目的是在一个线程比其他线程更频繁地需要访问单例的情况下使用它，因此无锁代码是可取的，我想使用原子变量进行练习。

I need a data structure to store 500k keys, each one with some associated data. 150 Threads will be running concurrently & accessing the keys. Once in a day I need to update the data structure since there may be some manipulation operation, say the key is deleted, new key is added or the data is changed. When the data structure updation is in progress I can not block any of the 150 threads from accessing it. I don't want to use current hash implementations like memcache or redis since the number of keys may grow in future & I want in-memory access for faster lookup? Instead will prefer some data structure implementation in C/C++.

我一直在尝试（我的尝试）一个无锁的多生产者多消费者环形缓冲区。这个想法的基础是使用 unsigned char 和 unsigned short 类型的固有溢出，将元素缓冲区固定为这些类型中的任何一种，然后你有一个自由循环回到环形缓冲区的开头。

问题是 - 我的解决方案不适用于多个生产者（尽管它适用于 N 个消费者，也适用于单个生产者单个消费者）。

写入的主要思想是使用临时索引“scratchIndex”，它充当伪锁，以在任何时候只允许一个生产者复制构造到元素缓冲区，然后更新 writeIndex 并允许任何其他生产者取得进展. 在我因暗示我的方法是“无锁”而被称为异教徒之前，我意识到这种方法并不是完全无锁的，但在实践中（如果可行的话！）它比使用普通互斥锁要快得多！

我在这里知道一个（更复杂的）MPMC ringbuffer 解决方案http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue，但我真的在尝试我的想法然后比较反对这种方法并找出每种方法的优点（或者实际上我的方法是否完全失败了！）。

我尝试过的事情；

• 使用 compare_exchange_weak
• 使用与我想要的行为匹配的更精确的 std::memory_order
• 在我拥有的各种索引之间添加缓存线垫
• 制作元素 std::atomic 而不仅仅是元素数组

我确信这归结为我脑海中的一个基本段错误，即如何使用原子访问来绕过使用互斥体，我将完全感谢谁能指出哪些神经元在我的脑海中严重失灵！:)

我正在尝试使用 C++11 原子原语来实现某种原子“线程计数器”。基本上，我有一个关键的代码部分。在此代码块中，任何线程都可以从内存中自由读取。但是，有时，我想做一个重置或清除操作，将所有共享内存重置为默认的初始化值。

这似乎是使用读写锁的绝佳机会。C++11 不包括开箱即用的读写互斥锁，但也许更简单的东西会做。我认为这个问题将是一个更好地熟悉 C++11 原子原语的好机会。

所以我想了一会儿这个问题，在我看来，我所要做的就是：

1. 每当线程进入临界区时，增加一个原子计数器变量

2. 每当线程离开临界区时，递减原子计数器变量

3. 如果一个线程希望将所有变量重置为默认值，它必须自动等待计数器为 0，然后自动将其设置为某个特殊的“清除标志”值，执行清除，然后将计数器重置为 0。

4. 当然，希望增加和减少计数器的线程还必须检查清除标志。

所以，我刚才描述的算法可以用三个函数来实现。第一个函数，increment_thread_counter()必须始终在进入临界区之前调用。第二个函数，decrement_thread_counter()，必须总是在离开临界区之前被调用。最后，只有当线程计数器 == 0时，clear()才能从临界区外部调用该函数。

这就是我想出的：

鉴于：

1. 线程计数器变量，std::atomic<std::size_t> thread_counter
2. 一个常数clearing_flag设置为std::numeric_limits<std::size_t>::max()

...

据我所知，这应该是线程安全的。请注意，该decrement_thread_counter函数不应该需要任何同步逻辑，因为它是一个increment()总是在之前调用的给定decrement()。因此，当我们到达 时decrement()，thread_counter 永远不会等于 0 或clearing_flag。

无论如何，由于 THREADING IS HARD™，而且我不是无锁算法方面的专家，我不完全确定该算法是否无竞争条件。

问题：这个代码线程安全吗？这里有任何可能的比赛条件吗？

我正在尝试创建一种缓冲输入形式，以查看在不使用 Rx 或任何其他库（标准 .net 4.5 之外）的情况下实现它的难易程度。所以我想出了以下课程：

主要是，一旦计时器滴答作响，它就会切换队列并继续触发事件。我意识到这可以通过一个列表来完成......

过了一会儿，我得到以下熟悉的异常：

在以下行：

声明和测试程序是：

我的想法是，在调用Interlocked.Exchange（原子操作）之后，调用 _items 将返回新集合。但是作品中似乎有一个小鬼……

我在 ruby​​ 中编写了一些代码来通过线程池处理数组中的项目。在这个过程中，我预先分配了一个与传入数组大小相同的结果数组。在线程池中，我在预分配数组中分配项目，但这些项目的索引保证是唯一的。考虑到这一点，我是否需要在作业周围加上Mutex#synchronize?

例子：

（此测试代码需要很长时间才能运行，但似乎每次都打印“成功”。）

为了安全起见，我似乎想将其包围Array#[]=起来Mutex#synchronize，但我的问题是：

在 Ruby 的规范中，这段代码是否被定义为安全的？

下面是我的用例

我有一个全局变量，所有 CPU 上的多个线程都在访问它。

通过原子比较和交换

带旋转试锁

这是粗略的代码，我希望它很清楚。如果不清楚，请告诉我。

global_var 不是 int 它是结构。

所以，我的主要目标是保护 global_var，哪个更快 atomic_compare_and_swap 或 spin.trylock()，还有其他一些技术？

所以，我试图解决本质上是生产者-消费者问题，但略有不同。

• “生产者”线程创建令牌并将它们添加到列表中
• “消费者”线程扫描令牌列表并处理它们。
• 作为处理的结果，一些令牌可能会被删除，而其他令牌可能会保留更长时间。

所以主要区别在于生产者的输出可以以任意顺序从列表中删除，不一定是先进先出。

现在，我正在考虑两个线程之间共享的结构的同步。我想要一个无锁结构。我知道无锁队列，但是由于上述原因，队列不太适合用例。仍然可以为此使用队列，如下所示：

• 将令牌出列并处理它
• 如果它不应该被删除，请将其重新加入队列

但是，如果可能的话，我想避免它。理想情况下，我想要的是一个线程可以附加到的无锁单链表，而另一个线程可以从中删除任意元素。你能指出我的一些实现或论文吗？