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

Question

以下代码是一个原子指针类的框架,它取自PARSEC基准套件中用于共享内存多处理器的模拟退火应用程序.

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

因为图形很大并且每个线程都可以选择任何一对节点,所以唯一可行的解​​决方案是无锁并发数据结构(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个物体(因此锁定一个物体)的情况下,它在实践中应该相对较好地工作.

最后,我有两个评论:

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