c++ - 在 C++11 中以无锁方式原子交换两个 std::atomic<T*> 对象？

Question

以下代码是从 PARSEC benchmark suite for shared-memory multiprocessors 中的模拟退火应用程序中提取的原子指针类的框架。 .

在该应用程序中，中央数据结构是一个图形(更具体地说，是集成电路的网表)。图中的每个节点都有一个指示其物理位置的属性。该算法产生许多线程，每个线程重复并随机选择两个节点并交换它们的物理位置，如果这样可以为芯片带来更好的路由成本。

由于图很大，每个线程都可以选择任意一对节点，唯一可行的解​​决方案是无锁并发数据结构 (CDS)。这就是为什么以下 AtomicPtr类是至关重要的(它用于以无锁方式自动交换指向两个物理位置对象的指针)。 函数atomic_load_acq_ptr()是在汇编代码中定义的，与 std::atomic<T*>::load(memory_order_acquire) 密切对应.

我想使用 C++11 原子实现该 CDS。

template <typename T>
class AtomicPtr {
  private:
    typedef long unsigned int ATOMIC_TYPE;
    T *p __attribute__ ((aligned (8)));
    static const T *ATOMIC_NULL;
    inline T *Get() const {
        T *val;
        do {
            val = (T *)atomic_load_acq_ptr((ATOMIC_TYPE *)&p);
        } while(val == ATOMIC_NULL);
        return val;
    }
    inline void Swap(AtomicPtr<T> &X) {
        // Define partial order in which to acquire elements to prevent deadlocks
        AtomicPtr<T> *first;
        AtomicPtr<T> *last;
        // Always process elements from lower to higher memory addresses
        if (this < &X) {
            first = this;
            last  = &X;
        } else {
            first = &X;
            last  = this;
        }
        // Acquire and update elements in correct order
        T *valFirst = first->Checkout(); // This sets p to ATOMIC_NULL so all Get() calls will spin.
        T *valLast  =  last->PrivateSet(valFirst);
        first->Checkin(valLast); // This restores p to valLast
    }
};

std::atomic<T*>::exchange()方法只能用于交换裸T*带有 std::atomic<T*> 的指针目的。两个怎么交换std::atomic<T*>对象以无锁方式？

我能想到的是 AtomicPtr下面的类本身可以基于 std::atomic<T*>通过声明:

std::atomic<T*> p;

并替换所有 atomic_load_acq_ptr()通过 std::atomic<T*>::load(memory_order_acquire) 来电并替换所有 atomic_store_rel_ptr()通过 std::atomic<T*>::store(memory_order_release) 来电.但我的第一个想法是 std::atomic<T*>应该替换 AtomicPtr本身，并且可能有一种聪明的方式来交换std::atomic<T*>直接对象。有什么想法吗？

Answer 1

在我看来，获得所需内容的更简单方法是复制您在此处看到的逻辑。

问题是不可能跨两个原子对象进行原子操作，所以你必须遵循一个过程:

• 对原子进行排序(以避免死锁)
• “锁定”除最后一个以外的所有对象(递增顺序)
• 在最后一个上自动执行操作
• 执行操作并一次“解锁”其他操作(降序)

当然，这是非常不完美的:

• 不是原子的:当你忙于锁定一个变量时，任何尚未锁定的变量都可以改变状态
• 不是无障碍的:如果由于某种原因一个线程在锁定一个变量时被阻塞，所有其他挂起的线程也会被阻塞；小心避免这里出现死锁(如果你有其他锁的话)
• 脆弱:锁定变量后崩溃会让您陷入困境，避免可能抛出和/或使用 RAII 来“锁定”的操作

然而，在只有 2 个对象(因此需要锁定一个对象)的情况下，它在实践中应该工作得相对较好。

最后，我要说两句:

• 为了锁定你需要能够定义一个标记值，0x01通常适用于指针。
• C++ 标准不保证 std::atomic<T*>无锁，您可以使用 std::atomic<T*>::is_lock_free() 检查您的特定实现和平台.