次のコードは、共有メモリ マルチプロセッサ用の PARSEC ベンチマーク スイートのシミュレートされたアニーリング アプリケーションから取得したアトミック ポインター クラスのスケルトンです。
そのアプリケーションでは、中心的なデータ構造はグラフ (より具体的には、集積回路のネットリスト) です。グラフの各ノードには、物理的な位置を示す属性があります。アルゴリズムは多くのスレッドを生成し、各スレッドは繰り返しランダムに 2 つのノードを選択し、チップのルーティング コストが改善される場合はそれらの物理的な位置を交換します。
グラフは巨大で、ノードの任意のペアが各スレッドによって選択される可能性があるため、実行可能な唯一のソリューションは、ロックフリーの並行データ構造 (CDS) です。そのため、次のAtomicPtr
クラスが重要です (2 つの物理位置オブジェクトへのポインターをロックフリーでアトミックに交換するために使用されます)。この関数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()
と交換する場合にのみ使用できます。ロックなしで 2 つのオブジェクトを交換するにはどうすればよいですか?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*>