Quali sono le garanzie di ordinazione della memoria C++ 11 in questo caso angolare?

Question

Sto scrivendo un codice senza blocco, e ho trovato un modello interessante, ma non sono sicuro che si comporti come previsto in ordine di memoria rilassato.

Il modo più semplice per spiegarlo è con un esempio:

std::atomic<int> a, b, c; 

auto a_local = a.load(std::memory_order_relaxed); 
auto b_local = b.load(std::memory_order_relaxed); 
if (a_local < b_local) { 
    auto c_local = c.fetch_add(1, std::memory_order_relaxed); 
} 

Nota che tutte le operazioni utilizzano std::memory_order_relaxed.

Ovviamente, sul thread su cui viene eseguito questo, i carichi per a e b devono essere eseguiti prima che venga valutata la condizione if.

Analogamente, l'operazione di lettura-modifica-scrittura (RMW) su c deve essere eseguita dopo che la condizione è stata valutata (perché è condizionata a quella condizione ...).

Quello che voglio sapere è, questo codice garantisce che il valore di c_local è aggiornato almeno quanto i valori di a_local e b_local? Se è così, com'è possibile dato l'ordine di memoria rilassato? La dipendenza del controllo insieme all'operazione RWM agisce come una specie di recinto di acquisizione? (Nota che non c'è nemmeno una versione corrispondente da nessuna parte.)

Se quanto sopra è vero, credo che questo esempio dovrebbe funzionare anche (supponendo che non ci sia un overflow) - ho ragione?

std::atomic<int> a(0), b(0); 

// Thread 1 
while (true) { 
    auto a_local = a.fetch_add(1, std::memory_order_relaxed); 
    if (a_local >= 0) { // Always true at runtime 
     b.fetch_add(1, std::memory_order_relaxed); 
    } 
} 

// Thread 2 
auto b_local = b.load(std::memory_order_relaxed); 
if (b_local < 777) { 
    // Note that fetch_add returns the pre-incrementation value 
    auto a_local = a.fetch_add(1, std::memory_order_relaxed); 
    assert(b_local <= a_local); // Is this guaranteed? 
} 

Il filo 1, v'è una dipendenza di controllo che sospetto garantisce che a viene sempre incrementato prima b viene incrementato (ma ogni conservazione essendo incrementato collo-e-collo). Sul thread 2 esiste un'altra dipendenza di controllo che, a mio avviso, garantisce che b venga caricato in b_local prima che venga incrementato a. Ritengo inoltre che il valore restituito da fetch_add sarà almeno il più recente di qualsiasi valore osservato in b_local e che pertanto è necessario mantenere assert. Ma non sono sicuro, dal momento che questo si discosta significativamente dai soliti esempi di ordinamento della memoria, e la mia comprensione del modello di memoria C++ 11 non è perfetta (ho problemi a ragionare su questi effetti di ordinamento della memoria con qualsiasi grado di certezza). Ogni approfondimento è apprezzato!

---

Aggiornamento: Come bames53 ha utilmente sottolineato nei commenti, dato un sufficientemente intelligente compilatore, è possibile che un if potrebbe essere ottimizzato interamente nelle giuste circostanze, nel qual caso i carichi rilassato potrebbero essere riordinato per verificarsi dopo il RMW, causando i loro valori per essere più aggiornati rispetto al valore di ritorno fetch_add (il assert potrebbe sparare nel mio secondo esempio). Tuttavia, cosa succede se invece di un if, è inserito uno atomic_signal_fence (non atomic_thread_fence)? Questo certamente non può essere ignorato dal compilatore, non importa quali siano le ottimizzazioni, ma garantisce che il codice si comporti come previsto? In questo caso, la CPU è autorizzata a eseguire un nuovo ordine?

Il secondo esempio diventa allora:

std::atomic<int> a(0), b(0); 

// Thread 1 
while (true) { 
    auto a_local = a.fetch_add(1, std::memory_order_relaxed); 
    std::atomic_signal_fence(std::memory_order_acq_rel); 
    b.fetch_add(1, std::memory_order_relaxed); 
} 

// Thread 2 
auto b_local = b.load(std::memory_order_relaxed); 
std::atomic_signal_fence(std::memory_order_acq_rel); 
// Note that fetch_add returns the pre-incrementation value 
auto a_local = a.fetch_add(1, std::memory_order_relaxed); 
assert(b_local <= a_local); // Is this guaranteed? 

---

Un altro aggiornamento: Dopo aver letto tutte le risposte finora e pettinatura attraverso lo standard me stesso, non credo che si possa dimostrare che la il codice è corretto usando solo lo standard. Quindi, qualcuno può inventarsi un contro-esempio di un sistema teorico conforme allo standard e anche lanciare l'asserzione?

Answer 1

Questo esempio ha una variazione di comportamento da lettura ad aria sottile. La discussione pertinente nelle specifiche è nella sezione 29.3p9-11. Poiché la versione attuale dello standard C11 non garantisce il rispetto delle dipendenze, il modello di memoria dovrebbe consentire l'attivazione dell'asserzione. La situazione più probabile è che il compilatore ottimizzi via il controllo che a_local> = 0. Ma anche se si sostituisce tale controllo con una barriera di segnale, le CPU sarebbero libere di riordinare quelle istruzioni. È possibile testare esempi di codice simili nei modelli di memoria C/C++ 11 utilizzando lo strumento CDSChecker open source. Il problema interessante del tuo esempio è che per un'esecuzione che viola l'asserzione, ci deve essere un ciclo di dipendenze. Più concretamente:

Il file b.fetch_add nel thread uno dipende da a.fetch_add nella stessa iterazione del ciclo a causa della condizione if. A.fetch_add nella thread 2 dipende da b.load. Per una violazione di asserzione, dobbiamo leggere b.load di T2 da un file b.fetch_add in una iterazione del loop successiva rispetto a a.fetch_add di T2. Considerare ora b.fetch_add da cui legge b.load e chiamarlo # per riferimento futuro. Sappiamo che b.load dipende da # dato che prende il valore da #.

Sappiamo che # deve dipendere da a.fetch_add di T2 poiché a.fetch_add di T2 legge e aggiorna un precedente a.fetch_add da T1 nella stessa iterazione del ciclo di #. Quindi sappiamo che # dipende da a.fetch_add nel thread 2. Questo ci dà un ciclo di dipendenze ed è semplicemente strano, ma consentito dal modello di memoria C/C++. Il modo più probabile di produrre quel ciclo è (1) che il compilatore calcoli che a.local è sempre maggiore di 0, rompendo la dipendenza. Può quindi eseguire lo srotolamento del loop e riordinare il file fetch_add di T1 come vuole.

Answer 2

Le recinzioni del segnale non forniscono le garanzie necessarie (beh, a meno che 'thread 2' non sia un segnale che gira effettivamente su 'thread 1').

Per garantire un comportamento corretto, è necessaria la sincronizzazione tra i thread e il recinto che lo rappresenta è std::atomic_thread_fence. etichetta

---

Let dichiarazioni modo da poter diagramma varie esecuzioni (con recinzioni filetto sostituzione recinzioni di segnale, come richiesto):

while (true) { 
    auto a_local = a.fetch_add(1, std::memory_order_relaxed); // A 
    std::atomic_thread_fence(std::memory_order_acq_rel);  // B 
    b.fetch_add(1, std::memory_order_relaxed);    // C 
} 

auto b_local = b.load(std::memory_order_relaxed);    // X 
std::atomic_thread_fence(std::memory_order_acq_rel);   // Y 
auto a_local = a.fetch_add(1, std::memory_order_relaxed);  // Z 

Così per prima cosa supponiamo che X carica un valore scritto da C. Il seguente paragrafo specifica che in quel caso le recinzioni si sincronizzano e si verifica un -prima che venga stabilita la relazione.

29,8/2:

Un recinto rilascio Un sincronizza con una recinzione acquisiscono B se esistono operazioni atomiche X e Y, sia operando su un oggetto atomico M, tale che A è preceduto da X, X modifica M, Y viene sequenziato prima B e Y legge il valore scritto da X o un valore scritto da qualsiasi effetto collaterale della sequenza rilascio ipotetico X capeggeremmo se fosse un operazione di rilascio.

Ed ecco un possibile ordine di esecuzione in cui le frecce sono accade-prima relazioni.

Thread 1: A₁ → B₁ → C₁ → A₂ → B₂ → C₂ → ... 
       ↘ 
Thread 2: X → Y → Z 

Se un effetto collaterale X su un oggetto atomico M avviene prima di un valore di calcolo B di M, quindi la valutazione B adotta il valore da X o da un effetto collaterale Y che segue X nell'ordine di modifica di M. — [C++ 11 1.10/18]

Così il carico a Z deve prendere il suo valore da A₁ o da una modifica successiva. Pertanto, l'affermazione vale perché il valore scritto in A₁ e in tutte le successive modifiche è maggiore o uguale al valore scritto in C₁ (e letto da X).

---

Ora diamo un'occhiata al caso in cui le recinzioni non si sincronizzano. Ciò accade quando il carico di b non carica un valore scritto da thread 1, ma legge invece il valore con cui viene inizializzato b. C'è ancora la sincronizzazione in cui i fili inizia però:

30.3.1.2/5

sincronizzazione: Il completamento della invocazione del costruttore si sincronizza con l'inizio della invocazione della copia di f.

Specifica il comportamento del costruttore di std::thread. Quindi (supponendo che la creazione del thread sia correttamente sequenziata dopo l'inizializzazione di a) il valore letto da Z deve prendere il suo valore dall'inizializzazione di a o da una delle successive modifiche sul thread 1, il che significa che le asserzioni rimangono valide.