Scambio atomico di due oggetti std :: atomici <T*> in modalità senza blocco in C++ 11?

Question

Il seguente codice è uno scheletro di una classe di puntatore atomico prelevata da un'applicazione di ricottura simulata nello PARSEC benchmark suite for shared-memory multiprocessors.

In tale applicazione, la struttura dati centrale è un grafico (più specificamente una netlist di un circuito integrato). Ogni nodo nel grafico ha un attributo che indica la sua posizione fisica. L'algoritmo genera più thread e ogni thread ripetutamente e seleziona in modo casuale due nodi e scambia le loro posizioni fisiche se ciò comporta un costo di routing migliore per il chip.

Poiché il grafico è enorme e ogni coppia di nodi può essere scelta da ciascun thread, l'unica soluzione praticabile è una struttura di dati concorrenti senza blocco (CDS). Ecco perché la seguente classe AtomicPtr è cruciale (è usata per scambiare atomicamente puntatori con due oggetti di posizione fisica in modo bloccato). La funzione atomic_load_acq_ptr() è definita nel codice assembly e corrisponde a std::atomic<T*>::load(memory_order_acquire).

Voglio implementare quel CDS usando gli atomici 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 
    } 
}; 

Procedimento std::atomic<T*>::exchange() può essere utilizzato solo per scambiare un puntatore nudo T* con un oggetto std::atomic<T*>. Come fare lo scambio di due oggetti std::atomic<T*> in modo bloccato?

Quello che mi viene in mente è che la classe AtomicPtr di seguito può essere a sua volta basata su std::atomic<T*> dichiarando:

std::atomic<T*> p; 

e sostituzione di tutte le chiamate da atomic_load_acq_ptr()std::atomic<T*>::load(memory_order_acquire) e sostituendo tutte le chiamate da atomic_store_rel_ptr()std::atomic<T*>::store(memory_order_release). Ma il mio primo pensiero è che std::atomic<T*> dovrebbe sostituire lo stesso AtomicPtr e potrebbe esserci un modo intelligente per scambiare direttamente gli oggetti std::atomic<T*>. qualche idea?

Answer 1

Mi sembra che il modo più semplice per ottenere ciò che desideri sia replicare la logica che hai visto qui.

Il problema è che non v'è alcuna possibilità di ottenere un operazioni atomiche attraverso due oggetti atomici, quindi si deve seguire una procedura:

• ordine i Atomics (per evitare di dead-serrature)
• " blocco" tutti tranne l'ultimo (crescente)
• eseguire l'operazione atomicamente sull'ultimo
• eseguire l'operazione e 'sblocco' gli altri uno alla volta (ordine decrescente)

012.

Questo è, ovviamente, del tutto imperfetta:

• non atomica: mentre si è occupato di blocco una variabile, una delle non ancora bloccato potrebbe cambiare lo stato
• non ostruzione libera: se per qualche motivo un il thread viene bloccato mentre si blocca una variabile, inoltre vengono bloccati tutti gli altri thread in sospeso; stare attenti ad evitare situazioni di stallo qui (se avete altre serrature)
• fragile: un crash dopo aver bloccato una variabile ti lascia incagliato, evitare operazioni che possono lanciare e/o utilizzare RAII a "bloccare"

Tuttavia dovrebbe funzionare relativamente bene nella pratica nel caso di solo 2 oggetti (e quindi uno da bloccare).

Infine, ho due osservazioni:

• per bloccare è necessario essere in grado di definire un valore sentinella, 0x01 solito funziona bene per i puntatori.
• lo standard C++ non garantisce che std::atomic<T*> sia privo di blocco, è possibile controllare questo per la vostra particolare implementazione e piattaforma con std::atomic<T*>::is_lock_free().

Answer 2

Avete controllato un'operazione CAS (confronto e scambio)?

std::atomic<T*> v; 

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

Answer 3

Il più vicino si può venire senza una spinlock è:

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

che è sicuro per b thread.

a non è possibile accedere contemporaneamente.