Primer SMP per Android

Le versioni della piattaforma Android 3.0 e successive sono ottimizzate per supportare architetture multiprocessore. Questo documento presenta i problemi che possono sorgere durante la scrittura di codice multithread per sistemi multiprocessore simmetrici in C, C++ e nel linguaggio di programmazione Java (di seguito denominato semplicemente "Java" per brevità). È inteso come un'introduzione per gli sviluppatori di app per Android, non come una discussione completa sull'argomento.

Introduzione

SMP è l'acronimo di "Symmetric Multi-Processor" (multiprocessore simmetrico). Descrive un design in cui due o più core della CPU identici condividono l'accesso alla memoria principale. Fino a qualche anno fa, tutti i dispositivi Android erano UP (Uni-Processor).

La maggior parte dei dispositivi Android, se non tutti, ha sempre avuto più CPU, ma in passato solo una di queste veniva utilizzata per eseguire le applicazioni, mentre le altre gestivano vari componenti hardware del dispositivo (ad esempio, la radio). Le CPU potevano avere architetture diverse e i programmi in esecuzione su di esse non potevano utilizzare la memoria principale per comunicare tra loro.

La maggior parte dei dispositivi Android venduti oggi è basata su design SMP, il che rende le cose un po' più complicate per gli sviluppatori di software. Le race condition in un programma multi-thread potrebbero non causare problemi visibili su un uniprocessore, ma potrebbero verificarsi regolarmente quando due o più thread vengono eseguiti contemporaneamente su core diversi. Inoltre, il codice potrebbe essere più o meno soggetto a errori se eseguito su architetture di processori diverse o anche su implementazioni diverse della stessa architettura. Il codice che è stato testato accuratamente su x86 potrebbe non funzionare correttamente su ARM. Il codice potrebbe iniziare a non funzionare se viene ricompilato con un compilatore più moderno.

Il resto di questo documento spiegherà il motivo e ti indicherà cosa devi fare per assicurarti che il tuo codice si comporti correttamente.

Modelli di coerenza della memoria: perché gli SMP sono un po' diversi

Questa è una panoramica rapida e superficiale di un argomento complesso. Alcune aree saranno incomplete, ma nessuna dovrebbe essere fuorviante o errata. Come vedrai nella sezione successiva, i dettagli qui di solito non sono importanti.

Consulta la sezione Ulteriori letture alla fine del documento per trovare indicazioni su trattazioni più approfondite dell'argomento.

I modelli di coerenza della memoria, o spesso semplicemente "modelli di memoria", descrivono le garanzie che il linguaggio di programmazione o l'architettura hardware fornisce in merito agli accessi alla memoria. Ad esempio, se scrivi un valore nell'indirizzo A e poi un valore nell'indirizzo B, il modello potrebbe garantire che ogni core della CPU veda le scritture nell'ordine in cui avvengono.

Il modello a cui la maggior parte dei programmatori è abituata è la coerenza sequenziale, descritta come segue (Adve & Gharachorloo):

• Tutte le operazioni di memoria sembrano essere eseguite una alla volta
• Tutte le operazioni in un singolo thread sembrano essere eseguite nell'ordine descritto dal programma del processore.

Supponiamo temporaneamente di avere un compilatore o un interprete molto semplice che non introduca sorprese: traduce le assegnazioni nel codice sorgente in istruzioni di caricamento e archiviazione esattamente nell'ordine corrispondente, un'istruzione per accesso. Per semplicità, supponiamo anche che ogni thread venga eseguito sul proprio processore.

Se esamini un po' di codice e vedi che esegue alcune letture e scritture dalla memoria, su un'architettura della CPU con coerenza sequenziale sai che il codice eseguirà queste letture e scritture nell'ordine previsto. È possibile che la CPU stia effettivamente riordinando le istruzioni e ritardando le letture e le scritture, ma non c'è modo per il codice in esecuzione sul dispositivo di capire che la CPU sta facendo qualcosa di diverso dall'eseguire le istruzioni in modo semplice. (Ignoreremo l'I/O del driver del dispositivo mappato in memoria).

Per illustrare questi punti, è utile considerare piccoli snippet di codice, comunemente chiamati test di verifica.

Ecco un semplice esempio, con il codice in esecuzione su due thread:

Thread 1	Thread 2
A = 3 B = 5	reg0 = B reg1 = A

In questo e in tutti i futuri esempi di litmus, le posizioni di memoria sono rappresentate da lettere maiuscole (A, B, C) e i registri della CPU iniziano con "reg". Tutta la memoria è inizialmente pari a zero. Le istruzioni vengono eseguite dall'alto verso il basso. In questo caso, il thread 1 memorizza il valore 3 nella posizione A e poi il valore 5 nella posizione B. Il thread 2 carica il valore dalla posizione B in reg0, quindi carica il valore dalla posizione A in reg1. (Tieni presente che scriviamo in un ordine e leggiamo in un altro).

Si presume che il thread 1 e il thread 2 vengano eseguiti su core della CPU diversi. Dovresti sempre fare questa ipotesi quando pensi al codice multi-thread.

La coerenza sequenziale garantisce che, dopo che entrambi i thread hanno terminato l'esecuzione, i registri si troveranno in uno dei seguenti stati:

Registrati	Stati
reg0=5, reg1=3	possibile (il thread 1 è stato eseguito per primo)
reg0=0, reg1=0	possibile (il thread 2 è stato eseguito per primo)
reg0=0, reg1=3	possibile (esecuzione simultanea)
reg0=5, reg1=0	mai

Per arrivare a una situazione in cui vediamo B=5 prima di vedere l'archiviazione in A, le letture o le scritture dovrebbero avvenire fuori ordine. Su una macchina con coerenza sequenziale, questo non può accadere.

I monoprocessori, inclusi x86 e ARM, sono normalmente coerenti in sequenza. I thread sembrano essere eseguiti in modo intercalato, poiché il kernel del sistema operativo passa da uno all'altro. La maggior parte dei sistemi SMP, inclusi x86 e ARM, non è coerente in modo sequenziale. Ad esempio, è comune che l'hardware memorizzi nel buffer gli store durante il loro percorso verso la memoria, in modo che non raggiungano immediatamente la memoria e non diventino visibili ad altri core.

I dettagli variano notevolmente. Ad esempio, x86, sebbene non sia coerente in modo sequenziale, garantisce comunque che reg0 = 5 e reg1 = 0 rimangano impossibili. Le operazioni di archiviazione vengono memorizzate nel buffer, ma il loro ordine viene mantenuto. ARM, invece, non lo fa. L'ordine degli store con buffer non viene mantenuto e gli store potrebbero non raggiungere tutti gli altri core contemporaneamente. Queste differenze sono importanti per i programmatori di assembly. Tuttavia, come vedremo di seguito, i programmatori C, C++ o Java possono e devono programmare in modo da nascondere queste differenze di architettura.

Finora abbiamo ipotizzato in modo irrealistico che solo l'hardware riordini le istruzioni. In realtà, anche il compilatore riordina le istruzioni per migliorare le prestazioni. Nel nostro esempio, il compilatore potrebbe decidere che un codice successivo nel Thread 2 ha bisogno del valore di reg1 prima di reg0 e quindi caricare prima reg1. In alternativa, un codice precedente potrebbe aver già caricato A e il compilatore potrebbe decidere di riutilizzare quel valore anziché caricare nuovamente A. In entrambi i casi, i caricamenti in reg0 e reg1 potrebbero essere riordinati.

Il riordinamento degli accessi a diverse posizioni di memoria, nell'hardware o nel compilatore, è consentito, poiché non influisce sull'esecuzione di un singolo thread e può migliorare significativamente le prestazioni. Come vedremo, con un po' di attenzione, possiamo anche evitare che influisca sui risultati dei programmi multithread.

Poiché anche i compilatori possono riordinare gli accessi alla memoria, questo problema non è in realtà nuovo per gli SMP. Anche su un uniprocessore, un compilatore potrebbe riordinare i caricamenti in reg0 e reg1 nel nostro esempio e il Thread 1 potrebbe essere pianificato tra le istruzioni riordinate. Tuttavia, se il nostro compilatore non riordinasse le istruzioni, potremmo non riscontrare mai questo problema. Sulla maggior parte degli SMP ARM, anche senza il riordinamento del compilatore, il riordinamento verrà probabilmente visualizzato, possibilmente dopo un numero molto elevato di esecuzioni riuscite. A meno che tu non stia programmando in linguaggio assembly, gli SMP generalmente aumentano la probabilità di riscontrare problemi che erano presenti fin dall'inizio.

Programmazione senza race condition dei dati

Fortunatamente, di solito esiste un modo semplice per evitare di pensare a questi dettagli. Se segui alcune regole semplici, di solito puoi ignorare tutta la sezione precedente, ad eccezione della parte relativa alla "coerenza sequenziale". Purtroppo, le altre complicazioni potrebbero diventare visibili se violi accidentalmente queste regole.

I linguaggi di programmazione moderni incoraggiano uno stile di programmazione noto come "data-race-free". Se prometti di non introdurre "race condition" ed eviti una serie di costrutti che dicono al compilatore il contrario, il compilatore e l'hardware promettono di fornire risultati coerenti in sequenza. Ciò non significa che evitino il riordinamento degli accessi alla memoria. Significa che se segui le regole, non potrai sapere se gli accessi alla memoria vengono riordinati. È un po' come dire che la salsiccia è un cibo delizioso e appetitoso, a patto che tu prometta di non visitare la fabbrica di salsicce. Le race condition dei dati rivelano la dura verità sul riordinamento della memoria.

Che cos'è una "race condition"?

Una race condition dei dati si verifica quando almeno due thread accedono contemporaneamente agli stessi dati ordinari e almeno uno di questi li modifica. Per "dati ordinari" intendiamo qualcosa che non è specificamente un oggetto di sincronizzazione destinato alla comunicazione tra thread. Mutex, variabili di condizione, variabili volatili Java o oggetti atomici C++ non sono dati ordinari e i loro accessi possono essere in competizione. In realtà, vengono utilizzati per impedire le race condition su altri oggetti.

Per determinare se due thread accedono contemporaneamente alla stessa posizione di memoria, possiamo ignorare la discussione sul riordinamento della memoria di cui sopra e assumere la coerenza sequenziale. Il seguente programma non presenta una race condition dei dati se A e B sono variabili booleane ordinarie inizialmente false:

Thread 1	Thread 2
if (A) B = true	if (B) A = true

Poiché le operazioni non vengono riordinate, entrambe le condizioni verranno valutate come false e nessuna delle due variabili verrà mai aggiornata. Di conseguenza, non può verificarsi una race condition dei dati. Non è necessario pensare a cosa potrebbe accadere se il caricamento da A e l'archiviazione in B nel Thread 1 venissero in qualche modo riordinati. Il compilatore non è autorizzato a riordinare il Thread 1 riscrivendolo come "B = true; if (!A) B = false". Sarebbe come fare salsicce in mezzo alla città in pieno giorno.

Le race condition sui dati sono definite ufficialmente su tipi integrati di base come numeri interi e riferimenti o puntatori. L'assegnazione a un int e la lettura simultanea in un altro thread è chiaramente una race condition dei dati. Tuttavia, sia la libreria standard C++ sia le librerie Java Collections sono scritte in modo da consentirti di ragionare sulle race condition anche a livello di libreria. Promettono di non introdurre race condition dei dati, a meno che non si verifichino accessi simultanei allo stesso container, di cui almeno uno lo aggiorna. L'aggiornamento di un set<T> in un thread mentre lo si legge contemporaneamente in un altro consente alla libreria di introdurre una race condition dei dati e può quindi essere considerato informalmente una "race condition dei dati a livello di libreria". Al contrario, l'aggiornamento di un set<T> in un thread, durante la lettura di un altro in un altro thread, non comporta una race condition dei dati, perché la libreria promette di non introdurre una race condition dei dati (di basso livello) in questo caso.

Normalmente, gli accessi simultanei a campi diversi in una struttura di dati non possono introdurre una data race. Tuttavia, esiste un'eccezione importante a questa regola: le sequenze contigue di campi di bit in C o C++ vengono trattate come un'unica "posizione di memoria". L'accesso a qualsiasi campo di bit in una sequenza di questo tipo viene considerato come l'accesso a tutti i campi di bit per determinare l'esistenza di una race condition dei dati. Ciò riflette l'incapacità dell'hardware comune di aggiornare singoli bit senza leggere e riscrivere anche i bit adiacenti. I programmatori Java non hanno problemi analoghi.

Evitare le race condition dei dati

I linguaggi di programmazione moderni forniscono una serie di meccanismi di sincronizzazione per evitare le race condition dei dati. Gli strumenti più basilari sono:

Blocchi o mutex

I mutex (std::mutex o pthread_mutex_t di C++11) o i blocchi synchronized in Java possono essere utilizzati per garantire che determinate sezioni di codice non vengano eseguite contemporaneamente ad altre sezioni di codice che accedono agli stessi dati. Ci riferiremo a queste e ad altre strutture simili genericamente come "chiuse". L'acquisizione coerente di un blocco specifico prima di accedere a una struttura di dati condivisa e il suo rilascio successivo impediscono le race condition durante l'accesso alla struttura di dati. Inoltre, garantisce che gli aggiornamenti e gli accessi siano atomici, ovvero che nessun altro aggiornamento della struttura dei dati possa essere eseguito nel frattempo. Questo è meritatamente lo strumento di gran lunga più comune per prevenire le race condition dei dati. L'utilizzo dei blocchi synchronized di Java o di lock_guard o unique_lock di C++ garantisce che i blocchi vengano rilasciati correttamente in caso di eccezione.

Variabili volatili/atomiche

Java fornisce campi volatile che supportano l'accesso simultaneo senza introdurre race condition. Dal 2011, C e C++ supportano variabili e campi atomic con semantica simile. In genere sono più difficili da usare rispetto ai blocchi, poiché garantiscono solo che i singoli accessi a una singola variabile siano atomici. (In C++ questo normalmente si estende a semplici operazioni di lettura-modifica-scrittura, come gli incrementi. Java richiede chiamate al metodo speciali per questo). A differenza dei blocchi, le variabili volatile o atomic non possono essere utilizzate direttamente per impedire ad altri thread di interferire con sequenze di codice più lunghe.

È importante notare che volatile ha significati molto diversi in C++ e Java. In C++, volatile non impedisce le race condition dei dati, anche se il codice precedente lo utilizza spesso come soluzione alternativa per la mancanza di oggetti atomic. Questa opzione non è più consigliata. In C++, utilizza atomic<T> per le variabili a cui possono accedere contemporaneamente più thread. volatile di C++ è destinato ai registri dei dispositivi e simili.

Le variabili C/C++ atomic o Java volatile possono essere utilizzate per evitare race condition dei dati su altre variabili. Se flag è dichiarato di tipo atomic<bool> o atomic_bool (C/C++) o volatile boolean (Java) ed è inizialmente false, lo snippet seguente è privo di data race:

Thread 1	Thread 2
A = ...   flag = true	while (!flag) {} ... = A

Poiché il Thread 2 attende l'impostazione di flag, l'accesso a A nel Thread 2 deve avvenire dopo, e non contemporaneamente, l'assegnazione a A nel Thread 1. Pertanto, non esiste una race condition dei dati su A. La race su flag non viene conteggiata come una race di dati, poiché gli accessi volatili/atomici non sono "accessi alla memoria ordinari".

L'implementazione è necessaria per impedire o nascondere il riordinamento della memoria in modo sufficiente per far sì che il codice come il litmus test precedente si comporti come previsto. In genere, questo rende gli accessi alla memoria volatile/atomica sostanzialmente più costosi rispetto agli accessi ordinari.

Sebbene l'esempio precedente sia privo di race condition, i blocchi insieme a Object.wait() in Java o alle variabili di condizione in C/C++ di solito forniscono una soluzione migliore che non comporta l'attesa in un loop durante il consumo della batteria.

Quando il riordinamento dei ricordi diventa visibile

La programmazione senza race condition dei dati normalmente ci evita di dover gestire esplicitamente i problemi di riordinamento dell'accesso alla memoria. Tuttavia, esistono diversi casi in cui il riordinamento diventa visibile:

1. Se il tuo programma presenta un bug che genera una race condition involontaria, le trasformazioni del compilatore e dell'hardware possono diventare visibili e il comportamento del programma potrebbe essere sorprendente. Ad esempio, se dimentichiamo di dichiarare flag volatile nell'esempio precedente, il Thread 2 potrebbe vedere un A non inizializzato. In alternativa, il compilatore potrebbe decidere che il flag non può cambiare durante il loop del Thread 2 e trasformare il programma in

   Thread 1	Thread 2
   A = ...   flag = true	reg0 = flag; while (!reg0) {} … = A

   Durante il debug, potresti notare che il loop continua all'infinito nonostante flag sia true.
2. C++ fornisce funzionalità per rilassare esplicitamente la coerenza sequenziale anche se non sono presenti race condition. Le operazioni atomiche possono accettare argomenti memory_order_… espliciti. Analogamente, il pacchetto java.util.concurrent.atomic fornisce un insieme più limitato di funzionalità simili, in particolare lazySet(). Inoltre, i programmatori Java a volte utilizzano data race intenzionali per ottenere un effetto simile. Tutte queste opzioni offrono miglioramenti delle prestazioni a un costo elevato in termini di complessità di programmazione. Ne parleremo solo brevemente di seguito.
3. Alcuni codici C e C++ sono scritti in uno stile precedente, non del tutto coerente con gli standard linguistici attuali, in cui vengono utilizzate variabili volatile anziché atomic e l'ordinamento della memoria è esplicitamente non consentito inserendo i cosiddetti fence o barrier. Ciò richiede un ragionamento esplicito sul riordinamento degli accessi e sulla comprensione dei modelli di memoria hardware. Uno stile di programmazione di questo tipo è ancora utilizzato nel kernel Linux. Non deve essere utilizzato nelle nuove app per Android e non verrà discusso ulteriormente qui.

Fai pratica

Il debug dei problemi di coerenza della memoria può essere molto difficile. Se una dichiarazione di blocco, atomic o volatile mancante fa sì che un codice legga dati obsoleti, potresti non essere in grado di capire il motivo esaminando i dump della memoria con un debugger. Quando puoi eseguire una query del debugger, i core della CPU potrebbero aver osservato l'intero insieme di accessi e i contenuti della memoria e dei registri della CPU sembreranno trovarsi in uno stato "impossibile".

Cosa non fare in C

Di seguito sono riportati alcuni esempi di codice errato, insieme a semplici modi per correggerli. Prima di farlo, dobbiamo discutere l'uso di una funzionalità di base del linguaggio.

C/C++ e "volatile"

Le dichiarazioni volatile C e C++ sono uno strumento per scopi molto specifici. Impediscono al compilatore di riordinare o rimuovere gli accessi volatile. Questo può essere utile per il codice che accede ai registri dei dispositivi hardware, alla memoria mappata in più posizioni o in relazione a setjmp. Tuttavia, C e C++ volatile, a differenza di Java volatile, non sono progettati per la comunicazione tra thread.

In C e C++, gli accessi ai dati volatile possono essere riordinati con gli accessi ai dati non volatili e non esistono garanzie di atomicità. Pertanto, volatile non può essere utilizzato per condividere dati tra thread nel codice portatile, nemmeno su un uniprocessore. In genere, C volatile non impedisce il riordinamento degli accessi da parte dell'hardware, quindi di per sé è ancora meno utile negli ambienti SMP multi-thread. Questo è il motivo per cui C11 e C++11 supportano gli oggetti atomic. Ti consigliamo di utilizzare queste opzioni.

Molto codice C e C++ precedente utilizza ancora in modo improprio volatile per la comunicazione tra thread. Spesso questo funziona correttamente per i dati che rientrano in un registro della macchina, a condizione che vengano utilizzati con barriere esplicite o nei casi in cui l'ordinamento della memoria non è importante. Tuttavia, non è garantito che funzioni correttamente con i compilatori futuri.

Esempi

Nella maggior parte dei casi, è meglio utilizzare un blocco (come un pthread_mutex_t o un std::mutex C++11) anziché un'operazione atomica, ma utilizzeremo quest'ultima per illustrare come verrebbe utilizzata in una situazione pratica.

MyThing* gGlobalThing = NULL;  // Wrong!  See below.
void initGlobalThing()    // runs in Thread 1
{
    MyStruct* thing = malloc(sizeof(*thing));
    memset(thing, 0, sizeof(*thing));
    thing->x = 5;
    thing->y = 10;
    /* initialization complete, publish */
    gGlobalThing = thing;
}
void useGlobalThing()    // runs in Thread 2
{
    if (gGlobalThing != NULL) {
        int i = gGlobalThing->x;    // could be 5, 0, or uninitialized data
        ...
    }
}

L'idea è che allochiamo una struttura, inizializziamo i suoi campi e, alla fine, la "pubblichiamo" memorizzandola in una variabile globale. A quel punto, qualsiasi altro thread può vederlo, ma va bene perché è completamente inizializzato, giusto?

Il problema è che l'archiviazione in gGlobalThing potrebbe essere osservata prima dell'inizializzazione dei campi, in genere perché il compilatore o il processore hanno riordinato le archiviazioni in gGlobalThing e thing->x. Un altro thread che legge da thing->x potrebbe vedere 5, 0 o persino dati non inizializzati.

Il problema principale è una race condition dei dati su gGlobalThing. Se il Thread 1 chiama initGlobalThing() mentre il Thread 2 chiama useGlobalThing(), gGlobalThing può essere letto mentre viene scritto.

Questo problema può essere risolto dichiarando gGlobalThing come atomico. In C++11:

atomic<MyThing*> gGlobalThing(NULL);

In questo modo, le scritture saranno visibili agli altri thread nell'ordine corretto. Inoltre, garantisce di impedire alcune altre modalità di errore che sono altrimenti consentite, ma che è improbabile che si verifichino su hardware Android reale. Ad esempio, garantisce che non possiamo vedere un puntatore gGlobalThing che è stato scritto solo parzialmente.

Cosa non fare in Java

Non abbiamo ancora parlato di alcune funzionalità pertinenti del linguaggio Java, quindi le esamineremo rapidamente.

Tecnicamente, Java non richiede che il codice sia privo di race condition dei dati. Inoltre, esiste una piccola quantità di codice Java scritto con molta attenzione che funziona correttamente in presenza di race condition dei dati. Tuttavia, la scrittura di questo codice è estremamente complessa e ne parleremo solo brevemente di seguito. A peggiorare le cose, gli esperti che hanno specificato il significato di questo codice non ritengono più che la specifica sia corretta. (La specifica è corretta per il codice senza race condition dei dati).

Per il momento, ci atteniamo al modello senza data race, per il quale Java fornisce essenzialmente le stesse garanzie di C e C++. Anche in questo caso, il linguaggio fornisce alcune primitive che rilassano esplicitamente la coerenza sequenziale, in particolare le chiamate lazySet() e weakCompareAndSet() in java.util.concurrent.atomic. Come per C e C++, per il momento li ignoreremo.

Parole chiave "synchronized" e "volatile" di Java

La parola chiave "synchronized" fornisce il meccanismo di blocco integrato del linguaggio Java. Ogni oggetto ha un "monitor" associato che può essere utilizzato per fornire un accesso reciprocamente esclusivo. Se due thread tentano di "sincronizzarsi" sullo stesso oggetto, uno dei due attenderà il completamento dell'altro.

Come accennato in precedenza, volatile T di Java è l'analogo di atomic<T> di C++11. Gli accessi simultanei ai campi volatile sono consentiti e non comportano race condition dei dati. Ignorando lazySet() e così via e le race condition dei dati, è compito della VM Java assicurarsi che il risultato appaia comunque coerente in modo sequenziale.

In particolare, se il thread 1 scrive in un campo volatile e il thread 2 legge successivamente dallo stesso campo e vede il valore appena scritto, anche il thread 2 vedrà tutte le scritture eseguite in precedenza dal thread 1. In termini di effetto sulla memoria, la scrittura su un volatile è analoga al rilascio di un monitor, mentre la lettura da un volatile è come l'acquisizione di un monitor.

C'è una differenza notevole rispetto a atomic di C++: se scriviamo volatile int x; in Java, x++ è uguale a x = x + 1; esegue un caricamento atomico, incrementa il risultato e poi esegue un'archiviazione atomica. A differenza di C++, l'incremento nel suo complesso non è atomico. Le operazioni di incremento atomico sono invece fornite da java.util.concurrent.atomic.

Esempi

Ecco un'implementazione semplice, ma errata, di un contatore monotonico: (Java theory and practice: Managing volatility).

class Counter {
    private int mValue;
    public int get() {
        return mValue;
    }
    public void incr() {
        mValue++;
    }
}

Supponiamo che get() e incr() vengano chiamati da più thread e vogliamo assicurarci che ogni thread veda il conteggio corrente quando viene chiamato get(). Il problema più evidente è che mValue++ è in realtà composto da tre operazioni:

1. reg = mValue
2. reg = reg + 1
3. mValue = reg

Se due thread vengono eseguiti contemporaneamente in incr(), uno degli aggiornamenti potrebbe andare perso. Per rendere atomico l'incremento, dobbiamo dichiarare incr() "synchronized".

Tuttavia, non funziona ancora, soprattutto su SMP. Esiste ancora una race condition, in quanto get() può accedere a mValue contemporaneamente a incr(). In base alle regole di Java, la chiamata get() può sembrare riordinata rispetto ad altro codice. Ad esempio, se leggiamo due contatori di seguito, i risultati potrebbero sembrare incoerenti perché le chiamate get() sono state riordinate dall'hardware o dal compilatore. Possiamo correggere il problema dichiarando get() come sincronizzato. Con questa modifica, il codice è ovviamente corretto.

Purtroppo, abbiamo introdotto la possibilità di conflitti di blocco, che potrebbero compromettere le prestazioni. Anziché dichiarare get() come sincronizzato, potremmo dichiarare mValue con "volatile". (Tieni presente che incr() deve comunque utilizzare synchronize, poiché altrimenti mValue++ non è una singola operazione atomica.) In questo modo si evitano anche tutte le race condition, preservando la coerenza sequenziale. incr() sarà un po' più lento, poiché comporta sia l'overhead di ingresso/uscita del monitor sia l'overhead associato a un archivio volatile, ma get() sarà più veloce, quindi anche in assenza di conflitti questo è un vantaggio se le letture superano di gran lunga le scritture. (Vedi anche AtomicInteger per un modo per rimuovere completamente il blocco sincronizzato.)

Ecco un altro esempio, simile nella forma ai precedenti esempi in C:

class MyGoodies {
    public int x, y;
}
class MyClass {
    static MyGoodies sGoodies;
    void initGoodies() {    // runs in thread 1
        MyGoodies goods = new MyGoodies();
        goods.x = 5;
        goods.y = 10;
        sGoodies = goods;
    }
    void useGoodies() {    // runs in thread 2
        if (sGoodies != null) {
            int i = sGoodies.x;    // could be 5 or 0
            ....
        }
    }
}

Questo ha lo stesso problema del codice C, ovvero che esiste una race condition dei dati su sGoodies. Pertanto, l'assegnazione sGoodies = goods potrebbe essere osservata prima dell'inizializzazione dei campi in goods. Se dichiari sGoodies con la parola chiave volatile, la coerenza sequenziale viene ripristinata e tutto funzionerà come previsto.

Tieni presente che solo il riferimento sGoodies è volatile. Gli accessi ai campi al suo interno non lo sono. Una volta che sGoodies è volatile e l'ordinamento della memoria è stato conservato correttamente, non è possibile accedere ai campi contemporaneamente. L'istruzione z = sGoodies.x eseguirà un caricamento volatile di MyClass.sGoodies seguito da un caricamento non volatile di sGoodies.x. Se crei un riferimento locale MyGoodies localGoods = sGoodies, un z = localGoods.x successivo non eseguirà caricamenti volatili.

Un idioma più comune nella programmazione Java è il famigerato "double-checked locking":

class MyClass {
    private Helper helper = null;
    public Helper getHelper() {
        if (helper == null) {
            synchronized (this) {
                if (helper == null) {
                    helper = new Helper();
                }
            }
        }
        return helper;
    }
}

L'idea è che vogliamo avere una singola istanza di un oggetto Helper associata a un'istanza di MyClass. Dobbiamo crearlo una sola volta, quindi lo creiamo e lo restituiamo tramite una funzione getHelper() dedicata. Per evitare una race condition in cui due thread creano l'istanza, dobbiamo sincronizzare la creazione dell'oggetto. Tuttavia, non vogliamo pagare l'overhead per il blocco "synchronized" su ogni chiamata, quindi eseguiamo questa parte solo se helper è attualmente null.

In questo caso, si verifica una race condition dei dati nel campo helper. Può essere impostato contemporaneamente a helper == null in un altro thread.

Per capire come questo può non riuscire, considera lo stesso codice riscritto leggermente, come se fosse compilato in un linguaggio simile a C (ho aggiunto un paio di campi interi per rappresentare l'attività del costruttore Helper’s):

if (helper == null) {
    synchronized() {
        if (helper == null) {
            newHelper = malloc(sizeof(Helper));
            newHelper->x = 5;
            newHelper->y = 10;
            helper = newHelper;
        }
    }
    return helper;
}

Non c'è nulla che impedisca all'hardware o al compilatore di riordinare l'archiviazione in helper con quella nei campi x/y. Un altro thread potrebbe trovare helper non null, ma i suoi campi non ancora impostati e pronti per l'uso. Per ulteriori dettagli e altre modalità di errore, consulta il link "'Double Checked Locking is Broken' Declaration" nell'appendice o l'articolo 71 ("Use lazy initialization judiciously") in Effective Java, 2nd Edition di Josh Bloch.

Esistono due modi per risolvere il problema:

1. Scegli la soluzione più semplice ed elimina il controllo esterno. In questo modo, non esaminiamo mai il valore di helper al di fuori di un blocco sincronizzato.
2. Dichiara helper volatile. Con questa piccola modifica, il codice nell'Esempio J-3 funzionerà correttamente su Java 1.5 e versioni successive. (Potresti voler dedicare un minuto a convincerti che sia vero.)

Ecco un altro esempio di comportamento di volatile:

class MyClass {
    int data1, data2;
    volatile int vol1, vol2;
    void setValues() {    // runs in Thread 1
        data1 = 1;
        vol1 = 2;
        data2 = 3;
    }
    void useValues() {    // runs in Thread 2
        if (vol1 == 2) {
            int l1 = data1;    // okay
            int l2 = data2;    // wrong
        }
    }
}

In useValues(), se il Thread 2 non ha ancora osservato l'aggiornamento di vol1, non può sapere se data1 o data2 è già stato impostato. Una volta visualizzato l'aggiornamento a vol1, sa che è possibile accedere a data1 in sicurezza e leggerlo correttamente senza introdurre una race condition. Tuttavia, non può fare alcuna ipotesi su data2, perché l'archiviazione è stata eseguita dopo l'archiviazione volatile.

Tieni presente che volatile non può essere utilizzato per impedire il riordinamento di altri accessi alla memoria in conflitto tra loro. Non è garantito che generi un'istruzione di barriera di memoria della macchina. Può essere utilizzato per evitare race condition dei dati eseguendo il codice solo quando un altro thread ha soddisfatto una determinata condizione.

Cosa fare

In C/C++, preferisci le classi di sincronizzazione C++11, come std::mutex. In caso contrario, utilizza le operazioni pthread corrispondenti. Queste includono le barriere di memoria appropriate, che forniscono un comportamento corretto (coerente in sequenza, se non diversamente specificato) ed efficiente su tutte le versioni della piattaforma Android. Assicurati di utilizzarli correttamente. Ad esempio, ricorda che le attese delle variabili di condizione possono restituire un valore in modo spurio senza essere segnalate e, pertanto, devono essere visualizzate in un loop.

È meglio evitare di utilizzare direttamente le funzioni atomiche, a meno che la struttura dei dati che stai implementando non sia estremamente semplice, come un contatore. Il blocco e lo sblocco di un mutex pthread richiedono una singola operazione atomica ciascuno e spesso costano meno di un singolo fallimento della cache, se non c'è conflitto, quindi non risparmierai molto sostituendo le chiamate mutex con operazioni atomiche. I design senza blocchi per strutture di dati non banali richiedono molta più attenzione per garantire che le operazioni di livello superiore sulla struttura di dati appaiano atomiche (nel loro insieme, non solo nelle parti esplicitamente atomiche).

Se utilizzi operazioni atomiche, l'ordinamento rilassato con memory_order… o lazySet() può offrire vantaggi in termini di prestazioni, ma richiede una comprensione più approfondita di quella che abbiamo fornito finora. In seguito, si scopre che una grande parte del codice esistente che utilizza questi elementi presenta bug. Se possibile, evita di utilizzarli. Se i tuoi casi d'uso non corrispondono esattamente a uno di quelli descritti nella sezione successiva, assicurati di essere un esperto o di averne consultato uno.

Evita di utilizzare volatile per la comunicazione tra thread in C/C++.

In Java, i problemi di concorrenza vengono spesso risolti al meglio utilizzando una classe di utilità appropriata del pacchetto java.util.concurrent. Il codice è ben scritto e ben testato su SMP.

Forse la cosa più sicura che puoi fare è rendere immutabili i tuoi oggetti. Gli oggetti di classi come String e Integer di Java contengono dati che non possono essere modificati una volta creato un oggetto, evitando così qualsiasi potenziale race condition su questi oggetti. Il libro Effective Java, 2nd Ed. contiene istruzioni specifiche in "Item 15: Minimize Mutability". Nota in particolare l'importanza di dichiarare i campi Java "final" (Bloch).

Anche se un oggetto è immutabile, ricorda che comunicarlo a un altro thread senza alcun tipo di sincronizzazione è una race condition. In Java, questo può essere accettabile in alcuni casi (vedi sotto), ma richiede grande attenzione e probabilmente genererà un codice fragile. Se non è estremamente critico per le prestazioni, aggiungi una dichiarazione volatile. In C++, la comunicazione di un puntatore o di un riferimento a un oggetto immutabile senza una sincronizzazione adeguata, come qualsiasi race condition, è un bug. In questo caso, è ragionevolmente probabile che si verifichino arresti anomali intermittenti poiché, ad esempio, il thread di ricezione potrebbe visualizzare un puntatore alla tabella dei metodi non inizializzato a causa del riordinamento dello spazio di archiviazione.

Se né una classe di libreria esistente né una classe immutabile sono appropriate, è necessario utilizzare l'istruzione Java synchronized o C++ lock_guard/unique_lock per proteggere gli accessi a qualsiasi campo a cui possono accedere più thread. Se i mutex non sono adatti alla tua situazione, devi dichiarare i campi condivisi volatile o atomic, ma devi prestare molta attenzione a comprendere le interazioni tra i thread. Queste dichiarazioni non ti salveranno dai comuni errori di programmazione simultanea, ma ti aiuteranno a evitare i misteriosi errori associati all'ottimizzazione dei compilatori e ai problemi di SMP.

Nel costruttore, devi evitare di "pubblicare" un riferimento a un oggetto, ovvero di renderlo disponibile ad altri thread. Questo è meno critico in C++ o se segui il nostro consiglio "no data races" in Java. Tuttavia, è sempre un buon consiglio e diventa fondamentale se il codice Java viene eseguito in altri contesti in cui il modello di sicurezza Java è importante e il codice non attendibile potrebbe introdurre una race condition accedendo al riferimento all'oggetto "esposto". È fondamentale anche se scegli di ignorare i nostri avvisi e di utilizzare alcune delle tecniche descritte nella sezione successiva. Per maggiori dettagli, consulta (Safe Construction Techniques in Java)

Qualche informazione in più sugli ordini di memoria deboli

C++11 e versioni successive forniscono meccanismi espliciti per allentare le garanzie di coerenza sequenziale per i programmi senza data race. Gli argomenti espliciti memory_order_relaxed, memory_order_acquire (solo caricamenti) e memory_order_release (solo archivi) per le operazioni atomiche forniscono ciascuno garanzie rigorosamente più deboli rispetto all'argomento predefinito, in genere implicito, memory_order_seq_cst. memory_order_acq_rel fornisce garanzie sia di memory_order_acquire che di memory_order_release per le operazioni atomiche di lettura-modifica-scrittura. memory_order_consume non è ancora sufficientemente specificato o implementato per essere utile e per il momento deve essere ignorato.

I metodi lazySet in Java.util.concurrent.atomic sono simili agli store memory_order_release di C++. Le variabili ordinarie di Java vengono talvolta utilizzate in sostituzione degli accessi memory_order_relaxed, anche se in realtà sono ancora più deboli. A differenza di C++, non esiste un vero e proprio meccanismo per gli accessi non ordinati alle variabili dichiarate come volatile.

In genere, dovresti evitarli, a meno che non ci siano motivi di prestazioni urgenti per utilizzarli. Sulle architetture di macchine con ordinamento debole come ARM, il loro utilizzo consente in genere di risparmiare nell'ordine di alcune decine di cicli di macchina per ogni operazione atomica. Su x86, il miglioramento delle prestazioni è limitato agli store ed è probabile che sia meno evidente. In modo un po' controintuitivo, il vantaggio potrebbe diminuire con un numero di core più elevato, poiché il sistema di memoria diventa un fattore più limitante.

La semantica completa delle operazioni atomiche con ordinamento debole è complessa. In generale, richiedono una comprensione precisa delle regole del linguaggio, che non approfondiremo qui. Ad esempio:

• Il compilatore o l'hardware possono spostare gli accessi memory_order_relaxed in una sezione critica (ma non fuori) delimitata da un'acquisizione e un rilascio di un blocco. Ciò significa che due archiviazioni memory_order_relaxed potrebbero diventare visibili fuori ordine, anche se sono separate da una sezione critica.
• Una normale variabile Java, se utilizzata in modo improprio come contatore condiviso, può sembrare a un altro thread che diminuisca, anche se viene incrementata solo da un altro thread. Ma questo non è vero per l'atomico C++ memory_order_relaxed.

Con questo avvertimento, qui forniamo un piccolo numero di idiomi che sembrano coprire molti dei casi d'uso per le operazioni atomiche con ordinamento debole. Molte di queste si applicano solo a C++.

Accessi non legati alle gare

È abbastanza comune che una variabile sia atomica perché a volte viene letta contemporaneamente a una scrittura, ma non tutti gli accessi presentano questo problema. Ad esempio, una variabile potrebbe dover essere atomica perché viene letta al di fuori di una sezione critica, ma tutti gli aggiornamenti sono protetti da un blocco. In questo caso, una lettura protetta dallo stesso blocco non può essere in competizione, poiché non possono esserci scritture simultanee. In questo caso, l'accesso non in competizione (caricamento in questo caso) può essere annotato con memory_order_relaxed senza modificare la correttezza del codice C++. L'implementazione del blocco applica già l'ordinamento della memoria richiesto rispetto all'accesso da parte di altri thread e memory_order_relaxed specifica che, in sostanza, non è necessario applicare ulteriori vincoli di ordinamento per l'accesso atomico.

Non esiste un vero e proprio analogo in Java.

Il risultato non è considerato affidabile per la correttezza

Quando utilizziamo un carico di gara solo per generare un suggerimento, in genere è anche accettabile non applicare alcun ordinamento della memoria per il carico. Se il valore non è affidabile, non possiamo utilizzare il risultato in modo affidabile per dedurre informazioni su altre variabili. Pertanto, non è un problema se l'ordinamento della memoria non è garantito e il caricamento viene fornito con un argomento memory_order_relaxed.

Un'istanza comune di questo è l'utilizzo di compare_exchange C++ per sostituire in modo atomico x con f(x). Il caricamento iniziale di x per calcolare f(x) non deve essere affidabile. Se sbagliamo, l'operazione compare_exchange non andrà a buon fine e riproveremo. È possibile che il caricamento iniziale di x utilizzi un argomento memory_order_relaxed; l'unica cosa che conta è l'ordinamento della memoria per il compare_exchange effettivo.

Dati modificati in modo atomico, ma non letti

A volte i dati vengono modificati in parallelo da più thread, ma non vengono esaminati fino al completamento del calcolo parallelo. Un buon esempio è un contatore che viene incrementato in modo atomico (ad esempio utilizzando fetch_add() in C++ o atomic_fetch_add_explicit() in C) da più thread in parallelo, ma il risultato di queste chiamate viene sempre ignorato. Il valore risultante viene letto solo alla fine, dopo che tutti gli aggiornamenti sono stati completati.

In questo caso, non è possibile stabilire se gli accessi a questi dati sono stati riordinati, pertanto il codice C++ potrebbe utilizzare un argomento memory_order_relaxed.

I contatori di eventi semplici sono un esempio comune di questo tipo. Poiché è così comune, vale la pena fare alcune osservazioni su questo caso:

• L'utilizzo di memory_order_relaxed migliora le prestazioni, ma potrebbe non risolvere il problema di prestazioni più importante: ogni aggiornamento richiede l'accesso esclusivo alla riga della cache che contiene il contatore. Questo comporta un fallimento della cache ogni volta che un nuovo thread accede al contatore. Se gli aggiornamenti sono frequenti e si alternano tra i thread, è molto più veloce evitare di aggiornare ogni volta il contatore condiviso, ad esempio utilizzando contatori locali dei thread e sommandoli alla fine.
• Questa tecnica è combinabile con la sezione precedente: è possibile leggere contemporaneamente valori approssimativi e non affidabili mentre vengono aggiornati, con tutte le operazioni che utilizzano memory_order_relaxed. Tuttavia, è importante considerare i valori risultanti come completamente inaffidabili. Il fatto che il conteggio sembri essere stato incrementato una volta non significa che un altro thread possa essere considerato come se avesse raggiunto il punto in cui è stato eseguito l'incremento. L'incremento potrebbe invece essere stato riordinato con il codice precedente. (Come nel caso simile menzionato in precedenza, C++ garantisce che un secondo caricamento di un contatore di questo tipo non restituirà un valore inferiore a un caricamento precedente nello stesso thread. A meno che, ovviamente, il contatore non abbia superato il limite.
• È comune trovare codice che tenta di calcolare valori di contatore approssimativi eseguendo singole letture e scritture atomiche (o meno), ma non rendendo l'incremento atomico nel suo complesso. L'argomento usuale è che questo è "sufficientemente vicino" per i contatori delle prestazioni o simili. In genere no. Quando gli aggiornamenti sono sufficientemente frequenti (un caso che probabilmente ti interessa), una grande parte dei conteggi viene in genere persa. Su un dispositivo quad-core, è comune perdere più della metà dei conteggi. (Esercizio semplice: crea uno scenario con due thread in cui il contatore viene aggiornato un milione di volte, ma il valore finale del contatore è uno).

Comunicazione semplice con i flag

Un'operazione di archiviazione memory_order_release (o un'operazione di lettura-modifica-scrittura) garantisce che se successivamente un'operazione di caricamento memory_order_acquire (o un'operazione di lettura-modifica-scrittura) legge il valore scritto, osserverà anche tutte le operazioni di archiviazione (ordinarie o atomiche) che hanno preceduto l'operazione di archiviazione memory_order_release. Al contrario, i caricamenti precedenti a memory_order_release non osserveranno i salvataggi successivi al caricamento memory_order_acquire. A differenza di memory_order_relaxed, ciò consente di utilizzare queste operazioni atomiche per comunicare l'avanzamento di un thread a un altro.

Ad esempio, possiamo riscrivere l'esempio di blocco con doppio controllo riportato sopra in C++ come segue:

class MyClass {
  private:
    atomic<Helper*> helper {nullptr};
    mutex mtx;
  public:
    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper == nullptr) {
        lock_guard<mutex> lg(mtx);
        myHelper = helper.load(memory_order_relaxed);
        if (myHelper == nullptr) {
          myHelper = new Helper();
          helper.store(myHelper, memory_order_release);
        }
      }
      return myHelper;
    }
};

Il caricamento di acquisizione e l'archiviazione di rilascio garantiscono che se vediamo un helper non nullo, vedremo anche i suoi campi inizializzati correttamente. Abbiamo anche incorporato l'osservazione precedente secondo cui i carichi non di gara possono utilizzare memory_order_relaxed.

Un programmatore Java potrebbe rappresentare helper come java.util.concurrent.atomic.AtomicReference<Helper> e utilizzare lazySet() come archivio di rilascio. Le operazioni di caricamento continueranno a utilizzare semplici chiamate get().

In entrambi i casi, l'ottimizzazione delle prestazioni si è concentrata sul percorso di inizializzazione, che difficilmente è fondamentale per le prestazioni. Un compromesso più leggibile potrebbe essere:

    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper != nullptr) {
        return myHelper;
      }
      lock_guard&ltmutex> lg(mtx);
      if (helper == nullptr) {
        helper = new Helper();
      }
      return helper;
    }

In questo modo, viene fornito lo stesso percorso rapido, ma si ricorre a operazioni predefinite e sequenzialmente coerenti sul percorso lento non critico per le prestazioni.

Anche in questo caso, è probabile che helper.load(memory_order_acquire) generi lo stesso codice sulle attuali architetture supportate da Android di un riferimento semplice (con coerenza sequenziale) a helper. In realtà, l'ottimizzazione più vantaggiosa in questo caso potrebbe essere l'introduzione di myHelper per eliminare un secondo caricamento, anche se un compilatore futuro potrebbe farlo automaticamente.

L'ordinamento di acquisizione/rilascio non impedisce che le operazioni di archiviazione vengano visibilmente ritardate e non garantisce che diventino visibili ad altri thread in un ordine coerente. Di conseguenza, non supporta un pattern di programmazione complicato, ma abbastanza comune, esemplificato dall'algoritmo di esclusione reciproca di Dekker: tutti i thread impostano prima un flag che indica che vogliono fare qualcosa; se un thread t nota che nessun altro thread sta tentando di fare qualcosa, può procedere in sicurezza, sapendo che non ci saranno interferenze. Nessun altro thread potrà procedere, poiché il flag di t è ancora impostato. Questo non funziona se si accede al flag utilizzando l'ordinamento acquire/release, poiché ciò non impedisce di rendere visibile il flag di un thread ad altri in ritardo, dopo che hanno proceduto erroneamente. Il valore predefinito memory_order_seq_cst lo impedisce.

Campi immutabili

Se un campo di un oggetto viene inizializzato al primo utilizzo e poi non viene più modificato, potrebbe essere possibile inizializzarlo e successivamente leggerlo utilizzando accessi con ordinamento debole. In C++, potrebbe essere dichiarata come atomic e accessibile tramite memory_order_relaxed, mentre in Java potrebbe essere dichiarata senza volatile e accessibile senza misure speciali. Ciò richiede che siano soddisfatte tutte le seguenti condizioni:

• Dovrebbe essere possibile capire dal valore del campo stesso se è già stato inizializzato. Per accedere al campo, il valore di test e ritorno del percorso rapido deve leggere il campo una sola volta. In Java, quest'ultimo è essenziale. Anche se il campo risulta inizializzato, un secondo caricamento potrebbe leggere il valore non inizializzato precedente. In C++, la regola "leggi una volta" è semplicemente una buona pratica.
• Sia l'inizializzazione che i caricamenti successivi devono essere atomici, nel senso che gli aggiornamenti parziali non devono essere visibili. Per Java, il campo non deve essere long o double. Per C++, è necessaria un'assegnazione atomica; la costruzione in loco non funzionerà, poiché la costruzione di un atomic non è atomica.
• Le inizializzazioni ripetute devono essere sicure, poiché più thread potrebbero leggere contemporaneamente il valore non inizializzato. In C++, questo generalmente deriva dal requisito "trivialmente copiabile" imposto per tutti i tipi atomici; i tipi con puntatori di proprietà nidificati richiederebbero la deallocazione nel costruttore di copia e non sarebbero banalmente copiabili. Per Java, sono accettabili alcuni tipi di riferimento:
• I riferimenti Java sono limitati a tipi immutabili contenenti solo campi final. Il costruttore del tipo immutabile non deve pubblicare un riferimento all'oggetto. In questo caso, le regole dei campi final di Java garantiscono che se un lettore vede il riferimento, vedrà anche i campi final inizializzati. C++ non ha un analogo di queste regole e i puntatori agli oggetti di proprietà non sono accettabili anche per questo motivo (oltre a violare i requisiti di "trivially copyable").

Note di chiusura

Sebbene questo documento non si limiti a scalfire la superficie, non riesce a fare più di un'incisione superficiale. Questo è un argomento molto ampio e approfondito. Alcune aree di approfondimento:

• I modelli di memoria Java e C++ effettivi sono espressi in termini di una relazione happens-before che specifica quando è garantito che due azioni si verifichino in un determinato ordine. Quando abbiamo definito una data race, abbiamo parlato in modo informale di due accessi alla memoria che avvengono "simultaneamente". Ufficialmente, questo significa che nessuno dei due eventi si verifica prima dell'altro. È utile apprendere le definizioni effettive di happens-before e synchronizes-with nel modello di memoria Java o C++. Sebbene la nozione intuitiva di "simultaneamente" sia generalmente sufficiente, queste definizioni sono istruttive, in particolare se stai pensando di utilizzare operazioni atomiche con ordinamento debole in C++. (L'attuale specifica Java definisce lazySet() solo in modo molto informale.)
• Scopri cosa è consentito e cosa non è consentito fare ai compilatori quando riordinano il codice. (La specifica JSR-133 contiene alcuni ottimi esempi di trasformazioni legali che portano a risultati imprevisti.)
• Scopri come scrivere classi immutabili in Java e C++. (Non si tratta solo di "non modificare nulla dopo la costruzione").
• Interiorizza i consigli nella sezione Concorrenza di Effective Java, 2nd Edition. Ad esempio, dovresti evitare di chiamare metodi che devono essere sottoposti a override all'interno di un blocco sincronizzato.
• Leggi le API java.util.concurrent e java.util.concurrent.atomic per scoprire cosa è disponibile. Valuta la possibilità di utilizzare annotazioni di contemporaneità come @ThreadSafe e @GuardedBy (da net.jcip.annotations).

La sezione Ulteriori letture nell'appendice contiene link a documenti e siti web che illustrano meglio questi argomenti.

Appendice

Implementazione degli archivi di sincronizzazione

(This isn’t something most programmers will find themselves implementing, but the discussion is illuminating.)

Per i tipi integrati di piccole dimensioni come int e l'hardware supportato da Android, le normali istruzioni di caricamento e archiviazione garantiscono che un'archiviazione venga resa visibile nella sua interezza o non venga resa visibile affatto a un altro processore che carica la stessa posizione. In questo modo, viene fornita senza costi una nozione di base di "atomicità".

Come abbiamo visto in precedenza, questo non è sufficiente. Per garantire la coerenza sequenziale, dobbiamo anche impedire il riordinamento delle operazioni e assicurarci che le operazioni di memoria diventino visibili ad altri processi in un ordine coerente. Si scopre che quest'ultimo è automatico sull'hardware supportato da Android, a condizione che facciamo scelte oculate per applicare il primo, quindi lo ignoriamo in gran parte qui.

L'ordine delle operazioni di memoria viene preservato impedendo il riordinamento sia da parte del compilatore sia da parte dell'hardware. Qui ci concentriamo su quest'ultimo.

L'ordinamento della memoria su ARMv7, x86 e MIPS viene applicato con istruzioni "fence" che impediscono approssimativamente alle istruzioni che seguono la barriera di diventare visibili prima delle istruzioni che la precedono. (Queste sono anche comunemente chiamate istruzioni "barriera", ma ciò rischia di creare confusione con le barriere in stile pthread_barrier, che fanno molto di più). Il significato preciso delle istruzioni di barriera è un argomento piuttosto complicato che deve affrontare il modo in cui interagiscono le garanzie fornite da più tipi diversi di barriere e come queste si combinano con altre garanzie di ordinamento solitamente fornite dall'hardware. Questa è una panoramica generale, quindi sorvoleremo su questi dettagli.

Il tipo più elementare di garanzia di ordinamento è quello fornito dalle operazioni atomiche memory_order_acquire e memory_order_release di C++: le operazioni di memoria che precedono un'archiviazione di rilascio devono essere visibili dopo un caricamento di acquisizione. Su ARMv7, questo viene applicato da:

• Precedere l'istruzione di archiviazione con un'istruzione di barriera adatta. In questo modo, si impedisce che tutti gli accessi alla memoria precedenti vengano riordinati con l'istruzione store. (Inoltre, impedisce inutilmente il riordinamento con un'istruzione di archiviazione successiva).
• Seguendo l'istruzione di caricamento con un'istruzione di barriera adatta, impedendo il riordinamento del caricamento con gli accessi successivi. (E ancora una volta fornendo un ordinamento non necessario con almeno i caricamenti precedenti).

Insieme, sono sufficienti per l'ordinamento di acquisizione/rilascio di C++. Sono necessarie, ma non sufficienti, per la coerenza sequenziale di Java volatile o C++ atomic.

Per capire cos'altro ci serve, considera il frammento dell'algoritmo di Dekker che abbiamo menzionato brevemente in precedenza. flag1 e flag2 sono variabili C++ atomic o Java volatile, entrambe inizialmente false.

Thread 1	Thread 2
flag1 = true if (flag2 == false)     critical-stuff	flag2 = true if (flag1 == false)     critical-stuff

La coerenza sequenziale implica che una delle assegnazioni a flagn deve essere eseguita per prima ed essere vista dal test nell'altro thread. Pertanto, non vedremo mai questi thread eseguire contemporaneamente le "operazioni critiche".

Tuttavia, la barriera richiesta per l'ordinamento acquire-release aggiunge barriere solo all'inizio e alla fine di ogni thread, il che non è utile in questo caso. Inoltre, dobbiamo assicurarci che se un'operazione di archiviazione volatile/atomic è seguita da un'operazione di caricamento volatile/atomic, le due operazioni non vengano riordinate. In genere, questo viene applicato aggiungendo una barriera non solo prima di un'archiviazione con coerenza sequenziale, ma anche dopo. (Anche in questo caso, si tratta di un'operazione molto più complessa di quanto richiesto, poiché questa barriera in genere ordina tutti gli accessi alla memoria precedenti rispetto a tutti quelli successivi).

Potremmo invece associare la barriera aggiuntiva a caricamenti sequenzialmente coerenti. Poiché le memorizzazioni sono meno frequenti, la convenzione che abbiamo descritto è più comune e utilizzata su Android.

Come abbiamo visto in una sezione precedente, dobbiamo inserire una barriera di archiviazione/caricamento tra le due operazioni. Il codice eseguito nella VM per un accesso volatile sarà simile al seguente:

carico volatile	volatile store
reg = A fence for "acquire" (1)	fence for "release" (2) A = reg fence for later atomic load (3)

Le architetture delle macchine reali comunemente forniscono più tipi di barriere, che ordinano diversi tipi di accessi e possono avere costi diversi. La scelta tra queste opzioni è sottile e influenzata dalla necessità di garantire che gli store siano resi visibili ad altri core in un ordine coerente e che l'ordinamento della memoria imposto dalla combinazione di più barriere sia composto correttamente. Per maggiori dettagli, consulta la pagina dell'Università di Cambridge con le mappature raccolte di atomics ai processori effettivi.

In alcune architetture, in particolare x86, le barriere "acquire" e "release" non sono necessarie, poiché l'hardware applica sempre implicitamente un ordinamento sufficiente. Pertanto, su x86 viene generato solo l'ultimo fence (3). Analogamente, su x86, le operazioni atomiche di lettura-modifica-scrittura includono implicitamente una barriera forte. Pertanto, non richiedono mai barriere. Su ARMv7 sono necessarie tutte le barriere di cui abbiamo parlato sopra.

ARMv8 fornisce istruzioni LDAR e STLR che applicano direttamente i requisiti dei caricamenti e degli archivi volatili Java o sequenzialmente coerenti C++. In questo modo si evitano i vincoli di riordinamento non necessari menzionati sopra. Il codice Android a 64 bit su ARM utilizza queste istruzioni; abbiamo scelto di concentrarci sul posizionamento delle barriere ARMv7 perché fa più luce sui requisiti effettivi.

Per approfondire

Pagine web e documenti che forniscono maggiori dettagli o ampiezza. Gli articoli più utili in generale si trovano più in alto nell'elenco.

Shared Memory Consistency Models: A Tutorial

Scritto nel 1995 da Adve e Gharachorloo, questo è un buon punto di partenza se vuoi approfondire i modelli di coerenza della memoria.
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf

Barriere di memoria

Un breve articolo che riassume i problemi.
https://en.wikipedia.org/wiki/Memory_barrier

Nozioni di base sui thread

An introduction to multi-threaded programming in C++ and Java, di Hans Boehm. Discussione sulle race condition dei dati e sui metodi di sincronizzazione di base.
http://www.hboehm.info/c++mm/threadsintro.html

Java Concurrency In Practice

Pubblicato nel 2006, questo libro tratta un'ampia gamma di argomenti in modo molto dettagliato. Altamente consigliato per chiunque scriva codice multi-thread in Java.
http://www.javaconcurrencyinpractice.com

Domande frequenti su JSR-133 (Java Memory Model)

Una breve introduzione al modello di memoria Java, con una spiegazione della sincronizzazione, delle variabili volatili e della costruzione dei campi finali. (Un po' datato, in particolare quando si parla di altri linguaggi.)
http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html

Validity of Program Transformations in the Java Memory Model

Una spiegazione piuttosto tecnica dei problemi rimanenti con il modello di memoria Java. Questi problemi non si applicano ai programmi senza race condition.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.1790&rep=rep1&type=pdf

Panoramica del pacchetto java.util.concurrent

La documentazione del pacchetto java.util.concurrent. Nella parte inferiore della pagina è presente una sezione intitolata "Memory Consistency Properties" (Proprietà di coerenza della memoria) che spiega le garanzie fornite dalle varie classi.
java.util.concurrent Riepilogo del pacchetto

Java Theory and Practice: Safe Construction Techniques in Java

Questo articolo esamina in dettaglio i pericoli dell'escape dei riferimenti durante la creazione degli oggetti e fornisce linee guida per i costruttori thread-safe.
http://www.ibm.com/developerworks/java/library/j-jtp0618.html

Java Theory and Practice: Managing Volatility

Un articolo interessante che descrive cosa puoi e non puoi fare con i campi volatili in Java.
http://www.ibm.com/developerworks/java/library/j-jtp06197.html

The “Double-Checked Locking is Broken” Declaration

Spiegazione dettagliata di Bill Pugh dei vari modi in cui il blocco con doppio controllo viene interrotto senza volatile o atomic. Sono inclusi C/C++ e Java.
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

[ARM] Barrier Litmus Tests and Cookbook

Una discussione sui problemi di ARM SMP, illustrata con brevi snippet di codice ARM. Se gli esempi in questa pagina non sono abbastanza specifici o se vuoi leggere la descrizione formale dell'istruzione DMB, leggi questo articolo. Descrive anche le istruzioni utilizzate per le barriere di memoria sul codice eseguibile (potenzialmente utili se generi codice al volo). Tieni presente che questo è precedente ad ARMv8, che supporta anche istruzioni aggiuntive per l'ordinamento della memoria e ha adottato un modello di memoria leggermente più forte. Per maggiori dettagli, consulta il manuale di riferimento dell'architettura ARM® ARMv8, per il profilo dell'architettura ARMv8-A.
http://infocenter.arm.com/help/topic/com.arm.doc.genc007826/Barrier_Litmus_Tests_and_Cookbook_A08.pdf

Linux Kernel Memory Barriers

Documentazione per le barriere di memoria del kernel Linux. Include alcuni esempi utili e grafica ASCII.
http://www.kernel.org/doc/Documentation/memory-barriers.txt

ISO/IEC JTC1 SC22 WG21 (standard C++) 14882 (linguaggio di programmazione C++), sezione 1.10 e clausola 29 ("Libreria di operazioni atomiche")

Bozza dello standard per le funzionalità delle operazioni atomiche C++. Questa versione è vicina allo standard C++14, che include modifiche minori in quest'area rispetto a C++11.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4527.pdf
(intro: http://www.hpl.hp.com/techreports/2008/HPL-2008-56.pdf)

ISO/IEC JTC1 SC22 WG14 (standard C) 9899 (linguaggio di programmazione C) capitolo 7.16 ("Atomics <stdatomic.h>")

Bozza dello standard per le funzionalità delle operazioni atomiche C ISO/IEC 9899-201x. Per maggiori dettagli, consulta anche i report sui difetti successivi.
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

Mappature C/C++11 ai processori (University of Cambridge)

Raccolta di Jaroslav Sevcik e Peter Sewell di traduzioni di atomiche C++ in vari set di istruzioni di processori comuni.
http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html

Algoritmo di Dekker

La "prima soluzione corretta nota al problema della mutua esclusione nella programmazione concorrente". L'articolo di Wikipedia contiene l'algoritmo completo, con una discussione su come dovrebbe essere aggiornato per funzionare con i moderni compilatori di ottimizzazione e l'hardware SMP.
https://en.wikipedia.org/wiki/Dekker's_algorithm

Commenti su ARM e Alpha e dipendenze degli indirizzi

Un'email sulla mailing list arm-kernel di Catalin Marinas. Include un buon riepilogo delle dipendenze di indirizzo e controllo.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2009-05/msg11811.html

What Every Programmer Should Know About Memory

Un articolo molto lungo e dettagliato sui diversi tipi di memoria, in particolare le cache della CPU, di Ulrich Drepper.
http://www.akkadia.org/drepper/cpumemory.pdf

Reasoning about the ARM weakly consistent memory model

Questo documento è stato scritto da Chong e Ishtiaq di ARM, Ltd. e tenta di descrivere il modello di memoria ARM SMP in modo rigoroso ma accessibile. La definizione di "osservabilità" utilizzata qui proviene da questo documento. Anche in questo caso, si tratta di un'architettura precedente ad ARMv8.
http://portal.acm.org/ft_gateway.cfm?id=1353528&type=pdf&coll=&dl=&CFID=96099715&CFTOKEN=57505711

The JSR-133 Cookbook for Compiler Writers

Doug Lea ha scritto questo documento come complemento alla documentazione JSR-133 (Java Memory Model). Contiene l'insieme iniziale di linee guida per l'implementazione del modello di memoria Java utilizzato da molti autori di compilatori, che è ancora ampiamente citato e probabilmente fornisce informazioni utili. Purtroppo, le quattro varietà di barriere descritte qui non sono adatte alle architetture supportate da Android e le mappature C++11 riportate sopra sono ora una fonte migliore di ricette precise, anche per Java.
http://g.oswego.edu/dl/jmm/cookbook.html

x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors

Una descrizione precisa del modello di memoria x86. Purtroppo, le descrizioni precise del modello di memoria ARM sono molto più complicate.
http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf