我可以在不读取值的情况下确定数据竞争的结果吗？

Question

我试图更好地理解无锁编程：

假设我们在数据竞争中有两个线程：

// Thread 1
x = 1

// Thread 2
x = 2

有没有一种无锁的方式，第三个线程可以在无法读取 x 的情况下知道竞争的结果？

假设线程3消费了一个无锁队列，代码为：

// Thread 1
x = 1
queue.push(1)

// Thread 2
x = 2
queue.push(2)

然后可以将操作排序为：

x = 1
x = 2
queue.push(1)
queue.push(2)

或者

x = 1
x = 2
queue.push(2)
queue.push(1)

因此，只有一个无锁队列不足以让线程 3 在比赛后知道 x 的值。

Answer 1

如果您x在比赛开始前就知道 的值，那么使用原子读-修改-写操作的以下代码应该可以完成这项工作。

// Notes:
// x == 0
// x and winner are both atomic
// atomic_swap swaps the content of two variables atomically, 
// meaning, that no other thread can interfere with this operation

//thread-1:
t = 1;
atomic_swap(x, t);
if (t != 0) {
    //x was non zero, when thread-1 called the swap operation
    //--> thread-2 was faster
    winner = 1;
}    

//thread-2
t = 2;
atomic_swap(x, t);
if (t != 0) {
    //x was non zero, when thread-2 called the swap operation
    //--> thread-1 was faster
    winner = 2;
}  

//thread-3
while (winner == 0) {} 
print("Winner is " + winner);