Atomowa wymiana dwóch obiektów std :: atomowych <T*> w sposób pozbawiony blokady w C++ 11?

Question

Poniższy kod jest szkieletem klasy wskaźnika atomowego pobranej z symulowanej aplikacji wyżarzania w PARSEC benchmark suite for shared-memory multiprocessors.

W tej aplikacji centralną strukturą danych jest wykres (a dokładniej netlista układu scalonego). Każdy węzeł na wykresie ma atrybut wskazujący jego fizyczną lokalizację. Algorytm spawnuje wiele wątków, a każdy wątek wielokrotnie i losowo wybiera dwa węzły i wymienia ich fizyczne lokalizacje, jeśli powoduje to lepszy koszt routingu dla układu.

Ponieważ wykres jest ogromny i każda para węzłów może być wybrana dla każdego wątku, jedynym praktycznym rozwiązaniem jest blokująca współbieżna struktura danych (CDS). Dlatego kluczowa jest następująca klasa AtomicPtr (służy ona do wymiany atomowej wskaźników na dwa fizyczne obiekty lokalizacyjne w sposób pozbawiony blokady). Funkcja atomic_load_acq_ptr() jest zdefiniowana w kodzie zespołu i odpowiada ściśle std::atomic<T*>::load(memory_order_acquire).

Chcę zaimplementować ten CDS przy użyciu atomów C++ 11.

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 
    } 
}; 

Sposób std::atomic<T*>::exchange() można stosować tylko wymienić nagie T* wskaźnik z std::atomic<T*> obiektu. Jak dokonać wymiany dwóch obiektów std::atomic<T*> w sposób pozbawiony blokady?

Co mogę myśleć, że klasa AtomicPtr poniżej sama może być oparta na std::atomic<T*> oświadczając:

std::atomic<T*> p; 

i zastąpienie wszystkich atomic_load_acq_ptr() połączeń przez std::atomic<T*>::load(memory_order_acquire) i zastąpienie wszystkich atomic_store_rel_ptr() połączeń przez std::atomic<T*>::store(memory_order_release). Ale moja pierwsza myśl polegała na tym, że std::atomic<T*> sam powinien zastąpić AtomicPtr i może istnieć sprytny sposób na bezpośrednią wymianę obiektów std::atomic<T*>. jakieś pomysły?

Answer 1

Wydaje mi się, że prostszym sposobem uzyskania tego, co chcesz, jest skopiowanie logiki, którą tu zobaczyłeś.

Problemem jest to, że nie ma możliwości, aby dostać atomowej operacji całej dwóch obiektów atomowych, więc trzeba postępować zgodnie z procedurą:

• obciążenie Atomics (aby uniknąć martwych-zamki)
• " lock”wszystko oprócz ostatniego (rosnące)
• wykonać operację atomowo na ostatniej jednej
• wykonać operację i«unlock»pozostali jedną naraz (malejącą)

To jest, oczywiście, dość niedoskonała:

• nie atomowy: gdy jesteś zajęty blokowania zmienną, każda z jeszcze nie zamknięty może zmienić stan
• nie przeszkoda darmo: jeśli z jakiegoś powodu wątek jest blokowany, gdy zablokowana jest zmienna, wszystkie pozostałe wątki są również blokowane; należy uważać, aby uniknąć zakleszczenia tutaj (powinieneś mieć inne zamki)
• kruche: awaria po zablokowaniu zmienną pozostawia nam linka, unikać działań, które mogą rzucać i/lub stosowanie RAII „zablokować”

jednak powinien funkcjonować stosunkowo dobrze w praktyce w przypadku tylko 2 obiektów (a więc jednego do zablokowania).

Wreszcie, mam dwie uwagi:

• w celu zablokowania trzeba być w stanie określić wartość Sentinel 0x01 zazwyczaj działa dobrze dla wskaźników.
• Standard C++ nie gwarantuje, że std::atomic<T*> jest blokowany, możesz to sprawdzić dla swojej konkretnej implementacji i platformy za pomocą std::atomic<T*>::is_lock_free().

Answer 2

Czy sprawdziłeś operację CAS (porównaj i zamień)?

std::atomic<T*> v; 

     while(!v.compare_exchange_weak(old_value,new_value, std::memory_order_release, memory_order_relaxed)) 

Answer 3

Najbliżej można przyjść bez spinlock jest:

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

który jest bezpieczny dla b wątek.

a może nie być używany jednocześnie.