10

下面的代码是一个原子指针类的骨架,取自共享内存多处理器的 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*>直接交换对象。有什么想法吗?

4

3 回答 3

6

在我看来,获得你想要的更简单的方法是复制你在这里看到的逻辑。

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

  • 订购原子(以避免死锁)
  • “锁定”除最后一个以外的所有内容(递增顺序)
  • 在最后一个上原子地执行操作
  • 执行操作并一次“解锁”其他一个(递减顺序)

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

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

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

最后,我想说两句:

  • 为了锁定,您需要能够定义一个标记值,0x01通常适用于指针。
  • C++ 标准不保证std::atomic<T*>无锁,您可以使用std::atomic<T*>::is_lock_free().
于 2013-08-21T07:26:02.337 回答
3

没有自旋锁的最接近的是:

std::atomic<T> a;
std::atomic<T> b;
a = b.exchange(a);

哪个是线程安全的b

a不能同时访问。

于 2013-08-21T06:22:07.720 回答
0

您是否检查过 CAS(比较和交换)操作?

   std::atomic<T*> v;

      while(!v.compare_exchange_weak(old_value,new_value, std::memory_order_release, memory_order_relaxed))
于 2013-08-21T05:57:21.023 回答