6

想象一个有两个线程的程序。他们正在运行以下代码（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 循环中完成了一些工作怎么办？

4

2 回答 2

6

从理论上讲，是的。如果你能设法让两个线程像这样同步运行

    时间线程 A 线程 B
    ---- -------- --------
     || 中国科学院
     || atomic_write
     || 中国科学院
     \/ atomic_write

那么 CAS 将永远不会返回 true。

在实践中，当线程共享一个 CPU/Core 时，这永远不会发生，并且当线程在不同的 CPU 或 Core 上运行时也不太可能发生。在实践中，它不太可能在几个周期内发生，而且在天文数字上不太可能发生超过一个调度程序量子。

那就是如果这段代码

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

做它看起来做的事情，即获取 的当前值test，并比较它test以查看它是否已更改。在现实世界中，CAS 的迭代将被执行实际工作的代码分开。需要该volatile关键字来确保编译器在调用 CAS 之前获取测试，而不是假设它可能仍然存在于寄存器中的副本仍然有效。

或者您要测试的值不是当前的测试值，而是某种最后的已知值。

换句话说，这个代码示例是对理论的检验，但在实践中你不会像这样使用 CAS，所以即使你可以让它失败，它也不一定告诉你在使用时它会如何失败现实世界的算法。

于 2010-02-07T00:50:57.050 回答
2

在这种情况下肯定会发生饥饿。引用维基百科页面，

还表明，广泛可用的原子条件原语 CAS 和 LL/SC 在内存成本不随线程数线性增长的情况下无法提供许多常见数据结构的无饥饿实现。因此，无论在研究中还是在实践中，免等待算法都很少见。

（有关数学证明，请参见相关页面的链接）。

于 2010-02-07T00:30:05.277 回答