竞争的原子操作可以饿死彼此？

Question

设想一个程序具有两个线程。他们正在运行下面的代码（CAS是指比较和交换）：

// Visible to both threads
static int test;

// Run by thread A
void foo()
{
    // Check if value is 'test' and swap in 0xdeadbeef
    while(!CAS(&test, test, 0xdeadbeef)) {}
}

// Run by thread B
void bar()
{
    while(1) {
        // Perpetually atomically write rand() into the test variable
        atomic_write(&test, rand());
    }
}

是否有可能在线程B到永远使线程A的CAS失败，使得0xdeadbeef不会被写入“测试”？或不自然的调度抖动意味着，在实践中，这永远不会发生？如果哪些工作线程A的while循环中做了什么？

Answer 1

作为理论问题，是的。如果你能以某种方式管理得到在这样步调一致运行两个线程

    time     thread A     thread B
    ----     --------     --------
     ||       CAS
     ||                   atomic_write
     ||       CAS
     \/                   atomic_write

然后CAS永远不会返回true。

在实践中，当线程共享一个CPU /核心，这将不会发生，并且不可能当线程在不同的CPU或核心上运行的情况发生。在实践中它的的难以置信的不太可能发生超过几个周期多，天文不大可能发生超过一个调度量子更多。

这就是如果这个代码

void foo()
{
    // Check if value is 'test' and swap in 0xdeadbeef
    while(!CAS(&test, test, 0xdeadbeef)) {}
}

做的事情似乎做的，这是获取test的当前值，并把它比作test，看它是否已经改变。在现实世界中CAS的迭代会通过做实际工作的代码中分离出来。将需要的volatile关键字，以确保调用CAS而不是假定一个副本，它仍可能有一个寄存器之前，编译器获取的测试仍然是有效的。

或者，你会反对将测试值不会是的电流的测试值，而是某种的最后一个已知的值。

在换句话说，此代码示例是理论的测试，但你不会在实践中使用CAS这样的，所以即使你可以得到这个失败，它不一定告诉你怎么可能会失败在现实世界中的算法一起使用时。

Answer 2

饥饿一定可以在这样的情况下发生。引用维基百科页面，

  

还已经表明   广泛使用的原子条件   原语，CAS和LL / SC，不能   提供饥饿免费   许多常见的数据的实施方式中   结构没有内存成本   在数量呈线性增长   线程。无等待算法   因此罕见，无论是在研究和   在实践中。

（参见从页所讨论的数学证明的链接）。