代码之家 › 专栏 › 技术社区 › Joseph Garvin

相互竞争的原子能使彼此挨饿吗?

compare-and-swap lock-free atomic multithreading c++

6

Joseph Garvin · 技术社区 · 16 年前

想象一个有两个线程的程序。他们正在运行以下代码(cas指 Compare and Swap ):

// 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的CA失败,从而使0xdeadbeef从不写入“test”?或者,自然的调度抖动意味着在实践中这种情况永远不会发生?如果在线程A的while循环中完成了一些工作呢?

2 回复 | 直到 16 年前

1

6

John Knoeller 16 年前

理论上是的。如果你能设法让两个线程在这样的锁步中运行

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

这样的话,中科院就永远不会回到现实。

在实践中,当线程共享一个CPU/核心时,这种情况永远不会发生,当线程在不同的CPU或核心上运行时,这种情况也不太可能发生。实际上是 难以置信地 在几个周期内不太可能发生,在天文学上不太可能发生在超过调度量的情况下。

如果这个密码

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

执行它看起来要执行的操作,即获取 test ,并将其与 测试 看看它是否改变了。在现实世界中,CA的迭代将由实际工作的代码分隔开。这个 volatile 需要关键字来确保编译器在调用cas之前获取了测试,而不是假定它在寄存器中可能仍然有一个副本仍然有效。

或者你要测试的值不是 现在的 测试的价值,而是某种 最后已知 价值。

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

2

Alex Martelli 16 年前

在这种情况下,肯定会发生饥饿。引用 the wikipedia page ,

也表明广泛可用的原子条件原语,cas和ll/sc,不能提供免费的饥饿许多公共数据的实现无内存开销的结构线性增长线程。等待自由算法是因此在研究和在实践中。

(有关数学证明,请参见相关页面的链接)。