标签: lock-free

眼见为实。任何人都可以重现读取撕裂的小数的程序吗？我尝试旋转多个线程，在 1 和 2 之间更改相同的小数。我没有捕获任何与 1 或 2 不同的读取。

我希望看到读取器线程看不到写入器线程的原子更改，因此该值应该与 1 或 2 不同。

void TornDecimalReadTest()
{
    decimal sharedDecimal = 1;
    int threadCount = 100;
    var threads = new List<Thread>();

    for (int i = 0; i < threadCount; i++)
    {
        int threadId = i;
        var thread = new Thread(() =>
        {
            Thread.Sleep(5000);

            decimal newValue = threadId % 2 == 0 ? 1 : 2;
            bool isWriterThread = threadId % 2 == 0;

            Console.WriteLine("Writer : " + isWriterThread +
                " - …

我正在研究C++11 中mutex和之间的区别atomic。

据我了解，mutex是一种基于操作系统/内核实现的锁机制。例如，Linux 提供了一种机制，即futex. 在 的帮助下futex，我们可以实现mutex和semaphore。此外，我知道这futex是由低级原子操作实现的，例如CompareAndSet, CompareAndSwap。

对于std::atomic，我知道它是基于C++11引入的内存模型实现的。但是，我不知道内存模型在低级别是如何实现的。如果也是通过原子操作之类CompareAndSet的方式实现的，std::atomic和 和 有mutex什么区别？

总之，如果std::atomic::is_lock_free给我一个false，好吧，我会说这std::atomic与mutex. 但是如果它给了我一个true，它是如何在低级别实现的？

根据C++标准：

\n

如果 A 的值用作 B 的操作数，则求值 A 具有对求值 B 的依赖性，除非：

\n

\xe2\x80\x94 B 是 std::kill_dependency (29.3) 的任何特化的调用，或者

\n

\xe2\x80\x94 A 是内置逻辑 AND（&&，参见 5.14）或逻辑 OR（||，参见 5.15）运算符的左操作数，或者

\n

\xe2\x80\x94 A 是条件（?:，参见 5.16）运算符的左操作数，或者

\n

\xe2\x80\x94 A 是内置逗号 (,) 运算符的左操作数 (5.18)；（...）

\n

我可以理解为什么关系之前排序的依赖项会在kill_dependency调用时停止，但是为什么逻辑AND、OR、逗号等运算符也会破坏依赖链？

这是否意味着下面的代码有未定义的行为？

//thread1\nint y = 2\natomicVal.store(true);\n\n//thread2 \nauto x = atomicVal.load(std::memory_order_consume);\ncout << x && y;\n

在无锁的queue.pop()中，我在与循环内的原子获取同步后读取了一个trivialy_copyable变量（整型）。\n最小化的伪代码：

//somewhere else writePosition.store(...,release)\n\nbool pop(size_t & returnValue){\nwritePosition = writePosition.load(aquire)\noldReadPosition = readPosition.load(relaxed)\nsize_t value{};\ndo{\n  value = data[oldReadPosition]\n  newReadPosition = oldReadPosition+1\n}while(readPosition.compare_exchange(oldReadPosition, newReadPosition, relaxed)\n// here we are owner of the value\nreturnValue = value;\nreturn true;\n}\n

data[oldReadPosition]仅当该值之前从另一个线程读取时，才能更改内存。

读写位置都是 ABA 安全的。\n通过简单的复制，value = data[oldReadPosition]内存data[oldReadPosition]不会被改变。

但是写入线程queue.push(...)可以在读取时更改data[oldReadPosition]，前提是另一个线程已经读取了 oldPosition 并更改了 readPosition。

如果您使用该值，这将是一个竞争条件，但是当我们保持value不变时，它是否也是一个竞争条件，从而导致未定义的行为？标准不够具体或者我不\xc2\xb4不理解它。\nimo，这应该是可能的，因为它没有效果。\n我会很高兴得到一个合格的答案以获得更深入的见解

多谢

Windows提供了一个无锁的单链表,如本页所述: Win32 SList

我想知道这个功能是否存在一个好的C++包装器.当我说好的时候,我的意思是它尽可能地导出通常的STL接口,支持迭代器等.我宁愿使用别人的实现而不是坐下来编写STL类型的容器.

在数据结构同步的背景下,有人可以澄清"无锁"和"非阻塞"之间的区别吗？这些术语似乎可以被很多人互换使用,但我还不确定某个地方是否隐藏着一些微妙的差异.

我的意思是无锁是"没有锁",非阻塞更像是保证进步.我怀疑一个暗示另一个而不是相反,我不确定.

参考文献欢迎.

在本文中:无锁数据结构(pdf)显示以下"比较和交换"基础:

template <class T>
bool CAS(T* addr, T exp, T val)
{
  if (*addr == exp)
  {
    *addr = val;
    return true;
  }
  return false;
}

然后说

整个过程都是原子的

但那是怎么回事？是否有可能其他一些演员可以改变作业和作业addr之间的价值if？在这种情况下,假设所有代码都使用了这个CAS基础,那么下次有什么东西"预期"它是某种特定方式,而事实并非如此.但是,这并没有改变它可能发生的事实,在这种情况下,它仍然是原子的吗？如果另一个演员的变化被这个演员覆盖了,那么另一个演员回归真实呢？如果那不可能发生,为什么呢？

我想相信作者,所以我在这里错过了什么？我认为这一定是显而易见的.如果这看起来微不足道,我提前道歉.

在多生产者,多消费者的情况下.如果制作人正在写作int a,消费者正在阅读int a,我是否需要内存障碍int a？

我们都了解到:共享资源应该始终受到保护,标准不能保证正确的行为.

但是,在高速缓存一致的体系结构上,可以自动确保可见性,并保证8,16,32和64位变量MOV操作的原子性.

因此,为什么要保护int a呢？

" Treiber Stack "通常是最简单的无锁数据结构之一,因此在教授无锁算法的介绍时经常使用它.

我已经看到许多使用C++原子的Treiber Stacks的实现.算法本身很简单,所以真正的挑战是处理无锁数据结构的所有其他附带细节,例如提供一些执行安全内存回收的方法,避免ABA问题,以及以无锁方式分配节点.这可以通过各种方式解决,例如使用原子引用计数,危险指针,计数/标记指针以避免ABA,以及使用无锁内存池.

但忽略所有这些细节并专注于简单的算法本身,我想到的一个问题是,我可以回想起的Treiber Stacks的每个实现都使用原子下一个指针来实现节点类.例如:

struct Node
{
  T value;
  std::atomic<Node*> next;
};

但在考虑算法之后,我不确定为什么下一个指针需要是原子的.

一般的PUSH算法(忽略无锁分配,安全内存回收,退避,ABA避免等)是:

Node* n = new Node();
Node* front = m_front.load();
n->next.store(front);
while (!m_front.compare_exchange_weak(front, n))
{
  n->next.store(front);
}

一般的POP算法(再次,忽略除实际算法逻辑之外的所有细节)是:

Node* front = m_front.load();
Node* next = front->next.load();
while (!m_front.compare_exchange_weak(front, next))
{
  next = front->next.load();
}

这是PUSH算法的真实示例实现:

https://github.com/khizmax/libcds/blob/master/cds/intrusive/treiber_stack.h#L736

所以我不明白为什么下一个指针甚至需要是原子的.大多数C++实现使用next指针放松加载/存储,因此在读/写下一个指针时我们不需要任何内存栅栏,但我的想法是它根本不需要是原子的.

从我所看到的,任何时候都没有同时写入的任何节点的下一个指针.相反,可以同时加载下一个指针,但我从未看到算法同时加载+存储或同时存储+存储的任何机会.实际上,在PUSH算法中,根本不会同时访问下一个指针.

所以在我看来,当并发访问时,下一个指针实际上是"只读"的,所以我不确定为什么甚至有必要让它们成为原子.

然而,我见过的Treiber Stack的每个C++实现都使下一个指针成为原子.所以我是正确的,还是有某种原因下一个指针必须是原子的？

在MSVC for x64(19.10.25019)上,

    InterlockedOr(&g, 1) 

生成此代码序列:

    prefetchw BYTE PTR ?g@@3JC
    mov     eax, DWORD PTR ?g@@3JC                  ; g
    npad    3
$LL3@f:
    mov     ecx, eax
    or      ecx, 1
    lock cmpxchg DWORD PTR ?g@@3JC, ecx             ; g
    jne     SHORT $LL3@f

我本来期望更简单(和无环):

    mov      eax, 1
    lock or  [?g@@3JC], eax

InterlockedAnd生成类似的代码InterlockedOr.

必须为此指令设置循环似乎非常低效.为什么会生成此代码？

(作为旁注:我使用的全部原因是InterlockedOr对变量进行原子加载 - 我已经知道这InterlockedCompareExchange是做到这一点的方法.我很奇怪没有InterlockedLoad(&x),但我离题了... )