Barriere di memoria contro operazioni interbloccate

Question

Sto cercando di migliorare la mia comprensione delle barriere di memoria. Supponiamo di avere un modello di memoria debole e adattiamo Dekker's algorithm. È possibile farlo funzionare correttamente con il modello di memoria debole aggiungendo barriere di memoria?

Penso che la risposta sia un no sorprendente. Il motivo (se sono corretto) è che, sebbene sia possibile utilizzare una barriera di memoria per garantire che una lettura non venga spostata oltre un'altra, non può garantire che una lettura non visualizzi dati non aggiornati (come quelli in una cache). Quindi potrebbe vedere un po 'di tempo in passato quando la sezione critica è stata sbloccata (secondo la cache della CPU) ma al momento attuale altri processori potrebbero vederla come bloccata. Se la mia comprensione è corretta, è necessario utilizzare operazioni interbloccate come quelle comunemente chiamate test-and-set o compare-and-swap per garantire un accordo sincronizzato di un valore in una posizione di memoria tra più processori.

Quindi, possiamo giustamente aspettarci che nessun sistema di memoria debole fornisca solo barriere di memoria? Il sistema deve fornire operazioni come test-and-set o compare-and-swap per essere utili.

Mi rendo conto che i processori popolari, incluso x86, forniscono modelli di memoria molto più potenti di un modello di memoria debole. Si prega di concentrare la discussione sui modelli di memoria deboli.

(Se l'algoritmo di Dekker è una cattiva scelta, scegliere un altro algoritmo di mutua esclusione dove le barriere di memoria possono raggiungere con successo corretta sincronizzazione, se possibile.)

Answer 1

Hai ragione che una barriera di memoria non può garantire che una lettura veda i valori aggiornati. Quello che fa è applicare un ordinamento tra le operazioni, sia su un singolo thread, sia tra thread.

Ad esempio, se il thread A esegue una serie di negozi e quindi esegue una barriera di rilascio prima di un archivio finale in una posizione flag, e il thread B legge dalla posizione flag e quindi esegue una barriera di acquisizione prima di leggere gli altri valori quindi le altre variabili avranno i valori memorizzati dal thread a:

// initially x=y=z=flag=0 

// thread A 
x=1; 
y=2; 
z=3; 
release_barrier(); 
flag=1; 

// thread B 
while(flag==0) ; // loop until flag is 1 
acquire_barrier(); 
assert(x==1); // asserts will not fire 
assert(y==2); 
assert(z==3); 

Naturalmente, è necessario assicurarsi che il carico e memorizzare per flag è atomico (che semplici istruzioni load e store sono sulle CPU più comuni, a condizione che le variabili siano adeguatamente allineate). Senza il ciclo while sul thread B, il thread B potrebbe leggere un valore stantio (0) per flag e, pertanto, non è possibile garantire nessuno dei valori letti per le altre variabili.

Le fence possono quindi essere utilizzate per imporre la sincronizzazione nell'algoritmo di Dekker.

Ecco un esempio di implementazione in C++ (utilizzando le variabili atomiche C++ 0x):

std::atomic<bool> flag0(false),flag1(false); 
std::atomic<int> turn(0); 

void p0() 
{ 
    flag0.store(true,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_seq_cst); 

    while (flag1.load(std::memory_order_relaxed)) 
    { 
     if (turn.load(std::memory_order_relaxed) != 0) 
     { 
      flag0.store(false,std::memory_order_relaxed); 
      while (turn.load(std::memory_order_relaxed) != 0) 
      { 
      } 
      flag0.store(true,std::memory_order_relaxed); 
      std::atomic_thread_fence(std::memory_order_seq_cst); 
     } 
    } 
    std::atomic_thread_fence(std::memory_order_acquire); 

    // critical section 


    turn.store(1,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_release); 
    flag0.store(false,std::memory_order_relaxed); 
} 

void p1() 
{ 
    flag1.store(true,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_seq_cst); 

    while (flag0.load(std::memory_order_relaxed)) 
    { 
     if (turn.load(std::memory_order_relaxed) != 1) 
     { 
      flag1.store(false,std::memory_order_relaxed); 
      while (turn.load(std::memory_order_relaxed) != 1) 
      { 
      } 
      flag1.store(true,std::memory_order_relaxed); 
      std::atomic_thread_fence(std::memory_order_seq_cst); 
     } 
    } 
    std::atomic_thread_fence(std::memory_order_acquire); 

    // critical section 


    turn.store(0,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_release); 
    flag1.store(false,std::memory_order_relaxed); 
} 

Per un'analisi completa vedere il mio blog a http://www.justsoftwaresolutions.co.uk/threading/implementing_dekkers_algorithm_with_fences.html

Answer 2

Alcune barriere (come l'iSync PowerPC, e un carico .acq su ia64) hanno anche un effetto sui carichi successivi. vale a dire: se un carico era disponibile prima dell'isync dovuto al precaricamento deve essere scartato. Se usato in modo appropriato forse è sufficiente per far funzionare l'algoritmo di Dekker su un modello di memoria debole.

Hai anche la logica di invalidazione della cache che funziona per te. Se sai che il tuo carico è aggiornato a causa di qualcosa come un isync e che la versione cache dei dati è invalidata se un'altra CPU lo tocca, è sufficiente?

Interessanti domande a parte, l'algoritmo di Dekker è per tutti gli scopi pratici. Stai per voler utilizzare le interfacce hardware atomiche e le barriere di memoria per qualsiasi applicazione reale, quindi concentrarsi su come sistemare Dekker con l'atomica non mi sembra che valga la pena;)

Answer 3

Dire che si carica e si immagazzina barriera dopo ogni affermazione, e inoltre ti sei assicurato che il compilatore non abbia riordinato i tuoi negozi. Non sarebbe questo, su ogni ragionevole architettura, fornire una stretta coerenza? I lavori di Dekker su architetture coerentemente coerenti. La coerenza sequenziale è una condizione più debole rispetto alla consistenza stretta.

http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html

Anche su una CPU che ha un modello di consistenza debole, saresti ancora aspettano coerenza della cache. Penso che dove le cose vengono deragliate è il comportamento dei buffer dei negozi e delle letture speculate, e quali operazioni sono disponibili per svuotare le scritture memorizzate e invalidare le letture speculate. Se non esiste un recinto di carico che può invalidare le letture speculate, o non esiste una recinzione di scrittura che svuota un buffer di archivio, oltre a non essere in grado di implementare Dekker, non sarà possibile implementare un mutex!

Quindi ecco la mia richiesta. Se si dispone di una barriera di scrittura disponibile e di una barriera di lettura e la cache è coerente tra le CPU, è possibile rendere banalmente coerente tutto il codice in modo coerente mediante scritture di svuotamento (fence di magazzino) dopo ogni istruzione e speculazioni di flushing (recinzione di lettura) prima di ogni istruzioni. Quindi sostengo che non hai bisogno di atomici per quello di cui stai parlando, e che puoi fare ciò che ti serve solo con Dekker. Certo che non vorresti.

BTW, Corensic, la società per cui lavoro, scrive strumenti interessanti per il debug di problemi di concorrenza. Controlla http://www.corensic.com.