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