C#/CLR: MemoryBarrier e lacerato legge

Question

Basta giocare con la concorrenza nel mio tempo libero, e voleva provare impedendo strappato legge senza utilizzare le serrature sul lato lettore di modo che i lettori concorrenti non interferiscono con l'altro.

L'idea è quella di serializzare scrive tramite un blocco, ma utilizzare solo una barriera di memoria sul lato di lettura. Ecco un'astrazione riutilizzabili che incapsulano l'approccio mi si avvicinò con:

public struct Sync<T> 
    where T : struct 
{ 
    object write; 
    T value; 
    int version; // incremented with each write 

    public static Sync<T> Create() 
    { 
     return new Sync<T> { write = new object() }; 
    } 

    public T Read() 
    { 
     // if version after read == version before read, no concurrent write 
     T x; 
     int old; 
     do 
     { 
      // loop until version number is even = no write in progress 
      do 
      { 
       old = version; 
       if (0 == (old & 0x01)) break; 
       Thread.MemoryBarrier(); 
      } while (true); 
      x = value; 
      // barrier ensures read of 'version' avoids cached value 
      Thread.MemoryBarrier(); 
     } while (version != old); 
     return x; 
    } 

    public void Write(T value) 
    { 
     // locks are full barriers 
     lock (write) 
     { 
      ++version;    // ++version odd: write in progress 
      this.value = value; 
      // ensure writes complete before last increment 
      Thread.MemoryBarrier(); 
      ++version;    // ++version even: write complete 
     } 
    } 
} 

Non preoccuparti troppo pieno sulla variabile versione, evito che un altro modo. Quindi la mia comprensione e applicazione di Thread.MemoryBarrier è corretta in quanto sopra? Non sono necessarie alcune barriere?

Answer 1

Ho dato un'occhiata lunga al codice e sembra corretto per me. Una cosa che mi è subito venuta fuori è che hai usato un modello prestabilito per eseguire l'operazione di blocco basso. Vedo che stai utilizzando version come una sorta di blocco virtuale. Vengono rilasciati anche i numeri e vengono acquisiti numeri dispari. E poiché stai utilizzando un valore monotonicamente crescente per il blocco virtuale, stai anche evitando lo ABA problem. La cosa più importante, tuttavia, è che si continua a ciclo durante il tentativo di leggere fino a quando si osserva il valore di blocco virtuale per essere gli stessi prima dell'inizio di lettura rispetto a dopo che completa. Altrimenti, consideri questa una lettura fallita e riprova tutto da capo. Quindi sì, lavoro ben fatto sulla logica di base.

E per quanto riguarda il posizionamento dei generatori di barriera di memoria? Bene, anche questo sembra abbastanza buono. Sono richieste tutte le chiamate Thread.MemoryBarrier. Se dovessi scegliere la nit-pick, direi che ne hai bisogno di uno aggiuntivo nel metodo Write in modo che assomigli a questo.

public void Write(T value) 
{ 
    // locks are full barriers 
    lock (write) 
    { 
     ++version;    // ++version odd: write in progress 
     Thread.MemoryBarrier(); 
     this.value = value; 
     Thread.MemoryBarrier(); 
     ++version;    // ++version even: write complete 
    } 
} 

La chiamata aggiunto qui assicura che ++version e this.value = value non ottengono scambiati. Ora, la specifica ECMA consente tecnicamente quel tipo di riordino delle istruzioni. Tuttavia, l'implementazione di Microsoft della CLI e dell'hardware x86 hanno già una semantica volatile sulle scritture, quindi non sarebbe necessaria nella maggior parte dei casi. Ma, chi lo sa, forse sarebbe necessario sul runtime Mono che punta alla CPU ARM.

Sul lato Read di cose che riesco a trovare nessun difetto. In effetti, il posizionamento delle chiamate che hai è esattamente dove li avrei messi. Alcune persone potrebbero chiedersi perché non ne hai bisogno prima della lettura iniziale di version. Il motivo è perché il loop esterno catturerà il caso quando la prima lettura è stata memorizzata nella cache a causa dello Thread.MemoryBarrier più in basso.

Quindi questo mi porta a una discussione sulle prestazioni. È davvero più veloce di un blocco rigido nel metodo Read? Bene, ho fatto alcuni test approfonditi del tuo codice per aiutarti a rispondere. La risposta è un sì definitivo! Questo è un po 'più veloce di un blocco rigido. Ho provato a usare un Guid come tipo di valore perché è 128 bit e quindi è più grande della dimensione nativa della mia macchina (64 bit). Ho anche usato diverse varianti sul numero di scrittori e lettori. La tua tecnica di blocco basso ha costantemente e significativamente superato la tecnica del blocco rigido. Ho anche provato alcune varianti usando Interlocked.CompareExchange per eseguire la lettura protetta e anche loro sono stati più lenti. In effetti, in alcune situazioni è stato effettivamente più lento di prendere il blocco rigido. Devo essere onesto. Non ero affatto sorpreso da questo.

Ho fatto anche alcuni test di validità piuttosto significativi. Ho creato test che sarebbero durati per un po 'di tempo e non una volta ho visto una lettura lacerata. E poi come test di controllo avrei modificato il metodo Read in modo tale che sapevo che sarebbe stato scorretto e ho eseguito di nuovo il test. Questa volta, come previsto, le letture strappate hanno iniziato a comparire casualmente. Ho cambiato il codice in quello che hai e le letture strappate sono scomparse; di nuovo, come previsto. Questo sembrava confermare ciò che mi aspettavo già. Cioè, il tuo codice sembra corretto. Non ho una vasta gamma di ambienti hardware e di runtime con cui testare (né ho il tempo), quindi non sono disposto a dargli un sigillo di approvazione al 100%, ma penso di poter dare alla tua implementazione due pollici in su per adesso.

Infine, con tutto ciò che detto, eviterei comunque di metterlo in produzione. Sì, potrebbe essere corretto, ma il prossimo ragazzo che deve mantenere il codice probabilmente non lo capirà. Qualcuno potrebbe cambiare il codice e romperlo perché non capisce le conseguenze dei suoi cambiamenti. Devi ammettere che questo codice è piuttosto fragile. Anche il minimo cambiamento potrebbe romperlo.

Answer 2

Sembra che siete interessante in/implementazione aspettare-libera senza blocchi. Iniziamo da questa discussione, ad esempio: Lock-free multi-threading is for real threading experts